Folien zu “Data Mining”von

I. H. Witten und E. Frank

übersetzt von N. Fuhr

2

Zuverlässigkeit:Evaluierung des Gelernten

Aspekte: Training, Testen, Tuning Vorhersage der Qualität: Vertrauensintervalle Holdout, Kreuzvalidierung, Bootstrap Vergleich von Verfahren: der t-Test Schätzung von Wahrscheinlichkeiten:

Kostenfunktionen Kosten-basierte Maße Evaluierung nummerischer Vorhersagen Das Prinzip der minimalen Beschreibungslänge

5

3

Evaluierung: der Schlüssel zum Erfolg

Wie gut sind die Vorhersagen des Gelernten? Fehler in den Trainingsdaten ist kein guter

Indikator für die Qualität bei neuen Daten Sonst wäre 1-NN der optimale Klassifikator!

Einfache Lösung, wenn ausreichend viele Lerndaten (mit Klassenzugehörigkeit) verfügbar: Aufteilung der Daten in Trainings- und Testmenge

Aber: meist nur begrenzte Lerndatenmenge verfügbar Ausgefeiltere Techniken müssen angewendet werden

4

Aspekte der Evaluierung

Statistische Zuverlässigkeit von beobachteten Qualitätsunterschieden (→ Signifikanztests)

Wahl des Qualitätsmaßes: Anzahl korrekter Klassifikationen Genauigkeit der

Wahrscheinlichkeitsschätzungen Fehler in nummerischen Vorhersagen

Kosten für verschiedene Arten von Fehlern Für viele praktische Anwendungen sind die

Kosten relevant

5

Training und Testen I Naheliegendes Qualitätsmaß für

Klassifikationsprobleme: Fehlerrate Erfolg: Die Klasse einer Instanz wird korrekt

vorhergesagt Fehler: Die Klasse wird falsch vorhergesagt Fehlerrate: Anteil der Fehler an den

Entscheidungen für eine Menge von Instanzen

Resubstitutions-Fehler: Fehlerrate auf den Trainingsdaten

Resubstitutions-Fehler ist extrem optimistisch!

6

Training und Testen II Testmenge: unabhängige Instanzen, die nicht

zum Erlernen des Klassifikators benutzt wurden Annahme: Sowohl Trainings- als auch Testmenge

sind repräsentative Stichproben für das zugrundeliegende Problem

Test- und Trainingsmenge können sich grundsätzlich unterscheiden Beispiel: Klassifikator, der mit Kundendaten von

zwei verschiedenen Städten A und B entwickelt wurde Um die Qualität eines Klassifikators aus A für eine neue

Stadt zu schätzen, teste ihn mit Daten aus B

7

Anmerkung zum Parameter-Tuning

Die Testdaten dürfen in keiner Weise zum Lernen des Klassifikators benutzt werden!

Einige Lernverfahren arbeiten mit 2 Stufen: Stufe 1: Aufbau der grundlegenden Struktur Stufe 2: Optimierung der Parameter

Die Testdaten dürfen nicht zum Parameter-Tuning benutzt werden!

Ordentliches Vorgehen arbeitet mit drei Mengen: Trainingsdaten, Validierungsdaten, Testdaten Validierungsdaten werden zur Parameteroptimierung

benutzt

8

Optimale Ausnutzung der Daten

Nach der Evaluierung können alle Daten zum Lernen des endgültigen Klassifikators benutzt werden

Allgemein: je mehr Trainingsdaten, desto besser der Klassifikator (aber der Qualitätszuwachs nimmt ab)

Je umfangreicher die Testdaten, desto genauer die Schätzung der Fehlerrate

Holdout-Prozedur: Methode zum Aufteilen der Originaldaten in Lern- und TestdatenDilemma: idealerweise sollten sowohl Trainings- als

auch Testmenge möglichst groß sein!

9

Vorhersage der Qualität

Angenommen, die Fehlerrate beträgt 25%. Wie nahe ist dieser Wert an der wahren Fehlerrate? Hängt von der Größe der Testmenge ab

Vorhersage ist wie der Wurf einer (unfairen!) Münze “Kopf” ist ein “Erfolg”, “Zahl” ist ein “Fehler”

In der Statistik wird eine Folge solcher unabhängiger Ereignisse als Bernoulli-Prozess bezeichnet Statistik-Theorie liefert Vertrauensintervalle für den

wahren zugrundeliegenden Fehleranteil

10

Vertrauensintervalle Man kann sagen: p liegt innerhalb eines

bestimmten Intervalls mit einer gewissen vorgegebenen Konfidenz

Beispiel: S=750 Erfolge bei N=1000 Versuchen Geschätzte Erfolgsquote: 75% Wie nahe ist dies an der wahren

Erfolgswahrscheinlichkeit p? Antwort: mit 80%iger Wahrscheinlichkeit ist p∈[73.2,76.7]

Anderes Beispiel: S=75 und N=100 Geschätzte Erfolgsquote: 75% Mit 80%iger Konfidenz p∈[69.1,80.1]

11

Mittelwert und Varianz Mittelwert und Varianz für einen Bernoulli-Prozess:

p, p(1–p) Erwartete Erfolgsquote f=S/N Mittelwert und Varianz für f : p, p(1–p)/N Für ausreichend große N folgt f einer

Normalverteilung c%-Vertrauensintervall [–z ≤ X ≤ z] für

Zufallsvariable mit Mittelwert 0:Pr[–z ≤ X ≤ z]=c

Mit einer symmetrischen Verteilung:Pr[–z ≤ X ≤ z]=1-2*Pr[X ≥ z]

12

Vertrauensintervalle Vertrauensintervalle für die Normalverteilung mit

Mittelwert 0 und Varianz 1:

Also gilt z.B.:

Pr[–1.65 ≤ X ≤ 1.65]=90% Um diese Beziehung anzuwenden, müssen wir die

Zufallsvariable f so transformieren, dass sie Mittelwert 0 und Varianz 1 hat

0.2540%

0.8420%

1.2810%

1.655%

2.33

2.58

3.09

z

1%

0.5%

0.1%

Pr[X ≥ z]

–1 0 1 1.65

13

Transformation von f• Transformierter Wert von f :

(d.h. subtrahiere den Mittelwert und dividiere durch die Standardabweichung)

• Resultierende Gleichung:

• Auflösen nach p :

f −p

p 1−p / N

Pr [−z≤f −p

p1−p /N≤z ]=c

p= f z2

2N±z f

N−

f 2

N

z2

4N2 /1z2

N

14

Beispiele• f = 75%, N = 1000, c = 80% (so dass z = 1.28):

• f = 75%, N = 100, c = 80% (so dass z = 1.28):

• Anm.: Die Annahme einer Normalverteilung gilt nur für große N (d.h. N > 100)

• f = 75%, N = 10, c = 80% (so dass z = 1.28):

(nur grobe Näherung)

p∈[0.732 ,0.767]

p∈[0.691 ,0.801]

p∈[0.549 ,0.881]

15

Holdout-Schätzung Was tun, wenn nur wenige Lerndaten zur Verfügung

stehen? Die holdout-Methode reserviert eine Teilmenge zum

Testen und nutzt den Rest zum Trainieren Meist: ein Drittel zum Testen, der Rest für das Training

Problem: die Stichproben sind evtl. nicht repräsentativ Beispiel: eine Klasse kommt in den Testdaten nicht vor

Fortgeschrittene Version nutzt Stratifikation Stellt sicher, dass jede Klasse mit annähernd gleicher

relativer Häufigkeit in beiden Teilmengen vorkommt

16

Wiederholte holdout-Methode Holdout-Schätzung kann zuverlässiger gemacht

werden, indem der Prozess mit verschiedenen Teilstichproben wiederholt wird In jeder Iteration wird ein bestimmter Anteil der

Daten zufällig zum Trainieren ausgewählt (evtl. mit Stratifikation)

Die Fehlerquoten der verschiedenen Iterationen werden gemittelt, um eine Gesamt-Fehlerquote zu berechnen

Dies wird repeated holdout-Methode genannt Immer noch nicht optimal: die verschiedenen

Testmengen überlappen sich Können Überlappungen ganz vermieden werden?

17

Kreuzvalidierung

Kreuzvalidierung vermeidet überlappende Testmengen Teile Daten in k Teilmengen gleicher Größe auf Benutze reihum jede Teilmenge zum Testen, den

Rest jeweils zum Trainieren

Wird k-fache Kreuzvalidierung genannt Oft sind die Teilmengen stratifiziert, bevor die

Kreuzvalidierung durchgeführt wird Die Fehlerquoten werden gemittelt, um die

Gesamt-Fehlerrate zu berechnen

18

Mehr zu Kreuzvalidierung Standard-Methode zur Evaluierung: stratifizierte 10-

fache Kreuzvalidierung Warum 10?

Umfangreiche Experimente haben gezeigt, dass dies die beste Wahl ist, um zuverlässige Schätzungen zu bekommen

Ferner gibt es theoretische Begründungen hierzu

Stratifikation reduziert die Varianz der Schätzungen Noch besser: wiederholte stratifizierte

Kreuzvalidierung Z.B.: 10-fache Kreuzvalidierung wird 10-mal wiederholt

und die Ergebnisse gemittelt (reduziert die Varianz)

19

Leave-One-Out Kreuzvalidierung

Leave-One-Out:spezielle Form der Kreuzvalidierung: Anzahl der Durchführungen = Anzahl der

Trainingsinstanzen D.h., für n Trainingsinstanzen wird der

Klassifikator n-mal gelernt

Nutzt die Daten optimal aus Keine zufällige Stichprobenauswahl! Aber: großer Rechenaufwand

(Ausnahmen: NN, Support Vector Machine)

20

Leave-One-Out-KV und Stratifikation

Nachteil von Leave-One-Out-KV: Stratifikation ist nicht möglich Verfahren garantiert eine nicht-stratifizierte

Stichprobe, da die Testmenge nur eine einzige Instanz enthält!

Extrembeispiel: Datenmenge, in der zwei Klassen gleich häufig auftreten Einfacher Lerner sagt jeweils die Mehrheitsklasse

voraus 50% Genauigkeit auf frischen Daten Leave-One-Out-KV würde aber 100% Fehlerquote

liefern

21

Die Bootstrap-MethodeKV zieht Stichproben ohne Ersetzung

Eine Instanz, die einmal ausgewählt wurde, kann nicht nochmals für eine spezielle Trainings- oder Testmenge ausgewählt werden

Bootstrap zieht Stichproben mit Ersetzen, um die Trainingsmenge zu bildenZiehe n-mal mit Ersetzung aus einer Datenmenge

mit n Instanzen, um eine Stichprobe mit n Instanzen zu bilden

Benutze diese Daten als TrainingsmengeDie Instanzen aus der ursprünglichen

Datenmenge, die nicht in der Trainingsmenge vorkommen, werden als Testmenge verwendet

22

Der 0.632-Bootstrap

• Verfahren wird auch 0.632-Bootstrap genannt– Die Wahrscheinlichkeit, dass eine bestimmte Instanz

beim einmaligen Ziehen nicht ausgewählt wird, ist 1–1/n– Daraus ergibt sich die Wahrscheinlichkeit, dass die

Instanz in den Testdaten landet:

– Somit wird die Trainingsmenge ungefähr 63.2% aller Instanzen enthalten

1−1n

n

≈e−1=0.368

23

Schätzung der Fehlerquote beim Bootstrap

Die Fehlerschätzung aus den Testdaten ist sehr pessimistisch Trainiert wurde auf nur ~63% aller Instanzen

Daher wird die Fehlerquote mit dem Resubstitutions-Fehler verrechnet:

Der Resubstitutions-Fehler bekommt ein geringeres Gewicht als der Fehler auf den Testdaten

Der Vorgang wird mehrfach wiederholt und der Mittelwert der Fehlerraten berechnet

err=0.632⋅etest instances0.368⋅etraining instances

24

Mehr zu Bootstrap

Wahrscheinlich die beste Methode, um die Qualität bei sehr kleinen Datenmengen zu schätzen

Allerdings gibt es einige Probleme Betrachte die zufällige Datenmenge von vorhin

Ein perfekter Lerner erzielt 0% Resubstitutionsfehler und ~50% Fehler auf den Testdaten

Bootstrap-Schätzung für diesen Klassifikator:

Tatsächlich erwarteter Fehler: 50%err=0.632⋅500.368⋅0=31.6

25

Vergleich von Data-Mining-Verfahren

Häufige Frage: Welches von zwei Lernverfahren ist besser?

Anm.: Dies ist anwendungsabhängig! Naheliegende Methode: Vergleich der 10fach-

KV-Schätzungen Problem: Varianz in der Schätzung Varianz kann durch wiederholte KV reduziert

werden Aber: Wir wissen immer noch nicht, ob die

Ergebnisse statistisch signifikant sind

26

Signifikanztests

Signifikanztests sagen uns, wie sicher wir sein können, dass ein Unterschied wirklich existiert

Nullhypothese: es gibt keinen “wirklichen” Unterschied

Alternative Hypothese: Es gibt einen UnterschiedEin Signifikanztest misst, wieviel Evidenz es dafür

gibt, die Nullhypothese zu verwerfenBeispiel: Wir benutzen 10fache KVFrage: ist die Differenz bei den Mittelwerten der

zwei 10KV-Schätzer signifikant?

27

Paarweiser t-Test Der Student- oder t-Test sagt aus, ob die

Mittelwerte zweier Stichproben signifikant differieren

Nehme individuelle Stichproben bei der Kreuzvalidierung

Benutzung von paarweisem t-Test, da die einzelnen Stichprobenelemente paarweise auftreten Dieselbe KV wird zweimal angewendet

William GossetBorn: 1876 in Canterbury; Died: 1937 in Beaconsfield, EnglandObtained a post as a chemist in the Guinness brewery in Dublin in 1899. Invented the t-test to handle small samples for quality control in brewing. Wrote under the name "Student".

28

Verteilung der Mittelwerte• x1 x2 … xk und y1 y2 … yk sind die 2k Stichprobenwerte für

k-fache KV• mx und my sind die Mittelwerte• Mit ausreichend vielen Werten ist der Mittelwert der

unabhängigen Stichprobenwerte normalverteilt• Schätzungen für die Varianzen der Mittelwerte sind

σx2/k und σy

2/k • Wenn µx und µy die wahren Mittelwerte sind, dann sind

annähernd normalverteilt mit Mittelwert 0 und Varianz 1

mx−μx

σ x2/k

my−μy

σ y2 /k

29

Die Student-Verteilung

Bei kleinen Stichproben (k < 100) folgt der Mittelwert der Student-Verteilung mit k–1 Freiheitsgraden

Vertrauensintervalle:

0.8820%

1.3810%

1.835%

2.82

3.25

4.30

z

1%

0.5%

0.1%

Pr[X ≥ z]

0.8420%

1.2810%

1.655%

2.33

2.58

3.09

z

1%

0.5%

0.1%

Pr[X ≥ z]

9 Freiheitsgrade Normalverteilung

30

Verteilung der Differenzen

• Sei md = mx – my

• Die Differenzen der Mittelwerte (md) folgen ebenfalls der Student-Verteilung mit k–1 Freiheitsgraden

• Sei σd2 die Varianz der Differenzen

• Die standardisierte Version von md wird t-Statistik genannt:

• Wir benutzen t zur Durchführung des t-Tests

t=md

σd2/k

31

Test-Durchführung

• Lege ein Signifikanzniveau α fest • Wenn die Differenz signifikant ist auf dem α% Niveau,

dann beträgt die Wahrscheinlichkeit, dass tatsächlich ein Unterschied vorliegt (100-α)%

• Dividiere das Signifikanz-Niveau durch zwei, da der Test zweiseitig ist• D.h. Die wahre Differenz ist entweder +ve oder – ve

• Schlage den Wert für z nach, der zu α/2 gehört

• Falls t ≤ –z oder t ≥ z, dann ist der Unterschied signifikant• D.h., die Nullhypothese kann verworfen werden

32

Unabhängige Stichproben• Falls die KV-Schätzungen zu verschiedenen

Randomisierungen gehören, sind sie nicht verbunden, sondern unabhängig

• (oder wir benutzen k -fache KV für ein Verfahren und j -fache KV für das andere)

• Dann müssen wir den t-Test für unabhängige Stichproben mit min(k , j ) – 1 Freiheitsgraden anwenden

• Die t -Statistik wird dann zu:

t=md

σd2/k

t=mx−my

σ x2

k

σ y2

j

33

Interpretation des Ergebnisses

All unsere KV-Schätzer basieren auf der gleichen Datenmenge

Die Stichproben sind nicht unabhängig Besser wäre es, für jeden der k

Schätzwerte eine andere Datenmenge zu benutzen, um die Qualität für andere Datenbestände vorhersagen zu können

Oder: Benutze heuristischen Test, z.B. korrigierten t-Test mit neu gebildeten Stichproben

34

Vorhersage von Wahrscheinlichkeiten

• Bisheriges Qualitätsmaß: Erfolgsquote• Wird auch als 0-1 loss function bezeichnet :

• Die meisten Klassifikatoren liefern Klassen-Wahrscheinlichkeiten

• Bei manchen Anwendungen möchte man die Genauigkeit der Wahrscheinlichkeitsschätzungen messen

• 0-1 loss ist nicht das passende Maß hierfür

∑i

{0 if prediction is correct1 if prediction is incorrect

35

Quadratische Verlustfunktion

• p1 … pk sind die Wahrscheinlichkeitsschätzungen für eine Instanz

• c ist der Klassenindex der aktuellen Instanz• ac=1, sonst a1 … ak = 0

• Quadratischer Fehler ist:

• Wir wollen minimieren:

• Man kann zeigen, dass dies minimal ist wenn jeweils pj = pj*,

der wahren Wahrscheinlichkeit

∑j

p j−a j 2=∑

j≠cp j

21−pc 2

E [∑j

p j−a j 2

]

36

Informationelle Verlustfunktion

Die informationelle Verlustfunktion ist –log(pc),wobei c den Index der aktuellen Klasse bezeichnet

Anzahl der erforderlichen Bits, um die aktuelle Klasse mitzuteilen

Seien p1* … pk

* die wahren Klassenwahrscheinlichkeiten

Dann ist der Erwartungswert der Verlustfunktion:

Rechtfertigung: minimal wenn pj = pj*

Problem: Klassen mit Häufigkeit 0

−p1 log2p1−. ..−pk log2pk

37

Diskussion• Welche Verlustfunktion wählen?

– Beide belohnen gute Schätzungen– Quadratische Verlustfunktion berücksichtigt alle

Schätzungen von Klassenwahrscheinlichkeiten für eine Instanz

– Informationelle Verlustfunktion betrachtet nur die Wahrscheinlichkeitsschätzung für die tatsächliche Klasse

– Quadratischer Verlust ist beschränkt: er kann nicht größer als 2 werden

– Informationeller Verlust kann beliebig groß werden

• Informationeller Verlust ist verwandt mit dem MDL-Prinzip [später]

1∑j

p j2

38

Berücksichtigung der Kosten

Bei praktischen Anwendungen führen verschiedene Arten von Fehlern oft zu unterschiedlichen Kosten

Beispiele: Aufspüren von Terroristen

“Kein Terrorist” korrekt bei 99.99% aller Fälle

Kredit-Entscheidungen Erkennen von Ölflecken Fehlerdiagnosen Werbesendungen Spam-Filter

39

Berücksichtigung der Kosten

Die Fall-Matrix:

Es kann noch weitere Arten von Kosten geben!Z.B.: Kosten zum Sammeln der Trainingsdaten

Actual class

True negativeFalse positiveNo

False negativeTrue positiveYes

NoYes

Predicted class

40

Steigerungsdiagramm In der Praxis sind die Kosten oft unbekannt Entscheidungen werden gefällt, indem

verschiedene mögliche Szenarien verglichen werden

Beispiel: Werbesendung an 1.000.000 Haushalte• Versand an alle: 0.1% antworten (1000)• Data mining Tool identifiziert Teilmenge von 100,000

Aussichtsreichen, 0.4% davon antworten (400)40% der Antworten für 10% der Kosten kann sich lohnen

• Identifiziere Teilmenge von 400,000 Aussichtsreichen, 0.2% davon antworten (800)

Ein Steigerungsdiagramm erlaubt den visuellen Vergleich

41

Generierung eines Steigerungsdiagramms

Sortiere Instanzen nach der geschätzten Erfolgswahrscheinlichkeit :

x-Achse: Stichprobengrößey-Achse: Anzahl Erfolgsfälle

………

Yes0.884

No0.933

Yes0.932

Yes0.951

Actual classPredicted probability

42

Eine hypothetisches Steigerungsdiagramm

40% der Antworten für 10% der Kosten

80% der Antwortenfür 40% der Kosten

43

ROC-Kurven ROC-Kurven sind ähnlich zu

Steigerungsdiagrammen Steht für “receiver operating characteristic” Wird in der Signaltheorie benutzt, um den Tradeoff

zwischen Erfolgsquote und Fehlerrate in einem verrauschten Übertragungskanal darzustellen

Unterschiede zu Steigerungsdiagramm: y-Achse zeigt den Prozentsatz positiver Elemente in

der Stichprobe im Gegensatz zur deren absoluter Anzahl

x –Achse zeigt den Prozentsatz von falschen positiven in der Stichprobeim Gegensatz zur Stichprobengröße

44

Beispiel einer ROC-Kurve

Gezackte Kurve: eine Testdatenmenge Gestrichelte Kurve: Resultat von Kreuzvalidierung

45

Kreuzvalidierung und ROC-Kurven

Einfache Methode zur Erstellung einer ROC-Kurve mittels Kreuzvalidierung: Sammle Wahrscheinlichkeiten für die Instanzen in

den Testmengen Sortiere Instanzen nach Wahrscheinlichkeiten

Methode ist in WEKA implementiert Es gibt aber noch andere Möglichkeiten

Die im Buch beschriebene Methode generiert eine ROC-Kurve für jede Testmenge und mittelt dann

46

ROC-Kurven für zwei Verfahren

Für eine kleine, ausgewählte Menge, benutze Methode A Für größere Mengen, benutze Methode B Dazwischen: wähle zwischen A und B mit geeigneten Wahrscheinlichkeiten

47

Die konvexe Hülle

Für zwei Verfahren kann man jeden Punkt auf der konvexen Hülle errreichen!

TP und FP-Quoten für Verfahren 1: t1 und f1

TP und FP-Quoten für Verfahren 2: t2 und f2

Wenn Methode 1 für 100×q % der Fälle benutzt wird und Methode 2 für den Rest, dann TP-Rate für das kombinierte Verfahren:

q × t1+(1-q) × t2

FP-Rate für das kombinierte Verfahren:q × f2+(1-q) × f2

48

Kosten-sensitives LernenDie meisten Lernverfahren unterstützen kein

Kosten-sensitives LernenSie generieren denselben Klassifikator unabhängig

davon, welche Kosten den einzelnen Klassen zugeordnet werden

Beispiel: Standard-Lerner für EntscheidungsbäumeEinfache Methoden für Kosten-sensitives Lernen:

Resampling der Instanzen entsprechend den Kosten Gewichtung der Instanzen entsprechend den Kosten

Einige Verfahren können Kosten berücksichtigen, indem sie bestimmte Parameter variieren, z.B. naiver Bayes

49

Maße im Information Retrieval

Anteil der gefundenen Dokumente, die relevant sind: Precision=TP/(TP+FP)

Anteil der relevanten Dokumente, die gefunden wurden: Recall =TP/(TP+FN)

Precision/Recall-Kurven sind meist ähnlich zu hyperbolischen Kurven

Globale Maße: Mittelwert der Precision bei 20%, 50% und 80% Recall (three-point average recall)

F-Maß=(2×Recall×Precision)/(Recall+Precision)

50

Zusammenfassung der Maße

ErklärungAchsenDomäne

TP/(TP+FN)TP/(TP+FP)

RecallPrecision

Information retrieval

Recall-Precision- Kurve

TP/(TP+FN)FP/(FP+TN)

TP-QuoteFP-Quote

SignaltheorieROC-Kurve

TP(TP+FP)/(TP+FP+TN+FN)

TP Größe d. Teilm.

MarketingSteigerungsdiagramm

51

Evaluierung nummerischer Vorhersagen

• Gleiche Strategien: unabhängige Testmenge, Kreuzvalidierung, Signifikanztests, usw.

• Unterschied: Fehlermaße• Tatsächliche Werte: a1 a2 …an

• Vorhergesagte Werte: p1 p2 … pn

• Populärstes Maß: mittlerer quadratischer Fehler

– Einfache mathematische Manipulation

p1−a1 2. ..pn−an2

n

52

Andere MaßeDie Wurzel aus dem mittleren quadratischen Fehler

:

Der mittlere absolute Fehler ist weniger sensitiv gegenüber Ausreißern als der mittlere quadratische Fehler:

Manchmal ist der relative Fehler angemessener (z.B. 10% für einen Fehler von 50 beim Vorhersagewert 500)

∣p1−a1∣. ..∣pn−an∣

n

p1−a1 2...pn−an 2

n

53

Verbesserung des Mittelwerts

Wie stark verbessert sich ein Verfahren, wenn es den Mittelwert korrekt vorhersagt?

Der relative quadratische Fehler ist ( ):

Der relative absolute Fehler ist:

p1−a1 2. ..pn−an2

a−a12. ..a−an 2

a ist der Mittelwert

∣p1−a1∣. ..∣pn−an∣

∣a−a1∣...∣a−an∣

54

KorrelationskoeffizientMisst die statistische Korrelation zwischen den

Vorhersagewerten und den tatsächlichen Werten

Skalierungs-unabhängig, zwischen –1 und +1Gute Qualität drückt sich in größeren Werten aus!

SPA

SP SA

SPA=

∑i

pi−p ai−a

n−1SP=

∑i

pi−p 2

n−1SA=

∑i

ai−a 2

n−1

55

Welches Maß verwenden?

Am besten alle betrachten Oft ist es egal Beispiel:

0.910.890.880.88Korrelationskoeffizient

30.4%34.8%40.1%43.1%Relativer absoluter Fehler

35.8%39.4%57.2%42.2%Wurzel d. rel. quadr. Fehlers

29.233.438.541.3Mittlere absoluter Fehler

57.463.391.767.8Wurzel d. quadr. Fehlers

DCBA

D am besten C zweiter A, B hängt vom Standpunkt ab

56

Das MDL-Prinzip

MDL steht für minimum description lengthDie Beschreibungslänge ist definiert als:

Speicherplatz zur Beschreibung einer Theorie+

Speicherplatz zur Beschreibung der Fehler der Theorie

In unserem Fall ist die Theorie der Klassifikator und die Fehler die auf den Trainingsdaten

Gesucht: Klassifikator mit minimaler MDLMDL-Prinzip ist ein Kriterium zur Modellauswahl

57

Modellauswahl-Kriterien Modellauswahl-Kriterien versuchen, einen guten

Kompromiss zu finden zwischen:• Der Komplexität eines Modells• Seiner Vorhersagequalität auf den Trainingsdaten

Idee: Ein gutes Modell ist ein einfaches Modell, das eine hohe Genauigkeit auf den vorhandenen Daten erzielt

Auch bekannt als Occam’s Razor :die beste Theorie ist die kleinste,die alle Fakten beschreibt

William of Ockham, born in the village of Ockham in Surrey (England) about 1285, was the most influential philosopher of the 14th century and a controversial theologian.

58

Eleganz vs. Fehler

Theorie 1: sehr einfache, elegante Theorie die die Daten beinahe perfekt beschreibt

Theorie 2: deutlich komplexere Theorie, die die Daten fehlerfrei reproduziert

Theorie 1 ist zu bevorzugen Klassisches Beispiel: Keplers drei Gesetze zu der

Planetenbewegung Weniger genau als Kopernikus’ letzte Verfeinerung der

Ptolemäischen Theorie der Epizyklen

59

MDL und KomprimierungDas MDL-Prinzip hängt mit der Datenkomprimierung

zusammen:Die beste Theorie ist diejenige, die die Daten am stärksten

komprimiertD.h. um eine Datenmenge zu komprimieren, generieren wir

ein Modell und speichern dann das Modell und seine Fehler

Dazu müssen wir berechnen(a) die Größe des Modells, und(b) den Speicherplatz für die Fehler

(b) einfach: benutze den Informationsverlust(a) erfordert eine Methode zur Codierung des Modells

60

MDL und Bayes’ Theorem

L[T]=“Länge” einer Theorie L[E|T]=Codierung der Trainingsmenge in Bezug auf

die Theorie Beschreibungslänge= L[T] + L[E|T] Bayes’ Theorem schätzt die a-posteriori

Wahrscheinlichkeit einer Theorie bei gegebenen Daten:

Äquivalent zu:

Pr [ T∣E ]=Pr [E∣T ]Pr [T ]

Pr [E ]

−log Pr [T ∣E ]=−log Pr [ E∣T ]−log Pr [T ]log Pr [ E ]

konstant

61

MDL und MAP

MAP steht für maximum a posteriori probability Finden der MAP-Theorie korrespondiert zum Finden der

MDL Theorie Schwierigkeit bei der Anwendung des MAP-Prinzips:

Bestimmung der a-priori-Wahrscheinlichkeit Pr[T] der Theorie

Korrespondiert zum schwierigen Teil bei der Anwendung des MDL-Prinzips: Codierungsschema für die Theorie

D.h. wenn wir vorher wissen, dass eine bestimmte Theorie wahrscheinlicher ist, dann benötigen wir weniger Bits, um sie zu codieren

62

Diskussion des MDL-Prinzips

Vorteil: nutzt die Trainigsdaten voll aus bei der Auswahl eines Modells

Nachteil 1: passendes Codierungsschema/a-priori-Wahrscheinlichkeiten sind entscheidend

Nachteil 2: es gibt keine Garantie, dass die MDL-Theorie den erwarteten Fehler minimiert

Anmerkung: Occam’s Razor ist ein Axiom! Epicurus’ Prinzip der multiplen Erklärungen:

behalte alle Theorien, die konsistent mit den Daten sind

63

Bayes’sche Modell-Mittelung Basiert auf Epicurus’ Prinzip: alle Theorien werden zur

Vorhersage genutzt, entsprechend P[T|E] Sei I eine neue Instanz, deren Klasse vorhergesagt

werden soll Sei C die Zufallsvariable für die Klasse Dann schätzt BMM die Wahrscheinlichkeit von C unter

Berücksichtigung von I den Trainingsdaten E den möglichen Theorien Tj

Pr [ C∣I ,E ]=∑j

Pr [C∣I ,T j ]Pr [T j∣E ]

64

MDL und Clustering Beschreibungslänge einer Theorie:

Benötigte Bits zur Codierung der Cluster z.B. Zentroiden

Beschreibungslänge der Daten bei gegebener Theorie: codiere Clusterzugehörigkeit und relative Position im Cluster z.B. Distanz zum Zentroiden

Funktioniert, wenn das Codierungsschema für kleine Zahlen weniger Bits benötigt als für große

Bei nominalen Attributen müssen die Wahrscheinlichkeitsverteilungen für jedes Cluster codiert werden