Ontological concept expansion for improved similarity measures for description logic
View Patent ↗In one embodiment, prior to similarity measure computation, concept expansion is applied to an original ontology to generate an expanded ontology having the original concepts plus one or more pseudo-concepts, wherein at least one original concept is defined using a hierarchy of (possibly transitive) properties. As a result, the similarity measure computation can produce results that are better than those produced using conventional techniques. In one implementation, the similarity measure computation involves combining two similarity results: a first similarity result corresponding to common semantics found in the two concepts and a second similarity result corresponding to dissimilar semantics found in the two concepts.
1. A machine-implemented method comprising:
(a) the machine receiving an original ontology containing a plurality of original concepts, wherein at least one original concept is defined using a hierarchy of properties;
(b) the machine applying a concept expansion mechanism to the original ontology to generate an expended ontology containing the original concepts and one or more pseudo-concepts, wherein the concept expansion mechanism comprises:
(1) the machine classifying the original concepts by computing inferences using the original ontology;
(2) the machine rewriting at least one original concept definition by replacing at least one defined concept appearing in the original concept definition by its expression;
(3) the machine rewriting at least one sub-class axiom by replacing at least one defined concept appearing in a subsumption axiom by its expression as rewritten in step (2);
(4) the machine rewriting at least one original concept in its normal form;
(5) the machine generating a pseudo-concept of the expanded ontology for the at least one original concept rewritten in its normal form; and
(6) the machine classifying concepts of the expanded ontology by computing inferences using the expanded ontology; and
(c) the machine applying a similarity measure computation to the expanded ontology to generate a similarity measure characterizing similarity between at least two concepts in the expanded ontology, wherein the similarity measure generated using the expanded ontology provides more accurate characterization of the similarity between the at least two concepts than a corresponding similarity measure generated using the original ontology.
2. The method of claim 1 , wherein at least one property in the hierarchy is a transitive property.
3. The method of claim 2 , wherein the original ontology is a SHOQ ontology.
4. The method of claim 3 , wherein step (4) comprises the machine rewriting the at least one original concept in disjunctive normal form, wherein each disjunct of the disjunctive normal form is in conjunctive normal form.
5. The method of claim 3 , wherein step (5) comprises the machine generating the pseudo-concept by applying one or more generative functions to at least one conjunct of at least one disjunct of the at least one original concept rewritten in its SHOQ normal form.
6. The method of claim 5 , wherein:
the at least one original concept rewritten in its SHOQ normal form has at least one transitive property; and
the one or more generative functions determine at least one additional subsumption relation for the at least one original concept.
7. The method of claim 1 , wherein, for two concepts in the expanded ontology, the similarity measure computation comprises:
(1) generating a first similarity result corresponding to common semantics found in the two concepts;
(2) generating a second similarity result corresponding to dissimilar semantics found in the two concepts; and
(3) combining the first and second similarity results to generate the similarity measure.
8. The method of claim 7 , wherein:
the first similarity result is based on a number of direct subsumers of the two concepts; and
the second similarity result is based on (i) the number of direct subsumers of the two concepts, (ii) a common subsumer of the dissimilar semantics of the two concepts; and (iii) information content conveyed by the two concepts.
9. The method of claim 8 , wherein the similarity measure computation for the two concepts A and B is given by:
sim
(
A
,
B
)
=
2
×
n
c
(
A
,
B
)
n
t
(
A
,
B
)
+
[
(
1
-
2
×
n
c
(
A
,
B
)
n
t
(
A
,
B
)
)
×
(
2
×
I
C
(
R
C
S
(
δ
(
A
,
B
)
,
δ
(
B
,
A
)
)
)
I
C
(
δ
(
A
,
B
)
)
+
I
C
(
δ
(
B
,
A
)
)
)
]
,
where:
n c (A, B) is a number of semantically equivalent concepts in S D (A) and S D (B);
S D (A) is a direct subsumer set for concept A;
S D (B) is a direct subsumer set for concept B;
n t (A, B) is the number of direct subsumers of concepts A and B and is equal to | S D (A)|+| S D (B)|;
IC is an information content function;
RCS is the common subsumer of the dissimilar semantics of the two concepts; and
δ(A, B) is a semantic function that characterizes different semantics between the two concepts.
10. The method of claim 9 , wherein the information content function IC is given by:
I
C
(
A
)
=
-
log
(
1
+
n
s
(
A
)
1
+
n
s
(
Top
)
)
,
where:
Top refers to a root concept in the expanded ontology where concept A is defined; and
n S (A) is a total number of subsumers of concept A in the expanded ontology.
11. The method of claim 9 , wherein the semantic function δ(A, B) is given by:
δ
:
𝒢
O
×
𝒢
O
→
𝒲
O
(
A
,
B
)
→
{
⊓
i
C
i
such
that
C
i
∈
S
D
_
(
A
)
⊓
⫬
S
D
_
(
B
)
A
if
∀
C
i
∈
S
D
_
(
A
)
,
C
i
∈
S
D
_
(
B
)
.
12. A machine-implemented method comprising:
(a) the machine receiving an original ontology containing a plurality of original concepts;
(b) the machine applying a concept expansion mechanism to the original ontology to generate an expanded ontology containing the original concepts and one or more pseudo-concepts; and
(c) the machine applying a similarity measure computation to the expanded ontology to generate a similarity measure characterizing similarity between at least two concepts in the expanded ontology, wherein:
the similarity measure generated using the expanded ontology provides more accurate characterization of the similarity between the at least two concepts than a corresponding similarity measure generated using the original ontology;
for two concepts in the expanded ontology, the similarity measure computation comprises:
(1) the machine generating a first similarity result corresponding to common semantics found in the two concepts;
(2) the machine generating a second similarity result corresponding to dissimilar semantics found in the two concepts; and
(3) the machine combining the first and second similarity results to generate the similarity measure:
the first similarity result is based on a number of direct subsumers of the two concepts; and
the second similarity result is based on (i) the number of direct subsumers of the two concepts, (ii) a common subsumer of the dissimilar semantics of the two concepts; and (iii) information content conveyed by the two concepts.
13. The method of claim 12 , wherein the similarity measure computation for the two concepts A and B is given by:
sim
(
A
,
B
)
=
2
×
n
c
(
A
,
B
)
n
t
(
A
,
B
)
+
[
(
1
-
2
×
n
c
(
A
,
B
)
n
t
(
A
,
B
)
)
×
(
2
×
I
C
(
R
C
S
(
δ
(
A
,
B
)
,
δ
(
B
,
A
)
)
)
I
C
(
δ
(
A
,
B
)
)
+
I
C
(
δ
(
B
,
A
)
)
)
]
,
where:
n c (A, B) is a number of semantically equivalent concepts in S D (A) and S D (B);
S D (A) is a direct subsumer set for concept A;
S D (B) is a direct subsumer set for concept B;
n t (A, B) is the number of direct subsumers of concepts A and B and is equal to | S D (A)|+| S D (B)|;
IC is an information content function;
RCS is the common subsumer of the dissimilar semantics of the two concepts; and
δ(A, B) is a semantic function that characterizes different semantics between the two concepts.
14. The method of claim 13 , wherein the information content function IC is given by:
I
C
(
A
)
=
-
log
(
1
+
n
s
(
A
)
1
+
n
s
(
Top
)
)
,
where:
Top refers to a root concept in the expanded ontology where concept A is defined; and
n S (A) is a total number of subsumers of concept A in the expanded ontology.
15. The method of claim 13 , wherein the semantic function δ(A, B) is given by:
δ
:
𝒢
O
×
𝒢
O
→
𝒲
O
(
A
,
B
)
→
{
⊓
i
C
i
such
that
C
i
∈
S
D
_
(
A
)
⊓
⫬
S
D
_
(
B
)
A
if
∀
C
i
∈
S
D
_
(
A
)
,
C
i
∈
S
D
_
(
B
)
.
16. A machine comprising:
an input node configured to receive an original ontology containing a plurality of original concepts wherein at least one original concept is defined using a hierarchy of properties;
a concept expansion mechanism configured to apply concept expansion the original ontology to generate an expanded ontology containing the original concepts and one or more pseudo-concepts, wherein the concept expansion mechanism comprises:
(1) the machine classifying the original concepts by computing inferences using the original ontology;
(2) the machine rewriting at least one original concept definition by replacing at least one defined concept appearing in the original concept definition by its expression;
(3) the machine rewriting at least one sub-class axiom by replacing at least one defined concept appearing in a subsumption axiom by its expression as rewritten in step (2);
(4) the machine rewriting at least one original concept in its normal form;
(5) the machine generating a pseudo-concept of the expanded ontology for the at least one original concept rewritten in its normal form; and
(6) the machine classifying concepts of the expanded ontology by computing inferences using the expanded ontology; and
a similarity measure mechanism configured to apply a similarity measure computation to the expanded ontology to generate a similarity measure characterizing similarity between at least two concepts in the expanded ontology, wherein the similarity measure generated using the expanded ontology provides more accurate characterization of the similarity between the at least two concepts than a corresponding similarity measure generated using the original ontology.
17. The machine of claim 16 , wherein, for two concepts in the expanded ontology, the similarity measure computation comprises:
(1) generating a first similarity result corresponding to common semantics found in the two concepts;
(2) generating a second similarity result corresponding to dissimilar semantics found in the two concepts; and
(3) combining the first and second similarity results to generate the similarity measure.
18. The machine of claim 16 , wherein at least one property in the hierarchy is a transitive property.
19. The machine of claim 18 , wherein the original ontology is a SHOQ ontology.