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
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>>
class CPredicate
{
public:
friend class CFiller;
enum ePrimitive
{
PP,
NOT, AND, OR,
ATRANS, ATTEND, EXPEL, GRASP, INGEST, MBUILD, MOVE, MTRANS, PROPEL, PTRANS, SPEAK, DO };
CPredicate(CPredicate *owner = NULL) throw();
virtual void SetPredicateString(string dConstructionString) throw(
CMisconstructedPredicateString, CFiller::CMisconstructedFiller);
virtual EConclusion Is(shared_auto_ptr<CPredicate> dPredicate,
HYPOTHESISVECTOR *dHypothesis = NULL) throw();
virtual EConclusion IsNot(shared_auto_ptr<CPredicate> dPredicate) throw();
virtual EConclusion Has(shared_auto_ptr<CPredicate> dPredicate,
HYPOTHESISVECTOR *dHypothesis = NULL,
bool recursive = false) throw(CMathematicalError);
virtual void Evaluate() throw(CMathematicalError);
virtual void GetVariables(VARIABLESMAP &dVariables) throw();
virtual shared_auto_ptr<CFiller> GetVariable(string varName) throw();
virtual void ClearVariables() throw();
virtual string ToString(bool multiLine = true) throw(
CMisconstructedPredicateString, CFiller::CMisconstructedFiller);
virtual shared_auto_ptr<CPredicate> GetOwner() const throw();
virtual shared_auto_ptr<CPredicate> GetTopOwner() throw();
virtual ePrimitive GetPrimitive() const throw();
protected:
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;
ePrimitive m_primitive;
ROLEFILLERSMAP m_roleFillerPairs;
VARIABLESMAP m_variables;
CPredicate *m_owner;
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.
class CFiller
{
public:
friend class CPredicate;
virtual string ToString(bool multiLine = true) throw(CMisconstructedFiller);
virtual shared_auto_ptr<CPredicate> GetOwner() const throw();
virtual shared_auto_ptr<CPredicate> GetTopOwner() const throw();
enum eFillerType
{
eContent,
ePredicate,
eVariable,
eNull,
eDefined,
eTime,
eLessThanFiller,
eEqualToFiller,
eGreaterThanFiller,
eNotEqualToFiller
};
protected:
virtual EConclusion Compare(string roleName, CFiller &compareTo,
HYPOTHESISVECTOR *dHypothesis = NULL) throw();
virtual void RecursiveLogicalPredicateValueCompare(
EConclusion &dConclusionSoFar,
CFiller &compareTo, HYPOTHESISVECTOR *dHypothesis = NULL) throw();
eFillerType m_fillerType;
string m_fillerString;
shared_auto_ptr<CPredicate> m_fillerPredicate;
shared_auto_ptr<CFiller> m_inferenceFiller;
CPredicate *m_owner;
private:
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.
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.
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 (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 ((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)
{
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).
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());
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.
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.
