1: Artificial Intelligence

something that acts
rational agent
an agent that acts to achieve the best outcome
What is the focus of this book
concentrate on general principles of rational agents and on components for constructing them.
what is limited rationality?
acting appropriately when there is not enough time to do all the desired computations
First nontrivial algorithm
Euclid’s algorithm for computing greatest common divisors.
Incompleteness theorem
created by Kurt Godel (1906-1978), shows that in any formal theory as strong as Peano arithmetic (the elementary theory of natural numbers), there are true statements that are undecidable in the sense that they have no proof within the theory
What is computability?
the notion that a result can be represented by an algorithm, that is, that it can be computed.
What is intractable?
a problem is intractable if the time required to solve instances of the problem grows exponentially with the size of the instances.
How can one recognize an intractable problem?
theory of NP-completeness (Steven Cook, 1971) and Richard Karp(1972). Cook and Karp showed existence of large classes of canonical combinatorial search and reasoning problems that are NP-complete.

Any problem class to which the class of NP-complete problems can be reduced is probably intractable.

Theory of Probability
framed by Gerolamo Cardano, described it in terms of the possible outcomes of gambling events.
Expounded on by Blaise Pascal, James Bernoulli, and Thomas Bayes
Thomas Bayes
proposed rule for updating probabilities in the light of new evidence.
Economic questions of AI
1. How should we make decisions so as to maximize payoff?

2. How should we do this when others may not go along?

3. How should we do this when the payoff may be far in the future?

Adam Smith’s contribution to economics and AI?
economics can be thought of as consisting of individual agents maximizing their own economic well-being.
What is utilitiy?
preferred outcomes
What is Decision Theory?
combines probability theory with utility theory to provide a formal and complete framework for decisions made under uncertainty.

This is suitable for large economies where each agent need not pay attention to the actions of other agents

What is Game theory?
study of how actions of one agent can significantly affect the utility of others. Includes the result that, for some games, a rational agent should adopt policies that appear to be randomized.

Suitable for small economies

Who is the pioneering AI researcher?
pHerbert Simon (1916-2001). Won Nobel Prize in economics in 1978 for showing that models based on satisficing – making decisions that are “good enough” rather than laboriously calculating an optimal decision – gave a better description of actual human behavior.
Nicholas Rashevsky
first to apply mathematical models to the study of the nervous system
cell structure
each neuron consists of a cell body that contains the nucleus.

branching from body arefibers called dendrites and a single long fiber called the axon.

neuron makes connections with 10 to 100,000 other neurons at junctions called synapses.

signals are prpagated from neuron to neuron by electrochemical reaction.

Signas control brain activity in the short term and enable long-term changes in the connectivity of neurons. These mechanisms form the basis for learning in the brain.

brain vs computer
computers have cycle time that is a million times faster than a brain.

brain has far more storage and interconnection than high end pcs.

What is Behaviorism?
Attempt to answer question, how do humans and animals think and act?

rejected any theory involving mental processes on the grounds that introspection could not provide reliable evidence. Studied only objective measures of percepts given to an animal and its resulting actions.

What is cognitive psychology?
attempt to answer question, how do humans and animals think and act?

views brain as info-processing device.

3 steps to knowledge based agent:
1. the stimulus must be translated into an internal representation

2. the representation is manipulated by cognitive processes to derive new internal representations

3. these are in turn retranslated back into action

First operation computer
electromechanical Heath Robinson, built in 1940 by Alan Turing to decipher German messages.
First programmable computer
Z-3, intented by Konrad Zuse in Germany 1941.
First electronic computer
ABC, built by John Atanasoff and Clifford Berry bet. 1940-1942 at Iowa State University
Who is Norbert Wiener?
attempted to answer question “How can artifacts operate under their own control?”

created “Control Theory”. Challenged behaviorist orthodoxy, viewing purposive behavior as arising from a regulatory mechanism trying to minimize “error”, the difference between the current state and the goal state.

Wrote the book, “Cybernetics” in 1948, which became a bestseller and awoke the public to the possibility of artificially intelligent machines

Who is W. Ross Ashby?
wrote “Design for a Brain” (1948) elaborating on his idea that intelligence could be created by the use of homeostatic devices containing appropriate feedback loops to achieve stable adaptive behavior.
Modern control theory
goal to design systems that maximize an objective function over time. Similar to goal of AI: designing systems that behave optimally
What killed off interest in behaviorism?
Noam Chomsky pointed out that behaviorist theory did not address the notion of creativity in language – it did not explain how a child could understand and make up sentences that he or she had never heard before.
First program to embody the “thinking humanly” approach?
GPS (General Problem Solver) Designed from the start to imitate human problem-solving protocols. The order in which it considered subgoals and possible actions was similar to that in which humans approached the same problems.
physical symbol system hypothesis
a physical symbol system has the necessary and sufficient means for general intelligent action, meaning that any system exhibiting intelligence must operate by manipulating data structures composed of symbols.
high level programming language developed by John McCarthy in 1958. Became the dominant AI programming language for the next 30 years.
perceptron convergence theorem
says the learning algorithm can adjust the connection strengths of a perceptron to match any input data, provided such a match exists
The fact that a program can find a solution in principle does not mean…?
that the program contains any of the mechanisms needed to find it in practice.
what is a perceptron?
simple form of neural network
erroneous assumption of early AI devs?
larger problems could be solved with faster processors and more memory.
When did AI become an inudstry?
1980. hundreds of companies building expert systems, vision systems, robots, and software and hardware specialized for these purposes
What caused the AI winter?
companies fell by the wayside as they failed to deliver on extravagant promises.
prominent recent approach to AI methodology
Hidden Markov models (HMMs).
1. They are based on a rigorous mathematical theory, allowing speech researchers to build on decades of mathematical results dev’d in other fields.

2. They are generated by a process of training on a large corpus of real speech data

HMMs provide a mathematical framework for understanding the problem and support the engineering claim that they work well in practice.

Beyesian network
invented to allow efficient representation of and rigorous reasoning with uncertain knowledge. Currently dominates AI research on uncertain reasoning and expert systems
What is a normative expert system
one that acts rationally according to the laws of decision theory and do not try to imitate thought steps of human experts
Emergence of intelligent agents
1995-present. Very prominent in web-apps and internet tools like search engines, recommender systems, etc.
human-level AI
belief that AI should put less emphasis on creating ever-improved apps that are good at specific tasks and rather return to the roots of AI. In Simon’s words, “machines that think, that learn, and that create”