Transcription
Artificial IntelligenceByDr Zafar. M. Alvi
Artificial Intelligence (CS607)Table of Contents:12345Introduction. 41.1What is Intelligence? . 41.2Intelligent Machines . 71.3Formal Definitions for Artificial Intelligence. 71.4History and Evolution of Artificial Intelligence . 91.5Applications . 131.6Summary . 14Problem Solving . 152.1Classical Approach. 152.2Generate and Test . 152.3Problem Representation. 162.4Components of Problem Solving. 172.5The Two-One Problem . 182.6Searching. 212.7Tree and Graphs Terminology. 212.8Search Strategies . 232.9Simple Search Algorithm . 242.10Simple Search Algorithm Applied to Depth First Search. 252.11Simple Search Algorithm Applied to Breadth First Search. 282.12Problems with DFS and BFS. 322.13Progressive Deepening . 322.14Heuristically Informed Searches . 372.15Hill Climbing. 392.16Beam Search. 432.17Best First Search. 452.18Optimal Searches. 472.19Branch and Bound . 482.20Improvements in Branch and Bound . 552.21A* Procedure. 562.22Adversarial Search . 622.23Minimax Procedure . 632.24Alpha Beta Pruning . 642.25Summary . 712.26Problems. 72Genetic Algorithms. 763.1Discussion on Problem Solving. 763.2Hill Climbing in Parallel . 763.3Comment on Evolution. 773.4Genetic Algorithm . 773.5Basic Genetic Algorithm . 773.6Solution to a Few Problems using GA . 773.7Eight Queens Problem. 823.8Problems. 88Knowledge Representation and Reasoning. 894.1The AI Cycle . 894.2The dilemma. 904.3Knowledge and its types. 904.4Towards Representation . 914.5Formal KR techniques. 934.6Facts . 944.7Rules. 954.8Semantic networks . 974.9Frames . 984.10Logic. 984.11Reasoning . 1024.12Types of reasoning . 102Expert Systems . 1112 Copyright Virtual University of Pakistan
Artificial Intelligence (CS607)5.1What is an Expert? . 1115.2What is an expert system? . 1115.3History and Evolution . 1115.4Comparison of a human expert and an expert yystem. 1125.5Roles of an expert system. 1135.6How are expert systems used?. 1145.7Expert system structure . 1155.8Characteristics of expert systems . 1215.9Programming vs. knowledge engineering . 1225.10People involved in an expert system project . 1225.11Inference mechanisms . 1235.12Design of expert systems. 1296Handling uncertainty with fuzzy systems . 1456.1Introduction . 1456.2Classical sets . 1456.3Fuzzy sets . 1466.4Fuzzy Logic. 1476.5Fuzzy inference system . 1536.6Summary . 1586.7Exercise . 1587Introduction to learning. 1597.1Motivation . 1597.2What is learning ?. 1597.3What is machine learning ? . 1607.4Why do we want machine learning . 1607.5What are the three phases in machine learning?. 1607.6Learning techniques available . 1627.7How is it different from the AI we've studied so far?. 1637.8Applied learning . 1637.9LEARNING: Symbol-based. 1657.10Problem and problem spaces . 1657.11Concept learning as search . 1717.12Decision trees learning . 1767.13LEARNING: Connectionist . 1817.14Biological aspects and structure of a neuron . 1817.15Single perceptron. 1827.16Linearly separable problems. 1847.17Multiple layers of perceptrons. 1867.18Artificial Neural Networks: supervised and unsupervised . 1877.19Basic terminologies . 1877.20Design phases of ANNs. 1887.21Supervised . 1907.22Unsupervised . 1907.23Exercise . 1928Planning . 1958.1Motivation . 1958.2Definition of Planning . 1968.3Planning vs. problem solving . 1978.4Planning language . 1978.5The partial-order planning algorithm – POP . 1988.6POP Example . 1998.7Problems. 2029Advanced Topics . 2039.1Computer vision . 2039.2Robotics. 2049.3Clustering . 20510Conclusion . 2063 Copyright Virtual University of Pakistan
Artificial Intelligence (CS607)Artificial Intelligence1 IntroductionThis booklet is organized as chapters that elaborate on various concepts ofArtificial Intelligence. The field itself is an emerging area of computer sciencesand a lot of work is underway in order to mature the concepts of this field.In this booklet we will however try to envelop some important aspects and basicconcepts which will help the reader to get an insight into the type of topics thatArtificial Intelligence deals with.We have used the name of the field i.e. Artificial Intelligence (commonly referredas AI) without any explanation of the name itself. Let us now look into a simplebut comprehensive way to define the field.To define AI, let us first try to understand that what is Intelligence?1.1 What is Intelligence?If you were asked a simple question; how can we define Intelligence? many ofyou would exactly know what it is but most of you won’t exactly be able to defineit. Is it something tangible? We all know that it does exist but what actually it is.Some of us will attribute intelligence to living beings and would be of the view thatall living species are intelligent. But how about these plants and tress, they areliving species but are they also intelligent? So can we say that Intelligence is atrait of some living species? Let us try to understand the phenomena ofintelligence by using a few examples.Consider the following image where a mouse is trying to search a maze in orderto find its way from the bottom left to the piece of cheese in the top right corner ofthe image.This problem can be considered as a common real life problem which we dealwith many times in our life, i.e. finding a path, may be to a university, to a friendshouse, to a market, or in this case to the piece of cheese. The mouse triesvarious paths as shown by arrows and can reach the cheese by more than onepath. In other words the mouse can find more than one solutions to this problem.The mouse was intelligent enough to find a solution to the problem at hand.Hence the ability of problem solving demonstrates intelligence.Let us consider another problem. Consider the sequence of numbers below:1, 3, 7, 13, 21,4 Copyright Virtual University of Pakistan
Artificial Intelligence (CS607)If you were asked to find the next number in the sequence what would be youranswer? Just to help you out in the answer let us solve it for you “adding the nexteven number to the” i.e. if we add 2 to 1 we get 3, then we add 4 to 3 we get 7,then we get 6 to 7 we get 13, then we add 8 to 13 we get 21 and finally if we’lladd 10 to 21 we’ll get 31 as the answer. Again answering the question requires alittle bit intelligence. The characteristic of intelligence comes in when we try tosolve something, we check various ways to solve it, we check differentcombinations, and many other things to solve different problems. All this thinking,this memory manipulation capability, this numerical processing ability and a lot ofother things add to ones intelligence.All of you have experienced your college life. It was very easy for us to look at thetimetable and go to the respective classes to attend them. Not even caring thathow that time table was actually developed. In simple cases developing such atimetable is simple. But in cases where we have 100s of students studying indifferent classes, where we have only a few rooms and limited time to scheduleall those classes. This gets tougher and tougher. The person who makes thetimetable has to look into all the time schedule, availability of the teachers,availability of the rooms, and many other things to fit all the items correctly withina fixed span of time. He has to look into many expressions and thoughts like “Ifroom A is free AND teacher B is ready to take the class AND the students of theclass are not studying any other course at that time” THEN “the class can bescheduled”. This is a fairly simple one, things get complex as we add more andmore parameters e.g. if we were to consider that teacher B might teach morethan one course and he might just prefer to teach in room C and many otherthings like that. The problem gets more and more complex. We are pretty muchsure than none of us had ever realized the complexity through which our teachersgo through while developing these schedules for our classes. However, like weknow such time tables can be developed. All this information has to reside in thedeveloper’s brain. His intelligence helps him to create such a schedule. Hencethe ability to think, plan and schedule demonstrate intelligence.Consider a doctor, he checks many patients daily, diagnoses their disease, givesthem medicine and prescribes them behaviors that can help them to get cured.Let us think a little and try to understand that what actually he does. Thoughchecking a patient and diagnosing the disease is much more complex but we’ll tryto keep our discussion very simple and will intentionally miss out stuff from thisdiscussion.A person goes to doctor, tells him that he is not feeling well. The doctor asks hima few questions to clarify the patient’s situation. The doctor takes a fewmeasurements to check the physical status of the person. These measurementsmight just include the temperature (T), Blood Pressure (BP), Pulse Rate (PR) andthings like that. For simplicity let us consider that some doctor only checks thesemeasurements and tries to come up with a diagnosis for the disease. He takesthese measurements and based on his previous knowledge he tries to diagnosethe disease. His previous knowledge is based on rules like: “If the patient has ahigh BP and normal T and normal PR then he is not well”. “If only the BP isnormal then what ever the other measurements may be the person should behealthy”, and many such other rules.5 Copyright Virtual University of Pakistan
Artificial Intelligence (CS607)The key thing to notice is that by using such rules the doctor might classify aperson to be healthy or ill and might as well prescribe different medicines to himusing the information observed from the measurements according to his previousknowledge. Diagnosing a disease has many other complex information andobservations involved, we have just mentioned a very simple case here. However,the doctor is actually faced with solving a problem of diagnosis having looked atsome specific measurements. It is important to consider that a doctor who wouldhave a better memory to store all this precious knowledge, better ability ofretrieving the correct portion of the knowledge for the correct patient will be betterable to classify a patient. Hence, telling us that memory and correct andefficient memory and information manipulation also counts towards onesintelligence.Things are not all that simple. People don’t think about problems in the samemanner. Let us give you an extremely simple problem. Just tell us about yourheight. Are you short, medium or tall? An extremely easy question! Well youmight just think that you are tall but your friend who is taller than you might saythat NO! You are not. The point being that some people might have such adistribution in their mind that people having height around 4ft are short, around 5ftare medium and around 6ft are tall. Others might have this distribution thatpeople having height around 4.5ft are short, around 5.5ft are medium and around6.5ft are tall. Even having the same measurements different people can get tocompletely different results as they approach the problem in different fashion.Things can be even more complex when the same person, having observedsame measurements solves the same problem in two different ways and reachesdifferent solutions. But we all know that we answer such fuzzy questions veryefficiently in our daily lives. Our intelligence actually helps us do this. Hence theability to tackle ambiguous and fuzzy problems demonstrates intelligence.Can you recognize a person just by looking at his/her fingerprint? Though we allknow that every human has a distinct pattern of his/her fingerprint but just bylooking at a fingerprint image a human generally can’t just tell that this print mustbe of person XYZ. On the other hand having distinct fingerprint is really importantinformation as it serves as a unique ID for all the humans in this world.Let us just consider 5 different people and ask a sixth one to have a look atdifferent images of their fingerprints. We ask him to somehow learn the patterns,which make the five prints distinct in some manner. After having seen the imagesa several times, that sixth person might get to find something that is making theprints distinct. Things like one of them has fever lines in the print, the other onehas sharply curved lines, some might have larger distance between the lines inthe print and some might have smaller displacement between the lines and manysuch features. The point being that after some time, which may be in hours ordays or may be even months, that sixth person will be able to look at a newfingerprint of one of those five persons and he might with some degree ofaccuracy recognize that which one amongst the five does it belong. Only with 5people the problem was hard to solve. His intelligence helped him to learn thefeatures that distinguish one finger print from the other. Hence the ability tolearn and recognize demonstrates intelligence.6 Copyright Virtual University of Pakistan
Artificial Intelligence (CS607)Let us give one last thought and then will get to why we have discussed all this. Alot of us regularly watch television. Consider that you switch off the volume ofyour TV set. If you are watching a VU lecture you will somehow perceive that theperson standing in front of you is not singing a song, or anchoring a musical showor playing some sport. So just by observing the sequence of images of theperson you are able to perceive meaningful information out of the video. Yourintelligence helped you to perceive and understand what was happening on theTV. Hence the ability to understand and perceive demonstrates intelligence.1.2 Intelligent MachinesThe discussion in the above section has a lot of consequences when we see itwith a different perspective. Let us show you something really interesting nowand hence informally define the field of Artificial Intelligence at the same time.What if? A machine searches through a mesh and finds a path? A machine solves problems like the next number in the sequence? A machine develops plans? A machine diagnoses and prescribes? A machine answers ambiguous questions? A machine recognizes fingerprints? A machine understands? A machine perceives? A machine does MANY MORE SUCH THINGS! A machine behaves as HUMANS do? HUMANOID!!!We will have to call such a machine Intelligent. Is this real or naturalintelligence? NO! This is Artificial Intelligence.1.3 Formal Definitions for Artificial IntelligenceIn their book “Artificial Intelligence: A Modern Approach” Stuart Russell and PeterNorvig comment on artificial intelligence in a very comprehensive manner. Theypresent the definitions of artificial intelligence according to eight recent textbooks.These definitions can be broadly categorized under two themes. The ones in theleft column of the table below are concerned with thought process andreasoning, where as the ones in the right column address behavior.Systems that think likehumans“The exciting new effortto make computers think machines with minds,in the full and literalsense”(Haugeland,1985)“[The automation of]activitiesthatweassociate with humanthinking, activities suchSystems that act likehumans“The art of creatingmachines that performfunctions that requireintelligencewhenperformed by people”(Kurzweil 1990)“The study of how tomake computers dothings at which, at themoment, people are7 Copyright Virtual University of Pakistan
Artificial Intelligence (CS607)as decision making,problemsolving,learning ” (Bellman,1978)“The study of mentalfaculties through the useofcomputationalmodels” (Charniak andMcDermott)“Thestudyofcomputation that make itpossible to perceivereasonandact”(Winston 1992)better” (Rich and Knight,1991)“A field of study thatseeks to explain andemulateintelligentbehavior in terms ofcomputationalprocesses” (Schalkoff,1990)“The branch of computersciencethatisconcernedwiththeautomation of intelligentbehavior” (Luger andStubblefield, 1993)To make computers think like humans we first need to devise ways to determinethat how humans think. This is not that easy. For this we need to get inside theactual functioning of the human brain. There are two ways to do this: Introspection: that is trying to catch out own thoughts as they go by. Psychological Experiments: that concern with the study of science ofmental life.Once we accomplish in developing some sort of comprehensive theory that howhumans think, only then can we come up with computer programs that follow thesame rules. The interdisciplinary field of cognitive science brings togethercomputer models from AI and experimental techniques from psychology to try toconstruct precise and testable theories of the working of human mind.The issue of acting like humans comes up when AI programs have to interactwith people or when they have to do something physically which human usuallydo in real life. For instance when a natural language processing system makes adialog with a person, or when some intelligent software gives out a medicaldiagnosis, or when a robotic arm sorts out manufactured goods over a conveyerbelt and many other such scenarios.Keeping in view all the above motivations let us give a fairly comprehensivecomment that Artificial Intelligence is an effort to create systems that can learn,think, perceive, analyze and act in the same manner as real humans.People have also looked into understanding the phenomena of ArtificialInt
Artificial Intelligence deals with. We have used the name of the field i.e. Artificial Intelligence (commonly referred as AI) without any explanation of the name itself. Let us now look into a simple but comprehensive way to define the field. To define AI, let us first try to understand that what is Intellig
