Transcript Computational Complexity of terminological reasoning in BACK

Computational
Complexity of
Terminological
Reasoning in BACK
Authors: Bernhard Nebel, Technische Universität Berlin, CIS/KIT
Sekr. FR 5-8, Franklinstraße 28/29 D-1000 Berlin 10, West-Germany
e-mail: [email protected] published in Artificial Intelligence 34:
371-383, 1988
Presented by Jordan Bradshaw and Corey White
•
•
•
•
•
•
•
Introduction
Complexity of Subsumption
A Formal Treatment of Subsumption
Definition of FLN
Proof of NP-hardness
Formulation of the Problem
Consequences of Results
Overview
• The BACK system is part of the KL-ONE hybrid
knowledge representation system.
• Which is a FDL (frame-based description language)
• It's used to represent terminological knowledge
Introduction
Concept Relationship
Example
• Important characteristics of FDL
• take definition notions seriously
• Allows concepts/roles to specify relationships to other
concepts
• Grandparent is a specialization of parent, although its not
explicitly mentioned.
• Since there is more represented than what's explicitly
written, a reasoner is needed to uncover the hidden
relationships.
Introduction cont…
Introduction cont…
• Some queries can be reduced to other query types
• All queries in this case can be reduced to subsumptions
provided the concepts/roles.
•
•
•
•
Classification -> Subsumption (provided O(n2))
Disjointness ->Incoherency
Incoherency -> Subsumption
Property possession -> Classification
Introduction cont…
• Subsumption is a crucial part of terminological reasoning.
• Subsumption basic idea:
• All detected relationships in KL-ONE are sound, but the
detection procedure is incomplete.
• FDL used in KL-ONE the subsumption problem can be
intractable.
Complexity of
Subsumption
• BNF notation of introduction example:
A Formal Treatment of
Subsumption
• Partially defined concepts can be modeled by assuming
additional anonymous atomic concepts:
A Formal Treatment of
Subsumption
• Here is the extension, for the objects described by their
particular concept:
A Formal Treatment of
Subsumption
• C1 subsumes C2 if and only if set D and any extension
function ε over D, the following will hold:
•
• The language above, FL by Brachman & Levesque is
intractable with respect to subsumption.
• FL- , without the restr operator was shown to be more
acceptable from a computational complexity perspective.
A Formal Treatment of
Subsumption
N
Definition of FL
N
Definition of FL


It can be seen that FLN allows the introduction of incoherent
concepts:
More can be inferred from this example:
N
Definition of FL



It is therefore necessary to consider the disjointness of role
filler concepts.
This can still be handled in polynomial time, as there are n *
(n -1) / 2 pairs of sub roles to consider.
There are other more complex situations to consider though...
N
Definition of FL



These sub roles aren't pairwise disjoint but lead to
incoherency when considered together.
This is likely an intractable problem
Even if it wasn't intractable, there are still no sound, complete,
polynomial algorithms for subsumption
Proof of NP-hardness



Subsumption in FLN can be compared to the complement of
the SET-SPLITTING problem
SET-SPLITTING is proven NP-complete
SET-SPLITTING is defined as:

Given a collection C of subsets of a finite set S, is there a
partition of S into two subsets S1 and S2 such that no subset in C
is entirely contained in either S1 or S2.
Formulation of the Problem

Given a special case subsumption problem:



SUBSUMES ((atleast 3 R, X)
X is a description containing atleasts and alls on sub roles of
R
Consider a SET-SPLITTING problem with:



S = {s1, s2, … sn}
C = {c1, c2, … cm}
Each ci has the form:

Ci = {sf(i, 1), sf(i, 2), … sf(i, ||Ci||)}
Formulation of the Problem

This gives rise to an X of the form:


(and (atleast 1 (androle R Rprim1))
(all (androle RRprim1) π(s1))
(atleast 1 (androle R Rprim2))
(all (androle RRprim2) π(s2))
....
(atleast 1 (androle R Rprimn))
(all (androle RRprimn) π(sn))
Where π is a transformation function such that for each set
Ci the conjuction of π(sf(i,k)) for 1 < k < ||Ci|| forms an
incoherent concept
Formulation of the Problem



Under this formulation, this means that the corresponding sub
roles can't be filled with the same instance.
However, if the subset of S doesn't contain a set Ci, then the
sub roles can be filled with the same instance.
We then assume m roles in Ri corresponding to sets of Ci.
Formulation of the Problem

Where CPi,j is defined as:
Formulation of the Problem


This means that a conjunction of π(Sj) is incoherent iff for
some role Ri we have more than ||Ci|| -1 different atleast
restrictions
This results in the following analogy to the SETSPLITTING problem:



If a role R of concept X can be filled with 2 or less role fillers,
then there is a set splitting.
Else, a there is no set splitting.
Since this solves an instance of the SET-SPLITTING
problem, subsumption in FLN is co-NP-hard.
Consequences

This has some unfortunate consequences:




There are no complete, sound algorithms for subsumption on
FDLs with this much expressive power that run in polynomial
time.
We can improve this by reducing the expressiveness of the FDL:
removing atleast, atmost and androle can help
We can settle on algorithms that are not complete instead, but
tractable.
This is a common approach for AI algorithms
Consequences

To provide completeness, the expressiveness of the FDL must
be limited:




Remove all operators relating roles
Alternatively, restrict these operators to some, none and unique
Weakening the semantics has the effect of reducing what
inferences can be made
Even somewhat obvious relationships might be missed
Consequences

This gives us three ultimate choices:




A complete, sound algorithm: extremely slow
Weak semantics: might miss a lot of inferences
Strong semantics and incomplete algorithm: might miss some
less obvious inferences
The approach depends on what's needed, but most practical
systems would opt for the last option