AnnoAcc0708 < ApprAuto

---+!! Apprendimento Automatico - A.A. 2007-2008
---++ Docente: Roberto Navigli

| *Docente*             |  *Telefono*  | *Orario di ricevimento* | *Studio* |
| [[http://www.dsi.uniroma1.it/~navigli/index.html][Roberto Navigli]]  | 06-49918472 | Lunedì 14:00-15:00 | Via Salaria 113 - 3° Piano st. 312 | 

---++ Orari del corso

| *Quando*             |  *Dove*  |
| Martedì 13.00-15.00 | aula V (matematica) |
| Venerdì   8.30-10.30    | aula seminari DI (via salaria 113)|

---++ Introduzione

Il corso introduce un'area dell'<b>Intelligenza Artificiale</b>, detta appunto *Apprendimento Automatico* (*Machine Learning*). 
Il corso si svolge in circa 40-45 ore di lezione frontale (10-11 settimane). L'esame *consiste in una prova orale*, per verificare la conoscenza degli algoritmi studiati, ed *una prova pratica* (il *progetto*), sull'uso di (alcuni) degli algoritmi studiati, in vari ambiti applicativi. La prova orale può essere *sostituita da una prova scritta* che si terrà nei mesi di gennaio e febbraio. Verrà svolta *una prova scritta in itinere* (a mo' di esonero per la prima parte del programma), come per tutti gli altri corsi, nella settimana prestabilita a tale scopo ogni anno.

Durante il corso, verranno introdotti e discussi i principali algoritmi di apprendimento automatico.  
Gli studenti potranno, praticamente per ciascun algoritmo,  effettuare delle esercitazioni pratiche utilizzando il software [[http://www.cs.waikato.ac.nz/ml/weka/][Weka]], che mette a disposizione implementazioni dei vari algoritmi, e utilities varie per lo studio dei risultati. 
Viene anche messo a disposizione un sito che raccoglie dati pre-elaborati e praticamente pronti per l'utilizzo da parte di algoritmi di ML, in ambiti vari (medicina, biologia, marketing, riconoscimento di immagini, ecc.).

---++ Avvisi

   * Il *ricevimento del 22 settembre 2008* è spostato al *23 settembre*, stessa ora.
   * Il *ricevimento del 7 e del 21 luglio 2008 è annullato*. Per favore, inviate un'email al docente per prendere appuntamento durante la settimana.
   * Causa esami, il *ricevimento del 18 febbraio 2008 è anticipato alle ore 11.00 (fino alle ore 12.00)*.
   * Il docente sarà all'estero per motivi di ricerca *dal 25 gennaio al 15 febbraio*. Il ricevimento è pertanto sospeso durante quel periodo. Per qualsiasi necessità, potete contattare il docente via email. 
   * La lezione di *venerdì 14 dicembre 2007* non avrà luogo per la concomitanza con il diciottesimo incontro con le aziende: siete tutti invitati (e interessati) a partecipare! L'incontro si terrà in Aula Alfa (piano terra, via salaria), dalle ore 9.
   * La lezione di *venerdì 30 novembre 2007* non avrà luogo.
   * La lezione di *venerdì 2 novembre 2007* non avrà luogo.
   * La lezione di *venerdì 5 ottobre 2007* non avrà luogo.

---++ Appelli 2007/2008

Il prossimo appello d'esame (orale) per l'A.A. 2007/2008 si terrà il *16 settembre alle ore 9 in aula alfa (via salaria)*. Per prenotarvi, inviate un'email al docente.

Testi e risultati delle prove precedenti:
 
   * [[%ATTACHURL%/esame_21_02_2008.pdf][Testo e soluzioni dell'esame scritto del 21 febbraio 2008]]
   * [[Risultati dell'esame scritto del 21 febbraio 2008]]
   * [[%ATTACHURL%/esame_22_01_2008.pdf][Testo dell'esame scritto del 22 gennaio 2008]]
   * [[Risultati dell'esame scritto del 22 gennaio 2008]]
   * [[%ATTACHURL%/esonero_15_01_2008.pdf][Testo e soluzioni del secondo esonero del 15 gennaio 2008]]
   * [[Risultati del secondo esonero]]
   * [[%ATTACHURL%/esonero_13_11_2007.pdf][Testo e soluzioni del primo esonero del 13 novembre 2008]]
   * [[Risultati della prova intermedia][Risultati del primo esonero]]

---++ Argomenti trattati nel corso

| *Data*             |  *Argomenti*  | *MS* | *PDF* | *Note* |
| 25 settembre 2007 | Introduzione | [[%ATTACHURL%/1Intro.ppt][ppt]] | [[%ATTACHURL%/1Intro.pdf][pdf]] | |
| 28 settembre 2007 | Apprendimento dei concetti (1) | [[%ATTACHURL%/2Example.ppt][ppt]] | [[%ATTACHURL%/2Example.pdf][pdf]] | |
| 2 ottobre 2007 | Esercitazione sull'algoritmo !VersionSpace | [[%ATTACHURL%/VSesempi.ppt][ppt]] | [[%ATTACHURL%/VSesempi.pdf][pdf]] | |
| 9 ottobre 2007 | Apprendimento dei concetti (2),<br>Alberi di decisione (1)| <br>[[%ATTACHURL%/3Decision.ppt][ppt]] | <br>[[%ATTACHURL%/3Decision.pdf][pdf]] |  |
| 12 ottobre 2007 | Alberi di decisione (2)| | |  |
| 16 ottobre 2007 | Introduzione a Weka,<br>Reti neurali (1) | [[http://garr.dl.sourceforge.net/sourceforge/weka/weka.ppt][ppt]] <br>[[%ATTACHURL%/4Neural.ppt][ppt]]| [[%ATTACHURL%/weka.pdf][pdf]]<br>[[%ATTACHURL%/4Neural.pdf][pdf]] | fino alla diapositiva 56 |
| 19 ottobre 2007 | Reti neurali (2),<br>Valutazione delle prestazioni | <br>[[%ATTACHURL%/ValutazionePrestazioni.ppt][ppt]]| <br>[[%ATTACHURL%/ValutazionePrestazioni.pdf][pdf]] | |
| 23 ottobre 2007 | Reti neurali (3) | | | |
| 26 ottobre 2007 | Reti neurali (4)<br>Esercitazione su Reti neurali | <br>[[%ATTACHURL%/Esercitazione3.doc][doc]] | <br>[[%ATTACHURL%/Esercitazione3.pdf][pdf]] | |
| 30 ottobre 2007 | Esercitazione su alberi di decisione,<br> Richiamo di concetti di probabilità | [[%ATTACHURL%/Esercitazione2.doc][doc]]<br> [[%ATTACHURL%/5Bayes.ppt][ppt]]| <br>[[%ATTACHURL%/5Bayes.pdf][pdf]] | |
| 6 novembre 2007 | Apprendimento Bayesiano (1) | [[%ATTACHURL%/5Bayes.ppt][ppt]]| [[%ATTACHURL%/5Bayes.pdf][pdf]] | |
| 9 novembre 2007 | Esercitazione di preparazione all'esonero | | | |
| 13 novembre 2007 | <b>Prova intermedia</b> | | [[%ATTACHURL%/esonero_13_11_2007.pdf][pdf]] ||
| 20 novembre 2007 | Apprendimento Bayesiano (2),<br>Esercitazione su Naive Bayes,<br>Weka per Reti Neurali e Naive Bayes |<br>[[%ATTACHURL%/Esercitazione4.doc][doc]]|<br>[[%ATTACHURL%/Esercitazione4.pdf][pdf]]| File ARFF per [[%ATTACHURL%/xor.arff][XOR]] <br>e risoluzione dell'ambiguità<br>delle parole ([[%ATTACHURL%/wsd_train.arff][training]] e [[%ATTACHURL%/wsd_test.arff][test set]]) |
| 23 novembre 2007 | Algoritmi Genetici, Programmazione Genetica | [[%ATTACHURL%/6GA.ppt][ppt]]| [[%ATTACHURL%/6GA.pdf][pdf]] | [[%ATTACHURL%/MyFitnessFunction.java][Funzione di fitness per JGap:<br>il valore della f è il valore decimale dell'istanza]]<br>[[%ATTACHURL%/Example.java][Semplice esempio di AG con JGap]] |
| 27 novembre 2007 | Apprendimento non supervisionato | [[%ATTACHURL%/7UL.ppt][ppt]] | [[%ATTACHURL%/7UL.pdf][pdf]] ||
| 4 dicembre 2007 | <b>Presentazione dei progetti</b> | |||
| 7 dicembre 2007 | Apprendimento per Rinforzo | [[%ATTACHURL%/8AR.ppt][ppt]] | [[%ATTACHURL%/8AR.pdf][pdf]]||
| 11 dicembre 2007 | Support Vector Machines (1) | [[%ATTACHURL%/9SVM.ppt][ppt]] | [[%ATTACHURL%/9SVM.pdf][pdf]]  | |
| 18 dicembre 2007 | Support Vector Machines (2),<br>Metodi di Ensemble (1) | <br>[[%ATTACHURL%/10Ensembles.ppt][ppt]] | <br>[[%ATTACHURL%/10Ensembles.pdf][pdf]] ||
| 21 dicembre 2007 | Metodi di Ensemble (2),<br>Valutazione delle Prestazioni (2) | <br>[[%ATTACHURL%/ValutazionePrestazioni.ppt][ppt]]|||
| 8 gennaio 2008 | Esercitazione di preparazione all'esame ||||
| 11 gennaio 2008 | Esercitazione di preparazione all'esame ||||
| 15 gennaio 2008 | <b>Secondo esonero</b>||| <b>Portate una calcolatrice scientifica!</b> |

---++ Programma dettagliato

*Introduzione.* Il problema dell'apprendimento. [[http://en.wikipedia.org/wiki/Statistical_classification][Classificatori]]. Addestramento. Rappresentazione del dominio. Funzione obiettivo e funzione appresa.

*Apprendimento di concetti.* Rappresentazione delle ipotesi, spazio delle ipotesi. Algoritmo FIND-S. [[http://en.wikipedia.org/wiki/Version_space][Algoritmo !VersionSpace]]. Concetto di [[http://en.wikipedia.org/wiki/Inductive_bias][bias]] o inclinazione. Studio delle curve di apprendimento. Sovradattamento, rumore, attributi irrilevanti.

*Alberi di decisione.* Caratteristiche. [[http://en.wikipedia.org/wiki/Occam's_Razor][Principio del rasoio di Occam]]. [[http://en.wikipedia.org/wiki/ID3_algorithm][Algoritmo ID3]], concetto di [[http://it.wikipedia.org/wiki/Entropia_%28teoria_dell%27informazione%29][entropia]], stima dell'entropia di una classificazione, misure di impurità di una classificazione. Scelta dell'attributo migliore: [[http://en.wikipedia.org/wiki/Information_gain_in_decision_trees][guadagno informativo]] e gain ratio. Problemi dell'apprendimento: sovradattamento (reduced error pruning, rule error pruning), valori mancanti. Alberi di decisione con [[http://www.cs.waikato.ac.nz/ml/weka/][Weka]].

*Reti Neurali.* Storia delle reti neurali. [[http://it.wikipedia.org/wiki/Neurone][Neurone]], [[http://it.wikipedia.org/wiki/Rete_neurale][rete neurale]], caratteristiche. [[http://it.wikipedia.org/wiki/Percettrone][Percettrone]], funzione somma e funzione soglia o di attivazione, funzione obiettivo. Funzioni rappresentabili con il percettrone, algoritmo di addestramento del percettrone, convergenza del percettrone. [[http://it.wikipedia.org/wiki/Discesa_del_gradiente][Discesa del gradiente]] (delta rule), discesa del gradiente stocastica. [[http://en.wikipedia.org/wiki/Feedforward_neural_network][Reti stratificate alimentate in avanti]], algoritmo di [[http://en.wikipedia.org/wiki/Backpropagation][Back Propagation]]. Condizioni di terminazione, convergenza, momento. !MultilayerPerceptron con [[http://www.cs.waikato.ac.nz/ml/weka/][Weka]].

*Apprendimento Bayesiano.* Richiami di calcolo delle probabilità: [[http://en.wikipedia.org/wiki/Sample_space][spazio di campionamento]], esiti, eventi, [[http://it.wikipedia.org/wiki/Probabilit%C3%A0][probabilità]], [[http://it.wikipedia.org/wiki/Probabilit%C3%A0_condizionata][probabilità condizionata]], somma di probabilità, probabilità congiunte, proprietà fondamentali, [[http://it.wikipedia.org/wiki/Teorema_di_Bayes][teorema di Bayes]], [[http://it.wikipedia.org/wiki/Variabile_casuale][variabili aleatorie]] discrete e continue, [[http://it.wikipedia.org/wiki/Funzione_di_probabilit%C3%A0][massa di probabilità]], [[http://it.wikipedia.org/wiki/Funzione_di_densit%C3%A0_di_probabilit%C3%A0][densità di probabilità]], distribuzione di probabilità, [[http://en.wikipedia.org/wiki/Expected_value][valore atteso]], [[http://it.wikipedia.org/wiki/Varianza][varianza]], [[http://it.wikipedia.org/wiki/Deviazione_standard][scarto quadratico]], [[http://en.wikipedia.org/wiki/Normal_distribution][distribuzione gaussiana]]. Teorema di Bayes nell'Apprendimento Automatico, MAP (Maximum A Posteriori) learning, MAP learning per l'apprendimento di concetti, Maximum Likelihood Learning, [[http://www.speech.sri.com/people/anand/771/html/node9.html][Optimal Bayes]], [[http://en.wikipedia.org/wiki/Naive_Bayes_classifier][Naive Bayes]]. Naive Bayes con [[http://www.cs.waikato.ac.nz/ml/weka/][Weka]].

*Algoritmi Genetici.* [[http://en.wikipedia.org/wiki/Genetic_algorithm][AG]]: Motivazioni. Algoritmo tipo. Rappresentazione delle ipotesi. [[http://en.wikipedia.org/wiki/Genetic_algorithm][Operatori per gli algoritmi genetici]]. Selezione delle ipotesi migliori. GABIL. Il problema del crowding e possibili soluzioni. [[http://en.wikipedia.org/wiki/Genetic_programming][Programmazione genetica]]. Passi preparatori per la PG. Il problema dei blocchi. Algoritmi genetici con [[http://jgap.sourceforge.net][JGap]].

*Apprendimento Non Supervisionato.* [[http://en.wikipedia.org/wiki/Unsupervised_learning][Unsupervised Learning]]: Motivazioni. Tecniche di [[http://en.wikipedia.org/wiki/Cluster_analysis][clustering]]: clustering gerarchico e clustering partitivo. [[http://www.resample.com/xlminer/help/HClst/HClst_intro.htm][Clustering gerarchico agglomerativo e divisivo]]. Clustering partitivo: [[http://en.wikipedia.org/wiki/K-means_algorithm][k-means]], metriche di distanza, scelta dei semi per k-means. Hard e soft clustering. [[http://www.know-center.tugraz.at/forschung/wissenserschliessung/downloads_demos/fuzzy_k_means_and_k_means_clustering_demo][Fuzzy k-means]]. Problemi nell'apprendimento non supervisionato.

*Apprendimento per Rinforzo.* [[http://en.wikipedia.org/wiki/Reinforcement_learning][Apprendimento per Rinforzo]]: Motivazioni. Definizione del modello. Obiettivi. Varianti. [[http://en.wikipedia.org/wiki/Q-learning][Q-Learning]]: algoritmo, condizioni di convergenza, scelta delle azioni future. Q-Learning per il caso non deterministico.

*Support Vector Machine.* [[http://en.wikipedia.org/wiki/Support_vector_machine][Macchine a vettori di supporto]]. Margine di classificazione. Vettori di supporto. SVM lineare. [[http://en.wikipedia.org/wiki/Lagrange_multipliers][Moltiplicatori Lagrangiani]]: problema primario e problema duale. Soft Margin Classification. SVM non lineare. Funzioni kernel.

*Metodi di Ensemble.* Combinare i classificatori: voting semplice e pesato. Generare i classificatori: [[http://en.wikipedia.org/wiki/Bootstrap_aggregating][Bagging]], [[http://en.wikipedia.org/wiki/Boosting][Boosting]], [[http://en.wikipedia.org/wiki/AdaBoost][AdaBoost]].

*Valutazione delle Prestazioni.* Modalità di test di un classificatore. [[http://en.wikipedia.org/wiki/Confusion_matrix][Matrice di confusione]]. Misure per valutare le prestazioni: [[http://en.wikipedia.org/wiki/Accuracy_and_precision][precisione]], [[http://en.wikipedia.org/wiki/Sensitivity_(tests)][recall]], [[http://en.wikipedia.org/wiki/Sensitivity_(tests)][TP e FP rate]], [[http://en.wikipedia.org/wiki/Accuracy_and_precision][accuratezza]], [[http://en.wikipedia.org/wiki/F1_Score][F1 measure]], scelta delle misure appropriate. [[http://en.wikipedia.org/wiki/Pearson%27s_chi-square_test][Test chi quadrato]] per l'indipendenza statistica, applicazione al confronto tra risultati su campioni e classificatori differenti. 

---++ Testi

Il testo adottato è:

   * Tom Mitchell, [[http://www-2.cs.cmu.edu/~tom/mlbook.html][Machine Learning]], Mc Graw-Hill, 1997, testo aderente a una buona parte del corso, da complementare con il materiale fornito

Per approfondire alcuni argomenti, si consiglia il seguente testo:

   * Ethem Alpaydin, [[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10341][Introduction to Machine Learning]], MIT Press, 2004

cui si aggiungono i lucidi usati dal docente e alcuni articoli di approfondimento.

---++ Progetto

Il progetto per l'A.A. 2007-2008 può essere *scelto da un insieme di 6 proposte del docente* (o *anche proposto dallo studente*, previa accettazione del docente). Informazioni dettagliate sul progetto [[Progetto0708][su questa pagina]].

<!--
Notevole: http://www.cs.iastate.edu/~cs573x/studyguide.html
http://www.cs.utah.edu/classes/cs5350/
http://satirist.org/learn-game/indexes/games.html

GA for chess: http://satirist.org/learn-game/methods/ga/chess.html
Otello: http://satirist.org/learn-game/methods/ga/marker.html
Poker: http://mlearn.ics.uci.edu/databases/poker/
Mastermind: 
Summary: http://mlearn.ics.uci.edu/MLSummary.html
http://ai-depot.com/GameAI/Learning.html
OntologyMapping con NeuralNetworks: http://www.jooneworld.com/docs/documentation.html
Disegnare alberi di decisione con graphviz
Alcuni progetti: http://www.cs.iastate.edu/~cs573x/labs.html

http://www.gameai.com/

Databases: http://mlearn.ics.uci.edu/databases/

Genetic algorithms:
http://cs.felk.cvut.cz/~xobitko/ga/
http://www.aaai.org/AITopics/html/genalg.html
http://www.mcs.drexel.edu/~shartley/geneticAlgorithms.html

Clustering: raggruppamento di parole y "simili" in collocazioni x y  (che si riferiscono allo stesso senso della prima parola x, es. smelling flower, smelling plant, ecc.). Semantic similarity o google counts?

A-life e algoritmi genetici

http://www.idt.mdh.se/kurser/cd5720/rjn/2006lp1/labs/labs.html
-->

---++ Materiale utile

Di seguito trovate materiale utile per lo svolgimento delle esercitazioni e del progetto:

   * *C4.5*: un tool per l'apprendimento di alberi di decisione ([[http://www.cse.unsw.edu.au/~quinlan/c4.5r8.tar.gz][programma C4.5]])
   * *WEKA*:Suite che implementa vari metodi di apprendimento automatico. Il sito [[http://www.cs.waikato.ac.nz/ml/weka/index.html][WEKA]] contiene un ambiente sperimentale Java in cui sono implementati i più noti algoritmi di apprendimento automatico (apprendimento rule-based, apprendimento bayesiano, reti neurali, ecc.). La documentazione di Weka è disponibile [[http://www.cs.waikato.ac.nz/ml/weka/index_documentation.html][cliccando qui]].
   * [[http://grb.mnsu.edu/grbts/doc/manual/J48_Decision_Trees.html][Come utilizzare Weka per apprendere alberi di decisione.]] Contiene anche una discussione dei parametri del classificatore J48
   * *JGap*: una [[http://jgap.sourceforge.net][suite per lo sviluppo di algoritmi genetici]] in Java
   * Dal sito [[http://www.ics.uci.edu/~mlearn/MLSummary.html][Machine Learning Repository Content Summary]] potete scaricare vari data set che si riferiscono a diverse possibili applicazioni di data-mining e classificazione automatica (dati genetici, medici, transazioni commerciali, immagini,...)
   * [[http://www.developer.com/java/other/article.php/10936_1559871_1][L'uso di Java per l'Apprendimento Automatico (in inglese)]]
   * [[http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/genetic/0.html][Repository per algoritmi e programmazione genetica]]
   * [[http://www.fon.hum.uva.nl/Service/Statistics/EqualDistribX2.html][Servizio online per test chi quadro per l'uguaglianza di distribuzioni]] (utilizza il fattore correttivo 0.5)

---++ Per approfondire

   * Un ottimo blog sull'Apprendimento Automatico: [[http://www.hunch.net]]
   * Una [[http://www.faqs.org/faqs/ai-faq/neural-nets/][FAQ sulle Reti Neurali]]
   * [[http://www.cs.iastate.edu/~honavar/Courses/cs673/machine-learning-courses.html][Altri corsi di Apprendimento Automatico]]
   * Un [[http://cs.felk.cvut.cz/~xobitko/ga/][tutorial]] sugli algoritmi genetici
   * Un [[http://www.cs.rutgers.edu/~mlittman/courses/lightai03/jain99data.pdf][articolo survey]] sul clustering
   * Un [[http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a.pdf][articolo survey]] sull'apprendimento per rinforzo

-- Users.RobertoNavigli - 07 Dec 2007
This topic: ApprAuto > WebHome > AnnoAcc0708
Topic revision: r131 - 2008-11-08 - RobertoNavigli