Artificial Intelligence 4. Knowledge Representation

Artificial Intelligence 4. Knowledge Representation

Artificial Intelligence 6. Representing Knowledge in Predicate Logic Course V231 Department of Computing Imperial College, London Jeremy Gow The Case of the Silk Gloves It was elementary my dear Watson. The killer always left a silk glove at the scene of the murder. That was his calling card. Our investigations showed that only three people have purchased such gloves in the past year. Of these, Professor Doolally and Reverend Fisheye have iron-clad alibis, so the murderer must have been Sergeant Heavyset. When he tried to murder us with that umbrella, we knew we had our man.

Not So Elementary The killer always left a silk glove at the scene of the murder. (This is inductive reasoning - guessing at a hypothesis) That was his calling card. (This is abductive reasoning - choosing an explanation) only three people have purchased such gloves in the past year. (This is model generation - constructing examples) Professor Doolally and Reverend Fisheye have iron-clad alibis. (This is constraint-based reasoning - ruling out possibilities) so the murderer must have been Sergeant Heavyset. (This is deductive reasoning - inferring new information from known facts) Bring on the Lawyers The murderer always confesses in some way So, Holmes never has to defend his reasoning

This is a good job, as its mostly unsound A good lawyer might point out that all the victims were coincidentally - members of the silk glove appreciation society. Wheres your case now, Mr. Holmes? Automated Reasoning Very important area of AI research Reasoning usually means deductive reasoning New facts are deduced logically from old ones Inductive Guessing facts from old ones and from evidence Two

reasoning (later in course) main aspects of deductive reasoning Logical representations (thousands of them) Rules of deduction (how to deduce new things) Lecture 6 and Lecture 7 Applications of Automated Reasoning Automated Automated mathematics Axioms(A) are given, theorem statement(T) is given Reasoning agent searches from A to T (or from T to A) Using

rules of deduction to move around the search space Automated verification Hardware and Software verification That theorem proving they perform as specified Remember the Intel chip fiasco? Intel now have lots of people working on automated verification First Order Predicate Logic Very

important way of representing knowledge Le c Prolog Deduction Expert Systems Theorem Proving 7 tu re re

6 ctu Le FOPL Syntax and Semantics Keep thinking of predicate logic as a language We need to communicate (share knowledge) with AI agent Using logic as the knowledge representation scheme Need to both inform and understand Syntax

Symbols used and how sentences are put together Predicates, connectives, constants, functions, variables, quantifiers Semantics How we interpret sentences How we translate between the two languages How we tell the truth of a sentence Predicates Predicates are statements that

Example: father(bob,bill) Father is the predicate name Certain things are related in specific ways Predicate name identifies the relationship Arguments are the things being related Arity is the number of things being related Relationship is (nearly) obvious: bob is bills father Bob and bill are the arguments (arity here is 2) Predicates can relate

Constants, functions and variables Connectives: And, Or And If predicates p1 and p2 are true then (p1 (iii) , p2) is true Or represented by: (i) & (ii) (iii) , (iii) , represented by: (i) (ii) | (iii) ; (ii) | (iii) ; If either predicate p1 or predicate p2 is true (or both) Then Also (p1 (ii) | (iii) ; p2) is true

note the use of brackets Indicate where to stop and work out truth values Connectives: Not, Implies, Equivalence Not represented by: (i) (ii) (ii) (iii) \+ Changes predicate truth (true to false, or false to true) Implies is represented by: or If one statement is true, then another is also true

equivalent to represented by: Youll also hear: if and only if & necessary and sufficient condition Examples of Connectives in Use Simon lectures AI and bioinformatics lectures_ai(simon) lectures_bioinformatics(simon) lectures_bioinformatics(simon) Better: lectures(simon,ai) lectures_bioinformatics(simon) lectures(simon,bioinfo) If Simon isnt lecturing AI, Bob must be lectures(simon,ai) lectures(bob,ai) George and Tony will win or Saddam will lose

(will_win(george) lectures_bioinformatics(simon) will_win(tony)) will_win(saddam) Constants Stand Such as england or barbara_woodhouse Also for actual things use constants for specific words like blue But blue has different shades In this case you should have: Made blue a predicate name, then you could have had: shade_of_blue(aqua_marine), shade_of_blue(navy), etc.

Choosing predicates and constants is important Convention: use lower case letters for constants Functions Special predicates Where we think of them having inputs and an output If arity n, then the first n-1 arguments are inputs And the final argument is thought of the output Important

Only a function if a set of inputs has a unique output Use the equals sign to make I/O clear And to make it clear this is a function Example of a Function The cost of an omelette at the Red Lion is 5 Normally: cost_of(omelette,red_lion,five_pounds) But

Input: the name of a meal and the name of a pub Output: the cost of the meal So, cost_of is a function we can write this as: cost_of(omelette,red_lion) = five_pounds Using Functions for Abbreviation We want to minimise misunderstanding If we want to, we can abbreviate:

So, if we can, we should make sentences succinct If we are talking about the output of a function We can replace it with the predicate part i.e., replace the RHS of equality with the LHS Example: Omelettes at the Red Lion cost less than pancakes at House of Pancakes less_than(cost_of(omelette,red_lion),cost_of(pancake,pancake_house)) Variables Want to be more expressive now

Theres a meal at the Red Lion which costs 3 cost_of(meal,red_lion) But meal is a constant, like omelette or pancake Doesnt express what we wanted it to Were really talking about some general meal Not a meal in particular Call this meal X (a variable) cost_of(X,red_lion) =3

Not quite right yet =3 Variables Continued Need to further express our beliefs about X We say that: There is such a meal X There exists such a meal X We need a symbol for there exists This is represented as:

X (cost_of(X,red_lion) = 3) Still not quite right (see later) Quantifiers The exists sign is known as a quantifier A sentence is known as existentially quantified Using quantifiers is known as quantification One other quantifier: ( (forall sign) Example: all students enjoy AI lectures ( X (student(X) enjoys(X,ai_lectures)) This is universally quantified

Forall says that each predicate involving the quantified variable is true for every possible choice of that variable Terminology: Constants are ground variable, and we instantiate a variable All meals cost 3 becomes Spaghetti costs 3 Be careful with quantifiers!! There is a meal at the Red Lion which costs three pounds X (meal(X) lectures_bioinformatics(simon) cost_of(red_lion, X) = 3) What about: All the meals at the Red Lion cost three pounds Replace exists by forall: X (meal(X) lectures_bioinformatics(simon) cost_of(red_lion, X) = 3) X (meal(X) cost_of(red_lion, X) = 3)

X (meal(X) & serves(red_lion, X) cost_of(red_lion, X) =3) More Translation Pitfalls to Avoid (iii) , and (ii) | (iii) ; mixed up Example from lecture 4 Getting Every Monday and Wednesday I go to Johns house for dinner X (day(X,mon) day(X,weds) go(me,house(john)) lectures_bioinformatics(simon) eat(me,dinner)) Even More Pitfalls Getting confused with quantifiers Translate: All things in the bag are red Which of these translations is correct? 1. X (in_bag(X) red(X)) 2. X (red(X) in_bag(X)) 3. X ( Y (bag(X) lectures_bioinformatics(simon) in_bag(Y,X) red(Y))) Translating Logic to English

Take explicit sentence, make it more succinct Example: X (meal(X) lectures_bioinformatics(simon) cost_of(red_lion, X) = 3) 1. There is something called X, where X is a meal and X costs three pounds at the Red Lion 2. There is a meal, X, which costs three pounds at the Red Lion 3. There is a meal which costs 3 at the Red Lion The Prolog Programming Language Declarative Ask a friend to buy you some groceries For rather than procedural

declarative languages (Kowalski) Algorithm = Logic + Control That is, two most important aspects are: The underlying logical representation chosen The search techniques underpinning the language We look at the logic and search in Prolog From FOPL to Logic Programs Restrict representation to only implications Restrict implications to have the format ( Xi (P1 (iii) , P2 (iii) , (iii) , Pn H) These are called Horn clauses P1 (iii) , P2 (iii) , (iii) , Pn is called the body

H is called the head A collection of Horn clauses is called A Logic Program From Logic Programs to Prolog 1. Drop the universal quantification This is assumed in Prolog 2. Write the other way around So that P1 (iii) , P2 (iii) , (iii) , Pn H Becomes: H P1 (iii) , P2 (iii) , (iii) , Pn 3. Write as : Gives us: H :- P1 (iii) , P2 (iii) , (iii) , Pn

4. Write (iii) , as commas and put a full stop on the end: Gives us: H :- P1 , P2 , , Pn. Its now in Prolog format Example Translation In every lecture, if the lecturer is good, or the subject matter interesting, then the students are bright and attentive X (has_good_lecturer(X) subject_is_interesting_in(X)) students_bright_in(X) lectures_bioinformatics(simon) students_attentive_in(X)) Written as a Prolog Logic Program: students_bright_in(X) :students_bright_in(X) :students_attentive_in(X) students_attentive_in(X)

has_good_lecturer(X) subject_is_interesting(X) :- has_good_lecturer(X) :- subject_is_interesting(X) Search in Prolog Prolog programs consist of A database of many Horn clauses Given a query: ?- query_predicate(X). Prolog

searches the database From top to bottom To match the head and arity of the query predicate To a Horn clause already in the database Search in Prolog Continued Once it has found a match for the head It checks to see whether it can also match The variables in the body Does this using unification (see later lecture) Variables can be instantiated to constants Variables can be matched

If it gets a match, we say it has proved the query Prolog has a closed world assumption If it cannot prove a query, then the query is false Search Example president(X) :- first_name(X, georgedubya), second_name(X, bush). prime_minister(X) :- first_name(X, maggie), second_name(X, thatcher). prime_minister(X) :- first_name(X, tony), second_name(X, blair). first_name(tonyblair, tony). first_name(georgebush, georgedubya). second_name(tonyblair, blair). second_name(georgebush, bush). ?- prime_minister(P). P = tonyblair ?- \+ president(tonyblair) Yes Prolog Details Check

out the notes (and Russell & Norvig) How arithmetic is carried out How performance is measured Logical inferences per second (LIPS) How performance is greatly improved By compiling the code Either to something like C Or an intermediate language like the WAM LIPS are now in millions OR-Parallelism of Prolog

When trying to find a match to query ?- prime_minister(X) One processor takes this clause prime_minister(X) :- first_name(X, tony), second_name(X, blair). And another processor takes this: prime_minister(X) :- first_name(X, maggie), second_name(X, thatcher). AND-Parallelism of Prolog When trying to find a match to query

?- prime_minister(X) And looking in the database at: prime_minister(X) :- first_name(X, tony), second_name(X, blair). One processor tries to match this: first_name(X, tony) And another processor tries to match this: second_name(X, thatcher)

More tricky than OR-parallelism (variables have to match) Expert Systems Speak to experts in the field Determine a set of important rules for the task they do Encode them in a knowledge base, e.g., a Prolog program Use the program to try to do the experts task Major success in AI In particular medical/agricultural diagnosis systems "A leading expert on lymph-node pathology describes a fiendishly difficult case to the expert

system, and examines the system's diagnosis. He scoffs at the system's response. Only slightly worried, the creators of the system suggest he ask the computer for an explanation of the diagnosis. The machine points out the major factors influencing its decision and explains the subtle interaction of several of the symptoms in this case. The experts admits his error, eventually. From Russell and Norvig Example of a Prolog Expert System Card game from last lecture Overkill to use minimax to solve it As we can express what each player should do Using rules about which card to choose in which situation

Examples If there are three or four even numbered cards Then (rules for player one, first move) player one should choose the biggest even number If there are three or four odd numbered cards Then See player one should choose the biggest odd number notes for Prolog implementation of this

Recently Viewed Presentations

  • OptiSystem

    OptiSystem

    To model quantum-limited performance the . Shot Noise Distribution . has been set to the . Poisson. statistical noise model. The BER Test Set is the best tool to model quantum-limited performance as we need to count (over a very...
  • Dynamic Messaging with Microsoft BizTalk Enterprise Service ...

    Dynamic Messaging with Microsoft BizTalk Enterprise Service ...

    BizTalk is all about providing solutions based on configuration. Configuration happens at dev time or post-deployment. ESB Toolkit is all about runtime resolution, it interacts with external stores (e.g., service registry) to get operational configuration in a JIT manner.
  • Knee deformity :-Bow legs(Genu varum)and Knock knees(Genu ...

    Knee deformity :-Bow legs(Genu varum)and Knock knees(Genu ...

    Clinical features. Age :Patients are usually over 50 years old; they tend to be overweight and may have longstanding bow-leg deformity.. Pain is the leading symptom, worse after use, or on stairs. After rest, the joint feels stiff and it...
  • Elementary and Middle School Mathematics Teaching ...

    Elementary and Middle School Mathematics Teaching ...

    Learner Outcomes. 22.1 Describe strategies to meaningfully engage students in understanding exponents, order of operations, scientific notation, and very large and very small numbers.. 22.2 . Compare quantity and number line visuals for teaching integers, and contrast the different contexts...
  • Quality Improvement Methodologies - Henry Ford Health System

    Quality Improvement Methodologies - Henry Ford Health System

    Throughput Time to see a doctor Time from admission to bed … Process Improvement Techniques Total Quality Management Process Re-Engineering Constraint management Six Sigma Lean Systems Lean Manufacturing Attributed to Taichii Ohno of Toyota, but actually, the ideas are rooted...
  • Type title here - University of Bristol

    Type title here - University of Bristol

    Data linkage may be necessary to more completely identify cohorts for mortality studies. Data linkage introduces additional health information privacy concerns. It is important to be aware of privacy legislation. Steps from data request to data access can take several...
  • What is Dancing Dance is an expression of

    What is Dancing Dance is an expression of

    Dance Education This refers to an educational process whereby the central process is the learning and studying the dance as the medium to understand one's self society and culture. Classical Dance Dance with standardized rules and restriction. It can be...
  • Mr. E's Class

    Mr. E's Class

    Past S.S. LEAP Questions From Louisiana each of these items is in what direction? N/S/E/W/NE/NW/SE/SW Texas Minnesota Florida Utah California 3/3/09 Fact # 1 Vocabulary: Acadian - A group of people forced from their original homeland in Acadia (Nova Scotia)...