S6 AI 2022 NEW PDF - Artificial Intelligence Past Paper

 S6 BSc Computer Science CS1643: Artificial Intelligence MUSLIM ASSOCIATION COLLEGE OF ARTS AND SCIENCE Panavoor,Thiruvananthapuram,Kerala (Affiliated to the University of Kerala)...

 S6 BSc Computer Science CS1643: Artificial Intelligence MUSLIM ASSOCIATION COLLEGE OF ARTS AND SCIENCE Panavoor,Thiruvananthapuram,Kerala (Affiliated to the University of Kerala) Department of Computer Science CS1643: ARTIFICIAL INTELLIGENCE Name : ………………………………………………………………………………. Candidate Code :………………………………………………………………… [email protected] Page 1  S6 BSc Computer Science CS1643: Artificial Intelligence CS1643: ARTIFICIAL INTELLIGENCE SYLLABUS Module I: Overview of Artificial Intelligence: What is AI, The importance of AI; Knowledge: Introduction, Definition and Importance of knowledge, Knowledge–Based Systems, Representation of Knowledge, Knowledge Organization, Knowledge Manipulation, Acquisition of Knowledge. Module II: Formalized Symbolic Logics: Introduction, Syntax and Semantics for Propositional Logic and FOPL, Properties of Wffs, Conversion to Clausal Form, Inference Rules, The Resolution Principle; Structured Knowledge: Associative Networks, Frame Structures, Conceptual Dependencies and Scripts. Module III: Search and Control Strategies: Preliminary concepts, Examples of Search Problems, Uniformed or blind Search, Informed Search, Searching And-Or graphs; Matching Techniques: Introduction, Structures Used in Matching, Measures for Matching, Partial Matching, The RETE Matching Algorithm. Module IV: Natural Language Processing : Introduction, Overview of Linguistics, Grammars and Languages, Basic Parsing Techniques, Semantic Analysis and Representation Structures, Natural Language Generation, Natural Language Systems; Expert Systems : Introduction, Rule Based System Architecture, Knowledge Acquisition and Validation, Knowledge System Building Tools. [email protected] Page 2  S6 BSc Computer Science CS1643: Artificial Intelligence Module I Overview of Artificial Intelligence What is AI, The importance of AI; Knowledge: Introduction, Definition and Importance of knowledge, Knowledge–Based Systems, Representation of Knowledge, Knowledge Organization, Knowledge Manipulation, Acquisition of Knowledge. [email protected] Page 3  S6 BSc Computer Science CS1643: Artificial Intelligence What is Artificial Intelligence? Artificial Intelligence is composed of two words Artificial and Intelligence, where Artificial defines "man-made," and intelligence defines "thinking power", hence AI means "a man- made thinking power." Artificial Intelligence is a way of making a computer, a computer-controlled robot, or a software think intelligently, in the similar manner the intelligent humans think. According to John McCarthy (the father of Artificial Intelligence )AI is “The science and engineering of making intelligent machines, especially intelligent computer programs”. AI is accomplished by studying how human brain thinks, and how humans learn, decide, and work while trying to solve a problem, and then using the outcomes of this study as a basis of developing intelligent software and systems. Goals of AI 1. Following are the main goals of Artificial Intelligence: 2. Replicate human intelligence 3. Solve Knowledge-intensive tasks 4. An intelligent connection of perception and action 5. Building a machine which can perform tasks that requires human intelligence such as: Proving a theorem Playing chess Plan some surgical operation Driving a car in traffic 6. Creating some system which can exhibit intelligent behavior, learn new things by itself, demonstrate, explain, and can advise to its user. [email protected] Page 4  S6 BSc Computer Science CS1643: Artificial Intelligence Importance of AI With the help of AI, you can create such software or devices which can solve real-world problems very easily and with accuracy such as health issues, marketing, traffic issues, etc. With the help of AI, you can create your personal virtual Assistant, such as Cortana, Google Assistant, Siri, etc. With the help of AI, you can build such Robots which can work in an environment where survival of humans can be at risk. AI opens a path for other new technologies, new devices, and new Opportunities. Applications of Artificial Intelligence 1. AI in Healthcare o In the last, five to ten years, AI becoming more advantageous for the healthcare industry and going to have a significant impact on this industry. o Healthcare Industries are applying AI to make a better and faster diagnosis than humans. AI can help doctors with diagnoses and can inform when patients are worsening so that medical help can reach to the patient before hospitalization. 2. AI in Data Security o The security of data is crucial for every company and cyber-attacks are growing very rapidly in the digital world. o AI can be used to make your data more safe and secure. Some examples such as AEG bot, AI2 Platform,are used to determine software bug and cyber-attacks in a better way. 3. AI in Social Media o Social Media sites such as Facebook, Twitter, and Snapchat contain billions of user profiles, which need to be stored and managed in a very efficient way. o AI can organize and manage massive amounts of data. AI can analyze lots of data to identify the latest trends, hashtag, and requirement of different users. [email protected] Page 5  S6 BSc Computer Science CS1643: Artificial Intelligence 4. AI in Gaming o AI can be used for gaming purpose. The AI machines can play strategic games like chess, where the machine needs to think of a large number of possible places. 5. AI in Robotics: o Artificial Intelligence has a remarkable role in Robotics. o Usually, general robots are programmed such that they can perform some repetitive task, but with the help of AI, we can create intelligent robots which can perform tasks with their own experiences without pre-programmed. o Humanoid Robots are best examples for AI in robotics, recently the intelligent Humanoid robot named as Erica and Sophia has been developed which can talk and behave like humans. 6. AI in Entertainment We are currently using some AI based applications in our daily life with some entertainment services such as Netflix or Amazon. With the help of ML/AI algorithms, these services show the recommendations for programs or shows. 7. AI in E-commerce AI is providing a competitive edge to the e-commerce industry, and it is becoming more demanding in the e-commerce business. AI is helping shoppers to discover associated products with recommended size, color, or even brand. 8. AI in education: AI can automate grading so that the tutor can have more time to teach. AI chatbot can communicate with students as a teaching assistant. AI in the future can be work as a personal virtual tutor for students, which will be accessible easily at any time and any place. [email protected] Page 6  S6 BSc Computer Science CS1643: Artificial Intelligence Definition and importance of knowledge Intelligence requires knowledge. That is, to exhibit intelligence, knowledge is required. Knowledge plays a major role in building intelligent systems. Knowledge is the body of facts and principles. Knowledge can be language, concepts, procedures, rules, ideas, so on. Study of knowledge is called Epistemology. The meaning of knowledge is closely related to the meaning of intelligence Intelligent requires the identification and access to knowledge A common way to represent knowledge external to a computer or a human is in the form of written language. Example: Ramu is tall – This expresses a simple fact, an attribute possessed by a person Ramu loves his mother – This expresses a complex binary relation between two persons Types of Knowledge There are two types of knowledge 1.Procedural 2.Declarative 1.Procedural knowledge: It is compiled knowledge related to the performance of some task. For example, the steps used to solve an algebraic equation 2.Declarative knowledge: It is passive knowledge expressed as statements of facts about the world. For example, personnel data in a database, such data are explicit pieces of independent knowledge [email protected] Page 7  S6 BSc Computer Science CS1643: Artificial Intelligence Hypothesis Hypothesis is defined as a belief which is backed up with some supporting evidence, but it may still be false Belief is a meaningful and coherent expression. Thus belief may be true or false. Metaknowledge Metaknowledge is knowledge about knowledge, that is, knowledge about what we know Knowledge-Based System (KBS) A knowledge-based system (KBS) is a program that captures and uses knowledge from a variety of sources. A KBS assists with solving problems, particularly complex issues, by artificial intelligence. These systems are primarily used to support human decision making, learning, and other activities. A knowledge-based system is a major area of artificial intelligence. These systems can make decisions based on the data and information that resides in their database. A knowledge-based system is comprised of a knowledge base and an interface engine. The knowledge base functions as the knowledge repository, while the interface engine functions as the search engine. [email protected] Page 8  S6 BSc Computer Science CS1643: Artificial Intelligence What is knowledge representation? Humans are best at understanding, reasoning, and interpreting knowledge. Human knows things, which is knowledge and as per their knowledge they perform various actions in the real world. But how machines do all these things comes under knowledge representation and reasoning. Hence we can describe Knowledge representation as following: o Knowledge representation and reasoning (KR, KRR) is the part of Artificial intelligence which concerned with AI agents thinking and how thinking contributes to intelligent behavior of agents. o It is responsible for representing information about the real world so that a computer can understand and can utilize this knowledge to solve the complex real world problems such as diagnosis a medical condition or communicating with humans in natural language. o It is also a way which describes how we can represent knowledge in artificial intelligence. Knowledge representation is not just storing data into some database, but it also enables an intelligent machine to learn from that knowledge and experiences so that it can behave intelligently like a human.: Following are the kind of knowledge which needs to be represented in AI systems: o Object: All the facts about objects in our world domain. E.g., Guitars contains strings, trumpets are brass instruments. o Events: Events are the actions which occur in our world. o Performance: It describe behavior which involves knowledge about how to do things. o Meta-knowledge: It is knowledge about what we know. o Facts: Facts are the truths about the real world and what we represent. o Knowledge-Base: The central component of the knowledge-based agents is the knowledge base. It is represented as KB. The Knowledgebase is a group of the Sentences (Here, sentences are used as a technical term and not identical with the English language). Knowledge Organization / Types of Knowledge [email protected] Page 9  S6 BSc Computer Science CS1643: Artificial Intelligence The knowledge organization system provides a framework for the different classification of schemes used to organize knowledge. There are mainly four approaches to knowledge representation, which are given below: 1. Simple relational knowledge: 2. Inheritable knowledge: 3. Inferential knowledge: 4. Procedural knowledge: 1. Simple relational knowledge: o 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. o This approach of knowledge representation is famous in database systems where the relationship between different entities is represented. o This approach has little opportunity for inference. Example: The following is the simple relational knowledge representation. Player Weight Age Player1 65 23 Player2 58 18 Player3 75 24 2. Inheritable knowledge: o In the inheritable knowledge approach, all data must be stored into a hierarchy of classes. o All classes should be arranged in a generalized form or a hierarchal manner. o In this approach, we apply inheritance property. o Elements inherit values from other members of a class. o This approach contains inheritable knowledge which shows a relation between instance and class, and it is called instance relation. o Every individual frame can represent the collection of attributes and its value. o In this approach, objects and values are represented in Boxed nodes. [email protected] Page 10  S6 BSc Computer Science CS1643: Artificial Intelligence o We use Arrows which point from objects to their values. o Example: 3. Inferential knowledge: o Inferential knowledge approach represents knowledge in the form of formal logics. o This approach can be used to derive more facts. o It guaranteed correctness. o Example: Let's suppose there are two statements: a. Marcus is a man b. All men are mortal It can represent as; man(Marcus) ∀x = man (x) ----------> mortal (x)s 4. Procedural knowledge: o Procedural knowledge approach uses small programs and codes which describes how to do specific things, and how to proceed. o In this approach, one important rule is used which is If-Then rule. o In this knowledge, we can use various coding languages such as LISP language and Prolog language. [email protected] Page 11  S6 BSc Computer Science CS1643: Artificial Intelligence o We can easily represent heuristic or domain-specific knowledge using this approach. o But it is not necessary that we can represent all cases in this approach. Techniques of knowledge representation /Knowledge Manipulation There are mainly four ways of knowledge representation which are given as follows: 1. Logical Representation 2. Semantic Network Representation 3. Frame Representation 4. Production Rules [email protected] Page 12  S6 BSc Computer Science CS1643: Artificial Intelligence 1. Logical Representation Logical representation is a language with some concrete rules which deals with propositions. Logical representation means drawing a conclusion based on various conditions. This representation lays down some important communication rules. It consists of precisely defined syntax and semantics. Each sentence can be translated into logics using syntax and semantics. Syntax: o Syntaxes are the rules which decide how we can construct legal sentences in the logic. o It determines which symbol we can use in knowledge representation. o How to write those symbols. Semantics: o Semantics are the rules by which we can interpret the sentence in the logic. o Semantic also involves assigning a meaning to each sentence. Logical representation can be categorised into mainly two logics: a) Propositional Logics b) Predicate logics 2. Semantic Network Representation Semantic networks are alternative of predicate logic for knowledge representation. In Semantic networks, we can represent our knowledge in the form of graphical networks. This network consists of nodes representing objects and arcs which describe the relationship between those objects. Semantic networks can categorize the object in different forms and can also link those objects. Semantic networks are easy to understand and can be easily extended. This representation consist of mainly two types of relations: [email protected] Page 13  S6 BSc Computer Science CS1643: Artificial Intelligence a) IS-A relation (Inheritance) b) Kind-of-relation Example: Following are some statements which we need to represent in the form of nodes and arcs. Statements: a) Jerry is a cat. b) Jerry is a mammal c) Jerry is owned by Priya. d) Jerry is brown colored. e) All Mammals are animal. In the above diagram, we have represented the different type of knowledge in the form of nodes and arcs. Each object is connected with another object by some relation. 3. Frame Representation A frame is a record like structure which consists of a collection of attributes and its values to describe an entity in the world. Frames are the AI data structure which divides knowledge into substructures by representing stereotypes situations. It consists of a collection of slots and slot values. [email protected] Page 14  S6 BSc Computer Science CS1643: Artificial Intelligence These slots may be of any type and sizes. Slots have names and values which are called facets. Facets: The various aspects of a slot is known as Facets. Facets are features of frames which enable us to put constraints on the frames. Example: 1 Let's take an example of a frame for a book Slots Filters Title Artificial Intelligence Genre Computer Science Author Peter Norvig Edition Third Edition Year 1996 Page 1152 4. Production Rules Production rules system consist of (condition, action) pairs which mean, "If condition then action". It has mainly three parts: The set of production rules Working Memory The recognize-act-cycle In 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. This complete process is called a recognize-act cycle. [email protected] Page 15  S6 BSc Computer Science CS1643: Artificial Intelligence If there is a new situation (state) generates, then multiple production rules will be fired together, this is called conflict set. In this situation, the agent needs to select a rule from these sets, and it is called a conflict resolution. Example: o IF (at bus stop AND bus arrives) THEN action (get into the bus) o IF (on the bus AND paid AND empty seat) THEN action (sit down). Knowledge Acquisition Concept in Artificial Intelligence Knowledge Acquisition is the transformation of knowledge from the forms in which it exists into forms that can be used in a knowledge based system The primary goal discover, develop and implement efficient, effective method of knowledge acquisition It is a process of adding new knowledge to a knowledge base refining, improving previously acquire knowledge Acquisition is usually associated with some definite purpose such as expanding the capabilities of system, improving or enhancing the performance of some specific tasks Acquired knowledge consist of facts, rules, concept, procedure, formulas, relationship, stats, plans,heuristic or any relevant information The sources can be anyone of the following like-that , report, electronic document,database,newspaper,news channel,soft copy of document etc Three model of knowledge acquisition - 1. Handcrafting - means code knowledge is converted into program directly 2. Knowledge Engineering - means working with expert system to organise knowledge in a suitable form for an expert system to use. 3. Machine Learning - means to extract the knowledge from training examples *********************END of MODULE 1******************** [email protected] Page 16  S6 BSc Computer Science CS1643: Artificial Intelligence Module 2 Formalized Symbolic Logics Introduction, Syntax and Semantics for Propositional Logic and FOPL, Properties of Wffs, Conversion to Clausal Form, Inference Rules, The Resolution Principle; Structured Knowledge: Associative Networks, Frame Structures, Conceptual Dependencies and Scripts. [email protected] Page 17  S6 BSc Computer Science CS1643: Artificial Intelligence Formalized Symbolic Logics Symbolic AI Symbolic AI involves the explicit embedding of human knowledge and behavior rulesinto computer programs. Symbols are things we use to represent other things. Symbols play a vital role in the human thought and reasoning process. If I tell you that I saw a cat up in a tree, your mind will quickly conjure an image. Being able to communicate in symbols is one of the main things that make us intelligent. Therefore, symbols have also played a crucial role in the creation of artificial intelligence. We use symbols all the time to define things (cat, car, airplane, etc.) and people (teacher, police, salesperson). An example of symbolic AI tools is object-oriented programming. OOP languages allow you to define classes, specify their properties, and organize them in hierarchies. You can create instances of these classes (called objects) and manipulate their properties. Class instances can also perform actions, also known as functions, methods, or procedures. Each method executes a series of rule-based instructions that might read and change the properties of the current and other objects. Using OOP, you can create extensive and complex symbolic AI programs that perform various tasks. Symbolic artificial intelligence is very convenient for settings where the rules are very clear cut, and you can easily obtain input and transform it into symbols. [email protected] Page 18  S6 BSc Computer Science CS1643: Artificial Intelligence Propositional logic(PL) Propositional logic (PL) is the simplest form of logic where all the statements are made bypropositions. 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) The Sun rises from West (False proposition) b) 3+3= 7(False proposition) c) 5 is a prime number. Important features of PL 1. Symbols (to capture claims and logical connection between claims) 2. Syntax (the rules for how to take generate complex claims from simple ones) 3. Semantics (the meanings of the atomic units, and rules governing how meanings ofatomic units are put together to form complex meanings) [email protected] Page 19  S6 BSc Computer Science CS1643: Artificial Intelligence Syntax and Semantics of propositional logic The syntax of propositional logic defines the allowable sentences for the knowledge representation. There are two types of Propositions: 1. Atomic Propositions 2. Compound propositions 1. Atomic Proposition: Atomic propositions are the simple propositions. It consists of a single proposition symbol. These are the sentences which must be either true or false. Example: a) 2+2 is 4, it is an atomic proposition as it is a true fact. b) "The Sun is cold" is also a proposition as it is a false fact. 2. 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." Logical Connectives: Logical connectives are used to connect two simpler propositions or representing a sentence logically. We can create compound propositions 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 called a conjunction. Example: Rohan is intelligent and hardworking. It can be written as, [email protected] Page 20  S6 BSc Computer Science CS1643: Artificial Intelligence P= Rohan is intelligent, Q= Rohan is hardworking. → P𝖠 Q. 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 Doctor, 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. Following is the summarized table for Propositional Logic Connectives: Following are the truth table for all logical connectives: [email protected] Page 21  S6 BSc Computer Science CS1643: Artificial Intelligence [email protected] Page 22  S6 BSc Computer Science CS1643: Artificial Intelligence First-Order Logic in Artificial intelligence (FOPL) In propositional logic, we can only represent the facts, which are either true or false. PL is notsufficient to represent the complex sentences or natural language statements. The propositional logic has very limited expressive power. For overcoming this disadvantages we can useFirst-Order logic(FOPL) First-Order logic o First-order logic is another way of knowledge representation in artificial intelligence. It is an extension to propositional logic. o FOL is sufficiently expressive to represent the natural language statements in a better way. o First-order logic is also known as Predicate logic or First-order predicate logic. o First-order logic is a powerful language that develops information about the objects in a more easy way and can also express the relationship between those objects. o First-order logic consider the following o Objects: A, B, people, numbers, colors, wars, theories, squares, pits, wumpus, o Relations: It can be unary relation such as: red, round, is adjacent, or n-any relation such as: the sister of, brother of, has color, comes between o Function: Father of, best friend, third inning of, end of,...... [email protected] Page 23  S6 BSc Computer Science CS1643: Artificial Intelligence Syntax and Semantics of First-Order logic The syntax of FOL determines which collection of symbols is a logical expression in first-order logic. The basic syntactic elements of first-order logic are symbols. Following are the basic elements of FOL syntax: Constant 1, 2, A, John, Mumbai, cat,.... Variables x, y, z, a, b,.... Predicates Brother, Father, >,.... Function sqrt, LeftLegOf,.... Connectives 𝖠, ∨, ¬, ⇒, ⇔ Equality == Quantifier ∀, ∃ First-order logic statements can be divided into two parts: o Subject: Subject is the main part of the statement. o Predicate: A predicate can be defined as a relation, which binds two atoms together in a statement. Consider the statement: "x is an integer.", it consists of two parts, the first part x is the subject of the statement and second part "is an integer," is known as a predicate. [email protected] Page 24  S6 BSc Computer Science CS1643: Artificial Intelligence Quantifiers in First-order logic o A quantifier is a language element which generates quantification, and quantification specifies the quantity of specimen in the universe of discourse. o These are the symbols that permit to determine or identify the range and scope of the variable in the logical expression. There are two types of quantifier: a. Universal Quantifier, (for all, everyone, everything) b. Existential quantifier, (for some, at least one). a.Universal Quantifier: Universal quantifier is a symbol of logical representation, which specifies that the statement within its range is true for everything or every instance of a particular thing. The Universal quantifier is represented by a symbol ∀, which resembles an inverted A. Note: In universal quantifier we use implication "→". If x is a variable, then ∀x is read as: o For all x o For each x o For every x. Example: All man drink coffee. ∀x man(x) → drink (x, coffee). It will be read as: There are all x where x is a man who drink coffee. b) Existential Quantifier: Existential quantifiers are the type of quantifiers, which express that the statement within itsscope is true for at least one instance of something. It is denoted by the logical operator ∃, which resembles as inverted E. When it is used with a predicate variable then it is called as an existential quantifier. Note: In Existential quantifier we always use AND or Conjunction symbol (𝖠). [email protected] Page 25  S6 BSc Computer Science CS1643: Artificial Intelligence If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as: o There exists a 'x.' o For some 'x.' o For at least one 'x.' Example: Some boys are intelligent. ∃x: boys(x) 𝖠 intelligent(x) It will be read as: There are some x where x is a boy who is intelligent. Well-formed Formulas (WFFs) of Propositional Logic Propositional logic uses a symbolic “language” to represent the logical structure, or form, of a compound proposition. Like any language, this propositional logic has some rules for putting symbols together in the right way. Any expression that obeys the syntactic rules of propositional logic is called a well-formed formula, or WFF. Fortunately, the syntax of propositional logic is easy to learn. It has only three rules: Properties of WWf 1. Any capital letter by itself is a WFF. 2. Any WFF can be prefixed with “~”. (The result will be a WFF too.) 3. Any two WFFs can be put together with “ ”, “∨”, “⊃”, or “≡” between them, enclosing the result in parentheses. (This will be a WFF too.) [email protected] Page 26  S6 BSc Computer Science CS1643: Artificial Intelligence Here are some examples of well-formed formulas, along with brief explanations how these formulas are formed in accordance with the three rules of syntax: WFF explanation A by rule 1 ~A by rule 2, since A is a WFF ~~A by rule 2 again, since ~A is a WFF (~A B) by rule 3, joining ~A and B ((~A B) ⊃ ~~C) by rule 3, joining (~A B) and ~~C ~((~A B) ⊃ ~~C) by rule 2, since ((~A B) ⊃ ~~C) is a WFF In contrast, here are a few formulas that are not well-formed: non-WFF explanation A~ the ~ belongs on the left side of the negated proposition (A) parentheses are only introduced when joining two WFFs with , ∨, ⊃, or ≡ (A ) there’s no WFF on the right side of the (A B) ⊃ C) missing paranthesis on the left side [email protected] Page 27  S6 BSc Computer Science CS1643: Artificial Intelligence Converting a Sentence into Clausal Form Step I: Elimination of if-then operator: Replace”→” operator by ¬ & ∨operator. By replacing ‘if-then’ operator by negation and OR operator, we find. ᗄX (¬ (Child (X)𝖠 ⴺY (Takes (X, Y) 𝖠 Biscuit (Y))) ∨ Loves (john, X) Step II: Reduction of the scope of negation: Replace ¬ sign by choosing any of the following: In the present context, we rewrite the sentences as: Step III: Renaming the variable within the scope of quantifiers: Rename ⴺX by ⴺY when {ⴺX} is a subset/proper subset of {ᗄX}. In the present context, since X and Yare distinct, the above operation cannot be carried out. Step IV: Moving of quantifiers in the front of the expression: Bring all quantifiers at the front of the expression. Applying this on the example yields. Step V: Replacing existential quantifier as Skolem function of essential quantifiers: When an existential quantifier (Y) precedes an essential quantifier (X), replace Y as S (X), where S is the Skolem function. In this example, since Y is not a subset of X, such a situation does not arise. Also the essential quantifier is dropped from the sentence. Step VI: Putting the resulting expression in conjunctive normal form (CNF): For example, if the original expression is in the from P ∨ (Q 𝖠 R), then replace it by (P ∨ Q) 𝖠 (Q 𝖠 R). [email protected] Page 28  S6 BSc Computer Science CS1643: Artificial Intelligence In the present context, the resulting expression corresponding to expression (3) being in CNF, we need not do any operation at this step. Step VII: Writing one clause per line: If the original expression is of the following CNF, then rewrite each clause/line, as illustrated below. Original Expression: After writing one clause per line, the resulting expression become as follow: Inference Rule Inference rules are the templates for generating valid arguments. Inference rules are applied to derive proofs in artificial intelligence, and the proof is a sequence of the conclusion that leads to the desired goal. In inference rules, the implication among all the connectives plays an important role. Following are some terminologies related to inference rules: o Implication: It is one of the logical connectives which can be represented as P → Q. It is a Boolean expression. o Converse: The converse of implication, which means the right-hand side proposition goes to the left-hand side and vice-versa. It can be written as Q → P. o Contrapositive: The negation of converse is termed as contrapositive, and it can be represented as ¬ Q → ¬ P. o Inverse: The negation of implication is called inverse. It can be represented as ¬ P → ¬ [email protected] Page 29  S6 BSc Computer Science CS1643: Artificial Intelligence From the above term some of the compound statements are equivalent to each other, which we can prove using truth table: Hence from the above truth table, we can prove that P → Q is equivalent to ¬ Q → ¬ P, and Q→ P is equivalent to ¬ P → ¬ Q. Types of Inference rules: 1. Modus Ponens: The Modus Ponens rule is one of the most important rules of inference, and it states that if P and P → Q is true, then we can infer that Q will be true. It can be represented as: 2. Modus Tollens: The Modus Tollens rule state that if P→ Q is true and ¬ Q is true, then ¬ P will also true. It can be represented as: 3. Hypothetical Syllogism: The Hypothetical Syllogism rule state that if P→R is true whenever P→Q is true, and Q→R is true. It can be represented as the following notation: 4. Disjunctive Syllogism: The Disjunctive syllogism rule state that if P∨Q is true, and ¬P is true, then Q will be true. It can be represented as: [email protected] Page 30  S6 BSc Computer Science CS1643: Artificial Intelligence 5. Addition: The Addition rule is one the common inference rule, and it states that If P is true, then P∨Q will be true. 6. Simplification: The simplification rule state that if P𝖠 Q is true, then Q or P will also be true. It can be represented as: 7. Resolution: The Resolution rule state that if P∨Q and ¬ P𝖠R is true, then Q∨R will also be true. It can be represented as Resolution Principal Resolution method is an inference rule which is used in both Propositional as well as First-order Predicate Logic in different ways. This method is basically used for proving the satisfiability of a sentence. In resolution method, we use Proof by Refutation technique to prove the given statement. The key idea for the resolution method is to use the knowledge base and negated goal to obtain null clause (which indicates contradiction). Resolution method is also called Proof by Refutation. Since the knowledge base itself is consistent, the contradiction must be introduced by a negated goal. As a result, we have to conclude that the original goal is true. [email protected] Page 31  S6 BSc Computer Science CS1643: Artificial Intelligence In propositional logic, resolution method is the only inference rule which gives a new clause when two or more clauses are coupled together. Using propositional resolution, it becomes easy to make a theorem prover sound and complete for all. The process followed to convert the propositional logic into resolution method contains the below steps: 1. Convert the given axiom into clausal form, i.e., disjunction form. 2. Apply and proof the given goal using negation rule. 3. Use those literals which are needed to prove. 4. Solve the clauses together and achieve the goal. 1 Structured Knowledge Representation Structural knowledge is basic knowledge to problem-solving. It describes relationships between various concepts such as kind of, part of, and grouping of something. It describes the relationship that exists between concepts or objects. Properties of Good Knowledge Representation and Mapping 1. Mapping is the process that maps facts to representations and vice versa. 2. Forward mapping : facts to representation 3. Backward mapping : representation to facts [email protected] Page 32  S6 BSc Computer Science CS1643: Artificial Intelligence Associative Network Associative network means of representing relational knowledge as a labeled directed graph. Each vertex of the graph represents a concept and each label represents a relation between concepts. Access and updating procedures traverse and manipulate the graph. An associate memory network refers to a content addressable memory structure that associates a relationship between the set of input patterns and output patterns. Auto-Associative Network: An auto-associative network recovers a previously stored pattern that most closely relates to the current pattern. It is also known as an auto-associative correlator. Hetero-Associative Network: In a hetero-associate network, the recovered pattern is generally different from the input pattern not only in type and format but also in content. It is also known as a hetero- associative correlator. [email protected] Page 33  S6 BSc Computer Science CS1643: Artificial Intelligence Frame Structures A frame is a record like structure which consists of a collection of attributes and its values to describe an entity in the world. Frames are the AI data structure which divides knowledge into substructures by representing stereotypes situations. It consists of a collection of slots and slot values. These slots may be of any type and sizes. Slots have names and values which are called facets. Facets: The various aspects of a slot is known as Facets. Frames are derived from semantic networks and later evolved into our modern-day classes and objects. A single frame is not much useful. Frames system consist of a collection of frames which are connected. In the frame, knowledge about an object or event can be stored together in the knowledge base. The frame is a type of technology which is widely used in various applications including Natural language processing and machine visions. Example: 1 : Let's take an example of a frame for a book Slots Filters Title Artificial Intelligence Genre Computer Science Author Peter Norvig Edition Third Edition Year 1996 [email protected] Page 34  S6 BSc Computer Science CS1643: Artificial Intelligence Conceptual dependency (CD) Conceptual dependency (CD) is a theory of natural language processing which mainly deals with representation of semantics of a language. It techniques provide a useful formulation for representing more complex structures such as objects, scenes and multiple-sentence stories. One of the key ideas of the script approach is to reduce a sentence or story to a set of semantic primitives using a formalism called conceptual dependency (CD). Knowledge is represented in CD by elements what are called as conceptual structures. In order that knowledge is represented in CD form, certain primitive actions have been developed. The main motivation for the development of CD as a knowledge representation techniques are given below: 1. To construct computer programs which can understand natural language, 2. To make inferences from the statements and also to identify conditions in which two sentences can have similar meaning, 3. To provide facilities for the system to take part in dialogues and answer questions, 4. To provide a necessary plank that sentences in one language can be easily translated into other languages, and 5. To provide a means of representation which are language independent. Scripts A script is a structured representation describing a stereotyped sequence of events in a particular context. Scripts are used in natural language understanding systems to organize a knowledge base in terms of the situations that the system should understand. Scripts use a frame-like structure to represent the commonly occurring experience like going to the movies eating in a restaurant, shopping in a supermarket, or visiting an ophthalmologist. Thus, a script is a structure that prescribes a set of circumstances that could be expected to follow on from one another. [email protected] Page 35  S6 BSc Computer Science CS1643: Artificial Intelligence Scripts are beneficial because: Events tend to occur in known runs or patterns. A casual relationship between events exist. An entry condition exists which allows an event to take place. Prerequisites exist upon events taking place. Events tend to o Events tend to occur in known runs or patterns. Components of a script The components of a script include: Describing a script, special symbols of actions are used. These are: The components of a script include: 1. Entry condition: These are basic condition which must be fulfilled before events in the script can occur. 2. Results: Condition that will be true after events in script occurred. 3. Props: Slots representing objects involved in events 4. Roles: These are the actions that the individual participants perform. 5. Track: Variations on the script. Different tracks may share components of the same scripts. 6. Scenes: The sequence of events that occur. *************END OF MODULE 2*************** [email protected] Page 17 S6 BSc Computer Science CS1643: Artificial Intelligence Module III: Search and Control Strategies: Preliminary concepts, Examples of Search Problems, Uniformed or blind Search, Informed Search, Searching And-Or graphs; Matching Techniques: Introduction, Structures Used in Matching, Measures for Matching, Partial Matching, The RETE Matching Algorithm. [email protected] Page 37  S6 BSc Computer Science CS1643: Artificial Intelligence Search and Control Strategies Control Strategy in Artificial Intelligence scenario is a technique or strategy, tells us about which rule has to be applied next while searching for the solution of a problem within problem space. It helps us to decide which rule has to apply next without getting stuck at any point. These rules decide the way we approach the problem and how quickly it is solved and even whether a problem is finally solved. Control Strategy helps to find the solution when there is more than one rule or fewer rules for finding the solution at each point in problem space. Examples: Widely used Control Strategies are Breadth-First Search, Depth-First Search, Generate and Test, Hill-Climbing, Best-first search, Problem Reduction and many more. 1. Breadth-First Search: It searches along the breadth and follows first-in-first-out queue data structure approach. It will start to scan node A first and then B-C-D-E-F. 2. Depth-First Search: It searches along the depth and follows the stack approach. The sequence for scanning nodes will be A-B-D-E-C-F, it scans all the sub-nodes of parent nodes and then moves to another node. Uninformed Search Algorithms Uninformed search is a class of general-purpose search algorithms which operates in brute force-way. Uninformed search algorithms do not have additional information about state or search space other than how to traverse the tree, so it is also called blind search. Following are the various types of uninformed search algorithms: 1. Breadth-first Search 2. Depth-first Search 3. Depth-limited Search 4. Iterative deepening depth-first search 5. Uniform cost search 6. Bidirectional Search [email protected] Page 38 S6 BSc Computer Science CS1643: Artificial Intelligence Breadth-first Search Breadth-first search is the most common search strategy for traversing a tree or graph. This algorithm searches breadth wise in a tree or graph, so it is called breadth-first search. BFS algorithm starts searching from the root node of the tree and expands all successor node at the current level before moving to nodes of next level. The breadth-first search algorithm is an example of a general-graph search algorithm. Breadth-first search implemented using FIFO queue data structure. Example : Consider the following graph Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Insert it in a queue. Rule 2 − If no adjacent vertex found, remove the first vertex from queue. Rule 3 − Repeat Rule 1 and Rule 2 until queue is empty. [email protected] Page 39 S6 BSc Computer Science CS1643: Artificial Intelligence Step Traversal Description 1. Initialize the queue. 2. We start from visiting S (starting node), and mark it visited. 3. We then see unvisited adjacent node from S. In this example, we have three nodes but alphabetically we choose A mark it visited and enqueue it. [email protected] Page 40 S6 BSc Computer Science CS1643: Artificial Intelligence 4. Next unvisited adjacent node from S is B. We mark it visited and enqueue it. 5. Next unvisited adjacent node from S is C. We mark it visited and enqueue it. 6. Now S is left with no unvisited adjacent nodes. So we dequeue and find A. 7. From A we have D as unvisited adjacent node. We mark it visited and enqueue it. [email protected] Page 41 S6 BSc Computer Science CS1643: Artificial Intelligence At this stage we are left with no unmarked (unvisited) nodes. But as per algorithm we keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied the program is over. Depth-first Search Depth-first search isa recursive algorithm for traversing a tree or graph data structure. It is called the depth-first search because it starts from the root node and follows each path to its greatest depth node before moving to the next path. DFS uses a stack data structure for its implementation. The process of the DFS algorithm is similar to the BFS algorithm. Depth First Search algorithm(DFS) traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration. As in example given above, DFS algorithm traverses from A to B to C to D first then to E, then to F and lastly to G. It employs following rules. Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Push it in a stack. Rule 2 − If no adjacent vertex found, pop up a vertex from stack. (It will pop up all the vertices from the stack which do not have adjacent vertices.) Rule 3 − Repeat Rule 1 and Rule 2 until stack is empty. [email protected] Page 42 S6 BSc Computer Science CS1643: Artificial Intelligence Step Traversal Description 1. Initialize the stack 2. Mark S as visited and put it onto the stack. Explore any unvisited adjacent node from S. We have three nodes and we can pick any of them. For this example, we shall take the node in alphabetical order. 3. Mark A as visited and put it onto the stack. Explore any unvisited adjacent node from A. Both Sand D are adjacent to A but we are concerned for unvisited nodes only. [email protected] Page 43 S6 BSc Computer Science CS1643: Artificial Intelligence 4. Visit D and mark it visited and put onto the stack. Here we have B and C nodes which are adjacent to D and both are unvisited. But we shall again choose in alphabetical order. 5. We choose B, mark it visited and put onto stack. Here B does not have any unvisited adjacent node. So we pop B from the stack. 6. We check stack top for return to previous node and check if it has any unvisited nodes. Here, we find D to be on the top of stack. [email protected] Page 44 S6 BSc Computer Science CS1643: Artificial Intelligence 7. Only unvisited adjacent node is from D is C now. So we visit C, mark it visited and put it onto the stack. Informed Search Algorithms The informed search algorithm is more useful for large search space. Informed search algorithm uses the idea of heuristic, so it is also called Heuristic search. Heuristics function: Heuristic is a function which is used in Informed Search, and it finds the most promising path. It takes the current state of the agent as its input and produces the estimation of how close agent is from the goal. The heuristic method, however, might not always give the best solution, but it guaranteed to find a good solution in reasonable time. Heuristic function estimates how close a state is to the goal. It is represented by h(n), and it calculates the cost of an optimal path between the pair of states. The value of the heuristic function is always positive. Best-first Search Algorithm (Greedy Search): Greedy best-first search algorithm always selects the path which appears best at that moment. It is the combination of depth-first search and breadth-first search algorithms. It uses the heuristic function and search. Best-first search allows us to take the advantages of both algorithms. With the help of best-first search, at each step, we can choose the most promising node. In the best first search algorithm, we expand the node which is closest to the goal node and the closest cost is estimated by heuristic function, i.e. f(n)= g(n). [email protected] Page 45 S6 BSc Computer Science CS1643: Artificial Intelligence Were, h(n)= estimated cost from node n to the goal. The greedy best first algorithm is implemented by the priority queue. Best first search algorithm: Step 1: Place the starting node into the OPEN list. Step 2: If the OPEN list is empty, Stop and return failure. Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and places it in the CLOSED list. Step 4: Expand the node n, and generate the successors of node n. Step 5: Check each successor of node n, and find whether any node is a goal node or not. If any successor node is goal node, then return success and terminate the search, else proceed to Step 6. Step 6: For each successor node, algorithm checks for evaluation function f(n), and then check if the node has been in either OPEN or CLOSED list. If the node has not been in both list, then add it to the OPEN list. Step 7: Return to Step 2. A* Search Algorithm: A* search is the most commonly known form of best-first search. It uses heuristic function h(n), and cost to reach the node n from the start state g(n). It solve the problem efficiently. A* search algorithm finds the shortest path through the search space using the heuristic function. This search algorithm expands less search tree and provides optimal result faster. A* algorithm uses g(n)+h(n) instead of g(n). In A* search algorithm, we use search heuristic as well as the cost to reach the node. In A* search algorithm, we use search heuristic as well as the cost to reach the node. Hence we can combine both costs as following, and this sum is called as a fitness number. [email protected] Page 46 S6 BSc Computer Science CS1643: Artificial Intelligence Algorithm of A* search: Step1: Place the starting node in the OPEN list. Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and stops. Step 3: Select the node from the OPEN list which has the smallest value of evaluation function (g+h), if node n is goal node then return success and stop, otherwise Step 4: Expand node n and generate all of its successors, and put n into the closed list. For each successor n', check whether n' is already in the OPEN or CLOSED list, if not then compute evaluation function for n' and place into Open list. Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the back pointer which reflects the lowest g(n') value. Step 6: Return to Step 2. Example: In this example, we will traverse the given graph using the A* algorithm. The heuristic value of all states is given in the below table so we will calculate the f(n) of each state using the formula f(n)= g(n) + h(n), where g(n) is the cost to reach any node from start state. Here we will use OPEN and CLOSED list. [email protected] Page 47 S6 BSc Computer Science CS1643: Artificial Intelligence Solution: Initialization: {(S, 5)} [email protected] Page 48 S6 BSc Computer Science CS1643: Artificial Intelligence Iteration1: {(S--> A, 4), (S-->G, 10)} Iteration2: {(S--> A-->C, 4), (S--> A-->B, 7), (S-->G, 10)} Iteration3: {(S--> A-->C--->G, 6), (S--> A-->C--->D, 11), (S--> A-->B, 7), (S-->G, 10)} Iteration 4 will give the final result, as S--->A--->C--->G it provides the optimal path with cost 6. And-Or graph The AND-OR GRAPH (or tree) is useful for representing the solution of problems that can solved by decomposing them into a set of smaller problems, all of which must then be solved. This decomposition, or reduction, generates arcs that we call AND arcs. One AND arc may point to any number of successor nodes, all of which must be solved in order for the arc to point to a solution. Just as in an OR graph, several arcs may emerge from a single node, indicating a variety of ways in which the original problem might be solved. This is why the structure is called not simply an AND-graph but rather an AND-OR graph (which also happens to be an AND-OR tree) EXAMPLE FOR AND-OR GRAPH [email protected] Page 49 S6 BSc Computer Science CS1643: Artificial Intelligence Matching Techniques Matching is the process of comparing two or more structures to discover their likenesses or differences. The structures may represent a wide range of objects including physical entities, words or phrases in some language, complete classes of things, general concepts, relations between complex entities, and the like. The representations will be given in one or more of the formalisms like FOPL, networks, or some other scheme, and matching will involve comparing the component parts of such structures. Matching is used in a variety of programs for different reasons. It may serve to control the sequence of operations, to identify or classify objects, to determine the best of a number of different alternatives, or to retrieve items from a database. It is an essential operation such diverse programs as speech recognition, natural language understanding, vision, learning, automated reasoning, planning, automatic programming, and expert systems, as well as many others. In its simplest form, matching is just the process of comparing two structures or patterns for equality. The match fails if the patterns differ in any aspect. For example, a match between the two character strings acdebfba and acdebeba fails on an exact match since the strings differ in the sixth character positions. [email protected] Page 50 S6 BSc Computer Science CS1643: Artificial Intelligence Structures used in Matching The common structures include strings of characters a1 a2... ak , where the ai belong to given alphabet A, vector X = (x1 x2... xn), where the xi represents attribute values, matrices M (rows of vectors), general graphs, trees and sets The following are basic data structures used in matching 1.Variables The structures are constructed from basic atomic elements, numbers and characters Character string elements may represent either constants or variables 2.Graphs A graph is a collection of points called vertices, some of which are connected by line segments called edges A graph G = (V, E) is an ordered pair of sets V and E. An edge joints two distinct vertices in V 3.Tree A tree is a connected graph in which there are no cycles and each node has at most one parent below A node with no parent is called root node A node with no children is called leaf node 4.Sets A set is represented as an unordered list of unique elements such as the set (a d f c) or (red blue green yellow) 5.Bags A bag is a set which may contain more than one copy of the same member a, b, d and e Sets and bags are structures used in matching operations [email protected] Page 51 S6 BSc Computer Science CS1643: Artificial Intelligence Measures for Matching Matching can be done by the process called pattern recognition. Pattern is everything around in this digital world. A pattern can either be seen physically or it can be observed mathematically by applying algorithms. Example: The colors on the clothes, speech pattern, etc. What is Pattern Recognition? Pattern recognition is the process of recognizing patterns by using a machine learning algorithm. Pattern recognition can be defined as the classification of data based on knowledge already gained or on statistical information extracted from patterns and/or their representation. Pattern possesses the recognition following features: Pattern recognition system should recognize familiar patterns quickly and accurate Recognize and classify unfamiliar objects Accurately recognize shapes and objects from different angles Identify patterns and objects even when partly hidden Recognize patterns quickly with ease, and with automaticity. [email protected] Page 52 S6 BSc Computer Science CS1643: Artificial Intelligence RETE matching algorithm One potential problem with expert systems is the number of comparisons that need to be made between rules and facts in the database. In some cases, where there are hundreds or even thousands of rules, running comparisons against each rule can be impractical. The Rete Algorithm is an efficient method for solving this problem and is used by a number of expert system tools, including OPS5 and Eclipse. The Rete is a directed, acyclic, rooted graph The basic inference cycle of a production system is match, select and execute as indicated in Fig The operation in RATE algorithms are :- Match,Select and Execute 1.Match During the match portion of the cycle, the conditions in the LHS of the rules in the knowledge base are matched against the contents of working memory to determine which rules have their LHS conditions satisfied with consistent bindings to working memory terms. Rules which are found to be applicable are put in a conflict set 2.Select [email protected] Page 53 S6 BSc Computer Science CS1643: Artificial Intelligence From the conflict set, one of the rules is selected to execute. The selection strategy may depend on recency of useage, specificity of the rule or other criteria 3.Execute The rule selected from the conflict set is executed by carrying the action or conclusion part of the rule, the RHS of the rule. This may involve an I/O operation, adding, removing or changing clauses in working memory or simply causing a halt The above cycle is repeated until no rules are put in the conflict set or until a stopping condition is reached [email protected] Page 54  S6 BSc Computer Science CS1643: Artificial Intelligence Module IV Natural Language Processing Introduction, Overview of Linguistics, Grammars and Languages, Basic Parsing Techniques, Semantic Analysis and Representation Structures, Natural Language Generation, Natural Language Systems; Expert Systems : Introduction, Rule Based System Architecture, Knowledge Acquisition and Validation, Knowledge System Building Tools. [email protected] Page 55  S6 BSc Computer Science CS1643: Artificial Intelligence Natural Language Processing (NLP) Natural Language Processing (NLP) refers to AI method of communicating with an intelligent systems using a natural language such as English. Processing of Natural Language is required when you want an intelligent system like robot to perform as per your instructions, when you want to hear decision from a dialogue based clinical expert system, etc. The field of NLP involves making computers to perform useful tasks with the natural languages humans use. The input and output of an NLP system can be − 1. Speech 2. Written Text Components of NLP There are two components of NLP as given − 1. Natural Language Understanding (NLU) Understanding involves the following tasks − Mapping the given input in natural language into useful representations. Analyzing different aspects of the language. 2. Natural Language Generation (NLG) It is the process of producing meaningful phrases and sentences in the form of natural language from some internal representation. It involves − Text planning − It includes retrieving the relevant content from knowledge base. Sentence planning − It includes choosing required words, forming meaningful phrases, setting tone of the sentence. Text Realization − It is mapping sentence plan into sentence structure. [email protected] Page 56  S6 BSc Computer Science CS1643: Artificial Intelligence Steps in NLP There are general five steps − Lexical Analysis − It involves identifying and analyzing the structure of words. Lexicon of a language means the collection of words and phrases in a language. Lexical analysis is dividing the whole chunk of txt into paragraphs, sentences, and words. Syntactic Analysis (Parsing) − It involves analysis of words in the sentence for grammar and arranging words in a manner that shows the relationship among the words. The sentence such as “The school goes to boy” is rejected by English syntactic analyzer. Semantic Analysis − It draws the exact meaning or the dictionary meaning from the text. The text is checked for meaningfulness. It is done by mapping syntactic structures and objects in the task domain. The semantic analyzer disregards sentence such as “hot ice-cream”. Discourse Integration − The meaning of any sentence depends upon the meaning of the sentence just before it. In addition, it also brings about the meaning of immediately succeeding sentence. Pragmatic Analysis − During this, what was said is re-interpreted on what it actually meant. It involves deriving those aspects of language which require real world knowledge. [email protected] Page 57  S6 BSc Computer Science CS1643: Artificial Intelligence Overview of linguistics “Linguistics is the scientific study of language. It involves the analysis of language form, language meaning, and language in context. Linguists traditionally analyze human language by observing an interplay between sound and meaning. Traditionally it has been analyzing human language by observing an interplay between sound and meaning. It also deals with different factors that influence language, often: 1. Social. 2. Cultural. 3. Historical 4. Political Types of Linguistics 1. Historical and evolutionary linguistics: focuses on how languages change and grow over an extended period of time. 2. Semiotics: the study of direct and indirect language through signs and symbols. 3. Literary criticism: the historical and ideological analysis of literature, cinema, art, or published material. 4. Translation: the conversion and documentation of meaning in written/spoken text from one language or dialect onto another. 5. Speech-language pathology: a corrective method to cure phonetic disabilities and dis- functions at the cognitive level Grammars and Languages In the literary sense, grammars denote syntactical rules for conversation in natural languages. Linguistics have attempted to define grammars for processing and managing computer languages like any natural languages like English, Sanskrit, Mandarin, etc. The theory of formal languages finds its applicability extensively in the fields of Computer Science. Noam Chomsky gave a mathematical model of grammar in 1956 which is effective for writing computer languages. [email protected] Page 58  S6 BSc Computer Science CS1643: Artificial Intelligence A grammar G can be formally written as a 4-tuple (N, T, S, P) where − N or VN is a set of variables or non-terminal symbols. T or ∑ is a set of Terminal symbols. S is a special variable called the Start symbol, S ∈ N P is Production rules for Terminals and Non-terminals. A production rule has the form α → β, where α and β are strings on VN 𝖴 ∑ and least one symbol of α belongs to VN. Example Grammar G1 − ({S, A, B}, {a, b}, S, {S → AB, A → a, B → b}) Here, S, A, and B are Non-terminal symbols; a and b are Terminal symbols S is the Start symbol, S ∈ N Productions, P : S → AB, A → a, B → b Basic Parsing Techniques Parser is a compiler that is used to break the data into smaller elements coming from lexical analysis phase. A parser takes input in the form of sequence of tokens and produces output in the form of parse tree. Parsing is of two types: top down parsing and bottom up parsing. [email protected] Page 59  S6 BSc Computer Science CS1643: Artificial Intelligence 1. Top down paring o The top down parsing is known as recursive parsing or predictive parsing. o Bottom up parsing is used to construct a parse tree for an input string. o In the top down parsing, the parsing starts from the start symbol and transform it into the input symbol. Parse Tree representation of input string "acdb" is as follows: Bottom up parsing o Bottom up parsing is also known as shift-reduce parsing. o Bottom up parsing is used to construct a parse tree for an input string. o In the bottom up parsing, the parsing starts with the input symbol and construct the parse tree up to the start symbol by tracing out the rightmost derivations of string in reverse. [email protected] Page 60  S6 BSc Computer Science CS1643: Artificial Intelligence Semantic Analysis The purpose of semantic analysis is to draw exact meaning, or you can say dictionary meaning from the text. The work of semantic analyzer is to check the text for meaningfulness. The most important task of semantic analysis is to get the proper meaning of the sentence. For example, analyze the sentence “Ram is great.” In this sentence, the speaker is talking either about Lord Ram or about a person whose name is Ram. That is why the job, to get the proper meaning of the sentence, of semantic analyzer is important. semantic analysis can be divided into the following two parts − 1. Studying meaning of individual word It is the first part of the semantic analysis in which the study of the meaning of individual words is performed. This part is called lexical semantics. 2. Studying the combination of individual words In the second part, the individual words will be combined to provide meaning in sentences. Elements of Semantic Analysis Followings are some important elements of semantic analysis − Hyponymy :-It may be defined as the relationship between a generic term and instances of that generic term. Homonymy:-It may be defined as the words having same spelling or same form but having different and unrelated meaning. Polysemy:-Polysemy is a Greek word, which means “many signs”. It is a word or phrase with different but related sense. [email protected] Page 61  S6 BSc Computer Science CS1643: Artificial Intelligence Representation Structure Semantic analysis creates a representation of the meaning of a sentence. But before getting into the concept and approaches related to meaning representation, we need to understand the building blocks of semantic system. Building Blocks of Representation Structure 1. Entities − It represents the individual such as a particular person, location etc. For example, Haryana. India, Ram all are entities. 2. Concepts − It represents the general category of the individuals such as a person, city, etc. 3. Relations − It represents the relationship between entities and concept. For example, Ram is a person. 4. Predicates − It represents the verb structures. For example, semantic roles and case grammar are the examples of predicates. Natural Language Generation (NLG) Natural Language Generation (NLG) simply means producing text from computer data. It acts as a translator and converts the computerized data into natural language representation. In this, a conclusion or text is generated on the basis of collected data and input provided by the user. It is the natural language processing task of generating natural language from a machine representation system. The process to generate text can be as simple as keeping a list of readymade text that is copied and pasted. Example of a simple NLG system is the Pollen Forecast for Scotland system that could essentially be a template. NLG system takes as input six numbers, which predicts the pollen levels in different parts of Scotland. From these numbers, a short textual summary of pollen levels is generated by the system as its output. The typical stages of natural language generation are: Content determination: Deciding the main content to be represented in a sentence or the information to mention in the text. Document structuring: Deciding the structure or organization of the conveyed information. [email protected] Page 62  S6 BSc Computer Science CS1643: Artificial Intelligence Aggregation: Putting of similar sentences together to improve understanding and readability Lexical choice: Using appropriate words that convey the meaning clearly. Referring expression generation: Creating such referral expressions that help in identification of a particular object and region. Realisation: Creating and optimizing the text that should be correct as per the rules of grammar. There are three basic techniques for evaluating NLG systems: 1. Task-based evaluation: It includes human-based evaluation, who assess how well it helps him perform a task. For example, a system which generates summaries of medical data can be evaluated by giving these summaries to doctors and assessing whether the summaries help doctors make better decisions. 2. Human ratings: It assess the generated text on the basis of ratings given by a person on the quality and usefulness of the text. 3. Metrics: It compares generated texts to texts written by professionals. Natural Language Systems:-Expert Systems What are Expert Systems? The expert systems are the computer applications developed to solve complex problems in a particular domain, at the level of extra-ordinary human intelligence and expertise. Characteristics of Expert Systems High performance Understandable Reliable Highly responsive Capabilities of Expert Systems :-The expert systems are capable of − Advising Instructing and assisting human in decision making Demonstrating Deriving a solution Diagnosing [email protected] Page 63  S6 BSc Computer Science CS1643: Artificial Intelligence Explaining Interpreting input Predicting results Justifying the conclusion Suggesting alternative options to a problem Components of Expert Systems / Rule Based System Architecture The components of ES include − 1. Knowledge Base 2. Inference Engine 3. User Interface Let us see them one by one briefly − [email protected] Page 64  S6 BSc Computer Science CS1643: Artificial Intelligence 1. Knowledge Base It contains domain-specific and high-quality knowledge. Knowledge is required to exhibit intelligence. The success of any ES majorly depends upon the collection of highly accurate and precise knowledge. What is Knowledge? The data is collection of facts. The information is organized as data and facts about the task domain. Data, information, and past experience combined together are termed as knowledge. Components of Knowledge Base The knowledge base of an ES is a store of both, factual and heuristic knowledge.  Factual Knowledge − It is the information widely accepted by the Knowledge Engineers and scholars in the task domain. Heuristic Knowledge − It is about practice, accurate judgement, one’s ability of evaluation, and guessing. Knowledge Acquisition The success of any expert system majorly depends on the quality, completeness, and accuracy of the information stored in the knowledge base. The knowledge base is formed by readings from various experts, scholars, and the Knowledge Engineers. The knowledge engineer is a person with the qualities of empathy, quick learning, and case analyzing skills. He acquires information from subject expert by recording, interviewing, and observing him at work, etc. He then categorizes and organizes the information in a meaningful way, in the form of IF-THEN-ELSE rules, to be used by interference machine. The knowledge engineer also monitors the development of the ES. 2. Inference Engine Use of efficient procedures and rules by the Inference Engine is essential in deducting a correct, flawless solution. In case of knowledge-based ES, the Inference Engine acquires and manipulates the knowledge from the knowledge base to arrive at a particular solution. In case of rule based ES, it − Applies rules repeatedly to the facts, which are obtained from earlier rule application. Adds new knowledge into the knowledge base if required. [email protected] Page 65  S6 BSc Computer Science CS1643: Artificial Intelligence Resolves rules conflict when multiple rules are applicable to a particular case. To recommend a solution, the Inference Engine uses the following strategies − A. Forward Chaining B. Backward Chaining A. Forward Chaining It is a strategy of an expert system to answer the question, “What can happen next?” Here, the Inference Engine follows the chain of conditions and derivations and finally deduces the outcome. It considers all the facts and rules, and sorts them before concluding to a solution. This strategy is followed for working on conclusion, result, or effect. For example, prediction of share market status as an effect of changes in interest rates. B. Backward Chaining With this strategy, an expert system finds out the answer to the question, “Why this happened?” On the basis of what has already happened, the Inference Engine tries to find out which conditions could have happened in the past for this result. This strategy is followed for finding out cause or reason. For example, diagnosis of blood cancer in humans. [email protected] Page 66  S6 BSc Computer Science CS1643: Artificial Intelligence 3. User Interface User interface provides interaction between user of the ES and the ES itself. It is generally Natural Language Processing so as to be used by the user who is well-versed in the task domain. The user of the ES need not be necessarily an expert in Artificial Intelligence. It explains how the ES has arrived at a particular recommendation. The explanation may appear in the following forms − Natural language displayed on screen. Verbal narrations in natural language. Listing of rule numbers displayed on the screen. The user interface makes it easy to trace the credibility of the deductions. Knowledge System Building Tools Knowledge System Building Tools are programming systems which simplify the job of constructing an expert system. We divide expert system tools into four major categories as shown in Fig. [email protected] Page 67  S6 BSc Computer Science CS1643: Artificial Intelligence 1. Programming Languages: Most important programming languages used for expert system applications are generally either problem-oriented languages, such as FORTRAN and PASCAL, or symbol-manipulation languages, such as LISP and PROLOG. Problem oriented languages are designed for particular classes of problems; e.g., FORTRAN has convenient features for performing algebraic calculations Symbol-manipulation languages are designed for artificial intelligence applications; e.g., LISP 2. Knowledge Engineering Languages: A knowledge engineering language is a type of programming language designed to construct and debug expert system K.E. language provide certain faculties for building expert system; they are flexible than less programming languages with regard to how knowledge can be represented and manipulated. 3. System-Building Aids: The system-building aids consist of programs which help acquire and represent the domain expert’s knowledge and programs which help design the expert system under construction. These programs address very difficult tasks; many are research tools just beginning to evolve into practical and useful aids, although a few are offered as full-blown commercial systems 4. Tool Support Environment Facilities These are simply software packages which come with each tool to make it more user friendly and more efficient.It have four parts 1. Debugging Aids:To validate and evaluate programs based on the rule 2. Knowledge Base Editors:Updating the knowledge that ius already stored 3. I/O Facilities:To communicate with expert system 4. Explanation Facilities:Almost all expert systems can explain to users how they reach particular conclusions, though not all provide the same degree of software support for explanation. [email protected] Page 68