INFORMATION-THEORY BASED MEASURE OF SIMILARITY BETWEEN INSTANCES IN ONTOLOGY

• US 20080243809A1
• Filed: 03/29/2007
• Published: 10/02/2008
• Est. Priority Date: 03/29/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ranganathan, Anand, Ronen, Royi
• Granted Patent: US 7,792,838 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/367 Ontology

Abstract

Improved information processing techniques for measuring similarity between instances in an ontology are disclosed. For example, a method of measuring similarity between instances in an ontology for use in an information retrieval system includes the following steps. A set of instances from the ontology is obtained. At least one of the following similarity metrics for the set of instances is computed: (i) a first metric that measures similarity between instances in the set of instances with respect to ontology concepts to which the instances belong; (ii) a second metric which measures similarity between instances in the set of instances where the instances are subjects in statements involving a given ontology property; and (iii) a third metric which measures similarity between instances in the set of instances where the instances are objects in statements involving a given ontology property. At least one taxonomy induced by the at least one computed similarity metric is stored, wherein the at least one induced taxonomy is usable for responding to requests submitted to an information retrieval system. When two or more of the first metric, the second metric and the third metric are computed, and two or more induced taxonomies corresponding to the two or more computed similarity metrics are stored, the method may include merging the two or more induced taxonomies to form a combined taxonomy, wherein the combined taxonomy is usable for responding to requests submitted to an information retrieval system.

Claims

1. A method of measuring similarity between instances in an ontology for use in an information retrieval system, the method comprising the steps of:

obtaining a set of instances from the ontology;

computing at least one of the following similarity metrics for the set of instances;

a first metric that measures similarity between instances in the set of instances with respect to ontology concepts to which the instances belong;

a second metric which measures similarity between instances in the set of instances where the instances are subjects in statements involving a given ontology property; and

a third metric which measures similarity between instances in the set of instances where the instances are objects in statements involving a given ontology property; and

storing at least one taxonomy induced by the at least one computed similarity metric, wherein the at least one induced taxonomy is usable for responding to requests submitted to an information retrieval system.

2. The method of claim 1, wherein two or more of the first metric, the second metric and the third metric are computed, and two or more induced taxonomies corresponding to the two or more computed similarity metrics are stored, further comprising the step of merging the two or more induced taxonomies to form a combined taxonomy, wherein the combined taxonomy is usable for responding to requests submitted to an information retrieval system.

3. The method of claim 1, wherein the first metric, the second metric and the third metric comprise information theory-based measurements.

4. The method of claim 1, wherein the first metric measures similarity of instances i and j in the set of instances based on the similarity of C(i) and C(j), where C(i) and C(j) represent sets of concepts to which the instances belong.

5. The method of claim 4, wherein the first metric considers concept membership statements of instances in the set of instances by defining a description of an individual and a commonality between instances based on concepts to which they belong.

6. The method of claim 5, wherein a description of an instance is computed by defining a virtual class and making the instance the only member of the virtual class.

7. The method of claim 6, wherein information content of the description of the instance is the probability that a random instance to the virtual class.

8. The method of claim 7, wherein the commonality between two instances i and j is computed by expanding respective descriptions to include one or more other concept membership statements that can be inferred based on the concept taxonomy such that information content in the commonality is the probability that a pair of random instances satisfies the pair of class membership statements in the commonality.

9. The method of claim 8, wherein C(i, j) denotes the set of classes that are the least common ancestors of the virtual class for i and the virtual class for j, and V_i,j denotes the intersection of all classes in C(i, j) and represents a least common ancestors intersection class for instances i and j, and information content in the commonality between instances and i and j is the probability that a pair of random instances belong to V_i,j.

10. The method of claim 1, wherein the second metric measures similarity of instances i and j in the set of instances based on the similarity of sets of objects in statements where the instances are subjects in the statements.

11. The method of claim 10, wherein the similarity between instances i and j are based on statements where i and j are the subjects and the predicate is a given property.

12. The method of claim 11, wherein an instance is considered to belong to a virtual class of size one and a description for the instance is defined in terms of its membership to this virtual class.

13. The method of claim 12, wherein the virtual class is associated with a taxonomy is defined based on a range of the given property.

14. The method of claim 13, wherein information content of the description of the instance is the probability that a random individual belongs to the virtual class.

15. The method of claim 14, wherein a commonality between two instances i and j is computed by expanding respective descriptions to include one or more other statements that can be inferred based on the object-sets for the given property and the taxonomy associated with the range of the given property, and obtaining common pairs of statements that occur in both descriptions.

16. The method of claim 15, wherein the information content in the commonality is the probability that a pair of random instances satisfies the pairs of statements in the commonality.

17. The method of claim 1, wherein the third metric measures similarity of instances i and j in the set of instances based on the similarity of sets of subjects in statements where the instances are objects in the statements.

18. The method of claim 17, wherein the similarity between instances i and j are based on statements where i and j are the objects in the statements and the predicate is a given property.

19. The method of claim 18, wherein an instance is considered to belong to a virtual class of size one and a description for the instance is defined in terms of its membership to this virtual class.

20. The method of claim 19, wherein the virtual class is associated with a taxonomy is defined based on the domain of the given property.

21. The method of claim 20, wherein information content of the description of the instance is the probability that a random individual belongs to the virtual class.

22. The method of claim 21, wherein a commonality between two instances i and j is computed by expanding respective descriptions to include one or more other statements that can be inferred based on the subject-sets for the given property and the taxonomy associated with the domain of the given property, and obtaining common pairs of statements that occur in both descriptions.

23. The method of claim 22, wherein the information content in the commonality is the probability that a pair of random instances satisfies the pairs of statements in the commonality.

24. The method of claim 2, wherein two or more taxonomies are merged by merging two or more virtual classes for each instance computed in accordance with two or more of the metrics.

25. An article of manufacture for measuring similarity between instances in an ontology for use in an information retrieval system, comprising a computer readable storage medium containing one or more programs which when executed implement the steps of claim 1.

26. Apparatus for measuring similarity between instances in an ontology for use in an information retrieval system, the apparatus comprising:

a memory; and

a processor coupled to the memory and operative to;

(i) obtain a set of instances from the ontology;

(ii) compute at least one of the following similarity metrics for the set of instances;

a first metric that measures similarity between instances in the set of instances with respect to ontology concepts to which the instances belong;

a second metric which measures similarity between instances in the set of instances where the instances are subjects in statements involving a given ontology property; and

a third metric which measures similarity between instances in the set of instances where the instances are objects in statements involving a given ontology property; and

(iii) store at least one taxonomy induced by the at least one computed similarity metric, wherein the at least one induced taxonomy is usable for responding to requests submitted to an information retrieval system.

27. An information retrieval system, comprising a similarity measurement system configured to:

(i) obtain a set of instances from an ontology;

(ii) compute at least one of the following similarity metrics for the set of instances;

a first metric that measures similarity between instances in the set of instances with respect to ontology concepts to which the instances belong;

a second metric which measures similarity between instances in the set of instances where the instances are subjects in statements involving a given ontology property; and

a third metric which measures similarity between instances in the set of instances where the instances are objects in statements involving a given ontology property; and

(iii) store at least one taxonomy induced by the at least one computed similarity metric, wherein the at least one induced taxonomy is usable for responding to requests submitted to the information retrieval system.