1CS 343: Artificial IntelligenceIntroduction2Definition of AI•“The art of creating machines that perform functions thatrequire intelligence when performed by people” (Kurzweil,1990).•“The branch of computer science that is concerned with theautomation of intelligent behavior.” (Luger and Stublefield,1993)Systems that think like humans. Systems that think rationally.Systems that act like humans. Systems that act rationally.3Acting Humanly: The Turing Test•If the response of a computer to an unrestricted textualnatural-language conversation cannot be distinguishedfrom that of a human being then it can be said to be intelligent.•Loebner Prize: Current contest for restricted form of theTuring test.?Hi! Are you a computer?No. My name is Mary.Are you kidding, I’m Hal and Ican’t even multiply two-digitnumbers!4Thinking Humanly: Cognitive Modelling•Method must not just exhibit behavior sufficient to fool ahuman judge but must do it in a way demonstrablyanalogous to human cognition.•Requires detailed matching of computer behavior andtiming to detailed measurements of human subjectsgathered in psychological experiments.•Cognitive Science: Interdisiplinary field (AI, psychology,linguistics, philosophy, anthropology) that tries to formcomputational theories of human cognition.5Thinking Rationally: Laws of Thought•Formalize “correct” reasoning using a mathematical model(e.g. of deductive reasoning).•Logicist Program: Encode knowledge in formal logicalstatements and use mathematical deduction to performreasoning:Problems:-Formalizing common sense knowledge is difficult.-General deductive inference is computationallyintractable.6Acting Rationally: Rational Agents•An agent is an entity that perceives its environment and isable to execute actions to change it.•Agents have inherent goals that they want to achieve (e.g.survive, reproduce).•A rational agent acts in a way to maximize the achievementof its goals.•True maximization of goals requires omniscience andunlimited computational abilities.•Limited rationality involves maximizing goals within thecomputational and other resources available.7Foundations of AI•Many older disciplines contribute to a foundation forartificial intelligence:-Philosophy: logic, philosophy of mind, philosophy ofscience, philosophy of mathematics-Mathematics: logic, probability theory, theory ofcomputability-Psychology: behaviorism, cognitive psychology-Computer Science & Engineering: hardware, algorithms,computational complexity theory-Linguistics: theory of grammar, syntax, semantics8Birth•McCullouch and Pitts (1943) theory of neurons as logicalcomputing circuits.•Work in early 50’s by Claude Shannon and Turing on gameplaying and Marvin Minsky on neural networks.•Dartmouth conference (1956)-Organized by John McCarthy attended by Marvin Minsky,Allen Newell, Herb Simon, and a few others.-Coined term “artificial intelligence.”-Presentation of game playing programs and LogicTheorist.9Early Years•Development of General Problem Solver by Newell andSimon in early sixties.•Arthur Samuel’s late fifties work on learning to playcheckers.•Frank Rosenblatt’s Perceptron (1962) for training simpleneural networks•Work in the sixties at MIT lead by Marvin Minsky and JohnMcCarthy-Development of LISP symbolic programming language-SAINT: Solved freshman calculus problems-ANALOGY: Solved IQ test analogy problems-SIR: Answered simple questions in English-STUDENT: Solved algebra story problems-SHRDLU: Obeyed simple English commands in theblocks world10Early Limitations•Hard to scale solutions to toy problems to more realisticones due to difficulty of formalizing knowledge andcombinatorial explosion of search space of potentialsolutions.•Limitations of Perceptron demonstrated by Minsky andPapert (1969).11Knowledge is Power: Expert Systems•Discovery that detailed knowledge of the specific domaincan help control search and lead to expert levelperformance for restricted tasks.•First expert system DENDRAL for interpreting massspectrogram data to determine molecular structure byBuchanan, Feigenbaum, and Lederberg (1969).•Early expert systems developed for other tasks:-MYCIN: diagnosis of bacterial infection (1975)-PROSPECTOR: Found molybendum deposit based ongeological data (1979)-R1: Configure computers for DEC (1982)12AI Industry•Development of numerous expert systems in early eighties.•Estimated $2 billion industry by 1988.•Japanese start “Fifth Generation” project in 1981 to buildintelligent computers based on Prolog logic programming.•MCC established in Austin in 1984 to counter Japaneseproject.•Limitations become apparent, prediction of AI Winter-Brittleness and domain specificity-Knowledge acquisition bottleneck13Rebirth of Neural Networks•New algorithms discovered for training more complexneural networks (1986).•Cognitive modelling of many psychological processes usingneural networks, e.g. learning language.•Industrial applications:-Character and hand-writing recognition-Speech recognition-Processing credit card applications-Financial prediction-Chemical process control14Recent Times•General focus on learning and training methods to addressknowledge-acquisition bottleneck.•Shift of focus from rule-based and logical methods toprobabilistic and statistical methods (e.g. Bayes nets,Hidden Markov Models).•Increased interest in particular tasks and applications-Data mining-Intelligent agents and Internet applications(softbots, believable agents, intelligent informationaccess)-Scheduling/configuration applications(Successful companies: I2, Red Pepper,