Breve introduzione all’IA
Alessandro Cappellini
9 Aprile 2004
[email protected]
Churh - Turing
• Negli anni ’20 David Hilbert ha proposto il
problema della decidibilità come “sfida” della
moderna matematica.
• Secondo Turing: “Non è possibile stabilire in
maniera certa e meccanica la verità o la falsità
di tutti gli enunciati matematici”.
• Per dimostrarlo Turing teorizza la logical
computing machine.
Una macchina di Turing consta in
un nastro cartaceo diviso in
singole celle, che serve sia per
l’input che per l’output, una
testina per scrivere e cancellare
sul nastro e un interprete.
Algoritmi
E' un procedimento per la soluzione di un problema.
Esiste un qualcuno (una macchina o in generale un interprete) che
esegue ciò che l’algoritmo specifica (le istruzioni):
• azioni che devono essere eseguite;
• ordine con cui devono essere eseguite.
Un algoritmo può essere paragonato a una ricetta (entità astratta).
La ricetta scritta in un libro di cucina sarà un programma scritto
con un formalismo (linguaggio di programmazione).
Nel definire un problema algoritmico dobbiamo specificare:
• l'insieme degli input ammissibili;
• l'insieme degli output desiderati in funzione degli input.
Un problema algoritmico è risolto se si trova un algoritmo
appropriato (che deve fornire output corretti partendo da tutti gli
input ammissibili).
Problemi
•
•
•
•
Fortemente Indecidibili (Tiling Problem con spazio infinito)
Indecidibili (Halting Problem, Tiling Problem)
Intrattabili (Torri di Hanoi, Scacchi, Blocchi stradali)
Decidibili
TSP, Scheduling, problema dello zaino, massimizzazione,
problemi economici e di ricerca operativa sono NP-Completi (il
loro tempo di soluzione nei worst-case è non polinomiale).
Il calcolo parallelo aiuta la ricerca di soluzioni in casi adatti (e.g.
scavare un pozzo o un fossato).
I metodi Montecarlo e Las Vegas possono ridurre i problemi NP
alla classe RP. Ma ogni algoritmo casuale può essere simulato
da uno deterministico, ricadendo nella tesi di Church-Turing.
Halting Problem
Un programma si ferma davvero per tutti gli input
fornendo un risultato?
Secondo il teorema di Rice non possiamo dire “un bel
niente” sui programmi e non esiste un algoritmo in
grado di stabilire se una certa computazione ha
qualsiasi proprietà non banale.
Uno dei più famosi Halting problem è quello proposto da
L. Collatz in 1937, noto anche come 3x+1
(http://mathworld.wolfram.com/CollatzProblem.html).
Non è provato che si fermi per tutti gli input positivi, e
crea cicli per input negativi (-1, -5…)
Collatz – “3X+1”
#include <stdio.h>
// 3x+1 problem aka Collatz (1937)
La sequenza (hailstone
numbers) generata dal
numero 27 è lunga 111
elementi.
int main ()
{
int number,i;
i=0;
printf("choose an integer and hit return: \n");
scanf("%d", &number);
printf("\n");
while (number!=1)
{
10000
if (number%2==0)
9000
{number = number/2;}
8000
else {number = 3*number+1;}
7000
i++;
6000
printf("%d %d
\n",i,number); 5000
}
4000
return 0;
3000
2000
}
1000
106
99
92
85
78
71
64
57
50
43
36
29
22
15
8
1
0
Test di Turing
1950 Computing Machinery and Intelligence: “Can
machines Think?”
Il test proposto è una conversazione (chat) tra un umano e
alcuni soggetti (umani o macchine). Se l’esaminatore
non distinguerà la macchina dall’umano questa potrà
essere considerata intelligente.
Di solito si chiede al computer/programma di affrontare
sessioni diverse con diversi esaminatori per rendere il
giudizio meno soggettivo.
Molti pensano che nessun computer lo supererà mai.
Ogni anno si tiene il premio Loebner che premia chi più
si avvicina a superare il test di Turing.
Nessuno lo ha mai superato.
Storia
Blaise Pascal nel 1642 realizza la “Pascalina”, una
macchina calcolatrice meccanica.
Charles Babbage a fine 1800 progetta l’Analytic
Engine, un primo computer, mai realizzato e
Ada Byron (Lady Lovelace) inventa le basi
della programmazione.
Nel 1889 Herman Hollerith idea una macchina
calcolatrice a schede perforate per il censimento
americano e dopo poco fonda la International
Business Machines – I BM.
Computer Bellici
Konrad Zuse nel 1931 costruisce Z1, il primo calcolatore digitale
tedesco, usato per le traiettorie delle V2.
Turing collabora al progetto ULTRA che prevede la costruzione di
elaboratori per decifrare il codice tedesco Enigma, basato sui
numeri primi. A Bletchley Park verrà costruito Colossus, e nel
1943 si decifrerà il codice.
ENIAC (electronic numerical integrator and computer) di Prepser
Eckert e John Mauchly sarà usato per il calcolo delle tabelle di
artiglieria e per il progetto Manhattan. Ha il difetto che pochi
minuti di calcolo costano ore di settaggi di relè e interruttori.
EDVAC (electronic discrete variables automatic computer) è il
successore di ENIAC ed è programmabile.
Architettura von Neumann
Nel giugno 1945, durante la costruzione di EDVAC viene
formalizzata l’architettura di von Neumann, oggi
usata nella maggior parte dei calcolatori, che consta
in:
1. una memoria che contenga il programma (nella
macchina di Turing il lungo nastro cartaceo);
2. una unità di calcolo che riceve i dati ed esegue le
operazioni richieste dal programma;
3. una unità di controllo che interpreta le istruzioni di
programma in memoria e fa effettuare all’unità di
calcolo le operazioni corrispondenti.
Summer Research Project on Artificial Intelligence
Dartmouth College, NH, 1956
1. Migliorare la potenza di calcolo e raffinare i metodi di
programmazione;
2. Programmare un computer che “possieda un linguaggio”
manipoli simboli e concetti in maniera simile a una mente
umana;
3. Costruire sistemi di neuroni artificiali capaci di ricreare il
comportamento di sistemi nervosi biologici e di formare
concetti;
4. Stimare la durata di un calcolo o come trovare delle euristiche
per abbreviarla;
5. Automiglioramento dei calcolatori (che imparano da soli e
modificano il proprio programma);
6. Come far sì che i calcolatori possano formare concetti e
astrazioni;
7. Come mettere nei calcolatori una qualche forma di creatività e
libero arbitrio.
Allen Newel, Cilff Shaw, Herbert Simon
Logic theorist LT 1955-56 – viene definito il primo programma di IA.
Dimostra i teoremi contenuti nei Principia Mathematica di Russell e
Whitehead.
The General Problem Solver GPS 1957 – risolve la torre di Hanoi e il dilemma
di “lupo, capra e cavoli”. Si critica che il programma riceve una descrizione
tanto dettagliata del problema da contenere la soluzione dello stesso.
Edward Feigenbaum 1967 – Sistemi Esperti
Sono knowledge-based system composti principalmente da due parti: una base di
conoscenza e un motore inferenziale.
La base di conoscenza raccoglie in maniera simbolica tutte le conoscenze che un
esperto umano usa per risolvere il problema. Il metodo più utilizzato è costruire
una gran serie di regole (rule-based reasoning) del tipo “se X allora Y”.
Con Joshua Lederberg, Bruce Buchanan, George Sutherland scrive Heuristic
Dendral, un sistema esperto per la chimica che nel 1975 scopre nuove molocole.
Sistemi Esperti
Mycin (1974) di Edward Shortliffe è un sistema esperto in diagnosi su meningite
e infezioni del sangue con 400 regole, che batte diversi medici nella diagnosi.
Vantaggi:
• Sanno risolvere problemi scomponendoli in più sottoproblemi;
• Possono fornire una traccia della loro linea di ragionamento;
• Di fronte a informazioni incomplete o contraddittorie se ne rendono conto e
chiedono spiegazioni;
• La loro conoscenza non è stabilita, è possibile accrescerla.
Svantaggi:
• Sono rigidi: non escono dal loro settore specialistico;
• Non hanno creatività e non possono immaginare nuove strategie oltre a
schemi di aggiornamento prefissati;
• La comunicazione con l’uomo è scarsa e non flessibile;
• Sono privi del senso comune.
Un sistema esperto in uso alla Ford per concedere i prestiti, ne concesse uno a un
ragazzo di vent’anni, che vantava dieci anni di onorata carriera: non sapeva
cosa significasse avere vent’anni o dieci.
Douglas Lenat
Automatic Mathematician AM 1982 è un programma
LISP con possibilità di automodificarsi, che partendo
da semplici assiomi impara la matematica (insiemi,
addizioni, ecc.). Automodificandosi corre il rischio di
bloccarsi.
Eurisko è stato usato anche per una variante della
battaglia navale, e crea una strategia con molte navi
piccolissime e veloci, vincendo il campionato.
Cyc, da encyclopedia,1984 contiene 2000000 di regole
che descrivono le conoscenze umane anche più banali
come: “esistono cose che si possono toccare”. Alcune
versioni preliminari di Cyc gestiscono grandi database
“intelligenti”.
Joseph Weizenbaum – Eliza
Lo script Doctor impersona uno psicologo di scuola rogeriana che incoraggia il
paziente a parlare, durante tutta la seduta.
Ma di fronte a frasi come:
“Ho litigato con mia madre” o “Ho visto la Regina Madre” ci chiederebbe
comunque “Mi parli della sua famiglia”.
Kenneth Colby – Parry
Paziente paranoico che si ricorda l’andamento della conversazione.
Traduzioni automatiche
“Ho visto un film con Sharon Stone” – la frase ha due interpretazioni, di cui una
(la presenza fisica di Sharon Stone) viene scartata a priori dagli umani.
Terry Winograd – Shrdlu – 1971
Risposta ai sistemi esperti. Un robot virtuale in un mondo di giocattoli che può:
• Costruirsi una conoscenza completa del mondo e un senso comune sulle
proprietà degli oggetti;
• Modificare il mondo applicando piani e strategie diversi;
• Capire domande e ordini sottoposti in linguaggio naturale.
Giochi
Nel 1950, Claude Shannon, che aveva introdotto l’uso
dell’algebra booleana, teorizza una applicazione per
computer per giocare a scacchi.
Arthur Samuel nel 1960 inventa un programma che gioca
a dama Chinook che usa la regola del min-max. Dopo
poche mosse, osservati gli effetti della scelta, poteva
modificare i propri parametri di scelta del min-max,
migliorandosi.
11 maggio 1997 Deep Blue batte Garry Kasparov a
scacchi (Deep Thought il predecessore, aveva perso
con lui nel 1989).
A detta degli stessi programmatori Deep Blue non pensa
ma usa forza bruta.
Min-max
Secondo la teoria dei giochi di John von Neumann e Oskar
Morgenstern, in ogni momento l’algoritmo del minmax negli
scacchi e in altri giochi può stabilire la mossa migliore da fare. La
mossa massimizzerà il numero di posizioni favorevoli per un
giocatore, minimizzando quelle favorevoli all’avversario. Per
trovarla basta esplorare l’albero della soluzioni quanto più
approfonditamente possibile.
Euristiche
• Sono Regole Pratiche.
• Istruzioni che formalizzano idee intuitive che
eliminano rami interi dell’albero delle soluzioni.
• Un processo che può risolvere un certo problema, ma
che non offre nessuna garanzia di riuscirci, viene detto
un’euristica per quel problema (George Polya).
Cibernetica
• Norbert Wiener applica un potenziometro di
controllo all’artiglieria tenendo conto del
feedback. Sarà il padre della cibernetica, da
kybernetè timoniere.
• 1948 Walter Grey Walter tartarughe elettroniche
Elsie Electro Light sensitive Internal Externsal e
Elmer Electro Mechanical Robot.
• 1957 Planebot braccio robot industriale. Sono
capaci di montaggi e avvitare lampadine, ma
tutto deve essere dettagliatamente programmato
e posizionato con accuratezza.
Rodney Brooks
Costruisce insetti e semplici robot.
Hermes è servito come prototipo alla Nasa per Sojourner.
“L’intelligenza è una proprietà emergente dei sistemi
complessi. Apparirà spontaneamente quando
costruiremo un robot dotato di una gerarchia e di una
coordinazione sufficientemente completa e complicata
di reazioni fra stimolo e risposta”.
Nel 1992 realizza il “bambino
elettronico” di Turing: Kismet
(una testa capace di espressioni
che reagisce a stimoli visivi
esterni) e Cog (un bambino con
braccia che manipola giocattoli).
Il futuro dell’IA
• RoboCup: partite di calcio da 10 minuti con robot
reattivi.
• Reti neurali e Algortimi Genetici.
• Vita artificiale (inventata da von Neumann): Norms di
Stephen Grand.
• Intelligenza Artificiale Distribuita: tanti agenti capaci
di poche operazioni e in grado di coordinarsi.
• Computer affettivi.
Semplificando:
 L’IA forte ha un approccio top down, solo software e
con uso di ragionamento simbolico;
 La cibernetica ha un approccio bottom up.
Contro l’IA
• Secondo il teorema dell’incompletezza di Godel: “ogni
sistema formale è inconsistente, incoerente, cioè
permette di dimostrare frasi false, oppure è incompleto,
cioè non è capace di decidere, dimostrare, la verità o la
falsità di alcuni teoremi”. Un esempio è la frase “io non
sono dimostrabile”; se è dimostrabile è falsa, se invece
la frase fosse vera il teorema non è dimostrabile.
• Roger Penrose usa il teorema di Godel per attaccare
l’IA, sostenendo che nessun computer in grado di
manipolare simboli possa risolvere l’impasse.
• John Searle va contro contro l’IA forte con il paradosso
della Chinese Box, in cui un uomo, rinchiuso con dei
manuali di cinese, interagisce con dei madrelingua
all’esterno. I detrattori sostengono che l’intelligenza sia
nel complesso della stanza (sistema).
Bibliografia
Yurij Castelfranchi – Oliviero Stock
Macchine come Noi – La scommessa
dell’intelligenza Artificiale, Laterza, 2000
David Harel
Computer a responsabilità limitata – Dove le
macchina non riescono ad arrivare, Einaudi,
2000