Chapter 1
Artificial Intelligence tries to understand how we think, perceive, understand, predict, and manipulate the world…and how to build intelligent entities that. 
AI tries to automate intellectual tasks, which makes it a universal field. 
1.1 What is AI?
Concerned with thought processes, reasoning and behavior. Comparisons are made to human performance, as well as the ideal concept of intelligence, which we call rationality. A system is rational if it does the “right thing” given what it knows. 
Systems that think like humans	Systems that think rationally
Systems that act like humans	Systems that act rationally
Acting humanly: The Turing Test approach
The Turing Test, proposed by Alan Turing, to provide a satisfactory operational definition of intelligence. The test is based on the indistinguishability of behavior from that of a human. The entity passes the test if a human interrogator, after posing some written questions, cannot tell whether the responses come from a person or not. 
In general, the entity would need these things: 
•	Natural language processing for communication
•	Knowledge representation for storage of knowledge
•	Automated reasoning to answer questions and draw new conclusions
•	Machine learning to adapt to new circumstances and identify patterns
Newer additions to these requirements are based on robotic implementations of AI. The include: 
•	Computer vision for perception of objects
•	Robotics to manipulate objects
These 6 disciplines compose most of AI. 
Thinking humanly: the cognitive modeling approach
Introspection and psychological experiments to get inside the actual workings of the human mind. 
Allen Newell and Herbert Simon developed GPS, the “General Problem Solver,” that solved problems. They didn’t care about the solution as much as the process to arrive at the solution. The field of cognitive science brings AI computer models and psychology’s experimental techniques to construct precise and testable theories of the workings of the human mind. 
Real cognitive science is necessarily based on experimental investigation of humans or animals. 
Thinking rationally: the “laws of thought” approach
Aristotle’s syllogisms were descriptions of what were initially thought to govern the operation of the human mind. This initiated the field of logic. 
A logicist hopes to build on programs that can, in principle, solve any solvable problem in order to create intelligent systems. There are two main problems with this: 
•	It’s not easy to state informal knowledge in formal terms, especially when the knowledge is not 100% certain. 
•	There’s a difference between being able, in principle, to solve a problem…and in being able to do so in practice. Some of this has to do with storage resources, and some with problem intractability. 
Acting rationally: the rational agent approach
An agent is something that acts. Computer agents differ from programs in that they operate autonomously, perceive their environment, persist over long periods, adapt to change, and are capable of taking on another’s goals. A rational agent is one that acts to achieve the best outcome or, when there is uncertainty, the best expected outcome. 
Making correct inferences is part of being rational, but some ways of acting do not involve inference. 
We need to be able to represent knowledge and reason with it so we can reach good decisions in a wide variety of situations. Having a better understanding of “how the world works” helps to generate more effective strategies for dealing with it. 
The study of AI as rational-agent design has a few advantages: 
•	It’s more general than the “laws of thought” approach, correct inference is just one of several possible mechanisms for achieving rationality. 
•	More amenable to scientific development than are approaches based on human behavior because rationality is more clearly defined and completely general (human behavior evolved in a mostly not-understood way)
Achieving perfect rationality is not feasible in complicated environments. Later we may discuss limited rationality, acting appropriately when there is not enough time to do all the computations. 

1.2 The Foundations of Artificial Intelligence
Philosophy (428 BC to present)
•	Can formal rules be used to draw valid conclusions? 
•	How does the mental mind arise from the physical brain?
•	Where does knowledge come from?
•	How does knowledge lead to action?
•	Aristotle
o	Syllogisms for reasoning
•	Ramon Lull
o	Reasoning can be carried out by a mechanical artifact
o	Concept Wheels (cover of book)
•	Thomas Hobbes
o	Reasoning is like numerical computation
•	Leonardo da Vinci
o	Mechanical calculator’s design
•	Blaise Pascal
o	“Pascaline” calculator
•	Gottfried Wilhelm Leibniz
o	Mechanical device to carry out operations on concepts, limited
•	Renè Descartes
o	First discussion of the distinction between mind and matter and the problems that arise
o	Proponent of dualism, that the mind/soul/spirit is outside of nature, exempt from physical laws…but animals are exempt and can be treated like machines. 
•	Materialism is the opposite to dualism, says that the brain’s operation according to the laws of physics constitutes the mind. Free will is the way that perception of choices appears during this process.
•	Francis Bacon, also, separately, John Locke
o	Empiricism, which includes induction, that general rules are acquired by exposure to repeated associations between their elements. 
•	Bertrand Russell and Ludwig Wittgenstein
o	Logical positivism, that all knowledge can be characterized by logical theories connected to observation sentences that correspond to sensory input
•	Carnap and Carl Hempel
o	Confirmation theory about how knowledge is acquired by experience
o	First theory of the mind as a computational process. 
•	Connection between knowledge and action, AI requires both. 
Mathematics (c.800 to present)
•	What are the formal rules to draw valid conclusions?
•	What can be computed?
•	How do we reason with uncertain information?
•	Contributed mathematical formalization (and thus leaps in development) to: 
o	Logic
o	Computation
o	Probability
•	George Boole
o	Propositional/Boolean logic
•	Gottlob Frege
o	Extended Boole’s stuff to first order logic, the most basic knowledge representation system
•	Alfred Tarski
o	Theory of reference that shows how to relate the objects in a logic to objects in the real world
•	Euclid
o	First nontrivial algorithm, computed the greatest common denominators
•	Al-Khowarazmi (Persian)
o	Algorithms as objects
o	Brought Arabic numerals and algebra to Europe
•	David Hilbert
o	23 problems that would occupy mathematicians for the bulk of the century
o	Is there an algorithm for deciding the truth of any logical proposition involving the natural numbers? (the “decision problem”) Which meant “are there fundamental limits to the power of effective proof procedures?”
•	Kurt Godel
o	There exists an effective procedure to prove any true statement in the first-order logic of Frege and Russell, but that first-order logic cannot capture the principle of mathematical induction needed to characterize the natural numbers
o	Real limits do exist
o	Incompleteness theorem that in any language expressive enough to describe the properties of natural numbers, there are true statements that are undecidable in the sense that their truth cannot be established by any algorithms
•	Church-Turing thesis showed that no machine can tell in general whether a given program will return an answer on a given input or run forever
•	Intractability, the time to solve instances of the problem grows exponentially with the size of the instances. In general you want to break problems down into smaller tractable subproblems rather than intractable ones. 
•	Stephen Cook & Richard Karp
o	Intractable problems can be recognized by using the theory of NP completeness. Any problem class to which the class of NP-complete problems can be reduced to is likely intractable. Some are solvable, though. AI has helped explain why some of them are hard and others are easy. 
•	Gerolamo Cardano
o	Probability, possible outcomes of gambling events. Invaluable in quantitative sciences. 
•	Thomas Bayes
o	Rule for updating probabilities in light of new evidence. Bayes’ rule and the resulting field called Bayesian analysis form the basis of most modern approaches to uncertain reasoning in AI
Economics (1776-present)
•	How should we make decisions so that we maximize payoff?
•	How should we do this when others may not go along?
•	How should we do this when the payoff may be far in the future?
•	Adam Smith (1776, Scotland)
o	First to treat economics as a science 
o	Economies as individual agents maximizing their own economic well-being
•	Most economists will tell you they are really studying how people make choices that lead to preferred outcomes
•	Léon Walras (then Frank Ramsey, then John Von Neumann and Oskar Morgenstern
o	Mathematical treatment of preferred outcomes utility
•	Decision theory combines probability theory and utility theory, provides a formal and complete framework for decisions (economic and otherwise) made under uncertainty
•	John Von Neumann and Oskar Morgenstern
o	Game theory for small economies, the actions of one player can significantly affect the utility of another, for some games a rational agent should act in a random fashion, or at least in a fashion that appears random to adversaries
•	Operations research how to make rational decisions when payoffs are distant and when actions to get that payoff must be taken in sequence
•	Richard Bellman
o	Markov decision processes are classes of sequential decision problems
•	Herbert Simon
o	Book leads up to him by talking about complexity of making rational decisions
o	Simon did work on satisficing, making decisions that are “good enough” rather than laboriously calculating an optimal decision, and that this gives a better description of actual human behavior. 
Neuroscience (1861 – present)
•	How do brains process information? 
•	Neuroscience – the study of the nervous system and the brain in particular. 
•	Paul Broca
o	Study of speech deficit in brain-damaged patients
o	Persuaded the medical establishment of localized areas of the brain responsible for specific cognitive functions, that speech production was on the left hemisphere of the brain (Broca’s area)
•	Camillo Golgi 
o	Staining technique allowing the observation of individual neurons in the brain
•	Other areas of the brain can take over functioning when the “normal” area is damaged
•	Interesting conclusion: that a collection of simple cells can lead to thought, action, and consciousness or, in other words, that brains cause minds. 
Psychology (1879 – present)
•	How do humans and animals think and act? 
•	Hermann von Helmholtz
o	Father of psychology
•	Wilhem Wundt
o	First lab of experimental psychology in Leipzig
•	H. S. Jennings
o	Behaviorism rejected any theory of (studying one’s own) mental processes on the grounds that the subjective nature of introspection would not provide reliable evidence.
•	Behaviorists insisted on studying only objective measures of the percepts (or stimulus) given to an animal and the resulting actions (responses). Discovered a lot about rats and pigeons, but not so much about humans. 
•	William James
o	Father of cognitive psychology, the view that the brain is an information processing device. 
•	Kenneth Craik
o	Three key steps of a knowledge-based agent
	The stimulus must be translated into an internal representation
	The representation is manipulated by cognitive processes to derive new internal representations
	These are in turn retranslated back into action
•	Cognitive science likely began in America at a workshop at MIT in September, 1956. Noam Chomsky, George Miller, Allen Newell and Herbert Simon. 
Computer engineering (1940-present)
•	How can we build an efficient computer?
•	For AI to succeed we need intelligence and an artifact
•	Alan Turing (and team)
o	1940 First operational computer, the electromechanical Heath Robinson, built to decipher German messages
o	1943 Colossus: general purpose machine based on vacuum tubes
•	ENIAC – most influential forerunner of modern computers, started by secret military project
•	Joseph Mari Jacquard
o	First programmable device – loom that used punch cards for the desired pattern to be woven
•	Charles Babbage
o	Two machines designed, neither completed
o	Difference Engine compute math tables for engineering and scientific projects
o	Analytical Engine included addressable memory, stored programs, conditional jumps, and was the first artifact capable of universal computation
•	Ada Lovelace (Babbage’s colleague)
o	World’s first programmer? Wrote programs for his device(s?)
•	AI pioneered a number of things for computer science
o	Time sharing, interactive interpreters, personal computers with windows and mice, rapid development environments, the linked list data type, automatic storage management and key concepts in symbolic, functional, dynamic and object-oriented programming
Control theory and cybernetics (1948 -  present)
•	How can artifacts operate under their own control? 
•	Ktesibios of Alexandria (c. 250 BC)
o	First self-controlling machine: water clock with a regulator that kept the flow of water running through it at a constant, predictable pace…could modify its own behavior
•	Mathematical theory of stable feedback systems in 19th century
•	Norbert Wiener (worked with Bertrand Russell)
o	Central figure in creation of control theory. 
o	Viewed purposive behavior as arising from a regulatory mechanism trying to minimize “error” – the difference between current state and goal state
•	Modern control theory, especially a branch known as stochastic optimal control, has the goal of designing systems that maximize objective function over time
•	Calculus and matrix algebra, tools of control theory, lead to systems describable by fixed sets of continuous variables. Exact analysis is feasible only for linear systems. AI was founded in part as a way to escape from the limitations of mathematics and control theory in the 1950s
Linguistics (1957 – present)
•	How does language relate to thought?
•	B. F. Skinner
o	Comprehensive, detailed account of behaviorist approach to language learning, almost killed off behaviorism
•	Noam Chomsky 
o	Showed that behaviorist theory did not address the notion of creativity in language, that it did not explain how a child could understand and make up sentences he’d never heard before. 
o	Syntactic models did explain this and was formal enough to be programmed
•	AI was created and grew with linguistics, with hybrid fields called computational linguistics or natural language processing
•	Linguistics study and AI were linked to study of knowledge representation
1.3 the history of artificial intelligence 

Gestation of AI (1943 – 1955)
•	Warren McCulloch and Walter Pitts
o	First work on AI
o	Three sources: 
	Knowledge of the basic physiology and function of neurons in the brain
	A formal analysis of propositional logic due to Russell and Whitehead
	Turing’s theory of computation
o	Proposed a model of artificial neurons which were either on or off an switched based on stimuli, computable functions could be computed by networks of the neurons, suggested that these networks could learn
•	Donald Hebb
o	Simple updating rule for modifying the connection strengths between neurons, called Hebbian learning
•	Marvin Minsky and Dean Edmonds
o	At Harvard (undergrad), built first neural network computer, the SNARC, used vacuum tubes and B-24 pilot mechanism
o	Minsky later proved influential theorems showing the limitations of neural network research
•	Alan Turing
o	Turing test, machine learning, genetic algorithms, reinforcement learning
The birth of AI (1956)
•	John McCarthy
o	He named the field of study “artificial intelligence”
o	Brought together people from automata theory, neural nets, study of intelligence
o	2 month workshop at Dartmouth
•	Why isn’t AI a branch of mathematics?
o	AI embraced the idea of duplicating human faculties like creativity, self improvement, and language use
o	Methodology: is a branch of computer science. Wanted to build machines that could operate autonomously in complex, changing environments
Early enthusiasm, great expectations (1952 to 1969)
•	Fought against and disproved the critics saying “a machine can never do <blah>”
•	Newell and Simon
o	GPS – general problem solver, imitates human problem-solving protocols within a limited class of puzzles
o	Formulated the physical symbol system hypothesis, which states that “a physical symbol system has the necessary and sufficient means for general intelligent action” means that any system that exhibits intelligence must operate by manipulating data structures composed of symbols (has been challenged frequently)
•	Herbert Gelernter
o	Geometry Theorem Prover – proved theorems that were challenging
•	Arthur Samuel
o	Wrote checkers programs that learned how to play better than he did (illustrating learning)
•	John McCarthy
o	Defined LISP (predominant AI programming language)
o	With a team at MIT, invented time sharing
o	Described the Advice Taker hypothetical program that was the first complete AI system. It used general knowledge of the world , could accept new axioms and thus could achieve competence in new areas without being reprogrammed
o	Started the AI lab at Stanford (responsible for the Shakey robotics project – first to demonstrate the complete integration of logical reasoning and physical activity)
•	Minsky – get programs to work and eventually developed an anti-logical outlook
•	McCarthy – stressed representation and reasoning in formal logic
•	Minsky supervised students who chose limited problems that appeared to require intelligence to solve, these limited domains became known as microworlds. Most famous microworld was the blocks world. 
•	McCulloch and Pitts – early neural network work
•	Winograd and Cowan – large number of elements can collectively represent an individual concept, with a corresponding increase in robustness and parallelism. 
•	Adalines – networks (for learning)
•	Perceptrons – (Rosenblatt) inputs
•	Perceptron convergence theorem – (Rosenblatt) shows that his learning algorithm could adjust the connection strengths of perceptrons to match the input data, given that a match existed
A dose of reality (1966-1973)
•	Herbert Simon made a bunch of overzealous predictions that weren’t fulfilled on his time scale. His misperceptions were based on extending the success of AI on limited inputs to problems of more complex nature. 
o	Chess champion would be bested by a machine (off by 30 years)
o	1st: Early AI wasn’t based on knowledge, but on syntactic manipulation. Translation requires general knowledge of the subject in order to resolve ambiguity. 
o	2nd: some problems were intractable, AI would try different combinations of steps in order to find a solution…but on large inputs that doesn’t work at all! Just because a program can, in principle, find a solution, doesn’t mean it can practically find a solution. 
o	3rd: limitations on basic structures being used to generate intelligent behavior. Minsky and Papert proved that although a perceptron could be shown to learn anything it could represent, it could represent very little. Newer back-propagation algorithms have offered new promise in neural networks. 
•	Machine evolution, now called genetic algorithms, were based on making (random) small mutations on machine code to generate code that would have good performance on specific tasks…but it initially showed no progress. Newer algorithms use better representations and exhibit more success. 
Knowledge-based systems: the key to power? (1969-1979)
•	Weak methods – general purpose search mechanism trying to string together elementary reasoning steps to find complete solutions. Didn’t scale up to difficult problem instances. The alternative is to use more powerful, domain-specific knowledge that allows larger reasoning steps and can more easily handle typically occurring cases in narrow areas of expertise (“almost have to know the answer before you start?”)
•	DENDRAL – first successful knowledge-intensive system: its expertise derived from large numbers of special-purpose rules. 
•	MYCIN – expert system that reasoned on medical conditions, started with 450 rules, performed better than some experts and all junior doctors. 
o	1st: no general theoretical model existed from which Mycin rules could be deduced (unlike DENDRAL). Rules came from doctors and textbooks.
o	2nd: rules had to reflect the uncertainty associated with medical knowledge. Mycin incorporated a calculus of uncertainty called certainty factors, which fit well with how doctors assessed the impact of evidence on diagnosis
•	Eugene Charniak
o	Robust language understanding would require general knowledge about the world and general methods to use that knowledge
•	Minsky
o	Frames – assemble facts about particular object and event types and arrange the types into a large taxonomic hierarchy analogous to biological taxonomy
AI becomes an industry (1980-present)
•	Digital Equipment Corporation (DEC) makes AI system that configures orders for new computer systems, saves them $40M annually. Now something like it is used by every major corporation. 
The return of neural networks (1986-present)
•	John Hopfield
o	Uses techniques from statistical mechanics to analyze the storage and optimization properties of networks, treating collections of nodes like collections of atoms
•	Back propagation learning algorithm revitalizes neural networks
•	Connectionist models of intelligent systems question whether symbolic manipulation has any real explanatory role in the detailed models of cognition
AI becomes a science (1987-present)
•	Now is common to build on existing theories rather than propose new ones
•	AI founded initially in rebellion of other fields, and now embraces them, i.e. statistics, control theory, uncertain reasoning, stochastic modeling
•	Use of the internet with shared repositories of test data and code
•	Speech recognition begins to be dominated by use of hidden Markov models
o	1st: based on rigorous mathematical theory, can use base of years of math research
o	2nd: generated by a process of training on large corpus of real speech data
•	Neural networks also fit this trend, can now be compared against techniques in statistics, pattern recognition, machine learning. As a result of these techniques, data mining has surfaced as a sub-field
•	Judea Pearl
o	Brought about acceptance of probability and decision theory in AI
•	Peter Cheeseman
o	Bayesian network formalism used to allow efficient representation of and reasoning with uncertain knowledge. This largely overcomes problems inherent with probabilistic reasoning systems from 60s and 70s and now dominates AI research on uncertain reasoning and expert systems. 
&#61607;	Allows for learning from experience, combines best of classical AI and neural networks
o	Eric Horvitz and David Heckerman
&#61607;	Promoted the idea of normative expert systems that act rationally according to laws of decision theory and do not try to imitate the thought steps of human experts. 
The emergence of intelligent agents (1995-present)
•	Allen Newell, John Laird, Paul Rosenbloom
o	Best-known example of a complete agent architecture, which attempts to understand the workings of agents embedded in real environments with continuous sensory inputs. The internet is a good example of a great environment for this. 
•	The agent perspective isn’t the only one, but it’s what’s used in this book and, in some sense, is dominant. 
1.4 the state of the art
•	AI has subfields
o	Autonomous planning and scheduling: example: NASA system to detect, diagnose, and recover from errors as they occur
o	Game playing: Deep blue chess computer
o	Autonomous control: ALVINN computer vision system steers a car for 98% of a trip across the US
o	Diagnosis: medical diagnosis based on probabilistic analysis
o	Logistics planning: DART (dynamic analysis and replanning tool) by military cuts down troop movement planning overhead by huge amount, DARPA-based program
o	Robotics: robot assistants in microsurgery
o	Language understanding and problem solving: solves crossword puzzles using constraints on word fillers and context from online databases with current events, dictionaries and word associations

Alan Turing: 
Turing test (1950)
Allan Newell & Herbert Simon: 
“General Problem Solver”
Aristotle: 
Syllogisms