Paper 1

Scott E. Fahlman: "Marker-Passing Inference in the Scone Knowledge-Base System", First International Conference on Knowledge Science, Engineering and Management (KSEM'06), Guilin, China, August 2006. Proceedings published by and copyright by Springer-Verlag (Lecture Notes in AI).

see also the project webpage.

What is SCONE?

SCONE is a knowledge base and inference engine. The goal of the project is to provide a system that can be easily incorporated in larger systems that need a knowledge base and an inference engine. Therefore SCONE focuses on being:
  • efficient and scalable
  • easy to use and open source (two of the major features lacked by CYC)
  • based on an expressive representation language

Based on the marker-passing algorithm designed for a massively parallel machine NETL never built because too costly. The algorithm is not complete (i.e. the performed inferences don't guarantee to find an answer even if it exists) but is fast and performs frequently used operations, like:

  • multi-hierarchies with inheritance and exceptions
  • default reasoning with exceptions
  • type violation
  • set intersection
  • possible worlds (multiple views of the global KB)

Idea inspired by:

  • Qullian's semantic networks
  • the observation that humans:
    • do lots of inferences during the process of understanding natural language without feeling any mental effort (i guess that mental effort is related to consciousness, if you are not aware of the work the brain is doing then that work is effortless).
    • do pattern matching based on set of properties and expectations again without any apparent effort. And this patter matching is at the core of various human abilities like visual and speech recognition and even higher levels abilities like plan/intention recognition.

NETL structure:

  • Nodes:
    • every node has a very limited computing power.
    • every node has associated a fixed number of bits (called "marker-bits")
    • every node is connected to a serial controlled through a common bus, the nodes execute (in parallel) the commands presents on the common bus
    • every node has a "tie-point"
  • Edges (or links)
    • links are also nodes with computing power, their set of marker bits and a tie point
    • in addition a link has 5 wires that can be connected to 5 nodes:
      • A, B and C: connected to the nodes that are respectively the first, second and third argument of the relation represented by this link (the tie node present on a link is a reference to the relation represented by the link, so knowledge about the relation can be expressed)
      • PARENT: connected to a node that defines the type of this link. There are some predefined types of link that are known and properly used by the inference machinery:
        • is-a: represent the is-a hierachy. The node on the A link is an individual that belongs to the collection represented by the node on the B link. So Clyde is an individual that belongs to the Elephant collection and Elephant is an individual that belongs to the Mammal collection. In CYC clyde will be connected to Elephant with a is-a link but Elephant will be connected to Mammal with a genls link (because both Elephant and Mammal are collections).
        • eq: the nodes connected (using links A and B) are equal, so if we set a marker of the node on A we have to set the same also on the node on B.
        • cancel: used to express exception to split links. See figure 1 from the paper for an example. The author states that this technique is not always working because there could be multiple paths to the same conclusion and only some of them could be canceled leaving an ambiguous case. Not clear on page 8 why this system can be unsound.
        • map: are used to create virtual copies of certain subnets. See figure 2 from the paper for an example. This is another point in which this system shows limitations (in addition to the cancel links). A single mapping at a time can be considered for inference.
        • split: represent disjoint sets. A split link can connect a node, 'e', to any numerb of other nodes and represents the fact that 'e' is disjoint with all the other connected nodes.
      • CONTEXT: SCONE can organize knowledge in subnets associated to a particular context node. Context nodes are connected using is-a links. So, one can make hierarchies of contexts (with exceptions). All the nodes that are connected to a particular context node become active when that context node becomes active. One can add cancel nodes do represent exceptions.

Examples:

  • "mark all gray mammal that lives in Africa": set all gray things with marker 1, set all mammals with marker 2, set of things that lives in Africa with marker 3. Set all nodes with marker 1, 2 and 3 with marker 4. the answer is all the nodes with marker 4 set.
  • "Clyde is an elephant": connect the node Clyde and the node Elephant with a link of type is-a in which link A is connected to Clyde and link B is connected to Elephant.

His reason to implement on a sequential machine this parallel algorithm:

  • current machine are much faster than what was available when NETL has been designed.
  • the parallel core is small and simple and can be efficiently implemented on a modern sequential machine.
    • intersection is one of the most common operations to do. In SCONE, intersection of M sets each of size N_i is done in time \Sum_{i=1}^{M}{N_i}+min_{0<i<=M}{N_i} by marking all elements of set i with marker i and then checking the smallest of the M sets to see wihch elements have all the M markers set.
  • this method is more efficient and focused then a general resolution based theorem prover (though it is not complete).
  • it can be easily adapted to use cluster and vector machines.
  • the high focus obtained by this method helps to keep contained the effects of inconsistencies present in the KB

Key characteristics of the sequential implementation:

  • the marker bits are a contiguous set of bits in memory (so, a logical AND on a 32 bit machine can simultaneously intersect 32 markers in one clock cycle).
  • to each marker is associated a double linked list of all the nodes with that marker set. Also, a count of the length of this list is kept.
  • links are pointers.

Conclusion:

  • humans do some inferences unconsciously but other inferences with lots of conscious mental effort. SCONE tries to provide the unconscious mental capabilities of a human.
  • SCONE can be integrated in a general inference engine as a fast reasoner for the types of queries it can handle.
  • marker passing algorithm can be efficient on modern sequential processors and can be easily extended to take advantage of clusters and vector machines.

Comparison

SCONE is very similar to the MULTINET system. Multinet seems able to do more complex inferences but lacks some of the features of SCONE, most notably the ability to represent possible worlds.

Observations (starting points for discussion)

The thing i liked the most is the clean implementation of multiple views of a KB (the context nodes). Exceptions are handled in some cases but probabilistic approach will probably provide the complete answer to the problem. The advantages of this algorithm are not related to the use of semantic networks, the same could be done with a traditional FOL KB.

-- FabrizioMorbini - 16 Nov 2006

Topic attachments
I Attachment History Action Size Date Who CommentSorted ascending
JPEGjpeg fig1.jpeg r1 manage 57.5 K 2006-11-16 - 17:59 FabrizioMorbini  
JPEGjpeg fig2.jpeg r1 manage 40.6 K 2006-11-16 - 18:34 FabrizioMorbini  
Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2006-11-16 - FabrizioMorbini
 
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