1Foundations of Artificial IntelligenceIntroductionCS472 – Fall 2007Thorsten JoachimsReading: R&N Chapter 1.Lecture and ProjectCS472: Foundations of Artificial Intelligence– Instructor: Prof. Thorsten Joachims – Lecture– Introduction to AI techniques– Agents, Search, CSP, Machine Learning, Planning, Reasoning, Knowledge Representa-tion, Reinforcement LearningCS473: Practicum in Artificial Intelligence– Instructor: Prof. HodLipson– Project– Hands-on experience with AI methods– Meets separate from CS472– CS472 is co-requisiteContactWhere: Philips 219When: Mon, Wed, Fri 11:15-12:05Professor: Thorsten Joachims, Computer ScienceEmail: [email protected]: www.cs.cornell.edu/People/tjOffice Hours: 4153 Upson, We 1:30-2:30 Course web site: www.cs.cornell.edu/courses/CS472/2007fa/Teaching Assistants:Thomas Finley, Alexander Chao, Ilya Sukhar, Griffin Dorman, Rick KeiltyÆOffice hours posted on-line.SyllabusProblem solvingprinciples of search, uninformed search, informed (“heuristic”) search, constraint satisfaction, local search, genetic algorithms, game playingLearninginductive learning, decision tree learning, statistical approaches, support vector machines, kernels, neural networks Knowledge representation and reasoningknowledge bases and inference, propositional and first-order logic, theorem-proving, planning Natural language understandingsyntactic processing, ambiguity resolution, text understandingGeneral InformationText:Artificial Intelligence: A Modern ApproachRussell and Norvig, Prentice-Hall, Inc., second edition.Class Notes and Handouts:Available from course web site / CMS Homework: approx. 6 homework assignmentsExaminations: two prelims, one final exam.Prerequisites:programming and data structures (CS211 or CS312), basic discrete math (CS280), basic linear algebraGrading PolicyAssignments 45%Prelims 25%Final Exam 25%Participation/Interest 5%Late assignments drop 5% per each late day.Roughly: A=93-100; B=83-87; C=73-77; D=63-67; F= below 602Today’s LectureWhat is Artificial Intelligence (AI) anyway?- the components of intelligenceThe Current Frontier- recent achievementsCurrent Challenges- what makes AI problems hard?What is Intelligence?Intelligence:- ``the capacity to learn and solve problems''(Webster dictionary)- the ability to think and act rationallyGoal in Artificial Intelligence:- build and understand intelligent systems/agents- synergy between• philosophy, psychology, and cognitive science• computer science and engineering• mathematics and physicsWhat is involved in IntelligenceA) Ability to interact with the real world- to perceive, understand, and act- speech recognition, understanding, and synthesis- image understanding (computer vision)B) Reasoning and Planning- modeling the external world- problem solving, planning, and decision making- ability to deal with unexpected problems, uncertaintyC) Learning and Adaptation- we are continuously learning and adapting- Also: we want systems that adapt to us!- Major thrust of industry research.What is Artificial IntelligenceRich and Knight: the study of how to make computers do things which, at the moment, people do better.Handbook of AI: the part of computer science concerned with designing intelligent computer systems, that is, systems that exhibit the characteristics we associate with intelligence in human behavior -understanding language, learning, reasoning, solving problems, etc.Dean, Allen and Aloimonos: the design and study of the computerprograms that behave intelligently.Russell and Norvig: the study of [rational] agents that exist in an environment and perceive and act.Different ApproachesI Building exact models of human cognition• view from psychology and cognitive scienceII The logical thought approach• emphasis on ``correct'' inferenceIII Building rational ``agents''• agent: something that perceives and acts• emphasis on developing methods to match or exceed human performance [in certain domains]. Example: Deep Blue.Our focus is on III (most recent progress).Goals in AIEngineering GoalTo solve real-world problems. Build systems that exhibit intelligent behavior.Scientific GoalTo understand what kind of computational mechanisms are needed for modeling intelligent behavior.3Turing Test• Interrogator asks questions of two “people” who are out of sight and hearing. One is a person; the other is a machine.• 30 minutes to ask whatever he or she wants.• Task: to determine, only through the questions and answers typed into a computer terminal, which is which• If can't reliably distinguish the human from the computer, then the computer is deemed intelligent.Artificial intelligence is the enterprise of constructing an artifact that can pass the Turing test.Objections to Turing Test?Newell and Simon [1976]• Turing test is as much a test of the judge as it is of the machine.• Promotes the development of artificial con-artists, not artificial intelligence (Loebner competition).The Current FrontierInteresting time for AIDeep Blue vs. Kasparov (May, '97)- first match won against world-champion- ``intelligent & creative'' play- 200 million board positions per secondKasparov: “I could feel - I could smell - a new kind of intelligence across the table.”... still understood 99.9% of Deep Blue's moves.Intriguing issue: How does human cognition deal with the combinatorics of chess?Different Algorithm, Similar BehaviorDrew McDermott (New York Times, May, 1997):Saying Deep Blue doesn't really think about chess is like saying an airplane doesn't really fly because it doesn't flap its wings. ftp://ftp.cs.yale.edu/pub/mcdermott/papers/deepblue.txtThe brain- a neuron is the basic processing unit ( 1011)- many more synapses (1014) connect the neurons- cycle time: 10-3seconds (1 millisecond)How complex can we make computers?-108 (Itanium) or more transistors per CPU- supercomputer: thousands of CPUs, 1011bits of RAM- cycle times: order of 10-9secondsExamples, cont.•First “creative” proof by computer (Nov, '96)- 60 year open problem. - Robbins' problem in finite algebra.Qualitative difference from previous brute-force results.Does technique generalize?(Our own expert: Robert Constable.)Machine Learning• TD Gammon (Tesauro 1993; 1995)- World champion level but learns from scratch byplaying millions of games against itself!- Has changed human play• ALVINN (Pomerleau 1993)- Neural net used to steer vehicle in coast-to-coast highway driving- Speeds of up to 90 mph- DARPA