Knowledge Representation, Reasoning and Inference

Knowledge Representation, Reasoning and Inference

Q1.             Give ONE (1) own example for each of the followings:

a.                  Priori knowledge

b.                  Posteriori knowledge

c.                   Tacit knowledge

d.                  Explicit knowledge

e.                  Declarative knowledge

A1. 

a. Knowledge that are universally true, hence they cannot be denied. e.g. All dead will decay.

b. Knowledge that are derived from senses, and they can be true or false e.g. All nice smelling food taste sweet.

c. Unconscious knowledge that cannot defined or expressed in languages e.g. heart breathing, eye blinking

d. Documented knowledge found in books e.g. Economic theories, History of Malaysia.

e. Passive knowledge expressing facts about world e.g. the sun rises in the East.

Q2.             Besides the techniques you have learned in class, knowledge can also be represented in a form of decision table and decision tree.  Explore these two techniques and describe them (if necessary, give examples) in one page length.

A2.

 Fig. 2.0: Typical diagram of a developed Decision table.

Steps to create a Decision table are summarily given as follows:

1.      List all causes in the decision table. 2.  Calculate the number of possible combinations. 3. Fill columns with all possible combinations. 4. Reduce test combinations. 5. Check covered combinations. 6. Add effects to the table.

(NOTE: The adequate information to work on using this technique will be provided)

Application areas of Decision table are: Business Analysis, Programming, Testing, Hardware Design, etc.

Decision tree is a tree-like diagrammatic expression drawn to classify any object (information given) with a view of making decision from the result. It is also one of the techniques in representing knowledge. It aids decision especially when there is a need to plan and organise a sequence of decision and take into account how the choices made at earlier stages and the outcome of possible external events determine the types of decisions and events at later stages of that sequence.  In this technique, the classification is done by testing for the values of certain properties associated with the given information.

Decision tree consists of three nodes (points), with distinctive shapes which give different meaning:

1.      Decision node is represented by square; this is a point when decision has to be taken.

2.      Chance/ Uncertainty node is represented by circle; this is an external event which has an uncertain result.

3.      Result node is represented by triangle; this is the end point of the analysis giving the result of the steps earlier taken.

Q1.           Q3.  Create a frame-based representation for object vehicle.  You must have one super class and two instances.  You are free to determine the slots but their numbers must be 10. The slots must be a combination of single and multi-facets slots.  Your instances must not have the same facets for all slots, however, similarities are allowed to some of the slots.  Your representation must also show that the instances inherit some of their parent’s properties.  At the same time, they must also have their unique properties.

 Q4.             Consider the following story:

”All people that are not poor and are smart are happy.  Those people that can read are smart.  John is wealthy.  Helen can read and is wealthy.  Happy people have exciting lives.  Wealthy people are not poor”. 

a.                  Translate the story into predicate calculus expressions.

b.                  Find someone with an exciting life using the expressions in (a).

A4. a

1.      ᵾW(people(W) ʌ ¬are(W,poor) ʌare(W,smart)→are (W,happy)

2.      ᵾX(people(X) ʌ can(X,read) → are(X,smart)

3.      is(john,wealthy)

4.      can(helen,read) ʌ is(helen,wealthy)

5.      ᵾY(people (Y) ʌare(Y,happy)) → have(Y,exciting_lives)

6.      ᵾZ(people (Z) ʌ are(Z,wealthy)) → ¬are(Z,poor)

b.

Starting from statement 1:

ᵾW(people(W) ʌ ¬are(W,poor) ʌare(W,smart))→are (W,happy)

with statement 2 made above, we can say: W;X / X;W, also with the rule made, we can now have:

ᵾX(people(X) ʌ¬are(X,poor) ʌcan(X,read)) → are(X,happy)

with statement 5 made above, we can say X;Y/ Y;X, also with the rule made, we can now have:

ᵾY(people(Y) ʌ¬are(Y,poor) ʌcan(Y,read)) → have(Y,exciting_lives)

with statement 6 made above, we can say Y;Z / Z;Y, also with the rule, we can now have:

ᵾZ(people(Z) ʌare(Z,wealthy) ʌ can(Z,read)) →have(Z,exciting_lives)

with statement 4 made above, we can say Z;helen, so we can now have:

is(helen,wealthy) ʌ can(helen,read) → have(helen,exciting_lives)

So, Helen is the someone with exciting life. 

   Q5.             The following story is quoted from N. Wirth’s “Algorithms + data structures = programs” (Wirth, 1976).

“I married a widow (lets call her W) who has a grown-up daughter (call her D).  My father (F), who visited us quite often, fell in love with my step-daughter and married her.  Hence my father became my son-in-law and my step-daughter became my mother.  Some months later, my wife gave birth to a son (S1), who became the brother-in-law of my father, as well as my uncle.  The wife of my father, that is, my step-daughter, also had a son (S2).”

Create a set of predicate calculus expressions that represent the above situation.  Add expressions defining basic family relationships, e.g. the definition of father-in-law.  Use Modus Ponens to prove the conclusion that “I am my own grandfather”.

A5.

marry (I,W) ʌ mother(W,D) → step_daughter(I,D)

(fell_in_love(F,D) ʌ marry (F,D)) → (son_in_law(F,I) ʌ mother (D,I))

give_birth(W,S1) → brother_in_law(S,F) ʌ uncle (S,I)

give_birth(D_S2)

grandmother (W,S2)

grandfather(I,I)

           Q6.             You are given some facts as below:

ride(tom,bicycle) ride(X,scooter) ride(X,Y) ride(tom,Scooter,yellow) ride(tom,Y)

Explain, in your own words, the meaning of unification.  Your explanation should reflect your understanding on both pattern matching and instantiation concepts.  You can only use the predicates given above as examples in your explanation.  You may use some or all the predicates.

1.ride(tom,bicycle) 2.ride(X,scooter) 3.ride(X,Y) 4.ride(tom,Scooter,yellow)  5.ride(tom,Y)

A6.  Unification is one of the reasoning and inference concepts; it encompasses the other two concepts which are: Pattern matching and Instantiation. This means before we can conclude that two predicates unify they must have been pattern matched and /or instantiated. Looking at the set of facts/ predicates given below:

Considering predicate number 1 and 3; since both have identical string of symbol; ‘ride’, then both are said to match. Hence, X and Y can be instantiated with constants; tom and bicycle respectively. Conclusively, we say both predicates unify. This is also applicable to predicate number 2 and 5.

Q7.             Consider the rules and facts below: 

(1)     eats(X, meat) Ù walks_on(X, 2_legs) ® is(X, theoropoda)

(2)     eats(X, plant) Ù walks_on(X, 4_legs) ® is(X, sauropoda)

(3)     eats(X, plant) Ù walks_on(X, 2_legs) ® is(X, ornithopoda)

(4)     (is(X, sauropoda) Ú is(X, theoropoda) Ù similar_to(hipbones, modern_crocodiles) ® is(X, saurischia)

(5)     is(X, ornithopoda) Ù resemble(of(hipbones,X), of(hipbones,modern_birds)) ® is(X, ornithischia)

(6)     eats(dino, meat)

(7)     eats(dino, plant)

(8)     walks_on(dino, 2_legs)

(9)     resemble(of(hipbones,dino), of(hipbones,modern_birds))

a.                  Convert the above rules into clausal forms.

b.                  Use resolution to prove that the Dino is an Ornithischia.

 A7. a

1.      ¬ eats(X,meat) ᴠ ¬ walks_on(X,2_legs) ᴠ is(X,theoropoda)

2.      ¬ eats(X,plant) ᴠ ¬ walks_on(X,4_legs) ᴠ is(X,sauropoda)

3.      ¬ eats(X,plant) ᴠ ¬ walks_on(X,2_legs) ᴠ is(X,ornithopoda)

4.       ¬ is(X,sauropoda) ᴠ ¬similar_to(hipbones,modern_crocodiles) ᴠ is(X,saurischa)

5.      ¬ is(X,theoropoda ᴠ ¬similar_to(hipbones,modern_crocodiles) ᴠ is(X,saurischa)

6.      ¬ is(X,ornithipoda) ᴠ ¬ resemble(of(hipbones,X), of(hipbones,modern_birds)) ᴠ is(X,ornithischia)

7.        eats(dino,meat)

8.         eats(dino,plant)

9.         walks_on(dino,2_legs)

10.    resemble(of(hipbones,dino), of(hipbones,modern_birds))

b.

(a)   Resolution to prove that Dino is an Ornithischia: is(dino,ornithischia)

The goal is:   ¬ is(dino,ornithischa)