JP6702035B2 - Class estimating device, class estimating method, and class estimating program - Google Patents

Description

  The present invention relates to a class estimating device, a class estimating method, and a class estimating program.

  RDF (Resource Description Framework), which has been attracting attention in recent years, is a data format that describes the relationship between resources existing on the Web with three elements, "subject," "predicate," and "object." A resource represents an entity such as a person or thing, and is uniquely identified by a URI (Uniform Resource Identifier). The “subject” and “predicate” are resources, and the “object” is a resource or a character string (referred to as “literal”). RDF is generally represented by a directed graph having resources as nodes, and represents the relationship between the subject and the object by connecting the resources with an edge having a predicate as a weight.

  Each resource of RDF belongs to a set of resources called a class. The class to which each resource belongs is described by the "predicate" "rdf:type". For example, "subject" "http://xxx/Einstein", "predicate" "rdf:type", "object" "http://xxx/person", and "subject" "http://xxx/ Consider the relationship between the resources "Einstein", "predicate" "rdf:type", "object" "http://xxx/scientist". In this case, "Einstein" belongs to the "person class" and the "scientist class". At this time, Einstein is an “instance” of the “person class” and the “scientist class”.

  Providing appropriate schema information to such enormous RDF resources on the Web is expected to promote smooth use of the RDF resources.

  For example, there is a technique for generating metadata of a document by extracting "subject", "predicate", "object" from the document. Also, regarding the search for information that matches a query graph pattern from a large amount of data with a graph structure, there is a technique for generating a query graph pattern that acquires information having a meaning structure related to information input by a user. is there.

JP, 2005-258659, A JP, 2006-313501, A

  However, existing RDF resources include a resource to which class information is added and a resource to which class information is not added. Therefore, for example, when RDF resources are collectively acquired using the class information, the resources to which the class information is not added are omitted from the acquisition result. Therefore, there is a problem that the ease of resource search is reduced and the user cannot use the resource smoothly.

  One aspect is to provide, for example, a class estimation device, a class estimation method, and a class estimation program that learn a class classification rule for appropriately assigning class information to an RDF resource whose class is unknown. And

  In one proposal, for example, the class estimation device determines the appearance probability of the class of each object corresponding to each predicate in the RDF learning data indicating the relationship information between resources with three elements of the subject, the predicate, and the object. Then, an index showing the diversity of classes of each object corresponding to each predicate is calculated. Then, the class estimation device acquires the second predicate when the object is the object corresponding to the first predicate whose index exceeds the predetermined threshold. Then, the class estimation device combines the first predicate and the second predicate to generate each feature including a predicate corresponding to the class of each subject and a combined predicate that combines the first predicate and the second predicate. To do. Then, the class estimation device, based on the correspondence between each subject class and each feature, aggregates the appearance frequencies at which each feature appears corresponding to each class, and for each feature from the aggregated appearance frequency, Learn the class classification rules that classify the classes given by

  As one aspect, for example, a class classification rule for appropriately assigning class information to an RDF resource whose class is unknown can be learned.

FIG. 1A is a diagram illustrating RDF. FIG. 1B is a diagram showing a graph representation of RDF. FIG. 1C is a diagram illustrating resource classes. FIG. 2 is a block diagram illustrating an example of the configuration of the class estimating device according to the embodiment. FIG. 3 is a flowchart illustrating an example of the learning phase process according to the embodiment. FIG. 4 is a flowchart illustrating an example of the ambiguity calculation process according to the embodiment. FIG. 5 is a flowchart illustrating an example of the feature generation processing according to the embodiment. FIG. 6 is a diagram illustrating an example of the acquired learning data according to the embodiment. FIG. 7 is a diagram illustrating an example of the object class of the learning data according to the embodiment. FIG. 8 is a diagram showing an example of the list L1 in which the predicates included in the learning data according to the embodiment are listed by eliminating duplication. FIG. 9 is a diagram illustrating an example of calculation of the appearance probability of the object class according to the embodiment. FIG. 10 is a diagram illustrating an example of the expanded predicate storage list according to the embodiment. FIG. 11 is a diagram illustrating an example of a list L2 in which the subject included in the learning data according to the embodiment is listed by eliminating duplication. FIG. 12 is a diagram illustrating an example of expansion of the graph according to the embodiment. FIG. 13 is a diagram illustrating an example of the feature list according to the embodiment. FIG. 14 is a diagram illustrating an example of the class classification rule (the appearance frequency of each feature in each class) according to the embodiment. FIG. 15 is a flowchart illustrating an example of the classification phase process according to the embodiment. FIG. 16 is a diagram illustrating an example of the acquired class estimation target data according to the example. FIG. 17 is a diagram illustrating an example of a feature list of class estimation target data according to the embodiment. FIG. 18 is a diagram illustrating an example of class estimation according to the embodiment. FIG. 19 is a diagram illustrating an example of calculating the appearance probability of an object class according to another application example of the embodiment. FIG. 20 is a diagram illustrating an example of expansion of a graph according to another application example of the embodiment. FIG. 21 is a diagram showing an example of a classification rule (appearance frequency of each feature in each class) according to another application example of the embodiment.

  Hereinafter, a class estimation device, a class estimation method, and a class estimation program according to an embodiment will be described with reference to the accompanying drawings. The disclosed embodiments do not limit the disclosed technology. Further, the respective embodiments may be appropriately combined within a range that does not contradict. Further, in the following description of the embodiments, only the configuration related to the disclosed technology will be described, and description of the other configurations will be omitted. Further, in the following description of the embodiments, the later description of the same or similar configuration or processing that has already been described will be omitted.

  As shown in FIG. 1A, in the following embodiment, RDF (Resource Description Framework) is a combination of “subject”, “predicate”, and “object” in a data format that describes the relationship between resources existing on the Web. is there. FIG. 1A is a diagram illustrating RDF.

  A resource represents an entity such as a person or thing, and is uniquely identified by a URI (Uniform Resource Identifier). The “subject” and “predicate” are resources, and the “object” is a resource or a character string (referred to as “literal”). FIG. 1A shows three relationships of “subject”, “predicate” and “object”. “Http://xxx/Einstein” “http://xxx/name” “Albert Einstein”, “http://xxx/Einstein” “http://xxx/affiliation” “http://xxx/ZU "University", "http://xxx/Einstein", "http://xxx/field" "http://xxx/physics". The "object" "Albert Einstein" is a literal.

  Further, as shown in FIG. 1B, for example, the RDF indicating the relationship between “subject”, “predicate” and “object” in FIG. 1A has resources (“subject” and “object”) as nodes and “predicate” as a node. Resources are connected by directed edges as weights. As a result, the RDF indicating the relationship between the “subject”, the “predicate”, and the “object” is represented by a directed graph showing the relationship between the subject and the object. FIG. 1B is a diagram showing a graph representation of RDF.

  Further, as shown in FIG. 1C, in the following embodiment, each resource of RDF belongs to a set of resources called a class, and a resource belonging to the set of classes is an instance of the corresponding class. FIG. 1C is a diagram illustrating resource classes.

  In FIG. 1C, “http://xxx/Einstein” “rdf:type” “http://xxx/person”, “http://xxx/Einstein” “rdf:type” “http://xxx/science” The relationship between two "subjects", "predicates" and "objects" is shown. In FIG. 1C, “subject” “http://xxx/Einstein” belongs to the classes “person” and “scientist”. Note that rdf:type is an abbreviation for “http://www.w3.org/1999/02/22-rdf-syntax-ns#type”.

(Class estimation device according to an embodiment)
FIG. 2 is a block diagram illustrating an example of the configuration of the class estimating device according to the embodiment. The class estimation device 10 according to the embodiment includes an ambiguity calculation unit 11, an expansion predicate storage unit 12, a feature generation unit 13, a classification rule learning unit 14, a class classification rule storage unit 15, and a class estimation unit 16. The expansion predicate storage unit 12 and the class classification rule storage unit 15 are volatile or non-volatile storage devices.

  The ambiguity calculation unit 11 calculates the ambiguity of the object with respect to the input learning data (RDF resource), determines a predicate to be expanded, and stores it in the expanded predicate storage unit 12. The expansion predicate storage unit 12 stores the expansion result of the predicate expanded by the ambiguity calculation unit 11. The feature generation unit 13 refers to the expansion predicate storage unit 12 to determine a node to be expanded, and generates a feature from the input learning data (RDF resource).

  The feature means an input in machine learning for learning an output for an input based on actual data. For example, in an example in which learning data is created from a resource that is a “subject”, a class is estimated by using a “predicate” corresponding to the resource as a feature. Then, when a “predicate” other than “rdf:type” is input as a feature, learning is performed as an example of outputting each class corresponding to the “object” of the “predicate” “rdf:type”.

  The classification rule learning unit 14 learns the class classification rules from the features generated by the feature generation unit 13, and stores the learned class classification rules in the class classification rule storage unit 15. The class classification rule storage unit 15 stores the class classification rules learned by the classification rule learning unit 14.

  The feature generation unit 13 also refers to the expansion predicate storage unit 12 to determine a node to be expanded, and generates a feature from the input class estimation target data (RDF resource). The class estimation unit 16 estimates a class from the features of the class estimation target data (RDF resource) generated by the feature generation unit 13 using the class classification rules stored in the class classification rule storage unit 15, and the class estimation is performed. Output the result.

  Note that the ambiguity calculation unit 11 determines, based on the occurrence probability of each object class corresponding to each predicate in the RDF learning data indicating at least three elements of the subject, the predicate, and the object, the relationship information between the resources. It is an example of a calculation unit that calculates an index indicating the variety of classes of each object corresponding to each predicate. In addition, the feature generation unit 13 acquires a second predicate in the case where an object corresponding to a first predicate whose index exceeds a predetermined threshold is the subject, combines the first predicate and the second predicate, and It is an example of a generation unit that generates each feature including a predicate corresponding to a subject class and a combination predicate that combines a first predicate and a second predicate. Further, the classification rule learning unit 14 aggregates the appearance frequencies in which each feature appears corresponding to each class, based on the correspondence relationship between each subject class and each feature, and calculates each feature from the aggregated appearance frequency. 3 is an example of a learning unit that learns a class classification rule that classifies a class assigned to a. Further, the class estimation unit 16 refers to the class classification rule, calculates the sum of the appearance frequencies in which the input features appear in each class, and outputs the class whose sum exceeds the threshold value as the estimated class estimated from the features. It is an example of an estimation unit.

(Learning phase process according to the embodiment)
FIG. 3 is a flowchart illustrating an example of the learning phase process according to the embodiment. First, the ambiguity calculation unit 11 acquires learning data (RDF resource) (step S11). The learning data acquired by the ambiguity calculating unit 11 in step S11 is, for example, the learning data D1 illustrated in FIG. FIG. 6 is a diagram illustrating an example of the acquired learning data according to the embodiment.

  Next, the ambiguity calculation unit 11 determines that the "predicate" whose class is undetermined is "http://xxx/field" "http://xxx/nationality" in the learning data D1 acquired in step S11. A known class is acquired for the "object" of the record "http://xxx/belonging" (step S12). The "object" of the record of "predicate" "http://xxx/field" "http://xxx/nationality" "http://xxx/affiliation" whose class is undetermined is "http:// xxx/Physics "http://xxx/Japan" "http://xxx/KY University" "http://xxx/A Music" "http://xxx/S Manufacturing". FIG. 7 is a diagram illustrating an example of the object class of the learning data according to the embodiment.

  The class data D2 shown in FIG. 7 is “http://xxx/physics” “http://xxx/Japan” “http://xxx/KY University” “http://xxx/A music” “http The following shows each class acquired with "://xxx/S Seisakusho" as the "subject". Each class is “http://xxx/academic” “http://xxx/country” “http://xxx/university” “http://xxx/company”.

  Next, the ambiguity calculation unit 11 calculates the ambiguity of the object with respect to the predicate for the resource in the learning data D1 and determines the predicate to be developed, and stores the determined predicate in the expanded predicate storage unit 12 (ambiguity Calculation processing, step S13). Details of the ambiguity calculation process will be described later with reference to FIG.

  Next, the feature generation unit 13 refers to the expansion predicate storage unit 12 for the resource in the learning data D1 and expands the object to generate a feature (feature generation process, step S14). Details of the feature generation processing will be described later with reference to FIG.

  Next, the classification rule learning unit 14 learns the class classification rules from the features generated in step S14 and stores them in the class classification rule storage unit 15 (step S15). When step S15 ends, the class estimation device 10 ends the learning phase process according to the embodiment. The details of the classification rule will be described later with reference to FIG.

(Ambiguity calculation processing according to the embodiment)
FIG. 4 is a flowchart illustrating an example of the ambiguity calculation process according to the embodiment. First, the ambiguity calculation unit 11 enumerates the predicates included in the learning data D1 acquired in step S11 of FIG. 3 without duplication and stores them in the list L1 (step S13-1).

  FIG. 8 is a diagram showing an example of the list L1 in which the predicates included in the learning data according to the embodiment are listed by eliminating duplication. As shown in FIG. 8, the ambiguity calculation unit 11 eliminates the duplication of the “predicate” excluding the “rdf:type” representing the class in the learning data D1, “http://xxx/field” “http: Store "xxx/nationality" "http://xxx/affiliation" "http://xxx/name" in the list L1.

  Next, the ambiguity calculation unit 11 performs the processing of steps S13-3 to S13-5 described below for all the predicates stored in the list L1 in which the "predicate" is stored in step S13-1. It is determined whether or not (step S13-2). When all the predicates in the list L1 have been processed (step S13-2: Yes), the ambiguity calculation unit 11 ends the ambiguity calculation process and moves the process to step S14 in FIG. On the other hand, when the ambiguity calculation unit 11 has not processed all the predicates in the list L1 (step S13-2: No), the ambiguity calculation unit 11 moves the process to step S13-3.

  In step S13-3, the ambiguity calculation unit 11 selects one unprocessed predicate from the list L1 and determines whether the object of this predicate P is a literal. When the object of the predicate P is a literal (step S13-3: Yes), the ambiguity calculation unit 11 returns the process to step S13-2. On the other hand, when the object of the predicate P is not a literal (step S13-3: No), the ambiguity calculator 11 shifts the processing to step S13-4.

  In step S13-4, the ambiguity calculation unit 11 calculates the appearance probability of the class of the corresponding object in the learning data D1 for the unprocessed predicate P, and calculates the threshold value from the number of appearances of the class. The process of step S13-4 will be described with reference to FIG. FIG. 9 is a diagram illustrating an example of calculation of the appearance probability of the object class according to the embodiment.

  The appearance probability of a class of object is calculated for all resources to determine the ambiguity of the object for each predicate to determine in which predicate the object is expanded. First, for each predicate, the probability of occurrence of the class of the corresponding object is examined. Since there are some objects whose classes are not known in the actual data, only the objects whose classes are known are to be calculated for the appearance probability.

  In the example shown in FIG. 9, for the "predicate" "field (abbreviation of'http://xxx/' in field http://xxx/ field, the same applies below)", the corresponding "object" is not a literal Since the class that appears is one of “study”, the appearance probability of “study” is 1. As for the “predicate” and “affiliation”, the corresponding “object” is not a literal and the classes that appear are “university”, “company”, and “company”. The appearance probability of "1/3" and "company" is 2/3. Regarding the "predicate" and "nationality", the corresponding "object" that appears is not a literal, and the class that appears is "country", so the probability of appearance of "country" is 1. ..

Further, the maximum value of entropy for each “predicate” is log ₂ N, where N is the number of classes that appear, so (log ₂ N)/2 is the threshold for determining entropy, which will be described later. To do. Whether or not to expand the object is determined by dynamically changing the threshold according to the characteristics of the learning data D1 such as the threshold for determining the entropy threshold, for example, (log ₂ N)/2. You can judge appropriately.

Next, in step S13-5, the ambiguity calculation unit 11 causes the entropy S(S=−Σplog ₂ p;p of the appearance probability of each class to be the appearance probability of each class, and Σ to be the sum of all classes). Represents) is calculated. Then, when the entropy S is larger than the threshold calculated in step S13-4, the ambiguity calculation unit 11 stores the predicate P that is the current processing target in the expanded predicate storage unit 12. The entropy S indicates the ambiguity of the class of the object, and the larger the value, the more ambiguous the object is for each predicate. When the entropy S exceeds the threshold value, the corresponding object is expanded.

The ambiguity calculation unit 11 calculates the ambiguity of the object class (entropy S based on the appearance probability of each class) from the appearance probability of the object class for each predicate. The entropy S of the appearance probability of each class calculated by the ambiguity calculation unit 11 will be described with reference to the example of FIG. 9. In FIG. 9, since the class that appears in the “predicate” and “field” is one of “scholarship”, the ambiguity calculation unit 11 calculates entropy S=−1×log ₂ 1=0. Further, in this case, the ambiguity calculation unit 11 calculates the threshold value as (log ₂ N)/2=(log ₂ 1)/2=0. Therefore, the ambiguity calculation unit 11 saves the “predicate” and the “field” in the expanded predicate storage unit 12 because the condition that the “predicate” and the “field” has the entropy S=threshold and the entropy S is larger than the threshold. do not do. In other words, the class of the “object” that precedes the “predicate” and the “field” does not have a wide variety of possible resource resources, and the ambiguity is small.

In FIG. 9, in the "predicate" and "belonging", the class "university" appears with a probability of 1/3, and the class "company" appears with a probability of 2/3. From this, the ambiguity calculation unit 11 calculates that entropy S=−{(1/3)×log ₂ (1/3)+(2/3)×log ₂ (2/3)}≈0.92 To do. In addition, in this case, the ambiguity calculation unit 11 calculates the threshold as (log ₂ N)/2=(log ₂ 2)/2=0.5. Therefore, the ambiguity calculation unit 11 expands the "predicate" and "belonging" because the condition that "predicate" and "belonging" is entropy S>threshold, and entropy S is larger than the threshold. It is stored in the predicate storage list L and stored. In other words, the class of the “object” that precedes the “predicate” and “belongs” has a wide variety of possible class resources and is highly ambiguous. FIG. 10 is a diagram illustrating an example of the expanded predicate storage list according to the embodiment.

Further, in FIG. 9, since only the class of “country” appears in the “predicate” and “nationality”, the ambiguity calculation unit 11 calculates entropy S=−1×log ₂ 1=0. In this case, the ambiguity calculation unit 11 calculates the threshold as (log ₂ 1)/2=(log ₂ 1)/2=0. Therefore, the ambiguity calculation unit 11 stores the "predicate" and "nationality" in the expanded predicate storage unit 12 because the condition that the "predicate" and "nationality" are entropy S=threshold and the entropy S is larger than the threshold is not satisfied. do not do. In other words, the class of the “object” that precedes the “predicate” and “nationality” does not have a variety of possible class resources, and the ambiguity is small.

  When step S13-5 ends as described above, the ambiguity calculation unit 11 shifts the processing to step S13-2.

(Feature generation processing according to the embodiment)
FIG. 5 is a flowchart illustrating an example of the feature generation processing according to the embodiment. First, the feature generation unit 13 enumerates the subjects included in the learning data D1 acquired in step S11 of FIG. 3 without duplication and stores them in the list L2 (step S14-1).

  FIG. 11 is a diagram illustrating an example of a list L2 in which the subject included in the learning data according to the embodiment is listed by eliminating duplication. As shown in FIG. 11, the feature generation unit 13 eliminates duplication of the “subject” in the learning data D1 “http://xxx/Hideki Yukawa” “http://xxx/Ryuji Sakamoto” “http: //xxx/Ichiro Tanaka” is stored in the list L2 as a learning target resource.

  Next, the feature generation unit 13 performs the processes of steps S14-3 to S14-4 described below for all the learning target resources stored in the list L2 in which the learning target resources are stored in step S14-1. It is determined whether or not it has been performed (step S14-2). When the feature generation unit 13 has processed all the learning target resources in the list L2 (step S14-2: Yes), the feature generation process ends and the process proceeds to step S15 in FIG. On the other hand, when the feature generation unit 13 has not processed all the learning target resources in the list L2 (step S14-2: No), the process proceeds to step S14-3.

  In step S14-3, the feature generation unit 13 selects one unprocessed learning target resource from the list L2, and expands this learning target resource R when it has a predicate included in the expansion predicate storage unit 12. Get the predicate. That is, when the ambiguity of the class of the object with respect to the predicate is high, the feature generation unit 13 expands the previous graph of the corresponding object in the RDF graph representation.

  The expansion of the graph will be described with reference to FIG. FIG. 12 is a diagram illustrating an example of expansion of the graph according to the embodiment. In FIG. 12, "predicate" and "affiliation" are expansion targets, and "field" and "nationality" are not expansion targets. As shown in FIG. 12, "predicate", "affiliation" and the following are expanded for each of "subject", "Hideki Yukawa", "Ryuji Sakamoto", and "Ichiro Tanaka", and each predicate after expansion is acquired. In the example of FIG. 12, the predicate after the expansion of the “predicate” and “affiliation” for the “subject” “Hideki Yukawa” is “President” and “Faculty”. In addition, the predicate after the expansion of the "predicate" and "affiliation" for the "subject" "Ryuji Sakamoto" is "president" "work". Further, the predicate after the expansion of the "predicate" and "affiliation" for the "subject" and "Ichiro Tanaka" is "president" and "product".

  Note that in the example of FIG. 12, the expansion of the “object” is performed up to one node ahead, but it may be expanded recursively up to multiple nodes ahead.

  Next, the feature generation unit 13 combines the predicate of the learning target resource R to be processed and the predicate of the expansion destination acquired in step S14-3, generates a feature from this combination, and stores the feature in the feature list L3 (step S14). -4). That is, the feature generation unit 13 generates a combination feature that combines the predicates of the graph before and after the expansion, and creates learning data for class classification. Generation of features will be described with reference to FIGS. 12 and 13. FIG. 13 is a diagram illustrating an example of the feature list according to the embodiment.

  For example, when the learning target resource R to be processed is the “subject” “Hideki Yukawa” shown in FIG. 12, the feature generation unit 13 expands the “predicate” “affiliation” ahead and expands the “affiliation” result. To obtain the "President" and "Undergraduate". Then, the feature generation unit 13 determines, based on the “predicate”, “field”, “affiliation”, “nationality”, “name”, and “principal” and “faculty”, “field, affiliation” as the feature of each of the “person” and “scientist”. , Nationality, name, affiliation+president, affiliation+faculty” are generated and stored in the feature list L3 shown in FIG.

  Further, when the learning target resource R to be processed is the “subject” “Ryuji Sakamoto” shown in FIG. 12, the feature generation unit 13 expands the “predicate” “affiliation” ahead, and expands the “affiliation” result. "President" "Work" is acquired. Then, the feature generation unit 13 uses the “predicate”, “affiliation”, “nationality”, “name”, and “president” “work” as the features of the class “person” and “composer”, respectively, “affiliation, nationality, name, "Affiliation+President, Affiliation+Works" is generated and stored in the feature list L3 shown in FIG.

  Further, when the learning target resource R to be processed is the “subject” “Ichiro Tanaka” shown in FIG. 12, the feature generation unit 13 expands the “predicate” “affiliation” ahead, and expands the “affiliation” result. "President" "Product" is acquired. Then, the feature generation unit 13 uses the "predicate", "affiliation", "nationality", "name", and "president" "product" as the features of the class "person" "company employee", "affiliation, nationality, name, "Affiliation+President, Affiliation+Product" is generated and stored in the feature list L3 shown in FIG.

  When step S14-4 ends, the feature generation unit 13 moves the process to step S14-2.

(Class classification rules according to the embodiment)
FIG. 14 is a diagram illustrating an example of the class classification rule (the appearance frequency of each feature in each class) according to the embodiment. The class classification rules are learned and generated in step S15 of FIG. The class classification rule R1 shown in FIG. 14 is generated from the frequency of appearance of each feature in each class in the feature list L3 shown in FIG.

  First, the classification rule learning unit 14 lists features that appear in the feature list L3 by eliminating duplication. The features appearing in the feature list L3 are, as shown in FIG. 14, "field" "affiliation" "nationality" "name" "affiliation + president" "affiliation + department" "affiliation + president" "affiliation + work" "affiliation" + Product”. “Affiliation+President”, “Affiliation+Faculty”, “Affiliation+President”, “Affiliation+Works”, and “Affiliation+Product” are features additionally acquired by expanding the graph of the object.

  Then, the classification rule learning unit 14 aggregates the frequencies of appearance of each feature in the class, and sets each aggregation result as a score. In the example shown in FIG. 14, the “field” appears once in each of the “person” and “scientist” classes. Therefore, the score of the "person" class of the "field" is "1", and the score of the "scientist" class is "1". The "affiliation" appears three times in the "person" class, once in the "scientist" class, once in the "composer" class, and once in the "company employee" class. Therefore, the score of "person" class of "affiliation" is "3", the score of "scientist" class is "1", the score of "composer" class is "1", the score of "office worker" class is " 1”.

  The same applies to "nationality", "name", "affiliation + president", "affiliation + department", "affiliation + president", "affiliation + work", "affiliation + product". As described above, the classification rule learning unit 14 generates the class classification rule R1 in which the feature and the score in each class are associated with each other, and stores the class classification rule storage unit 15 in the class classification rule storage unit 15.

  That is, the class classification rule R1 is a score obtained by aggregating the frequency of appearance of each feature corresponding to each class based on the correspondence relationship between each subject class and each feature, and for each feature The classification of classes to which each feature may belong is learned based on the score. Here, each feature is based on the occurrence probability of the class of each object corresponding to each predicate in the RDF learning data indicating at least three elements of the subject, the predicate, and the object. The second predicate in the case where the object corresponding to the first predicate whose index indicating the variety of the class of each object corresponding to is a subject is acquired, and the first predicate and the second predicate are acquired. Predicates are combined, and predicates corresponding to the classes of each subject and combination predicates that combine the first predicate and the second predicate are included.

  Such a class classification rule R1 expands a graph and adds features when the ambiguity of the object class for each predicate is high, and thus suppresses an increase in features and a decrease in learning and classification speed. At the same time, the accuracy of learning and classification can be improved.

(Classification phase process according to the embodiment)
FIG. 15 is a flowchart illustrating an example of the classification phase process according to the embodiment. First, the feature generation unit 13 acquires class estimation target data (RDF resource) (step S21). The class estimation target data acquired by the feature generation unit 13 in step S21 is, for example, the class estimation target data D3 shown in FIG. FIG. 16 is a diagram illustrating an example of the acquired class estimation target data according to the example.

  Next, the feature generation unit 13 refers to the expansion predicate storage unit 12 for the resource in the class estimation target data D3 acquired in step S21 and expands the object to generate a feature (feature generation process, step S22). . For details of the feature generation process of step S22, refer to the feature generation process of step S14 described above with reference to FIG. 5 by referring to “learning data D1” and “learning target resource R” as “class estimation target data D3” It is the same as the one read as "Resource R".

  The feature generation unit 13 obtains the features and combination features shown in the feature list D4 of FIG. 17 from the class estimation target data D3 shown in FIG. 16, for example, by the process of step S22. FIG. 17 is a diagram illustrating an example of a feature list of class estimation target data according to the embodiment. In the example shown in FIG. 17, the features obtained from the class estimation target data D3 are “affiliation”, “nationality”, “name”, and “affiliation+president” “affiliation+faculty” obtained from the expansion result of “affiliation”. Is.

  Next, the class estimation unit 16 classifies the features included in the feature list D4 generated in step S22 by the classification rule learning unit 14 in step S15 of FIG. Rule R1 applies. The class estimating unit 16 estimates the class from the input features by applying the class classification rule R1 to the features, and outputs the estimation result (step S23).

  FIG. 18 is a diagram illustrating an example of class estimation according to the embodiment. For example, the class classification rule R1 shown in FIG. 18 is the same as the class classification rule R1 shown in FIG. The feature list D4 shown in FIG. 18 includes features of “affiliation”, “nationality”, “name”, “affiliation+president”, “affiliation+faculty”. The class estimating unit 16 refers to the class classification rule R1 and calculates the score of each class of each feature of “affiliation”, “nationality”, “name”, “affiliation+president”, “affiliation+faculty”. In the example shown in FIG. 18, the score of the “person” class is “3” for the “affiliation” feature, “3” for the “nationality” feature, “3” for the “name” feature, and “affiliation + president”. Since the feature is “1” and the feature of “affiliation+faculty” is “1”, the total score is 3+3+3+1+1=11.

  Similarly, the "scientist" class score is "1" for the "affiliation" feature, "1" for the "nationality" feature, "1" for the "name" feature, and "1" for the "affiliation + president" feature. Since the feature of “1” and “affiliation+faculty” is “1”, the total score is 1+1+1+1+1=5. In addition, the score of the “company employee” class is “1” for the “affiliation” feature, “1” for the “nationality” feature, “1” for the “name” feature, and “1” for the “affiliation + president” feature. Since the feature of “0” and “affiliation+faculty” is “0”, the total score is 1+1+1+0+0=3. The score of the "Composer" class is "1" for the "affiliation" feature, "1" for the "nationality" feature, "1" for the "name" feature, and "1" for the "affiliation + president" feature. Since the feature of “0” and “affiliation+faculty” is “0”, the total score is 1+1+1+0+0=3.

  Then, the class estimation unit 16 sets, for example, the score threshold to score 4, and outputs the “person” class and the “scientist” class having a score exceeding 4 which is the score threshold, as the estimation class for the class estimation target data.

(Other application examples of the embodiment)
FIG. 19 is a diagram illustrating an example of calculating the appearance probability of an object class according to another application example of the embodiment. In the example shown in FIG. 19, for the “predicate” and “location”, the corresponding “object” is not a literal, and the classes that appear are “city” and “prefecture”. Therefore, the appearance probability of “city, town and village” is 9/10, and the appearance probability of “prefecture” is 1/10. Also, for the "predicate" and "festival deity", the corresponding "object" is not a literal, and the classes that appear are "royal family" and "god", so "royal family" and "god" The appearance probabilities of both are 3/6.

  Similarly, for the “predicate” and “honson”, the corresponding “object” is not a literal and all the appearing classes are “Buddha”, so the appearance probability of “Buddha” is 1. Further, regarding the “predicate” and “open group”, since the corresponding “object” is not a literal and all the appearing classes are “monks”, the appearance probability of “monks” is 1.

Therefore, in the “predicate” and “location”, there are two classes that appear, “municipalities” and “prefectures”, and the respective occurrence probabilities are 9/10 and 1/10. Therefore, the ambiguity calculation unit 11 calculates that entropy S=−(9/10)×log ₂ (9/10)−(1/10)×log ₂ (1/10)≈0.47. Further, in this case, the ambiguity calculation unit 11 calculates the threshold as (log ₂ N)/2=(log ₂ 2)/2=1/2=0.5. Therefore, the ambiguity calculation unit 11 stores the “predicate” “location” in the expanded predicate storage unit 12 because the condition that the “predicate” “location” is entropy S<threshold and the entropy S is larger than the threshold is not satisfied. do not do. In other words, the class of the “object” that precedes the “predicate” and the “location” does not have a variety of possible class resources, and the ambiguity is small.

Similarly, the ambiguity calculation unit 11 has two classes, “royal family” and “god”, that appear in the “predicate” and “festival deity”, and the appearance probabilities are both 3/6. Therefore, entropy S=− (3/6)×log ₂ (3/6)−(3/6)×log ₂ (3/6)=1 is calculated. Further, in this case, the ambiguity calculation unit 11 calculates the threshold as (log ₂ N)/2=(log ₂ 2)/2=1/2=0.5. Therefore, the ambiguity calculation unit 11 saves the “predicate” “festival deity” in the expanded predicate storage unit 12 because the condition that the “predicate” “festival deity” becomes entropy S>threshold and the entropy S is greater than the threshold. To do. In other words, the class of the “object” that precedes the “predicate” and “festival” has a wide variety of possible class resources and is highly ambiguous.

Similarly, the ambiguity calculation unit 11 determines that entropy S=−1×log ₂ 1=0 since the only class that appears in the “predicate” “honson” is “France” and the appearance probability is 1. calculate. Further, in this case, the ambiguity calculation unit 11 calculates the threshold value as (log ₂ N)/2=(log ₂ 1)/2=0. Therefore, the ambiguity calculation unit 11 saves the “predicate” “honson” in the expanded predicate storage unit 12 because the condition that the “predicate” “honson” is the entropy S=threshold and the entropy S is greater than the threshold. do not do. That is, the class of the “object” that precedes the “predicate” and “honson” does not have a variety of possible class resources, and the ambiguity is small.

Similarly, the ambiguity calculation unit 11 determines that entropy S=−1×log ₂ 1=0 since the only class that appears in the “predicate” “open group” is “monk” and the appearance probability is 1. calculate. Further, in this case, the ambiguity calculation unit 11 calculates the threshold value as (log ₂ N)/2=(log ₂ 1)/2=0. Therefore, the ambiguity calculation unit 11 stores the “predicate” “open base” in the expanded predicate storage unit 12 because the condition that the “predicate” “open base” has the entropy S=threshold and the entropy S is larger than the threshold. do not do. In other words, the class of the “object” that precedes the “predicate” and “open base” does not have a wide variety of possible class resources, and the ambiguity is small.

  Therefore, in the example of FIG. 19, as shown in FIG. 20, “festival deity” is expanded and “location”, “honson”, and “Kaiki” are not expanded. FIG. 20 is a diagram illustrating an example of expansion of a graph according to another application example of the embodiment. As shown in FIG. 20, "prediction", "festival deity" and the following are expanded for each of "subject", "Meiji Shrine", "Yoshino Shrine", "Sumiyoshi Shrine", "Akama Shrine", "Itsukushima Shrine", and "Izumo Taisha Shrine". Get each predicate of. In the example of FIG. 20, for each of the “subject”, “Meiji Jingu”, “Yoshino Jingu”, and “Akama Jingu”, the predicate after the expansion of “predicate” and “festival god” is “reign” and “gengo”. In addition, the predicate after the expansion of the "predicate" "festival god" is the "official name" for "subject" "Sumiyoshi Shrine" "Itsukushima Shrine" "Izumo Taisha".

  Then, as described above, the feature generation unit 13 generates the feature list L3. When the subject is “Meiji Jingu”, the feature generation unit 13 expands beyond the “predicate” and “shrine god”, and acquires the “residence” and “gengo” that are the development results of the “shrine god”. Then, the feature generation unit 13 uses the "predicate", "location", "festival deity", and the "results" and "gengo", which are the development results of the "festival deity", as the features of the class "jingu" to "location, deity, deity". +Position, festival god+gengo” is generated and stored in the feature list L3 shown in FIG. The same applies to the other "subjects" shown in FIG.

  Then, as described above, the classification rule learning unit 14 generates the class classification rule R1 from the appearance frequency of each class of each feature. FIG. 21 is a diagram showing an example of a classification rule (appearance frequency of each feature in each class) according to another application example of the embodiment. The classification rule learning unit 14 associates the feature and the score in each class with respect to “location”, “festival deity”, “honson”, “kaiki”, “festival deity+reign”, “festival deity+gengo”, “festival deity+formal name”. The class classification rule R1 is generated and stored in the class classification rule storage unit 15. “Festival+reign”, “Festival+gengo”, “Festival+formal name” are the additional features acquired by developing the graph above the object.

  Further, the feature generation unit 13 obtains a feature and a combination feature based on the class estimation target data, similarly to the above. Then, the class estimating unit 16 refers to the class classification rule R1 and refers to each of the features of “location” “festival deity” “honson” “kaiki” “festival deity+reign” “festival deity+gengo” “festival deity+formal name”. Calculate the score for each class. Then, the feature generation unit 13 outputs a class whose score exceeds the score threshold as an estimated class for the class estimation target data.

  In the above embodiment, when the ambiguity (diversity) of the object class for each predicate is determined to be higher than a predetermined value by the threshold determination in the RDF graph, the graph before the expansion is expanded and the graphs before and after the expansion are expanded. Generate a combination feature that combines the predicates of. Then, the learning data for class classification based on the combination feature is generated, and the classification rule is learned from this learning data.

  Then, in the embodiment, a class estimation target resource whose class is to be estimated is input, a graph is expanded in the same manner as when learning the class classification rule to generate a combination feature, and the class classification rule is applied to the generated combination feature. By doing so, the class of the input resource is estimated. As a result, it is possible to improve the accuracy of class estimation while suppressing the processing load and the calculation cost by suppressing the increase in features.

  For example, among the vast amount of resources on the Web, there are resources that have the same predicate but different object classes, so it is not easy to accurately determine such resource classes. In order to discriminate a class with high accuracy, it is conceivable to increase the number of features serving as a clue for discrimination. However, simply increasing the number of features increases the processing load and reduces the calculation speed.

  Therefore, in the embodiment, the object is expanded only when the ambiguity of the class of the object with respect to each predicate exceeds the threshold value, and the class classification rule in which the features that characterize the class are increased is learned. As a result, it is possible to suppress an increase in processing load and a decrease in calculation speed, and perform class classification with high accuracy.

  Further, it is said that by defining a schema of a data structure as RDF for a vast amount of resources on the Web and linking the resources to each other and publishing them, a certain resource can be used as a clue to machine search for other resources. This is “Yoshitsugu Nishide et al., “Schema analysis of datasets and link relationship survey for the purpose of utilizing Open Data in Japan”, Research report information basics and access technology (IFAT), 1-8, general incorporated foundation. Institute of Electronics, Information and Communication Engineers, September 19, 2013, 2013-IFAT-112(4)”. For example, it is expected that data can be used smoothly by adding class information to resources. ..

  However, many resources published on the web do not have sufficient schema definition, such as class information is not added. Therefore, many resources published on the web cannot be mechanically accessed based on the schema and are difficult to utilize.

  However, using the result of the class estimation according to the embodiment, different RDF resources can be appropriately combined based on the estimated class. Therefore, the embodiment complements the inconvenience that it is not easy to search for a target resource based on other resources, and facilitates resource search, thereby improving the convenience of resource utilization.

  Each component of each device illustrated in the above embodiments does not necessarily have to be physically configured as illustrated. That is, the specific form of distribution or integration of the respective parts is not limited to the illustration, and all or part of the parts may be functionally or physically distributed/integrated in arbitrary units according to various loads and usage conditions. Can be configured.

  For example, the expansion predicate storage unit 12 and the class classification rule storage unit 15 may be external storage devices connected to the class estimation device 10. Further, the class estimation device 10 may be distributed and implemented in a learning device including the ambiguity calculation unit 11, the feature generation unit 13, and the classification rule learning unit 14 and an estimation device including the feature generation unit 13 and the class estimation unit 16. Good.

  Further, the various processing functions of the ambiguity calculation unit 11, the feature generation unit 13, the classification rule learning unit 14, and the class estimation unit 16 of the class estimation device 10 are all or in cooperation with a CPU (Central Processing Unit) and a memory. Any part is realized. Alternatively, all or any part of the various processing functions of the class estimation device 10 may be realized by a microcomputer such as MPU, MCU, ASIC, or FPGA. The MPU is a Micro Processing Unit, the MCU is a Micro Controller Unit, the ASIC is an Application Specific Integrated Circuit, and the FPGA is a Field-Programmable Gate Array.

  Further, the various processing functions of the class estimation device 10 may be implemented by a program that is analyzed and executed by a CPU (or a microcomputer such as MPU or MCU) or hardware such as wired logic, and all or any part thereof may be realized. Good.

10 Class Estimating Device 11 Ambiguity Calculation Unit 12 Expansion Predicate Saving Unit 13 Feature Generation Unit 14 Classification Rule Learning Unit 15 Class Classification Rule Saving Unit 16 Class Estimating Unit

Claims (6)

Corresponds to each predicate based on the occurrence probability of each object class corresponding to each predicate in the learning data of RDF (Resource Description Framework) that shows relation information between resources with at least three elements of subject, predicate, and object A calculation unit that calculates an index indicating the diversity of each object class
Acquires a second predicate in the case where an object corresponding to the first predicate whose index exceeds a predetermined threshold is a subject, combines the first predicate and the second predicate, and corresponds to each subject class And a generating unit that generates each feature including a combined predicate combining the first predicate and the second predicate,
Based on the correspondence relationship between each subject class and each feature, the appearance frequency of each feature corresponding to each class is aggregated, and the class assigned to each feature is classified from the aggregated appearance frequency. And a learning unit that learns a class classification rule that An estimation unit is further provided, which refers to the class classification rule, calculates a sum of appearance frequencies in which the input features appear in each class, and outputs a class in which the sum exceeds a threshold as an estimated class estimated from the features. ,
The generation unit, when each predicate in the RDF class estimation target data corresponds to the first predicate, acquires a second predicate when the object corresponding to the first predicate is the subject, Combining the first predicate and the second predicate to generate each feature including a predicate corresponding to each subject class and a combined predicate combining the first predicate and the second predicate;
The class estimating device according to claim 1, wherein the estimating unit estimates a class of a subject corresponding to the feature in the class estimation target data by using the feature generated by the generating unit as an input. The class estimation device according to claim 1 or 2, wherein the index is entropy based on the appearance probability. The class estimating device according to claim 1, 2 or 3, wherein the index is variable according to the number of appearances of a class of each object corresponding to each predicate. Computer
Corresponding to each predicate based on the occurrence probability of each object class corresponding to each predicate in the learning data of RDF (Resource Description Framework) that shows relation information between resources with at least three elements of subject, predicate, and object Calculate the index showing the diversity of each object class
Acquiring a second predicate when the object is the object corresponding to the first predicate whose index exceeds a predetermined threshold value,
Combining the first predicate and the second predicate,
Generating each feature including a predicate corresponding to each subject class and a combination predicate combining the first predicate and the second predicate;
Based on the correspondence relationship between each subject class and each feature, the appearance frequency of each feature corresponding to each class is aggregated, and the class assigned to each feature is classified from the aggregated appearance frequency. A class estimation method characterized by executing each process for learning a class classification rule. On the computer,
Corresponding to each predicate based on the occurrence probability of each object class corresponding to each predicate in the learning data of RDF (Resource Description Framework) that shows relation information between resources with at least three elements of subject, predicate, and object Calculate an index showing the diversity of each object class
Acquiring a second predicate when the object is the object corresponding to the first predicate whose index exceeds a predetermined threshold value,
Combining the first predicate and the second predicate,
Generating each feature including a predicate corresponding to each subject class and a combination predicate combining the first predicate and the second predicate;
Based on the correspondence relationship between each subject class and each feature, the appearance frequency of each feature corresponding to each class is aggregated, and the class assigned to each feature is classified from the aggregated appearance frequency. A class estimation program that executes each process of learning a class classification rule to be performed.

Images