AI Lecture Notes PDF

Lec 2 Dr Mosa Elkhedr  Lecture 2 Ch2: Knowledge Representation 1/31 Pyramid of Knowledge 2/31  Human Problem Solving Humans are best at understanding, reasoning, and interpreting knowledge. 3/31 Hum...

Lec 2 Dr Mosa Elkhedr  Lecture 2 Ch2: Knowledge Representation 1/31 Pyramid of Knowledge 2/31  Human Problem Solving Humans are best at understanding, reasoning, and interpreting knowledge. 3/31 Human Problem Solving... 4/31  Requirements for AI Problem Solving There are three factors which are put into the machine, which makes it valuable: 1.Knowledge: The information related to the environment is stored in the machine. 2.Reasoning: The ability of the machine to understand the stored knowledge. 3.Intelligence: The ability of the machine to make decisions on the basis of the stored information. 5/31  AI Technique In the real world, the knowledge has some unwelcome properties: ◦ Its volume is huge (Big data), next to unimaginable. ◦ It is not well-organized/well-formatted (unstructured data/heterogeneous). ◦ It keeps changing constantly (dynamic). AI technique is a manner ‫طريقه‬to organize and use the knowledge efficiently in such a way that: ◦ It should be perceivable‫ يمكن ادراكه‬by the people who provide it. ◦ It should be easily modifiable to correct errors. ◦ It should be useful in many situations though it is incomplete or inaccurate. 6/31  Knowledge Representation Language KR is a study of how the beliefs, intentions, and judgments of an intelligent system can be expressed suitably for automated reasoning. ‫هي دراسة لكيفية التعبير عن معتقدات ونوايا وأحكام النظام الذكي بشكل‬ ‫مناسب لالستدالل اآللي‬ Any KRL defined by two aspects: 1.The syntax of a language describes the possible configurations that can constitute sentences. For example, the syntax of the language of arithmetic expression such as x > y is a sentence about numbers. 2.The semantics determines the facts in the world to which the sentences refer. The semantics of the language says that x > y is false when y is a 7/31 bigger number than x, and true otherwise. All reasoning mechanisms must operate on representations of  Knowledge Representation The two most fundamental concerns of AI researchers are: 1.Knowledge representation, and 2.Search. Knowledge Representation: ◦ In general, a representation is a set of conventions about how to describe a class of things in a formal language, i.e., a language suitable for computer manipulation. ◦ Good representations are the key to good problem solving. Consider, for example, ◦ the children’s puzzle 3x3: 8/31  Reasoning and Inference Procedure Reasoning must be a process of constructing new configurations from old ones. We want to generate new sentences that are necessarily true, given that the old sentences are true. This relation between sentences is called entailment,‫ استلزام‬KB |= A. An inference procedure, given a knowledge base KB, it can generate new sentences that purport‫ يزعم‬to be entailed by KB. 9/31 Knowledge Representation and Reasoning KR 2 or KR&R is the field of AI dedicated to: ◦ Represent information/facts about the world in a form that a ◦ computer system can utilize to solve complex tasks. ◦ Not just about storing data in a database ◦ Allow a machine to learn from that knowledge and behave ◦ intelligently like a human being. Such as diagnosing a medical condition or having a dialog in a natural language. 10/3 1 Kinds of Knowledge to Represent 11/3 1  Representations and Mappings Mapping between facts and representation. Normal English is insufficient, too hard currently for a computer program to draw inferences in natural languages. 12/3 1 Knowledge Representation Schemes 13/3 1  Knowledge Representation Scheme Judgement Expressiveness‫يرات‬2‫التعب‬: able to handle different types and levels of granularity‫يل‬gg‫ تفاص‬of knowledge and knowledge structures and the relationships between them. Related to Representational Adequacy property. Can it clearly and completely represent the necessary data? Effectiveness‫فعالبة‬: it must provide a means of inferring new knowledge from old. It should also be amenable to computation. Related to Inferential Adequacy property. Can one use the data for computation and inference? Efficiency: it should not only support inference of new knowledge from old but must do so efficiently in order for new knowledge to be used. Related to Inferential Efficiency and Acquisitional Efficiency property.Can one gather and harness the data easily? 14/3 1 Explicitness‫راحه‬22‫الص‬: it should be able to provide an explanation of its inference and allow justifications of its reasoning. Related to Inferential Adequacy property.Does it  Knowledge Representation Scheme Parts A representation has four parts: 1.The lexical part: describes vocabulary of allowable symbols. 2.The structural part: describes constraints on the combination of symbols. 3.The procedural part: describes access procedures such as constructors. 4.The semantic part: associates a meaning with the description. 15/31  Semantic Network Process of knowledge representation is defined as a process of extracting or generating a set of rules for describing a class of entities. A semantic network, or frame network is a knowledge base that represents semantic relations between concepts in a network. It is a directed or undirected graph consisting of vertices, which represent concepts, and edges, which represent semantic relations between concepts, mapping or connecting semantic fields  Semantic Nets A node-and-link knowledge description technique. Semantic net parts: 1.Lexical: Nodes: represent objects and appear as circles, ellipses or rectangles Links: for connecting nodes (i.e., represent relations between objects) and appear as arrows pointing from one node to another node. 2.Structural: each link connects tail node to head node. 3.Semantic: nodes links denote application-specific entities. 4.Procedural: can construct a node, construct a link, list from node its out-links, list from link its tail node, list from link its label, etc. 16/31 Semantic Nets 17/31  Semantic Net Example "A bluebird is a small blue-colored bird and a bird is a feathered flying vertebrate." Objects: bluebird, bird, vertebrate, feather. Relations: “is”, “fly”, and “covered with”. Advances: unifying relations, may consider relation type as an object, e.g., bluebird has color blue, objects of this statement are bluebird and blue, the relation is the color, in this case it 18/31  Semantic Net Example "A bluebird is a small blue-colored bird and a bird is a feathered flying vertebrate." 18/31  Semantic Net Example... Semantic network can be translated to statements as follows: Bird – – is a – –> vertebrate Bird – – has property – –> flies Bird – – has covering – –> feather Bluebird – – is a – –> bird Bluebird – – has color – –> blue Bluebird – – has size – –> small 19/31  Semantic Net Example... "A farmer with his wolf, goat, and cabbage come to the edge of a river they wish to cross. There is a boat at the river’s edge which can carry only two things (including the farmer) at a time. If the wolf is ever left alone with the goat, the wolf will eat the goat; similarly, if the goat is left alone with the cabbage, the goat will eat the cabbage. So, the farmer must not leave the wolf alone with the goat or the goat alone with the cabbage. What is he to do?" 20/31 Farmer takes Goat across the river (valid move, no danger on either side). Farmer returns alone (valid, no danger on either side). Farmer takes Wolf across the river (valid move, leaving Cabbage alone is safe). Farmer brings Goat back (to avoid danger between Wolf and Goat). Farmer takes Cabbage across (valid move, no danger between Wolf and Cabbage). Farmer returns alone (valid, no danger). Farmer takes Goat across the river again (final move, all safely across). Semantic Net Example... 21/31  Advantages of Semantic Net Natural representation of knowledge. Simple and easily understandable. Efficient. Translatable to PROLOG. 22/31  Disadvantages of Semantic Net Take more computational time at runtime as we need to traverse the complete network tree to answer some questions. Inadequate as they do not have any equivalent quantifier‫محدد كمى‬, e.g., for all, for some, none, etc. Do not have any standard definition for the link names. Not intelligent and depend on the creator of the system. Try to model human-like memory to store the information, but in practice, it is not possible to build such a vast semantic network. 23/31  KR using Frames and Scripts In structured representations information is organized into more complex knowledge structures. Slots in the structure represent attributes into which values can be placed. These values are either specific to a particular instance or default values, which represent stereotypical information. Structured representations can capture complex situations or objects, for example eating a meal in a restaurant or the context of a hotel room. Such structures can be linked together as networks, giving property inheritance. Frames and scripts are the most common types of structured representations.”  Frames All information relevant to a particular concept is stored in a single complex entity called a frame. A frame is basically a group of slots and fillers that define a stereotypical object. A complete frame based representation will consist of a whole hierarchy or network of frames connected together by appropriate links/pointers. 24/31 Frame Types 25/31  Slots Each slot contains one or more facets. Facets may take the following forms: 1.Values/Defaults. 2.Ranges. 3.Pointers to other frames. 4. Set of rules or procedures. Slots can have procedures If-added: a procedural attachment which specifies an action to be taken when a value in the slot is added/modified. If-needed: a procedural attachment which triggers a procedure which goes out to get information which the slot does not have. 26/31 Slots... 27/31 Frame Example 28/31  Pros and Cons of Frames Pros: ◦ The frame KR makes the programming easier by grouping the related data. ◦ Inheritance is easily controlled. ◦ Easy to add slots for new attribute and relations. ◦ Easy to include default data and to search for missing values. Cons: ◦ As semantic networks, there are no standards for defining frame-based systems. ◦ In frame system inference mechanism is not be easily processed. ◦ Frames cannot represent exceptions. 29/31 Semantic Network to Frame Example 30/31 Semantic Network to Frame Example... 31/31  Predicate Calculus A language for expressing the qualities ‫الصفات‬and interactions between objects in problem areas, where the solutions involve qualitative reasoning ‫المنطق النوعى‬rather than numerical computations. Components of Predicate Calculus Predicate: denotes some attribute or connection among its arguments (appearing within parentheses). Parameters: are symbols that represent things in the domain. General form of a propositional calculus sentence: relation(1st object, 2nd object) 29/31  Predicate Calculus Propositional calculus sentences is read in the following sequence: st object – relation/predicate – 2nd object. For example, if we have a predicate “is_a (bluebird, bird)” −→ bluebird is_a bird Recall the "Bluebird" scenario. Solution for this scenario. has_size(bluebird, small) has_covering(bird, feather) 29/31  has_color(bluebird, blue) has_property(bird, flies) is_a(bluebird, bird) is_a(bird, vertebrate) Another scenario of "World of blocks". For describing blocks and their states as shown in the Figure , list of objects are {a, b, c, and table}, relation types are {on, and type}, new relations that could be inferred based on these relations are {clear −→ if object doesn’t carry any other objects, base object −→ if the object is directly on the table}. In predicate calculus, the rule can be written: ∀X,¬∃Yon(Y,X) → clear(X) That is, "for all X, X is clear if there does not exist a Y such that Y is on X". Such new inferences will be postponed after studying predicate calculus forms.  clear(c) clear(a) clear(a) clear(c) ontable(a) on(a,table) ontable(b) on(b,table) on(c,b) on(c,b) cube(b) is_a(b,cube) cube(a) is_a(a,cube) pyramid(c) is_a(c,pyramid) Syntax of Propositional Calculus First step in knowledge representation using predicate calculus is the abstraction −→ forming classes using set of symbols. Symbols: uppercase letters of the English alphabet – Examples of propositional symbols: P, Q, R, S... etc. – Truth symbols: true, false −→ interpreted into {T,F}. – Symbols denote propositions, or statements about the world that may be either true or false, e.g., "the weather is warm". Thus the terminology “interpretation” is a mapping from the propositional symbols into the set {T, F}.  Connectives: ∧,∨,¬,→,≡ Rules for forming well-formed formulas (WFF) in propositional calculus: 1. Every propositional symbol and truth symbol is a sentences (e.g., true, P, Q, and R are sentences). 2. The negation of a sentence is a sentence (e.g., ¬P). 3. The conjunction "and" of two sentences is a sentence (e.g., P ∧ Q). 4. The disjunction "or" of two sentences is a sentence (e.g., P ∨ Q). 5. The implication of one sentence from another is a sentence (e.g., P → Q). 6. The equivalence of two sentences is a sentence (e.g., P ≡ Q).  Semantics of Propositional Calculus Suppose that P and Q are two symbols the represent two sentence in the world e.g., P: “temperature >35” and Q: “weather is hot”. In case of assessing truth value between two symbols then number of permutations are (2#symbols), here 22 = 4.  Using truth table, we could conclude if the sentence is valid, satisfiable, or contradiction, as seen in Table : A sentence is valid/tautology if it holds under every interpretation. A sentence is satisfiable if it holds under some interpretation. A sentence is unsatisfiable/ contradiction if it holds under no interpretation  Important notes The representation principle: “Once a problem is described using an appropriate representation, the problem is almost solved”. Knowledge Representation Languages: to meet the needs for symbolic computing, AI has developed representation languages such as: predicate calculus, semantic networks, frames, and Production rules. LISP and PROLOG are languages for implementing these and other representations.  State space search refers to a problem-solving strategy that system atically investigates a space of issue states (called state space), i.e., sequential and alternate phases in the problem-solving process. There are two types for searching in the resulting state space search: 1. Exhaustive Search( brute-force search,): this technique tries all possible moves to get the solution path as indicated in tic- tac-toe game. This approach guarantees finding the solution, but it can be very inefficient for large problems because it explores all potential options without using any shortcuts or heuristics. exhaustive search is guaranteed to find the solution but is often computationally expensive, especially for large-scale problems, because it checks all possible options without optimization strategies.  2. Heuristic search: is a method of searching a problem space selectively. It directs search along routes with a high likelihood of success while avoiding wasteful or obviously dumb attempts A heuristic search is a problem-solving technique used in artificial intelligence and computer science, where a heuristic (a rule of thumb or an educated guess) is applied to guide the search process more efficiently toward the goal. It helps in reducing the number of paths or states to explore by prioritizing those that seem more promising based on the heuristic..  Characteristics of AI representation languages – Handle qualitative information. – Allow for the inference of new knowledge given a collection of facts and rules. Allow for the portrayal ‫تصوير‬of both broad concepts and specific instances. – Capture semantic meaning that is complicated. – Allow for meta-level logic.