Knowledge Representation I PDF

Knowledge Representation Dr. Imtiaz Hussain Khan [email protected]  Knowledge Representation Fundamental concepts about knowledge Needs for Knowledge Representation Characteristics of Knowledge Representation Overview of propositiona...

Knowledge Representation Dr. Imtiaz Hussain Khan [email protected]  Knowledge Representation Fundamental concepts about knowledge Needs for Knowledge Representation Characteristics of Knowledge Representation Overview of propositional logic Overview of predicate logic  We would like to build a system that: we could TELL a set of facts  This system we call a Knowledge Base (KB) Ali is a Muslim. All Muslims believe in one God. we could ASK questions, and receive correct answers  Is Ali a Muslim?  Is Williams a Muslim? can automatically ADD more facts in it  Ali believes in one God.  AI can (also) be viewed as study of intelligent behavior achieved through computational means  Knowledge representation and reasoning is the study of how to reason (compute) with knowledge in order to decide what to do  But, before reasoning with knowledge, first we need to represent (encode) it  Knowledge generally emerges as follows: data  information  knowledge  Data: Collection of (disconnected) facts  Temperature drops to 10C.  It starts raining.  Information emerges when relationships among facts are established  Temperature dropped to 10C AND then it started raining.  Knowledge emerges when relationships among patterns are identified and understood  Rain pattern: If the humidity is very high and temperature drops substantially then atmosphere is unlikely to hold moisture, so it rains.  We understand through knowledge different kinds of facts about something (the world)  Knowledge is necessary for intelligent behavior  If I get tired, I’d like to take rest. [If I get tired, I’d like to work hard!!!]  A knowledge representation is encoding of knowledge (in some appropriate way)  KR is substitute for the thing itself  A priori knowledge  Comes before knowledge perceived through senses  Considered to be universally true (All bachelors are unmarried)  A posteriori knowledge  Knowledge verifiable through senses  May not always be reliable (Some bachelors are very happy)  Procedural knowledge  Knowing HOW to do something: to determine if A is taller than B, first determine heights of A & B  Declarative knowledge  Knowing that something is true/false  Mine sweeper world  You have to find a way from a start field to an exit field on a board where mines are hidden. An electronic device tells you how many mines are hidden on the neighbouring fields (vertically, horizontally, and diagonally) However, the device is unable to give the exact location of the mines that it has detected. How do you proceed?  Once we have walked on the board for a while, how can we express the knowledge that we have acquired?  The initial cell, for instance, has no bomb  We could express this type of knowledge with binary (0/1) variables that tell us, for each cell, whether there is a bomb or not: B13 = 0  When we see that our device can detect no mines in the proximity of the start field, we can express that knowledge as: B12+B14+B22+B23+B24 = 0  What we need to know, to safely reach the goal state?  Facts, e.g. There is no mine in the vicinity of a cell; B13 = 0  Rules, e.g. If there is a mine in a cell, do not go to that cell  How to draw inference?  Knowledge base, reasoning and language  To draw (rational) inference, we first need to be able to state the rules and the known facts about a problem  The internal representation of facts and rules is called a knowledge base (KB)  The KB is the starting point for all reasoning that we may want to perform  Therefore, we need a kind of language that allows us to express what we know  Assumption of (traditional) AI work is that:  Knowledge may be represented as “symbol structures”  complex data structures, representing bits of knowledge (objects, concepts, facts, rules, strategies..)  For example, “red” could represent colour red “car1” could represent my car red(car1) could represent fact that my car is red  Intelligent behavior can be achieved through manipulation of symbol structures  But,in which language these symbol structures be expressed?  Possibility 1: Natural languages  Very expressive, but notoriously ambiguous  Inference would be very difficult  So, not a good choice  Possibility 2: Programming languages  Very precise, but lack expressiveness  Not all kind of required knowledge can be represented  So, again, not a good choice  Possibility 3: Formalisms, e.g. logic, which balance the above trade-offs  Ideally, a KR language should have  Representational Adequacy/expressiveness  Clear syntax/semantics  Inferential adequacy  Inferential efficiency  Naturalness  Consistency In practice no one language is perfect, and different languages are suitable for different problems  Consider the following facts:  Sun is shining  Most people believe in Allah  Ahmed will finish his job before Asar prayer  How do we represent all kind of facts  These can be represented as natural language strings  But hard then to manipulate and draw conclusions  Hard to understood by machines  Some notations/languages only allow you to represent certain things  Time, beliefs, uncertainty, all hard to represent  Knowledge representation languages should have precise syntax and semantics  You must know exactly what an expression means in terms of objects in the real world Real World Real World Map to KR language Map back to real world Representation New Inference conclusions of facts in World Computer Computer  Suppose we have decided that “red1” refers to a dark red color, “car1” is my car, car2 is another..  Syntax of a language will tell you which of the following is legal: red1(car1), red1 car1, car1(red1), red1(car1 & car2)?  Semantics of a language tells you exactly what an expression means - e.g., Pred(Arg) means that the property referred to by Pred applies to the object referred to by Arg  E.g., property “dark red” applies to my car  It would be helpful if our representation scheme is quite intuitive and natural for human readers  Could represent the fact that my car is red using the notation:  abc  xyz  where abc refers to my car, xyz refers to redness and  used in some way to associate properties to objects  But this wouldn’t be very helpful  Representing knowledge would not be very interesting unless you can use it to make inferences:  Draw new conclusions from existing facts  If its raining, Hassan never goes out  It’s raining today  so..  Inferential adequacy refers to how easy it is to draw inferences using represented knowledge  Representing everything as natural language strings has good representational adequacy and naturalness, but very poor inferential adequacy  You may be able, in principle, to make complex deductions given knowledge represented in a sophisticated language  But it may be just too inefficient  Generally the more complex the possible deductions, the less efficient will be the reasoner  Representation and inference system should be sufficient for the task, without being hopelessly inefficient  A consistent KR system would help avoid redundant information  Hassan is clever  Hassan is smart  A consistent KR system would also help avoid conflicting information  Hassan is clever  Hassan is dull-minded  A Logic is a formal language, which  has precise syntax and semantics  Syntax: what expressions are allowed in the language  Semantics: what they mean in terms of mapping to real world  supports sound inference  How can we draw new conclusions from existing statements (proof theory)  Independent of domain of application  Different logics exist  propositional logic  predicate logic  temporal logic  fuzzy logic (etc.)  Proposition is a statement which has a truth value (True or False)  Teaching is a noble profession  Propositional logic  A simple language useful to express key ideas and definitions  User defines a set of propositional symbols, like p and q  User also defines the semantics of each propositional symbol: o p means “It is hot” o q means “It is humid”  Pick the smallest/atomic statements without and, or, etc. about which you could answer the question is it true or false?  Use propositional variables to stand for these statements, and connect them with the relevant logical connectives p: It is hot q: It is humid r: It is raining (p  q) r If it is hot and humid, then it is raining qp If it is humid, then it is hot M: I have money L: I like the LG-mobile B: I will buy the LG-mobile T: I find a touch screen (M  L  T) B If I have money and I like the LG-mobile and I find a touch screen, then I will buy the LG-mobile If I have money and I like the LG-mobile, then I will buy it if I find a touch screen The same logical formula can be expressed in different ways  A sentence (well formed formula) is defined as follows:  A symbol is a sentence (e.g. p)  If p is a sentence, then p is a sentence  If p is a sentence, then (p) is a sentence  If p and q are sentences, then (p  q), (p  q), (p q), and (p ↔ q) are sentences  A sentence results from a finite number of applications of the above rules o We call these recursive definitions Implication is always true, when the premise is false. Why? P=>Q means “if P is true then I am claiming that Q is true, otherwise no claim” Only way for this to be false is if P is true and Q is false But, truth table construction is very expensive!  How do we draw new conclusions from existing supplied facts?  We can define inference rules, which are guaranteed to give true conclusions given true premises (Laws of thought-based approach in AI)  One such rule is modus ponens  If A is true and A B is true, then conclude B is true  All living things will eventually die  Some mammals can fly  The above facts cannot be expressed in propositional logic  Propositionallogic does not deal with general statements, which include quantifiers  But, quantifications are very common in knowledge/reasoning processes  Propositional logic lacks expressivity – we need some other logic to represent quantification  Predicate logic could serve this purpose  Predicate A sentence often has two parts: subject and predicate  Subject is what/whom the sentence is about Crow is black.  Predicate tells something about the subject Crow is black.  Predicate logic allows us to describe properties of objects and/or relations among the objects  Crow is black: black(crow)  Hassan is brother of Bilal: brother_of(hassan, bilal)  In predicate logic, the basic unit is a predicate- argument structure, called an atomic sentence:  likes(hassan, chocolate)  tall(ali)  Arguments can be:  constant symbol, such as ali  variable symbol, such as X  function expression, e.g., father_of(hassan)  So we can have:  likes(X, chocolate)  friends(son_of(ali), son_of(omar))  Predicate returns truth value; function returns object  Constants and functions are often called ground terms, because they represent objects in the real world