Share PowerPoint. Anywhere!
Attempted to read or write protected memory. This is often an indication that other memory is corrupt.

km tutorial 2006f

Uploaded from authorPOINT Lite
Download as Download Not Available PPT
Presentation Description

No description available

Comments Sign in to comment
Uploaded By:

Mark Inappropriate
 Add to your favorites
Embed URL Thumbnail


Customize embed|   WordPress Embed

Like authorSTREAM?


You can vote once a day till December
10th, Vote Now!
What's up on authorSTREAM?
Contribute a Slide
Views: 18
Like it  ( Likes) Dislike it  ( Dislikes)
Added: February 07, 2008 This presentation is Public
Presentation Category :Education
Tags Add Tags
Presentation StatisticsNew!
Views on authorSTREAM: 18
Presentation Transcript

KM: The Knowledge Machine A knowledge representation and reasoning system : KM: The Knowledge Machine A knowledge representation and reasoning system


What is KM? : What is KM? A Knowledge Representation Language (KRL) (like KIF, or CycL, or …) an interpreter sitting on top of Lisp expressive formal semantics A Reasoning Engine backward chaining automatic classification reasoning with actions (simulation) defaults (inheritance with overrides) Mature Free


What Do You Do with KM? : What Do You Do with KM? Create Knowledge Bases descriptions of things in the world objects, events, properties, relationships descriptions of the rules that allow us to reason about things in the world Ask Questions about Knowledge what are the facts? what can be inferred from the facts? what can be inferred from the inferences from facts? Run Simulations in the World Described in the KB what would be the state of objects if certain events took place?


Representing Knowledge : Representing Knowledge What are the kinds of things in the world? Event, Object, Artifact, Device, Computer, … What are the real individual things of each kind? PartyAtMyHouseThisSaturday, ThePCInMyOffice What properties hold for all individuals of some kind? all events occur at some place and time most computers have hard drives What properties hold for specific individuals? this lecture is at 3:30pm, your favorite color is green How do kinds of things relate to each other? all Computers are Devices, all People have a Mother How do individuals relate to each other? Thomas’ father is Bob, Texas is part of the USA


An Informal Knowledge Base : An Informal Knowledge Base Classes Event, Object, Artifact, Device, Computer, Person, Place, Hard-Drive are Classes every Event e occurs at a time-of-occ t and place-of-occ p The superclass of Computer is Device every Person p1 has a mother p2 most Computers c have a part h that is a Hard-Drive Instances PartyAtMyHouseThisSaturday is an instance of Event ThePCInMyOffice is an instance of Computer ThisLecture is an instance of Event with time-of-occ 3:30pm You is an instance of Person with favorite-color green Thomas is an instance of Person with father Bob (a Person) Texas is an instance of Place with is-part-of USA (a Place)


KM for Representing Knowledge : KM for Representing Knowledge English ThePCInMyOffice is an instance of Computer the superclass of Computer is Device Is ThePCInMyOffice a Device? FOPC Computer(ThePCInMyOffice) x Computer(x)  Device(x) Device(ThePCInMyOffice) KM (ThePCInMyOffice has (instance-of (Computer)) ) (Computer has (superclasses (Device)) ) (ThePCInMyOffice isa Device) (t)


This Tutorial : This Tutorial Overview of the KM language and inference based on a detailed script of using KM the examples are “toy” Not a tutorial in how to do knowledge representation! KM Manuals give the full reference* how to download and run KM details of the syntax logical semantics for the expressions Tutorial works best if you ask lots of questions!! * http://www.cs.utexas.edu/~mfkb/km.html


Interaction with KM : Interaction with KM Interaction with KM: read-eval-print User gives KM an expression (assertion/query) KM “reads” the expression given by the user evaluates it and prints the result KM> 123 (123) KM> (1 + 1) (2) KM> (the count of MonteCristo) (Edmond) KM> _


Expressions in KM : Expressions in KM The basic expressions in KM are assertions facts and rules about the world queries expressions whose evaluation searches the facts and rules KM> (*Shiner has (instance-of (Cat))) (*Shiner) KM> (*Shiner has (brother (*Kashmir))) (*Shiner) KM> (the brother of *Shiner) (*Kashmir) KM> (the instance-of of *Kashmir) (Cat) How does it know?


Knowledge Bases in KM : Knowledge Bases in KM KM expressions can be loaded from a file into KM More KM expressions can be evaluated by the interpreter, possibly modifying the loaded KB The modified KB can be saved from the KM environment into a file KM> (load-kb "a-family.km") Loading a-family.km... a-family.km loaded! KM> (the father of *Thomas) (*Bob) KM> (the mother of *Thomas) (*BettyJo) KM> (*Bryen has (father (*Thomas))) (*Bryen) KM> (the grandmother of *Bryen) (*BettyJo) KM> (save-kb "a-family2.km") a-family2.km saved!


Instances : Instances Recall: an instance denotes some object in the world a class is a collection of instances1 An instance (individual) evaluates to itself ;;; --- instances --- ;;; "Fred" KM> *Fred (*Fred) ;;; "1" KM> 1 (1) ;;; "1 + 1" KM> (1 + 1) (2) 1 or, more precisely, a class has a collection of instances associated with it (the class’s extension)


“Creating instances” (existential quantification) : “Creating instances” (existential quantification) We can “create” (assert the existence of) an instance of a particular class Logic: x.(x) (e.g. x.Cat(x)) KM: (a ) ;;; "A cat." KM> (a Cat) (_Cat0) ; _Cat0 is a Skolem individual denoting that cat ;;; "A black cat with a head and a tail." KM> (a Cat with (color (*Black)) (parts ((a Head) (a Tail))) ) (_Cat1) KM> (showme _Cat1) (_Cat1 has (instance-of (Cat)) (color (*Black)) (parts ((a Head) (a Tail)))) (_Cat1)


Slots : Slots Slots relate instances together Two ways to specify slots: on existing instances ( has ( ())) directly on new instances when created (a with ( ())) KM> (a Car) (_Car3) KM> (_Car3 has (color (*Silver))) (_Car3) KM> (showme _Car3) (_Car3 has (instance-of (Car)) (color (*Silver))) KM> (a Car with (color (*Silver))) (_Car4) KM> (showme _Car4) (_Car4 has (instance-of (Car)) (color (*Silver)))


Slots : Slots Slots can relate instances together Slots are themselves frames can specify properties of the slot on these frames ;;; --- slot declarations (optional) --- ;;; "'age' is a slot relating physical objects (Physobj) to Numbers. ;;; A physical object has at most one age." KM> (age has (instance-of (Slot)) (domain (Physobj)) (range (Number)) (inverse (is-age-of)) ; name of the inverse slot (cardinality (N-to-1))) ; one age per thing


Superclasses : Superclasses Slots can also give information about classes The syntax is the same as for instances ( has ( ())) KM> (Car has (superclasses (Vehicle)) (subclasses (Hybrid-Car Station-Wagon Sports-Car)) (instances (_Car3 _Car4))) (Car) KM> (the subclasses of Vehicle) (Car)


The Taxonomy (Inheritance Hierarchy) : The Taxonomy (Inheritance Hierarchy) KM> (*Fred has (instance-of (Person))) KM> (Person has (superclasses (Physobj))) KM> (Physobj has (superclasses (Thing))) ;;; "Show me the concept taxonomy." KM> (taxonomy) Thing Number Physobj Car Cat House Person I *Fred I *Joe …. etc….. Classes can themselves be subclasses of (multiple) other classes (taxonomy) shows the entire taxonomy


Instance Frames and Simple Queries : Instance Frames and Simple Queries Frames describe objects in the world list its properties, and relationships to other objects Queries: Form is (the of ) – an “access path” ;;; "Fred is a person." KM> (*Fred has (instance-of (Person))) ;;; "Fred's age is 32." KM> (*Fred has (age (32))) ;;; "Show me the frame representing Fred." KM> (showme *Fred) (*Fred has (instance-of (Person)) (age (32))) ;;; "What is the age of Fred?" KM> (the age of *Fred) (32)


Slot Inverses : Slot Inverses KM keeps track of inverse relations also X→r→Y Y→r-1→X ;;; "Fred owns a car." KM> (*Fred has (owns ((a Car)))) ;;; "What does Fred own?" KM> (the owns of *Fred) (_Car1) ; (Skolem _Car1 created, denoting that car) ;;; "Show me the frame representing that last car." KM> (showme (thelast Car)) (_Car1 has (instance-of (Car)) (owns-of (*Fred))) ; note the inverse slot (default name is "-of")


Embedded Units and Access Paths : Embedded Units and Access Paths Frames can be embedded within frames An access path may be embedded in an access path ;;; --- embedded units --- ;;; "Joe is a person, and owns a red car." KM> (*Joe has (instance-of (Person)) (owns ((a Car with (color (*Red)))))) ;;; --- access paths --- ;;; "What are the color(s) of the thing(s) which Joe owns?" KM> (the color of (the owns of *Joe)) (*Red)


Embedded Units and Access Paths (cont) : Embedded Units and Access Paths (cont) An access path will select all values on a slot. (the of ) To select a subset give a class name in the query (the of ) add a filter (“generate and test”), discussed later (allof (the of ) where ) ;;; "Joe is a person, and owns a car and a teddy bear." KM> (*Joe has (instance-of (Person)) (owns ((a Car) (a Teddy-Bear)))) ;;; "What does Joe own?" KM> (the owns of *Joe) (_Car1 _Teddy-Bear2) ;;; "What vehicles does Joe own?" KM> (the Vehicle owns of *Joe)) (_Car1)


Class Frames and Inheritance : Class Frames and Inheritance Can state properties for all members of a class (every has ( ())) Each instance of that class acquires (inherits) those properties ;;; "People are physical objects" (property of the class) KM> (Person has (superclasses (Physobj))) ;;; "Every person lives in a house." (property of class members) KM> (every Person has (lives-in ((a House)))) ;;; "Every house has a door and a roof." KM> (every House has (parts ((a Door) (a Roof)))) ;;; "What does Joe live in?" KM> (the lives-in of *Joe) (_House3) ;;; "What are the parts of the thing which Joe lives in?" KM> (the parts of (the lives-in of *Joe)) (_Door4 _Roof5)


Self : Self ;;; "Every person likes him/herself" KM> (every Person has (likes (Self))) (Person) KM> (the likes of *Fred) (*Fred) KM> (the likes of *Joe) (*Joe) ;;; "Every person likes their favorite color(s)." KM> (every Person has (likes ((the favorite-color of Self)))) (Person) ;;; "Fred's favorite color is blue." KM> (*Fred has (instance-of (Person)) (favorite-color (*Blue))) (*Fred) KM> (the likes of *Fred) (*Fred *Blue) KM> (the Color likes of *Fred) (*Blue) Within a class frame, Self refers to the instance inheriting the information.


Exercises : Exercises ;; "All professors have (at least) one car which is old, is ;; their favorite color, and was made in Sweden." (Professor has (superclasses (Person))) (every Professor has (owns ( (a Car with (age (*Old)) (color ((the favorite-color of Self))) (made-by ((a Manufacturer with (location (*Sweden))))))))) 1. Write the KM queries to find: - the car that a professor owns - the age of a professor’s car - the location of the manufacturer of the professor’s car 2. Create a KM frame describing the concept of a Car (the Car class): (every Car has ...)


Answers to Exercises : Answers to Exercises 1a. (the Car owns of (a Professor)) 1b. (the age of (the Car owns of (a Professor))) 1c. (the location of (the made-by of (the Car owns of (a Professor)))) 2. For example... (every Car has (color ((a Color))) (age ((a Age-Value))) (made-by ((a Manufacturer))) (parts ((a Chassis) (a Engine) (a Fuel-Tank with (supplies ((the Engine parts of Self)))))))


Exercise : Exercise (Electrophoresis has (superclasses (Process))) (every Electrophoresis has (sample ((a Chemical))) (equipment ((a Separation-unit) (a Syringe))) (subevents ( (a Remove with (object ((the sample of Self))) (location ((the delivery-medium of (the sample of Self))))) (a Insert with (object ((the sample of Self))) (destination ((the Separation-unit equipment of Self))) (equipment ((the Syringe equipment of Self))))))) (Albumin has (superclasses (Chemical))) (every Albumin has (delivery-medium ((a Bottle))) (storage-medium ((a Fridge)))) 3. What is the result of the query: KM> (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin))))))


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin))))))


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) KM> (a Electrophoresis with (sample ((a Albumin)))) (_Electrophoresis5)


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5))


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) KM> (showme _Electrophresis5) (_Electrophoresis5 has (instance-of (Electrophoresis)) (sample ((a Albumin))) (subevents ((a Remove) (a Insert))))


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) (the location of _Remove6)


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) (the location of _Remove6) KM> (showme _Remove6) (_Remove6 has (instance-of (Remove)) (object ((the sample of _Electrophoresis5))) (location ((the delivery-medium of (the sample of _Electrophoresis5)))) (subevents-of (_Electrophoresis5)))


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) (the location of _Remove6) (the delivery-medium of (the sample of _Electrophoresis5))


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) (the location of _Remove6) (the delivery-medium of (the sample of _Electrophoresis5)) KM> (showme _Electrophresis5) (_Electrophoresis5 has (instance-of (Electrophoresis)) (sample ((a Albumin))) (subevents (_Remove6 (a Insert))))


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) (the location of _Remove6) (the delivery-medium of (the sample of _Electrophoresis5)) (the delivery-medium of _Albumin7)


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) (the location of _Remove6) (the delivery-medium of (the sample of _Electrophoresis5)) (the delivery-medium of _Albumin7) KM> (showme _Alubmin7) (_Albumin7 has (instance-of (Albumin)) (sample-of (_Electrophoresis5)) (delivery-medium ((a Bottle))) (storage-medium ((a Fridge))))


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) (the location of _Remove6) (the delivery-medium of (the sample of _Electrophoresis5)) (the delivery-medium of _Albumin7) (a Bottle)


Answers to Exercises : Answers to Exercises 3. _Bottle8 (i.e., a Skolem instance of Bottle). (the location of (the Remove subevents of (a Electrophoresis with (sample ((a Albumin)))))) (the location of (the Remove subevents of _Electrophoresis5)) (the location of _Remove6) (the delivery-medium of (the sample of _Electrophoresis5)) (the delivery-medium of _Albumin7) (a Bottle) _Bottle8


Simple Data Types : Simple Data Types KM> (3.1 isa Number) (t) KM> (3 isa Integer) (t) KM> (3.1 isa Integer) NIL KM> (t = (not NIL)) (t) KM> (f = NIL) NIL KM> ("apocope" isa String) (t) KM> (99 = 100 +/- 2) (t) KM> (99 = 100 +/- 1 %) (t) KM> (4.99999 = 5.00000) (t) KM has numbers, integers, strings, booleans


Rules : Rules ;;; "A person is a voter if he/she is older than 18." KM> (every Person has (is-voter ((if ((the age of Self) >= 18) then *Yes else (if ((the age of Self) < 18) then *No))))) ;;; "Is Fred a voter?" [Fred is 32, asserted earlier] KM> (the is-voter of *Fred) (*Yes) ;;; "Joe is 12 years old." KM> (*Joe has (instance-of (Person)) (age (12))) (*Joe) ;;; "Is Joe a voter?" KM> (the is-voter of *Joe) (*No) The expression for a slot-value may be a rule The rule is evaluated when the slot-value is queried The tests and result of the rule are themselves KM expressions ;;; "Is some generic person a voter?" KM> (the is-voter of (a Person)) NIL


Exercise : Exercise 4. Complete the expression on the “brightness” slot for the concept of a Light, so that the result depends on the light’s switch position. (every Light has (part ((a Switch with (position ((a PositionValue))))) (brightness (...))) (*Up has (instance-of (PositionValue))) (*Down has (instance-of (PositionValue))) (*Bright has (instance-of (BrightnessValue))) (*Dark has (instance-of (BrightnessValue))))


Answers to Exercises : Answers to Exercises 4. (every Light has (part ((a Switch with (position ((a PositionValue)))))) (brightness ( (if ((the position of (the Switch part of Self)) = *Up) then *Bright else (if ((the position of (the Switch part of Self)) = *Down) then *Dark))))) Note that if the position is unknown, then the brightness will be unknown also (which is what we want).


Complex Types : Complex Types ;;; "Jason has two favorite colors" KM> (*Jason has (favorite-color (*Blue *Green))) (*Jason) KM> (the favorite-color of *Jason) (*Blue *Green) ;;; "So does Mike" KM> (*Mike has (favorite-color ((:set *Blue *Green)))) (*Mike) KM> (the favorite-color of *Mike) (*Blue *Green) ;;; "Mike, John and Jason finished 1st, 2nd and 3rd" KM> (a Tournament with (finishers ((:seq *Mike *John *Jason)))) (_Tournament6) ;;; "Mike had scores of 66, 67, 73 and 67 KM> (*Mike has (round-score ((:bag 66 67 73 67)))) (*Mike) KM also has sets, sequences, bags


Arithmetic : Arithmetic ;;; "What is 1 + 1?" KM> (1 + 1) (2) ;;; "A person's age in days is their age [in years] times 365." KM> (every Person has (age-in-days (((the age of Self) * 365)))) (Person) ;;; "What is Fred's age in days?" KM> (the age-in-days of *Fred) (11680) ;;; "What was Mike's total score last week?“ KM> (*Mike has (round-score ((:bag 66 67 73 67)))) (Mike) KM> (the sum of (the round-score of *Mike)) (273) KM has infix operators +, -, *, /, ^ Also has arithmetic slots: (the sum of ….), etc. sum, difference, product, quotient, and others


Set Expressions : Set Expressions ;;; "Show me every person [in the KB so far]?" KM> (every Person) (*Joe *Fred) ;;; or equivalently KM> (the all-instances of Person) (*Joe *Fred) ;;; "Which people are over 18?" KM> (allof (the all-instances of Person) where ((the age of It) > 18)) (*Fred) ;;; "What is the favorite color(s) of the people over 18?" KM> (forall (the all-instances of Person) where ((the age of It) > 18) (the favorite-color of It)) (*Blue) Procedurally, KM iterates over a set of values Two main iterators (allof where ) (forall where ) Keyword It denotes the value in each iteration


Aside: Tracing in KM : Aside: Tracing in KM KM> (*Lily has (instance-of (Person)) (favorite-color (*Lilac)) (age (21))) (*Lily) KM> (trace) (Tracing of KM switched on) KM> (forall (the all-instances of Person) where ((the age of It) > 18) (the favorite-color of It)) 1 -> (forall (the all-instances of Person) where ((the age of It) > 18) (the favorite-color of It)) 2 -> (the all-instances of Person) 2 <- (*Joe *Fred *Lily) [(the all-instances of Person)] 2 -> ((the age of *Joe) > 18) 3 -> (the age of *Joe) 3 <- (12) [(the age of *Joe)] 2 <- FAIL! [((the age of *Joe) > 18)] 2 -> ((the age of *Fred) > 18) 3 -> (the age of *Fred) 3 <- (32) [(the age of *Fred)] 2 <- (t) [((the age of *Fred) > 18)] 2 -> (the favorite-color of *Fred) 2 <- (*Blue) [(the favorite-color of *Fred)] 2 -> ((the age of *Lily) > 18) 3 -> (the age of *Lily) 3 <- (21) [(the age of *Lily)] 2 <- (t) [((the age of *Lily) > 18)] 2 -> (the favorite-color of *Lily) 2 <- (*Lilac) [(the favorite-color of *Lily)] 1 <- (*Blue *Lilac) [(forall ... (*Blue *Lilac) KM> (untrace) (Tracing of KM switched off)


What’s Wrong with Set Expressions? : What’s Wrong with Set Expressions? Two main iterators (allof where ) (forall where ) Keyword It denotes the value in each iteration Hint: if can be any KM expression, could it be an iterator? could and contain iterators?


Set Expressions with Variables : Set Expressions with Variables ;;; "Which people are over 18?" KM> (allof ?x in (the all-instances of Person) where ((the age of ?x) > 18)) (*Fred *Lily) ;;; "What is the favorite color(s) of the people over 18?" KM> (forall ?y in (the all-instances of Person) where ((the age of ?y) > 18) (the favorite-color of ?y)) (*Blue *Lilac) ;;; "What things do people over 18 own that are their favorite colors?" KM> (forall ?p in (the all-instances of Person) where ((the age of ?p) > 18) (allof ?t in (the owns of ?p) where ((the color of ?t) = (the favorite-color of ?p)) ) ) (_Car11 _House13) A slightly more general form allows for nested iterators (allof in where ) (forall in where )


Unification : Unification ;;; "Johanne likes some cute puppy" KM> (*Johanne has (likes ((a Puppy with (trait (*cute)))))) (*Johanne) ;;; "What puppy does Johanne like?“ KM> (the likes of *Johanne) (_Puppy25) ;;; "Victor is a puppy" KM> (*Victor has (instance-of (Puppy)) (color (*brown))) (*Victor) Is it possible that _Puppy25 and *Victor are the same puppy? What would we then know about *Victor?


Unification : Unification The assertion of equality of two objects The merging of data structures associated with instances (_Person3 has (parts ((a Brain))) (name ("Albert"))) ) (_Student4 has (parts ((a Body))) (gpa (9.6))) ) (_Student4 has (parts ((a Brain) (a Body))) (name ("Albert"))) (gpa (9.6)) )


Vertical Unification (Inheritance) : Vertical Unification (Inheritance) Inheritance is a kind of unification An instance of a class is the unification of anonymous instances of all its ancestor classes (every Person has (parts ((a Brain))) ) (every Student has (gpa ((a Number))) ) (_Student4 has (parts ((a Brain) (a Body))) (gpa ((a Number))) ) (every Living-Thing has (parts ((a Body))) ) isa superclasses superclasses _Living-Thing832 _Person834 _Student836 _Student4 = _Living-Thing832 & _Person834 & _Student836 & _Student4


Multiple Inheritance and Unification : Multiple Inheritance and Unification ;;; Can a pet and a fish unify? KM> ((a Pet) &? (a Fish)) (t) ;;; Unify these two objects together KM> ((a Pet) & (a Fish)) (_Pet1) KM> (showme _Pet1) (_Pet1 has (instance-of (Pet Fish))) ;;; Unify these two sets together KM> (((a Cat) (a Dog)) && ((a Cat) (a Rabbit))) (_Cat1 _Dog2 _Rabbit3) If several frames contribute to a slot’s values, KM will unify the different sets of values together set unification is heuristic, not deductive “&” unifies two instances together “&&” unifies two sets together “&?” and “&&?” check if unification is possible (without doing the unification)


Inheritance and Unification: Example : Inheritance and Unification: Example ;;; "Every big car has a large engine." KM> (every Big-Car has (parts ((a Engine with (size (*Large)))))) ;;; "Every powerful car has a powerful engine." KM> (every Powerful-Car has (parts ((a Engine with (power (*Lots)))))) ;;; "Suburbans are both big and powerful cars." KM> (Suburban has (superclasses (Big-Car Powerful-Car))) ;;; "What are the parts of a Suburban?" KM> (the parts of (a Suburban)) (COMMENT: (_Engine7 && _Engine8) unified to be _Engine7) (_Engine7) KM> (showme (thelast Engine)) (_Engine7 has (instance-of (Engine)) (size (*Large)) (power (*Lots)) (parts-of (_Suburban6))) Here KM decides the 2 engines are coreferential because (i) same class (or one’s classes subsumes the others’) (ii) unification doesn’t violate constraints Note result of unification: Engine is both large and has lots of power.


Inheritance & Unification: Another Example : Inheritance & Unification: Another Example ;;; "Every person has two legs and a head." KM> (every Person has (parts ((a Head) (a Leg) (a Leg)))) (Person) ;;; "Fred has a leg." KM> (*Fred has (parts ((a Leg)))) (*Fred) ;;; "What are the parts of Fred?" ;;; [Note: two legs -- KM unifies one of the two legs on Person ;;; with the leg on Fred] KM> (the parts of *Fred) (_Leg9 _Head10 _Leg11) Again, the different contributing value sets are unified together.


Defeating Inheritance : Defeating Inheritance KM> (birth has (domain (Animal)) (instance-of (Slot)) (cardinality (N-to-1))) (birth) KM> (every Mammal has (birth (*Live))) (Mammal) KM> (Platypus has (superclasses (Mammal))) (Platypus) KM> (every Platypus has (birth (*Egg))) (Platypus) KM> (the birth of (a Platypus)) ERROR! Unification (*Egg & *Live) failed! NIL KM> (birth has (inherit-with-overrides (t))) (birth) KM> (the birth of (a Platypus)) (*Egg) There are several tools in KM to control unification One powerful tool is inherit-with-overrides


Constraints : Constraints Can attach constraints to a slot constrains the allowed values on that slot checked when that slot is queried Two types: value constraints: applies to each value in turn (every Witch has (pet ((must-be-a Cat with (color (*Black)))))) (every Witch has (pet ((mustnt-be-a Dog)))) (every Sedan has (doors ((<> 3)))) (a Cat with (color ((constraint (TheValue = *Black))))) (a Witch with (pet ((constraint ((the color of TheValue) = *Black))))) set constraints: applies to the set of values (every Animal has (parts ((at-least 2 Leg)))) (every Human has (parts ((at-most 2 Leg)))) (every Bipod has (parts ((exactly 2 Leg)))) (a Triumvirate with (member ((set-constraint ((the number of TheValues) = 3)))))


Value Constraints : Value Constraints ;;; "A person's friends must all be of class Person." KM> (every Person has (friends ((must-be-a Person)))) ;;; "A person cannot marry him/herself." (<> means "cannot equal") KM> (every Person has (spouse ((<> Self)))) ;;; "Fred's spouse is himself (and Smilla)." KM> (*Fred has (spouse (*Fred *Smilla))) KM> (showme *Fred) (*Fred has (instance-of (Person)) (age (32)) (favorite-color (*Blue)) (spouse (*Fred *Smilla)) (spouse-of (*Fred))) (*Fred) ;;; "Who is Fred's spouse?" [The constraint violation is detected at query time] KM> (the spouse of *Fred) ERROR! Constraint violation! Discarding value *Fred (conflicts with (<> *Fred)) Checks each value in turn, when the slot is queried keyword TheValue denotes the value being tested must-be-a constraints are enforced (not just checked)


Set Constraints : Set Constraints ;;; "Every Airplane has exactly two wings." KM> (every Airplane has (parts ((exactly 2 Wing)))) (Airplane) ;;; General value constraints: TheValue denotes the value being checked. KM> (every Person has (leg-parts ((constraint (TheValue isa Leg))))) ;;; General set constraints: TheValues denotes the set of values being checked. KM> (every Person has (leg-parts ((set-constraint ((the number of TheValues) <= 2))))) Checks the entire set of values on a slot Keyword TheValues denotes the set being tested Useful for at most / at least constraints


Defined Classes and Automatic Classification : Defined Classes and Automatic Classification ;;; "A Texan is a person who lives in Texas, ;;; AND every person living in Texas is a Texan." KM> (every Texan has-definition (instance-of (Person)) (lives-in (*Texas))) KM> (every Texan has (likes (*Willie))) KM> (the instance-of of *Fred) (Person) KM> (*Fred has (lives-in (*Texas))) (COMMENT: *Fred satisfies definition of Texan,) (COMMENT: so changing *Fred's classes from (Person) to (Texan)) (*Fred) KM> (the instance-of of *Fred) (Texan) KM> (the likes of *Fred) (*Willie) Defining properties of a class: Any object with these properties is in that class (every has-definition (instance-of ()) ( ()) ...) If new info found about an instance, its classes are re-checked


Care with Automatic Classification : Care with Automatic Classification KM> (Island-Country has (superclasses (Country))) (Island-Country) KM> (every Island-Country has-definition (instance-of (Country)) (neighbors ((exactly 0 Country)))) (Island-Country) KM> (*USA has (instance-of (Country))) (COMMENT: *USA satisfies definition of Island-Country,) (COMMENT: so changing *USA's classes from (Country) to (Island-Country)) (*USA) KM> (*Canada has (instance-of (Country)) (neighbors (*USA))) (*Canada) KM> (*Spain has (instance-of (Country)) (neighbors (*Portugal))) (COMMENT: *Spain satisfies definition of Island-Country,) (COMMENT: so changing *Spain's classes from (Country) to (Island-Country)) (*Spain) KM is eager with automatic classification as soon as an instance is created or modified, KM (re)checks all classification rules


Exercise : Exercise 5. Create KM frames defining the concept of a RedWine (a red wine) a bachelor a square


Answers to Exercise : Answers to Exercise 5a. (every RedWine has-definition (instance-of (Wine)) (color (*Red))) 5b. (every Bachelor has-definition (instance-of (Man)) (spouse ((exactly 0 Thing)))) 5c. (every Square has-definition (instance-of (Rectangle)) (length ((the width of Self))) (width ((the length of Self))))


Situations : Situations A situation is a partition of the knowledge base Mainly to represent “snapshots” of the world at different times Facts can differ in each situation But each situation acquires all the facts of the global situation Situations can be temporally ordered Can define actions which change a situation, and thus perform simulation *Global _Situation1 _Situation2 _Situation3 supersituations subsituations supersituations subsituations supersituations subsituations import project next-situation next-situation prev-situation prev-situation project


Situations: Fluents and Non-Fluents : Situations: Fluents and Non-Fluents ;;; "Mike was born in 1977." KM> (*Mike has (birthdate (1977))) (*Mike) ;;; "birthdate is a constant ('non-fluent')" KM> (birthdate has (instance-of (Slot)) (cardinality (N-to-1)) (fluent-status (*Non-Fluent))) ;;; "age may vary, but by default will remain unchanged." KM> (age has (instance-of (Slot)) (cardinality (N-to-1)) (fluent-status (*Inertial-Fluent))) Non-fluent: Fact is universally true Inertial-fluent: Fact can propagate from one situation to the next (Non-inertial) Fluent: Fact does not propagate


Situations: Projection (example) : Situations: Projection (example) ;;; "Create a new situation." KM> (new-situation) (COMMENT: Changing to situation _Situation24) ;;; "In this situation, Mike is 27 years old." [_Situation24] KM> (*Mike has (age (27))) ;;; "What is Mike's age [in this situation]?" [_Situation24] KM> (the age of *Mike) (27) ;;; "Create and go to a new situation, the temporal successor of this one." [_Situation24] KM> (next-situation) (COMMENT: Changing to situation _Situation25) ;;; "What is Mike's age [in this situation]?" [_Situation25] KM> (the age of *Mike) (COMMENT: Projected *Mike age = (27) from _Situation24 to _Situation25) (27)


Situations: Projection (cont) : Situations: Projection (cont) [_Situation25] KM> (next-situation) (COMMENT: Changing to situation _Situation26) (_Situation26) ;;; "In this situation, Mike is 28 years old." [_Situation26] KM> (*Mike has (age (28))) (*Mike) ;;; "What is Mike's age [in this situation]?" ;;; [Note '27' is not projected, as '28' overrides it and this slot cannot ;;; have multiple values.] [_Situation26] KM> (the age of *Mike) (28) For “inertial fluents”, facts only propagate from one situation to the next if it is consistent to do so.


Querying Situations from the Global Situation : Querying Situations from the Global Situation ;;; "Exit this situation, and return to the 'global situation'." [_Situation26] KM> (global-situation) (COMMENT: Changing to situation *Global) (t) ;;; "In the last situation created, what was Mike's age?" KM> (in-situation (thelast Situation) (the age of *Mike)) (28) ;;; "In which situations was Mike 27?" KM> (allof (the all-instances of Situation) where (in-situation It ((the age of *Mike) = 27))) (_Situation25 _Situation24) Can also query one situation from another (in-situation ) KM remembers each situation (so can query over them all)


Specifying Actions : Specifying Actions ;;; "Every switching on is an Action." KM> (Switching-On has (superclasses (Action))) (Switching-On) ;;; "Every switching on changes a switch's position from down to up." KM> (every Switching-On has (object ((a Switch))) (del-list ((:triple (the object of Self) position *Down))) (add-list ((:triple (the object of Self) position *Up)))) (Switching-On) Actions define how an event changes the world They specify preconditions: facts which must be true for the action to be performable add-list, del-list: facts which become true/false as a result of the action Facts are stated as “triples” (frame-slot-value structures)


Simulation : Simulation ;;; "Create a new situation." KM> (new-situation) ;;; "There is a switch whose position [in this situation] is down." [_Situation27] KM> (a Switch with (position (*Down))) (_Switch28) ;;; "Create and enter the situation resulting from switching that switch on." [_Situation27] KM> (do-and-next (a Switching-On with (object (_Switch28)))) (_Situation30) ;;; "What is the position [in this new situation] of that switch?" [_Situation30] KM> (the position of _Switch28) (*Up) do-and-next will ‘execute’ an action in a situation creates a new situation updates the facts in it, according to the action


Simulation (cont) : Simulation (cont) ;;; --- previous situations are preserved --- ;;; "In the previous situation, what was the position of the switch?" [_Situation30] KM> (in-situation (the prev-situation of (curr-situation)) (the position of _Switch28)) (*Down) ;;; "In which situations was the switch down?" [_Situation30] KM> (allof (the all-instances of Situation) where (in-situation It ((the position of _Switch28) = *Down))) (_Situation27) again, previous situations can be queried and quantified over


Another Example of Simulation : Another Example of Simulation (Open has (superclasses (Action))) (every Open has (object ((a Door))) (pcs-list ((:triple (the object of Self) lock-state *Unlocked))) (add-list ((:triple (the object of Self) door-state *Open))) (del-list ((:triple (the object of Self) door-state *Closed))) ) (lock-state has (instance-of (Slot)) (cardinality (N-to-1))) (door-state has (instance-of (Slot)) (cardinality (N-to-1))) [_Situation1] KM> (a Door with (lock-state (*Unlocked))) (_Door2) [_Situation1] KM> (a Open with (object (_Door2))) (_Open3) [_Situation1] KM> (do-and-next _Open3) (COMMENT: Changing to Situation _Situation4) (_Situation4) [_Situation4] KM> (the door-state of _Door2) (*Open)


Another Example of Simulation : Another Example of Simulation [_Situation4] KM> (a Door) (_Door5) [_Situation4] KM> (do-and-next (a Open with (object (_Door5)))) (COMMENT: Assuming (:triple _Door5 lock-state *Unlocked), to do action _Open6...) (COMMENT: Changing to Situation _Situation7) (_Situation7) [_Situation7] KM> (in-situation _Situation4 (the lock-state of _Door5)) (*Unlocked) [_Situation7] KM> (a Door with (lock-state (*Locked))) (_Door8) [_Situation7] KM> (do-and-next (a Open with (object (_Door8)))) (do _Open9): Can't do this action as it would be inconsistent to assert precondition(s): (:triple _Door8 lock-state *Unlocked) NIL [_Situation7] KM>


Text Generation : Text Generation KM> (every Remove has (text ( (:seq "Remove" (the object of Self) "from" (the location of Self))))) ;;; "What is are the text for a remove of a sample from a box?” KM> (the text of (a Remove with (object ((a Sample))) (location ((a Box))))) ((:seq "Remove" _Sample14 "from" _Box15)) ;;; "Make a sentence from these fragments." KM> (make-sentence (the text of (a Remove with (object ((a Sample))) (location ((a Box)))))) ("Remove the sample from the box.") A special type of instance is a sequence (:seq v1 … vn) Text strings can be built up as a sequence of fragments


Slot Hierarchies : Slot Hierarchies ;;; "parts has subslots mechanical-parts." KM> (parts has (instance-of (Slot)) (subslots (mechanical-parts structural-parts))) (parts) ;;; "Every airplane has a jet engine as one of its mechanical parts ;;; and a fuselage as one of its structural parts." KM> (every Airplane has (mechanical-parts ((a Jet-Engine))) (structural-parts ((a Fuselage)))) (Airplane) ;;; "What are the parts of an airplane?" KM> (the parts of (a Airplane)) (_Jet-Engine23 _Fuselage24) Slots can have subslots Values of subslots are also values of the superslot values “propagate up”)


Prototypes Example : Prototypes Example KM> (a Airplane with (has-part ((a Wing) (a Wing)))) (_Airplane9) KM> (showme _Airplane9) (Airplane9 has (instance-of (Airplane)) (has-part ((a Wing) (a Wing)))) KM> (showme Airplane) (Airplane has (superclasses (Device)) (instances (_Airplane9))) KM> (the has-part of (a Airplane)) NIL


Prototypes Example : Prototypes Example KM> (a-prototype Airplane) (_ProtoAirplane11) [prototype-mode] KM> (_ProtoAirplane11 has (has-part ((a Wing) (a Wing)))) (_ProtoAirplane11) [prototype-mode] KM> (end-prototype) KM> (showme Airplane) (Airplane has (superclasses (Device)) (instances (_Airplane9 _Airplane10 _ProtoAirplane11)) (prototypes (_ProtoAirplane11))) KM> (the has-part of (a Airplane)) (COMMENT: Cloned _ProtoAirplane11 -> _Airplane15 to find (the has-part of _Airplane14)) (COMMENT: (_Airplane14 & _Airplane15) unified to be _Airplane14) (Wing16 _Wing17)


KM: Some Outstanding Issues : KM: Some Outstanding Issues Reasoning can get complex, and hard to debug No full truth maintenance Need for “defaults” – added during RKF Heuristic unification can sometimes get it wrong Knowledge engineer can provide guidance Use of prototypes important for KM in Shaken Explanations: store which rule derived which fact being extended to store the “proof tree” for a fact


A KM Concept Library : A KM Concept Library Insight: even domain-specific representations contain common abstractions Approach: we build a library consisting of a small hierarchy of reusable, composable, domain-independent concepts (“components”) a small vocabulary of relations to connect them then domain experts build representations by instantiating and composing these components


A Library of Components : small A Library of Components easy to learn easy to use broad semantic distinctions (easy to choose) allows detailed pre-engineering


Component Library Contents : Component Library Contents actions — things that happen, change states Enter, Copy, Replace, Transfer, etc. states — relatively temporally stable events Be-Closed, Be-Attached-To, Be-Confined, etc. entities — things that are Substance, Place, Object, etc. roles — things that are, but only in the context of things that happen Container, Catalyst, Barrier, Vehicle, etc.


Library Contents : Library Contents relations between events, entities, roles agent, donor, object, recipient, result, etc. content, part, material, possession, etc. causes, defeats, enables, prevents, etc. purpose, plays, etc. properties between events/entities and values rate, frequency, intensity, direction, etc. size, color, integrity, shape, etc.


Informal Representation : Informal Representation “A person throws a ball toward the door of a room. The ball passes through the door and into the room…”


KM + CLib Representation : KM + CLib Representation (a Activity with (agent ((a Person))) (object ((a Ball))) (first-subevent ((the Throw subevent of Self))) (subevent ( (a Throw with (object ((the Ball object of Self))) (destination ((a Door))) (next-event ((the Move-Into subevent of Self))) ) (a Move-Into with (object ((the Ball object of Self))) (base ((a Room with (has-region ( (the Door destination of (the Throw subevent of Self))))))) ) )) )


Component Library Adds… : Component Library Adds…


Component Library Adds… : Component Library Adds… The Ball and the Person must be together at t0 The Ball must be held by the Person at t0 The Ball must not be otherwise Restrained The path to the Door must not be Blocked At t1 the Ball is at the Door and no longer at the Person At t1 the Ball is outside the Room but not shut out of it The Door must not be Closed The Ball passes through the Doorway At t2 the Ball is inside the Room and no longer outside At t2 the Room has the Ball among its contents Blocked paths can be unblocked Closed Doors can be Opened …


http://www.cs.utexas.edu/users/mfkb/RKF/tree/ : http://www.cs.utexas.edu/users/mfkb/RKF/tree/


  • Account

  • RSS

  • Browse

  • Help & Info

  • Why authorSTREAM
Catch the buzz on authorSTREAM | Teach and Learn Online in a Free Virtual Classroom on WiZiQ
Copyright © 2002-2008 authorSTREAM. All rights reserved.