Maschinelles Ler­nen: Sym­bol­is­che Ansätze - WS 09/10

Prof.​ Dr.​ J.​ Fürnkranz

Die Ve­r­anstal­tung im Vor­lesungsverze­ich­nis.

	Tag	Zeit	Raum	Start
Vor­lesung	Don­ner­stag	09:50-11:30	S202/C110	15.10.
Übung	Di­en­stag	09:50-11:30	S202/C110	20.10.

Ankündi­gun­gen

Die Nach­prüfung find­et am 20.7.2010 statt.​ Je nach­dem wie viele An­mel­dun­gen es gibt wird diese mündlich oder schriftlich sein.​ Melden Sie sich bitte bis zum 11.7.2010 über das Sekre­tari­at an.

Die Klausurein­sicht wird am Fre­itag, den 26.3.10 von 9:00 - 11:00 Uhr in Raum S202/E302 stat­tfind­en.

Die Klausurnoten hängen nun am schwarzen Brett vor den Räumen des Fachge­bi­ets aus.

In­halt

Durch die En­twick­lung der In­for­ma­tion­stech­nolo­gie sind immer größere Daten­men­gen verfügbar.​ Diese en­thal­ten oft im­plizites Wis­sen, das, wenn es bekan­nt wäre, große wirtschaftliche oder wis­senschaftliche Be­deu­tung hätte.​ Data Min­ing ist ein Forschungs­ge­bi­et, das sich mit der Suche nach po­ten­tiell nützlichem Wis­sen in großen Daten­men­gen beschäftigt, und Maschinelles Lern­ver­fahren gehören zu den Schlüssel­tech­nolo­gien in­ner­halb dieses Ge­bi­ets.

Die Vor­lesung bi­etet eine Einführung in das Ge­bi­et des Maschinellen Ler­nens unter dem beson­deren As­pekt des Data Minings.​ Es wer­den Ver­fahren aus ver­schiede­nen Paradig­men des Maschinellen Ler­nens mit ex­em­plar­ischen An­wen­dun­gen vorgestellt.​ Um das Wis­sen zu op­er­a­tional­isieren, wer­den in den Übun­gen prak­tisch­e Er­fahrun­gen mit Ler­nal­go­rith­men gesam­melt.

• Or­gan­isatorisches
• Einführung (Grund­be­griffe, Lern­prob­leme, Konzepte, Beispiele, Repräsen­ta­tion)
• Regel-Ler­nen
  • Ler­nen einzel­ner Regeln (Gen­er­al­isierung und Spezial­isierung, Struk­turi­erte Hy­pothe­senräume, Ver­sion Spaces), last up­date: 22.10.09
  • Ler­nen von Regel-Men­gen (Cov­er­ing Strate­gie, Evaluierungs­maße für Regeln, Prun­ing, Mehr-Klassen­prob­leme)
• Evaluierung und kosten-sen­si­tives Ler­nen (Ac­cu­ra­cy,X-Val,ROC-Kur­ven,Cost-Sen­si­tive Learn­ing)
• In­stanzen­basiertes Ler­nen (last up­date: 10.12.2009 nach der Vor­lesung (3 neue Folien zu kD-Trees))
• Entschei­dungs­baum-Ler­nen (ID3, C4.5, etc.​),​ last up­date 14.1.10
• En­sem­ble-Meth­o­d­en (Bias/Vari­ance, Bag­ging, Ran­dom­iza­tion, Boost­ing, Stack­ing, ECOCs), last up­date 20.1.10 
• Pre-Pro­cess­ing (Fea­ture Sub­set Se­lec­tion, Diskretisierung, Sam­pling, Data Clean­ing), last up­date 28.1.10
  
• Clus­ter­ing und Ler­nen von As­sozi­a­tion­sregeln

Übun­gen

In den Übun­gen er­hal­ten Sie Auf­gaben über den Vor­lesungsstoff, oft alte Klausur-Auf­gaben, die Sie selb­st lösen sollen, und die dann in der fol­gen­den Übungsstunde durchbe­sprochen wer­den.

1. Übung, 27. 10. 09: Klas­si­fika­tion­sprob­leme, (Musterlösung)
   
2. Übung, 03. 11. 09: Hypthe­sen­raum, Gen­er­al­isierung, (Musterlösung)
   
3. Übung, 10. 11. 09: Ver­sion Spaces, (Musterlösung)
4. Übung, 24. 11. 09: Regeller­nen, (Musterlösung)
   
5. Übung, 26. 11. 09: Regeller­nen 2, (Musterlösung)
   
6. Übung, 03. 12. 09: Eval­u­a­tion, (Musterlösung)
   
7. Übung, 08. 12. 09: In­stanzen­basiertes Ler­nen (Up­date 3.12.09) (Musterlösung)
8. Übung, 15. 12. 09: In­stanzen­basiertes Ler­nen 2 (Up­date 16.12.09) (Musterlösung, Up­date 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: En­sem­bles (Musterlösung)
    
12. Übung, 02. 02. 10: Pre-Pro­cess­ing (Musterlösung)
13. Übung, 09. 02. 10: As­sozi­a­tion­sregeln (Musterlösung)
    

Klausur

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

Er­laubte Un­ter­la­gen:
Sie dürfen ein von Ihnen selb­st dop­pel­seit­ig handbeschriebenes Din A4-Blatt zur Klausur mitbringen.​ Alle an­deren Un­ter­la­gen, ins­beson­dere Elek­tro­n­is­che Hil­f­s­mit­tel (Taschen­rech­n­er, Handy, elek­tro­n­is­ches Wörter­buch, etc.​) sind nicht er­laubt.

Pro­jekt

Zusätzlich zu den Übun­gen wer­den Sie noch prak­tis­che Er­fahrun­gen mit der Data Min­ing Soft­ware Weka sammeln.​ Die Ab­gabe soll in Form einer Präsen­ta­tion jew­eils einen Tag vor der Be­sprechung in der Übung (sofern nicht an­ders angekündigt) an fol­gende Mailadresse geschickt wer­den: ml-project09@​ke.​informatik.​tu-darmstadt.​de

Auf­gaben

• 26. 11. 09: Auf­gabe 1 - Up­date 18.​11.​ (Datum war falsch) (benötigte Datensets - Up­date 16.11.09)
• 12. 01. 10: Auf­gabe 2 (Datensets für Aufg.1, Datensets für Aufg.2, Datensets für Aufg.4)
• Beacht­en Sie bitte, dass Re­gres­sionsbäume und Entschei­dungsbäume erst in den bei­den fol­gen­den Vor­lesun­gen be­han­delt wer­den.
• 09. 02. 10: Auf­gabe 3 (Datensets für Aufg. 1, Datensets für Aufg. 2, Datenset für Aufg. 3, Datensets für Aufg. 4)
• Beacht­en Sie bitte, dass einige Auf­gaben erst in späteren Vor­lesun­gen be­han­delt wer­den.
• Beacht­en Sie bitte, dass der Daten­satz adult.​arff für Auf­gabe 3 des Pro­jek­ts fehler­haft (kein .arff-file) war.​ Bitte diesen erneut herun­ter­laden.
  

Forum

Das Diskus­sions­fo­rum zur Lehrver­anstal­tung find­en Sie hier.

Ma­te­ri­alien

Lit­er­atur

Die fol­gen­den bei­den Lehrbücher be­han­deln einen Großteil des Stoffes:

• Tom Mitchell, Ma­chine Learn­ing, Mc­Graw Hill 1997.​
• Ian H.​ Witten, Eibe Frank, Data Min­ing: Prac­ti­cal Ma­chine Learn­ing Tools and Tech­niques with Java Im­ple­men­ta­tions, Mor­gan Kauf­mann, 2nd edi­tion 2005.​ (Die zweite Aus­gabe ist um einiges um­fan­gre­ich­er als die erste).

Während die Lehrbücher den Stoff im Großen und Ganzen be­han­deln, und in vie­len Punk­ten auch noch tiefer gehen, wer­den in der Vor­lesung zum Teil an­dere Schw­er­punk­te gesetzt.​ Als ergänzende Lit­er­atur empfehlen wir im Wesentlichen die fol­gen­den Ar­beit­en (bitte auf Up­dates acht­en):

• Einführung
  • Mitchell, ch. 1
  • Wit­ten & Frank, ch. 1
• Regel-Ler­nen
  • Mitchell, ch.3, ch. 10
  • Wit­ten & Frank, 3.3, 4.4, 6.2
  • Jo­hannes Fürnkranz and Peter Flach. ROC 'n' rule learn­ing -- to­wards a bet­ter un­der­stand­ing of cov­er­ing al­go­rithms. Ma­chine Learn­ing, 58(1):39-77, 2005.​
• Entschei­dungs­baum-Ler­nen
  • Mitchell, ch.3
  • Wit­ten & Frank, 3.2, 4.3, 6.1
  • J.​ R.​ Quinlan.​ Induc­tion of de­ci­sion trees.​ Machine Learn­ing, 1:81-106, 1986.​
• Inkre­mentelles Ler­nen
  • Ut­goff, P.​E.​ In­cre­men­tal in­duc­tion of de­ci­sion trees. Ma­chine Learn­ing, 4, 161-186, 1989.​
• Naive Bayes
  • Mitchell, 6.1-6.9
  • Wit­ten & Frank, 4.2
• In­stance-Based Learn­ing
  • Mitchell, 8.1, 8.2, 8.5, 8.6
  • Wit­ten & Frank, 3.8, 4.7, 6.4
• Eval­u­a­tion and Cost-Sen­si­tive Learn­ing
  • Wit­ten & Frank, 5.1-5.5, 5.7
  • Tom Fawcett: An In­tro­duc­tion to ROC Anal­y­sis, Pat­tern Recog­ni­tion Let­ters 27(8): 861-874 (2006).
  • Peter Flach: The many faces of ROC anal­y­sis in ma­chine learn­ing, Tu­to­ri­al held at ICML-04.​
  • Charles Elkan: The Foun­da­tions of Cost-Sen­si­tive Learn­ing. In Pro­ceed­ings of the 17th In­ter­na­tion­al Joint Con­fer­ence on Ar­ti­fi­cial In­tel­li­gence (IJ­CAI-01), pp. 973-978.​
• As­so­ci­a­tion Rules
  • Wit­ten & Frank, 3.4, 4.5
  • Bart Goethals. Sur­vey on Fre­quent Pat­tern Min­ing. Manuscript, 2003.​
• En­sem­ble Meth­ods
  • Thomas G.​ Dietterich. En­sem­ble meth­ods in ma­chine learn­ing. In J.​ Kit­tler and F.​ Roli (Ed.​) First In­ter­na­tion­al Work­shop on Mul­ti­ple Clas­si­fi­er Sys­tems, Lec­ture Notes in Com­put­er Sci­ence (pp. 1-15). New York: Springer Verlag.​
  • Boost­ing an­i­miert

Pa­pers zu vie­len The­men find­en Sie oft auch mit Cite­Seer, DER Such­mas­chine für wis­senschaftliche Texte der In­for­matik

Ma­chine-Learn­ing-Werkzeuge

• Weka
• QDA (Qual­i­ta­tive Data Anal­y­sis)
• Rapid Miner (for­mer­ly YALE - Yet An­oth­er Learn­ing En­vi­ron­ment)

Beispiel-Datensätze

• Weka stellt auch einige Datensätze bere­it
• UCI Ma­chine Learn­ing Repos­i­to­ry

Data Min­ing-Wet­tbe­werbe

• Data Min­ing-Cup
  • Data Min­ing-Cup 2008
  • Data Min­ing-Cup 2007
  • Data Min­ing-Cup 2006
  • Data Min­ing-Cup 2005
  • Data Min­ing-Cup 2004
  • Data Min­ing-Cup 2003
  • Data Min­ing-Cup 2002
  • Data Min­ing-Cup 2001
  • Data Min­ing-Cup 2000
• KDD-Cup
  • KDD-Cup 2005
  • KDD-Cup 2004
  • KDD-Cup 2003
  • KDD-Cup 2002
  • KDD-Cup 2001
  • KDD-Cup 2000