AI Unit 2 PDF - BPSY121-4 Artificial Intelligence

BPSY121-4 Artificial Intelligence (AI) Dr. Suganthi J MISSION VISION CORE VALUES CHRIST is a nurturing ground for an individual’s...

BPSY121-4 Artificial Intelligence (AI) Dr. Suganthi J MISSION VISION CORE VALUES CHRIST is a nurturing ground for an individual’s Excellence and Service Faith in God | Moral Uprightness holistic development to make effective contribution to Love of Fellow Beings  CHRIST Deemed to be University Unit II: Knowledge Representation First order logic: Syntax and semantics for first order logic, Using first order logic, Knowledge engineering in first order logic, inference in first order logic; Propositional versus First order logic. Excellence and Service  CHRIST Deemed to be University Knowledge Representation in AI describes the representation of knowledge. Basically, it is a study of how the beliefs, intentions, and judgments of an intelligent agent can be expressed suitably for automated reasoning. One of the primary purposes of Knowledge Representation includes modeling intelligent behavior for an agent. Excellence and Service  CHRIST Deemed to be University Relation between Knowledge and Intelligence: Knowledge of real-worlds plays a vital role in intelligence and same for creating artificial intelligence. Knowledge plays an important role in demonstrating intelligent behavior in AI agents. An agent is only able to accurately act on some input when he has some knowledge or experience about that input. Excellence and Service  CHRIST Deemed to be University The different kinds of knowledge that need to be represented in AI include: Objects Events Performance Facts Meta-Knowledge Knowledge-base Excellence and Service  CHRIST Deemed to be University Types of Knowledge Excellence and Service  CHRIST Deemed to be University Declarative Knowledge – It includes concepts, facts, and objects and expressed in a declarative sentence. Structural Knowledge – It is a basic problem-solving knowledge that describes the relationship between concepts and objects. Procedural Knowledge – This is responsible for knowing how to do something and includes rules, strategies, procedures, etc. Meta Knowledge – Meta Knowledge defines knowledge about other types of Knowledge. Heuristic Knowledge – This represents some expert knowledge in the field or subject. Excellence and Service  CHRIST Deemed to be University Cycle of Knowledge Representation in AI ▪Perception ▪Learning ▪Knowledge Representation & Reasoning ▪Planning ▪Execution Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University The Perception component retrieves data or information from the environment. with the help of this component, you can retrieve data from the environment, find out the source of noises and check if the AI was damaged by anything. Then, there is the Learning Component that learns from the captured data by the perception component. The goal is to build computers that can be taught instead of programming them. Learning focuses on the process of self-improvement. In order to learn new things, the system requires knowledge acquisition, inference, acquisition of heuristics, faster searches, etc. Excellence and Service  CHRIST Deemed to be University The main component in the cycle is Knowledge Representation and Reasoning which shows the human-like intelligence in the machines. The Planning and Execution components depend on the analysis of knowledge representation and reasoning. Planning includes giving an initial state, finding their preconditions and effects, and a sequence of actions to achieve a state in which a particular goal holds. Now once the planning is completed, the final stage is the execution of the entire process. Excellence and Service  CHRIST Deemed to be University Techniques of Knowledge Representation in AI Excellence and Service  CHRIST Deemed to be University Logical Representation Logical representation is a language with some definite rules which deal with propositions and has no ambiguity in representation. It represents a conclusion based on various conditions and lays down some important communication rules. Also, it consists of precisely defined syntax and semantics which supports the sound inference. Each sentence can be translated into logics using syntax and semantics. Excellence and Service  CHRIST Deemed to be University Semantic Network Representation Semantic networks work as an alternative of predicate logic for knowledge representation. In Semantic networks, you can represent your knowledge in the form of graphical networks which consists of nodes representing objects and arcs which describe the relationship between those objects. Also, it categorizes the object in different forms and links those objects. This representation consist of two types of relations: IS-A relation (Inheritance) Kind-of-relation Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University Frame Representation A frame is a record like structure that consists of a collection of attributes and values to describe an entity in the world. These are the AI data structure that divides knowledge into substructures by representing stereotypes situations. Basically, it consists of a collection of slots and slot values of any type and size. Slots have names and values which are called facets. Excellence and Service  CHRIST Deemed to be University Production Rules Agent checks for the condition and if the condition exists then production rule fires and corresponding action is carried out. The condition part of the rule determines which rule may be applied to a problem. Whereas, the action part carries out the associated problem-solving steps. This complete process is called a recognize-act cycle. The production rules system consists of three main parts: 1. The set of production rules 2. Working Memory 3. The recognize-act-cycle Excellence and Service  CHRIST Deemed to be University Approaches to knowledge representation: 1. Simple relational knowledge: It is the simplest way of storing facts which uses the relational method, and each fact about a set of the object is set out systematically in columns. This approach of knowledge representation is famous in database systems where the relationship between different entities is represented. This approach has little opportunity for inference. Excellence and Service  CHRIST Deemed to be University Example: The following is the simple relational knowledge representation. Player Weight Age Player1 65 23 Player2 58 18 Player3 75 24 Excellence and Service  CHRIST Deemed to be University 2. Inheritable knowledge: In the inheritable knowledge approach, all data must be stored into a hierarchy of classes. All classes should be arranged in a generalized form or a hierarchal manner. Elements inherit values from other members of a class. This approach contains inheritable knowledge which shows a relation between instance and class, and it is called instance relation. Every individual frame can represent the collection of attributes and its value. Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University 3. Inferential knowledge: Inferential knowledge approach represents knowledge in the form of formal logics. This approach can be used to derive more facts. It guaranteed correctness. Example: Statements and Representation: Marcus is a man man(Marcus) All men are mortal ∀x = man (x) → mortal (x) Excellence and Service  CHRIST Deemed to be University 4. Procedural knowledge: Uses small programs and codes which describes how to do specific things, and how to proceed with one important rule which is If-Then rule. In this knowledge, various coding languages such as LISP language and Prolog language are used. Excellence and Service  CHRIST Deemed to be University Propositional Logic (PL) Simplest form of logic where all the statements are made by propositions. A proposition is a declarative statement which is either true or false. It is a technique of knowledge representation in logical and mathematical form. Example: a) It is Sunday. b) The Sun rises from West (False proposition) c) 3+3= 7(False proposition) d) 5 is a prime number. Excellence and Service  CHRIST Deemed to be University Basic facts about Propositional Logic: Also called Boolean logic as it works on 0 and 1. Symbolic variables are used to represent the logic, such A, B, C, P, Q, R, etc. Can be either true or false, but it cannot be both. Propositional logic consists of an object, relations or function, and logical connectives also called logical operators. Propositions and connectives are the basic elements of the propositional logic. Connectives can be said as a logical operator which connects two sentences.. Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University A proposition formula which is always true is called Tautology (valid sentence) A proposition formula which is always false is called Contradiction A proposition formula which has both true and false values is called Statements which are questions, commands, or opinions are not propositions such as "Where is Rohini", "How are you", "What is your name”. Compound proposition: Compound propositions are constructed by combining simpler or atomic propositions, using parenthesis and logical connectives. Example: a) "It is raining today, and street is wet." b) "Ankit is a doctor, and his clinic is in Mumbai." Excellence and Service  CHRIST Deemed to be University Logical Connectives: Connect two simpler propositions or representing a sentence logically. Compound propositions are created with the help of logical connectives. There are mainly five connectives, which are given as follows: 1. Negation: A sentence such as ¬ P is called negation of P. A literal can be either Positive literal or negative literal. 2. Conjunction: A sentence which has ∧ connective such as, P ∧ Q is a conjunction. Example: Rohan is intelligent and hardworking. It can be written as, P= Rohan is intelligent, Q= Rohan is hardworking. → P∧ Q. Excellence and Service  CHRIST Deemed to be University 3. Disjunction: A sentence which has ∨ connective, such as P ∨ Q. is called disjunction, where P and Q are the propositions. Example: "Ritika is a doctor or Engineer", Here P= Ritika is Doctor. Q= Ritika is Engineer, so we can write it as P ∨ Q. 4. Implication: A sentence such as P → Q, is called an implication. Implications are also known as if-then rules. It can be represented as If it is raining, then the street is wet. Let P= It is raining, and Q= Street is wet, so it is represented as P → Q 5. Biconditional: A sentence such as P⇔ Q is a Biconditional sentence, Example : If I am breathing, then I am alive P= I am breathing, Q= I am alive, it can be represented as P ⇔ Q. Excellence and Service  CHRIST Deemed to be University Propositional Logic Connectives Excellence and Service  CHRIST Deemed to be University Truth Table: In propositional logic, one can combine all the possible combination with logical connectives, and the representation of these combinations in a tabular format is called Truth table. Following are the truth table for all logical connectives: Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University Truth table with three propositions: Excellence and Service  CHRIST Deemed to be University Precedence of connectives: Just like arithmetic operators, there is a precedence order for propositional connectors or logical operators. This order should be followed while evaluating a propositional problem. Following is the list of the precedence order for operators: Precedence Operators First Precedence Parenthesis Second Precedence Negation Third Precedence Conjunction(AND) Fourth Precedence Disjunction(OR) Fifth Precedence Implication Six Precedence Biconditional Excellence and Service  CHRIST Deemed to be University Logical Equivalence: Two propositions are said to be logically equivalent if and only if the columns in the truth table are identical to each other. Let's take two propositions A and B, so for logical equivalence, A⇔B from the below truth table one can see that column for ¬A∨B and A→B, are identical hence A is Equivalent to B Excellence and Service  CHRIST Deemed to be University Excellence and Service  CHRIST Deemed to be University Points to connect FOL with Predicate Logic: Main connective for universal quantifier ∀ is implication → Main connective for existential quantifier ∃ is and ∧. Excellence and Service →  CHRIST Deemed to be University First-Order Logic - Sum Up Constants: Specific objects in the domain (e.g., Alice, Bob). Variables: Symbols that represent any object in the domain (e.g., x, y). Predicates: Functions that map objects to truth values (Likes(Alice, IceCream)). Quantifiers: Symbols to indicate the scope of a statement (∀ (for all), ∃ (exists)). Logical Connectives: Same as in propositional logic. Excellence and Service  CHRIST Deemed to be University Sample MCQs Which of the following is a valid term in First-Order Logic? a) John b) Likes(John, Mary) c) ∀x Likes(x, y) d) Like Excellence and Service  CHRIST Deemed to be University Which of the following is a valid term in First-Order Logic? a) John b) Likes(John, Mary) c) ∀x Likes(x, y) d) Like Answer: a) John Explanation: A term in FOL can be a constant (e.g., John) Likes(John, Mary) is a formula, not a term. Excellence and Service  CHRIST Deemed to be University Which of the following symbols represents the universal quantifier in First-Order Logic? a) ∃ b) ∀ c) → d) ∧ Excellence and Service  CHRIST Deemed to be University Which of the following symbols represents the universal quantifier in First-Order Logic? a) ∃ b) ∀ c) → d) ∧ Answer: b) ∀ Explanation: The universal quantifier is represented by the symbol ∀, meaning "for all." Excellence and Service  CHRIST Deemed to be University Which of the following is the main difference between Propositional Logic (PL) and First-Order Logic (FOL)? a) FOL allows variables, whereas PL does not. b) FOL is less expressive than PL. c) PL allows quantifiers, whereas FOL does not. d) FOL does not use connectives like ∧, ∨. Excellence and Service  CHRIST Deemed to be University Which of the following is the main difference between Propositional Logic (PL) and First-Order Logic (FOL)? a) FOL allows variables, whereas PL does not. b) FOL is less expressive than PL. c) PL allows quantifiers, whereas FOL does not. d) FOL does not use connectives like ∧, ∨. Answer: a) FOL allows variables, whereas PL does not. Explanation: First-Order Logic (FOL) extends Propositional Logic (PL) by introducing variables, quantifiers (e.g., ∀, ∃), and predicates, making it more expressive. Excellence and Service  CHRIST Deemed to be University Which of the following represents a correct use of unification in First-Order Logic? a) ∀x ∃y (Loves(x, y)) → ∀y ∃x (Loves(x, y)) b) ∀x (Loves(x, y)) → ∀y (Loves(x, y)) c) ∀x (FatherOf(x, y) → Parent(x, y)) d) FatherOf(John) and FatherOf(x) are unified. Excellence and Service  CHRIST Deemed to be University Which of the following represents a correct use of unification in First-Order Logic? a) ∀x ∃y (Loves(x, y)) → ∀y ∃x (Loves(x, y)) b) ∀x (Loves(x, y)) → ∀y (Loves(x, y)) c) ∀x (FatherOf(x, y) → Parent(x, y)) d) FatherOf(John) and FatherOf(x) are unified. Answer: d) FatherOf(John) and FatherOf(x) are unified. Explanation: Unification is the process of making two terms identical by finding an appropriate substitution for their variables. In this case, unifying FatherOf(John) and FatherOf(x) involves substituting x with John. Excellence and Service  CHRIST Deemed to be University What does the formula ∀x ∃y (Loves(x, y)) mean in First-Order Logic? a) "Everyone loves someone." b) "Someone loves everyone." c) "No one loves anyone." d) "Everyone is loved by someone." Excellence and Service  CHRIST Deemed to be University What does the formula ∀x ∃y (Loves(x, y)) mean in First-Order Logic? a) "Everyone loves someone." b) "Someone loves everyone." c) "No one loves anyone." d) "Everyone is loved by someone." Answer: a) "Everyone loves someone.“ Explanation: The formula ∀x ∃y (Loves(x, y)) means "For every person x, there exists a person y such that x loves y." Excellence and Service  CHRIST Deemed to be University Excellence and Service First-order logic is a foundational framework for representing knowledge in artificial intelligence (AI), especially in expert systems, natural language processing (NLP), and various other reasoning tasks.  CHRIST Deemed to be University Inference Terminology ▪ Substitution ▪ Negation Excellence and Service  CHRIST Deemed to be University Inference Terminology Substitution: Substitution is a basic procedure applied to terms & formulations F[a/x] refers to the substitution of a constant "a" for the variable "x." Excellence and Service  CHRIST Deemed to be University Inference Terminology Equality: Indicates that the two terms relate to the same thing. Example: Brother (John) = Smith. The object referred by the Brother (John) is close to the object referred by Smith. The equality symbol can be used with negation to portray that two terms are not the same objects. Example: ￢(x=y) which is equivalent to x ≠y. Excellence and Service  CHRIST Deemed to be University FOL Inference rules for Quantifier 1. Universal Generalization 2. Universal Instantiation 3. Existential Instantiation 4. Existential Introduction Excellence and Service  CHRIST Deemed to be University 1. Universal Generalization If premise P(c) is true, for any arbitrary element c in the universe of discourse, we can arrive at the conclusion ∀ x P(x) Let's represent, P(c): "A byte contains 8 bits", so "All bytes contain 8 bits.“ for ∀ x P(x) , it will also be true. Excellence and Service  CHRIST Deemed to be University 2. Universal Instantiation Universal elimination, used to add additional sentences many times. Any sentence P(c) can be inferred by substituting a ground term c (a constant within domain x) from ∀ x P(x) for any object in the universe of discourse IF "Every person like ice-cream"=> ∀x P(x) so we can infer that "John likes ice-cream" => P(c) Excellence and Service  CHRIST Deemed to be University 3. Existential Instantiation Also known as Existential Elimination is a legitimate FOL inference rule This rule states that for a new constant symbol c, one can deduce P(c) from the formula given in the form of ∃ x P(x) Only constraint is that ‘c’ must be a new word for which P(c) is true. From the given sentence: ∃x Crown(x) ∧ OnHead(x, John) we can infer: Crown(K) ∧ OnHead( K, John), as long as K does not appear in the knowledge base. Excellence and Service  CHRIST Deemed to be University 4. Existential Generalization This rule argues that if some element c in the universe of discourse has the property P, we can infer that something in the universe has the attribute P. "Priyanka got good marks in English.“ "Therefore, someone got good marks in English." Excellence and Service  CHRIST Deemed to be University Generalized Modus Ponens Rule "P implies Q, and P is declared to be true, hence Q must be true," summarizes Generalized Modus Ponens. Kings are evil, so we will find some x such that x is king, and x is greedy so we can infer that x is evil. Excellence and Service References Russell, S. and Norvig, P. (2014). Artificial Intelligence – A Modern Approach. 3rd Ed, India: Pearson Education Knowledge Engineering in First-order logic - Javatpoint