This notebook serves as the supporting material for Chapter 12 Knowledge Representation. In this notebook we will show how to use the code repository to represent the most important aspects of the real world in first order logic, such as action, space, time, thoughts and shopping. In this notebook we will be building representations of various complex domains in first order logic. First, let's load the aima-jar.
In [2]:
%classpath add jar ../out/artifacts/aima_core_jar/aima-core.jar
There are two choices for representing categories in first order logic, predicates and objects.That is, we can use the predicate $ Basketball (b)$ , or we can reify the category as an object, Basketballs. We could then say $Member (b, Basketballs )$, which we will abbreviate as $ b \in Basketballs $ , to say that b is a member of the category of basketballs. We say $Subset(Basketballs, Balls)$, abbreviated as $ Basketballs \subset Balls $, to say that Basketballs is a subcategory of Balls.
First-order logic makes it easy to state facts about categories, either by relating objects to categories or by quantifying over their members. Here are some types of facts, with examples of each:
Let us learn how to represent this using first order logic and the code repository. We will add the code written in each block to the Utils class at the end of the notebook so that the code can be reused. Let us create a basic domain for ontology creation that includes predicates like $Member()$ and $Subset()$. Other constants and presicates can then be later added to this domain.
In [3]:
package aima.notebooks.knowledgerepresentation;
import aima.core.logic.fol.domain.FOLDomain;
FOLDomain domain = new FOLDomain();
domain.addPredicate("Member");
domain.addPredicate("Subset");
return domain.toString();
Out[3]:
Now, let's see how can we incorporate the above five facts into our ontology or knowledge base.
In [5]:
import aima.notebooks.knowledgerepresentation.Utils;
import aima.core.logic.fol.domain.*;
import aima.core.logic.fol.kb.*;
FOLDomain domain = Utils.getOntologyBasicDomain();
// Add the category basketballs to the domain
domain.addConstant("Basketballs");
// Add the basketball BB9 to the domain
domain.addConstant("BB9");
// Add the category Balls
domain.addConstant("Balls");
domain.addConstant("Nine");// because our knowledge doesnot include real numbers
//Add relevant properties
domain.addPredicate("Spherical");
domain.addPredicate("Round");
domain.addPredicate("Orange");
domain.addPredicate("Diameter");
domain.addConstant("Dogs");
domain.addConstant("DomesticatedSpecies");
// Create a knowledgebase
FOLKnowledgeBase kb = new FOLKnowledgeBase(domain);
//BB9 ∈ Basketballs
kb.tell("Member(BB9, Basketballs)");
// Basketballs ⊂ Balls
kb.tell("Subset(Basketballs,Balls)");
// ( x ∈ Basketballs ) ⇒ Spherical(x)
kb.tell("(Member(x,Basketballs) => Spherical(x))");
// Orange(x) ∧ Round(x) ∧ Diameter(x) = 9.5″ ∧ x ∈ Balls ⇒ x ∈ Basketballs
kb.tell("((((Orange(x) AND Round(x)) AND Diameter(x,Nine) AND Member(x, Balls))) => Member(x, Basketballs))");
// Dogs ∈ DomesticatedSpecies
kb.tell("Member(Dogs,DomesticatedSpecies)");
return kb.toString();
Out[5]:
Now, as explained in the text we also require some other relations(such as being disjoint) for the categories. And even if we know that males and females are disjoint, we will not know that an animal that is not a male must be a female, unless we say that males and females constitute an exhaustive decomposition of the animals. A disjoint exhaustive decomposition is known as a partition. The following examples illustrate these three concepts: $$ Disjoint(\{Animals, Vegetables\}) $$ $$ ExhaustiveDecomposition (\{Americans, Canadians , Mexicans\}, NorthAmericans)$$ $$ Partition(\{Males, Females\}, Animals) $$
Now, as far as first order logic is concerned the above three predicates can be defined as follows : $$ Disjoint(s) \iff (\forall c_1 , c_2\quad c_1 \in s \wedge c_2 \in s \wedge c_1 \neq c_2 \implies Intersection(c_1 , c_2 ) = \{ \})$$ $$ ExhaustiveDecomposition (s, c) \iff (\forall i\quad i \in c \iff \exists c_2 \quad c_2 \in s \wedge i \in c_2 )$$ $$ Partition(s, c) \iff Disjoint(s) \wedge ExhaustiveDecomposition (s, c) $$
In order to add these definitions we will have to expand our basic ontology domain to include a few more constants and predicates. The Intersection must be added as a function. Also we must add a constant called Phi for the empty set $\phi$. Also we will later add the definition of intersection as follows:
$$ x \in A\cap B \iff (x\in \wedge x\in B)$$
In [6]:
package aima.notebooks.knowledgerepresentation;
import aima.core.logic.fol.domain.FOLDomain;
FOLDomain domain = new FOLDomain();
domain.addPredicate("Member");
domain.addPredicate("Subset");
domain.addPredicate("Disjoint");
domain.addPredicate("ExhaustiveDecomposition");
domain.addPredicate("Partition");
domain.addFunction("Intersection");
domain.addConstant("Phi");
return domain;
Out[6]:
Now let us create a knowledge base that incorporates the knowledge about categories and their partitions. We will call this categoryKb and we will improve it as we go ahead.
In [7]:
package aima.notebooks.knowledgerepresentation;
import aima.core.logic.fol.domain.*;
import aima.core.logic.fol.kb.*;
FOLDomain domain = Utils.getOntologyBasicDomain();
FOLKnowledgeBase kb = new FOLKnowledgeBase(domain);
// equality axioms
// Reflexivity Axiom
kb.tell("x = x");
// Symmetry Axiom
kb.tell("(x = y => y = x)");
// Transitivity Axiom
kb.tell("((x = y AND y = z) => x = z)");
// Function Intersection Substitution Axiom
kb.tell("(( x = y AND w = z) => ( Intersection(x,w) = Intersection(w,z) ))");
// Predicate Substitution Axioms
kb.tell("((x = y AND v = w AND Member(x,v)) => Member(y,w))");
kb.tell("((x = y AND v = w AND Disjoint(x,v)) => Disjoint(y,w))");
kb.tell("((x = y AND v = w AND ExhaustiveDecomposition(x,v)) => ExhaustiveDecomposition(y,w))");
kb.tell("((x = y AND v = w AND Partition(x,v)) => Partition(y,w))");
// Definition of disjoint Disjoint(s) ⟺ ( ∀ c1,c2 c1 ∈ s ∧ c2 ∈ s ∧ c1 ≠ c2 ⟹ Intersection(c1,c2) = {})
kb.tell(" ( Disjoint(s) <=> (FORALL x,y (( Member(x,s) AND Member(y,s) AND (NOT ( x = y ))) => (Intersection(x,y) = Phi)))) ");
// Definition of ExhaustiveDecomposition ExhaustiveDecomposition(s,c) ⟺ ( ∀i i ∈ c ⟺ ∃ c2 c2 ∈ s ∧ i ∈ c2 )
kb.tell("(ExhaustiveDecomposition(s,c) <=> ( FORALL i ( Member(i,c) => (EXISTS c2 (Member(c2,s) AND Member(i,c2))))))");
// Definition of Partition
kb.tell("(Partition(s,c) <=> ( Disjoint(s) AND ExhaustiveDecomposition(s)))");
// Definition for intersection
kb.tell("( Member(x, Intersection(s,b)) <=> (Member(x,a) AND Member(x,b)))");
//Definition of Phi
kb.tell("(FORALL x NOT Member(x,Phi))");
kb.tell("(Subset(a,b) <=> (FORALL x (Member(x,a) => Member(x,b))))");
return kb;
Out[7]:
Now, let's ask our knowledge base whether GermanShepherd is an animal by telling it that GermanShepherd is a Dog and that all dogs are animals.
In [8]:
import aima.notebooks.knowledgerepresentation.Utils;
import aima.core.logic.fol.domain.*;
import aima.core.logic.fol.kb.*;
FOLDomain domain = new FOLDomain();
domain.addConstant("GermanShepherd");
domain.addConstant("Dog");
domain.addConstant("Animals");
FOLKnowledgeBase kb = Utils.getCategoryKnowledgeBase(domain);
kb.tell("Member(GermanShepherd,Dog)");
kb.tell("Subset(Dog,Animals)");
System.out.println(! kb.ask("Member(GermanShepherd,Animals)").getProofs().isEmpty());
System.out.println(! kb.ask("Member(Dog,Animals)").getProofs().isEmpty());
Out[8]:
For future sections we will need this knowledge base with an extended domain. For this purpose, we have created some helper functions in the Utils class at the end of the notebook.
To specify the composition of a particular object we need the PartOf hierarchy. This is similar to the subset hierarchy in a few aspects. The PartOf relation is transitive and reflexive. So, we have the following relations to add to our knowledge base. $$ PartOf (x, y) \wedge PartOf (y, z) \implies PartOf (x, z) $$ $$ PartOf (x, x) $$
We will use the following statements as our examples and then ask the knowledge base *if Bucharest is a part of Earth**. $$PartOf (Bucharest , Romania )$$ $$PartOf (Romania, EasternEurope )$$ $$PartOf (EasternEurope , Europe)$$ $$PartOf (Europe, Earth)$$
In [9]:
package aima.notebooks.knowledgerepresentation;
import aima.core.logic.fol.domain.*;
import aima.core.logic.fol.kb.*;
FOLDomain domain = new FOLDomain();
domain.addConstant("Bucharest");
domain.addConstant("Romania");
domain.addConstant("EasternEurope");
domain.addConstant("Europe");
domain.addConstant("Earth");
domain.addPredicate("PartOf");
FOLKnowledgeBase kb = Utils.getCategoryKnowledgeBase(domain);
// now add the partof relation
kb.tell("(FORALL x (PartOf(x,x)))");
kb.tell("((PartOf(x,y) AND PartOf(y,z)) => PartOf(x,z))");
// Now add the domain specific knowledge
kb.tell("PartOf(Bucharest,Romania)");
kb.tell("PartOf(Romania,EasternEurope)");
kb.tell("PartOf(EasternEurope,Europe)");
kb.tell("PartOf(Europe,Earth)");
return kb.ask("PartOf(Bucharest,Earth)");
Out[9]:
We motivate you to try the Biped(a) and BunchOf(s) relations from the book using the APIs from the code.
Measurements play an important role in understanding the world around us. They are an important dimension in the description of the world. To represent measurements, we can assume that the universe includes abstract measure objects such as "Length" (maybe the entire set of physical quantities or just the seven fundamental ones). Then, we can have unit functions that take numbers as arguements. We can easily represent the following sentences in first order logic by a process similar to the one demonstrated above. $$ Diameter (Basketball 12 ) = Inches(9.5) $$ $$ ListPrice(Basketball 12 ) = \$(19) $$ $$ d \in Days \implies Duration(d) = Hours(24) $$
The most important thing about measures is not the particular numerical values but the fact that the measures can be ordered. We will code the following example which demonstrates the necessity of ordering for measures quantities. Till now we have not added $LessThan$ and $GreaterThan$ predicates. Let's add them. They are exactly similar to the $PartOf$ predicate. $$e_1 \in Exercises \wedge e_2 \in Exercises \wedge Wrote(Norvig, e_1 ) \wedge Wrote(Russell , e_2 ) \implies Difficulty(e_1 ) > Difficulty(e_2 ) $$ $$e_1 \in Exercises \wedge e_2 \in Exercises \wedge Difficulty(e_1 ) > Difficulty(e_2 ) \implies ExpectedScore (e_1 ) < ExpectedScore (e_2 )$$
In [10]:
package aima.notebooks.knowledgerepresentation;
import aima.core.logic.fol.domain.*;
import aima.core.logic.fol.kb.*;
FOLDomain domain = new FOLDomain();
domain.addConstant("Exercises");
domain.addConstant("Norvig");
domain.addConstant("Russell");
domain.addFunction("Difficulty");
domain.addFunction("ExpectedScore");
domain.addPredicate("Wrote");
domain.addPredicate("LessThan");
domain.addPredicate("GreaterThan");
FOLKnowledgeBase kb = Utils.getCategoryKnowledgeBase(domain);
// Now add the domain specific knowledge
kb.tell("((Member(e1,Exercises) AND Member(e2, Exercises) AND Wrote(Norvig,e1)"+
" AND Wrote(Russell,e2)) => (GreaterThan(Difficulty(e1), Difficulty(e2))))");
return kb;
Out[10]:
Try adding the second condition and experimenting with the knowledge base. Also try to build an ontology about things and stuff( Section 12.2.1).
In the earlier sections, we learnt about Situation Calculus. However, in this notebook we will look at an alternate formalism known as Event Calculus which is based on points of time rather than situations. Event calculus reifies fluents and events. (For examples, refer text). We will represent time intervals by the $Interval(i_1,i_2)$ function($i_1$ represents start time and $i_2$ the finish time). We will use the version of event calculus described in the text which consist of the following predicates:
$T (f, t)$ Fluent $f $is true at time $t$
$Happens(e, i)$ Event $e$ happens over the time interval $i$
$Initiates(e, f, t)$ Event $e $ causes fluent $f$ to start to hold at time $t$
$Terminates(e, f, t)$ Event $ e$ causes fluent $f$ to cease to hold at time $t$
$Clipped (f, i) $ Fluent $f$ ceases to be true at some point during time interval $i$
$Restored (f, i)$ Fluent $f$ becomes true sometime during time interval $i$
The axioms defining the above predicate are as follows:
$Happens(e, (t_1 , t_2 )) \wedge Initiates(e, f, t_1 ) \wedge \neg Clipped (f, (t_1 , t)) \wedge t_1 < t \implies$
$T (f, t)$
$Happens(e, (t_1 , t_2 )) \wedge Terminates(e, f, t_1 ) \wedge \neg Restored (f, (t_1 , t)) \wedge t_1 < t \implies$
$\neg T (f, t)$
$Clipped (f, (t_1 , t_2 )) \iff$
$ \exists e, t, t_3 Happens(e, (t, t_3 )) \wedge t_1 \leq t < t_2 \wedge Terminates(e, f, t)$
$Restored (f, (t_1 , t_2 )) \iff$
$\exists e, t, t_3 Happens(e, (t, t_3 )) \wedge t_1 \leq t < t_2 \wedge Initiates(e, f, t)$
All these axioms can be included in the kb in a way similar to the one used above. Now we will look at an interesting application of Knowledge Representation - The Internet Shopping World.
In this final section we put together all we have learned to encode knowledge for a shopping research agent that helps a buyer find product offers on the Internet. The shopping agent is given a product description by the buyer and has the task of producing a list of Web pages that offer such a product for sale, and ranking which offers are best. For a detailed description of the shopping world refer the text. Here, we will briefly state axioms and then use them in the knowledge base.
The strategy is to start at the home page of an online store and consider all pages that can be reached by following relevant links.The agent will have knowledge of a number of stores, for example:
$Amazon \in OnlineStores \wedge Homepage(Amazon, $“$amazon.com$”$) $
$Ebay \in OnlineStores \wedge Homepage(Ebay, $“$ebay.com$”$)$
Now, a page is relevant to the query if it can be reached by a chain of zero or more relevant category links from a store’s home page, and then from one more link to the product offer. We can define relevance:
$Relevant (page, query) \iff$
$\exists store, home store \in OnlineStores \wedge Homepage(store, home)$
$\wedge \exists url , url_2 RelevantChain(home, url_2 , query) \wedge Link (url_2 , url )$
$\wedge page = Contents(url )$
Here the predicate Link (from, to) means that there is a hyperlink from the from URL to the to URL. To define what counts as a RelevantChain, we need to follow not just any old hyperlinks, but only those links whose associated anchor text indicates that the link is relevant to the product query. For this, we use LinkText(from, to, text) to mean that there is a link between from and to with text as the anchor text. A chain of links between two URLs, start and end, is relevant to a description d if the anchor text of each link is a relevant category name for d. The existence of the chain itself is determined by a recursive definition, with the empty chain (start = end ) as the base case:
$RelevantChain(start , end , query) \iff (start = end )$
$\vee (\exists u, text LinkText(start , u, text ) \wedge RelevantCategoryName (query, text )$
$\wedge RelevantChain(u, end , query))$
The $RelevantCategoryName (query, text )$ is true when one of the following holds:
The logical definition of RelevantCategoryName is as follows:
$RelevantCategoryName (query, text ) \iff$ $ (query \subset text \vee text \subset query )$
Now,the only missing element is the Contents(url ) function, which refers to the HTML page at a given URL. The agent doesn’t have the page contents of every URL in its knowledge base; nor does it have explicit rules for deducing what those contents might be. Instead, we can arrange for the right HTTP procedure to be executed whenever a subgoal involves the Contents function. In this way, it appears to the inference engine as if the entire Web is inside the knowledge base. This is an example of a general technique called procedural attachment, whereby particular predicates and functions can be handled by special-purpose methods.
We also need a large taxonomy of categories as mentioned in figure 12.9. For a real world system, enlisting around a thousand categories would be useful for the customer.Now, let us encode this into our knowledge base:
In [32]:
package aima.notebooks.knowledgerepresentation;
import aima.core.logic.fol.domain.*;
import aima.core.logic.fol.kb.*;
FOLDomain domain = new FOLDomain();
domain.addConstant("Amazon");
domain.addConstant("Ebay");
domain.addConstant("amazon");
domain.addConstant("ebay");
domain.addConstant("OnlineStores");
domain.addConstant("ebay");
domain.addFunction("Contents");
domain.addPredicate("Relevant");
domain.addPredicate("Link");
domain.addPredicate("LinkText");
domain.addPredicate("RelevantCategoryName");
domain.addPredicate("RelevantChain");
domain.addPredicate("Homepage");
FOLKnowledgeBase kb = Utils.getCategoryKnowledgeBase(domain);
// Now add the domain specific knowledge
kb.tell("(Member(Amazon, OnlineStores) AND Homepage(Amazon,amazon))");
kb.tell("(Member(Ebay, OnlineStores) AND Homepage(Ebay,ebay))");
kb.tell("(Relevant(page,query) <=>"+
"((EXISTS store,home Member(store,OnlineStores) AND Homepage(store,home))"+
" AND (EXISTS url,url2 RelevantChain(home,url2,query) AND Link(url2,url)) AND (page = Contents(url))))");
kb.tell("(RelevantChain(start,end,query) <=> ((start = end) OR (EXISTS u,text (LinkText(start,u,text)"+
" AND RelevantCategoryName(query,text) AND RelevantChain(u,end,query)))))");
kb.tell("(RelevantCategoryName(query,text) <=> (EXISTS c1,c2 Subset(c1,c2) OR Subset(c2,c1)))");
return kb;
Out[32]:
This concludes our implementation of a really simple Internet Shopping Agent, It can be extended to use a variety of axioms and Inference procedures.However, this agent has enough capability that with the right domain-specific knowledge it can actually be of use to a shopper. Because of its declarative construction, it extends easily to more complex applications. The main point of this section is to show that some knowledge representation—in particular, the product hierarchy—is necessary for such an agent, and that once we have some knowledge in this form, the rest follows naturally.
In [33]:
package aima.notebooks.knowledgerepresentation;
import aima.core.logic.fol.domain.*;
import aima.core.logic.fol.kb.*;
public class Utils{
public static FOLDomain getOntologyBasicDomain(){
FOLDomain domain = new FOLDomain();
domain.addPredicate("Member");
domain.addPredicate("Subset");
domain.addPredicate("Disjoint");
domain.addPredicate("ExhaustiveDecomposition");
domain.addPredicate("Partition");
domain.addFunction("Intersection");
domain.addConstant("Phi");
return domain;
}
public static FOLDomain getFiveExampleDomain(){
FOLDomain domain = Utils.getOntologyBasicDomain();
// Add the category basketballs to the domain
domain.addConstant("Basketballs");
// Add the basketball BB9 to the domain
domain.addConstant("BB9");
// Add the category Balls
domain.addConstant("Balls");
domain.addConstant("Nine");// because our knowledge doesnot include real numbers
//Add relevant properties
domain.addPredicate("Spherical");
domain.addPredicate("Round");
domain.addPredicate("Orange");
domain.addPredicate("Diameter");
domain.addConstant("Dogs");
domain.addConstant("DomesticatedSpecies");
return domain;
}
public static FOLKnowledgeBase getFiveExampleKnowledgeBase(){
FOLKnowledgeBase kb = new FOLKnowledgeBase(Utils.getOntologyBasicDomain());
//BB9 ∈ Basketballs
kb.tell("Member(BB9, Basketballs)");
// Basketballs ⊂ Balls
kb.tell("Subset(Basketballs,Balls)");
// ( x ∈ Basketballs ) ⇒ Spherical(x)
kb.tell("(Member(x,Basketballs) => Spherical(x))");
// Orange(x) ∧ Round(x) ∧ Diameter(x) = 9.5″ ∧ x ∈ Balls ⇒ x ∈ Basketballs
kb.tell("((((Orange(x) AND Round(x)) AND Diameter(x,Nine) AND Member(x, Balls))) => Member(x, Basketballs))");
// Dogs ∈ DomesticatedSpecies
kb.tell("Member(Dogs,DomesticatedSpecies)");
return kb;
}
public static FOLKnowledgeBase getCategoryKnowledgeBase(FOLDomain domain){
domain.addPredicate("Member");
domain.addPredicate("Subset");
domain.addPredicate("Disjoint");
domain.addPredicate("ExhaustiveDecomposition");
domain.addPredicate("Partition");
domain.addFunction("Intersection");
domain.addConstant("Phi");
domain.addPredicate("PartOf");
domain.addPredicate("LessThan");
domain.addPredicate("GreaterThan");
FOLKnowledgeBase kb = new FOLKnowledgeBase(domain);
// equality axioms
// Reflexivity Axiom
kb.tell("x = x");
// Symmetry Axiom
kb.tell("(x = y => y = x)");
// Transitivity Axiom
kb.tell("((x = y AND y = z) => x = z)");
// Function Intersection Substitution Axiom
kb.tell("(( x = y AND w = z) => ( Intersection(x,w) = Intersection(w,z) ))");
// Predicate Substitution Axioms
kb.tell("((x = y AND v = w AND Member(x,v)) => Member(y,w))");
kb.tell("((x = y AND v = w AND Disjoint(x,v)) => Disjoint(y,w))");
kb.tell("((x = y AND v = w AND ExhaustiveDecomposition(x,v)) => ExhaustiveDecomposition(y,w))");
kb.tell("((x = y AND v = w AND Partition(x,v)) => Partition(y,w))");
// Definition of disjoint Disjoint(s) ⟺ ( ∀ c1,c2 c1 ∈ s ∧ c2 ∈ s ∧ c1 ≠ c2 ⟹ Intersection(c1,c2) = {})
kb.tell(" ( Disjoint(s) <=> (FORALL x,y (( Member(x,s) AND Member(y,s) AND (NOT ( x = y ))) => (Intersection(x,y) = Phi)))) ");
// Definition of ExhaustiveDecomposition ExhaustiveDecomposition(s,c) ⟺ ( ∀i i ∈ c ⟺ ∃ c2 c2 ∈ s ∧ i ∈ c2 )
kb.tell("(ExhaustiveDecomposition(s,c) <=> ( FORALL i ( Member(i,c) => (EXISTS c2 (Member(c2,s) AND Member(i,c2))))))");
// Definition of Partition
kb.tell("(Partition(s,c) <=> ( Disjoint(s) AND ExhaustiveDecomposition(s)))");
// Definition for intersection
kb.tell("( Member(x, Intersection(s,b)) <=> (Member(x,a) AND Member(x,b)))");
//Definition of Phi
kb.tell("(FORALL x NOT Member(x,Phi))");
kb.tell("(Subset(a,b) <=> (FORALL x (Member(x,a) => Member(x,b))))");
// now add the partof relation
kb.tell("(FORALL x (PartOf(x,x)))");
kb.tell("((PartOf(x,y) AND PartOf(y,z)) => PartOf(x,z))");
//ordering axioms
kb.tell("((LessThan(x,y) AND LessThan(y,z)) => LessThan(x,z))");
kb.tell("((GreaterThan(x,y) AND GreaterThan(y,z)) => GreaterThan(x,z))");
kb.tell("(LessThan(x,y) <=> GreaterThan(y,x))");
return kb;
}
}
Out[33]:
In [ ]: