Maschinelles Lernen: Symbolische Ansätze - WS 09/10

Prof. Dr. J. Fürnkranz

Die Veranstaltung im Vorlesungsverzeichnis.

	Tag	Zeit	Raum	Start
Vorlesung	Donnerstag	09:50-11:30	S202/C110	15.10.
Übung	Dienstag	09:50-11:30	S202/C110	20.10.

Ankündigungen

Die Nachprüfung findet am 20.7.2010 statt. Je nachdem wie viele Anmeldungen es gibt wird diese mündlich oder schriftlich sein. Melden Sie sich bitte bis zum 11.7.2010 über das Sekretariat an.

Die Klausureinsicht wird am Freitag, den 26.3.10 von 9:00 - 11:00 Uhr in Raum S202/E302 stattfinden.

Die Klausurnoten hängen nun am schwarzen Brett vor den Räumen des Fachgebiets aus.

Inhalt

Durch die Entwicklung der Informationstechnologie sind immer größere Datenmengen verfügbar. Diese enthalten oft implizites Wissen, das, wenn es bekannt wäre, große wirtschaftliche oder wissenschaftliche Bedeutung hätte. Data Mining ist ein Forschungsgebiet, das sich mit der Suche nach potentiell nützlichem Wissen in großen Datenmengen beschäftigt, und Maschinelles Lernverfahren gehören zu den Schlüsseltechnologien innerhalb dieses Gebiets.

Die Vorlesung bietet eine Einführung in das Gebiet des Maschinellen Lernens unter dem besonderen Aspekt des Data Minings. Es werden Verfahren aus verschiedenen Paradigmen des Maschinellen Lernens mit exemplarischen Anwendungen vorgestellt. Um das Wissen zu operationalisieren, werden in den Übungen prak­tisch­e Erfahrungen mit Lernalgorithmen gesammelt.

• Organisatorisches
• Einführung (Grundbegriffe, Lernprobleme, Konzepte, Beispiele, Repräsentation)
• Regel-Lernen
  • Lernen einzelner Regeln (Generalisierung und Spezialisierung, Strukturierte Hypothesenräume, Version Spaces), last update: 22.10.09
  • Lernen von Regel-Mengen (Covering Strategie, Evaluierungsmaße für Regeln, Pruning, Mehr-Klassenprobleme)
• Evaluierung und kosten-sensitives Lernen (Accuracy,X-Val,ROC-Kurven,Cost-Sensitive Learning)
• Instanzenbasiertes Lernen (last update: 10.12.2009 nach der Vorlesung (3 neue Folien zu kD-Trees))
• Entscheidungsbaum-Lernen (ID3, C4.5, etc.), last update 14.1.10
• Ensemble-Methoden (Bias/Variance, Bagging, Randomization, Boosting, Stacking, ECOCs), last update 20.1.10 
• Pre-Processing (Feature Subset Selection, Diskretisierung, Sampling, Data Cleaning), last update 28.1.10
  
• Clustering und Lernen von Assoziationsregeln

Übungen

In den Übungen erhalten Sie Aufgaben über den Vorlesungsstoff, oft alte Klausur-Aufgaben, die Sie selbst lösen sollen, und die dann in der folgenden Übungsstunde durchbesprochen werden.

1. Übung, 27. 10. 09: Klassifikationsprobleme, (Musterlösung)
   
2. Übung, 03. 11. 09: Hypthesenraum, Generalisierung, (Musterlösung)
   
3. Übung, 10. 11. 09: Version Spaces, (Musterlösung)
4. Übung, 24. 11. 09: Regellernen, (Musterlösung)
   
5. Übung, 26. 11. 09: Regellernen 2, (Musterlösung)
   
6. Übung, 03. 12. 09: Evaluation, (Musterlösung)
   
7. Übung, 08. 12. 09: Instanzenbasiertes Lernen (Update 3.12.09) (Musterlösung)
8. Übung, 15. 12. 09: Instanzenbasiertes Lernen 2 (Update 16.12.09) (Musterlösung, Update 15.2.10)
   
9. Übung, 12. 01. 10: Bäume (Musterlösung)
10. Übung, 19. 01. 10: Bäume 2 (Musterlösung)
11. Übung, 26. 01. 10: Ensembles (Musterlösung)
    
12. Übung, 02. 02. 10: Pre-Processing (Musterlösung)
13. Übung, 09. 02. 10: Assoziationsregeln (Musterlösung)
    

Klausur

Die Klausur findet am 24.2.2010 im Zeitraum von 12:15 - 13:45 Uhr statt.

Erlaubte Unterlagen:
Sie dürfen ein von Ihnen selbst doppelseitig handbeschriebenes Din A4-Blatt zur Klausur mitbringen. Alle anderen Unterlagen, insbesondere Elektronische Hilfsmittel (Taschenrechner, Handy, elektronisches Wörterbuch, etc.) sind nicht erlaubt.

Projekt

Zusätzlich zu den Übungen werden Sie noch praktische Erfahrungen mit der Data Mining Software Weka sammeln. Die Abgabe soll in Form einer Präsentation jeweils einen Tag vor der Besprechung in der Übung (sofern nicht anders angekündigt) an folgende Mailadresse geschickt werden: ml-project09@ke.informatik.tu-darmstadt.de

Aufgaben

• 26. 11. 09: Aufgabe 1 - Update 18.11. (Datum war falsch) (benötigte Datensets - Update 16.11.09)
• 12. 01. 10: Aufgabe 2 (Datensets für Aufg.1, Datensets für Aufg.2, Datensets für Aufg.4)
• Beachten Sie bitte, dass Regressionsbäume und Entscheidungsbäume erst in den beiden folgenden Vorlesungen behandelt werden.
• 09. 02. 10: Aufgabe 3 (Datensets für Aufg. 1, Datensets für Aufg. 2, Datenset für Aufg. 3, Datensets für Aufg. 4)
• Beachten Sie bitte, dass einige Aufgaben erst in späteren Vorlesungen behandelt werden.
• Beachten Sie bitte, dass der Datensatz adult.arff für Aufgabe 3 des Projekts fehlerhaft (kein .arff-file) war. Bitte diesen erneut herunterladen.
  

Forum

Das Diskussionsforum zur Lehrveranstaltung finden Sie hier.

Materialien

Literatur

Die folgenden beiden Lehrbücher behandeln einen Großteil des Stoffes:

• Tom Mitchell, Machine Learning, McGraw Hill 1997.
• Ian H. Witten, Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, 2nd edition 2005. (Die zweite Ausgabe ist um einiges umfangreicher als die erste).

Während die Lehrbücher den Stoff im Großen und Ganzen behandeln, und in vielen Punkten auch noch tiefer gehen, werden in der Vorlesung zum Teil andere Schwerpunkte gesetzt. Als ergänzende Literatur empfehlen wir im Wesentlichen die folgenden Arbeiten (bitte auf Updates achten):

• Einführung
  • Mitchell, ch. 1
  • Witten & Frank, ch. 1
• Regel-Lernen
  • Mitchell, ch.3, ch. 10
  • Witten & Frank, 3.3, 4.4, 6.2
  • Johannes Fürnkranz and Peter Flach. ROC 'n' rule learning -- towards a better understanding of covering algorithms. Machine Learning, 58(1):39-77, 2005.
• Entscheidungsbaum-Lernen
  • Mitchell, ch.3
  • Witten & Frank, 3.2, 4.3, 6.1
  • J. R. Quinlan. Induction of decision trees. Machine Learning, 1:81-106, 1986.
• Inkrementelles Lernen
  • Utgoff, P.E. Incremental induction of decision trees. Machine Learning, 4, 161-186, 1989.
• Naive Bayes
  • Mitchell, 6.1-6.9
  • Witten & Frank, 4.2
• Instance-Based Learning
  • Mitchell, 8.1, 8.2, 8.5, 8.6
  • Witten & Frank, 3.8, 4.7, 6.4
• Evaluation and Cost-Sensitive Learning
  • Witten & Frank, 5.1-5.5, 5.7
  • Tom Fawcett: An Introduction to ROC Analysis, Pattern Recognition Letters 27(8): 861-874 (2006).
  • Peter Flach: The many faces of ROC analysis in machine learning, Tutorial held at ICML-04.
  • Charles Elkan: The Foundations of Cost-Sensitive Learning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), pp. 973-978.
• Association Rules
  • Witten & Frank, 3.4, 4.5
  • Bart Goethals. Survey on Frequent Pattern Mining. Manuscript, 2003.
• Ensemble Methods
  • Thomas G. Dietterich. Ensemble methods in machine learning. In J. Kittler and F. Roli (Ed.) First International Workshop on Multiple Classifier Systems, Lecture Notes in Computer Science (pp. 1-15). New York: Springer Verlag.
  • Boosting animiert

Papers zu vielen Themen finden Sie oft auch mit CiteSeer, DER Suchmaschine für wissenschaftliche Texte der Informatik

Machine-Learning-Werkzeuge

• Weka
• QDA (Qualitative Data Analysis)
• Rapid Miner (formerly YALE - Yet Another Learning Environment)

Beispiel-Datensätze

• Weka stellt auch einige Datensätze bereit
• UCI Machine Learning Repository

Data Mining-Wettbewerbe

• Data Mining-Cup
  • Data Mining-Cup 2008
  • Data Mining-Cup 2007
  • Data Mining-Cup 2006
  • Data Mining-Cup 2005
  • Data Mining-Cup 2004
  • Data Mining-Cup 2003
  • Data Mining-Cup 2002
  • Data Mining-Cup 2001
  • Data Mining-Cup 2000
• KDD-Cup
  • KDD-Cup 2005
  • KDD-Cup 2004
  • KDD-Cup 2003
  • KDD-Cup 2002
  • KDD-Cup 2001
  • KDD-Cup 2000