Intro AI sem1.pdf

1 Intro AI Notes By Parnika Btech Cse AI Chitkara University  2 Unit -1 Introduction to Artificial Intelligence What is Artificial Intelligence? A man-made thinking power. some people say that as per Greek myth...

1 Intro AI Notes By Parnika Btech Cse AI Chitkara University  2 Unit -1 Introduction to Artificial Intelligence What is Artificial Intelligence? A man-made thinking power. some people say that as per Greek myth, there were Mechanical men in the early days who can work and behave like humans Why Artificial Intelligence? create software or devices solve real-world problems Goals Of AI Create expert systems Improve problem solving skills Include knowledge representation Facilitate planning Promote creativity What comprises AI? Reasoning Learning Language understanding Application areas of AI 1. Astronomy : solving complex universe problems 2. Healthcare : faster diagnosis 3. Gaming : strategic gaming like chess 4. Finance : algorithm trading 5. Cyber security : Cyber attacks 6. Social Media : analyse data to find latest trends 7. Travel transport : AI chatbots for faster customer 2  3 help. 8. Automotive Industry: Self driven cars 9. Robotics : Humanoid robots 10. Entertainment : Recommendation service on netflix 11. Agriculture : IOT sensors 12.E commerce : recommendations 13.Education : AI tutors Importance Of AI Help humans to devoid hard tasks Manage the complex web Better decision making Better tools and services Make business prediction Advantages Of AI High accuracy High speed High reliability Useful for risky areas Daily applications Digital assistant Public Utility Available 24x7 New inventions Disadvantages Of AI High Cost Can’t think Out Of Box No feeling and emotions Increase dependency on machines No original creativity Unemployment 3  4 History Of AI 1. Maturation of AI (1943 - 1952) Artificial Neurons : 1943 Hebbian Learning (rule for modifying connection strength between neurons): 1949 Turing Test : 1950 2. Birth Of AI (1952-1956) Logic Theorist (1st AI program which could solve 38/52 mathematical problems) : 1955 AI was coined as an academic field : 1956 High level computer languages such as LISP were invented 3. Golden years - Early enthusiasm (1956 - 1974) First chatbot named ELIZA : 1966 Humanoid robot named WABOT 1 : 1972 4. First AI winter (1974 - 1980) Severe shortage from government for funding Decreased interest in publicity of AI 5. A Boom Of AI (1980 - 1987) Expert system with decision making ability : 1980 First National conference of American Association at Stanford : 1980 6. The second AI winter (1987-1993) Lack of investment fo XCON 7. The emergence of Intelligent Agents(1993-2011) IBM deep blue beats world chess champion:1997 Roomba , an AI vacuum cleaner : 2002 AI on FB, twitter : 2006 8. Deep Learning, Big Data etc (2011-present) IBM Watson’s won jeopardy, a quiz : 2011 Google Now : 2012 Eugene Goostman won turing test : 2014 Project Debater : 2018 Duplex : took a hairdresser appointment on calls and 4  5 the lady didn't recognize that it wasn't a human. Types Of AI AI Type 1 based on Capabilities 1. Weak AI or Narrow AI Most common Performs a dedicated task Only trained for one task Apple siri is a good eg IBM’s Watson supercomputer is good eg Eg : self driven cars, speech and image recognition 2. General AI Performs intelligent task like human Smarter and think like human Currently no such AI exists Still under research 3. Super AI Performs better tasks than humans Ability to think, puzzles etc Still a hypothetical concept 5  6 AI Type 2 : Based on functionality 1. Reactive Machines Purely reactive machines are most basic Do not store past experiences Only focus on current scenarios Eg : IBM’s Deep Blue System Eg : Google’s AlphaGo 2. Limited Memory Store past experiences for a short period of time Eg : self driven cars 3. Theory Of Mind Understands human emotions Still not developed 4. Self Awareness Have their on conscious and sentiments Smarter than human mind Hypothetical concept What is an Agent? An agent runs a cycle of perceiving ,thinking and acting. An agent can be ➔ Human Agent : it has eyes, ears and other organs 6  7 which work for sensors and hands , legs and vocal tracts work for actuators ➔ Robotic Agent : it has cameras, infrared range finder, NLP for sensors and various motors for actuators. ➔ Software Agent : can have keystrokes, file contents as sensory input and can act on those inputs and display output on screen. Sensors: An agent observes the environment through sensors. Actuators: Only responsible for moving and controlling the system. Effectors: affect the environment. Eg: display screens Intelligent Agents An autonomous entity that uses sensors and actuators for achieving goals for receiving goals and learning from the environment. For eg : thermostat Rule 1: must have the ability to perceive an environment Rule 2: the observation must be used to make decisions Rule 3 : decision should result in action Rule 4: must be a rational action Rational Agents Has clear preference,models uncertainty and acts in a way to maximise performance. It performs the right things Uses : game theory and decision theory AI reinforcement learning algorithm: for each best positive outcome the agent gets positive reward and for negative outcome the agent gets negative reward. 7  8 Rationality Rationality of an agent is measured by its performance measure. It is judged on the following points Performance measure which defines success criteria Agent prior knowledge of its environment Best possible actions that the agent can perform The sequence of percepts Structure of an AI Agent Agent = Architecture + Agent program Architecture : A machinery on which an AI agent executes Agent Function : Maps percept to an action Agent Program : executes physical architecture to function f PEAS Representation It is a type of model on which an AI agent works upon. P : Performance E : Environment A : Actuators S : Sensors Performance measure is objective of success of agent behaviour PEAS for self driving cars Performance : safety , time , comfort Environment : road , pedestrian , signals Actuators : steering , accelerator, brake Sensors : Camera , GPS, speedometer Example of Agents with their PEAS Representation 8  9 Agent Environment in AI Where the agent lives, operates and provides the agent with something to sense and act upon. Types of AI agent Agents can be grouped into five classes based on their degree of perceived intelligence and capability. Simple Reflex Agent Model-based reflex agent Goal-based agents Utility-based agent Learning agent 1. Simple Reflex Agent 9  10 Pros Most simple agents Based on the current perceptions Fully observable environment Not consider any parts of history condition - action rule Maps current state to action Cons very limited intelligence Do not have knowledge of non perceptual parts of the current state Too big to generate and to state Not adaptive to changes in environment 2. Model Based reflex agent 10  11 Partially observable environment Can track the situation It has two main factors: MODEL (how things happen in the world) and Internal State (current state based on percept history) Based on a model called knowledge of the world Updating the agent state requires about : How the world revolves AND How the agent affects the world Goal Based Agent Needs to know the goal Model based agent having goal information Choose an action to achieve a goal Searching and planning model 11  12 Utility Based Agent Utility measurement Not only goals but the best way to achieve the goals Perform the best action Function maps each state to a real number 12  13 Learning Agents past experiences or has learning capabilities. starts to act with basic knowledge and then can act and adapt automatically through learning. has mainly four conceptual components : Learning element(responsible for making improvements), Critic(takes feedback from critics), Performance element(takes external action) and Problem generator(suggesting actions) Learns, analyses performance and looks for new ways to improve performance. 13 14 14  15 Unit 2 Problem solving agents: Rational agents Use search technologies Goal based agent with atomic representations Search space , start state and goal state Search Algorithm Technologies 1. Searching : a step by step procedure to search in a given search space. Search space : set of possible solutions as graph/tree Nodes : state of problem 15  16 Edges : possible actions/ transitions between states Start state : beginning Goal test : tests the working of agent 2. Search Tree : A tree representation of search problem Root node is the initial state Leaf nodes : have no children / goal test Path : sequence of nodes from root to leaves 3. Actions : description of available actions to agents, allowable changes in state. An environment is the surrounding of an agent Applicability : not all actions are applicable in every state. Cost : use the minimal cost. Eg : chess game 4. Transition Model : description of what each action does. Eg : chess - Root node : current state 16  17 Child node : legal move Transition model : pieces move 5. Path cost : assigns numeric cost to each path 6. Solution : action sequence that goes from start node to goal node 7. Optimal solution : lowest cost among solutions Properties Of Search Algorithms Completeness : guarantees a solution for a random input Optimality : solution with lowest path cost Time complexity : measure of time taken Space complexity : maximum storage required Completeness and Optimality Optimality guarantees best possible solution Completeness guarantees existence of solution 1. Uninformed Search Algorithms 17  18 Operate in brute force way Blind search , as they have no other information about the state except traversing the tree Breadth First Search Traversing a tree or graph breadthwise Starts searching from root node Eg of general graph search algorithm FIFO queue structure Puts each vertex graph into 2 categories 1. Visiteds 2. Not visited Marks each vertex as visited while avoiding cycles WORKING OF ALGORITHM 1. Starts by putting any one of the graphs vertices to the end of the queue 18  19 2. Take the front items of the queue and add them to visited list (if not visited already) 3. Create a list of that vertex adjacent nodes, add ones which aren’t in the visited list to the back of the queue 4. Keep repeating steps 2 and 3 until the queue is empty 5. Print the list for the BFS travel 6. Make sure to cover each vertex , node even if it has disconnected ends BREADTH FIRST SEARCH PSEUDOCODE Create a Queue Q Mark v as visited and put v into Q While Q is non empty 1. Remove the head u of Q 2. Mark and enqueue all the univisited neighbours of u ADVANTAGES Provides any solution if solution exists Provides minimal solution with least number of steps if more than one solution exists DISADVANTAGES Lots of memory needed as each level of tree needs space Needs a lot of time 19  20 Space time complexity is EXAMPLES Snake ladder Chess Flood fill algorithm Shortest path in maze Count number of islands DEPTH FIRST SEARCH Recursive algorithm for traversing the graph or tree structure Starts from root node Follows each path to the greatest depth before the next node Uses stack data structure for its implementation Similar to BFS algorithm Puts each vertex into 2 categories : visited and unvisited WORKING OF THE DFS ALGORITHM 1. Puts any one of the graph’s vertex on top of stack 2. Take the top of item and add to the list (if not visited ) 3. Create a list of that vertex’s adjacent node. Add ones which aren’t in the list to the top of stack 4. Keep repeating step 2 and 3 until the stack is empty 5. Print DFS visited list 20  21 DEPTH FIRST SEARCH PSEUDOCODE ADVANTAGES Very little memory required as it only needs to store stack Takes less time than BFS (if traverses the right path) DISADVANTAGES No guarantee to find solution Sometimes goes into deep search DEPTH LIMITED SEARCH ALGORITHM Similar to depth first search with a predetermined limit the node at the depth limit will treat as it has no successor nodes further. 21  22 Depth-limited search can be terminated with two Conditions of failure: Standard failure value: It indicates that the problem does not have any solution. Cutoff failure value: It defines no solution for the problem within a given depth limit. Advantages : Memory efficient Disadvantages : incompleteness, doesn’t guarantee optimality Uniform Cost Search Algorithm search is a searching algorithm used for traversing a weighted tree or graph. algorithm comes into play when a different cost is available for each edge. 22  23 The primary goal of the uniform-cost search is to find a path to the goal node which has the lowest cumulative cost. Uniform-cost search expands nodes according to their path costs from the root node. It can be used to solve any graph/tree where the optimal cost is in demand. A uniform-cost search algorithm is implemented by the priority queue. It gives maximum priority to the lowest cumulative cost. Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the same. 23  24 Advantages : optimal solution with least cost at each state Disadvantages: algorithm may be stuck in infinite loop due to inconsiderate number of steps Iterative deepening depth-first Search finds out the best depth limit and does it by gradually increasing the limit until a goal is found. combines the benefits of Breadth-first search's fast search and depth-first search's memory efficiency. useful for uninformed search when search space is large, and the depth of goal node is unknown. Advantages : combines the benefits of BFS and DFS search algorithms in terms of fast search and memory efficiency. Disadvantages : it repeats all the work of the previous phase. 24  25 Bidirectional Search Algorithm runs two simultaneous searches, one from the initial state called forward-search and the other from the goal node called backward-search, to find the goal node. replaces one single search graph with two small subgraphs in which one starts the search from an initial vertex and the other starts from the goal vertex. The search stops when these two graphs intersect each other. can use search techniques such as BFS,DFS, etc. 25  26 Advantages: Fast, less memory Disadvantages: difficult implementation,one should know the goal state in advance. Informed Search Algorithms more useful for large search spaces. uses the idea of heuristic, so it is also called Heuristic search. Heuristics function: Heuristic is a function that 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 the agent is to the goal. Heuristic function estimates how close a state is to the goal. might not always give the best solution, but it guarantees to find a good solution in a reasonable time. A heuristic function helps the search algorithm choose a branch from the ones that are available. It helps with the decision process by using some extra knowledge about the search space. Eg: If you went to a supermarket with many check-out counters, you would try to go to the one with the least number of people waiting. This is a heuristic that reduces your wait time. 26  27 Heuristic Function 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. Here h(n) is heuristic cost, and h*(n) is the estimated cost. Pure Heuristic Search the simplest form of heuristic search algorithms. expands nodes based on their heuristic value h(n). maintains two lists, OPEN and CLOSED lists. In the CLOSED list, it places those nodes which have already expanded in the OPEN list, it places nodes that have yet not been expanded. On each iteration, each node n with the lowest heuristic value is expanded and generates all its successors, and n is placed to the closed list. The algorithm continues unit a goal state is found. In the informed search we will discuss two main algorithms which are given below: 1. Best First Search Algorithm (Greedy search) 2. A* Search Algorithm Best-first Search Algorithm (Greedy Search) 27  28 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. at each step, we can choose the most promising node. Implemented by the priority queue. we expand the node which is closest to the goal node, and the closest cost is estimated by heuristic function. To search the graph space, the BFS method uses two lists for tracking the traversal. An ‘Open’ list that keeps track of the current ‘immediate’ nodes available for traversal ‘CLOSED’ list that keeps track of the nodes already traversed. Estimate to Goal 28 29 29 30 30 31 31 32 32 33 33  34 A* Search Algorithm It uses the heuristic function h(n), and cost to reach the node n from the start state g(n). 34  35 has combined features of Uniform Cost Search (UCS) and greedy best-first search, by which it solve the problem efficiently. Finds shortest path through the search space using heuristic theorem Expands less search tree and provides optimal solution. similar to UCS except that it uses g(n)+h(n) instead of g(n). 35 36 36 37 37 38 38  39 Hill Climbing Theorem a local search algorithm that continuously moves in the direction of increasing elevation/value to find the peak of the mountain or best solution to the problem It terminates when it reaches a peak value where no neighbour has a higher value. Used for optimising mathematical problems Eg: Travelling salesman problem(we need to minimise the distance travelled by the salesman) Hill Climbing Algorithm 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49