Rough Design Sketch for an Ontology Engine

 

Preliminary Notes, not for distribution

 

 

Ben Goertzel

July 21, 2002

 

 

Contents

 

1        Introduction

2        Basic Software Architecture

3        The Novamente Core

4        Sketch of OE Object Structure

5        Sketch of OEShell Command Language

6        Advanced Capabilities for Future Versions

 

 

1.  Introduction

 

This document sketches a rough conceptual overview of a possible API for a “Ontology Engine” (OE).

 

Once the concepts are agreed upon, the design given here can be turned into a rigorous API proposal expressed in a particular programming language, or in a formal modeling language (UML, sequence diagrams, etc.).

 

Here I will describe a basic software architecture for the OE, sketch an object structure, and a command language intended to be embedded in a customized Unix shell, the OEshell.  An example OEshell script exemplifying the capabilities of the proposed OE server is given.  Finally, some more advanced capabilities that may be of interest for later OE versions are described (these are largely inspired by the Webmind and Novamente AI Engines).

 

 

2.  Basic Software Architecture

 

The basic concept of OE is the KnowledgeSystem (KS).  KnowledgeSystems can exist in two states:

 

 

OE provides mechanisms for:

 

 

Our preference is to make OE 1.0 a Unix-based system, but if necessary, with a little extra work, it can be made able to run on Windows as well.  We have experience with several standard DB’s including Oracle.

 

OE 1.0 will be a relatively simple system, lacking many important features that may be added in later versions, including:

 

  1. Automatic disambiguation of newly entered knowledge
  2. Distributed processing of active KS’s
  3. Support of large KS’s that, while active, can span both disk and RAM, with automated adaptive paging
  4. Automated inference methods that act on an active KS, adding new knowledge derived from the existing knowledge
  5. Natural language querying
  6. Visualization of knowledge structures
  7. Convenient knowledge entry by humans

 

All of these are things with which the author and his implementation team have direct experience; they were implemented in the Webmind AI Engine (though 5, NLP querying, was only implemented to a limited extent).  All involve fairly subtle issues.  The final section of this document explores these issues, closely inspired by the way the issues were dealt with in the Webmind AI Engine (WAE).

 

Occasionally in the following I will use a generic language to refer to the contents of OE Knowledge Systems, referring to “knowledge items” and “relational knowledge items”.  In the more specific language to be introduced in Section 4 below, knowledge items are {Concepts, HyperEdges, Hypergraphs, ConceptInheritanceLinks, HypergraphInheritanceLinks}, whereas relational knowledge items are all of the above except Concepts.

 

3.  The Novamente Core

 

The OE architecture proposed here will use as its back end a piece of C++ software known as the Novamente core.  The Novamente core was created primarily to serve as the back end for a system called the Novamente AI Engine.   However, the Novamente core can also be used to support a variety of other AI architectures, including for instance neural net algorithms or predicate logic based reasoning systems.

 

The Novamente core is currently proprietary to Novamente LLC, but we could make it open-source in order to build the OE in collaboration with other organizations without legal complications.

 

Essentially, an instance of the Novamente core consists of:

 

A table called the AtomTable, containing an efficient representation of a large labeled, weighted hypergraph.  The AtomTable is implemented so as to support distributed knowledge storage.  It is space-efficient yet supports a number of time-efficient access mechanisms, an achievement which has required a fair amount of cleverness in terms of designing special table indices, etc.

 

A queue of objects called MindAgents, which act on the AtomTable.  These include some housekeeping MindAgents, such as those which poll for external input, collect garbage, collect and report system statistics, periodically save the AtomTable to disk, etc.  MindAgents are scheduled by a sophisticated scheduling mechanism that allows non-conflicting MindAgents to operate simultaneously on the different processors of an SMP machine.

 

An interface called nmshell, a customized Unix shell that allows commands to be sent to and from a running core in a convenient way

 

There are also mechanisms for saving the contents of the AtomTable as XML or as DB records in a traditional DB, although these mechanisms are not currently fully functional and require some updating.

 

Currently the Novamente core runs only on Unix.  It has been tested extensively on RedHat and Mandrake Linux, and extension to other Unix flavors will require only some makefile-editing.  To make it run on Windows, using the cygwin package, would require roughly one man-month of effort (earlier versions ran on Windows, but this functionality has not been maintained over time).

 

What the Novamente AI Engine adds to this framework are:

 

 

Most of the Novamente Atom types are either Nodes or Links.  Nodes are essentially 0-ary relations, whereas Links are n-ary relations.  Novamente supports Nodes that contain small executable programs as well as Nodes that contain data of various types, and it supports Nodes that contain directed acyclic graphs representing complex executable programs or complex logical relationships.

 

The Novamente core is not in itself tied to these specialized Atom types or MindAgents, and can be used for any AI method that can be cast into the form of algorithms for acting on and querying some specialized type of labeled, weighted hypergraph.

 

 

4.  Sketch of OE Object Structure

 

Access to the OE will involve two mechanisms:

 

 

One use of the C++ API is to customize a particular OE variant.  For instance, the OE version 1 design supports various mechanisms for naming and labeling knowledge items, and various definitions of knowledge-item weight.  Future versions may support further customizable features.  Customizable features are to be specified by creating new C++ classes subclassing appropriate abstract classes in the OE C++ API.  OE must then be re-compiled following the modifications.  There is also the option to use defaults for everything, e.g. single-number weights and String labels/names.

 

Once the configurable features of the OE have been set, there are two ways to interact with the OE:

 

  1. Direct calls to the C++ API, through another C++ program or through appropriate calls from a program in another language (e.g. native method calls in a Java program)
  2. Commands issued via the OEshell

 

These mechanisms are basically equivalent and the choice depends on convenience in the context of a particular application.  The OE C++ API provides some methods for comparing different Knowledge Systems, which are not included in the OEshell command set, as the latter is focused on dealing with a single KS at a time.

In dealing with the Novamente AI Engine, we often find it handy to have other programs produce length nmshell scripts and then load these scripts into the Novamente AI Engine; it seems likely that this will be a handy way of interacting with OE as well. 

 

The remainder of this section gives a loose description of a collection of software objects.  It should be assumed that each object gets an appropriate constructor method, and appropriate get and set methods; I won’t describe these explicitly here.  (The pseudocode used is roughly Java-ish in syntax; multiple inheritance is assumed in a couple places but this is only of the innocuous sort achievable via Java interfaces.)

 

This is definitely a “conceptual, pseudocode-ish API”; efficiency is not being considered here.  Things may look fairly different in detail when we create the actual API, but the logic and overall object structure will be about the same as here.  For example, I use arrays frequently here but it’s possible that other container classes will be substituted for the real implementation, etc.

 

The “code comments” accompanying the pseudocode object structure sketched below contain significant information in some cases; hence are worth reading…

 

Please note that the classes described here are not classes that exist within the Novamente core.  Rather, these are special OE “wrapper” classes.  Inside the OE implementation, these classes will be unwrapped appropriately into Novamente Atoms and commands to Novamente MindAgents.  However, the idea of the API is that the OE programmer should not have to know anything about Novamente Atoms or MindAgents, but only about directly OE-relevant structures and processes. 

 

 

4.1  Basic Objects

 

 

/* A system for naming entities in the ontology should be provided.

For example, names can be Strings, lists of some sort, etc. */

 

abstract class Name

       String toString()

       fromString(String s) //needed for OEshell

 Boolean equals(Name n)

 

/*The default implementation of Name*/

 

class StringName extends Name

      String myString;

      …

 

/*a marker class to encompass variablenames and concepts*/

 

class ConceptMarker

 

/* A system for naming variables must be provided, for giving queries that involve variable names */

 

class VariableName extends ConceptMarker

String toString()

FromString(String s) //needed for OEshell

Boolean equals(VariableName v)

 

/*default variable name*/

 

class StringVariableName extends VariableName

      …

 

/*The generic notion of a weight.  This supports pdf weights, interval weights, fuzzy weights, pretty much whatever you want, so long as it’s part of a valued metric space*/

 

abstract class Weight

      float distance(Weight w) //distance to another weight object

      float similarity(Weight w, float c) // 2^(-c*this.distance(w))

      float similarity(Weight w) //distance with default c

      float strength() //a single number representing the weight

                  //e.g. the midpoint of an interval weight,

                  //the mean of a pdf weight…

      fromArray(float [])

            // the OEshell requires that a weight be representable

            // as an array of numbers    

      int arrayLen

            //number of #’s in the array repr. of the weight

 

//simple example weight class: a weight is a single number

 

class probabilityWeight extends Weight

      float prob;  //should be in [0,1]

      …

 

//generic notion of a label, just a marker class, with the same

// properties as a name

 

abstract class Label extends Name

 

//typical label

abstract class StringLabel extends label

      String label; …

     

 

 

4.2  Knowledge-bearing Objects

 

//A Concept is a named, labeled entity

 

class Concept extends ConceptMarker

      Name n

      Label L

 

/* an inheritance link between concepts has a weight and a label

This is implicitly an ordered link.  [Unordered links could be designed easily too of course]*/

 

class ConceptInheritanceLink:

      Name source

      Name target

      Weight w

      Label L

 

 

/*I am assuming here that a hyperedge joins n Concepts.  If we want to support hyperedges that join hyperedges or hypergraphs instead of just concepts, this can be supported too*/

 

Class HyperEdge

      Name [] x 

      Int length

      Weight w

      Label L

      Name n

Boolean ordered   // can specify unordered (set-type) hyperedge

                        //or ordered (list-type)

 

/* This is a hyperedge that contains some concrete concepts and some variables. These are to be used as parts of queries */

 

Class VariableHyperEdge

      ConceptMarker [] x

      Boolean ordered

      Weight w  //the weight here is used to specify how important

                  // different hyperedges that compose a single

//query are

 

/* A hypergraph, which is simply a set of hyperedges with a weight and label */

 

class HyperGraph

      HyperEdge []  h

      Weight w

      Label L

      Name n

 

      //computes similarity btw two hypergraphs, a number in [0,1]

 

float getSimilarity(Hypergraph A)

 

//computes the hypergraph that is the intersection of these two //hypergraphs

 

Hypergraph getIntersection(Hypergraph A)

 

 

      //computes the intersection, specifying a number in [0,1]

// telling how much

      // computational effort to spend on the intersection computation

     

Hypergraph getIntersection(Hypergraph A, float effort)

 

 

/* A hypergraph that is a query; its component hyperedges may contain variables

Note that the same variables may span different hyperedges in the query*/

 

class VariableHypergraph

      VariableHyperEdge [] h

 

// Inheritance link between hypergraphs

 

HyperGraphInheritanceLink

      Hypergraph source

      Hypergraph target

      Weight w

      Label L

 

 

4.3  Knowledge Systems

 

 

/* The basic class encapsulating a system of knowledge

The methods of this class are the key methods of the OE */

 

class KnowledgeSystem

     

Name n //each knowledge system has a name

      Concept [] concepts

      HyperGraph [] hypergraphs

      ConceptInheritanceLink [] conceptLinks

      HypergraphInheritanceLink [] hypergraphLinks

 

      // saves a knowledge system in a conventional rdb

SaveKnowledgeSystemToDB(String DBaddress)

 

      //exports ks as XML

SaveKnowledgeSystemAsXML(String filename)

 

      //loads ks from DB into RAM

KnowledgeSystem LoadKnowledgeSystemFromDB(String DBaddress)

 

      //loads from XML into RAM

KnowledgeSystem LoadKnowledgeSystemFromXML(String filename)

 

 

      //default constructor

      KnowledgeSystem createEmptyKnowledgeSystem(Name n)

 

      // add stuff to knowledge system

 

      addConcept(Concept c)

      addConceptInheritanceLink(ConceptInheritanceLink c)

      addHyperedge(Hyperedge h)

      add Hypergraph(Hypergraph h)

      add HypergraphInheritanceLink( HypergraphInheritanceLink h)

 

 

      //finds the similarity with another knowledge system

float getSimilarity(KnowledgeSystem B)

     

//finds the intersection with another knowledge system,

//optionally specifying how much effort should be put into it

 

KnowledgeSystem getIntersection(KnowledgeSystem B)

KnowledgeSystem getIntersection(KnowledgeSystem B, float effort)

 

      //processes a query

Hypergraph submitQuery( VariableHypergraph V)

 

      //gets a neighborhood

Hypergraph getNeighborhood(Hypergraph H, int n, threshold e)

 

//gets a neighborhood, specifying only hypergraphs of a

// certain label

 

Hypergraph getNeighborhood(Hypergraph H, int n, threshold e, label [] L)

 

//other variants of “get” are possible of course

 

 

 

 

 

5.  Sketch of OEShell Command Language

 

The OEshell command language is a customized Unix shell, intended specifically for interaction with an OE server.

 

The precise syntax of the OEshell command language will be specified later.  This section simply describes the basic ideas in the form of an initial syntax sketch, and gives some examples of usage.

 

The key point to notice here is the fancy use of shell variables.  For instance, where a  String is specified, a shell variable representing a string may of course be substituted.  But the fancy part is that shell variables representing complex objects may also be used.   This is enabled by having a customized shell.

 

For instance, suppose we create two hyperedges via the commands

 

h1$ = addHyperedge –t (“eat”, “Cliff”, “steak”) -w (.8,.9)

h2$ = addHyperedge –t (“eat”, “Ben”,”rat”) –w (.3,.4)

 

These might represent the pieces of knowledge “Cliff eats steak” and “Ben eats rat”, each with an interval weight.  The “eat”, “Cliff”, “steak” etc. are interpreted by the OE as names of Concepts.

 

We can then create a hypergraph containing these two hyperedges, using the command

 

addHypergraph –t (h1$, h2$)

 

The OEshell recognizes that h1$ stands, not for the command “addHyperedge –t (“eat”, “Cliff”, “steak”) -w (.8,.9)” itself, but rather for the hyperedge produced by the command.

 

Also, note that in the makeVarHypergraph command, I have introduced a special syntax for variables.   A variable is denoted by a string beginning with a !, as in !v1, !v2, etc.  The same variable names can be used across different makeVarHypergraph commands submitted in the same OEshell session, another convenience of having a customized shell.

 

 

5.1  Command List

 

What follows is a list of OEshell commands, based closely on the C++ API described in the previous section:

 

makeKS –n <string>

 

loadKS –l <string>

 

loadKSfromDB –n <string> -l <string>

      // -n = name, -l = location

 

saveKS –l <string>

      // -l = location

 

saveKStoDB –l <string>

 

addCIL –s <string> -t <string> -w <list of numbers>

 

      // -s = source, -t = target, -w = weight

      //the weight object in use determines the

//meaning of the #’s in the w list

 

addHyperedge –t <list of Strings> -w <list of numbers>

[ -lab <string> ] [-n <string>]

 

addHypergraph –t <list of shell vars representing hyperedges>

[ -lab <string> ] [-n <string>]

 

addHIL –s <shell var representing hypergraph>

- t<shell var representing hypergraph> -w <(list of numbers)>

 

getSim –s <shell var repr. hypergraph> -t <shell var repr. hypergraph>

     

getInt –s <shell var repr. hypergraph> -t <shell var repr. hypergraph>

      -o <int>

 

      // -o 1 gives output in text, -o 2 gives it in XML

 

makeVarHyperedge –t <list of Strings or query var names>

-w <list of numbers>

 

makeVarHypergraph –t <list of shell vars repr. Var Hyperedges>

 

query –q <shell var repr. VariableHypergraph) –o <int>

 

getneighbors –q <shell var repr. hypergraph> -rad <int> -thresh <float>

 [-label <list of Strings>]

 

clearvar –l <list of strings>

      //clears a query variable name so it can be freshly reused

 

closeKS

 

 

5.2  Example Session

 

This section contains a brief description of a very simple example session with OEshell. 

 

A String representation for names/labels, and an interval representation for weights, is assumed.

 

Also, for illustration purposes, I have introduced two artificial labels for hyperedges, representing posited hyperedge (relationship) types, VerbRelation and AssociatedSet.

 

 

 

> makeKS –n “test”

> addCIL “cat” “animal” –w (.9,.1)

> addCIL “animal” “lifeform” –w (.9,1)

> addCIL “eats” “does” –w (.9, 1)

> set h1 [addHyperEdge (“eats”, “cat”, “mouse”) –w (.6,1) –lab “VerbRelation”]

> set h2 [addHyperEdge (“eats”, “mouse”, “cat”) –w (0,.1) –lab “VerbRelation”]

> set h3 [addHyperEdge (“mouse”,”cat”) –w (.8.1) –lab “AssociatedSet”]

> set h4 [addHyperGraph ($h1, $h2) –n “PetsEating”]

> set h5 [addHyperGraph ($h2,$h3), -n “CatStuff”]

> getSim($h4,$h5)

.5

> set h6 [makeVarHyperedge(eats,cat,!v1)]

> set h7 [makeVarHypergraph –t $h6]

> query $h7 -o 1

mouse

> getInt ($h4, $h5) –o 1

HyperEdge (“eats”, “mouse”, “cat”) w=(0,.1) lab=VerbRelation)

> saveKS –l “testKS.xml”

> closeKS

 

It must be emphasized that the OEshell is not intended for end user interaction.  Like the nmshell we expect it will have three primary purposes:

 

 

 

 

 

6.  Advanced Capabilities for Future Versions

 

This section reviews the various advanced capabilities mentioned in Section 2 above, which will be left out of OE version 1, but can be added to later versions.

 

These capabilities are a grab-bag: some of them are purely technical back-end extensions and others are fairly serious AI problems.  All of them are things that we did in the WAE, however.

 

 

6.1 Disambiguation. 

 

OE Version 1 will assume that all concepts with the same name, in the same knowledge system, are identical.  No method for “automatic sense disambiguation” will be provided.   This means that, if you load in information about a concept named “cow” it is merged with information about any existing concept in the knowledge base named “cow”.    A message will be sent to the log file when this kind of merging is accomplished.  Optionally, the user can be given the option to perform disambiguation by hand, making the choice in each case of whether to perform the merge or not.

 

Automated disambiguation may be done (and was done in WAE) as follows: When a new named knowledge item is added, a judgment is made regarding its similarity to the existing knowledge item with the same name.   If the similarity is large enough, a merge is made; if not, a new name is assigned to the newly inserted knowledge item.  The algorithms are simple, but our experience shows that substantial domain-dependent tuning is required to achieve adequate performance.  (Making this domain-dependent tuning adaptive is a serious “artificial general intelligence” problem.)

 

 

6.2 Distributed Processing.  

 

Support of query processing across distributed knowledge systems is not terribly difficult on a conceptual level, but involves some thorny CS issues.  It cannot be handled adequately by off-the-shelf distributed processing software platforms; it requires custom code.

. 

First, it requires a back end in which a relational knowledge object in the KS (e.g. an inheritance relation or a hyperedge or hypergraph), instead of pointing directly to the software objects representing the knowledge items it relates (e.g. hypergraphs or concepts), points to handles representing these knowledge items.  The Novamente core system supports this, using a variant of the Transaction Buffer design pattern (in which local handles reduce to direct pointers, while remote handles are interpreted as agent addresses).  Hence, although the Novamente core is currently a one-machine system, its knowledge representation is designed for future extension to distributed processing.  (The WAE used a different but related mechanism, which was not adequately efficient in the single-machine case.)

 

Next, to achieve reasonably efficient processing, one requires a clever knowledge allocation mechanism, that allocates knowledge items to machines based on their relatedness, so that each machine tends to contain closely interrelated pieces of knowledge.  In the use case where new knowledge is rapidly being added and new queries are rapidly being submitted, this knowledge allocation mechanism must be real-time (this was done in WAE). 

 

6.3 Paging. 

 

To support very large knowledge systems, the system should be able to store KS’s partly in RAM and partly in the DB, and automatically page info back and forth between the two.   To make this work really well, some degree of “anticipatory” behavior is required, wherein knowledge objects related to recent queries are proactively loaded into RAM.  This was done in WAE and no major problems were encountered.

 

6.4   Reasoning

 

There are two ways to integrate automated reasoning with the OE. 

 

First, one may simply create reasoning algorithms that read the XML variant of a Knowledge System, and then create new knowledge, which may be loaded into the KS either by directly editing the XML knowledge file, or by the ordinary knowledge addition method.

 

Second, one may create reasoning algorithms that “plug in” directly to an active KS.  The Novamente core supports plug-ins called MindAgents, C++ objects that must support the MindAgent interface.  Many useful tools are supplied for MindAgents to use, e.g. various ways of selecting active knowledge items to act upon, various heuristic AI algorithms, etc.   The Novamente AI engine contains specific MindAgents implementing algorithsm such as probabilistic term logic, neural-net-like association formation and evolutionary programming, many of which could be customized to act on OE knowledge items in a useful way.  But the architecture also supports the introduction of MindAgents implementing completely different AI ideas.

 

6.5   Natural language querying

 

Queries, in the OE framework, are represented by certain command strings.  The translation of NL sentences into command strings is obviously a large problem unto itself.

 

A simple initial approach would be:

 

 

We have NLP toolkits that may be useful in this process, or it may be useful to introduce third-party software, such as iCognate’s Artificial Cognition Engine (ACE), an NLP toolkit that has a fairly strong functionality.  (I know Ed Heflin (creator of ACE and CEO of iCognate) fairly well, and I’m sure he would be quite willing to customize ACE for OE on a contract basis, using inexpensive Vettatech staff to carry out the customization.)

 

 

6.6  Visualization of knowledge structures

 

The visualization and visual editing/creation of Knowledge Systems is a nontrivial issue.  It may be split into at least two subtasks

 

1)      Visualization of a large KS

2)      Visualization and interactive editing of a small segment of a KS

 

The former is probably best handled by creating customized layout algorithms to plug into the open-source Tulip graph visualization program.  Tulip is designed for visualization of large graphs.  It does not, as is, deal with hypergraphs, but its open architecture allows for the plug-in of new layout algorithms, and based on my study so far, it seems it should be possible to customize it for large-hypergraph visualization with reasonable effort.

 

The latter is a different problem entirely, requiring different graph layout algorithms and also serious consideration of human factors issues.  A different customization of Tulip is one possibility here, as is customization of the commercial product “thebrain”, if one could obtain cooperation of the firm producing that product.

 

Generally speaking, there are two ways a visualization component can interact with OE:

 

 

The static approach is easiest for initial testing, but the dynamic approach is not particularly difficult either, unless (as in WAE and the Novamente AI Engine) one has a KS that is continually and rapidly updating itself with new self-created knowledge.

 

 

6.7    Convenient Knowledge Entry by Humans

 

It is possible for humans to enter knowledge into an OE via OEshell, but this is obviously an awkward mechanism for large-scale knowledge entry.

 

Our experience is that graphical mechanisms are also relatively slow and awkward for knowledge entry, and that the best alternative is a special textual format.

 

For this purpose, in the Webmind AI Engine, we created a special knowledge entry format called KNOW, which is described online at http://www.goertzel.org/papers/KNOWSpecification.htm

and in an appendix to Creating Internet Intelligence (Goertzel, 2002).

 

At Webmind Inc. we had about 10 individuals, some with minimal technical background, entering knowledge in this format, and we found it to be reasonably workable.  We do not currently possess a KNOW parser and syntax checker, but these could easily be created.

KNOW has an XML and textual form; the textual form is used for human knowledge entry and the XML form is used for syntax checking and for entry of knowledge into systems such as the Novamente AI Engine or the OE.  (The transformation of KNOW-XML into OE-XML is a simple matter that can be carried out using XSLT or other standard programming methodologies.)