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!