Bil682 Yapay Anlayış Artificial Intelligence Güz 2011 Dr. Nazlı İkizler Cinbiş

Bil682 - Yapay Anlayış Artificial Intelligence

• Güz 2011

• Dr. Nazlı İkizler Cinbiş

• Slides mostly adapted from AIMA

What is AI?

• A system is rational if it does the right thing given what it knows

Acting humanly: Turing Test

• Alan Turing (1950) "Computing machinery and intelligence":

• Operational test for intelligent behavior: the Imitation Game

• The computer passes the test if a human interrogator, after posing some written questions, cannot tell whether the written responses come from a person or not. If the response of a computer to an unrestricted textual natural-language conversation cannot be distinguished from that of a human being then it can be said to be intelligent.

• Suggested major components of AI: Natural Language Processing, Knowledge Representation, Automated Reasoning, Machine Learning

• Total Turing Test: requires Computer Vision and Robotics as well

Thinking humanly: cognitive modeling

• In order to say that a given program thinks like a human, we must have some way of determining how humans think

• Requires scientific theories of internal activities of the brain

• -- How to validate? Requires

• 1) Cognitive Science: Predicting and testing behavior of human subjects (top-down)
• or 2) Cognitive Neuroscience: Direct identification from neurological data (bottom-up)

• Both approaches (roughly, Cognitive Science and Cognitive Neuroscience) are now distinct from AI

Thinking rationally: "laws of thought"

• Aristotle: what are correct arguments/thought processes?

• Several Greek schools developed various forms of logic: notation and rules of derivation for thoughts; may or may not have proceeded to the idea of mechanization

• Formalize “correct” reasoning using a mathematical model(e.g. of deductive reasoning).

• Direct line through mathematics and philosophy to modern AI : logicist tradition hopes to build logic programs to create intelligent systems

• Problems:

• Informal knowledge may not be represented in formal terms of logic.
• Solving problems in principle is different than solving in practice.

Acting rationally

• Rational behavior: doing the right thing

• The right thing: that which is expected to maximize goal achievement, given the available information
• Doesn't necessarily involve thinking – e.g., blinking reflex
• But thinking should be in the service of rational action
• Entirely dependent on goals
• Irrational != insane, irrationality is a suboptimal action
• Rational != successful

Rational agents

• An agent is an entity that perceives its environment and is able to execute actions to change it.

• Abstractly, an agent is a function from percept histories to actions:

• [f: P*  A]

• For any given class of environments and tasks, we seek the agent (or class of agents) with the best performance

Rational agents

• Agents have inherent goals that they want to achieve (e.g. survive, reproduce).

• A rational agent acts in a way to maximize the achievement of its goals.

• True maximization of goals requires omniscience and unlimited computational abilities.

• In real world, usually lots of uncertainty

• Usually, we’re just approximating rationality

•  design best program for given machine resources and available knowledge

Foundations of AI

• Philosophy Logic, methods of reasoning, mind as physical system foundations of learning, language, rationality

• Mathematics Formal representation and proof algorithms, computation, (un)decidability, (in)tractability, probability

• Economics utility, decision theory

• Neuroscience physical substrate for mental activity

• Psychology phenomena of perception and motor control, experimental techniques

• Computer Science hardware, algorithms, computational complexity theory, fast computers

• Control theory design systems that maximize an objective function over time

• Linguistics knowledge representation, grammar, syntax, semantics

Abridged history of AI

• 1943 McCulloch & Pitts: Boolean circuit model of brain

• 1950 Turing's "Computing Machinery and Intelligence"

• 1956 Dartmouth meeting: "Artificial Intelligence" adopted

• 1952—69 Look, Ma, no hands!

• 1950s Early AI programs, including Samuel's checkers program, Newell & Simon's Logic Theorist, Gelernter's Geometry Engine

• 1965 Robinson's complete algorithm for logical reasoning

• 1960s Work in the sixties at MIT lead by Marvin Minsky and John McCarthy

• 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 world

Abridged history of AI

• 1966—73 AI discovers computational complexity Neural network research almost disappears

• 1969—79 Early development of knowledge-based systems

• 1980-- AI becomes an industry

• 1986-- Neural networks return to popularity

• 1987-- AI becomes a science

• 1995-- The emergence of intelligent agents

Early Limitations

• Hard to scale solutions to toy problems to more realistic ones due to difficulty of formalizing knowledge and combinatorial explosion of search space of potential solutions.

• Limitations of Perceptron demonstrated by Minsky and Papert (1969).

Knowledge is Power: Expert Systems

• Discovery that detailed knowledge of the specific domain can help control search and lead to expert level performance for restricted tasks.

• First expert system DENDRAL for interpreting mass spectrogram data to determine molecular structure by Buchanan, Feigenbaum, and Lederberg (1969).

• Early expert systems developed for other tasks:

• MYCIN: diagnosis of bacterial infection (1975)
• PROSPECTOR: Found molybendum deposit based on geological data (1979)
• R1: Configure computers for DEC (1982)

AI Industry

• Development of numerous expert systems in early eighties.

• Estimated $2 billion industry by 1988.

• Japanese start “Fifth Generation” project in 1981 to build

• intelligent computers based on Prolog logic programming.

• MCC established in Austin in 1984 to counter Japanese project.

• Limitations become apparent, prediction of AI Winter

• Brittleness and domain specificity
• Knowledge acquisition bottleneck

Rebirth of Neural Networks

• New algorithms (e.g. backpropagation) discovered for training more complex neural networks (1986).

• Cognitive modeling of many psychological processes using neural networks, e.g. learning language.

• Industrial applications:

• Character and hand-writing recognition
• Speech recognition
• Processing credit card applications
• Financial prediction
• Chemical process control

What Can AI Do?

• Quiz: Which of the following can be done at present?

• 
  Play a decent game of table tennis?

• 
  Drive safely along a curving mountain road?

• 
  Drive safely along busy traffic?

• 
  Buy a week's worth of groceries on the web?

• 
  Discover and prove a new mathematical theorem?

• 
  Converse successfully with another person for an hour?

• 
  Perform a complex surgical operation?

• 
  Unload a dishwasher and put everything away?

• 
  Translate spoken Chinese into spoken English in real time?

• 
  Write an intentionally funny story?

State of the Art

• Deep Blue defeated the reigning world chess champion Garry Kasparov in 1997

• Proved a mathematical conjecture (Robbins conjecture) unsolved for decades

• No hands across America (driving autonomously 98% of the time from Pittsburgh to San Diego)

• 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

• Proverb solves crossword puzzles better than most humans

NASA's on-board autonomous planning program controlled the scheduling of operations for a spacecraft

• NASA's on-board autonomous planning program controlled the scheduling of operations for a spacecraft

• Sojourner, Spirit, and Opportunity explore Mars.
• NASA Remote Agent in Deep Space I probe explores solar system.

• DARPA grand challenge: Autonomous vehicle navigates across desert and then urban environment.

• iRobot Roomba automated vacuum cleaner, and PackBot used in Afghanistan and Iraq wars.

• Spam filters using machine learning.

• Question answering systems automatically answer factoid questions.

• Usable machine translation thru Google.

Recent Times

• General focus on learning and training methods to address knowledge-acquisition bottleneck.

• Shift of focus from rule-based and logical methods to probabilistic and statistical methods (e.g. Bayes nets, Hidden Markov Models).

• Increased interest in particular tasks and applications

• Data mining
• Machine Learning
• Intelligent agents and Internet applications(softbots, believable agents, intelligent information access)
• Scheduling/configuration applications

Fields of AI

• Machine Learning

• Computer Vision

• Speech Recognition

• Natural Language Processing

• Data Mining

• Information Retrieval

• Game programming

• Robotics, Planning

• …

About this course

• Discussion of recent research problems

• Theory and Applications

• Hands-on Experience

About this course: Resources

• Course Book:

• Artificial Intelligence: A Modern Approach, 3/E Stuart Russell Peter Norvig

• ISBN-10: 0136042597

• ISBN-13:  9780136042594

• Publisher:  Prentice Hall Format:  Cloth; 1152 pp Published:  12/01/2009

• Book on Learning:

• Machine Learning, Tom Mitchell, McGraw Hill, 1997.

• Additional Readings:

• Research papers

Course Contents

• Search

• Uninformed, Informed, Constraint Satisfaction

• Game Playing

• Learning

• Supervised Learning, Bayesian Learning
• Decision Trees, Adaboost
• Neural Nets
• Hidden Markov Models
• Reinforcement Learning

• Applications and Research Problems on

• Computer Vision
• Natural Language Processing
• …

Evaluation

• Paper presentation %20

• Presentation %15
• Peer review %5

• Participation %10

• Participation to presentations

• Project %35

• Intermediate report %10
• Final report %25

• Final Exam %35

Project

• Each student should decide on a research project related to a field of AI.

• Project Deadlines

• Project proposals due : 19.10.2011
• Intermediate project report due: 18.11.2011
• Final report due: 26.12.2011

Reading Assignment

• Alan Turing’s “Computing Machinery and Intelligence” (1950)

• First vision of AI