Question? Leave a message!




Artificial Intelligence 4. Knowledge Representation

Artificial Intelligence 4. Knowledge Representation
Artificial Intelligence 4. Knowledge Representation www.ThesisScientist.comRepresentation  AI agents deal with knowledge (data) – Facts (believe observe knowledge) – Procedures (how to knowledge) – Meaning (relate define knowledge)  Right representation is crucial – Early realisation in AI – Wrong choice can lead to project failure – Active research area www.ThesisScientist.comChoosing a Representation  For certain problem solving techniques – „Best‟ representation already known – Often a 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  Some general representation schemes – Suitable for many different (and new) AI applications www.ThesisScientist.comSome General Representations 1. Logical Representations 2. Production Rules 3. Semantic Networks • Conceptual graphs, frames 4. Description Logics (see textbook) www.ThesisScientist.comWhat is a Logic  A language with concrete rules – No ambiguity in representation (may be other errors) – Allows unambiguous communication and processing – Very unlike natural languages e.g. English  Many ways to translate between languages – A statement can be represented in different logics – And perhaps differently in same logic  Expressiveness of a logic – How much can we say in this language  Not to be confused with logical reasoning – Logics are languages, reasoning is a process (may use logic) www.ThesisScientist.comSyntax and Semantics  Syntax – Rules for constructing legal sentences in the logic – Which symbols we can use (English: letters, punctuation) – How we are allowed to combine symbols  Semantics – How we interpret (read) sentences in the logic – Assigns a meaning to each sentence  Example: “All lecturers are seven foot tall” – A valid sentence (syntax) – And we can understand the meaning (semantics) – This sentence happens to be false (there is a counterexample) www.ThesisScientist.comPropositional Logic  Syntax – Propositions, e.g. “it is wet” – Connectives: and, or, not, implies, iff (equivalent) – Brackets, T (true) and F (false)  Semantics (Classical AKA Boolean) – Define how connectives affect truth  “P and Q” is true if and only if P is true and Q is true – Use truth tables to work out the truth of statements www.ThesisScientist.comPredicate Logic  Propositional logic combines atoms – An atom contains no propositional connectives – Have no structure (todayiswet, johnlikesapples)  Predicates allow us to talk about objects – Properties: iswet(today) – Relations: likes(john, apples) – True or false  In predicate logic each atom is a predicate – e.g. first order logic, higherorder logic www.ThesisScientist.comFirst Order Logic  More expressive logic than propositional – Used in this course (Lecture 6 on representation in FOL)  Constants are objects: john, apples  Predicates are properties and relations: – likes(john, apples)  Functions transform objects: – likes(john, fruitof(appletree))  Variables represent any object: likes(X, apples)  Quantifiers qualify values of variables – True for all objects (Universal): X. likes(X, apples) – Exists at least one object (Existential): X. likes(X, apples) www.ThesisScientist.comExample: FOL Sentence  “Every rose has a thorn”  For all X – if (X is a rose) – then there exists Y  (X has Y) and (Y is a thorn) www.ThesisScientist.comExample: FOL Sentence  “On Mondays and Wednesdays I go to John‟s house for dinner”  Note the change from “and” to “or” – Translating is problematic www.ThesisScientist.comHigher Order Logic  More expressive than first order  Functions and predicates are also objects – Described by predicates: binary(addition) – Transformed by functions: differentiate(square) – Can quantify over both  E.g. define red functions as having zero at 17  Much harder to reason with www.ThesisScientist.comBeyond True and False  Multivalued logics – More than two truth values – e.g., true, false unknown – Fuzzy logic uses probabilities, truth value in 0,1  Modal logics – Modal operators define mode for propositions – Epistemic logics (belief)  e.g. p (necessarily p), p (possibly p), … – Temporal logics (time)  e.g. p (always p), p (eventually p), … www.ThesisScientist.comLogic is a Good Representation  Fairly easy to do the translation when possible  Branches of mathematics devoted to it  It enables us to do logical reasoning – Tools and techniques come for free  Basis for programming languages – Prolog uses logic programs (a subset of FOL) –Prolog based on HOL www.ThesisScientist.comNonLogical Representations  Production rules  Semantic networks – Conceptual graphs – Frames  Logic representations have restricitions and can be hard to work with – Many AI researchers searched for better representations www.ThesisScientist.comProduction Rules  Rule set of condition,action pairs – “if condition then action”  Matchresolveact cycle – Match: Agent checks if each rule‟s condition holds – Resolve:  Multiple production rules may fire at once (conflict set)  Agent must choose rule from set (conflict resolution) – Act: If so, rule “fires” and the action is carried out  Working memory: – rule can write knowledge to working memory – knowledge may match and fire other rules www.ThesisScientist.comProduction Rules Example  IF (at bus stop AND bus arrives) THEN action(get on the bus)  IF (on bus AND not paid AND have oyster card) THEN action(pay with oyster) AND add(paid)  IF (on bus AND paid AND empty seat) THEN sit down  conditions and actions must be clearly defined – can easily be expressed in first order logic www.ThesisScientist.comGraphical Representation  Humans draw diagrams all the time, e.g. – Causal relationships – And relationships between ideas www.ThesisScientist.comGraphical Representation  Graphs easy to store in a computer  To be of any use must impose a formalism – Jason is 15, Bryan is 40, Arthur is 70, Jim is 74 – How old is Julia www.ThesisScientist.comSemantic Networks  Because the syntax is the same – We can guess that Julia‟s age is similar to Bryan‟s  Formalism imposes restricted syntax www.ThesisScientist.comSemantic Networks  Graphical representation (a graph) – Links indicate subset, member, relation, ...  Equivalent to logical statements (usually FOL) – Easier to understand than FOL – Specialised SN reasoning algorithms can be faster  Example: natural language understanding – Sentences with same meaning have same graphs – e.g. Conceptual Dependency Theory (Schank) www.ThesisScientist.comConceptual Graphs  Semantic network where each graph represents a single proposition  Concept nodes can be – Concrete (visualisable) such as restaurant, my dog Spot – Abstract (not easily visualisable) such as anger  Edges do not have labels – Instead, conceptual relation nodes – Easy to represent relations between multiple objects www.ThesisScientist.comFrame Representations  Semantic networks where nodes have structure – Frame with a number of slots (age, height, ...) – Each slot stores specific item of information  When agent faces a new situation – Slots can be filled in (value may be another frame) – Filling in may trigger actions – May trigger retrieval of other frames  Inheritance of properties between frames – Very similar to objects in OOP www.ThesisScientist.comExample: Frame Representation www.ThesisScientist.comFlexibility in Frames  Slots in a frame can contain – Information 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  Can also be expressed in first order logic www.ThesisScientist.comRepresentation Logic  AI wanted “nonlogical representations” – Production rules – Semantic networks  Conceptual graphs, frames  But all can be expressed in first order logic  Best of both worlds – Logical reading ensures representation welldefined – Representations specialised for applications – Can make reasoning easier, more intuitive www.ThesisScientist.com
Website URL
Comment