Paper
Inheritance Comes of Age: Applying Nonmonotonic Techniques to Problems in Industry.
Summary
because non-monotonic reasoning is not and never been present in industrial applications, its presence in the ai community is gradually reducing.
Leora gives as motivations to the lack of industrial applications two factors:
- researchers work on problems that are not apparently related to industrial needs;
- there are very few efficient algorithms and some are not even implemented.
In this paper the author describes an industrial application and an extended of the traditional inheritance with exception algorithm for this application.
(KL-ONE and K-REP are KBS that use inheritance networks without exceptions)
The application considered is a medical insurance application. a standard hierarchical network with exception does efficiently the job but only for the taxonomic part.
There is part of the knowledge to be encoded that is not taxonomic. The author gives the following examples:
- there is a co-pay of 20% for diagnostic services.;
- patients in drug reabilitation programs lose all rehab benefits for a year if they are non-compliant;
- more in general knowledge about a patient history.
So, the author extends the network structure to a FAN (Formula Augmented Network).
Some definitions:
- what is a FAN? a tuple (N,W,B,L1,L2,O) where:
- N is the set of nodes in the network;
- B is a set of sorted FOL formulas (background knowledge);
- W is another set of formulas in sorted FOL (these are formulas that will be connected with nodes);
- L1 is the set of links between nodes in the network. A link can be:
- positive that corresponds to a is-a link, negative that corresponds to a cancel link;
- strict that correspond to a forall, defeasible that corresponds to a most (typically).
- L2 is the set of links between nodes and set of wffs in W.
- Also these links can be strict or defeasible (every formula in W is true in the connected node, or every formula in W is typically true at the connected node);
- Also they can be negative/positive (true/false formulas);
- Each set of wffs connected to a node must be consistent with B.
- O is a set of partial ordering. A partial order for each node that is a fork and in which the multiple paths are not negative paths. Basically it is away to solve the problem of multiple inheritance by preferring a path to another.
- path. A path pi(x,sigma,y) is a positive path from the node x to the node y (sigma is the actual path). pi'(.) is a negative path. A path can be:
- conflicted: a path from x to y is conflicted if there is another path of opposite sign and same start and end points;
- preempted: a path is preempted if there is a conflicting path that is shorter at the end (e.g. x->v->w->y is preempted by and x->v->y (given that the first is all positive and in the second the v->y link is negative);
- constructible if it can be built by concatenating paths in the networks;
- inherited or undefeated if it is constructible and neither preempted nor conflicted.
NOTE: a path from x to y means that x is-a y
multiple inheritance: x is a fork when there multiple paths from x to different destinations (see previous note if it seems to other way around). So basically x is both a y and a z and something else.
How does inheritance of formulas work?
The problem comes from the fact that the link in L2 between a node and a set of formulas and usually defeasible links. So, a formula that is typically true in a node, it can be false in a child of that node.
The technique the author proposes is:
- given a node N, find all the nodes N_i with undefeated paths from N to N_i.
- find the maximally consistent subset made doing to union of the set of formulas linked to N_i and N and the set B.
2 problems:
- determining consistency is semi-decidable: consider only a subclass of formulas for which deciding consistency is decidable. But still, deciding consistency is intractable. The author suggests a divide-and-conquer strategy: to compute consistency consider only the formulas belonging to a certain type. So, this implies that the formulas are dived into type of formulas (in the paper: administrative, medical, ...) and formulas in a type are always consistent with formulas in the other types.
- there are more than 1 (typically) maximal subset. Which formula to remove: build a preference order.
The preference criteria are;
- specificity: prefer more specific information. Given that bird fly and that Tweety (a bird) doesn't fly, then prefer the Tweety knowledge about flying instead of the generic bird knowledge because it is more specific to respect to Tweety.
- order: when specificity doesn't help (multiple paths), then use the order O to choose which path to inherit from.
Open questions:
- what to do with preempting paths. See figure 7 for an example.
- determining conflicting paths can depend on knowledge. Therefore, it might be the case that in the network two path are not conflicting each other but given the background knowledge they are.
Why using this mixed representation mechanism instead of a either all-network or all-formulas approach?
* converting everything to network goes against the principle that the nodes in a network represents concrete entities (now formulas would become nodes). Plus, the definition of inconsistency becomes difficult (because it depends on some property of paths not easily specifiable).
* converting everything to formulas is not optimal because the distinction between taxonomic knowledge and general knowledge is lost. Plus efficient algorithms could be harder to write.
Conclusions:
- check for problems for real world applications, use them instead of toy examples.
- basic research is still needed
- balance between basic reasearch and industrial collaboration
- develop tools (not only on paper)
- solving a real problem is typically harder and more complex than solving a toy problem.
-- FabrizioMorbini - 03 Jan 2007