Click here to Skip to main content
Click here to Skip to main content

The Building of a Knowledge Base Using C++ and an Introduction to the Power of Predicate Calculus

, 11 Feb 2009
Rate this:
Please Sign up or sign in to vote.
An article introducing Conceptual Dependency and predicate calculus operations.

Introduction

How old is your operating system? UHH, that old? I do not mean how long ago you bought it, I meant to ask about its mental age. Is your computer's operating system intelligence the equivalent of a one year old or the equivalent of a ten year old? Well, if you use the same operating system that I do, the answer to that question is most probably that it is equivalent to a foetus more than anything else, or an older being that is not human and has learned how to use that calculator we had left laying around, but can only operate that same calculator if we dictate to him exactly what to input in it. In this article, I will explain and provide the source code in order to bring your computer operating system to a mental age of about a 10 year-old (not that bad for 100K of code). That is, I will bring it to the point where it can answer easy questions following a statement of facts, and also become able to make simple inferences from multiple, initially unrelated facts that are linked together by separate statements.

Background

Typically, inventions are made to resemble us. For historical reasons out of our control, the computer was invented as an object that does not resemble us in any way. Let's face it, we are good at dealing with concepts, but are weak at dealing with syntax (words). On the other side, a computer is extremely good at dealing with syntax (words) - for example, ask a computer to find all occurences of the word 'difficult' in a 2000 pages document - but is useless when having to deal with concepts. As a consequence of that, we have become more and more frustrated with computers that truly cannot support us in the way we are, but instead forces us to betray our conceptual nature in order to use them.

How could we make a computer smarter and finally have a tool that really completes us? The following is a basis to start building upon.

The first element that is used to get to our goal is the use and some understanding of Conceptual Dependency (CD). CD has been around since the 1970s and it basically states that everything can be reduced to a small set of primitives (conceptual atoms) and role-filler pairs (more on that later). There is plenty of documentation available online and in printed publication, but I will give it only a quick overview here (rely more on the online documentation than what I've inserted into this article). Click here for online information on Conceptual Dependency.

In an eggshell (not even a nutshell), CD states that the basic relationship between objects of knowledge can be reduced to a limited amount of primitives.

The action primitives introduced in CD theory are:

  • ATRANS: to change the abstract relationship of an object.
  • ATTEND: an animate object directing a sense organ towards a stimulus.
  • EXPEL: to take something from inside an animate object and force it out.
  • GRASP: to physically grasp an object.
  • INGEST: to take something inside an animate object.
  • MBUILD: to create or combine thoughts internally.
  • MOVE: to move a body part.
  • MTRANS: to transfer information mentally.
  • PROPEL: to apply a force to something.
  • PTRANS: to change the location of an object.
  • SPEAK: an animate object producing a sound.

Another key element introduced by CD is the state primitive PP. A PP - short for Picture Producer - is an object of knowledge that can generate a picture into someone's mind. For example, 'John' can be thought of and generate a corresponding picture, hence, John is a picture producer. We can say the same thing about a car, a plane, a flower, etc.

Each primitive is then associated with a set of role-filler pairs (requiring at least one).

For example, in CD, the concept "John went to New-York in a red car" would look something like this:

PTRANS[ACTOR:PP[NAME:JOHN
                TYPE:PERSON]
       DESTINATION:PP[CITY:NEW-YORK
                      COUNTRY:USA
                      TYPE:LOCATION]
       INSTRUMENT:PP[CLASS:CAR
                     COLOR:RED
                     TYPE:VEHICULE]
       OBJECT:PP[NAME:JOHN
                 TYPE:PERSON]
       TIME:PAST]
Interpretation:
 
The picture-producer object 'John' had a physical location changed where its destination was a city named New-York, located in a country named the USA and used an instrument picture-producer of class car, type vehicle that is of color red.

The beauty of CD is that it completely abstracts the syntax, and I find it useful to hold knowledge in such a way that it can later be retrieved successfully without being constrained by syntax.

The Anatomy of a Predicate

Predicate.JPG

A predicate is composed of a valid primitive and at least one role-filler pair where each filler can be associated any amount of inference fillers. Each filler (including inference fillers) can be static text, a mathematical operation, or a predicate.

With that in mind, let's write a computer program to answer the following questions (starts easy but gets more difficult as we go on):

  • Is a red car a car?
  • Is a car a red car?
  • Is a car of undefined color a car?
  • Is a car a car of undefined color?
  • Is a car of undefined color a red car?
  • Is a red car a car of undefined color?
  • Is a car of defined color a car?
  • Is a car a car of defined color?
  • Is a car of defined color a red car?
  • Is a red car a car of defined color?
  • Is a colored car a car?
  • Is a car a colored car?
  • Is a colored car a red car?
  • Is a red car a colored car?
  • Is a car that is not red a car?
  • Is a car a car that is not red?
  • Is a car that is not red a red car?
  • Is a red car a car that is not red?
  • Is an object that is not a car a car?
  • Is an object that is not a car has anything to do with a car?
  • Is an object that is not a car has anything to do with a boat?
  • Is an object that is not a car a boat?
  • Is a boat an object that is not a car?
  • Is a car an object that is not a car?
  • Is an object that is a car or a boat a car?
  • Is an object that is a car or a boat a red car?
  • Is a car an object that is a car or a boat?
  • Is a red car an object that is a car or a boat?
  • Is an object that is a car and a boat a car?
  • Is an object that is a car and a boat a red car?
  • Is a car an object that is a car and a boat?
  • Is a red car an object that is a car and a boat?
  • Provided the statement "John went to New-York in a red car", How did John go to New-York?, Where did John go?, Who went where?, Who went where and how?, What is the name of the person who went to a defined city? Who will go where?
  • Provided high-school law's of physics (V = Vi + a * t), have Predicate Calculus resolve a simple problem.
  • How tall is Lee if we know the following:
    • "John Smith, 180 cm tall, threw a football 85 yards."
    • "John Wilson is 205 cm tall."
    • "Peter is 142 cm tall."
    • "Peter Walker is 135 cm tall."
    • "John Richter died in the past."
    • "Lee is 20 percent taller than Peter and smaller than John Wilson."
  • Provided that same statements, what happens if I stated that "Lee is 20 percent taller than Peter and smaller than John."
  • Is lee shorter than 200 cm if we know that "Lee, of a height greater than 1.1 times the one of Peter, and shorter than John, travelling in a car at a speed of 3 m/s and accelerates at 1.8 m/s 2 for a period of 3 seconds"?
  • What is the meaning of life?... This one I'll keep for another weekend project.

The attached code executes and produces this output:

"A car":

PP[CLASS:CAR
   TYPE:VEHICULE]

"A red car":

PP[CLASS:CAR
   COLOR:RED
   TYPE:VEHICULE]

        Is a red car a car?: YES

        Is a car a red car?: MAYBE

"A car of undefined color":

PP[CLASS:CAR
   COLOR:{NULL}
   TYPE:VEHICULE]

        Is a car of undefined color a car?: YES

        Is a car a car of undefined color?: YES

        Is a car of undefined color a red car?: NO

        Is a red car a car of undefined color?: NO

"A car of defined color":

PP[CLASS:CAR
   COLOR:{DEFINED}
   TYPE:VEHICULE]

        Is a car of defined color a car?: NO

        Is a car a car of defined color?: NO

        Is a car of defined color a red car?: YES

        Is a red car a car of defined color?: YES

"A colored car":

PP[CLASS:CAR
   COLOR:{COLOR}
   TYPE:VEHICULE]

        Is a colored car a car?: YES, variables: None

        Is a car a colored car?: MAYBE, variables: None

        Is a colored car a red car?: MAYBE, variables: COLOR = RED

        Is a red car a colored car?: YES, variables: COLOR = RED

"A car that is not red":

PP[CLASS:CAR
   COLOR:!RED
   TYPE:VEHICULE]

        Is a car that is not red a car?: YES, variables: None

        Is a car a car that is not red?: MAYBE, variables: None

        Is a car that is not red a red car?: NO, variables: None

        Is a red car a car that is not red?: NO, variables: None

"An object that is not a car":

NOT[VALUE:PP[CLASS:CAR
             TYPE:VEHICULE]]

        Is an object that is not a car a car?: NO, variables: None

        Is an object that is not a car has anything to do with a car?: NO

        Is an object that is not a car has anything to do with a boat?: MAYBE

        Is an object that is not a car a boat?: MAYBE

        Is a boat an object that is not a car?: YES

        Is a car an object that is not a car?: NO

"An object that is a car or a boat":

OR[VALUE1:PP[CLASS:CAR
             TYPE:VEHICULE]
   VALUE2:PP[CLASS:BOAT
             TYPE:VEHICULE]]

        Is an object that is a car or a boat a car?: MAYBE

        Is an object that is a car or a boat a red car?: MAYBE

        Is a car an object that is a car or a boat?: NO

        Is a red car an object that is a car or a boat?: NO

"An object that is a car and a boat":

AND[VALUE1:PP[CLASS:CAR
              TYPE:VEHICULE]
    VALUE2:PP[CLASS:BOAT
              TYPE:VEHICULE]]

        Is an object that is a car and a boat a car?: YES

        Is an object that is a car and a boat a red car?: MAYBE

        Is a car an object that is a car and a boat?: NO

        Is a red car an object that is a car and a boat?: NO

"John went to New-York in a red car":

PTRANS[ACTOR:PP[NAME:JOHN
                TYPE:PERSON]
       DESTINATION:PP[CITY:NEW-YORK
                      COUNTRY:USA
                      TYPE:LOCATION]
       INSTRUMENT:PP[CLASS:CAR
                     COLOR:RED
                     TYPE:VEHICULE]
       OBJECT:PP[NAME:JOHN
                 TYPE:PERSON]
       TIME:PAST]

        How did John went to New-York?: HOW = PP[CLASS:CAR/COLOR:RED/TYPE:VEHICU
LE]

        Where did John go?: WHERE = PP[CITY:NEW-YORK/COUNTRY:USA/TYPE:LOCATION]

        Who went where?: WHERE = PP[CITY:NEW-YORK/COUNTRY:USA/TYPE:LOCATION], WH
O = PP[NAME:JOHN/TYPE:PERSON]

        Who went where and how?: HOW = PP[CLASS:CAR/COLOR:RED/TYPE:VEHICULE], WH
ERE = PP[CITY:NEW-YORK/COUNTRY:USA/TYPE:LOCATION], WHO = PP[NAME:JOHN/TYPE:PERSO
N]

        What is the name of the person who went to a defined city?: CITY = NEW-Y
ORK, NAME = JOHN

        Who will go where?: N/A

******** INTRA-PREDICATE INFERENCE ***********

"The car speeding predicate":

PTRANS[ACCELERATION:2.1
       INITIALSPEED:2
       OBJECT:PP[CLASS:CAR
                 TYPE:VEHICULE]
       TIME:PRESENT
       TIMEPERIOD:4]

"The speeding intra-predicate inference":

PTRANS[ACCELERATION:{DEFINED}
       FINALSPEED:{NULL};='INITIALSPEED'+('ACCELERATION'*'TIMEPERIOD')
       INITIALSPEED:{DEFINED}
       TIMEPERIOD:{DEFINED}]

"The car speeding predicate after intra-predicate inference":

Result: YES

PTRANS[ACCELERATION:2.1
       FINALSPEED:=10.4
       INITIALSPEED:2
       OBJECT:PP[CLASS:CAR
                 TYPE:VEHICULE]
       TIME:PRESENT
       TIMEPERIOD:4]

******** KNOWLEDGE BASE INFERENCE ***********

Populating knowledge base: "Speed inference predicate":

PTRANS[ACCELERATION:{DEFINED}
       FINALSPEED:{NULL};='INITIALSPEED'+('ACCELERATION'*'TIMEPERIOD')
       INITIALSPEED:{DEFINED}
       TIMEPERIOD:{DEFINED}]

Populating knowledge base: "John Smith, 180 cm tall, threw a football 85 yards."
:

PROPEL[ACTOR:PP[HEIGHT:180
                LASTNAME:SMITH
                NAME:JOHN]
       DISTANCE::85
       OBJECT::PP[TYPE:FOOTBALL]
       TIME:PAST]]

Populating knowledge base: "John Wilson is 205 cm tall.":

MBUILD[OBJECT:PP[HEIGHT:205
                 LASTNAME:WILSON
                 NAME:JOHN]]

Populating knowledge base: "Peter is 142 cm tall.":

MBUILD[OBJECT:PP[HEIGHT:142
                 NAME:PETER]]

Populating knowledge base: "Peter Walker is 135 cm tall.":

MBUILD[OBJECT:PP[HEIGHT:135
                 LASTNAME:WALKER
                 NAME:PETER]]

Populating knowledge base: "John Richter died in the past.":

MBUILD[FROM:PP[HEALTH:!-10
               LASTNAME:RICHTER
               NAME:JOHN]
       TIME:PAST
       TO:PP[HEALTH:-10
             LASTNAME:RICHTER
             NAME:JOHN]]

"Creating predicate: Lee is 20 percent taller than Peter and smaller than John W
ilson.":

PP[HEIGHT:AND[VALUE1:>{PETERHEIGHT}*1.2;KB >> PP[NAME:PETER/HEIGHT:{PETERHEIGHT}
]
              VALUE2:<{JOHNHEIGHT};KB >> PP[NAME:JOHN/LASTNAME:WILSON/HEIGHT:{JO
HNHEIGHT}]]
   NAME:LEE]

"Following inference":

PP[HEIGHT:AND[VALUE1:OR[VALUE1:>170.4
                        VALUE2:>162]
              VALUE2:<205]
   NAME:LEE]

Is Lee smaller than 200 cm?: YES

"Creating predicate: Lee is 20 percent taller than Peter and smaller than John."
:

PP[HEIGHT:AND[VALUE1:>{PETERHEIGHT}*1.2;KB >> PP[NAME:PETER/HEIGHT:{PETERHEIGHT}
]
              VALUE2:<{JOHNHEIGHT};KB >> PP[NAME:JOHN/HEIGHT:{JOHNHEIGHT}]]
   NAME:LEE]

"Following inference":

PP[HEIGHT:AND[VALUE1:OR[VALUE1:>170.4
                        VALUE2:>162]
              VALUE2:OR[VALUE1:<180
                        VALUE2:<205]]
   NAME:LEE]

Is Lee smaller than 200 cm?: MAYBE

******** MIXED KNOWLEDGE BASE AND INTRA-PREDICATE INFERENCE ***********

The concept: Lee, of a height greater than 1.1 times the one of Peter, and small
er than John, travelling in a car at a speed of 3 m/s and accelerates at 1.8 m/s
2 for a period of 3 seconds.

"The construction of the predicate":

PTRANS[ACCELERATION:1.8
       INITIALSPEED:3
       INSTRUMENT:PP[CLASS:CAR
                     TYPE:VEHICULE]
       OBJECT:PP[HEIGHT:AND[VALUE1:>{PETERHEIGHT}*1.1;KB >> PP[NAME:PETER/HEIGHT
:{PETERHEIGHT}]
                            VALUE2:<{JOHNHEIGHT};KB >> PP[NAME:JOHN/HEIGHT:{JOHN
HEIGHT}]]
                 NAME:LEE]
       TIME:PRESENT
       TIMEPERIOD:3]

"Following inference":

PTRANS[ACCELERATION:1.8
       FINALSPEED:=8.4
       INITIALSPEED:3
       INSTRUMENT:PP[CLASS:CAR
                     TYPE:VEHICULE]
       OBJECT:PP[HEIGHT:AND[VALUE1:OR[VALUE1:>156.2
                                      VALUE2:>148.5]
                            VALUE2:OR[VALUE1:<180
                                      VALUE2:<205]]
                 NAME:LEE]
       TIME:PRESENT
       TIMEPERIOD:3]

Is Lee smaller than 200 cm?: MAYBE

Using the Code

The CPredicate class is the public entry-point to our solution. It is defined as the following:

#define VARIABLESMAP map<string, vector<shared_auto_ptr<CFiller>>>
#define ROLEFILLERSMAP map<string, shared_auto_ptr<CFiller>>

// PRIMITIVE[ROLE1:FILLER1/ROLE2:FILLER2...] where there is at least one
// role-filler pair.

class CPredicate
{
public:

	friend class CFiller;

	// All primitives allowed are enumerated here. They are divided in 3
         // groups (state, logical and action primitives).

	enum ePrimitive
	{
		// Make sure to maintain s_StatePrimitive_begin and
                  // s_StatePrimitive_end if you change this.
		// State primitives go here:

		PP,		// Picture-Producer

		// Make sure to maintain s_LogicalPrimitive_begin and
                  // s_LogicalPrimitive_end if you change this.
		// Logical primitives go here:

		NOT,		// Not logical primitive, requires the exclusive
                                     // role VALUE
		AND,		// And logical primitive, requires the exclusive
                                     // roles VALUE1 and VALUE2
		OR,		// Or logical primitive, requires the exclusive
                                     // roles VALUE1 and VALUE2

		// Make sure to maintain s_ActionPrimitive_begin and
                  // s_ActionPrimitive_end if you change this.
		// Action primitives go here:

		ATRANS,		// to change the abstract relationship of an object
		ATTEND,		// an animate object directing a sense organ
                                     // towards a stimulus
		EXPEL,		// to take something from inside an animate object
                                     // and force it out
		GRASP,		// to physically grasp an object
		INGEST,		// to take something inside an animate object
		MBUILD,		// to create or combine thoughts internally
		MOVE,		// to move a body part
		MTRANS,		// to transfer information mentally
		PROPEL,		// to apply a force to something
		PTRANS,		// to change the location of an object
		SPEAK,		// an animate object producing a sound
		DO		// anything else
	};

	// ASSUMPTIONS:
	// It needs to be passed the right immediate (not top-most) owner.
	// The object is not ready and fully constructed until SetPredicateString
         // is called and returns without an exception being thrown.

	CPredicate(CPredicate *owner = NULL) throw();

	// PROMISES:
	// It constructs the CPrimitive object based on the string passed to it
         // (which may in turn construct other CPredicate objects).
	// ASSUMPTIONS:
	// A newly created CPredicate object.
	// dConstructionString in the form of PRIMITIVE[ROLE:FILLER] with at least
         // one role-filler pair.

	virtual void SetPredicateString(string dConstructionString) throw(
             CMisconstructedPredicateString, CFiller::CMisconstructedFiller);

	// PROMISES:
	// It will return the conclusion (YES, NO or MAYBE) to specify if the this 
         // CPredicate is a dPredicate and
	// fill dHypothesis with related origin of its conclusions (as there may be
         // more than one).
	// ASSUMPTIONS:
	// Both CPredicate objects needs to be fully constructed (including the call
         // to SetPredicateString).

	virtual EConclusion Is(shared_auto_ptr<CPredicate> dPredicate, 
		HYPOTHESISVECTOR *dHypothesis = NULL) throw();
	
	// PROMISES:
	// It will return the conclusion (YES, NO or MAYBE) to specify if the this
         // CPredicate is not a dPredicate.	
	// ASSUMPTIONS:
	// Both CPredicate objects needs to be fully constructed (including the call
         // to SetPredicateString).
	
	virtual EConclusion IsNot(shared_auto_ptr<CPredicate> dPredicate) throw();

	// PROMISES:
	// It will return the conclusion (YES, NO or MAYBE) to specify if the this
         // CPredicate has a dPredicate and
	// fill dHypothesis with related origin of its conclusions (as there may be
         // more than one).
	// ASSUMPTIONS:
	// Both CPredicate objects needs to be fully constructed (including the call
         // to SetPredicateString).
	// Always call with recursive = false.

	virtual EConclusion Has(shared_auto_ptr<CPredicate> dPredicate, 
		HYPOTHESISVECTOR *dHypothesis = NULL, 
		bool recursive = false) throw(CMathematicalError);

	// PROMISES:
	// This method will resolve all inferences.
	// The inference is not dynamic, but only a snapshot at the time where that
         // metod was called.
	// ASSUMPTIONS:
	// A CPredicate object that is fully constructed (including the call to
         // SetPredicateString). The other used inference objects or resources need
         // to be set-up accordingly.

	virtual void Evaluate() throw(CMathematicalError);

	// PROMISES:
	// This method will return all the variables (including when residing
         // in predicate fillers) and no duplicate will be in the returned values.
	// ASSUMPTIONS:
	// A CPredicate object that is fully constructed (including the call
         // to SetPredicateString).

	virtual void GetVariables(VARIABLESMAP &dVariables) throw();

	// PROMISES:
	// This method will clear all the variables (including the ones residing in
         // predicate fillers).
	// ASSUMPTIONS:
	// A CPredicate object that is fully constructed (including the call to
         // SetPredicateString).

	virtual shared_auto_ptr<CFiller> GetVariable(string varName) throw();

	// PROMISES:
	// This method will clear all the variables (including the ones residing in
         // predicate fillers).
	// ASSUMPTIONS:
	// A CPredicate object that is fully constructed (including the call to
         // SetPredicateString).

	virtual void ClearVariables() throw();

	// PROMISES:
	// The construction of a predicate from the string returned by it would
         // succeed and generate
	// another predicate that is equal to it.
	// ASSUMPTIONS:
	// It needs to be passed a fully built predicate (including lower predicates).
	// Call with mutiLine to false if you want the string all in one line (the '/'
	// separator will be used instead of a new-line and indentation).

	virtual string ToString(bool multiLine = true) throw(
             CMisconstructedPredicateString, CFiller::CMisconstructedFiller);

	// PROMISES:
	// It returns the immediate predicate holding the predicate (or NULL if none).
	// ASSUMPTIONS:
	// A CPredicate object that is fully constructed (including the call to
         // SetPredicateString).
	
	virtual shared_auto_ptr<CPredicate> GetOwner() const throw();

	// PROMISES:
	// It returns the top-most predicate holding the predicate.
	// ASSUMPTIONS:
	// A CPredicate object that is fully constructed (including the call to
         // SetPredicateString).

	virtual shared_auto_ptr<CPredicate> GetTopOwner() throw();

	// PROMISES:
	// It returns the primitive from the predicate.
	// ASSUMPTIONS:
	// A CPredicate object that is fully constructed (including the call
         // to SetPredicateString).

	virtual ePrimitive GetPrimitive() const throw();

protected:

	// Protected methods (refer to the code)...

	// To better identify the predicate type:

	static const ePrimitive s_StatePrimitive_begin = PP;
	static const ePrimitive s_StatePrimitive_end = PP;
	static const ePrimitive s_LogicalPrimitive_begin = NOT;
	static const ePrimitive s_LogicalPrimitive_end = OR;
	static const ePrimitive s_ActionPrimitive_begin = ATRANS;
	static const ePrimitive s_ActionPrimitive_end = DO;

	// Protected members:

	ePrimitive m_primitive;
	ROLEFILLERSMAP m_roleFillerPairs;
	VARIABLESMAP m_variables;
	CPredicate *m_owner;	// We need to keep that as a pointer to avoid
                                    // circular referencing.

private:

	virtual void ProcessInferences() throw(CInferenceNotHandled);
	ePrimitive GetPrimitive(string dPrimitiveString) throw(
             CMisconstructedPredicateString);
	unsigned int m_inferenceCount;
};

The key methods in that class are the Is and the Has methods. Note that primitives are of three different natures, state primitives, logical primitives and action primitives. Each CPredicate object also holds a list of variables that would have been acquiring content throughout its processing. The variables as well as the roleFillerPairs data-member hold CFiller objects that are defined as following.

// A CFiller object is an essential component of a predicate. The predicate reads
// as follow:
// PRIMITIVE[ROLE1:FILLER1{OPTIONAL:;INFERENCEFILLER1}/ROLE2:FILLER2{
// OPTIONAL:;INFERENCEFILLER2}], 
// Each role holds a filler, the CFiller object then holds everything from
// FILLER1 to the right, the right INFERENCEFILLER1 is optional and is another filler
// all together.

// There are many types of fillers:
// - A content filler:		PRIMITIVE[ROLE:CONTENT{
//                                   OPTIONAL:;INFERENCEFILLER}] where CONTENT is text.
// - A predicate filler:	PRIMITIVE[ROLE:PREDICATE{
//                                   OPTIONAL:;INFERENCEFILLER}] where PREDICATE
//                                   is another predicate.
// - A variable filler:		PRIMITIVE[ROLE:{VARIABLE}{
//                                   OPTIONAL:;INFERENCEFILLER}] where VARIABLE is a
//                                   variable name.
// - A null filler:		PRIMITIVE[ROLE:{NULL}{OPTIONAL:;INFERENCEFILLER}]
// - A defined filler:		PRIMITIVE[ROLE:{DEFINED}{OPTIONAL:;INFERENCEFILLER}]
// - A time filler:		PRIMITIVE[ROLE:{TIME}{OPTIONAL:;INFERENCEFILLER}]
//                                   where TIME is a time variable.
// - A less than filler:	PRIMITIVE[ROLE<VALUE{OPTIONAL:;INFERENCEFILLER}] where VALUE
//                                   is a filler or a number.
// - A equal to filler:		PRIMITIVE[ROLE=VALUE{OPTIONAL:;INFERENCEFILLER}]
//                                   where VALUE is a filler or a number.
// - A greater than filler:	PRIMITIVE[ROLE>VALUE{OPTIONAL:;INFERENCEFILLER}] where VALUE
//                                   is a filler or a number.
// - A not equal to filler:	PRIMITIVE[ROLE!VALUE{OPTIONAL:;INFERENCEFILLER}] where VALUE
//                                   is a filler or a number.

// A filler always can track back its owner predicate from the m_owner member.

class CFiller
{
public:
	friend class CPredicate;

	// PROMISES:
	// The construction of a filler from the string returned by it would succeed
         // and generate another filler that is equal to it.
	// ASSUMPTIONS:
	// It needs to be passed a fully built filler (including lower predicates).
	// Call with mutiLine to false if you want the string all in one line (the '/'
	// separator will be used instead of a new-line and indentation).

	virtual string ToString(bool multiLine = true) throw(CMisconstructedFiller);

	// PROMISES:
	// It returns the immediate predicate holding the filler.

	virtual shared_auto_ptr<CPredicate> GetOwner() const throw();

	// PROMISES:
	// It returns the top most predicate to theimmediate predicate holding
         // the filler.

	virtual shared_auto_ptr<CPredicate> GetTopOwner() const throw();

	// Enumeration of all filler types:
	enum eFillerType
	{
		eContent,
		ePredicate,
		eVariable,
		eNull,
		eDefined,
		eTime,
		eLessThanFiller,
		eEqualToFiller,
		eGreaterThanFiller,
		eNotEqualToFiller
	};

protected:

	// PROMISES:
	// This needs to return a conclusion (YES, NO or MAYBE) on the camparation
         // of 2 fillers.
	// In roleName, you need to pass the role of the filler (not the one of
         // compareTo).
	// ASSUMPTIONS:
	// Will return YES, NO or MAYBE depending on its determination.

	virtual EConclusion Compare(string roleName, CFiller &compareTo,
             HYPOTHESISVECTOR *dHypothesis = NULL) throw();

	// Used internally to support the Compare method.
	virtual void RecursiveLogicalPredicateValueCompare(
                  EConclusion &dConclusionSoFar, 
		CFiller &compareTo, HYPOTHESISVECTOR *dHypothesis = NULL) throw();

	// Members:
	eFillerType m_fillerType;			  // The filler type.
	string m_fillerString;			  // A string holding content 
                                                         // (may be empty).
	shared_auto_ptr<CPredicate> m_fillerPredicate;  // A potential predicate
                                                         // (may be empty).
	shared_auto_ptr<CFiller> m_inferenceFiller;	  // The next linked inference
                                                         // filler (may be empty).
	CPredicate *m_owner;			  // The owner of the CFiller object.

	// NOTE: We need to keep m_owner as a pointer to avoid circular referencing.

private:

	// Construction of the CFiller objects is private since it is only achieved by
	// itself or friends.

	CFiller(CPredicate &dPredicate) throw();
	CFiller(CPredicate &dOwner, string dContent) throw(CMisconstructedFiller);
};

To define a new predicate, simply create a new CPredicate object and then call SetPredicateString with the corresponding content.

	// We conceptually define a car.

	shared_auto_ptr<CPredicate> dCarPredicate(new CPredicate());
	dCarPredicate.get()->SetPredicateString("PP[TYPE:VEHICULE/CLASS:CAR]");

For information on shared_auto_ptr (used for garbage collection in C++), refer to the step 1 (Garbage Collection) of this article.

	// We conceptually define a red car.

	shared_auto_ptr<CPredicate> dRedCarPredicate(new CPredicate());
	dRedCarPredicate.get()->SetPredicateString(
             "PP[TYPE:VEHICULE/CLASS:CAR/COLOR:RED]");

To get to the determination if a red car is a car, call the Is method on dRedCarPredicate object. The Is method is a key element to the implementation. The returned value is an EConclusion, which basically is a three-way result: YES, NO or MAYBE. The Is method iterates through each role-filler pairs of the compared object and ensures that each of them can be matched from the current object. For this case, we call the Is method for dRedCarPredicate object (since we want to know if a red car is a car and not the other way around), and we pass dCarPredicate as a parameter.

	EConclusion dConclusion = dRedCarPredicate.get()->Is(dCarPredicate);

Since a red car has more role-filler pairs than a car and that all the role-filler pairs of a car are included, we come to the determination that a red car is indeed a car. The Is method performs additional checks for null and defined fillers (fillers that may be identified to be existant or not). The Is method also keeps track of how it got to its determination by managing a vector of HYPOTHESISVECTOR. This will later be useful in order to ensure that our matches are not enclosed into logical predicates.

EConclusion CPredicate::Is(shared_auto_ptr<CPredicate> dPredicate,
    HYPOTHESISVECTOR *dHypothesis) throw()
{
	if (m_primitive != dPredicate.get()->m_primitive)
	{
		return PerformLogicalPredicateAnalysis(dPredicate);
	}
	ROLEFILLERSMAP::const_iterator iter;
	ROLEFILLERSMAP::const_iterator iter2;
	EConclusion dReturn = YES;
	for (iter = dPredicate.get()->m_roleFillerPairs.begin(); iter !=
             dPredicate.get()->m_roleFillerPairs.end(); iter++)
	{
		iter2 = m_roleFillerPairs.find(iter->first);
		if (iter->second.get()->m_fillerType == CFiller::eNull)
		{
			if (iter2 != m_roleFillerPairs.end())
			{
				return NO;
			}
		}
		else if (iter->second.get()->m_fillerType == CFiller::eDefined)
		{
			if (iter2 == m_roleFillerPairs.end())
			{
				return NO;
			}
		}
		else if (iter2 != m_roleFillerPairs.end())
		{
			EConclusion dCurReturn = iter2->second.get()->Compare(
                               iter->first, *(iter->second.get()));
			if (!((iter2->second.get()->m_fillerType ==
                                     CFiller::eVariable) ||
				(iter->second.get()->m_fillerType ==
                                     CFiller::eVariable)))
			{
				if (dCurReturn < dReturn)
				{
					dReturn = dCurReturn;
				}
				if (dReturn == NO)
				{
					return dReturn;
				}
			}
		}
		else
		{
			if (dHypothesis != NULL)
			{
				dHypothesis->push_back(CHypothesis(MAYBE, this,
                                     dPredicate));
			}
			return MAYBE;
		}
	}
	for (iter = m_roleFillerPairs.begin(); iter != m_roleFillerPairs.end(); iter++)
	{
		if (iter->second.get()->m_fillerType == CFiller::eDefined)
		{
			iter2 = dPredicate.get()->m_roleFillerPairs.find(iter->first);
			if (iter2 == dPredicate.get()->m_roleFillerPairs.end())
			{
				return NO;
			}
		}
		if (iter->second.get()->m_fillerType == CFiller::eVariable)
		{
			iter2 = dPredicate.get()->m_roleFillerPairs.find(iter->first);
			if (iter2 != dPredicate.get()->m_roleFillerPairs.end())
			{
				if (dReturn > MAYBE)
				{
					dReturn = MAYBE;
				}
			}
		}
	}
	if (dHypothesis != NULL)
	{
		dHypothesis->push_back(CHypothesis(dReturn, this, dPredicate));
	}
	return dReturn;
}

If we run our algorithm on our first set of questions, we get the following result:

"A car":

PP[CLASS:CAR
   TYPE:VEHICULE]

"A red car":

PP[CLASS:CAR
   COLOR:RED
   TYPE:VEHICULE]

        Is a red car a car?: YES

        Is a car a red car?: MAYBE

"A car of undefined color":

PP[CLASS:CAR
   COLOR:{NULL}
   TYPE:VEHICULE]

        Is a car of undefined color a car?: YES

        Is a car a car of undefined color?: YES

        Is a car of undefined color a red car?: NO

        Is a red car a car of undefined color?: NO

"A car of defined color":

PP[CLASS:CAR
   COLOR:{DEFINED}
   TYPE:VEHICULE]

        Is a car of defined color a car?: NO

        Is a car a car of defined color?: NO

        Is a car of defined color a red car?: YES

        Is a red car a car of defined color?: YES

"A colored car":

PP[CLASS:CAR
   COLOR:{COLOR}
   TYPE:VEHICULE]

        Is a colored car a car?: YES, variables: None

        Is a car a colored car?: MAYBE, variables: None

        Is a colored car a red car?: MAYBE, variables: COLOR = RED

        Is a red car a colored car?: YES, variables: COLOR = RED

"A car that is not red":

PP[CLASS:CAR
   COLOR:!RED
   TYPE:VEHICULE]

        Is a car that is not red a car?: YES, variables: None

        Is a car a car that is not red?: MAYBE, variables: None

        Is a car that is not red a red car?: NO, variables: None

        Is a red car a car that is not red?: NO, variables: None

It must be noted that in the process of comparing two predicates with the Is method, an acquisition of values matching variables is done. For example, in the Is method being called from the object populated with the predicate PP[CLASS:CAR/COLOR:{COLOR}/TYPE:VEHICULE] being passed the predicate PP[CLASS:CAR/COLOR:RED/TYPE:VEHICULE], the result is a YES, but a variable COLOR was also affected the value RED. The syntax of a variable filler is {VARIABLENAME} and everytime the algorithm encounters a variable throughout its processing, it affects the matching value. The last stated example would not only state that a PP[CLASS:CAR/COLOR:RED/TYPE:VEHICULE] is indeed a PP[CLASS:CAR/COLOR:{COLOR}/TYPE:VEHICULE], but that such initially undefined COLOR is RED. To extract a variable following a Is or Has method invoquation, use the GetVariable or GetVariables methods.

In order to handle the more difficult questions that involve logical primitives within predicates, we need a more exhaustive algorithm. This is implemented into the PerformLogicalPredicateAnalysis method that is invoked at the begining of the Is method.

EConclusion CPredicate::PerformLogicalPredicateAnalysis(
    shared_auto_ptr<CPredicate> dPredicate, HYPOTHESISVECTOR *dHypothesis)
{
	// If no new hypothesis were generated and there is a negation, we
         // may need to generate a maybe.
	if (m_primitive == NOT)
	{
		shared_auto_ptr<CFiller> dFiller = GetFiller("VALUE");
		if ((dFiller.get() != NULL) && 
			(dFiller.get()->m_fillerType == CFiller::ePredicate) && 
			((dFiller.get()->m_fillerPredicate.get())->Is(dPredicate) == NO))
		{
			if (dHypothesis != NULL)
			{
				dHypothesis->push_back(CHypothesis(MAYBE,
                                        dFiller.get()->m_fillerPredicate.get(),
                                        dPredicate));
			}
			return MAYBE;
		}
	}
	if (dPredicate.get()->GetPrimitive() == NOT)
	{
		shared_auto_ptr<CFiller> dFiller = dPredicate.get()->GetFiller("VALUE");
		if ((dFiller.get() != NULL) && 
			(dFiller.get()->m_fillerType == CFiller::ePredicate) && 
			((dFiller.get()->m_fillerPredicate.get())->Is(this) == NO))
		{
			if (dHypothesis != NULL)
			{
				dHypothesis->push_back(CHypothesis(YES,
                                         dFiller.get()->m_fillerPredicate.get(), this));
			}
			return YES;
		}
	}
	if (m_primitive == OR)
	{
		EConclusion dConclusion1 = NO;
		EConclusion dConclusion2 = NO;
		shared_auto_ptr<CPredicate> dPredicate1;
		shared_auto_ptr<CPredicate> dPredicate2;
		shared_auto_ptr<CFiller> dFiller = GetFiller("VALUE1");
		if ((dFiller.get() != NULL) && 
			(dFiller.get()->m_fillerType == CFiller::ePredicate))
		{
			dConclusion1 = dFiller.get()->m_fillerPredicate.get()->Is(
                               dPredicate);
			dPredicate1 = dFiller.get()->m_fillerPredicate;
		}
		dFiller = GetFiller("VALUE2");
		if ((dFiller.get() != NULL) && 
			(dFiller.get()->m_fillerType == CFiller::ePredicate))
		{
			dConclusion2 = dFiller.get()->m_fillerPredicate.get()->Is(
                               dPredicate);
			dPredicate2 = dFiller.get()->m_fillerPredicate;
		}
		// If both sides of an or states the same conclusion, we keep
                  // that conclusion
		if ((dConclusion1 == dConclusion2) && (dConclusion1 != NO))
		{
			if (dHypothesis != NULL)
			{
				dHypothesis->push_back(CHypothesis(dConclusion1,
                                        dPredicate1, dPredicate));
				dHypothesis->push_back(CHypothesis(dConclusion2,
                                        dPredicate2, dPredicate));
			}
			return dConclusion1;
		}
		else if ((dConclusion1 != NO) || (dConclusion2 != NO))
		{
			if (dHypothesis != NULL)
			{
				dHypothesis->push_back(CHypothesis(MAYBE, this,
                                        dPredicate));
			}
			return MAYBE;
		}
	}
	if (m_primitive == AND)
	{
		EConclusion dConclusion1 = NO;
		EConclusion dConclusion2 = NO;
		shared_auto_ptr<CFiller> dFiller = GetFiller("VALUE1");
		if ((dFiller.get() != NULL) && 
			(dFiller.get()->m_fillerType == CFiller::ePredicate))
		{
			dConclusion1 = dFiller.get()->m_fillerPredicate.get()->Is(
                               dPredicate);
			if (dConclusion1 != NO)
			{
				if (dHypothesis != NULL)
				{
					dHypothesis->push_back(CHypothesis(
                                                  dConclusion1,
                                                  dFiller.get()->m_fillerPredicate,
                                                  dPredicate));
				}
			}
		}
		dFiller = GetFiller("VALUE2");
		if ((dFiller.get() != NULL) && 
			(dFiller.get()->m_fillerType == CFiller::ePredicate))
		{
			dConclusion2 = dFiller.get()->m_fillerPredicate.get()->Is(
                                dPredicate);
			if (dConclusion2 != NO)
			{
				if (dHypothesis != NULL)
				{
					dHypothesis->push_back(CHypothesis(
                                                  dConclusion2,
                                                  dFiller.get()->m_fillerPredicate,
                                                  dPredicate));
				}
			}
		}
		if ((dConclusion1 != NO) || (dConclusion2 != NO))
		{
			if (dConclusion1 > dConclusion2)
			{
				return dConclusion1;
			}
		}
	}
	return NO;
}

That allows us to get through our next set of answers.

"An object that is not a car":

NOT[VALUE:PP[CLASS:CAR
             TYPE:VEHICULE]]

        Is an object that is not a car a car?: NO, variables: None

        Is an object that is not a car has anything to do with a car?: NO

        Is an object that is not a car has anything to do with a boat?: MAYBE

        Is an object that is not a car a boat?: MAYBE

        Is a boat an object that is not a car?: YES

        Is a car an object that is not a car?: NO

"An object that is a car or a boat":

OR[VALUE1:PP[CLASS:CAR
             TYPE:VEHICULE]
   VALUE2:PP[CLASS:BOAT
             TYPE:VEHICULE]]

        Is an object that is a car or a boat a car?: MAYBE

        Is an object that is a car or a boat a red car?: MAYBE

        Is a car an object that is a car or a boat?: NO

        Is a red car an object that is a car or a boat?: NO

"An object that is a car and a boat":

AND[VALUE1:PP[CLASS:CAR
              TYPE:VEHICULE]
    VALUE2:PP[CLASS:BOAT
              TYPE:VEHICULE]]

        Is an object that is a car and a boat a car?: YES

        Is an object that is a car and a boat a red car?: MAYBE

        Is a car an object that is a car and a boat?: NO

        Is a red car an object that is a car and a boat?: NO

The Has method was also needed in order to answer some of the previous questions. The Has method is fairly similar to the Is method, but it drills down the used CFiller predicate objects to match with one. It does so while taking into account that a match may itself be enclosed within a logical predicate, consequentely changing the outcome.

EConclusion CPredicate::Has(shared_auto_ptr<CPredicate> dPredicate,
    HYPOTHESISVECTOR *dHypothesis, bool recursive) throw(CMathematicalError)
{
    HYPOTHESISVECTOR locVector;
    if (!recursive)
    {
        if (dHypothesis == NULL)
        {
            dHypothesis = &locVector;
        }
        dHypothesis->clear();
    }
    VARIABLESMAP keepVariables = m_variables;
    EConclusion dConclusion = Is(dPredicate, dHypothesis);
    if (dConclusion != YES)
    {
        m_variables = keepVariables;
    }
    ROLEFILLERSMAP::const_iterator iter2;
    for (iter2 = m_roleFillerPairs.begin(); (iter2 != m_roleFillerPairs.end()); iter2++)
    {
        if (iter2->second.get()->m_fillerType == CFiller::ePredicate)
        {
            iter2->second.get()->m_fillerPredicate.get()->Has(dPredicate,
                dHypothesis, true);
        }
    }
    if (!recursive)
    {
        if (dHypothesis->size() > 0)
        {
            // Let's look if the Predicate is enclosed within a logical primitive
            dConclusion = NO;
            for (unsigned int i = 0; i < dHypothesis->size(); i++)
            {
                CPredicate *curPredicate = dHypothesis->at(i).m_predicate->m_owner;
                while (curPredicate != NULL)
                {
                    if (curPredicate->GetPrimitive() == NOT)
                    {
                        if (dHypothesis->at(i).m_conclusion == YES)
                        {
                            dHypothesis->at(i).m_conclusion = NO;
                        }
                        else if (dHypothesis->at(i).m_conclusion != MAYBE)
                        {
                            dHypothesis->at(i).m_conclusion = NO;
                        }
                    }
                    else if ((curPredicate->GetPrimitive() == OR) &&
                        (dHypothesis->at(i).m_conclusion == YES))
                    {
                        dHypothesis->at(i).m_conclusion = MAYBE;
                    }
                    curPredicate = curPredicate->m_owner;
                }
                if (dHypothesis->at(i).m_conclusion > dConclusion)
                {
                    dConclusion = dHypothesis->at(i).m_conclusion;
                }
            }
        }
        ResolveIntraPredicateInferences(*dHypothesis);
    }
    return dConclusion;
}

Intra-Predicate Inference

The Is or the Has method can be called with a predicate that has some inference fillers. Take, for example, the case of this predicate:

PTRANS[ACCELERATION:{DEFINED}
    FINALSPEED:{NULL};='INITIALSPEED'+('ACCELERATION'*'TIMEPERIOD')
    INITIALSPEED:{DEFINED}
    TIMEPERIOD:{DEFINED}]

That could be read as 'if the acceleration, the initial speed and the time period are defined, and the final speed is unknown, then the final speed is the initial speed plus the acceleration times the time period.' That is simple High-School physics (V = Vi + a * t). Such a resolution is called an intra-predicate inference (since all the elements of resolution rely within the same given predicate).

// A car that travels at a speed of 2 m/s and accelerates at 2.1 m/s2 for
// a period of 4 seconds.
shared_auto_ptr<CPredicate> dSpeedPredicate(new CPredicate());
dSpeedPredicate.get()->SetPredicateString("PTRANS[OBJECT:PP[TYPE:VEHICULE/CLASS:CAR]/
   INITIALSPEED:2/ACCELERATION:2.1/TIMEPERIOD:4/TIME:PRESENT]");
printf("\"The car speeding predicate\":\n\n%s\n\n",
   dSpeedPredicate->ToString().c_str());
	
// We infer the final speed from that predicate (V = Vi + at)
shared_auto_ptr<CPredicate> dSpeedInferencePredicate(new CKnowledgePredicate());
dSpeedInferencePredicate.get()->SetPredicateString(
    "PTRANS[INITIALSPEED:{DEFINED}/ACCELERATION:{DEFINED}/TIMEPERIOD:{" +
    "DEFINED}/FINALSPEED:{NULL};='INITIALSPEED'+('ACCELERATION'*'TIMEPERIOD')]");
	
printf("\"The speeding intra-predicate inference\":\n\n%s\n\n",
    dSpeedInferencePredicate->ToString().c_str());	
	
dConclusion = HasTest(dSpeedPredicate, dSpeedInferencePredicate);
shared_auto_ptr<CPredicate> dEvaluatedPredicate = dSpeedPredicate;
dEvaluatedPredicate->Evaluate();
printf("\"The car speeding predicate after intra-predicate inference\":\n\nResult:
    %s\n\n%s\n\n", dConclusion.c_str(), dEvaluatedPredicate->ToString().c_str());
"The car speeding predicate":

PTRANS[ACCELERATION:2.1
       INITIALSPEED:2
       OBJECT:PP[CLASS:CAR
                 TYPE:VEHICULE]
       TIME:PRESENT
       TIMEPERIOD:4]

"The speeding intra-predicate inference":

PTRANS[ACCELERATION:{DEFINED}
       FINALSPEED:{NULL};='INITIALSPEED'+('ACCELERATION'*'TIMEPERIOD')
       INITIALSPEED:{DEFINED}
       TIMEPERIOD:{DEFINED}]

"The car speeding predicate after intra-predicate inference":

Result: YES

PTRANS[ACCELERATION:2.1
       FINALSPEED:=10.4
       INITIALSPEED:2
       OBJECT:PP[CLASS:CAR
                 TYPE:VEHICULE]
       TIME:PRESENT
       TIMEPERIOD:4]

Knowledge Base Inference

In order to infer from initially unrelated objects of knowledge, a knowledge base is required. Take, for example, the statement "Lee is 20 percent taller than Peter and smaller than John Wilson."

The first step in order to populate the inferenced value (height) has to do with the construction and maintenance of a knowledge base. Such knowledge base is populated with CKnowledgePredicate objects, that are defined as following:

class CKnowledgePredicate: public CPredicate
{
public:
	virtual void SetPredicateString(string dConstructionString) throw(
             CMisconstructedPredicateString, CFiller::CMisconstructedFiller);
};

The implementation is as following:

void CKnowledgePredicate::SetPredicateString(string dConstructionString) throw(
    CMisconstructedPredicateString, CFiller::CMisconstructedFiller)
{
	CPredicate::SetPredicateString(dConstructionString);
	vector<ePrimitive> dPrimitivesVector;
	vector<CFiller::eFillerType> dFillerTypes;
	EnumeratePrimitivesAndFillersUsed(dPrimitivesVector, dFillerTypes);
	bool hasActionPrimitive = false;
	unsigned int i;
	for (i = 0; ((i < dPrimitivesVector.size()) && (!hasActionPrimitive)); i++)
	{
		hasActionPrimitive = ((dPrimitivesVector[i] >=
                      s_ActionPrimitive_begin) && (dPrimitivesVector[i] <=
                      s_ActionPrimitive_end));
	}
	if (!hasActionPrimitive)
	{
		throw(CMisconstructedPredicateString(
                      "No action primitive in knowledge predicate."));
	}
	bool hasForbidenFillerTypes = false;
	for (i = 0; ((i < dFillerTypes.size()) && (!hasForbidenFillerTypes)); i++)
	{
		hasForbidenFillerTypes = ((dFillerTypes[i] ==
                      CFiller::eLessThanFiller) || (dFillerTypes[i] ==
                      CFiller::eGreaterThanFiller));
	}
	if (hasForbidenFillerTypes)
	{
		throw(CMisconstructedPredicateString(
                      "A forbiden filler type is used to construct predicate."));
	}
}

The implementation of CKnowledgePredicate further constrains how a CPredicate object should be. There are some simple reasons for that. For example, I could not add in a knowledge base the predicate PP[CLASS:CAR/TYPE:VEHICULE] ("a car") and expect anything useful from it. Just by stating "a car," no new knowledge is acquired. The same could be said about the predicate "a car or a boat." Hence, the new condition of having at least one action primitive is added to the implementation of CKnowledgePredicate. Once an action primitive is included into a predicate, it indeed is a knowledge predicate. Another constraint to the implementation of a CKnowledgePredicate relates to the filler types used. The added knowledge needs to be a knowledge of some sort, and not an incertitude. For example, trying to add the predicate MBUILD[OBJECT:PP[HEIGHT:>135/LASTNAME:WALKER/NAME:PETER]] "Peter Walker's height is greater than 135 cm" would fail since we did not acquire a complete knowledge about its height (but rather identified an incertitude). Although the implementation could be modified to relieve that constraint (allowing value ranges, and/or not testing greater and lesser than role-filler pairs), for the time being, it is as such.

At last, a knowledge base is simply defined as following:

class CKnowledgeBase
{
public:
	friend class CKnowledgeBaseInferencePredicate;
	CKnowledgeBase();
	virtual void Add(shared_auto_ptr<CKnowledgePredicate> dNewKnowledge);
protected:
	vector<shared_auto_ptr<CKnowledgePredicate>> m_knowledge_base;
};

The first step is then to populate a knowledge base with facts (some related, others unrelated):

shared_auto_ptr<CKnowledgeBase> dHeightKnowledgeBase(new CKnowledgeBase());

shared_auto_ptr<CKnowledgePredicate> dPredHolder2(new CKnowledgePredicate());
dPredHolder2.get()->SetPredicateString(
    "PROPEL[ACTOR:PP[NAME:JOHN/LASTNAME:SMITH/HEIGHT:180]/" +
    "OBJECT::PP[TYPE:FOOTBALL]/DISTANCE::85/TIME:PAST]]");
dHeightKnowledgeBase->Add(dPredHolder2);
shared_auto_ptr<CKnowledgePredicate> dPredHolder3(new CKnowledgePredicate());
dPredHolder3.get()->SetPredicateString("MBUILD[OBJECT:PP[NAME:JOHN/" +
    "LASTNAME:WILSON/HEIGHT:205]]");
dHeightKnowledgeBase->Add(dPredHolder3);
shared_auto_ptr<CKnowledgePredicate> dPredHolder4(new CKnowledgePredicate());
dPredHolder4.get()->SetPredicateString("MBUILD[OBJECT:PP[NAME:PETER/HEIGHT:142]]");
dHeightKnowledgeBase->Add(dPredHolder4);
shared_auto_ptr<CKnowledgePredicate> dPredHolder5(new CKnowledgePredicate());
dPredHolder5.get()->SetPredicateString("MBUILD[OBJECT:PP[NAME:PETER/" +
    "LASTNAME:WALKER/HEIGHT:135]]");
dHeightKnowledgeBase->Add(dPredHolder5);
shared_auto_ptr<CKnowledgePredicate> dPredHolder6(new CKnowledgePredicate());
dPredHolder6.get()->SetPredicateString("MBUILD[FROM:PP[NAME:JOHN/LASTNAME:RICHTER/" +
    "HEALTH:!-10]/TO:PP[NAME:JOHN/LASTNAME:RICHTER/HEALTH:-10]/TIME:PAST]");
dHeightKnowledgeBase->Add(dPredHolder6);

printf("Populating knowledge base: \"John Smith, 180 cm tall, threw a football" +
    "85 yards.\":\n\n%s\n\n", dPredHolder2.get()->ToString().c_str());
printf("Populating knowledge base: \"John Wilson is 205 cm tall.\":\n\n%s\n\n",
    dPredHolder3.get()->ToString().c_str());
printf("Populating knowledge base: \"Peter is 142 cm tall.\":\n\n%s\n\n",
    dPredHolder4.get()->ToString().c_str());
printf("Populating knowledge base: \"Peter Walker is 135 cm tall.\":\n\n%s\n\n",
    dPredHolder5.get()->ToString().c_str());
printf("Populating knowledge base: \"John Richter died in the past.\":\n\n%s\n\n",
    dPredHolder6.get()->ToString().c_str());

Once that is in place, we need to create a class where the CPredicate behavior would be augmented to refer to a CKnowledgeBase object to obtain resolution of an inference. This is done through the CKnowledgeBaseInferencePredicate class, defined as the following:

class CKnowledgeBaseInferencePredicate: public CPredicate
{
public:
	CKnowledgeBaseInferencePredicate(CPredicate *owner = NULL) throw(
             CMisconstructedPredicateString);
	virtual void Evaluate(shared_auto_ptr<CKnowledgeBase> dKnowledgeBase) throw(
             CMathematicalError);
protected:
	virtual shared_auto_ptr<CPredicate> Factory(string dConstructionString,
             CPredicate *owner = NULL);
	virtual void ProcessInference(string dInference) throw();
	static CKnowledgeBase *m_knowledgebase;
private:
	virtual void Evaluate() throw(CMathematicalError);
};

The key method in this class is the ProcessInference method. That method was declared as virtual in the CPredicate class and it is invoked on each inference fillers to let derived classes resolve them. For the implementation of CKnowledgeBaseInferencePredicate, it is as following:

void CKnowledgeBaseInferencePredicate::ProcessInference(string dInference) throw()
{
	if (dInference.find("KB >> ") == 0)
	{
		SearchAndReplace(dInference, "KB >> ", "", 1);
		shared_auto_ptr<CPredicate> dPredicate(
                      new CKnowledgeBaseInferencePredicate());
		dPredicate.get()->SetPredicateString(dInference);
		if (CKnowledgeBaseInferencePredicate::m_knowledgebase != NULL)
		{
			for (unsigned int i = 0; i <
                               CKnowledgeBaseInferencePredicate::m_knowledgebase->
                               m_knowledge_base.size(); i++)
			{
				CKnowledgeBaseInferencePredicate::m_knowledgebase->
                                         m_knowledge_base[i].get()->ClearVariables();
				if (
                                      CKnowledgeBaseInferencePredicate::m_knowledgebase->
                                      m_knowledge_base[i].get()->Has(dPredicate) != NO)
				{
					VARIABLESMAP dVariables;
					CKnowledgeBaseInferencePredicate::m_knowledgebase->
                                              m_knowledge_base[i].get()->GetVariables(dVariables);
					AppendVariables(dVariables);
				}
			}
		}
	}
}

It basically iterates through each knowledge acquired in the CKnowledgeBase object passed as a parameter to the Evaluate method.

Once all this is in place, we can continue and build our predicate to resolve through knowledge base inference.

// Lee is 20% taller than Peter and smaller than John Wilson

shared_auto_ptr<CPredicate> dHeightPredicate2(new CKnowledgeBaseInferencePredicate());
dHeightPredicate2.get()->SetPredicateString(
    "PP[NAME:LEE/HEIGHT:AND[VALUE1:>{PETERHEIGHT}*1.2;KB >> 
    PP[NAME:PETER/HEIGHT:{PETERHEIGHT}]/VALUE2:<{JOHNHEIGHT};KB >>
    PP[NAME:JOHN/LASTNAME:WILSON/HEIGHT:{JOHNHEIGHT}]]]");
	
printf("\"Creating predicate: Lee is 20 percent taller than Peter and smaller than" +
    "John Wilson.\":\n\n%s\n\n", dHeightPredicate2->ToString().c_str());

((CKnowledgeBaseInferencePredicate*)dHeightPredicate2.get())->Evaluate(
    dHeightKnowledgeBase);

printf("\"Following inference\":\n\n%s\n\n", dHeightPredicate2->ToString().c_str());

shared_auto_ptr<CPredicate> dTestHeightPredicate(new CKnowledgeBaseInferencePredicate());
dTestHeightPredicate.get()->SetPredicateString("PP[NAME:LEE/HEIGHT:<200]");

dConclusion = IsTest(dHeightPredicate2, dTestHeightPredicate);
printf("Is Lee smaller than 200 cm?: %s\n\n", dConclusion.c_str());

Which will generate this output:

Populating knowledge base: "John Smith, 180 cm tall, threw a football 85 yards."
:

PROPEL[ACTOR:PP[HEIGHT:180
                LASTNAME:SMITH
                NAME:JOHN]
       DISTANCE::85
       OBJECT::PP[TYPE:FOOTBALL]
       TIME:PAST]]

Populating knowledge base: "John Wilson is 205 cm tall.":

MBUILD[OBJECT:PP[HEIGHT:205
                 LASTNAME:WILSON
                 NAME:JOHN]]

Populating knowledge base: "Peter is 142 cm tall.":

MBUILD[OBJECT:PP[HEIGHT:142
                 NAME:PETER]]

Populating knowledge base: "Peter Walker is 135 cm tall.":

MBUILD[OBJECT:PP[HEIGHT:135
                 LASTNAME:WALKER
                 NAME:PETER]]

Populating knowledge base: "John Richter died in the past.":

MBUILD[FROM:PP[HEALTH:!-10
               LASTNAME:RICHTER
               NAME:JOHN]
       TIME:PAST
       TO:PP[HEALTH:-10
             LASTNAME:RICHTER
             NAME:JOHN]]

"Creating predicate: Lee is 20 percent taller than Peter and smaller than John W
ilson.":

PP[HEIGHT:AND[VALUE1:>{PETERHEIGHT}*1.2;KB >> PP[NAME:PETER/HEIGHT:{PETERHEIGHT}
]
              VALUE2:<{JOHNHEIGHT};KB >> PP[NAME:JOHN/LASTNAME:WILSON/HEIGHT:{JO
HNHEIGHT}]]
   NAME:LEE]

"Following inference":

PP[HEIGHT:AND[VALUE1:OR[VALUE1:>170.4
                        VALUE2:>162]
              VALUE2:<205]
   NAME:LEE]

Is Lee smaller than 200 cm?: YES

Points of Interest

This project was done within a couple of days and is really only scraping the surface about what could be done with predicate calculus. The most interesting things to do as an extension of what is exposed in this article comes after further coding implements rules that can dynamically build predicates from natural-language input. That's right, one can build predicates from natural-language input and then all these predicate calculus operations become available to the concepts that were built and populated to a knowledge base.

I intend to assemble my notes on the subject and prepare another article that exposes how predicates can be built from natural-language input and post it here soon. Stay tuned for that.

In relation to this article exclusively, the code could be modified to lift the constraints related to greater or lesser than filler exclusion within a knowledge base predicate. That would add a little complexity, but would result into an even more useful algorithm. Also, the fact that resolution of inferences requires iterating through each and every single item of knowledge held in the knowledge base in the current algorithm is an obvious limitation. The algorithm could easily be improved with a knowledge indexing mechanism. Such knowledge indexing mechanism could be based on an organized structure such as the one explained in this article, where the primary index could be the hierarchy of primitives used into the predicate to compare, and the stored data would be the knowledge predicates. Adapting the algorithm to use such a structure would greatly improve the efficiency and would allow a high number of knowledge predicates to be inferred from.

My professional use of this algorithm relates to speech recognition. Although the entire approach is patent protected under US patent number 7,286,987 and multiple later continuations and cannot be released under a public domain license, it could still be interesting for you to know how that works. Within the context of speech recognition, the phonetic analysis process acquires words candidates, sort of a two dimensional array of potential words having been spoken over time. Once that is in place, the syntactic analysis process takes over and sequences potentially spoken words into syntactically valid sequences of words. Only then the conceptual analysis process will use predicate calculus as or comparable to what is described into this article to extract the valid concepts from the invalid ones (one will always give priority to a pure concept over one that has some kind of inpurity element associated to it). The result is speech recognition that disambiguates based on a conceptual analysis process instead of a straight phonetic analysis process as it is mostly done to this day.

Additional Licensing Notes

Feel free to use this technique and code in your work, however be aware that a limited license is in use; such license excludes commercial and commercial not-for-profit deployments without prior authorization by the author. See license.txt or license.pdf in the included attachment for the entire license agreement.

History

January 1st, 2009: First draft of this article written.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Roy, Philippe
Software Developer (Senior)
Canada Canada
Philippe Roy was a key contributor throughout his 20+ years career with many high-profile companies such as Nuance Communications, IBM (ViaVoice and ProductManager), VoiceBox Technologies, just to name a few. He is creative and proficient in OO coding and design, knowledgeable about the intellectual-property world (he owns many patents), tri-lingual, and passionate about being part of a team that creates great solutions.
 
Oh yes, I almost forgot to mention, he has a special thing for speech recognition and natural language processing... The magic of first seeing a computer transform something as chaotic as sound and natural language into intelligible and useful output has never left him.

Comments and Discussions

 
Generalgood stuff PinmemberWerson Kremlor12-Feb-09 11:52 
GeneralFun stuff. Easy 5 PinmemberFranc Morales11-Feb-09 17:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140902.1 | Last Updated 11 Feb 2009
Article Copyright 2009 by Roy, Philippe
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid