Unit-I Artificial IntelligencEGTRHe.pptx

SDFRGRHDHLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL

1. Artificial Intelligence BY: Hanamant Jakaraddi Department of Computer Applications Acharya Institute of Graduate Studies

2. Table of Content Introduction to Artificial Intelligence: Definitions AI Applications AI representation Properties of internal Representation Heuristic search techniques Best first search Depth first Search mean and end analysis A * and AO* Algorithm Game Playing Minimize search procedure Alpha beta cutoffs

3. Introduction to Artificial Intelligence Some Definitions AI is a technique that facilitates a machine to perform all cognitive functions such as perceiving, learning and reasoning that are otherwise performed by humans. “The Science and Engineering of making intelligent machines, especially intelligent Computer programs is Artificial intelligence” –JOHN MC CARTHY [Father of AI] 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. 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.

4. Continued… The exciting new effort to make computers think … machines with minds, in the full literal sense. The study of mental faculties through the use of computational models. A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes. The study of how to make computers do things at which, at the moment, people are better. It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence.

5. Continued… Artificial Intelligence (AI) is the machine-displayed intelligence that simulates human behavior or thinking and can be trained to solve specific problems. AI is a combination of Machine Learning techniques and Deep Learning. AI models that are trained using vast volumes of data have the ability to make intelligent decisions. Deep learning is an artificial intelligence (AI) function that imitates the workings of the human brain in processing data and creating patterns for use in decision making. Deep learning is a subset of machine learning. Modern AI focuses on the definition : “ engineering” approach success is judged by how well the agent performs .

6. AI Facts and Figures According to  Tractica , a market research firm, the Global AI Market is expected to reach a revenue of 118 billion by dollars by 2025. As per  Gartner , 37% of organizations have implemented AI in some form. The percentage of enterprises employing AI grew 270% over the past four years. According to  Servion Global Solutions , by 2025, 95% of customer interactions will be powered by AI. A recent 2020 report from  Statista  reveals that the global AI software market is expected to grow approximately 54% year-on-year and is expected to reach a forecast size of  22.6 billion U.S. dollars.  Let’s now take a look at how AI is used in different domains.

7. Different Types of AI Modeling exactly how humans actually think Modeling exactly how humans actually act Modeling how ideal agents “should think” Modeling how ideal agents “should act”

8. Artificial Intelligence Applications Gaming − AI plays crucial role in strategic games such as chess, poker, tic-tac-toe, etc., where machine can think of large number of possible positions based on heuristic knowledge. Natural Language Processing − It is possible to interact with the computer that understands natural language spoken by humans. Expert Systems − There are some applications which integrate machine, software, and special information to impart reasoning and advising. They provide explanation and advice to the users. Vision Systems − These systems understand, interpret, and comprehend visual input on the computer. A spying airplane takes photographs, which are used to figure out spatial information or map of the areas. Doctors use clinical expert system to diagnose the patient. Police use computer software that can recognize the face of criminal with the stored portrait made by forensic artist .

9. Continued… Speech Recognition − Some intelligent systems are capable of hearing and comprehending the language in terms of sentences and their meanings while a human talks to it. It can handle different accents, slang words, noise in the background, change in human’s noise due to cold, etc. Handwriting Recognition − The handwriting recognition software reads the text written on paper by a pen or on screen by a stylus. It can recognize the shapes of the letters and convert it into editable text. Intelligent Robots − Robots are able to perform the tasks given by a human. They have sensors to detect physical data from the real world such as light, heat, temperature, movement, sound, bump, and pressure. They have efficient processors, multiple sensors and huge memory, to exhibit intelligence. In addition, they are capable of learning from their mistakes and they can adapt to the new environment.

10. Artificial Intelligence Applications AI in E-Commerce AI in Finance AI in Business AI in Banking AI in Marketing AI in Social Media AI in Healthcare AI in Education AI in Law AI in Transportation AI in Automobiles AI in Manufacturing AI in Navigation AI in Robotics AI in Gaming

11. AI in E-commerce Personalized Shopping: Artificial Intelligence technology is used to create recommendation engines through which you can engage better with your customers. These recommendations are made in accordance with their browsing history, preference, and interests. It helps in improving your relationship with your customers and their loyalty towards your brand. AI-powered Assistants: Virtual shopping assistants and chatbots help improve the user experience while shopping online. Natural Language Processing is used to make the conversation sound as human and personal as possible. Moreover, these assistants can have real-time engagement with your customers. Did you know that on amazon.com, soon, customer service could be handled by chatbots? Fraud Prevention: Credit card frauds and fake reviews are two of the most significant issues that E-Commerce companies deal with. By considering the usage patterns, AI can help reduce the possibility of credit card frauds taking place. Many customers prefer to buy a product or service based on customer reviews. AI can help identify and handle fake reviews. 

12. AI in Finance AI in personal finance applications, such as Intuit Mint or TurboTax, is disrupting financial institutions. Applications such as these collect personal data and provide financial advice. Other programs, such as IBM Watson, have been applied to the process of buying a home. Today, artificial intelligence  software  performs much of the trading on Wall Street .

13. Machine learning algorithms are being integrated into analytics and customer relationship management ( CRM ) platforms to uncover information on how to better serve customers. Chatbots have been incorporated into websites to provide immediate service to customers. Automation of job positions has also become a talking point among academics and IT analysts. AI in Business

14. AI in Banking AI in banking .  Banks are successfully employing chatbots to make their customers aware of services and offerings and to handle transactions that don't require human intervention. AI virtual assistants are being used to improve and cut the costs of compliance with banking regulations. Banking organizations are also using AI to improve their decision-making for loans, and to set credit limits and identify investment opportunities .

15. Artificial intelligence applications are popular in the marketing domain as well. Using AI, marketers can deliver highly targeted and personalized ads with the help of behavioral analysis, pattern recognition, etc. It also helps with retargeting audiences at the right time to ensure better results and reduced feelings of distrust and annoyance. AI can help with content marketing in a way that matches the brand's style and voice. It can be used to handle routine tasks like performance, campaign reports, and much more.   Chatbots powered by AI, Natural Language Processing, Natural Language Generation, and Natural Language Understanding can analyze the user's language and respond in the ways humans do.  AI in Marketing

16. Instagram: On Instagram, AI considers your likes and the accounts you follow to determine what posts you are shown on your explore tab.  Facebook: Artificial Intelligence is also used along with a tool called DeepText . With this tool, Facebook can understand conversations better. It can be used to translate posts from different languages automatically. Twitter: AI is used by Twitter for fraud detection, removing propaganda, and hateful content . Twitter also uses AI to recommend tweets that users might enjoy, based on what type of tweets they engage with . AI in Social Media

17. AI is used in healthcare to build sophisticated machines that can detect diseases and identify cancer cells. AI can help analyze chronic conditions with lab and other medical data to ensure early diagnosis. AI uses the combination of historical data and medical intelligence for the discovery of new drugs . The biggest bets are on improving patient outcomes and reducing costs. Companies are applying machine learning to make better and faster diagnoses than humans. One of the best-known healthcare technologies is IBM Watson. It understands natural language and can respond to questions asked of it. The system mines patient data and other available data sources to form a hypothesis, which it then presents with a confidence scoring schema. Other AI applications include using online virtual health assistants and chatbots to help patients and healthcare customers find medical information, schedule appointments, understand the billing process and complete other administrative processes. An array of AI technologies is also being used to predict, fight and understand pandemics such as COVID-19. AI in Healthcare

18. AI in Education AI can automate grading, giving educators more time. It can assess students and adapt to their needs, helping them work at their own pace. AI tutors can provide additional support to students, ensuring they stay on track. And it could change where and how students learn, perhaps even replacing some teachers.

19. AI in Law AI in law .  The discovery process -- sifting through documents -- in law is often overwhelming for humans. Using AI to help automate the legal industry's labor-intensive processes is saving time and improving client service. Law firms are using machine learning to describe data and predict outcomes, computer vision to classify and extract information from documents and natural language processing to interpret requests for information .

20. AI in Transportation AI in transportation .  In addition to AI's fundamental role in operating autonomous vehicles, AI technologies are used in transportation to manage traffic, predict flight delays, and make ocean shipping safer and more efficient .

21. Artificial Intelligence is used to build self-driving vehicles. AI can be used along with the vehicle’s camera, radar, cloud services, GPS, and control signals to operate the vehicle. AI can improve the in-vehicle experience and provide additional systems like emergency braking, blind-spot monitoring, and driver-assist steering. AI in Automobiles

22. AI in Manufacturing AI in manufacturing .  Manufacturing has been at the forefront of incorporating robots into the  workflow . For example, the industrial robots that were at one time programmed to perform single tasks and separated from human workers, increasingly function as  cobots : Smaller, multitasking robots that collaborate with humans and take on responsibility for more parts of the job in warehouses, factory floors and other workspaces .

23. Based on research from  MIT , GPS technology can provide users with accurate, timely, and detailed information to improve safety. The technology uses a combination of Convolutional Neural Network and Graph Neural Network, which makes lives easier for users by automatically detecting the number of lanes and road types behind obstructions on the roads. AI is heavily used by Uber and many logistics companies to improve operational efficiency, analyze road traffic, and optimize routes. AI in Navigation

24. Robotics is another field where artificial intelligence applications are commonly used. Robots powered by AI use real-time updates to sense obstacles in its path and pre-plan its journey instantly.  It can be used for – Carrying goods in hospitals, factories, and warehouses Cleaning offices and large equipment Inventory management AI in Robotics

25. Another sector where Artificial Intelligence applications have found prominence is the gaming sector. AI can be used to create smart, human-like NPCs to interact with the players. It can also be used to predict human behavior using which game design and testing can be improved. The Alien Isolation games released in 2014 uses AI to stalk the player throughout the game. The game uses two Artificial Intelligence systems - ‘Director AI’ that frequently knows your location and the ‘Alien AI,’ driven by sensors and behaviors that continuously hunt the player. AI in Gaming

26. Knowledge Representation in AI describes the representation of knowledge. Basically, it is a study of how the beliefs, intentions, and judgments of an intelligent agent can be expressed suitably for automated reasoning. Logical representation is a language with some concrete rules which deals with propositions and has no ambiguity in representation. Logical representation  means drawing a conclusion based on various conditions. Importance of representation: 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 . AI Representation

27. Primarily, we see five types of knowledge in any knowledge representation block in AI systems. The knowledge types are as follows: Declarative : It is the type of knowledge that deals with facts, instances, objects, declared as a statement. Structural : It deals with the type of knowledge that describes the relationship between instances and description.  Procedural : It deals with the procedures and rules required for a particular system to work efficiently.  Meta : It is the knowledge consisting of the higher-level data of other types of knowledge data. Heuristic : It represents the data that helps in governing decisions.  Types of Knowledge

28. As search engines are made up of codes, natural language processing technology helps these applications to understand humans. In fact, they are also able to predict what a human wants to ask by compiling top-ranked searches and predicting their queries when they start to type. New features such as voice search and image search are also constantly being programmed into machines. If you want to find a song that is playing at a mall, you can simply hold your phone up to it, and a music-identifying app will tell you what it is within seconds. Searching Algorithms

29. Based on the search problems we can classify the search algorithm into: Uninformed search (Blind search) informed search (Heuristic search) Uninformed / Blind Search Informed search Breadth first search Uniform cost search Depth first search Depth limited search Iterative Deeping depth first search Best first search A* search AO* algorithm Problem reduction Hill climbing Types of Search Algorithm Search Algorithm

30. A problem determines the graph and the goal but not which path to select from the frontier. A search strategy specifies which paths are selected from the frontier. Different strategies are obtained by modifying how the selection of paths in the frontier is implemented . Breadth first Depth first Iterative deepening Uninformed Search Strategies

31. Breadth-first search completes one level before moving on to next level Has to keep in memory all the competing paths that aspire to be extended to a goal node A possible representation of candidate paths: list of lists Easiest to store paths in reverse order; then , to extend a path, add a node as new head (easier than adding a node at end of list) Breadth first Search algorithm

32. Breadth first Search algorithm

33. Breadth first Search algorithm

34. Breadth first Search algorithm

35. Breadth first Search algorithm

36. Is not guaranteed to find shortest solution first Susceptible to infinite loops (should check for cycles) Has low space complexity: only proportional to depth of search Only requires memory to store the current path from start to the current node When moving to alternative path, previously searched paths can be forgotten Properties of Breadth first Search algorithm

37. Depth first Search algorithm

38. Depth first Search algorithm

39. Depth first Search algorithm

40. Depth first Search algorithm

41. Depth first Search algorithm

42. Depth first Search algorithm

43. Depth first Search algorithm

44. Depth first Search algorithm

45. Iterative deepening combines the benefits of depth-first and breadth-first search. In general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known. The iterative deepening search algorithm, which repeatedly applies depth- limited search with increasing limits. It terminates when a solution is found or if the depth- limited search returns failure, meaning that no solution exists. Iterative Deepening

46. For simpler analysis consider state-space as a tree Uniform branching b Solution at depth d n Number of nodes at level n :   Complexity of basic seach methods

47. Completeness: is the algorithm guaranteed to find a solution when there is one? Optimality: Does the strategy find the optimal solution? Time: How long does it take to find a solution? Space: How much memory is needed to perform the search ? Complexity A nalysis

48. Time and Space Complexity orders

49. Time: number of nodes generated Space: maximum number of nodes stored in memory Branching factor: b Maximum number of successors of any node Depth: d Depth of shallowest goal node Path length: m Maximum length of any path in the state space Cost Variables

50. Uninformed /Blind search(Brute force way): The uninformed search does not contain any domain knowledge such as closeness ,the location of the goal. It operates in a brute force way, as it only includes information about how to traverse the tree and how to identify leaf and goal nodes . Uninformed search applies a way in which search tree is searched without any information about the search space like initial state operatores & test for goal ,so it is called blind search it examines each node until it reach the goal node .

51. Informed search : It uses domain knowledge the problem informed is available which can guide the search Informed search strategies can find a solution more efficient than an uninformed informed search is also called as Heuristic search A heuristic is a way which might not always be guarantees for the best soln but guaranteed to find a good soln in reasonable time . It cab solve much complex problem which could not be solved in another way.

52. Heuristic Search Techniques and Function Heuristic Search ( Informed) : The purpose of heuristic function is to guide the search process in the most profitable path among all that are available . Heuristic search  is defined as a procedure of search that endeavors to upgrade an issue by iteratively improving the arrangement dependent on a given heuristic capacity or a cost measure. *This technique doesn’t generally ensure to locate an ideal or the best arrangement, however, it may rather locate a decent or worthy arrangement inside a sensible measure of time and memory space. *This is a sort of an alternate route as we regularly exchange one of optimality, culmination, exactness, or accuracy for speed. *It may be a function which is employed in Informed Search, and it finds the foremost promising path. It takes the present state of the agent as its input and produces the estimation of how close agent is from the goal.

53. BEST FIRST SEARCH(informed search): Best first search Algorithm(Greedy Search) It always selects the path which appears best at that moment. It is combination of DFS & BFS It uses the heuristitc function h(n)<=h*(n) and search h(n)=heuristic cost h*(n)=estimated cost The greedy best first alg is implemented by priority queue

54. Best Search Algorithm: Step1 : Place the starting node into the open list . Step2 : If the open list is empty ,stop and return failure. Step3 : Remove the node n, from the open list which has lowest value of h(n) and place it in the closed list Step4 : Expand the node n, and generate the successors of node n. Step5 :Check each successor of node n and find whether any node is a goal node , then return success and terminate the search . Step6 : for each successor node ,algorithm checks for evaluation function F(n) & 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 OPEN list . Step5 : Return to step 2.

55. Best first search algorithm example :

56. Advantages and Disadvantages of Best First Search: Advantage: Best first search can switch between BFS & DFS by gaining the advantages of both the algorithm. This algorithm is more efficient than BFS & DFS algorithm Disadvantage: It can behave as an unguided depth first search in the worst case . It can get stuck in a loop as DFS. This algorithm is not optimal.

57. Means-Ends Analysis Means –Ends Analysis is problem –solving techniques used in Artificial intelligence for limiting search in AI programs It is a mixture of Backward and Forward search technique. The MEA analysis process centred on the evaluation of the difference between the current state and goal state.

58. How means-ends analysis Works The means –end analysis process can be applied recursively for a problem. It is a strategy to control search in problem –solving. Following are the main steps which describes the working of MEA technique. Frist evalute the difference between intial state and final state . Select the various operators which can be applied for each difference Apply the operator at each difference ,which reduces the difference between the current state and goal state .

59. Operator Sub goaling: In the MEA process , we detect the differences between the current state and goal state . Once this occur ,then we can apply an operator to reduce the differences But sometimes it is possible that an operator cannot be applied to the current state. So we create the subproblem of the current state , in which operator can be applied , such type of backward chaining in which operators are selected , and then sub goals are set up to establish the preconditions of the operator is called operator sub goaling

60. Example of Means-Ends Analysis: Initial State Goal state

61. Evaluating the initial state *In the first step,we will evalute the initial state and will compare the initial and goal state to find the differences between both states. Applying Delete operator: First we will apply the Delete operator to remove this dot .

62. Applying move operator: The new state occurs which we will again compare with goal state after comparing these states there is another difference that is the square is outside the circle ,so we will apply the move operator.

63. Applying Expand Operator : We will compare this state with the goal state, there is still one difference in size of the square so we will apply Expand operator. finally ,it will generate the goal state . Goal state

64. A* Search Algorithm: A* search algorithm finds the shortest path through the search space using the heuristic function. It uses h(n), & cost to reach the node n from the start state g(n). This algorithm expands less search tree and provides optimal result faster. It is similar to UCS(uniform cost search)except that it uses g(n)+h(n) instead of g(n). In uniform cost search we only use the g(n). A* use search heuristic as well as the cost to reach the node hence we combine both costs as, F(n)=g(n)+h(n) {fitness numbers} F(n)=Estimated cost of the cheapest solution g(n)=cost to reach node n from start state h(n)=cost to reach from node n to goal node .

65. Algorithm of A* Search: Step1: place the starting node in OPEN list . Step2: check if the OPEN list is empty or not, if the lists empty the return failure & stops. Step3: Select the node from the OPEN list which has the small value of evaluation function (g+h),if node n is goal node then return success & stop ,otherwise. Step4: Expand node n& generate all of its successors , & put n in 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 in the OPEN list. Step5: Else if node ‘n’ is already in OPEN & CLOSED , then it should be attached to the back pointer which reflects the lowest g(n) value . Step 6: Return to step 2.

66. Advantages : It is best algorithm than other search algorithm. It is optimal & complete. It can solve very complex problems. Disadvantages: It does not always produce shortest path. It is not practical for various large – scale problems.

67. A* search Algorithm example:

68. AO* Search Algorithm: AO* Algorithm basically based on  problem decomposition (Breakdown problem into small pieces) When a problem can be divided into a set of sub problems, where each sub problem can be solved separately and a combination of these will be a solution,  AND-OR graphs  or  AND - OR trees  are used for representing the solution. 

69. Scope of AI *Theorem Proving *Game playing *Natural language process Speech processing Computer vision Robotics Expert system

70. Game Playing: Game playing is a search problem defined by, Initial States, Successor function Goal test Path cost/utility/pay off function. AI has continued to improve , with aims set on a player being unable to tell the difference between computer and human player. A game must “Feel” natural Obeys law of the game Characters aware of the environment Path finding (A* algorithm) Decision making planning

71. The game AI is about the illusion of human behaviour: Smart too a certain extent Non –repeating behaviour Emotional influences (irrationality, "personality”) Body language to communicate emotions Being integrated in the environment Game AI needs various computer science disciplines Knowledge based systems Machine learning Multi agent systems Computer graphics and animation Data structures

72. Game Tree : Mini Max Algorithm Alpha – Beta Pruning

73. Mini Max Algorithm: Back tracking algorithm Best move strategy used Max will try to maximize its utility(best move) Min will try to minimize utility(worst move)

74. Example:

75. Time complexity:

76. The above category of games can be represented as a tree where the nodes represent the current state of the game and the arcs represent the moves. For Example : Game of Tic- Tac -Toe

77. Alpha-Beta Pruning ALPHA-BETA pruning is a method that reduces the number of nodes explored in Minimax strategy. Cut off search by exploring less no of nodes. It reduces the time required for the search and it must be restricted so that no time is to be wasted searching moves that are obviously bad for the current player. The exact implementation of alpha-beta keeps track of the best move for each side as it moves throughout the tree.

78. Example:

79. The efficiency of the Alpha-Beta procedure depends on the order in which successors of a node are examined. If we were lucky, at a MIN node we would always consider the nodes in order from low to high score and at a MAX node the nodes in order from high to low score. In general it can be shown that in the most favorable circumstances the alpha-beta search opens as many leaves as minimax on a game tree with double its depth.

80. The algorithm maintains two values, alpha and beta, which represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. Initially alpha is negative infinity and beta is positive infinity. As the recursion progresses the "window" becomes smaller. When beta becomes less than alpha, it means that the current position cannot be the result of best play by both players and hence need not be explored further.

81. Quiescence Search Quiescence search  is an algorithm typically used to evaluate minimax game trees in game-playing computer programs.  It is a remedy for the horizon problem  faced by AI engines for various games like chess and Go The  Horizon Effect  is caused by the depth limitation of the search algorithm, and became manifest when some negative event is inevitable but postponable. Because only a partial game tree has been analyzed, it will appear to the system that the event can be avoided when in fact this is not the case

82. This problem occurs because computers only search a certain number of moves ahead. Human players usually have enough intuition to decide whether to abandon a bad-looking move, or search a promising move to a great depth. A quiescence search attempts to emulate this behavior by instructing a computer to search "interesting" positions to a greater depth than "quiet" ones (hence its name) to make sure there are no hidden traps and, usually equivalently, to get a better estimate of its value.

83. As the main motive of quiescence search is usually to get a good value out of a poor evaluation function, it may also make sense to detect wide fluctuations in values returned by a simple heuristic evaluator over several ply. 

84. Secondary Search One proposed solution is to examine the search space beyond the apparently best move to see if something is looming just over the horizon. In that case we can revert to the second-best move. Obviously then the second-best move has the same problem, and there isn't time to search beyond all possible acceptable moves.

85. Constraint Satisfaction Problem(CSP): CSP consists of three components V,D,C. V is set of variables {V1,V2,---- Vn }. D is set of domains {D1,D2,…. Dn }. C is set of constraints that specify allowable combination of values . Ci=( Scope,Relation ) Where scope is set of variables that participate in constraint Where Relation is relation that define the values that variable can take C1=((V1,V2),(V1≠V2)).