Knowledge base and Algorithms.pptx

INTRODUCTION TO ARTIFICIAL Compiled by Nidhi Sharma INTELLIGENCE  KEY RESEARCH AREAS IN AI Problem solving, planning, and search --- generic problem solving  architecture based on ideas from cognitive science (game playing, robotics). Knowledge Repre...

INTRODUCTION TO ARTIFICIAL Compiled by Nidhi Sharma INTELLIGENCE  KEY RESEARCH AREAS IN AI Problem solving, planning, and search --- generic problem solving  architecture based on ideas from cognitive science (game playing, robotics). Knowledge Representation – to store and manipulate information (logical and probabilistic Automated reasoning / Inference – to use the stored information to answer questions and draw new conclusions Machine Learning – intelligence from data; to adapt to new circumstances and to detect and extrapolate patterns Natural Language Processing – to communicate with the machine Computer Vision --- processing visual information Robotics--- Autonomy, manipulation, full integration of AI capabilities  AI- BOOMING All of the tech giants such as Microsoft, Uber, Google, Facebook, Apple, Amazon, Oracle, Intel, IBM or Twitter are competing in the race to lead the market and acquire the most innovative and promising AI businesses.  KNOWLEDGE REPRESENTATION Is the process of encoding knowledge in a form that can be used by computational systems to solve complex problems, reason, and make decisions. It is a fundamental aspect of AI systems as it enables machines to understand, manipulate, and reason about the world. The main goals of knowledge representation in AI are: Expressivity: Representing knowledge in a language that captures the semantics and meaning of the concepts being modeled. This allows AI systems to reason effectively and make intelligent decisions. Efficiency: Representing knowledge in a way that allows for efficient storage, retrieval, and manipulation by computational systems. This includes optimizing data structures and algorithms for knowledge representation. Inference: Enabling AI systems to derive new knowledge from existing knowledge through logical reasoning, deduction, induction, and abduction. Integration: Integrating diverse forms of knowledge from different sources and domains into a unified representation framework. This includes integrating structured data, unstructured data, expert knowledge, and commonsense knowledge. Flexibility: Providing a flexible framework that can accommodate changes and updates to knowledge representations over time. This allows AI systems to adapt to new information, new  KNOWLEDGE REPRESENTATION What are the different ways that we can represent knowledge so it can be reviewed by an Artificial Intelligence computer program ? Logic-based Representations: Using formal logical languages such as predicate logic, propositional logic, and first-order logic to represent knowledge in a declarative and explicit manner. This includes techniques like production rules, inference engines, and theorem proving. Semantic Networks: Representing knowledge using a network structure where nodes represent concepts or entities, and edges represent relationships between them. Semantic networks are useful for representing hierarchical knowledge structures and semantic associations. Frames: Structuring knowledge using frames or schemas that represent objects as collections of attributes and values. Frames provide a structured way to represent complex entities, their properties, and relationships. Ontologies: Formalized representations of domain knowledge using a set of concepts, relationships, and axioms. Ontologies provide a shared vocabulary for describing entities and their interrelationships, facilitating interoperability and knowledge sharing between different systems. Probabilistic Models: Representing uncertain or probabilistic knowledge using probabilistic graphical 1. EXPERT SYSTEMS  EXPERT LEARNING SYSTEMS Expert Learning Systems were commercially the first and most successful domain in Artificial Intelligence. These programs mimic the experts in whatever field is being studied. Rule -based or Expert systems systems-Knowledge bases consisting of hundreds or thousands of rules of the form: IF (condition) THEN (action). Telephone networking Diagnostic internal medicine Cardiologist Delivery routing Weather forecasting Organic compounds computer configuration Professional auditor Battlefield tactician Mineral prospecting Engineering-Structural Manufacturing analysis Auto mechanic Space -station life support Infectious diseases-Pulmonary Audiologist function Civil law  EXPERT LEARNING SYSTEMS Use rules to store knowledge (“rule rule-based”). The rules are usually gathered from experts in the field being represented (“expert system”). Most widely used knowledge model in the commercial world. IF (it is raining AND you must go outside) THEN (put on your raincoat) Rules can fire off a chain of other rules IF (raincoat is on) THEN (you will not get wet) ACTIVITY Propose a ‘Field/Scenario/Problem’ where you want AI to be implemented. Design an Expert system for the scenario/problem in hand. Hint: -Keep the scenario simple and specific -Consider different aspect to it GARDNER EXPERT SYSTEM EXAMPLE GARDEN EXPERT SYSTEM Named abbreviations that Variables that are needed to represent the represent conclusions: state of the lawn NONE —apply no treatment at this time BARE—the lawn has large, bare TURF —apply a turf turf-building areas treatment SPARSE—the lawn is generally WEED —apply a weed weed-killing thin treatment BUG —apply a bug bug-killing treatment WEEDS—the lawn contains many weeds FEED —apply a basic fertilizer treatment WEED & FEED —apply a weed weed- BUGS—the lawn shows killing and fertilizer combination evidence of bugs treatment GARDEN Some Rules: EXPERT SYSTEM if (THECURRENT DAY–LAST DAYIS LESS THAN 30) then NONE if (SEASON= winter) then not BUGS Data that is available: if (BARE) then TURF if (SPARSEand not WEEDS) then FEED LAST—the date of the last lawn treatment if (BUGSand not SPARSE) then BUG CURRENT—current date if (WEEDSand not SPARSE) then WEED SEASON—the current season if (WEEDSand SPARSE) then WEED & FEED Now we can formulate some rules for our gardening expert system 2. SEMANTIC (WORD DESCRIPTION) NETWORKS SEMANTIC NETWORKS A knowledge representation technique that focuses on the relationships between objects A directed graph or word chart is used to represent a semantic network or net LET’S TRY OUT ONE! Cat mm Ma al F ly a l Eye Sc s es  AI often revolves around the use of algorithms SEARCH TREES An algorithm is a set of instructions that a mechanical computer can execute. SEARCH TREES A complex algorithm is often built on top of another, simpler, one and a common way to visualize it is with a tree design. TIC-TAC-TOE A simple example of an algorithm is the following recommendations for optimal play at tic-tac-toe: If someone has a "threat" (that is, two in a row), take the remaining square. Otherwise, If a move "forks" to create two threats at once, play that move. Otherwise, Take the center square if it is free. Otherwise, If your opponent has played in a corner, take the opposite corner. Otherwise, Take an empty corner if one exists. Otherwise, Take any empty square.  SEARCH TREES Searching is a step by step method to solve a search-problem in a specified search space. A search problem can have three main factors: oSearch Space oStart State oGoal test Properties of Search Algorithms- Completeness Optimality Time Complexity Space Complexity  TYPES OF SEARCH ALGORITHMS 1. Uninformed/Blind Search:- like Breadth-first search Depth-first search Depth-Limited search Uniform cost search Iterative deepening depth-first search Bidirectional Search Informed Search:- like Greedy Search A* Search  BREADTH-FIRST SEARCH BFS is the most common search for traversing a tree or graph. This algorithm searches breadthwise in a tree or graph, so it is called breadth-first search. In BFS search starts from root node and then before moving to next level all successor node from current level is expand. It is an example of a general-graph search algorithm. It uses queue data structure. DEPTH-FIRST SEARCH DEPTH-LIMITED SEARCH ALGORITHM [DFS + Predetermined limit] It can solve the problem of infinite path in the Depth-first search. The node at the depth limit will treat as it has no successor nodes further.  UNIFORM-COST SEARCH ALGORITHM In this algorithm at every state the path with the least cost is selected. INFORMED SEARCH ALGORITHMS The algorithms have information on the goal state, which helps in more efficient searching. This information is obtained by something called a heuristic. A heuristic is a function that estimates how close a state is to the goal state. Different heuristics are used in different informed algorithms BEST-FIRST SEARCH ALGORITHM (GREEDY SEARCH) In greedy search, we expand the node closest to the goal node. The “closeness” is estimated by a heuristic h(x). Heuristic: A heuristic h is defined as- h(x) = Estimate of distance of node x from the goal node. Lower the value of h(x), closer is the node from the goal. Strategy: Expand the node closest to the goal state, i.e. expand the node with a lower h value.  A* SEARCH ALGORITHM The algorithm utilizes a heuristic function to estimate the cost from the current node to the goal node, along with the actual cost from the start node to the current node. By considering both the actual cost and the estimated cost, A* search intelligently explores the graph to find the optimal path How the A* search algorithm works? Initialize two lists: an open list and a closed list. The open list contains the nodes to be explored, while the closed list contains the nodes that have been evaluated. Add the start node to the open list. While the open list is not empty, do the following steps: a. Select the node with the lowest f(n) value from the open list, where f(n) = g(n) + h(n). Here, g(n) is the cost from the start node to the current node, and h(n) is the heuristic value estimated from the current node to the goal node. b. If the selected node is the goal node, you have found the optimal path. Stop the search. c. Expand the selected node by generating its neighboring nodes. d. For each neighboring node, calculate its g(n) value (the cost from the start node to the neighboring node) and h(n) value (the estimated cost from the neighboring node to the goal node). e. If the neighboring node is already in the open list with a lower f(n) value, skip it. f. If the neighboring node is already in the closed list with a lower f(n) value, skip it. g. Otherwise, add the neighboring node to the open list and record its f(n) value, g(n) value, and parent node. h. Move the current node to the closed list. If the open list becomes empty and the goal node has not been found, there is no path from the start node to the goal node. The A* algorithm combines the actual cost of reaching the current node with the estimated cost of reaching the goal node. This allows it to make informed decisions during the search, exploring the most promising paths first. A* EXAMPLE  FORWARD AND BACKWARD CHAINING INFERENCE ENGINE The inference engine is the component of the intelligent system in artificial intelligence, which applies logical rules to the knowledge base to infer new information from known facts. The first inference engine was part of the expert system. Inference engine commonly proceeds in two modes, which are: Forward chaining Backward chaining PROLOG Prolog (short for Programming in Logic) is a high-level programming language associated with artificial intelligence and computational linguistics. It is one of the earliest logic programming languages, created in the early 1970s by Alain Colmerauer and Robert Kowalski. Declarative Paradigm Facts Rules Queries Backtracking Unification HORN CLAUSE AND DEFINITE CLAUSE Horn clause and definite clause are the forms of sentences, which enables knowledge base to use a more restricted and efficient inference algorithm. Logical inference algorithms use forward and backward chaining approaches, which require KB in the form of the first-order definite clause. HORN CLAUSE AND DEFINITE CLAUSE Definite clause: A clause which is a disjunction of literals with exactly one positive literal is known as a definite clause or strict horn clause. Horn clause: A clause which is a disjunction of literals with at most one positive literal is known as horn clause. Hence all the definite clauses are horn clauses. Example: (¬ p V ¬ q V k). It has only one positive literal k. It is equivalent to p ∧ q → k. Literal: A literal is an atomic formula or its negation. FORWARD CHAINING Forward chaining is also known as a forward deduction or forward reasoning method when using an inference engine. Forward chaining is a form of reasoning which start with atomic sentences in the knowledge base and applies inference rules (Modus Ponens) in the forward direction to extract more data until a goal is reached. The Forward-chaining algorithm starts from known facts, triggers all rules whose premises are satisfied, and add their conclusion to the known facts. This process repeats until the problem is solved.  FORWARD CHAINING: PROPERTIES It is a down-up approach, as it moves from bottom to top. It is a process of making a conclusion based on known facts or data, by starting from the initial state and reaches the goal state. Forward-chaining approach is also called as data driven as we reach to the goal using available data. Forward -chaining approach is commonly used in the expert system, such as CLIPS, business, and production rule systems. FORWARD CHAINING: EXAMPLE Let's say we have a rule-based system that determines whether a person is eligible for a discount based on their age and membership status. The rules are as follows: 1. If a person is a member, they are eligible for a discount. 2. If a person is not a member, but their age is 60 or above, they are eligible for a discount. 3. If none of the above conditions are met, the person is not eligible for a discount. FORWARD CHAINING: EXAMPLE Now, let's suppose we have the following information: 1. Person A is a member. 2. Person B is not a member and is 65 years old. 3. Person C is not a member and is 40 years old. We can use forward chaining to determine the eligibility for a discount for each person by applying the rules incrementally: FORWARD CHAINING: EXAMPLE 1.We start with an empty knowledge base. 6. We add the information that Person 2.We add the information that Person A is a C is not a member and is 40 years old member to the knowledge base. to the knowledge base. 3.We apply the rules to the knowledge base: 7. We apply the rules to the Rule 1: Person A is a member, so they are eligible for a discount. knowledge base: Rule 1: Person C is not a member, so this The knowledge base now contains the rule doesn't apply. information that Person A is eligible for a Rule 2: Person C is not a member, and their discount. age is not 60 or above, so this rule doesn't apply either. 4. We add the information that Person B is not a member and is 65 years old to the knowledge Rule 3: None of the previous rules apply, so base. Person C is not eligible for a discount. 5. We apply the rules to the knowledge base: The knowledge base remains Rule 1: Person B is not a member, so this rule unchanged. doesn't apply. Rule 2: Person B is not a member, but their age is At the end of this forward chaining 60 or above, so they are eligible for a discount. process, we have determined that The knowledge base now contains the Person A and Person B are eligible for information that Person A is eligible for a a discount, while Person C is not discount and Person B is eligible for a discount. eligible.  BACKWARD CHAINING Backward-chaining is also known as a backward deduction or backward reasoning method when using an inference engine. A backward chaining algorithm is a form of reasoning, which starts with the goal and works backward, chaining through rules to find known facts that support the goal. It is known as a top-down approach. Backward-chaining is based on modus ponens inference rule. In backward chaining, the goal is broken into sub-goal or subgoals to prove the facts true. Backward -chaining algorithm is used in game theory, automated theorem proving tools, inference engines, proof assistants, and various AI applications. BACKWARD CHAINING: EXAMPLE Suppose we have a rule-based system that determines whether a student is eligible for a scholarship based on their grades and extracurricular activities. The rules are as follows: 1. If a student's GPA is above 3.5, they are eligible for the scholarship. 2. If a student's GPA is below 3.5, but they have participated in a significant extracurricular activity, they are eligible for the scholarship. 3. If none of the above conditions are met, the student is not eligible for the scholarship. BACKWARD CHAINING: EXAMPLE Is Student A's GPA above 3.5? Yes, it is 3.7. Now, let's suppose we have the following information: Since the condition of the first rule is satisfied, we conclude that Student A is eligible for the Student A has a GPA of 3.7. scholarship. Student B has a GPA of 3.2 and has participated in 3. We examine the second rule: If a student's GPA is below 3.5, but they have participated in a significant a significant extracurricular activity. extracurricular activity, they are eligible for the scholarship. Student C has a GPA of 3.1 and has not participated Is Student B's GPA below 3.5? Yes, it is 3.2. in any significant extracurricular activity. Has Student B participated in a significant extracurricular activity? Yes, they have. We can use backward chaining to determine the eligibility for a scholarship for each student by starting with the goal Since both conditions of the second rule are (eligibility for a scholarship) and working backward to find satisfied, we conclude that Student B is eligible for the supporting facts: the scholarship. 4. We examine the third rule: If none of the above 1.We start with the goal of determining the eligibility conditions are met, the student is not eligible for the for a scholarship. scholarship. None of the previous rules apply to Student 2.We examine the first rule: If a student's GPA is C. above 3.5, they are eligible for the scholarship. Therefore, we conclude that Student C is not eligible for the scholarship.  GENETIC ALGORITHMS GENETIC ALGORITHMS Genetic Algorithms are the heuristic search and optimization techniques that mimic the process of natural evolution. “Select The Best, Discard The Rest” EXAMPLE Giraffes have long necks Giraffes with slightly longer necks could feed on leaves of higher branches when all lower ones had been eaten off. They had a better chance of survival. Favourable characteristic propagated through generations of giraffes. Now, evolved species has long necks This longer necks may have due to the effect of mutation initially. However as it was favorable, this was propagated over the generations.  Initial Population of animals Thus genetic Struggle For algorithms Existence implement Survival Of the the optimization Millio Fittest ns of strategies by Year simulating Surviving Individuals evolution of Reproduce, species Propagate Favourable through natural Characteristics selection Evolved Species SIMPLE GENETIC ALGORITHMS Start They are commonly used to generate Initialize high-quality solutions for optimization problems and search problems. Evaluate Solution T= Optimu m 0 No Solutio n Selection Yes T=T+1 Stop Crossover Mutation SIMPLE GENETIC ALGORITHMS function sga () { Initialize population; Calculate fitness function; While(fitness value != termination criteria) { Selection; Crossover; Mutation; Calculate fitness function; } } NATURE TO COMPUTER MAPPING Nature Computer Population Set of solutions Individual Solution to a problem Fitness Quality of a solution Chromosome Encoding for a solution Gene Part of the encoding solution GA OPERATORS AND PARAMETERS Selection The process that determines which solutions are to be preserved and allowed to reproduce and which ones deserve to die out. Select The primary objective of the selection operator is to emphasize the the good solutions and eliminate the bad solutions in a population while best, keeping the population size constant. discard the rest Crossove The most popular crossover selects any two solutions strings r randomly from the mating pool and some portion of the strings is exchanged between the strings. A probability of crossover is also introduced in order to give freedom to an individual Mutationstring solution is theto occasional introduction determine whether the ofsolution new features wouldin gotofor the Mutation solution strings crossover or not.of the population pool to maintain diversity in the population. Though crossover has the main responsibility to search for the optimal solution, mutation is also used for this purpose. SEARCH SPACE The population of individuals are maintained within search space. Each individual represents a solution in search space for given problem. Each individual is coded as a finite length vector (analogous to chromosome) of components. These variable components are analogous to Genes. Thus a chromosome (individual) is composed of several genes (variable components). BINARY- SELECTION, CROSS- OVER AND MUTATION SELECTION AND CROSS- OVER 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 Mutatio n ELITISM Crossover and mutation may destroy the best solution of the population pool Elitism is the preservation of few best solutions of the population pool Elitism only means that the most fit handful of individuals are guaranteed a place in the next generation - generally without undergoing mutation. Elitism is defined in percentage or in number APPLICATION OF GENETIC ALGORITHMS Genetic algorithms have many applications, some of them are – Recurrent Neural Network Mutation testing Code breaking Filtering and signal processing Learning fuzzy rule base etc