Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

29
Apprendimento Automatico: Introduzione Roberto Navigli 1 Roberto Navigli Apprendimento Automatico: Introduzione

Transcript of Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Page 1: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

1

Roberto Navigli

Apprendimento Automatico:Introduzione

Page 2: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

2

Apprendimento Automatico (Machine Learning)

• Una delle aree fondamentali dell’Intelligenza Artificiale• Mira a sviluppare algoritmi e metodi al fine di permettere

alla macchina di apprendere• Apprendimento: il processo di “comprendere”

costruendo un modello dei dati osservati al fine di utilizzarlo in predizioni future– Regole d’associazione– Classificazione– Regressione– Clustering

• Tipicamente si vuole ottimizzare un criterio di prestazione utilizzando dati d’esempio o precedente esperienza

Page 3: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

3

Dove si colloca l’Apprendimento Automatico

sapere

Page 4: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

4

Dove si colloca l’Apprendimento Automatico

scienze

Page 5: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

5

Dove si colloca l’Apprendimento Automatico

informatica

Page 6: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

6

Dove si colloca l’Apprendimento Automatico

Intelligenza Artificiale

Page 7: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

7

Cos’è l’Intelligenza Artificiale?

A voi la risposta…

Page 8: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

8

Un’area dell’Intelligenza Artificiale

• Risoluzione di problemi• Ragionamento automatico• Pianificazione• Apprendimento automatico• Rappresentazione della conoscenza• Elaborazione del linguaggio naturale• Visione artificiale• Robotica• …

Page 9: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

9

Macchine “Intelligenti” in Breve (1)

• L’idea di dispositivi meccanici e macchine intelligenti data almeno ai tempi della Grecia antica

• Aristotele inventa il sillogismo, il primo sistema formale di deduzione logica (V secolo a.C.)

Page 10: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

10

Macchine “Intelligenti” in Breve (1)

• L’idea di dispositivi meccanici e macchine intelligenti data almeno ai tempi della Grecia antica

• Aristotele inventa il sillogismo, il primo sistema formale di deduzione logica (V secolo a.C.)

• Roger Bacon (frate, filosofo e scienziato) si dice abbia creato teste parlanti (“talking heads”) che potevano rispondere a qualsiasi domanda (XIII secolo d.C.)

Page 11: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

11

Macchine “Intelligenti” in Breve (1)

• L’idea di dispositivi meccanici e macchine intelligenti data almeno ai tempi della Grecia antica

• Aristotele inventa il sillogismo, il primo sistema formale di deduzione logica (V secolo a.C.)

• Roger Bacon (frate, filosofo e scienziato) si dice abbia creato teste parlanti (“talking heads”) che potevano rispondere a qualsiasi domanda (XIII secolo d.C.)

• La Bibbia di Gutenberg va in stampa (1456)• Blaise Pascal (1642) creò la prima calcolatrice, migliorata poi da

Leibniz

Page 12: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

12

Macchine “Intelligenti” in Breve (1)

• L’idea di dispositivi meccanici e macchine intelligenti data almeno ai tempi della Grecia antica

• Aristotele inventa il sillogismo, il primo sistema formale di deduzione logica (V secolo a.C.)

• Roger Bacon (frate, filosofo e scienziato) si dice abbia creato teste parlanti (“talking heads”) che potevano rispondere a qualsiasi domanda (XIII secolo d.C.)

• La Bibbia di Gutenberg va in stampa (1456) • Blaise Pascal (1642) creò la prima calcolatrice, migliorata poi da

Leibniz• Mary Shelley pubblica Frankestein (1818)

Page 13: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

13

Macchine “Intelligenti” in Breve (1)

• L’idea di dispositivi meccanici e macchine intelligenti data almeno ai tempi della Grecia antica

• Aristotele inventa il sillogismo, il primo sistema formale di deduzione logica (V secolo a.C.)

• Roger Bacon (frate, filosofo e scienziato) si dice abbia creato teste parlanti (“talking heads”) che potevano rispondere a qualsiasi domanda (XIII secolo d.C.)

• La Bibbia di Gutenberg va in stampa (1456) • Blaise Pascal (1642) creò la prima calcolatrice, migliorata poi da

Leibniz• Mary Shelley pubblica Frankestein (1818)• Charles Babbage e Lady Ada Byron (Lovelace) inventarono la

prima macchina programmabile (macchina analitica, 1837-71)

Page 14: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

14

Macchine “Intelligenti” in Breve (2)

• Warren McCulloch e Walter Pitts pubblicano "A Logical Calculus of the Ideas Immanent in Nervous Activity" (1943), gettando le fondamenta per le reti neurali

• Alan Turing pubblica "Computing Machinery and Intelligence" (1950), in cui viene proposto il Test di Turing:

– La macchina riesce a comportarsi in modo sufficientemente simile a un essere umano?

– Se una macchina supera il test di Turing, allora è intelligente (Strong AI)• Isaac Asimov pubblica le tre leggi della robotica (1950)• John McCarthy conia il termine “intelligenza artificiale" come argomento

della Dartmouth Conference, la prima conferenza sul tema (1956)• Arthur Samuel (IBM) scrive il primo programma che gioca (a dama, 1952-

62) • Margaret Masterman e colleghi (Cambridge) inventano le reti semantiche

per la traduzione automatica• Marvin Minsky e Seymour Papert

pubblicano “Perceptrons” (1968) e dimostrano i limiti delle reti neurali semplici

Page 15: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

15

Macchine “Intelligenti” in Breve (3)

• Terry Winograd dimostra come sia possibile scrivere programmi che comprendano semplici comandi in lingua inglese (SHRLDU)

– Natural Language Understanding

• Nel 1975, Minsky pubblica “A framework for representing knowledge” (introducendo i frame)

• Metà degli anni ’70: emergono i limiti degli approcci GOFAI all’IA– GOFAI (Good Old-Fashioned Artificial Intelligence): l’approccio storico all’IA basato su logica e

risoluzione dei problemi in domini ristretti (es. giocare a scacchi)

• 1978: Tom Mitchell (Stanford) inventa il concetto di Spazio delle Versioni per descrivere lo spazio di ricerca di un programma per la formazione di concetti

• Anni ‘80: le reti neurali vengono ampiamente utilizzate grazie all’algoritmo di Backpropagation (descritto per la prima volta da Werbos nel 1974).

• Inizio anni ’90: TD-Gammon, sviluppato da Gerry Tesauro, dimostra l’importanza dell’apprendimento per rinforzo (campione del mondo)

• Deep Blue (programma per scacchi) batte l’attuale campione del mondo, Garry Kasparov

Page 16: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

16

Macchine “Intelligenti” in Breve (3)

• Camera cinese– Esperimento (Searle, 1980) che tenta di dimostrare come una

macchine che elabora simboli non possa “comprendere” o avere una “mente”

– Supponiamo che l’IA abbia finalmente realizzato un programma per computer che si comporti come se fosse in grado di comprendere il cinese. Data una stringa cinese in ingresso, esso fornisce una risposta in cinese. Supponiamo che la macchina passi il Test di Turing.

– Supponiamo che un essere umano abbia un manuale in inglese contenente il suddetto programma… egli passerebbe il test non capendo tuttavia nulla di cinese!

Page 17: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

17

Perché non scrivere direttamente un programma?

• Esercizio: provate a scrivere un programma che giochi bene a scacchi– Claude Shannon: "Programming a computer to play chess" (1950).

• Situazioni in cui non è possibile codificare semplicemente la conoscenza in un programma:– Esperienza umana non è disponibile (es. una sonda spaziale)– L’uomo non è in grado di spiegare l’esperienza (es.

riconoscimento del parlato)– Le scelte cambiano nel tempo (sistemi dinamici, reti di computer)– Le scelte devono essere adattate a casi particolari (es.

riconoscimento dei volti)

Page 18: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

18

Apprendimento Automatico Schematizzato

classificatore

supervisione

ambiente

dati

classificazione

Page 19: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

19

Esempio di Problema di Apprendimento Automatico (1)

• Riconoscimento della scrittura:

Page 20: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

20

Esempio di Problema di Apprendimento Automatico (2)

• Risoluzione dell’ambiguità del linguaggio:– Es. ricerca con google: beagle

– Eppure beagle significa:

Page 21: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

21

Esempio di Problema di Apprendimento Automatico (3)

• Agenti intelligenti:

Page 22: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

22

Apprendimento Automatico: Altri Esempi

• Strategie di marketing: impiego di informazioni d’acquisto per determinare suggerimenti pubblicitari (es. amazon)

• Classificazione di una forma d’onda in una parola del lessico (speech recognition)

• Question typing: classificazione del tipo di domanda in un sistema di Question Answering

• Rischio del credito: quanto è affidabile un cliente?• Determinare il comportamento di un personaggio in un

ambiente di storytelling (es. storytron)• Traduzione automatica (machine translation)• Conduzione di autovetture

Page 23: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

23

Come apprendiamo noi?

cake, cake, cake, I do love cake!cake, cake, cake, I do love cake!

Page 24: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

24

Importanza dell’Apprendimento Automatico

• Collo di bottiglia della conoscenza (knowledge acquisition bottleneck)– E’ più facile acquisire automaticamente la conoscenza che codificarla a

mano

• Progressi nell’area degli algoritmi e dei modelli teorici e sperimentali

• Macchine più potenti• Applicazioni industriali rilevanti • Crescente disponibilità di dati in linea

– Wikipedia, Wiktionary, Flickr, Twitter, ecc.– Collezioni di blog– Google Web1T– Search log– Reti sociali

• Fortissima relazione con il data mining

Page 25: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

25

Notizie sul corso

• 4 crediti (dal prossimo anno: 6 crediti!)• 11 settimane (45 ore circa)• Testi:

– T. Mitchell. Machine Learning, McGrawHill, 1997– E. Alpaydin. Introduction to Machine Learning, MIT Press, 2004– P. Tan, M. Steinbach, V. Kumar, Introduction to Data Mining,

Pearson Addison Wesley, 2005

• Pagina del corso:– http://twiki.di.uniroma1.it/twiki/view/ApprAuto

• Per discussioni, progetto, ecc. iscrivetevi al gruppo google apprauto2010:– http://groups.google.com/group/apprauto2010

Page 26: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

26

Argomenti del Corso

• Apprendimento supervisionato– Alberi di decisione– Apprendimento basato su istanze – Apprendimento probabilistico– Reti neurali

• Apprendimento non supervisionato– Clustering

• Apprendimento per rinforzo• Applicazioni: Traduzione automatica

Page 27: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

27

Modalità d’Esame

• E’ necessario:– Sostenere due prove scritte d’esonero oppure una prova orale

a fine corso– Realizzare un progetto in java (→ thesis track available)

• Il progetto sarà modulare, in modo da poter essere svolto in gruppo ma anche da consentire che ognuno sia in grado di svolgere la sua parte di lavoro autonomamente:– Sarà prevista una revisione periodica del progetto dal momento

della sua assegnazione fino alla prima data di consegna

• Chi non segue, può richiedere un progetto ad hoc, assegnato dal docente, e può svolgere solo la prova orale

Page 28: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

28

Sogni realizzabili

• Ricevimento a fine lezione una volta a settimana• Alla fine di ogni lezione saranno proposti uno o più

esercizi da svolgere a casa– Non è obbligatorio svolgerli, ma serve a rendere più solida la

vostra preparazione

• Dispense• Laddove possibile, proporre spunti di ricerca

– Un universo da esplorare…

• Proporvi seminari di ricerca attinenti la materia– Es. caffè scienza, visitatori del dipartimento, ecc.

• Birra & ricerca

Page 29: Apprendimento Automatico: Introduzione Roberto Navigli 1 Apprendimento Automatico: Introduzione.

Apprendimento Automatico: IntroduzioneRoberto Navigli

29

Sogni meno realizzabili