1 Artificial Intelligence 4. Knowledge RepresentationCourse V231 Department of Computing Imperial College © Simon Colton
2 Representation Representation RepresentationThink about knowledge, rather than data in AI Facts, procedures, meaning Cannot have intelligence without knowledge Always been very important in AI Choosing the wrong representation Could lead to a project failing Still a lot of work done on representation issues
3 Representations for Problem solving techniquesFor certain problem solving techniques The “best” representation has already been worked out Often it is an obvious requirement of the technique Or a requirement of the programming language (e.g., Prolog) Examples: First order theorem proving (first order logic) Inductive logic programming (logic programs) Neural networks learning (neural networks) But what if you have a new project? What kind of general representations schemes are there?
4 Four General Representation TypesLogical Representations Semantic Networks Production Rules Frames
5 4.1 Logical Representations What is a logic?Lay down some concrete communication rules In order to give information to agents, and get info Without errors in communication (or at least, fewer) Think of a logic as a language Many ways to translate from one language to another Expressiveness How much of natural language (e.g., English) We are able to translate into the logical language Not to be confused with logical reasoning “Sherlock Holmes used pure logic to solve that…” This is a process, not a language
6 Syntax and Semantics of LogicsHow we can construct legal sentences in the logic Which symbols we can use (English: letters, punctuation) How we are allowed to write down those symbols Semantics How we interpret (read) sentences in the logic i.e., what the meaning of a sentence is Example: “All lecturers are six foot tall” Perfectly valid sentence (syntax) And we can understand the meaning (semantics) This sentence happens to be false (there is a counterexample)
7 Propositional Logic Syntax SemanticsPropositions such as P meaning “it is wet” Connectives: and, or, not, implies, equivalent Brackets, T (true) and F (false) Semantics How to work out the truth of a sentence Need to know how connectives affect truth E.g., P and Q is true if and only if P is true and Q is true P implies Q is true if P and Q are true or if P is false Can draw up truth tables to work out the truth of statements
8 First Order Predicate LogicMore expressive logic than propositional And one we will use a lot in this course Later lecture all about first order predicate logic Syntax allows Constants, variables, predicates, functions and quantifiers So, we say something is true for all objects (universal) Or something is true for at least one object (existential) Semantics Working out the truth of statement This can be done using rules of deduction
9 Example Sentence In English: In first order predicate logic:“Every Monday and Wednesday I go to John’s house for dinner” In first order predicate logic: X ((day_of_week(X, monday) day_of_week(X, weds)) eat(me, dinner))). (go_to(me, house_of(john) Note the change from “and” to “or” Translating is problematic
10 Higher Order Predicate LogicMore expressive than first order predicate logic Allows quantification over functions and predicates, as well as objects For example We can say that all our polynomials have a zero at 17: f (f(17)=0). Working at the meta-level Important to AI, but not often used
11 Other Logics Fuzzy logic Multi-valued logics Modal logicsUse probabilities, rather than truth values Multi-valued logics Assertions other than true and false allowed E.g., “unknown” Modal logics Include beliefs about the world Temporal logics Incorporate considerations of time
12 Why Logic is a Good RepresentationSome of many reasons are: It’s fairly easy to do the translation when possible There are whole tracts of mathematics devoted to it It enables us to do logical reasoning Programming languages have grown out of logics Prolog uses logic programs (a subset of predicate logic)
13 Semantic Networks Logic is not the only fruitHumans draw diagrams all the time, e.g., E.g. causal relationships: And relationships between ideas:
14 Graphical RepresentationsGraphs are very easy to store inside a computer For information to be of any use We must impose a formalism on the graphs Jason is 15, Bryan is 40, Arthur is 70, Jim is 74 How old is Julia?
15 Better Graphical RepresentationBecause the formalism is the same We can guess that Julia’s age is similar to Bryan’s
16 Semantic Network FormalismsUsed a lot for natural language understanding Represent two sentences by graphs Sentences with same meaning have exactly same graphs Conceptual Dependency Theory Roger Schank’s brainchild Concepts are nodes, relationships are edges Narrow down labels for edges to a very few possibilities Problem: Not clear whether reduction to graphs can be automated for all sentences in a natural language
17 Conceptual Graphs John Sowa Each graph represents a single propositionConcept nodes can be: Concrete (visualisable) such as restaurant, my dog spot Abstract (not easily visualisable) such as anger Edges do not have labels Instead, we introduce conceptual relation nodes Many other considerations in the formalism See Russell and Norvig for details
18 Example Conceptual GraphAdvantage: Single relationship between multiple concepts is easily representable
19 Production Rule RepresentationsConsists of
20 Example Production RuleAs reported in Doug Lenat’s PhD thesis 102. After creating a new generalization G of Concept C Consider looking for non-examples of G This was paraphrased In general, we have to be more concrete About exactly when to fire and what to do
21 Frame RepresentationsInformation retrieval in face of new situation The information is store in frames with slots Some of the slots trigger actions, causing new situations Frames are templates Which are to be filled-in in a situation Filling them in causes an agent to Undertake actions and retrieve other frames Frames are extensions of record datatype in databases Also very similar to objects in OOP
22 Flexibility in Frames Slots in a frame can containInformation for choosing a frame in a situation Relationships between this and other frames Procedures to carry out after various slots filled Default information to use where input is missing Blank slots - left blank unless required for a task Other frames, which gives a hierarchy
23 Example Frame