Transcript foundations - Computer Science Department

Philosophical History
• Aristotle and other Greeks developed
the foundations of mathematical logic
• The mind-body dilemma emerged
after the Renaissance
– thinking could be studied separately from
the physical world
– it is necessary to “reconnect” the mind
and the body since the interaction is
essential for human existence
• Mental processes are achieved by
physical systems, such as the brain or
the computer
• Mental processes like physical
processes can be characterized by
formal logic or mathematics
• David Hume said: “Cognition is
computation.”
Development of Logic
• Euler helped develop graph theory
which is a foundation of modeling
search spaces
• Charles Babbage and Ada Lovelace
(his programmer) worked on the
Analytic Engine
• George Boole developed the
mathematics of formal logic
• Frege helped develop the first order
predicate calculus
• In this century, Russell, Whitehead,
and Tarski expanded the development
of logic
Turing's Test
• Questioner:
Aims to discover if A or B is the Computer
• (A) Computer: aims to fool the questioner
(B) Human: aims to help the questioner
• Turing's rationale: "The question and answer method
seems to be suitable for introducing almost any one of the
fields of human endeavor which we wish to include"
(Turing 1950, p.435).
• What questions would you ask to determine whether A or
B is the computer?
• What would be some of the computer’s strategies to fool
the questioner?
The Imitation Game
• Questioner:
Aims to discover if A or B is the Man
• (A) Male: aims to fool the questioner
(B) Female: aims to help the questioner
• Some of Turing’s Comments
• "The [imitation] game may perhaps be criticized on the
ground that the odds are weighted too heavily against the
machine. This objection is a very strong one, but at least
we can say that if, nevertheless, a machine can be
constructed to play the imitation game satisfactorily, we
need not be troubled by this objection" (Turing 1950, p.
435).
• "in about fifty years' time [by the year 2000] it will be
possible to program computers ... to make them play the
imitation game so well that an average interrogator will
have no more than 70 per cent. chance of making the
correct identification after five minutes of questioning."
(Turing 1950, p.442).
The Turing Test
• Proposed by Alan Turing in 1950 in
Computing Machinery and Intelligence
• Features
– provides an objective method for
measuring intelligence
– avoids philosophical issues, such as
whether a machine is conscious
– focuses attention on content and not the
means of delivery
• Weaknesses
– only deals with symbolic problem
solving
– does not include perception or dexterity
• Some questions
– can a computer be original or creative?
– Is it impossible to test enough
circumstances to judge intelligence?
Other Viewpoints
• Herbert Simon
– intelligent behavior is based on richness
of environment and not the complexity of
some internal structure
– culture is an important factor in forming
intelligence
• Alternatives to the rationalists
– language use is based on cultural context
and not some abstract meaning
– intelligence is not knowing what is true
by how to cope in an ever changing
world
• New trends in AI
– connectionist networks
– artificial life and genetic algorithms
– agent-oriented intelligence
Emergent View of Intelligence - 1
• Major features
– Agents are semi-autonomous
– Agents are situated in their local
environment and do not know of the “big
picture”
– Agents are interactional, they cooperate
on a particular task
– The “society” of agents is structured in a
cooperative fashion
– Intelligence emerges from the society as
a whole, it is more than the sum of parts
• Can the brain be viewed as a
collection of agents?
• Where do agents appear in silicon in
modern devices?
Emergent View of Intelligence - 2
• Designing and building such a society
– need to represent knowledge
– need strategies for searching for
alternative solutions
– need architectures to support the
interaction of agents
• How could agents be implemented in
terms of a programming language?
Game Playing
• Much of the early work in AI is based
on solving puzzles or playing games
• Emphasizes the state space search
process (chapters 3 and 4)
• Heuristics
– useful but potential fallible strategy for
solving problems
– heuristics help prune the search space so
that solutions can be found in a
reasonable amount of time
• Heuristics can be used to control the
searching process and can be applied
to expert systems too
Strategies for Tic-Tac-Toe
• How many different arrangements are
there for X’s and O’s for a 3x3 tic-tactoe board, worst case?
• A win is based on “three in a row” for
any row, column, or diagonal
• Devise a strategy to select the best
available move. Try to formulate as
an algorithm.
Automated Reasoning
• Historical roots in theorem proving
– Logic Theorist and General Problem
Solver (1963) from Newell & Simon
– predicate calculus (chapter 2) provides
logical foundations
– Prolog (chapter 9) provides a
programming language implementation
• Limitations
– limited problem domains
– inability to distinguish relevant from
irrelevant
• Applications
– design of logic circuits, program
correctness, complex control systems
– often machines and humans work
cooperatively to solve problems
A Little Help from my Friends
• Think of a situation where human
problem solving can be aided by a
computer. The computer should not
do all the work, rather is should work
cooperatively with the human or be
guided by the human.
Expert Systems
• Encodes theoretical knowledge and
heuristic knowledge based on expert
human problem solvers
• Applications - chemistry (Dendral),
infectious disease (Mycin), oil
(Prospector), internal medicine
(Internist), configuring computer
systems (XCON)
• Limitations
– doesn’t capture “deep” knowledge or
provide “deep” explanations
– lacks robustness and flexibility
– difficult to verify, so often not used in
life-critical applications
– does not learn from experience
Design of an Expert System
• Suppose you want to design an expert
system for simple auto repair to
determine why a car won’t start?
What questions would you have the
computer ask the user?
Natural Language Understanding
• Efforts in language translation
– English-Russian translations motivated
by “cold war”, translation between
European community motivated by
economics in the EEC
– Goes well beyond dictionary and
syntactic knowledge
• Requires extensive knowledge about
the domain of discourse
– often only effective in “blocks world”
domains (e.g., SHRDLU)
– techniques do not generalize
• Current approaches
– try to find formalizes that are general in
structure but can be adapted to a variety
of domains
– examples, semantic networks and
stochastic models
Why is NLP so hard?
• Give some reasons why you think
natural language processing is so
difficult?
Modeling Human Performance
• Many AI applications, even expert
systems, are not concerned with
human internal mental processes
• However, in other areas such as
human cognition or tutoring systems,
modeling internal human performance
is critical
• Cognitive science has adapted many
AI methodologies
– provides a new vocabulary for
developing theories
– provides a means to implement, test, and
refine theories
• Intelligent Tutoring Systems (ITS)
must model human problem solving if
they are to be effective
Teaching Addition
• How would you design an ITS to
teach addition to a fourth grader? You
may assume the students already
know the 10 x 10 single digit addition
table.
Planning and Robotics
• Planning is finding a sequence of
atomic actions to accomplish a
particular goal
– efficiency is an important consideration
– must be able to respond to environmental
changes
• Heuristic problem decomposition is
one approach to planning
• Modern techniques include
interactions of multiple semiautonomous agents
• Planning will be covered in chapters 5
and 9
Planning Research
• Why does NASA fund a significant
amount of planning research?
Machine Learning - 1
• Learning is a critical aspect of
intelligent behavior
• Early applications
– Samuel’s checker playing program
– Automated Mathematician by Lenat
– Meta-DENDRAL learns patterns by
examining spectographic data in organic
chemistry
• Modern approaches
– using connectionist networks to
recognize patterns
– using genetic algorithms
• Although machine learning is a “hot
topic” in AI there has only been
limited success in particular domains
so far
Machine Learning - 2
• Name some situations where you
think machine learning is appropriate?
• What characteristics would you need
in the programming language used to
implement learning?
Emergent Computation
• Neural architectures
– not based on symbols and operations like
traditional AI but modeled after human
neurons in the brain
– knowledge emerges from the entire
system based on network connections
and threshold values
– these systems handle “noise” much better
than symbolic systems
• Advantages
– system is distributed so they are more
robust
– neural systems are more easily
parallelized
• Other emergent models - genetic
algorithms and artificial life
Neural Nets
• Neural nets is a “hot topic” in AI.
What have you heard about neural
nets and their applications?
AI and Philosophy
• AI emerges from western rational
philosophical traditions but can also
contribute to philosophy
• Physical symbol system hypothesis
(Newell and Simon): the necessary
and sufficient condition for a physical
system to exhibit intelligence is that it
be a physical symbol system
• Natural language is an example of a
physical symbol system
• What do you think of Newell and
Simon’s hypothesis? Consider both
the necessary and the sufficient.
Environments for developing AI
• Knowledge structuring
– object-oriented systems
– expert system frameworks
• Programming languages
– Lisp and Prolog are traditional languages
for AI development
– these languages allow for rapid
prototyping of AI systems
– production level tools can be
programmed in imperative or objectoriented languages
• Programming in this class
– small programs will be in Lisp and
Prolog
– the language for the project will be
selected based on the project topic