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, ...
  • there are more than 1 (typically) maximal subset. Which formula to remove: build a preference order.

Observations (starting points for discussion)

Further readings

-- FabrizioMorbini - 03 Jan 2007

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r2 - 2007-01-03 - FabrizioMorbini
 
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback