CI Unit 1.pptx

COMPUTATIONAL INTELLIGENCE MSc CS Sem – I, Paper – 4 UNIT 1 – Part 1  WHAT IS AI? Definitions of AI from 4 aspects: Think Like Think Rationally Humans Act Like Humans Act Rationally  Thinking Humanly (compared to human performance)...

COMPUTATIONAL INTELLIGENCE MSc CS Sem – I, Paper – 4 UNIT 1 – Part 1  WHAT IS AI? Definitions of AI from 4 aspects: Think Like Think Rationally Humans Act Like Humans Act Rationally  Thinking Humanly (compared to human performance) “The exciting new effort to make computers think... machines with minds, in the full and literal sense.” (Haugeland, 1985) “[The automation of] activities that we associate with human thinking, activities such as decision- making, problem solving, learning...” (Bellman, 1978)  Thinking Rationally (compared to ideal performance) “The study of mental faculties through the use of computational models.” (Charniak and McDermott, 1985) “The study of the computations that make it possible to perceive, reason, and act.” (Winston, 1992)  Acting Humanly (compared to human performance) “The art of creating machines that perform functions that require intelligence when performed by people.” (Kurzweil, 1990) “The study of how to make computers do things at which, at the moment, people are better.” (Rich and Knight, 1991)  Acting Rationally (compared to ideal performance) “Computational Intelligence is the study of the design of intelligent agents.” (Poole et al., 1998) “AI... is concerned with intelligent behavior in artifacts.” (Nilsson, 1998)  To Act humanly computer would need to possess the following capabilities: natural language processing, knowledge representation, automated reasoning, machine learning, computer vision,  To Think humanly we need to use cognitive science that brings together computer models from AI and experimental techniques from psychology to construct precise and testable theories of the human mind.  To Think rationally “laws of thought” approach is useful. E.g “Socrates is a man; all men are mortal; therefore, Socrates is mortal.” This is a field of Logic.  To Acting rationally we build a rational agent. A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome. AGENTS AND ENVIRONMENTS  AGENTS An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. sensors actuators For human eyes, ears, and hands, legs, agent other organs vocal tract, etc robotic cameras and various motors agent infrared range finders  percept refer to the agent’s perceptual inputs at any given instant. agent’s percept sequence is the complete history of everything the agent has ever perceived. PROBLEM-SOLVING AGENTS The goal of a problem solving agent is to choose a proper sequence of actions that will lead to a rational environment state. Performance measure evaluates  The process of looking for a sequence of actions that reaches the goal is called search. A search algorithm takes a problem as input and returns a solution in the form of an action sequence.  What is a PROBLEM & a SOLUTION? A problem can be defined formally by five components: 1. The initial state that the agent starts in. 2. A description of the possible actions available to the agent. 3. Transition model - A description of what each action does. successor : any state reachable from a given state by a single action. state space of the problem is a set of all states reachable from the initial state by any sequence of actions. A path in the state space is a sequence of states connected by a sequence of actions.  4. The goal test, which determines whether a given state is a goal state. 5. A path cost function assigns a numeric cost to each path. A solution to a problem is an action sequence that leads from the initial state to a goal state. an optimal solution has the lowest path cost among all solutions. The Romania Problem  Imagine an agent in the city of Arad, Romania, enjoying a touring holiday. Suppose the agent has a map of Romania. Now, suppose the agent has a nonrefundable ticket to fly out of Bucharest the following day. In that case, it makes sense for the agent to adopt the goal of getting to Bucharest. Define Romania Problem using 5 Components initial state: our agent is In(Arad). possible actions available: e.g. {Go(Sibiu), Go(Timisoara), Go(Zerind)}. Transition model: e.g. RESULT(In(Arad),Go(Zerind)) = In(Zerind). goal test: {In(Bucharest )} ? path cost: in this example distance in km’s will be added together for final path cost.  SEARCHING FOR SOLUTIONS Initial state, actions and states in the state space of the problem form a search tree. For Romania problem the search tree may look like this,  This is how we may search for the action sequence to find Bucharest.  Measuring problem-solving algorithms performance Completeness: Is the algorithm guaranteed to find a solution when there is one? Optimality: Does the strategy find the optimal solution? Time complexity: How long does it take to find a solution? Space complexity: How much memory is SEARCH STRATEGIES There are two types: 1. UNINFORMED SEARCH STRATEGIES(blind search) The strategies have no additional information about states beyond that provided in the problem definition. They do generate successors and check whether it is goal state or not. ex. Breadth-first search, Depth-first search, Iterative deepening depth-first search  BFS  DFS  Iterative Deepening 2.INFORMED SEARCH STRATEGIES(Heuristic Search) Strategy that uses problem-specific knowledge beyond the definition of the problem itself. more efficient than an uninformed strategy. In Heuristic Search we use 3 functions; f(n):- estimated cost to reach goal from initial node via node n. g(n):- estimated cost to reach node n from initial node. h(n):- (heuristic function) estimated cost to reach goal from node n.  Best-first search, it is the general approach we follow in informed search. Here, a node is selected for expansion based on an evaluation function i.e. a cost estimate, f(n) The node with the lowest evaluation is expanded first.  Greedy best-first search Expanding node closest to the goal, this may likely to lead to a solution quickly. there for we use, f(n) = h(n) In Romania problem, lets use straight-line- distance hSLD as heuristic. If the goal is to reach Bucharest then, SLD to Bucharest is the heuristic value. SLD can not be calculated using problem description and it is a useful heuristic.  Values of hSLD Arad 366 Drobeta 242 Bucharest 0 Eforie 161 Sibiu 253 Giurgiu 77 Timisoara 329 Hirsova 151 Zerind 374 Iasi 226 Fagaras 176 Lugoj 244 Oradea 380 Urziceni 80 Rimnicu Neamt 234 Vilcea 193 Mehadia 241 Craiova 160 Vaslui 199 Pitesti 100 Fagaras Stages in a greedy best-first tree search Greedy best-first search It is not optimal:- path via Sibiu and Fagaras(450km) is 32 kilometers longer than the path through Rimnicu Vilcea and Pitesti(418). It is incomplete:- consider going from Iasi to Fagaras. If we imagine from given map, algo. will lead us to Neamt as its SLD to Fagarus is lesser than that of Vaslui. But in reality it is a dead end. (i.e. Greedy) Fagaras  A* search In A* search, f(n) = g(n) + h(n) g(n) cost to reach the node n & h(n) cost to get from the node n to the goal. So in A* Search we expand a node with the lowest value of g(n) + h(n) i.e. will find for the solution through n with the cheapest estimated cost. Stages in an A∗ search  Optimality of A*: Admissibility and consistency A∗ is optimal if h(n) is admissible. An admissible heuristic is one that never overestimates the cost to reach the goal. Straight-line distance is admissible because the shortest path between any two points is a straight line, so the straight line cannot be an overestimate.  Consistency is slightly stronger condition. A heuristic h(n) is consistent if, for every node n and every successor n’ of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal from n’. hSLD is a consistent heuristic. Hence A* Search is optimal.  Completeness of A*: As A* expands all nodes with f(n) P ∧ Q Conclusion-1: It's raining. ==> P Conclusion-2: the ground is wet. ==> Q Inference Rules Resolution: If P ∨ Q and ¬ P ∨ R is true, then Q ∨ R will also be true. Case 1: P is true. Then ¬ P is false. So for 2nd sentence to be true R must be true. Case 2: ¬ P is true. Then P is false. So for 1st sentence to be true Q must be true. Statement-1: It is raining, or I will make tea. ==> P ∨ Q Statement-2 : It is not raining, or I will read a book. ==> ¬ P ∨ R Conclusion: I will make tea, or I will read a book. ==> Q ∨ R  Inference: Forward chaining and Backward Chaining There are two main methods of reasoning when using an inference engine, Forward chaining and Backward Chaining. Forward Chaining: (Deductive inference rule) Conclude from "A" and "A implies B" to "B". Example: It is raining. ==> A If it is raining, the street is wet. ==> A ⇒ B The street is wet. ==> B  Forward Chaining Example The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of America, has some missiles, and all of its missiles were sold to it by Colonel West, who is American. Prove that Col. West is a criminal.  Step 1  Step 2  Step 3  Inference: Forward chaining and Backward Chaining Backward Chaining: (Abductive inference rule) Conclude from "B" and "A implies B" to "A". Example: The street is wet. ==> B If it is raining, the street is wet. ==> A ⇒ B It is raining. ==> A  Now Lets Solve problem using Backward Chaining Step 1  Step 2  Step 3  Step 4  Step 5 Finally we proved Col.West is criminal using backward chaining algorithm. Inference: Forward chaining and Backward Chaining Forward Chaining Backward Chaining Forward chaining starts from Backward chaining starts from known facts and applies the goal and works backward inference rule to extract more through inference rules to find data unit it reaches to the goal. the required facts that support the goal. It is a bottom-up approach It is a top-down approach Its is data-driven inference It is goal-driven technique as technique as we reach to the we start from the goal and goal using the available data. divide into sub-goal to extract the facts. Inference: Forward chaining and Backward Chaining Forward Chaining Backward Chaining It tests for all the available It only tests for few required rules. So it is slow. rules. It is comparatively fast. It is suitable for the planning, It is suitable for diagnostic, monitoring, control, and prescription, and debugging interpretation application. application. It can generate an infinite It generates a finite number of number of possible conclusions. possible conclusions. Inference: Forward chaining and Backward Chaining Forward Chaining Backward Chaining It operates in the forward It operates in the backward direction. direction. Forward chaining is aimed for Backward chaining is only any conclusion. aimed for the required data. First Order Predicate Logic In simple words, First order Predicate Logic / Predicate Logic is the Propositional logic with quantifiers and variables. Predicate Logic Predicates: These are relations showing how one element is related to another. Example – Animal(donkey) -- Donkey is an animal. – Eats(donkey, grass) -- Donkey eats grass. Predicate Logic Variables: Term which may have different values. Example. x, y, z, horse. Constants: Symbols to represent an element which may be a physical object such as chair, man, banana or an abstract idea or viewpoint. Example. – Jacky a horse (physical object) Predicate Logic Connectives: Used to express compound propositions by combining formulae to build more complex world wide formula (WWF). Example ▫ ∧ and, ∨ or, → implies,  iff, ￢ negation Quantifiers: Used to express assertions involving words for all or each. ▫ Universal quantifiers: ∀ ▫ Existential quantifiers: ∃ Predicate Logic Universal quantifiers: We use symbol ∀ and a variable say Xi (i>=1). Xi range over the domain of interpretation. Example. ▫ All birds have feathers. ∀x [Birds(x) Have_Feathers(x)] variable occurring just after ∀ is universally quantified var. Existential quantifiers: ∃x asserts that there exists at least one assignment of x, so that the concerned formula is true. Example ▫ ∃x (x ≥ x2) is true since x = 0 is a solution.  Predicate Logic “Everybody loves somebody” - ∀x ∃y Loves(x, y) “There is someone who is - ∃y ∀x Loves(x, loved by everyone” y) One’s husband is one’s male spouse – ∀ w, h Husband(h,w) ⇔ Male(h) ∧ Spouse(h,w) A grandparent is a parent of one’s parent – ∀ g, c Grandparent (g, c) ⇔ ∃p Parent(g, p) ∧ Parent(p, c) A sibling is another child of one’s parents – ∀ x, y Sibling(x, y) ⇔ x ≠ y ∧ ∃p Parent(p, x) ∧ Predicate Logic Male and female are disjoint categories: – ∀x Male(x) ⇔ ￢ Female(x) There is a country that borders both Iraq and Pakistan. – ∃c Country(c) ∧ Border (c, Iraq) ∧ Border (c, Pakistan). All countries that border Ecuador are in South America. – ∀c Country(c) ∧ Border (c,Ecuador ) ⇒ In(c, Predicate Logic 1. Every student has a book. ∀x (student(x))  (∃y) book(y) ∧ has(x,y) 2. Every woman is caring. Jane is woman. Therefore Jane is caring. Woman(x) – x is a woman Caring(x) – x is caring Every woman is caring: ∀x (Woman(x)  Caring(x)) Jane is a woman: Woman(Jane) Jane is caring: Caring(Jane) Predicate Logic  Write the following assertions in first-order logic  Convert to First order logic:  Emily is either a surgeon or a lawyer.  All surgeons are doctors.  Joe does not have a lawyer  Emily has a boss who is a lawyer.  There exists a lawyer all of whose customers are doctors.  Every surgeon has a lawyer. Predicate Logic Translate into good, natural English (no xs or ys!): ∀ x, y, l SpeaksLanguage(x, l) ∧ SpeaksLanguage(y, l) ⇒ Understands (x, y) ∧ Understands(y, x). Predicate Logic Example using Forward Chaining 3. Every mother cares for her children. Nitu is a mother. Ritu is her child. Show that Nitu Cares for Ritu. ▫ Every mother cares for her children: ▫ ∀x (mother (x))  (∃y) child(y, x) ∧ care(x, y) ▫ Nitu is a mother: Mother(Nitu) ▫ Ritu is her child: Child(Ritu, Nitu) ∀x (mother (x))  ((∃y) child(y, x) ∧ care(x, y)) ∧ Mother(Nitu) Mother(Nitu)  ((∃y) child(y, Nitu) ∧ care(Nitu, y)) ∧ Child(Ritu, Nitu)  Mother(Nitu)  ((∃y) child(Ritu, Nitu) ∧ care(Nitu, Ritu))  Care(Nitu, Ritu). Hence Proved. Predicate Logic All students who are members can read in a library: ∀x (student (x) ∧ member(x, library)  read(x)) There is someone who is going to teach all the subjects. ∃x [person(x) ∧ (∀y)] [subject(y)  will_teach(x, y)] (there exists some x for person x and all subjects y such that y is a subject implicates that x is going to teach for y) Anyone who is good and intelligent will deliver excellent lecture. ∀x [Q(x) ∧ I(x)]  R(x) Q(x) = x is good; I(x) = x is intelligent; R(x) = x delivers an excellent lecture. Predicate Logic Tom is a student of computer science but not a cricket or baseball player. student(Tom, computer science) ∧ ￢ cricket_player(Tom) ∧ ￢ baseball_player(Tom) For all students, there is some time for play and watch a movie. ∀x [student(x) (∃y) time(y)] ∧ [ play(x, y) ∨ watch_movie(x, y) ] If you do not run, then you will be lazy. ∀x (person(x) ∧ ￢ run(x))  lazy(x) Predicate Logic All persons either like it or dislike it. ∀x [person(x)] ((∃y)  like(x, y) ∨ ￢ like(x, y)) Every student reads the topic or ignores it. ∀x Student(x) ∧ (∃y topic(y)  read(x, y) ∨ ignore(x, y)) She is beautiful and intelligent but not sincere. beautiful(she) ∧ intelligent(she) ∧ ￢  Predicate Logic Using Backward Chaining: Consider Following statements: 1. Marcus was a man. man(Marcus) 2. Marcus was a Pompeian. Pompeian(Marcus) 3. All Pompeian were Romans. (∀x) Pompeian(x)  Roman(x) 4. Caesar was a Ruler. ruler(Caesar) Predicate Logic 5. All Romans were either loyal to Caesar or hated him. (∀x) Roman(x)  loyalto(x, Caesar) ∨ hate(x, Caesar) “or” can be sometimes “inclusive-or” and “exclusive- or”. In above sentence or is actually used as exclusive-or, to express that we can write, (∀x) Roman(x)  (loyalto(x, Caesar) ∨ hate(x, Caesar)) ∧ Predicate Logic 7. People only try to assassinate rulers they are not loyal to. (∀x) (∀y) person(x) ∧ ruler(y) ∧ try_assassinate(x,y)  ￢ loyalto(x,y) Again the above sentence is ambiguous. It may mean that “the only ruler that people try to assassinate are those to whom they are not loyal” (we have used this meaning) or does this mean that “the only thing people try to do is to assassinate rulers to whom they are not loyal”. 8. Marcus tried to assassinate Caesar. try_assassinane(Marcus, Caesar)  Predicate Logic Additional background knowledge: 9. All men are people. (∀x) man(x)  people(x) Was Marcus loyal to Caesar? Lets try solving this in Backward Chain fashion. Can we prove, ￢ loyalto(Marcus, Caesar) Predicate Logic ￢ loyalto(Marcus, Caesar) ↑ (using 7) person(Marcus) ∧ ruler(Caesar) ∧ try_assassinate(Marcus, Caesar) ↑ (using 4) person(Marcus) ∧ try_assassinate(Marcus, Caesar) ↑ (using 8) person(Marcus) ↑ (using 9) Man(marcus) ↑ (using 1) NIL. Hence  HOME WORK 1. John likes all kind of food. 2. Apples and chicken are food. 3. Anything anyone eats and is not killed by is food. 4. Bill eats peanuts and is still alive. 5. Sue eats everything that Bill eats. Prove that “John Likes Peanuts” using backward chaining.  Home Work What is wrong with the following argument: 1. Men are widely distributed over the earth. 2. Socrates is a man. 3. Conclusion: Therefore, Socrates is widely distributed over the earth. How should the facts expressed by these sentences be represented in logic so that this problem does not arise ? Resolutio n This is another method of reasoning when using an inference engine. In chaining methods we compare Predicates and here we compute Predicates. Resolution is a theorem proving technique that proceeds by building refutation proofs, i.e., proofs by contradictions. Resolution efficiently operate on the conjunctive normal form or clausal form. – Disjunction of literals (an atomic sentence) is called a clause – A sentence represented as a conjunction of clauses is said to be conjunctive normal form or CNF Resolution Conjunctive Normal Form rules: – Eliminate implication ‘→’ a→b=¬a∨b ¬ (a ∧ b) = ¬ a ∨ ¬ b …………………….. DeMorgan’s Law ¬ (a ∨ b) = ¬ a ∧ ¬ b ……………………... DeMorgan’s Law ¬ (¬ a) = a – Eliminate Quantifier ‘∃’ & ‘∀’ – Eliminate AND a∧b splits into a and b (a ∨ b) ∧ c splits into a ∨ b and c (a ∧ b) ∨ c splits into a ∨ c and b ∨ c  Resolution Steps for Resolution: Conversion of facts into first-order logic. Convert FOL statements into CNF Negate the statement which needs to prove (proof by contradiction) Draw resolution graph / Refutation tree. Resolution Example 1: 1.Cat likes Fish 2.Cats eats everything they like. 3.Mani is a Cat. Prove that “Mani eats Fish”  Resolutio n Step 1: Conversion of facts into first-order logic 1. ∀x Cat(x)  likes(x, fish) 2. ∀x ∀y [Cat(x) ∧ likes(x, y)]  eats(x, y) 3. Cat(Mani) Prove eats(Mani, Fish) Step 2: Convert FOL statements intoStep CNF3: Negate the 1. ￢ Cat(x) ∨ likes(x, fish) goal statement ￢ eats(Mani, 2. ￢ [Cat(x) ∧ likes(x, y)] ∨ eats(x,oy) Fish) ￢ Cat(x) ∨ ￢ likes(x, y) ∨ eats(x, y) 3. Cat(Mani) Resoluti on Step 4: Draw Refutation tree. ￢ eats(Mani, Fish) ￢ Cat(x) ∨ ￢ likes(x, y) ∨ eats(x, y) ￢ Cat(Mani) ∨ ￢ Cat(Man likes(Mani, Fish) i) ￢ likes(Mani, ￢ Cat(x) ∨ likes(x, Fish) fish) ￢ Cat(Mani) Cat(Mani) NIL  Resolution Example 2: 1. Ravi likes all kind of food. 2. Apples and chicken are food. 3. Anything anyone eats and is not killed by is food. 4. Ajay eats peanuts and is still alive. 5. Rita eats everything that Ajay eats. Prove : Ravi likes peanuts.  Resolution 1. ∀x : food(x) → likes (Ravi, x) 2. food (Apple) ∧ food (chicken) 3. ∀a : ∀b: eats (a, b) ∧ ￢ killed (a) → food (b) 4. eats (Ajay, Peanuts) ∧ alive (Ajay) 5. ∀c : eats (Ajay, c) → eats (Rita, c) 6. ∀d : alive(d) → ￢ killed (d) 7. ∀e: ￢ killed(e) → alive(e) Prove: likes (Ravi, Peanuts) Resoluti on Converting FOL into CNF 1. ¬ food(x) V likes(Ravi, x) food(Apple) Λ food(chicken) 2. food(Apple) 3. food(chicken) ∀a ∀b ¬ [eats(a, b) Λ ¬ killed(a)] V food(b) 4. ¬ eats(a, b) V killed(a) V food(b) eats (Ajay, Peanuts) Λ alive(Ajay) 5. eats (Ajay, Peanuts) 6. alive(Ajay)  Resolution 7. ¬ eats(Ajay, c) V eats(Rita, c) 8. ¬ alive(d) V ¬ killed(d) ∀x ¬ [¬ killed(e) ] V alive(e) 9. killed(e) V alive(e) Prove : likes(Ravi, Peanuts). o Negate the conclusion: ¬ likes (Ravi, Peanuts) Resolution Refutation tree:  Home Work Consider the following statements: 1. If maid stole jewelry then butler is not guilty. 2. Either maid stole the jewelry or she milk the cow. 3. If maid milk the cow then butler got the cream. Use resolution to Prove. If butler is guilty then he got the cream.