Apprendimento Automatico

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:


Formato dei file delle immagini PGM:


http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo8/ml94faces/faces/
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+Usa
ge+Data
Scegliere due classificatori giudicati appropriati
al task e applicarli al problema
Analisi di Mercato
degli Utenti Internet
File final_general.col
File changes
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Universal: (when applicable)
•
Not Say! = 0
•
Don't Know = 98
•
Other = 99
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
…
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
00105230111110000001000100000
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
00005356121210000000000000001
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


Una parola può esprimere più significati o sensi:



Può essere supervisionato o non supervisionato
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!