Apprendimento Automatico

Progetti A.A. 2007/2008

Punteggio assegnato alle prove

Prova scritta (25/30) Due esoneri hanno come voto complessivo la

media Progetto (5/30)

Deve essere almeno sufficiente (2,5 punti)

Progetto 1: Face Recognition

Determinare una funzione obiettivo, ad esempio la classificazione dell'espressione, della posa, degli occhi o dell'utente ritratto in una foto

Determinare la rappresentazione delle istanze Apprendere un classificatore basato su rete

neurale alimentata in avanti Il progetto ricalca quello assegnato da Tom

Mitchell alla Carnegie Mellon: http://www.cs.cmu.edu/~tom/faces.html

Face Recognition: immagini da classificare

Le immagini, in formato PGM, si trovano a: http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-

8/ml94faces/faces/ Formato dei file delle immagini PGM:

http://netpbm.sourceforge.net/doc/pgm.html Libreria Java per il caricamento di file PGM:

http://www.thur.de/~Voland/pub/java/pgmdiff/pgm.java

Face Recognition: classi Il nome di ciascun file immagine è del tipo:

user-id_posa_espressione_occhi_scala.pgm user-id: nome della persona posa: posizione della testa scelto tra { straight, left,

right, up } espressione: espressione facciale scelta tra { neutral,

happy, sad, angry } occhi: stato degli occhi { open, closed } scale: dimensione dell'immagine scelta tra { 1, 2, 4}

indica rispettivamente: 128x120, 64x60, 32x20

Face Recognition

Progetto 1: Elementi di Valutazione

Rappresentazione delle istanze Struttura e parametrizzazione della Rete

Neurale Analisi delle prestazioni

Valutate anche rispetto alle baseline (es. la classe più frequente, una scelta a caso, ecc.)

Progetto 2: Analisi di Mercato

Dato un insieme di dati relativi agli utenti sulla rete, scegliere una funzione obiettivo (ad esempio: identificare la fascia di reddito degli utenti (attributo Household Income) oppure la disponibilità a pagare per ottenere servizi (attributo Willingness to Pay Fees))

Data set ottenibile all’indirizzo: http://archive.ics.uci.edu/beta/datasets/

Internet+Usage+Data Scegliere due classificatori giudicati appropriati

al task e applicarli al problema

Analisi di Mercato degli Utenti Internet

File final_general.col

• Actual Time• Age• Community Building• Community Membership_Family• Community Membership_Hobbies• Community Membership_None• Community Membership_Other• Community Membership_Political• Community Membership_Professional• Community Membership_Religious• Community Membership_Support• Country Disability_Cognitive• Disability_Hearing• Disability_Motor• Disability_Not Impaired• Disability_Not Say• Disability_Vision• Education Attainment• Falsification of Information• Gender• Household Income• …

File changes

Universal: (when applicable)• Not Say! = 0 • Don't Know = 98• Other = 99

Education level:• grammar=0• high school=1• professional=2• some college=3• college=4• masters=5• doctoral=6• special=7• other=99

Gender:• female=0• male=1

…

Analisi di Mercato degli Utenti Internet

final_general.dat.gz: (5 41 2 0 0 1 0 0 0 0 0 40 0 0 0 1 0 0 5 1 1 8 0 0 0 0 0

0 0 1 0 5 2 3 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 99 2 93819 )

(2 28 2 0 0 0 0 0 0 0 1 40 0 0 0 1 0 0 3 2 0 1 1 0 0 0 0 0 0 0 0 5 3 5 6 1 2 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 2 0 0 0 0 1 0 4 0 95708)

(99 25 0 1 1 0 0 0 1 0 0 7 0 0 0 1 0 0 4 2 1 8 0 0 0 0 0 0 0 0 1 5 0 99 6 4 2 1 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 2 1 1 1 0 0 0 0 1 1 99 2 97218)

Progetto 2: Elementi di Valutazione

Classificatori prescelti Analisi delle prestazioni

Valutate anche rispetto alle baseline (es. la classe più frequente, una scelta a caso, ecc.)

Studio delle prestazioni al variare della dimensione del data set

Studio delle prestazioni quando valuto il classificatore su: un test set separato, il training set, ten-fold cross validation, ecc.

Progetto 3: Natural Language Processing (NLP)

Apprendere un classificatore per risolvere l’ambiguità di una parola Può essere supervisionato o non supervisionato

Una parola può esprimere più significati o sensi: the musicians left their instrument cases backstage it may rain in which case the picnic will be canceled

Fissata la parola di interesse (es. case) avremo un classificatore che data una frase rappresentata in un certo modo fornisce il senso più appropriato (Word Sense Disambiguation) Nel caso non supervisionato, in realtà siamo noi a creare i

sensi senza conoscere un inventario a priori (Word Sense Discrimination)

WordNet WordNet è un dizionario gratuito in formato elettronico della

lingua inglese (http://wordnet.princeton.edu) E’ organizzato come una rete semantica: dato un senso di una

parola, è possibile ottenere informazioni quali: Iperonimi, ovvero antenati nella gerarchia tassonomica (case is-a

container is-a instrumentality is-a artifact is-a object)

Word Sense Disambiguation Data una frase contenente la parola in esame:

The musicians left their instrument cases backstage.

Si applica il part-of-speech tagging (categorizzazione sintattica): The/DT musician/NN leave/VB their/JJ instrument/NN

case/NN backstage/RB. DT: articolo o aggettivo indicativo NN: nome VB: verbo PRP: pronome possessivo JJ: aggettivo RB: avverbio

Word Sense Disambiguation

Determinare le caratteristiche per rappresentare un’istanza

Data la lunghezza variabile di una frase, ci concentriamo sull’”intorno” della parola in esame (es. case): Lemma di k parole a sinistra e destra di case: their,

instrument, (a sinistra), backstage, - (a destra) Il lemma è la forma “normalizzata” di una parola

(singolare per i nomi, infinito per i verbi, ecc.) Part of speech di k parole a sinistra e destra: JJ,

NN, RB, -

Word Sense Disambiguation

Altre caratteristiche che si possono aggiungere alla rappresentazione (opzionale): Informazioni ottenute da dizionari (es. WordNet)

Iperonimi, concetti in alto nella gerarchia tassonomica (solo per i nomi)

Informazioni di dominio delle parole della frase WordNet domains

Per ogni parola della frase, si possono conteggiare i domini associati ai diversi sensi delle varie parole

case#n#1: law (legge) case#n#11: furniture (arredamento) ecc.

Progetto 3: Elementi di Valutazione

Scelta delle feature Algoritmo di apprendimento Valutazione:

nel caso supervisionato, vi fornisco io le etichette per ciascun esempio nel data set

nel caso non supervisionato, se fissiamo il numero di cluster pari o vicino al numero di sensi in WordNet per la parola in esame, possiamo valutare se i cluster ottenuti hanno una correlazione rispetto ai sensi in WordNet

Giochi Classici: Progetto 4 Scegliere un classificatore per uno dei giochi seguenti:

Tris (Tic Tac Toe)

Dama (http://www.aaai.org/AITopics/html/checkers.html)

MasterMind

Se utilizzate un classificatore “classico” (es. decision trees), potreste voler:

Generare insiemi d'addestramento di varie dimensioni per capire quale dimensione è sufficiente per apprendere un classificatore accurato

Valutare il classificatore in una partita reale contro di voi o contro un giocatore preconfezionato

Altre idee?

Oppure: programmazione genetica, apprendimento per rinforzo

Valutare il classificatore in una partita reale contro di voi oppure contro un giocatore preconfezionato

Progetto 4: Elementi di Valutazione

Rappresentazione delle istanze o dei programmi Scelta del classificatore Valutazione del modello appreso

Progetto 5: Videogioco Pac-man (http://it.wikipedia.org/wiki/Pac-Man):

Progetto 5: Videogioco Pac-man (http://it.wikipedia.org/wiki/Pac-Man):

Abbiamo un mondo costituito da una matrice NxN Ogni elemento della matrice è: vuoto, pillola

normale, pillola speciale, muro Due tipi di agenti: Pac-man e i fantasmini Apprendere un buon agente di tipo Pac-man, che

vinca il maggior numero di partite

Progetto 5: Elementi di Valutazione

Rappresentazione degli agenti Scelta dell’algoritmo di apprendimento Valutazione del modello appreso Fantasia!

Progetto 6: Controllo del Traffico Apprendere un modello per il controllo del

traffico Problemi:

Rappresentare la strada

Esempio http://www.vishnu.bbn.com/papers/traffic/traffic.html Utilizza la programmazione genetica (PG) Ad esempio, la funzione di fitness scelta è:

Per implementare il controllo dei segnali, si devono realizzare alcune funzioni che le “creature” di PG possono utilizzare per accedere alle informazione sugli incroci

Function Description Result Type

QUEUE_FULL Is the traffic backed up to the sensors? boolean

WAITING Is a car waiting at the intersection? boolean

TIME_SINCE_CHANGE How many seconds ago was the light last changed?

integer

APPROACHING Is a car current approaching the intersection? boolean

CONSTANT_X Get the value of the constant X for the current signal and the current active street

integer

Esempio

Le regole apprese:

Progetto 6: Elementi di Valutazione

Rappresentazione degli oggetti (incroci, semafori, veicoli)

Scelta dell’algoritmo di apprendimento Valutazione del modello appreso (su quante

simulazioni la coda raggiunge il sensore di coda piena?)

Fantasia!