What is Artificial Intelligence?

(1)

1 0 - Introduction 0 - Introduction What is Artificial Intelligence?

What is Artificial Intelligence?

Laurea

Laurea MAGISTRALE in MAGISTRALE in COMPUTER SCIENCE COMPUTER SCIENCE

ARTIFICIAL INTELLIGENCE

Questi lucidi sono stati preparati per uso didattico. Essi contengono materiale originale di proprietà dell'Università degli Studi di Bari e/o figure di proprietà di altri autori, società e organizzazioni di cui e' riportato il riferimento. Tutto o parte del materiale può essere fotocopiato per uso personale o didattico ma non può essere distribuito per uso commerciale. Qualunque altro uso richiede una specifica autorizzazione da parte dell'Università degli Studi di Bari e degli altri autori coinvolti.

Automatic Servant

• III sec a.C. • Philo of Byzantium

– ~280-220 a.C.

Digesting Duck

• 30/05/1739 • Jacques De Vaucanson

– 1709-1782

Mechanical Turk

• ~1770-1854 – Fake!

• Wolfgang Von Kempelen

– 1734-1804

Frankenstein

• 1818 • Mary Wollstonecraft Shelley

– 1797-1851

Attempt of scientist Victor Frankenstein to create

artificial life

Euphonia

• ~1830-40’s • Joseph Faber – ~1800

“…It is a speech synthesizer variously known as the Euphonia and the Amazing Talking Machine. By pumping air with the bellows … and manipulating a series of plates, chambers, and other apparatus (including an artificial tongue ... ), the operator could make it speak any European language. A German immigrant named Joseph Faber spent seventeen years perfecting the Euphonia, only to find when he was finished that few people cared."

[David Lindsay "Talking Head", Invention

& Technology, Summer 1997, 57-63]

(2)

Golem

• 1913-1914, 1915 • Gustav Meyrink (Gustav Meyer)

– 1868-1932

An animated anthropomorphic being that is created entirely from inanimate matter (usually clay or mud) [wikipedia]

Inspired by the legend of rabbi Judah Loew ben Bezalel

Computer Science & Artificial Intelligence

● Timeline

●

1837: Babbage's Analytical Engine

●

1936: Turing Machine

●

1943-46: ENIAC (decimal)

●

1946-1949: EDVAC (digital)

– Von Neumann's architecture

●

1956 (June): Artificial Intelligence

– Dartmouth Summer Research Project on Artificial Intelligence

Short History: 1943-1956

● Prelude

●

First chess-playing programs

– Claude Shannon & Alan Turing

●

1951: First neural computer

– Marvin Minsky & Dean Edmonds

●

1955: Signed a research project on AI

– Laid the basis for talks and discussions at Dartmouth

Prelude

●

C.E. Shannon (1950)

– General purpose digital computers are an extension over the ordinary use of numerical computers in several ways.

– First, the entities dealt with are not primarily numbers, but rather chess positions, circuits, mathematical expressions, words, etc.

– Second, the proper procedure involves general principles, something of the nature of judgement, and considerable trial-and-error, rather than a strict, unalterable computing process.

– Finally, the solutions of these problems are not merely right or wrong but have a continuous range of "quality"

from the best down the worst. We might be satisfied with a machine that designed good filters even though they were not always the best possible.

– […]

Prelude

●

C.E. Shannon (1950)

– […] The computer operates under the control of a

"program". The program consists in a sequence of elementary "orders". [...]

– Another type of order involves a decision, for example:

C 291, 118, 345.

– This tells the machine to compare the contents of box 291 and 218 [in memory]. If the first is larger, the machine goes on to the next order in the program. If not, it takes its next order from box 345.

– This type of order enables the machine to choose from alternative procedures, depending on the results of previous calculations.

Prelude

●

A.G. Oettinger (1952)

– The great importance of the E order [i.e., the branching instruction] arises from the fact that the choice between these alternatives is based on the results of earlier operations. […]

– Hence, while the programmer must essentially foresee the need for a choice and provide E orders to meet this need, the actual decision is made by the machine itself on the basis of the information obtained in the course of operation either from its own store or […] from the outside world. [...]

– More interesting types of learning behaviour can be obtained by giving the machine a programme which provides for the transformation of its own orders in the fashion described above.

– By the liberal provision of E orders in the programme,

the machine is enabled to organize new information

meaningfully and to select alternative modes of

behaviour on the basis of this organization.

(3)

Prelude

●

O. Schmitt (as opposed to Oettinger)

– Even in the building of efficient machines, it is necessary to abandon the idea of perfectly correct, uniformly logical solutions which is to arrive at generally appropriate quick solution to complex problems when provided only with sketchy, conflicting, and partially inappropriate information.

●

1955, Symposium at the IRE National Convention on “The Design of Machines to Simulate the Behavior of the Human Brain”

– Contrapositions

●

Determinacy Indeterminacy

●

“Purely digital” “Statistical, distributed”

computers computers

●

“Black&White” logic “Grey” logic

●

Logical Common-sense

reasoning (knowledge-based) reasoning

●

Fully-informed Real life, partially-informed decision procedures decision procedures

History in Short: 1956

● Birth

●

Real: Logic Theorist by Allen Newell & Herbert Simon

– First program with “reasoning” capabilities

– Able to build a proof for many theorems in Chapter 2 of Russell’s Principia Matematica

●

Formal: First 2-month workshop held at Dartmouth College

– Name (Artificial Intelligence) by John McCarthy

– Attended by the “fathers” of the new discipline

– Foundations of the discipline

– Identification of some now still classical research areas

– Principles of the first so-called “intelligent” computer programs

• John McCarthy – 1961-2011

Official Birth

● Birth

●

June 1956, Dartmouth (New Hampshire, USA)

– Dartmouth Summer Research Project on Artificial Intelligence

– Organized Convention

●

Foundation of the new discipline

●

Identification of (now classical) research areas

●

Outlining of first so-called "intelligent" computer programs

●

Fathers

– John McCarthy, Marvin Minsky, Nathaniel Rochester, Claude Shannon

●

Ray Solomonoff, Oliver Selfridge, Trenchard More, Allen Newell (Turing prize 1975), Herbert Simon (Turing prize 1975, Nobel prize 1978), Arthur Samuel

●

[Turing +1954]

What’s New or Different

● H.A. Simon’s contrapositions with respect to decision-making theories (1946-1956 ca.):

●

omniscient partially informed

●

ideal rationality bounded rationality

●

maximizing satisficing

●

well-structured ill-structured problems (real-life) problems

●

linear programming heuristic programming

Definitions

● Machine Intelligence

●

“The program [is] capable of performing functions which, in living organisms, are considered to be the result of intelligent behaviour”

– (A.G. Oettinger,1952)

● Artificial Intelligence

●

“Programs […] exhibit that we call intelligent behavior when we observe it in human beings”

– (E.A. Feigenbaum & J. Feldman,

"Computers and Thought", 1963)

(4)

Aims

● Trying to understand and build intelligent entities

●

Which definition of Intelligence?

– Some operational definitions

●

The study of how to make computers do things that, at present, human beings do better (playing chess, solve problems, understand, reason, learn autonomously, …), i.e., how to build systems that act like human beings

●

The building of a symbol handler that is able to pass Turing's test

●

Better defining intelligent behavior...

Intelligent Behavior

●

React flexibly to different situations

●

Take advantage of casual and sometimes unforseeable circumstances

●

Make sense from ambiguous and contradictory messages

●

Recognize the relevance of the different elements in a given situation

●

Find similarities and analogies among different situations, in spite of concrete elements of diversity

●

Notice distinctions among different situations, in spite of concrete elements of similarity

●

Synthesize new concepts, produce new ideas

Intelligent Behavior in Machines

● Branches of AI

●

Cybernetics

– Intelligence = Control & Communication

●

Knowledge Engineering

– Intelligence = Representation

●

Expert Systems (ES)

– Intelligence = Behaving like a human expert

●

Machine Learning (ML)

– Intelligence = Improving performance through experience

Strong Approach

● Can we build machines that think intelligently?

●

i.e., have real conscious minds?

– This question raises some of the toughest conceptual problems of the entire Philosophy

● AI foundations

●

Philosophy

●

Mathematics

– Logics

●

Psychology

●

Linguistics

●

Computer Engineering

Weak Approach

● Can we build machines that act as if they were intelligent?

● Yes, but...

●

There are things that computers cannot do, independently of how we program them

– Incompleteness of Formal Systems

●

Failure in the long term

– Learning

●

Actually building suitable programs is unfeasible

– Complexity of knowledge

History in Short: 1952-1966

●

Initial excitement

– “Strong” approach prevails: building programs that think as human beings

– Success of early AI programs, given the primitive processing and programming tools of those days

●

General Problem Solver (GPS) by Newell & Simon that solved puzzles

●

Geometry Theorem Prover by Nataniel Rochester

●

LISP language by John McCarthy, that became the dominant language for AI

●

After initial excitement

– Marvin Minsky focused on the creation of programs that, albeit in limited domains (MicroWorlds), actually worked

●

First programs able to solve analogy problems in the domain of

simple geometric figures or to manipulate such figures

organizing them in stacked blocks

(5)

Intelligence as Problem Solving

●

Is it possible to solve problems for which an algorithm is not known in advance? What to do when...

– ...the solution strongly depends on the specific instance?

– ...the external situation changes in time?

●

E.g., some problems must be tackled with “tentative” methods (games, maze solving, ...). In these cases defining a solving method amounts to searching for a solution in the space of possible “problem states”

●

The program:

– Is an environment in which representing, using and changing information and knowledge useful for the solution

●

not a set of immutable statements representing the solution – Builds dynamically a solution against a given number of

possibilities

More Recent Definitions

●

“The exciting new effort to make computers think… machines with minds, in the full and literal sense”

(Haugeland, 1985)

●

“The automation of activities that we associate with human thinking, activities such as decision making, problem solving, learning..”

(Bellman, 1978)

●

“The study of mental faculties through the use of computational models” (Charniak & Mc Dermott, 1985)

●

“The study of the computation that make it possible to perceive, reason and act” (Winston, 1992)

●

“The art of creating machines that perform functions that require intelligence when performed by people” (Kurzweil, 1990)

●

“The study of how to make computers do things at which, at the moment, people are better”

(Rich & Knight, 1991)

●

“A field of study that seeks to explain and emulate intelligent behaviour in terms of computational processes”

(Schalkoff, 1990)

●

“The branch of Computer Science that is concerned with the automation of intelligent behaviour”

(Lugerland and Stubblefield, 1993)

More Recent Definitions

● Systems that think like human beings

● Cognitive Modeling

● 1978-1985

● Systems that think rationally

● Laws of Thought

● 1985-1992

● Systems that act like human beings

● Turing’s Test

● 1990-1991

● Systems that act rationally

● Rational Agent

● 1990-1993

Thinking Like a Human Being

● Cognitive Approach

●

Focus: study of computational models and experimental techniques that allow us to build and check theories about the cognitive skills in humans

– Examples

●

Learning languages

●

Memory

●

...

●

Related Disciplines

– Psychology

– Cognitive Sciences

– Psycholinguistics

– Neurology

Acting Like a Human Being

● Turing’s Test

(1950, “Computing machinery and intelligence”)

●

Operational test for intelligent action

– To act like a human being, a computer should be able of:

●

Natural Language Processing

●

Knowledge Representation

●

Automated Reasoning

●

Automated Learning

●

Perceive, see, move, understand, take autonomous decisions, ...

●

Related disciplines: all sub-areas of AI

– linguistics, signal processing, statistics, logics, cognitivism, psychology, mathematics, philosophy, computer engineering

Acting Like a Human Being

● Turing’s Test inspiration: the Imitation Game

●

3 players: man A, woman B, third person C

●

C kept separate from A and B

●

C must determine which is the man and which is the woman

– A must cheat at C

– B must help him

●

by issuing them a series of questions

– Answers typewrited so as to prevent C from having any

hint (e.g., writing or speech analysis)

(6)

Acting Like a Human Being

● Turing’s Test idea: Replace A by a machine

●

If the percentage of times in which C makes a correct guess about who is the man and who is a woman is the same before and after replacing A with a machine

●

Then the machine should be deemed as intelligent

– In the given situation, it would be indistinguishable from a human being

Acting Like a Human Being

● Eliza (Joseph Weizenbaum, 1966)

●

Example:

– Q: Are you an artificial intelligent expert?

– A: Oh, I am an artificial intelligent expert!

– Q: Did you ever teach an artificial intelligence course?

– A: Oh, I ever teached an artificial intelligence course!

– Q: can you explain me the backward propagation algorithm?

– A: Why do you ask?

●

https://www.masswerk.at/elizabot/

Thinking Rationally

● Logic-based Approach

●

Logics is the discipline that studies the laws of thought

– Aristotle was the first thinker trying to encode the laws of thought

●

Syllogisms

●

Based on this approach, it is possible to express problems that are typical of human reasoning in a formal notation, and to find a solution to them

●

Related disciplines:

– Logics, Mathematics, Statistics

Thinking Rationally

● What’s logics?

●

In common language

– A consistent and convincing way of reasoning

●

But also...

– A way to connect words or actions that does not necessarily has a rational explanation, rather a sentimental one

●

Logics of heart, children’s logics, ...

●

In Mathematics

– Studies the laws that allow to develop areasoning such that, starting from true claims (premises), one obtains true conclusions by means of a process called deduction

– Premises –(deduction)--> Conclusions

Acting Rationally

● Intelligent Agents

●

Acting Rationally = pursuing one’s objectives, starting from one’s perception of the surrounding reality or belief

●

Agent: an entity that perceives and acts accordingly

●

Approach in a sense more realistic than the previous ones, because the standard for rationality is more clearly defined and delimited

2 Levels

● Sub-symbolic

●

Low-level Processes

●

Perception

●

Brain

●

Irrational

– Compiled

– Not explainable

●

Fast

– Efficiency

● Symbolic

●

High-level Processes

●

Reasoning

●

Mind

●

Rational

– Interpreted

– Explainable

●

Slow

– Complexity

Need for cooperation!

(7)

Basic Questions

● To understand reality, external phenomena must be compared to internal representations

●

How to build internal representations?

● Only rational mental processes

●

(not emotions)

can be reproduced by Computer Science

●

Which rational mechanisms?

History in Short: 1966-1974

● A dose of reality

●

Early AI programs set ambitious goals and soon encountered complexity problems

– Limited a priori knowledge base

– Many problems computationally intractable

– Weak theoretical models and representation mechanisms

●

Power of knowledge: early knowledge-intensive systems

– DENDRAL (1969)

●

Deduced molecular structures based on information provided by a mass spectrometer. Owed its success to the large number of expert-encoded ad-hoc (heuristic) rules

– Heuristic Programming Project (Feigenbaum et al.)

●

Birth of the Expert Systems area

What's New or Different

●

Initial convinction that the main task of AI was studying problem solving strategies effectively selective, or "heuristics"

●

Heuristic Programming

– “A branch of computer programming, which uses heuristics – common-sense rules drawn from experience – to solve problems. This is in contrast to algorithmic programming, which is based on mathematically provable procedures. Heuristic programming is characterized by programs that are self- learning; they get better with experience. Heuristic programs do not always reach the very best result but usually produce a good result.”

– As in humans, explores only a portion of the paths that, based on the available information, might lead to an acceptable solution for the given problem, while satisfying some fundamental requirements

History in Short: 1980-1992

● AI becomes an industry

●

First industrial applications of AI

– Especially thanks to the success obtained in some specific areas by Expert Systems

●

1981: Japanese government announces the “Fifth Generation” project

– Aim: building architectures oriented to AI applications

●

(E. Feigenbaum, P. McCorduck: The fifth generation:

artificial intelligence and Japan's computer challenge to the world, 1983)

●

LISP machines

– Xerox, Texas Instruments, and Symbolics build workstations oriented to the development of LISP applications

History in Short: End of XX century

● 1997: IBM’s Deep Blue beats world chess champion Gary Kasparov

●

Brute force approach

History in Short: Beginning of XXI century

● 14-16/2/2011: IBM’s Watson beats human players at “Jeopardy!”

●

DeepQA Technology

– 90 servers IBM Power 750

●

POWER7 processor (8 cores x 4 threads, 3.5 Ghz)

●

16 TB RAM

(8)

History in Short: Beginning of XXI century

● 2015: Google DeepMind’s AlphaGo beats 18- time world GO champion Lee Sedol

●

4-1 games

● 2017: AlphaGo Zero (starts from scratch) beats all previous versions of AlphaGo

●

Million matches before matching human ability

Theoretical basis

● Traditional AI

●

Algorithmic vision of mind

– Mental mechanisms similar to programs

●

Systems mainly based on deductive paradigm

● Modern AI

●

Theory of mental models

– Mental processes based on analogical mechanisms that match reality with internal representations

●

Systems mainly based on inductive and incremental processes

AI Today

● The rebirth

●

More stable and accurate theoretical models

●

Enormous advancements in technology

– Computational power

– Connectivity

– Infrastructures

AI Today

● Focus: building working systems

●

Based on existing theories, rather than inventing new theories

– Knowledge-based Intelligent Agents

– Systems that can learn autonomously, even knowledge in explicit form, and define their objectives

– Integration of symbolic and sub-symbolic learning approaches (Statistical Relational Learning)

●

Use of probabilistic models predominant – E.g., Hidden Markov Models

– Applications oriented to processing knowledge expressed in multimodal and multimedia form (images, texts, videos, audio, ...) in the IST (Information Society Technology) philosophy

AI Today

● Opportunity:

wealth of available data

●

Internet & Social Networks

●

Internet of Things (IoT)

– Objects are Internet resources

– They may interact

●

Send data about themselves

●

Obtain data from other sources

– They may acquire intelligence through this interaction

●

Examples:

– Earlier clock alarms in case of traffic jams – Plants tell the sprinkler when they are to be watered – Drugs containers warn people that they have to take drugs

AI Today

● Motivation: Use of computers by anybody for any task requires extreme flexibility

●

Beyond capabilities of traditional algorithmic approaches

● A hot topic

●

Many job and business opportunities

●

Already pervasive in our lives, but...

– How much of what is passed off as AI is really AI?

●

Ethical Issues

– How far can we go in putting our lives in the hands of AI

systems?

(9)

AI Today

● A well-known example: self-driving cars

●

Adaptive cruise-control systems

– Keep distance from other cars

– Read road signs

– Park autonomously

– Stop-and-go engine

– Warning if driver falls asleep

– ...run over pedestrians?

AI Today

● Imitation of "human" performance obsolete for some tasks

●

E.g., AlphaGo

● Dilemma

●

Opportunity

– Solving problems that are so far out of reach for humans

●

Problem

– Control of Complexity

●

Handling Critical Situations

– [Michie-Johnston, “The Creative Computer”, Penguin 1985]

AI Today

● Why a symbolic approach?

●

Computers in their present form have in a sense gone as far as they can go. No longer can they be built with the central aim of maximizing

performance and making the best of machine resources.

●

Instead, they will have to work on a totally different basis – one designed to be anthropocentric. To make computers comprehensible, we must build them in the image of the human mind.

– Michie, Johnston

The Human Window

● Michie, Johnston

The Human Window

● While a look-up system is too shallow in that it gives too little information,

● a look-ahead system tends to be too deep by giving too much.

● This is a separate issue from the power of the system – how much it is capable of doing.

●

Michie, Johnston

AI Tomorrow

● CPU < GPU < ...quantum computing?

●

Qubit + Entanglement

● Combinatorial problems

[Jonathan Hui, “QC – What is a Quantum Computer?”]

Ettore Majorana

1906-1938?

(10)

Ethical Issues

● Trustworthiness

● Transparency

● Explainability

● Accountability

Ethical Issues

● Are

statistical correlations sufficient?

●

Need

for causal relationships

Bedsheet tanglings

Cheese consumed

Per capita cheese consumption correlates with

Number of people who died by becoming tangled in their bedsheets

Bedsheet tanglings Cheese consumed

2000 2001 2002 2003 2004 2005 2006 2007 2008 2009

200 deaths 400 deaths 600 deaths 800 deaths

28.5lbs 30lbs 31.5lbs 33lbs

tylervigen.com

0.947091

0.935701

Hanging suicides

US spending on science

US spending on science, space, and technology correlates with Suicides by hanging, strangulation and suffocation

Hanging suicides US spending on science

1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009

6000 suicides 8000 suicides

4000 suicides 10000 suicides

$15 billion

$20 billion

$25 billion

$30 billion

tylervigen.com

0.99789126

Symbolic Knowledge Representation

● Various Formalisms

● 2 main categories

●

Order 0 (propositional logics)

– Feature Vectors

– Attribute-Value pairs

●

Order 1 (predicate logics)

– Complex Schemes

– Objects, Attributes, Relationships

Traditional Programming and AI

● A + D = R

● Algorithms

● Data (Structures)

● Results

● H + O |= C

● Hypotheses

● Observations

● Conclusions

J. McCarthy, M.L. Minsky, N. Rochester, C.E.

Shannon: A proposal for the Dartmouth Summer Research Project on Artificial Intelligence, 1955

●

P. McCorduck: Machines Who Think, 1979

●

D. Michie, R. Johnston: The Creative Computer – Machine Intelligence and Human Knowledge, 1984

●

D. Hofstadter, D. Dennett: The Mind’s I, 1985

Sub-areas of Artificial Intelligence

● Methodological Areas

●

Knowledge Representation

●

Automatic Reasoning and Problem Solving

●

Planning

●

Machine Learning

● Application Areas

●

Expert Systems

●

Robotics

●

Natural Language Processing

●

Image Processing

(11)

An example: Search

● Knight’s Tour ...

●

“The first real program I tried to write was called the Knight’s Tour. You jump a knight piece around the chessboard, only in valid moves for a knight, in a pattern so that it hits every one of the sixty-four squares on the board exactly once. [...] I wrote my program [...] to try all the moves until you can’t move again. And if it didn’t hit all the squares by the time it got stuck, the program would back up and change a move and try again from there. It would keep backtracking as far as it needed and then kept going. That computer could calculate instructions a million times a second, so I figured it would be a cinch and would solve this problem quickly.

An example: Search

● ... Knight’s Tour ...

●

“[...] The computer doesn’t spit out anything. The lights on the computer flickered, and then the lights just stayed the same. Nothing was happening. My engineer friend let it run a while longer and then said, “Well, probably it’s in a loop”. [...] Anyway, the next week I went back and I wrote my program so that I could flip a switch in order to get printouts of whatever chess arrangement it was working on. I remember pulling the printouts out and studying them that very day and realizing something. The program was in fact working the way it was supposed to. I hadn’t done anything wrong. It just wasn’t going to come up with a solution for 10 ²⁵ years. That’s a lot longer than the universe has even been around.”

An example: Search

● ... Knight’s Tour

●

“That made me realize that a million times a second didn’t solve everything. Raw speed isn’t always the solution. Many understandable problems need an insightful, well-thought-out approach to succeed.”

An example: Search

● ... Knight’s Tour

●

“That made me realize that a million times a second didn’t solve everything. Raw speed isn’t always the solution. Many understandable problems need an insightful, well-thought-out approach to succeed.”

– Steve Wozniak

An example: Search

● ... Knight’s Tour

●

“That made me realize that a million times a second didn’t solve everything. Raw speed isn’t always the solution. Many understandable problems need an insightful, well-thought-out approach to succeed.”