CS 561, Session 191Logical reasoning systems• Theorem provers and logic programming languages• Production systems• Frame systems and semantic networks• Description logic systemsCS 561, Session 192Logical reasoning systems• Theorem provers and logic programming languages – Provers: use resolution to prove sentences in full FOL. Languages: use backwardchaining on restricted set of FOL constructs.• Production systems – based on implications, with consequentsinterpreted as action (e.g., insertion & deletion in KB). Based onforward chaining + conflict resolution if several possible actions.• Frame systems and semantic networks – objects as nodes in agraph, nodes organized as taxonomy, links represent binaryrelations.• Description logic systems – evolved from semantic nets. Reasonwith object classes & relations among them.CS 561, Session 193Basic tasks• Add a new fact to KB – TELL• Given KB and new fact, derive facts implied by conjunction of KBand new fact. In forward chaining: part of TELL• Decide if query entailed by KB – ASK• Decide if query explicitly stored in KB – restricted ASK• Remove sentence from KB: distinguish between correcting false sentence, forgetting useless sentence, or updating KB re. change in the world.CS 561, Session 194Indexing, retrieval & unification• Implementing sentences & terms: define syntax and map sentences onto machine representation.Compound: has operator & arguments.e.g., c = P(x) ∧ Q(x) Op[c] = ∧; Args[c] = [P(x), Q(x)]• FETCH: find sentences in KB that have same structure as query.ASK makes multiple calls to FETCH.• STORE: add each conjunct of sentence to KB. Used by TELL.e.g., implement KB as list of conjunctsTELL(KB, A ∧¬B)TELL(KB, ¬C ∧ D)then KB contains: [A, ¬B, ¬C, D]CS 561, Session 195Complexity• With previous approach, FETCH takes O(n) time on n-element KBSTORE takes O(n) time on n-element KB (if check for duplicates)Faster solution?CS 561, Session 196Table-based indexing• What are you indexing on? Predicates (relations/functions).Example:xxxxxxxx-dog(alice)dog(rover)dog(fido)dogxxxxxxxx-Mother(ann,al)Mother(ann,sam)Mother(grace,joe)MotherPremiseConclu-sionNegativePositiveKeyCS 561, Session 197Table-based indexing•Use hash table to avoid looping over entire KB for each TELL or FETCHe.g., if only allowed literals are single letters, use a 26-element array to store their values.• More generally: - convert to Horn form- index table by predicate symbol- for each symbol, store:list of positive literalslist of negative literalslist of sentences in which predicate is in conclusionlist of sentences in which predicate is in premiseCS 561, Session 198Tree-based indexing• Hash table impractical if many clauses for a given predicate symbol• Tree-based indexing (or more generally combined indexing):compute indexing key from predicate and argument symbolsPredicate?First arg?CS 561, Session 199Tree-based indexingExample:Person(age,height,weight,income)Person(30,72,210,45000)Fetch( Person(age,72,210,income))Fetch(Person(age,height>72,weight<210,income))CS 561, Session 1910Unification algorithm: ExampleUnderstands(mary,x) implies Loves(mary,x)Understands(mary,pete) allows the system to substitute petefor x and make the implication that IFUnderstands(mary,pete) THEN Loves(mary,pete)CS 561, Session 1911Unification algorithm• Using clever indexing, can reduce number of calls to unification• Still, unification called very often (at basis of modus ponens) => need efficient implementation.• See AIMA p. 303 for example of algorithm with O(n^2) complexity(n being size of expressions being unified).CS 561, Session 1912Logic programmingRemember: knowledge engineering vs. programming…CS 561, Session 1913Logic programming systemse.g., Prolog:• Program = sequence of sentences (implicitly conjoined)• All variables implicitly universally quantified• Variables in different sentences considered distinct• Horn clause sentences only (= atomic sentences or sentences withno negated antecedent and atomic consequent)• Terms = constant symbols, variables or functional terms• Queries = conjunctions, disjunctions, variables, functional terms• Instead of negated antecedents, use negation as failure operator: goal NOT P considered proved if system fails to prove P• Syntactically distinct objects refer to distinct objects• Many built-in predicates (arithmetic, I/O, etc)CS 561, Session 1914Prolog systemsCS 561, Session 1915Basic syntax of facts, rules and queries <fact> ::= <term> .<rule> ::= <term> :- <term> .<query> ::= <term> .<term> ::= <number> | <atom> | <variable> | <atom> (<terms>)<terms> ::= <term> | <term>, <terms>CS 561, Session 1916A PROLOG ProgramA PROLOG Program• A PROLOG program is a set of factsand rules.• A simple program with just facts :parent(alice, jim).parent(jim, tim).parent(jim, dave).parent(jim, sharon).parent(tim, james).parent(tim, thomas).CS 561, Session 1917A PROLOG ProgramA PROLOG Program• c.f. a table in a relational database.• Each line is a fact(a.k.a. a tuple or a row).• Each line states that some person X is a parent of some (other) person Y.• In GNU PROLOG the program is kept in an ASCII file.CS 561, Session 1918A PROLOG QueryA PROLOG Query• Now we can ask PROLOG questions :| ?- parent(alice, jim).yes| ?- parent(jim, herbert).no| ?-CS 561, Session 1919A PROLOG QueryA PROLOG Query• Not very exciting. But what about this :| ?- parent(alice, Who).Who = jimyes| ?-•Whois called a logical variable.• PROLOG will set a logical variable to any value which makes the query succeed.CS 561, Session 1920A PROLOG Query IIA PROLOG Query II• Sometimes there is more than one correct answer to a query. • PROLOG gives the answers one at a time. To get the next answer type ;.| ?- parent(jim, Who).Who = tim ? ;Who = dave ? ;Who = sharon ? ;yes| ?-NB : The ;do not actually appear on the screen.NB : The ;do not actually appear on the screen.CS 561, Session 1921A PROLOG Query IIA PROLOG Query II| ?- parent(jim, Who).Who = tim ? ;Who = dave ? ;Who = sharon ? ;yes| ?-•After finding that jim was a parent of sharonGNU PROLOG detects that there are no more alternatives for parent and ends the search.NB : The ;do not actually appear on the screen.NB : The ;do not actually appear on the screen.CS 561, Session 1922Prolog exampleconjunctionCS 561, Session 1923Append• append([], L, L)• append([H| L1], L2, [H| L3]) :-
View Full Document
Unlocking...