Transcript machine
Artificial Intelligence Introduction AI You are a caveman (or woman) I travel back in time and bring you a LapTop and show you some of the things it is capable of doing. Question : Would you, as a caveman, consider the computer to be intelligent? Big questions Can machines think? If so, how? If not, why not? What does this say about humans? What does this say about the mind? AI Long Term Goals Produce intelligent behaviour in machines Why use computers at all? – They can do things better than us – Big calculations quickly and reliably We do intelligent things – So get computers to do intelligent things Some Advantages of Artificial Intelligence – more powerful and more useful computers – new and improved interfaces – solving new problems – better handling of information – relieves information overload – conversion of information into knowledge The Disadvantages – increased costs – difficulty with software development - slow and expensive – few experienced programmers – few practical products have reached the market as yet. Some AI Systems that are Better Than Humans Backgammon – TD gammon was the first program to beat the worlds best players (Gerald Tesauro) http://researchweb.watson.ibm.com/massive/t dl.html Why AI? Engineering: To get machines to do a wider variety of useful things – e.g., understand spoken natural language, recognize individual people in visual scenes, find the best travel plan for your vacation, etc. Cognitive Science: As a way to understand how natural minds and mental phenomena work – e.g., visual perception, memory, learning, language, etc. Philosophy: As a way to explore some basic and interesting (and important) philosophical questions – e.g., the mind body problem, what is consciousness, etc. What is Artificial Intelligence ? making computers that think? the automation of activities we associate with human thinking, like decision making, learning ... ? the art of creating machines that perform functions that require intelligence when performed by people ? What’s easy and what’s hard for AI? It’s been easier to mechanize many of the high-level tasks we usually associate with “intelligence” in people – e.g., symbolic integration, proving theorems, playing chess, medical diagnosis It’s been very hard to mechanize tasks that lots of animals can do – walking around without running into things – catching prey and avoiding predators – interpreting complex sensory information (e.g., visual, aural, …) – modeling the internal states of other animals from their behavior – working as a team (e.g., with pack animals) Is there a fundamental difference between the two categories? What can AI systems do? Here are some example applications Computer vision: face recognition from a large set Robotics: autonomous (mostly) automobile Natural language processing: simple machine translation Expert systems: medical diagnosis in a narrow domain Spoken language systems: ~1000 word continuous speech Planning and scheduling: Hubble Telescope experiments Learning: text categorization into ~1000 topics User modeling: Bayesian reasoning in Windows help (the infamous paper clip…) Games: Grand Master level in chess (world champion), checkers, etc. IBM’s Deep Blue versus Kasparov On May 11, 1997, Deep Blue was the first computer program to beat reigning chess champion Kasparov in a 6 game match (2 : 1 wins, with 3 draws) Massively parallel computation (259th most powerful supercomputer in 1997) Evaluation function criteria learned by analyzing thousands of master games Searched the game tree • from 6-12 ply usually, up to 40 ply in some situations. One ply corresponds to – one turn of play. Robotics Shakey (1966-1972) Kismet (late 90s, 2000s) Cog (90s) Robocup Soccer (2000s) Boss (2007) How is it Currently Done? Crusher and, more recently, PerceptTOR DARPA grand challenge Stanley Robot Stanford Racing Team www.stanfordracing.org Next few slides courtesy of Prof. Sebastian Thrun, Stanford University What About the DARPA Grand Challenge? Autonomous Navigation in the Desert over a 132 mile course. 5 Teams succeeded! – http://www.darpa.mil/grandchallenge05/gcorg/index.html This was a monumental achievement in autonomous robotics HOWEVER: This was not an unstructured environment! – GPS waypoints were carefully chosen, sometimes less than a meter apart. Stanley’s Technology Path Planning Laser Terrain Mapping Learning from Human Drivers Adaptive Vision Sebastian Stanley Images and movies taken from Sebastian Thrun’s multimedia website. SENSOR INTERFACE RDDF database PERCEPTION PLANNING&CONTROL USER INTERFACE Top level control corridor Touch screen UI pause/disable command Wireless E-Stop Laser 1 interface RDDF corridor (smoothed and original) driving mode Laser 2 interface Laser 3 interface road center Road finder Laser 4 interface laser map Laser 5 interface Laser mapper Camera interface Vision mapper Radar interface Radar mapper Path planner trajectory map VEHICLE INTERFACE vision map Steering control obstacle list Touareg interface vehicle state (pose, velocity) GPS position UKF Pose estimation GPS compass vehicle state (pose, velocity) IMU interface vehicle state Throttle/brake control Power server interface velocity limit Surface assessment Wheel velocity Brake/steering heart beats emergency stop Linux processes start/stop health status Process controller Health monitor power on/off data GLOBAL SERVICES Data logger Communication requests File system Communication channels Inter-process communication (IPC) server clocks Time server Europa Hydrobot http://www.resa.net/nasa/images/gem/HYDR OBOT.JPG AI Applications Games: AI Applications Games: AI Applications Robotic toys: AI Applications Transportation: – Pedestrian detection: AI Applications Medicine: – Image guided surgery AI Applications Autonomous Planning & Scheduling: – Telescope scheduling Why is AI hard? Two usual ingredients (for standard AI) Representation – need to represent our knowledge in computer readable form Reasoning – need to be able to manipulate knowledge and derive new knowledge – many possible ways to do this, but most give rubbish – finding the successful way usually involves search Both of these are hard. The Travelling Salesman Problem (TSP) A salesperson has to visit a number of cities (S)He can start at any city and must finish at that same city The salesperson must visit each city only once For example, with 5 cities a possible tour is: A C D B E Combinatorial Explosion A 50 City TSP has 1.52 * 1064 possible solutions Age of the universe is 15 billion (1.5 * 1010) years There are 30 million seconds in a year Age of universe is about 45 * 1016 seconds A 10GHz computer might do 109 tours per second Running since start of universe, it would still only have done 1026 tours Not even close to evaluating all tours! Need to be clever about how to solve such search problems! AI Generic Techniques Automated Reasoning – Resolution, proof planning, Davis-Putnam, CSPs Machine Learning – Neural nets, ILP, decision tree learning Natural language processing – N-grams, parsing, grammar learning Robotics – Planning, edge detection, cell decomposition Evolutionary approaches – Crossover, mutation, selection Course Overview: Three areas AI fundamentals – Characterisations, terminology, methodologies – Representation and search – Application to game playing Automated reasoning (deduction) – Socrates was mortal Machine learning (induction) – Every man has died, so we all die Some Famous Imitation Games 1960s ELIZA – Rogerian psychotherapist 1970s SHRDLU – Blocks world reasoner 1980s NICOLAI – unrestricted discourse 1990s Loebner prize – win $100,000 if you pass the test 33 The problem with ELIZA Eliza used simple pattern matching – “Well, my friend made me come here” – “Your friend made you come here?” Eliza written by Joseph Weizenbaum 34 Who does AI? Academic researchers (perhaps the most Ph.D.-generating area of computer science in recent years) – Some of the top AI schools: CMU, Stanford, Berkeley, MIT, UIUC, UMd, U Alberta, UT Austin, ... (and, of course, Swarthmore!) Government and private research labs – NASA, NRL, NIST, IBM, AT&T, SRI, ISI, MERL, ... Lots of companies! – Google, Microsoft, Honeywell, Teknowledge, SAIC, MITRE, Fujitsu, Global InfoTek, BodyMedia, ... The course topics introduction to AI AI application areas Knowledge representation Search space Machine learning Course overview Introduction and Agents (chapters 1,2) Search (chapters 3,4,5,6) Logic (chapters 7,8,9) Planning (chapters 11,12) Uncertainty (chapters 13,14) Learning (chapters 18,20) Natural Language Processing (chapter 22,23) AI definition AI is a branch of computer science and it concerned with intelligent behavior. What is AI? There are no crisp definitions Q. What is artificial intelligence? A. It is the science and engineering of making intelligent machines, especially intelligent computer programs. Q. what is intelligence? A. Intelligence is the computational part of the ability to achieve goals in the world. Varying kinds and degrees of intelligence occur in people, many animals and some machines. What is Intelligence? Intelligence: – “the capacity to learn and solve problems” (Websters dictionary) – in particular, the ability to solve novel problems the ability to act rationally the ability to act like humans Artificial Intelligence – build and understand intelligent entities or agents – 2 main approaches: “engineering” versus Success Stories Deep Blue defeated the reigning world chess champion Garry Kasparov in 1997 AI program proved a mathematical conjecture (Robbins conjecture) unsolved for decades During the 1991 Gulf War, US forces deployed an AI logistics planning and scheduling program that involved up to 50,000 vehicles, cargo, and people Can Computers Talk? This is known as “speech synthesis” – translate text to phonetic form e.g., “fictitious” -> fik-tish-es – use pronunciation rules to map phonemes to actual sound Difficulties – sounds made by this “lookup” approach sound unnatural – sounds are not independent – a harder problem is emphasis, emotion, etc humans understand what they are saying Conclusion: – NO, for complete sentences – YES, for individual words Can Computers Recognize Speech? Speech Recognition: – mapping sounds from a microphone into a list of words – classic problem in AI, very difficult “Lets talk about how to wreck a nice beach” (I really said “________________________”) Recognizing single words from a small vocabulary systems of 99%) can do this with high accuracy (order Alan M Turing, Hero Helped to found theoretical CS – 1936, before digital computers existed Helped to found practical CS – wartime work decoding Enigma machines – ACE Report, 1946 Helped to found practical AI – first (simulated) chess program Helped to found theoretical AI … 47 Can Computers “see”? Recognition v. Understanding (like Speech) – Recognition and Understanding of Objects in a scene look around this room you can effortlessly recognize objects human brain can map 2d visual image to 3d “map” Why is visual recognition a hard problem? What did Turing think? Turing (in 1950) believed that by 2000 – computers available with 128Mbytes storage – programmed so well that interrogators have only a 70% chance after 5 minutes of being right “By 2000 the use of words and general educated opinion will have altered so much that one will be able to speak of machines thinking without expecting to 49 be contradicted” Turing Test Three rooms contain a person, a computer, and an interrogator. The interrogator can communicate with the other two by teleprinter. The interrogator tries to determine which is the person and which is the machine. The machine tries to fool the interrogator into believing that it is the person. If the machine succeeds, then we conclude that the machine can think. The Imitation Game Interrogator in one room – computer in another – person in a third room From typed responses only (text-only), can interrogator distinguish between person and computer? If the interrogator often guesses wrong, say the machine is intelligent. 51 Can Machines Think? Turing starts by defining machine & think – Will not use everyday meaning of the words otherwise we could answer by Gallup poll – Instead, use a different question closely related, but unambiguous “I believe the original question to be too meaningless to deserve discussion” 52 A sample game Turing suggests some Q & A’s: Q: Please write me a sonnet on the subject of the Forth Bridge A: Count me out on this one, I never could write poetry Q: Add 34957 to 70764. – (pause about 30 seconds) A: 105621 Q: Do you play chess? A: Yes Q: I have K at my K1, and no other pieces. You have only K at K6 and R at R1. It is your move. What do you play? – (pause about 15s) A: R-R8 mate 53 Some Famous Imitation Games 1960s ELIZA – Rogerian psychotherapist 1970s SHRDLU – Blocks world reasoner 1980s NICOLAI – unrestricted discourse 1990s Loebner prize – win $100,000 if you pass the test 54 “Chinese room” argument [Searle 1980] image from http://www.unc.edu/~prinz/pictures/c-room.gif Person who knows English but not Chinese sits in room Receives notes in Chinese Has systematic English rule book for how to write new Chinese characters based on input Chinese characters, returns his notes – Person=CPU, rule book=AI program, really also need lots of paper (storage) – Has no understanding of what they mean – But from the outside, the room gives perfectly reasonable answers in Chinese! Searle’s argument: the room has no intelligence in it! Some AI videos Note: there is a lot of AI that is very valuable! http://www.youtube.com/watch?v=ICgL1OWsn58&feature=related http://www.youtube.com/watch?v=HacG_FWWPOw&feature=related http://videolectures.net/aaai07_littman_ai/ http://www.ai.sri.com/~nysmith/videos/SRI_AR-PA_AAAI08.avi http://www.youtube.com/watch?v=ScXX2bndGJc