AI Introduction

Course Outline

Artificial Intelligence

Definition. The science of developing methods to solve problems usually associated with human intelligence.
Alternate definitions:
building intelligent entities or agents;
making computers think or behave like humans
studying the human thinking through computational models;
generating intelligent behavior, reasoning, learning.

Questions

What do we call intelligence?
Examples of intelligent tasks.
Can an artificial being ever be considered "alive"? What does it mean to be "alive"?

Natural Intelligence

Definition. Intelligence - inter ligare (Latin) - the capacity of creating connections between notions.
Wikipedia: the ability to solve problems.
WordNet: the ability to comprehend; to understand and profit from experience.
Complex use of creativity, talent, imagination.
Biology - Intelligence is the ability to adapt to new conditions and to successfully cope with life situations.
Psychology - a general term encompassing various mental abilities, including the ability to remember and use what one has learned, in order to solve problems, adapt to new situations, and understand and manipulate one’s reality.
Nonlinear, non-predictable behavior.

Visions of AI

Systems that think like humans.
Systems that act like humans.
Systems that think rationally.
Systems that act rationally.
A distinction between being intelligent and acting intelligently, and being like a human, or solving similar problems (not necessarily the same way).

Thinking Humanly

Cognitive science: modeling the processes of human thought.
Through a set of experiments and computational models, trying to build good explanations of what we do when we solve a particular task.
Relevance to AI: to solve a problem that humans (or other living being) are capable of, it's good to know how we go about solving it.
Early approaches tried to solve any problem exactly the way a human would do. Now we know that it's not the best approach.

Acting Humanly

How do you distinguish intelligent behavior from intelligence?
Turing test, by A. Turing, 1950: determining if a program qualifies as artificially intelligent by subjecting it to an interrogation along with a human counterpart.
The program passes the test if a human judge cannot distinguish between the answers of the program and the answers of the human subject.
It hasn't been passed yet.
http://www.loebner.net/Prizef/loebner-prize.html

Thinking Rationally

Systems capable of reasoning, capable of making logical deductions from a knowledge base.
This requires some capacity to make logical inferences, like "All humans are mortal; Socrates is a human; thus Socrates is mortal".
Good news: formal logic is easy to express as a program and its rules are clear.
Bad news: Gödel's incompleteness theorem and SAT is NP-Complete.

Gödel's Theorem

At some point it was believed that one could prove anything using only logic, building a formal system to describe the knowledge - Hilbert.
K. Gödel proved in his Incompleteness Theorem that within any formal system, some statements that are true could not be proven using only formal logic based on the axioms of that system.
What this means: logic is a powerful and necessary tool in automatic reasoning, but to make useful deductions one requires domain-specific knowledge.

SAT - NP-Complete

SAT - satisfiability problem. Given a logical formula involving a set of Boolean variables, is there a set of values for these variables such that the formula is true?
Relevance to AI: the problem of deciding if something is true in a given system (making a deduction) comes down to solving a particular SAT problem.
NP-complete: there is no known polynomial algorithm to solve this problem, but if we find one for it, then we can solve any other NP problem. For now a guaranteed solution is exponential.

Acting Rationally

Many AI applications adopt the intelligent agent approach.
An agent is an entity capable of generating action.
In AI a rational agent must be autonomous, capable of perceiving its environment, adaptable, with a given goal.
Most often the agents are small pieces of code with a specific proficiency. The problem is solved by combining the skills of several agents.

History of AI

1943 - W. McCulloch and W. Pitts designed the first neural network. M. Minsky and D. Edmonds built the first one in 1951 at Princeton.
1950 - A. Turing, "Computing Machinery and Intelligence".
1956 - J. McCarthy organized a workshop at Darmouth where the name of AI was officially adopted for the field.
Early successes: the General Problem Solver (puzzles), Geometry Theorem Prover, Samuel's checkers player.
1958 - McCarthy invented Lisp.
The early systems were successful on small problems but failed on larger ones.
1958 - Friedberg's machine evolution (now better known as hill-climbing) using mutations; it failed to find good solutions.
1966 - a commission reports on the failing of machine translation and all funding to such projects is ceased.
1969 - Minsky and Papert, Perceptrons, proved that they could learn anything they could represent, but there was not much they could represent.
Knowledge-based systems - that contain domain-specific knowledge giving them more problem-solving power - Expert Systems. The industry adopted them on a relatively large scale, but many such projects failed.
More recent developments combine AI methods with strategies from other fields.
Although the initial ambition of AI seems a distant goal at most, many methods have been developed that are used in most areas of CS.

Successes in AI

1975 - Meta-Dendral learning program finds new rules in spectral chemistry.
1978 - Herb Simon wins the Nobel Prize in Economics for his theory of bounded rationality.
1979 - The Stanford Cart, built by Hans Moravec, the first computer-controlled autonomous vehicle.
80s - neural networks with backpropagation algorithm become popular, evolutionary computation
1997 - Deep Blue beats G. Kasparov, first Robo-Cup.
2000 - Interactive robots commercially available, Kismet (MIT), robots used for real applications.

Related Fields

Main Areas of AI

Relevant Publications