Unit 1: Introduction to Artificial Intelligence PDF

21CSC206T-Artificial Intelligence UNIT - 1 Introduction to AI Topics-Introduction to AI AI-Basics AI techniques Problem solving with AI AI Models Data acquisition and learning aspects in AI Problem solving...

21CSC206T-Artificial Intelligence UNIT - 1 Introduction to AI Topics-Introduction to AI AI-Basics AI techniques Problem solving with AI AI Models Data acquisition and learning aspects in AI Problem solving Problem solving process Formulating problems Problem types and characteristics Problem space and search Toy Problems Tic-tac-toe problems Missionaries and Cannibals Problem Real World Problem Travelling Salesman Problem 2 1  Overview of AI Definition of Artificial Intelligence Artificial-(Man Made) Produced by human art or effort. Intelligence- (Thinking Power) ability to acquire knowledge and use it. So AI was defined as: AI is the branch of computer science by which we can create intelligent machine that can behave like a human, act like a human, able to make decisions for solving the problems. AI don’t need any preprogrammed machine to do some work. We have to create a machine with programmed algorithms which can work with its own intelligence. 2  What is Artificial Intelligence? Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better. (Rich and Knight) It deals with the science that is about the efforts of making a machine behave intelligently and respond in a way as human would have responded and in due process, deliver reasonable answers. In other words, a branch of science and engineering that focuses on making machine intelligent is widely known as AI. Why Artificial Intelligence? With the help of AI, create software (or) device, which can solve real world problems very easily and accuracy such as health issues, marketing and traffic issues. create our personal virtual assistants, such as Google Assistant, siri etc. Build robots which can work in a environment where survival of human is at risk. AI opens a path for new technologies, new devices, new opportunities. 3  Goals of Artificial Intelligence 1. Replicates human intelligence 2. Solve knowledge intensive tasks 3. An intelligent connection of perception and action 4. Building a machine which can perform tasks that requires human intelligence such as Providing a theorem Playing chess Self Autonomous cars in traffic Plan some surgical operation Intelligence Intelligence = Knowledge + ability to perceive, feel, comprehend, process, communicate, judge, learn Judgement, Making Ability to use comprehend, speak, write the verbal and decision prediction written lines Working through details of Gaining Knowledge problems to reach the solution. (Decision Making) Mechanism to Acquire, interpret, select, organize 4  What is Artificial Intelligence ? THOUGHT Systems that think Systems that think like humans rationally Systems that act Systems that act BEHAVIOUR like humans rationally HUMAN RATIONAL Artificial Intelligence Systems that act like humans- Turing Test Systems that think like humans- cognitive modeling Systems that think ‘rationally’- laws of thought Systems that act rationally- Rational agent”- Logic+ Domain knowledge 5  Systems that act like humans: Turing Test Enter a room which has a computer terminal. Type what you want into the terminal, and study the replies. At the other end of the line is either a human being or a computer system. If it is a computer system, and at the end of the period you cannot reliably determine whether it is a system or a human, then the system is deemed to be intelligent. ? The Turing Test approach a human questioner cannot tell if there is a computer or a human answering his question, via teletype (remote communication) The computer must behave intelligently Intelligent behavior to achieve human-level performance in all cognitive tasks These cognitive tasks include: Natural language processing for communication with human Knowledge representation to store information effectively & efficiently Automated reasoning to retrieve & answer questions using the stored information Machine learning to adapt to new circumstances Systems that think like humans: cognitive modeling Humans as observed from ‘inside’ How do we know how humans think? -Introspection vs. psychological experiments Cognitive Science “The exciting new effort to make computers think … machines with minds in the full and literal sense” (Haugeland) “[The automation of] activities that we associate with human thinking, activities such as decision- making, problem solving, learning …” (Bellman) 6  Systems that think ‘rationally’ "laws of thought" Humans are not always ‘rational’ Rational - defined in terms of logic? Logic can’t express everything (e.g. uncertainty) Logical approach is often not feasible in terms of computation time (needs ‘guidance’) “The study of mental facilities through the use of computational models” (Charniak and McDermott) “The study of the computations that make it possible to perceive, reason, and act” (Winston) Systems that act rationally: “Rational agent” LOGIC + Domain knowledge Rational behavior: doing the right thing The right thing: that which is expected to maximize goal achievement, given the available information Giving answers to questions is ‘acting’. replicates human thought processes makes the same decisions as humans uses purely logical reasoning Thus, it covers more generally different situations of problems Compensate the incorrectly reasoned conclusion Study AI as rational agent – advantages: It is more general than using logic only Because: LOGIC + Domain knowledge It allows extension of the approach with more scientific methodologies 7  Applications of Artificial Intelligence Heuristic Search Computer Vision Adversarial Search (Games) Fuzzy Logic Natural Language Processing Knowledge Representation Planning Playing chess Driving on the highway Answering questions Recognizing speech Diagnosing diseases Translating languages Data mining ARTIFICIAL INTELLIGENCE- HISTORY AND FOUNDATION 1. AI has been a part of mainstream research since last 60 years. 2. But AI Philosophy is as old as one thousand years. 3. Allan turning devised a simple test of intelligence in 1950, Where the response of machine is expected to be intelligent enough so that it is difficult to find out whether it is machine or human sitting on the other side. 4. In 1956 , John McCarthy insisted ad made AI as a topic for conference at Dartmount. 5. In 1958, he invented the Lisp Language. (mathematical theory of recursive functions) 6. Initially AI was focused on common sense reasoning and obvious reaction. That is problem solving and decision making was based on set of simple hypothesis. 8  Example of a Traditional mechanical Intelligent system Here once the water reaches to certain level, the water tap is closed to avoid overflow. In washing machine these system were replaced with the sensor based level detector. Later Fuzzy logic came into the picture that allowed deciding the level of water dynamically based on the quantity of cloth. So, we now having machine , with Fuzzy logic Included. AI techniques AI deals with a large Spectrum of Problem, this includes the following : 1. Various Day to Day Practical Problem. (Traffic, Lift) 2. Different identification and authentication problems with their applications in security. 3. Various classification problems resulting in decision-making. (Image processing) But most of these problems are complex and hard to resolve. The very reason of the complexity is the dynamic nature of these problems unlike some routine mathematical problems. Al techniques need to look at these problems from analysis perspective and from the perspective of research initiatives to resolve them. Al techniques need to be built from the problem-solving perspectives. 9  AI techniques AI techniques encompass a variety of approaches to enable machines to perform tasks requiring human-like intelligence. 1.Machine Learning (ML): Supervised, Unsupervised, and Reinforcement Learning. 2.Deep Learning: Involving deep neural networks for tasks like image and speech recognition. 3.Natural Language Processing (NLP): Teaching machines to understand and generate human language. 4.Computer Vision: Enabling machines to interpret visual information from images and videos. 5.Expert Systems: Rule-based systems emulating human decision-making in specific domains. 6.Fuzzy Logic: Handling uncertainty and imprecision in decision-making. 7.Robotics: Integrating AI for autonomous decision-making in robotic systems. AI techniques Contd… The main objective of Al techniques is to capture knowledge based on the data and information. The knowledge captures generalizations that share properties, are grouped together, rather than being allowed separate representation. There are different scenarios and the relevant data is captured. The AI techniques need to handle different problems. The broad categorization of these problems can be as follows: 1. Structured problems 2. Unstructured problems 3. Linear problems 4. Non-linear problems 10  PROBLEM SOLVING WITH AI Al has been very well used to solve structured problems. (well and ill structured problems). The well-structured problems are some of the very commonly faced problems during day-to-day life. These problems yield a right answer or right inference when an appropriate algorithm is applied. Some of the well-structured problems are given below: 1. Solving a quadratic equation to find out the value of X 2. Calculating path of the trajectory when a missile is fired 3. Calculating speed of ball when it reaches to batsman 4. Network flow analysis problem 5. Tic Tac Toe problems PROBLEM SOLVING WITH AI While ill-structured problems are the problems which do not yield a particular answer. In this case, there is possibility of more than one answer, and even a particular situation decides the correctness of the answer. Interestingly, ill-structured problems represent many of the real-world problems. Some examples of the ill-structured problems are given below: 1. Predicting how to dispose wet waste safely 2. Analysis of theoretical prepositions and adequacy of the same in a particular scenario 3. Identifying the security threats in big social gatherings unstructured problems are difficult to represent and model. There are possibilities of more than one goal states in case of unstructured problems. In most of the cases, exact goal is not known. Eg, System to improve life expectancy of human being, expanding the business. 11  AI MODELS One important aspect of building Al solutions is modelling the problem. Dunker introduced 'maze hypothesis' as a part of the psychological theory. In this particular hypothesis, the creative and intelligent tasks handled by human beings are modelled like a set of maze of paths from an initial node to a certain or resultant node. Human at any point of time analyses maze; for choices, he could find those which can lead to goal. These choices and maze-based approach can help in solving many multi alternative solution problems.. Slowly, it became evident that all problems cannot be solved using maze models or the approach described above. This brought more focus on logic theory machines. Effective application of logic theory machines is found very useful in general problem solving, even this is found very useful for a wide spectrum of problems like chess problem. Chess can be viewed as a controlled environment in which computer is given a situation and a goal. AI MODELS Semiotics Models: Semiotics is the study of the use of symbolic communication. Semiotics can include signs, logos, gestures and other linguistic and nonlinguistic communication methods. As a word, semiotics derives from the Greek, which describes the action of interpreting sign. Statistical Models: Statistical models refer to representation and formalisation of relationships through statistical techniques. Most of the Al problems can be represented as statistical or pattern matching problems. Various learning models from Al perspective are based on statistics. The historical data is used here in decision-making. Statistical model employs probabilistic approaches and is typically a collection of probability density functions and distribution functions. 12  AI MODELS AI models are computational structures or algorithms used in artificial intelligence and machine learning systems. They are trained on data to perform specific tasks or make decisions without explicit programming. Common types include linear regression, logistic regression, decision trees, random forests, support vector machines, neural networks, recurrent neural networks, LSTM, GRU, transformer models (e.g., BERT, GPT), K-means clustering, hierarchical clustering, PCA, autoencoders, and generative adversarial networks. The choice of a model depends on factors like data characteristics, problem complexity, and desired outcomes. DATA ACQUISITION AND LEARNING ASPECTS IN AI 1. Knowledge discovery-Data mining and machine learning: Data Extraction, Extracting the meaning full information. The mining process includes data cleaning, preprocessing, identifying and interpreting the patterns, understanding the application and generating the target data with the consolidated patterns. 2. Computational learning theory (COLT): Mathematical Model, These models help in analyzing the efficiency and complexity in terms of computation, prediction and feasibility of the algorithms. 3. Neural and evolutionary computation: to speed up the Mining of data, based on Biological properties eg, Neural Network 4. Intelligent agents and multi-agent systems: Intelligent agents and multi-agent systems (MAS) si a core part of intelligent systems, which allows timely decision-making in complex scenarios. An agent in simple terms, is a software program that assists user. An intelligent agent is the one which is flexible in terms of its action to get the desired outcome. 13  DATA ACQUISITION AND LEARNING ASPECTS IN AI 5. Multi-perspective integrated intelligence: For any problem to solve, each and every individual can have his own perspective. Some information might be present in some perspective, while it could be missing in other perspective, which could be effective in terms of decision-making. Example: Consider a scenario, where you want to apply for a job in a renowned company. You tend to seek feedback from some employees. Each will have his own perspective in relation to management, working environment, appraisals and so on. Some friend of yours might not be working, but is acquainted with the company. He would also have a different perspective. Based on this knowledge, possibly you could land upon a decision whether to take up the job or not. Problem Solving Problem solving, as the name suggests, is an area to deal with finding answer for some unknown situations. It involves understanding, representation, formulation and solving. This simple definition encapsulates two types of problems 1. Simple Problem 2. Complex Problem 1. Simple Problem can be solved by a deterministic procedure. There is a guarantee of a solution. 2. Solving complex problems is indeed a complex and tricky task. For us, solving a problem at hand is not so difficult since we can reason out, perceive, learn, but for a machine, it is actually very difficult. While drawing conclusions, we can use the statistical methods, the mathematical modelling processes and so on to get the best solutions. Al focuses on mapping of these intellectual abilities into the machine to get the best solutions. 14  Problem Solving Process Problem-solving is a process of generating solutions for a given situation. The above diagram shows problem-solving process applied to achieve goal state. This process consists of sequence of well-defined methods that can handle doubts or inconsistency issues, uncertainty, ambiguity and help in achieving the desired goal. The term problem can be defined with following conditions: 1. Every problem has a well-defined objective. 2. Solution to every problem consists of a set of activities. Each activity changes the state of problem, i.e., from the present state to the new state. 3. Previous knowledge and domain knowledge both are used as the resources Problem Solving Process Contd… General problem-solving techniques involve the following: 1. Problem definition 2. Problem analysis and representation 3. Planning 4. Execution 5. Evaluating solution 6. Consolidating gains 15  FORMULATING PROBLEMS 1. Problem identification is the first step in problem solving process. Once the problem is identified, we need to be very precise and specific with respect to the problem space along with the target that we need to achieve. 2. Second step here is the analysis and representation of the task knowledge. Usually, we understand the problem in terms of diagram, description and so on. But in Al, the target is to use machine to solve a problem, once the solution is planned and fed to it. This is done using state-space diagram. So, the problem is defined in terms of state. Solution to any problem is the collection of such different states and set of operations. This collection of states is termed as state space. Each of these states is achieved using the application of actions/ operations to the previous state. During problem-solving process, an operator is applied to a state to move it to the next state. FORMULATING PROBLEMS Consider a problem where three cells in the four-cell board are filed with single digits and one cell is left blank. The game is to change positions of the digit and blank cell of the board to arrive at new board positions. The rule of the game is blank cell can change the position with a digit by horizontal or vertical movement. Diagram represents the initial and the final states of this game. PROBLEM: To reach from the initial state to the final state, with the minimum number of moves. 1. Now we define state space Operation and action space. 2. Action Space has an operation on blank cell ie, move up(U),Move Down(D), Move Left (L) and Move right (R). 3. S0  Starting State & Sn  Final/goal State. 16  FORMULATING PROBLEMS Contd… A well defined problem, hence, is described in terms of 1. Initial state 2. Goal state 3. List of states 4. Operators or functions that change state or transition of state 5. Path (sequence of states leading to goal state) 6. Path cost (functions that assign a cost to the path) PROBLEM TYPES AND CHARACTERISTICS 1. Deterministic or observable: Each state is fully observable and it goes to one definite state after any action. Here, the goal state is reachable in one single action or sequence of actions. For example, vacuum cleaner with sensor, Here next state can be found using current state and action. 2. Non-observable: This type of problem comes under multiple-state problems. So, the problem- solving agent does not have any information about the state. Application of operator can lead problem to multiple states in this case. Hence, each state goes to a number of states after the application of an operator. Example: Let us take an example of vacuum cleaner. The goal state is to clean the floor rather clean floor. Action is to suck if there is dirt. So, in non-observable condition, as there is no sensor, it will have to suck the dirt, irrespective of whether it is towards right or left. Here, the solution space is the states specifying its movement across the floor. 3. Non-deterministic or partially observable: In this type of problem, the effect of action is not clear. 17  PROBLEM TYPES AND CHARACTERISTICS 4. Unknown state space: Unknown state space problems are typically exploration problems. States and impact of actions are not known. There is a need to discover to understand the outcomes of actions. For example, online search that involves acting without complete knowledge of the next state or searching address without map. Problem Characteristics Is the problem decomposable ? Can Solution steps be ignored or undone ? Is the Universe Predictable? Is a good solution absolute or relative ? Is the solution a state or a path? What is the role of knowledge? Does the task require interaction with a person ? 18  Water Jug Problem PROBLEM: To find out a way to empty 2 gal jug and fill 5 gal jug with 1 gal water. Let us first convert this problem into a state-space (problem problem formulation step). So, we need to define the states, actions and goals. States: Amount of water in the jugs Actions: 1. Empty the big jug. 2. Empty the small jug. 3. Pour water from small jug to big jug. 4. Pour water from big jug to small jug. Goal: To get the specified amount of water 1( gal) in big jug and empty the smaller jug. Path cost: The number of actions applied. (Minimum the number of actions, better is the solution). Water Jug Problem Contd… Initial state: (5, 2) Goal state: (1, 0) 19  PROBLEM SPACE AND SEARCH Search is a general algorithm that helps in finding the path in the state space. Every problem (as said before) can be solved with the help of search. It considers one or more path. The path may lead to the solution or might be dead end. In case of dead end, backtrack should occur. The search algorithm, makes use of control strategy like that of forward or backward search. Informed search does not guarantee a solution, but there is high probability of getting a solution. Eg. A8,AO*, greedy search etc Uninformed strategy generates all possible states in the state space and checks for the goal state. Eg BFS,DFS, Depth first search Toy Problem 1. Tic-tac-toe Problem 2. Missionaries and cannibals 3. Traveler salesman problem. 4. 8 queen Problem etc 20