1

1

Intelligenza artificiale

Docenti:

Francesca Rossi, Alessandro Sperduti

2

Scopo del corso

Fornire tecniche e strumenti tipici dell’intelligenza artificiale

Suddivise in tante aree diverse, ognuna con le sue tecniche

Uso in problemi di tutti i giorni

3

Organizzazione del corso

Docenti:

Francesca Rossi (prima parte)

Alessandro Sperduti (seconda parte)

Lezioni in aula

Progetto a gruppi (circa 30 ore ciascuno) e due compitini (o orale)

Orario:

Lunedi’ 15:30-17:30

Martedi’ 15:30-17:30

Mercoledi’ 13:30-15:30

Giovedi’ 11:30-13:30

Aula: 1BC50

4

Forme di progetto (1)

Proattivo

Su proposta dello studente, previa discussione con il docente. Sono, ad esempio, incoraggiate attivita’ relative all'introduzione di tecniche dell'Intelligenza Artificiale all'interno di sistemi sviluppati per i corsi di Ingegneria del Software della Laurea Triennale.

Contributivo

Alcuni degli algoritmi presentati nel libro di testo sono stati implemetati e resi disponibili in un "Online Code Repository". Gli algoritmi sono implementati nei seguenti linguaggi: Python, Java, Lisp.

Diversi algoritmi non sono ancora implementati (in alcun linguaggio, o per alcuni linguaggi, ad esempio Java) e possono quindi costituire oggetto del progetto.

5

Forme di progetto (2)

Conoscitivo/Comparativo Lo studente "sperimenta" vari sistemi esistenti e

reperibili in rete e li compara con spirito critico rispetto a varie dimensioni, fra cui: facilita’ d'uso, facilita’ di comprensione/modificabilità del codice sorgente, prestazioni rispetto al dominio applicativo.

La relazione finale del progetto assume in questo caso ruolo preminente.

Esplorativo Lo studente elabora e sperimenta idee proprie,

come ad esempio euristiche relative ad un particolare dominio applicativo.

6

Gruppi/prodotti del progetto

Gruppi di lavoro: Sono ammessi gruppi di lavoro non superiori a

3 studenti (preferibilmente 2 studenti).

Prodotti del progetto: Relazione finale (in HTML) che descrive

l'attivita’ svolta, incluso almeno un caso di studio

2 punti in piu’ nel voto finale se si presenta il progetto tramite presentazione pubblica

Codice prodotto (nei casi in cui e’ previsto)

Consuntivo orario delle singole attivita’ svolte.

2

7

Risorse

Libro:

S. Russell, P. Norvig, "Artificial Intelligence: a Modern Approach",

Prentice Hall, 2002 (II edizione) o … (III

edizione)

Lucidi e altre informazioni (prima parte): www.math.unipd.it/~frossi/ia2011.html

8

Contenuti del corso

Introduzione, storia

Agenti intelligenti Risoluzione di problemi: ricerca, giochi,

soddisfacimento di vincoli

Rappresentazione della conoscenza e ragionamento: calcolo proposizionale calcolo dei predicati deduzione automatica introduzione alla programmazione logica

Pianificazione

Cenni di Apprendimento Automatico Trattamento dell'Incertezza

approccio probabilistico reti bayesiane

9

Cos’e’ l’IA?

Diverse nozioni

Sistemi hardware/software che

Pensano come gli umani

Agiscono come gli umani

Pensano razionalmente

Agiscono razionalmente

10

Agire come gli umani:

Test di Turing (1950)

A uomo, B computer C persona (separata da A e B) C pone domande ad A e B per riconoscere

chi e’ l’uomo e chi e’ il computer Comunicazione via testo B puo’ cercare di ingannare C

Idea alla base del test: Le macchine possono pensare? Le macchine

possono comportarsi in modo intelligente? L’intelligenza puo’ essere misurata guardando il

comportamento esterno, non il ragionamento che ha portato a quel comportamento

Intelligente = umano Ma ci sono comportamenti umani che non sono

intelligenti, e viceversa

11

Pensare come gli umani:

Scienze (neuro)cognitive

Teorie scientifiche dell’attivita’ interna del cervello

Non riescono a modellare l’intelligenza umana generale

12

Pensare razionalmente:

leggi del pensiero

Aristotele: quali sono i processi del pensiero?

Logica, regole di derivazione del pensiero

Filosofia, matematica

Non tutti i comportamenti intelligenti sono regolati da deliberazioni logiche

3

13

Agire razionalmente

Eseguire l’azione migliore per massimizzare il raggiungimento di un

obbiettivo

date le informazioni a disposizione

Agente: entita’ che percepisce e agisce Funzione da storie di percezioni ad azioni

f: P* A

Limitazioni computazionali la razionalita’ perfetta e’ spesso impossibile

Cerchiamo l’agente migliore per lo scopo da raggiungere, date certe limitazioni computazionali

14

Breve storia dell’IA

1943: McCulloch & Pitts: Modelli del cervello basati siu circuiti Booleani

1950: Test di Turing 1952-69: Molte promesse e eccitamento per specifici programmi 1950s: Primi programmi di IA (dama, deduzioni logiche, teoriemi di

geometria, ecc.) 1956: incontro di Dartmouth (termine “IA”) 1965: algoritmi di Robinson per il ragionamento logico 1966-74: IA scopre la complessita’ computazionale, reti neurali quasi

scompaiono 1969-79: Primi sistemi basati su conoscenza 1980-88: Sistemi esperti nell’industria 1988-93: I sistemi esperti non ripecchiano le promesse (inverno

dell’IA) 1985-95: Ritornano le reti neurali 1988- : Maggiore base scientifica e tecnica (neat vs. scruffy) 1995- : Agenti dappertutto 2003- : IA per scopi specifici, integrata in altri sistemi, …

15

Le macchine hanno dei limiti

Godel (1932) Dato un qualunque sistema formale, ci sono

affermazioni vere che non possono essere provate dalle regole logiche di quel sistema

Turing (1936) Analogo in termini di macchine Macchina di Turing: modello generale

astratto di un calcolatore Sequenza di passi elementari Scrittura e lettura su un nastro infinitamente

lungo

Ci sono dei problemi che la macchina di Turing non puo’ risolvere Esempio: dato un programma P e un suo

input I, decidere in tempo finito se P(I) si ferma o va in ciclo

Affermazioni vere che non possono essere generate dalla macchina

Con questi limiti, possiamo costruire una macchina “intelligente”?

16

Test di Turing (1950)

A uomo, B computer C persona (separata da A e B) C pone domande ad A e B per riconoscere

chi e’ l’uomo e chi e’ il computer Comunicazione via testo B puo’ cercare di ingannare C

Idea alla base del test: L’intelligenza puo’ essere misurata guardando il

comportamento esterno, non il ragionamento che ha portato a quel comportamento

Intelligente = umano Ma ci sono comportamenti umani che non sono

intelligenti, e viceversa

E’ questa la nozione corretta di IA, o comunque quella che ci interessa ottenere?

17

Gli inizi dell’IA come scienza

McCarthy, Shannon, Minsky Analogia tra calcolo matematico e comportamento

degli esseri umani Computer = cervello Come si simula l’intelligenza umana?

1956: incontro di Dartmouth (NH, USA) John McCarthy introdusse il termine Intelligenza

Artificiale

Logic Theorist (Simon) Provo’ 38 su 52 teoremi dai Principia Mathematica

di Russell e Whitehead

General Problem Solver (Carnegie Institute) Prove di teoremi e puzzles Prova di un teorema aperto

18

LISP (MIT), 1958

Linguaggio per creare programmi di IA in domini diversi tra loro

Esempi: Student: risolve problemi

algebrici in forma di frase

Dendral: risolve problemi di chimica

4

19

Altre milestones

ELIZA (1965) Programma che interagisce con i pazienti Imita un terapista rogeriano Intelligente secondo il test di Turing Solo matching di parole chiave, senza

nessuna comprensione del testo

MYCIN (1976) Sistema esperto che effettua diagnosi per

malattie ematiche infettive

CYC (dal 1983) Ragionamento basato sul senso comune

Base di dati di conoscenza (20 milioni di fatti ovvi ma dati per scontati)

Collegamenti tra fatti e logica induttiva Non si puo’ restringere il dominio se si vuole

il senso comune

Deep Blue (1997) Batte a scacchi il campione del mondo

Kasparov

20

Approccio connessionista

Reti neurali (dagli anni ’60)

Si ispirano al cervello umano

Neuroni e connessioni tra loro

Apprendimento automatico tramite aggiustamento dei pesi delle connessioni

Sulla base di esempi

21

IA “debole”

Risolvere specifici problemi o effettuare ragionamenti che non possono essere compresi pienamente dalle capacità cognitive umane No autoconsapevolezza No intuito No ampiezza di livelli di abilità cognitive

proprio dell'uomo Si risolutore di problemi specifici, anche

molto difficili, in modo intelligente

Puo’ essere detta intelligente una macchina con queste caratteristiche?

22

Scienza o fantascienza?

Hal (2001-Odissea nello spazio), 1968 Perche’ non c’e’ ancora un computer come HAL? Abbiamo raggiunto e superato HAL in molti domini

linguaggio Hardware Scacchi Ecc.

Ma in domini come il senso comune abbiamo ottenuto poco Poco delimitati

Difficili da specificare

Ci interessa un computer che possa imitare il pensiero e il comportamento umano?

Negli attuali convegni di IA, sono descritte soprattutto macchine (hw o sw) intelligenti in modo mirato e utile per l’uomo

23

Analogia IA vs. volo artificiale

Il sogno di volare non si e’ realizzato imitando gli uccelli

Nessuno cerca di costruire una macchina che voli in modo cosi’ simile ad un piccione che puo’ ingannare altri piccioni!

L’IA puo’ essere realizzata anche senza imitare il ragionamento umano, e senza cercare di superare il test di Turing Affiancare/aumentare

l’intelligenza umana

In alcuni domini specifici

24

Aiuto o sostituto?

Non si vuole costruire un sosia

dell’uomo

Tecnologie che incrementano alcuni aspetti dell’intelligenza umana

Aiutate anche dalla potenza di calcolo e dalla

quantita’ di memoria

Esempio: Google usa algoritmi basati anche su programmi di IA

Utilissimo per fare in modo intelligente una cosa ben precisa: cercare informazioni sul web

5

25

Cosa puo’ essere fatto con l’IA?

Esempi: Sistemi esperti (medicina, altri campi dove serve un esperto umano) Scacchi Sistemi di schedulazione di aerei Gestione turni personale Robot per ospedali Lettori per ciechi

Traduzione, comprensione del linguaggio naturale Biologia e genomica Riconoscimento di oggetti, visione Ricerca su web, aste online Guida autonoma su strade di citta’ o montagna Comprare articoli su web Traduzione tra linguaggi

Aiutano gli uomini a compiere in modo intelligente lavori specifici che altrimenti sarebbero eseguiti meno bene o non eseguiti affatto

26