Machine Learning 101

Was ist Lernen?

Verhaltensänderung eines Agenten in Richtung der Optimierung eines Gütefunktionals (Bewertungsfunktion) durch Erfahrung.

Warum Lernen?

• Nicht alle Situationen vorhersehbar
• Nicht alle Details modellierbar
• Lösung oder Lösungsweg unbekannt, nicht explizit programmierbar
• Data Mining: Entdeckung neuen Wissens durch Analyse der Daten
• Selbstanpassende Programme

=> Lernen wichtige Eigenschaft lebender Wesen :-)

Learning Agent

Feedback während des Lernens

• Überwachtes Lernen

  • Lernen durch Beobachtung
  • Vorgabe von Beispielen: Ein- und Ausgabewerte

  => Regression, Klassifikation

• Unüberwachtes Lernen

  • Erkennen von Mustern in den Inputdaten, Clustering
  • Kein Feedback (!)

• Reinforcement Lernen

  • Bewertung der Aktionen des Agenten am Ende einer Aktionsfolge

Beispiel Kleinkind: Lernen von Klassen/Konzepten durch Beispiele

• Zuerst ist alles "Katze" (Übergeneralisierung)
• Differenzierung durch Feedback der Umwelt; Erkennung unterschiedlicher Ausprägungen

Beispiel: Kreditrisiko

• Bankkunde beantragt Kredit

• Soll er aus Sicht der Bank den Kredit bekommen?

• Bankangestellter betrachtet (relevante) Merkmale des Kunden:

  • Alter, Einkommen, sozialer Status
  • Kundenhistorie bei der Bank
  • Höhe des Kredits

• Bewertung des Kreditrisikos:

  • Klassifikation: Guter oder schlechter Kunde (Binäre Entscheidung: 2 Klassen)
  • Regression: Vorhersage Gewinn/Verlust für die Bank (Höhe des Gewinns/Verlusts interessant)

Beispiel: Autoreparatur

• Gegeben: Eigenschaften eines Autos

  => Eigenschaften: Ausprägungen der Merkmale

• Gesucht: Diagnose und Reparaturanleitung

  => Hypothese über den Merkmalen (Funktion $\operatorname{h}$)

Lernen durch Beobachten: Lernen einer Funktion $\operatorname{f}$

Funktionsapproximation: Lernen einer Funktion $\operatorname{f}$ anhand von Beispielen

• Ein Beispiel ist ein Tupel $(\mathbf{x}, \operatorname{f}(\mathbf{x}))$, etwa $$ (\mathbf{x}, \operatorname{f}(\mathbf{x})) = \left(\begin{array}{ccc} O & O & X \\ . & X & . \\ X & . & . \end{array}, +1\right) $$

• Aufgabe: Baue Hypothese $\operatorname{h}$ auf, so dass $\operatorname{h} \approx \operatorname{f}$.

  • Benutze dazu Menge von Beispielen => Trainingsdaten.

• Ziele:

  1. Konsistente Hypothese: Übereinstimmung bei Trainingsdaten
  2. Generalisierende Hypothese: Korrekte Vorhersage bei unbekannten Daten

Anmerkung: Stark vereinfachtes Modell realen Lernens!

Konstruieren einer konsistenten Hypothese

Welcher Zusammenhang ist hier dargestellt? Offenbar eine Art Funktionsverlauf ... Wir haben für einige x-Werte die zugehörigen y-Werte vorgegeben.

Konstruieren einer konsistenten Hypothese (cnt.)

Die einfachste Approximation wäre eine lineare Funktion. Allerdings werden hierbei einige Werte mehr oder weniger stark nicht korrekt widergegeben, d.h. man hat einen relativ hohen (Trainings-) Fehler.

Konstruieren einer konsistenten Hypothese (cnt.)

Die Hyperbel erklärt die Trainingsdaten bis auf den einen Punkt sehr gut. Die Frage ist, ob dieser eine Punkt zum zu lernenden Zusammenhang gehört oder ein Ausreißer ist, den man gefahrlos ignorieren kann?

Konstruieren einer konsistenten Hypothese (cnt.)

Die grüne Hypothese ist von allen bisher gezeigten die komplexeste, erklärt aber alle Datenpunkte. D.h. hier wäre der Trainingsfehler Null. Zwischen den Trainingsdaten zeigt das Modell eine "glatte" Approximation, d.h. es wird auch neue Daten, die es beim Training nicht gesehen hat, relativ gut erklären. (Dabei liegt freilich die Annahme zugrunde, dass alle relevanten Daten in der Trainingsmenge vorhanden sind, d.h. dass es insbesondere zwischen den Datenpunkten keine Ausreißer o.ä. gibt.)

Konstruieren einer konsistenten Hypothese (cnt.)

Diese Hypothese erklärt ebenfalls sämtliche Trainingsdaten. Allerdings schwingt die Funktion zwischen den Daten stark hin und her. Vermutlich entspricht dies nicht dem zu lernenden Funktionsverlauf. Der Trainingsfehler wäre wie bei der deutlich einfacheren Hypthese aus dem letzten Schritt Null. Der Generalisierungsfehler (sprich die Abweichung, wenn man das Modell nach Daten zwischen den Trainingspunkten fragt) dürfte erheblich höher liegen.

D.h. hier hat das Modell einfach die Trainingsdaten auswendig gelernt, aber nicht den Zusammenhang zwischen den Daten! Dies ist in der Regel unerwünscht!

Occam's Razor

Bevorzuge die einfachste konsistente Hypothese!

1. Wenn es mehrere mögliche Erklärungen für einen Sachverhalt gibt, ist die einfachste Erklärung allen anderen vorzuziehen.
2. Eine Erklärung ist "einfach", wenn sie möglichst wenige Variablen und Annahmen enthält und wenn diese in klaren logischen Beziehungen zueinander stehen, aus denen der zu erklärende Sachverhalt logisch folgt.

Trainingsdaten und Merkmalsvektoren

Lehrer gibt Beispiele vor: Eingabe $\mathbf{x}$ und passende Ausgabe $\operatorname{f}(\mathbf{x})$

• Ausgabe: typischerweise Skalar (Funktionswert oder Klasse) => Beispiel: Bewertung eines Spielstandes bei TicTacToe

• Eingabe: (Beschreibung des) Objekt(s) oder Situation, die zur Ausgabe gehört => Beispiel: Spielstand bei TicTacToe

Merkmalsvektoren:

• Zusammenfassen der relevanten Merkmale zu Vektoren

Beispiel: Schwimmen im See

Beschreibung der Faktoren, wann ich im See schwimmen möchte:

1. Scheint die Sonne?
2. Wie warm ist das Wasser?
3. Wie warm ist die Luft?

• Trainingsbeispiel:
  • Eingabe: Merkmalsvektor (sonnig, warm, warm)
  • Ausgabe: Klasse ja

Dabei wird davon ausgegangen, dass jeder Faktor (jedes Merkmal) an einer bestimmten Stelle im Merkmalsvektor aufgeführt ist. Beispielsweise gehört das sonnig zur Frage "Scheint die Sonne", warm jeweils zur Wasser- und zur Lufttemperatur.

Damit hat man in einem Vektor eine Situation komplett beschrieben, d.h. einen Zustand der Welt mit den relevanten Dingen beschrieben. Diesem Zustand kann man beispielsweise ein Label (Klasse) verpassen, hier in diesem Fall "ja, in dieser Welt möchte ich schwimmen".

Die Trainingsmenge baut sich dann beim überwachten Lernen aus vielen solcher Paare (Merkmalsvektor, Klasse) auf, und die Algorithmen sollen diese Zuordnung lernen, d.h. ein Modell für diese Daten erzeugen, welches die Daten gut erklärt und darüber hinaus für neue Daten aus der selben Datenquelle gute Vorhersagen macht.

Trainingsdaten -- Merkmalsvektoren

Generell: Merkmalsvektor für Objekt $v$: $$ \mathbf{x}(v) = (x_1, x_2, \ldots, x_n) $$

• $n$ Merkmale (Attribute)
• Attribut $x_t$ hat $m_t$ mögliche Ausprägungen
• Ausprägung von $v$ bzgl. $x_t$: $\quad x_t(v) = i \quad$ (mit $i = 1 \ldots m_t$)

Anmerkung: Stellen Sie sich den Merkmalsvektor vielleicht wie einen Konstruktor einer Klasse x vor: Die einzelnen Attribute $x_t$ sind die Parameter, aus denen der Merkmalsvektor aufgebaut ist/wird. Jedes der Attribute hat einen Typ und damit eine bestimmte Anzahl erlaubter Werte ("Ausprägungen") ...

Trainingsbeispiel:

• Tupel aus Merkmalsvektor und zugehöriger Klasse: $\left(\mathbf{x}(v), k\right)$

Wrap-Up

• Lernen ist Verhaltensänderung, Ziel: Optimierung einer Gütefunktion

  • Aufbau einer Hypothese, die beobachtete Daten erklären soll
  • Arten: Überwachtes Lernen, Unüberwachtes Lernen, Reinforcement Lernen

• Merkmalsvektoren gruppieren Eigenschaften des Problems bzw. der Objekte

• Trainingsdaten: Beispielobjekte (durch Merkmalsvektoren beschrieben) plus Vorgabe vom Lehrer

CAL2

Entscheidungsbäume: Klassifikation

• Attribute als Knoten im Baum
• Ausprägungen als Test (Ausgang, Verzweigung)
• Klasse (Funktionswert) als Blatt

Erinnern Sie sich an das Beispiel mit der Auto-Reparatur aus der letzten Sitzung.

Die relevanten Eigenschaften (Merkmale) eines Autos würden als Knoten im Baum repräsentiert. Beispiel: "Motor startet" oder "Farbe".

Jedes Merkmal hat eine Anzahl von möglichen Ausprägungen, diese entsprechen den Verzweigungen am Knoten. Beispiel: "startet", "startet nicht" oder "rot", "weiß", "silber", ... .

Entsprechend kann man durch Abarbeiten des Entscheidungsbaumes am Ende zu einer Diagnose gelangen (Klasse).

Eine andere Sichtweise ist die Nutzung als Checkliste für eine Reparatur ...

Definition Entscheidungsbaum

• Erinnerung: Merkmalsvektor für Objekt $v$: $$ \mathbf{x}(v) = (x_1, x_2, \ldots, x_n) $$

  • $n$ Merkmale (Attribute)
  • Attribut $x_t$ hat $m_t$ mögliche Ausprägungen
  • Ausprägung von $v$ bzgl. $x_t$: $\quad x_t(v) = i \quad$ (mit $i = 1 \ldots m_t$)

• Alphabet für Baum: $$ \lbrace x_t | t=1,\ldots,n \rbrace \cup \lbrace \kappa | \kappa = \ast,A,B,C,\ldots \rbrace \cup \lbrace (,) \rbrace $$

• Entscheidungsbaum $\alpha$: $$ \alpha = \left\lbrace \begin{array}{ll} \kappa & \text{Terminalsymbole: } \kappa = \ast,A,B, \ldots\\ x_t(\alpha_1, \alpha_2, \ldots, \alpha_{m_t}) & x_t \text{ Testattribut mit } m_t \text{ Ausprägungen} \end{array}\right. $$

Anmerkung: Stellen Sie sich die linearisierte Schreibweise wieder wie den (verschachtelten) Aufruf von Konstruktoren vor. Es gibt die Oberklasse Baum, von der für jedes Attribut eine Klasse abgeleitet wird. D.h. der Konstruktor für eine Attributklasse erzeugt letztlich ein Objekt vom Obertyp Baum. Außerdem sind die Terminalsymbole A, B, ... Objekte vom Typ Blatt, welches eine Unterklasse von Baum ist ...

Dabei wird die Anzahl der möglichen Ausprägungen für ein Attribut berücksichtigt: Jede Ausprägung hat einen Parameter im Konstruktor. Damit werden die Unterbäume beim Erzeugen des Knotens übergeben.

Induktion von Entscheidungsbäumen: CAL2

1. Anfangsschritt: $\alpha^{(0)} = \ast$ (totales Unwissen)

2. $n$-ter Lernschritt: Objekt $v$ mit Klasse $k$, Baum $\alpha^{(n-1)}$ gibt $\kappa$ aus

   • $\kappa = \ast$: ersetze $\ast$ durch $k$
   • $\kappa = k$: keine Aktion nötig
   • $\kappa \neq k$: Fehler
     • Ersetze $\kappa$ mit neuem Test: $\kappa \gets x_{t+1}(\ast, \ldots, \ast, k, \ast, \ldots, \ast)$
     • $x_{t+1}$: nächstes Attribut, auf dem aktuellen Pfad noch nicht verwendet
     • Symbol $k$ an Position $i$ wenn $x_{t+1}(v) = i$

$\alpha^{(n)}$ bezeichnet den Baum im $n$-ten Lernschritt.

CAL2 ist ein Meta-Algorithmus: Es ist ein Algorithmus, um einen Algorithmus zu lernen :-)

Beispiel mit CAL2

Ergebnis: $x_1(x_2(A, B), x_2(A, B))$

Anmerkung: Denken Sie an die Analogie von oben. $x_1$ kann als Konstruktor einer Klasse x1 betrachtet werden, die eine Unterklasse von Baum ist. Durch den Aufruf des Konstruktors wird als ein Baum erzeugt.

Es gibt in $x_1$ zwei mögliche Ausprägungen, d.h. der Baum hat in diesem Knoten zwei alternative Ausgänge. Diese Unterbäume werden dem Konstruktor von x1 direkt beim Aufruf übergeben (müssen also Referenzen vom Typ Baum sein).

CAL2: Bemerkungen

• Nur für diskrete Merkmale und disjunkte Klassen

• Zyklischer Durchlauf durch Trainingsmenge

• Abbruch:

  • Alle Trainingsobjekte richtig klassifiziert => Kein Fehler in einem kompletten Durchlauf
  • (Differenzierung nötig, aber alle Merkmale verbraucht)
  • (Lernschrittzahl überschritten)

Wrap-Up

• Darstellung der Hypothese als Entscheidungsbaum
• CAL2: diskrete Attribute, disjunkte Klassen

Pruning

Pruning: Bedingt irrelevante Attribute

Baum: $\alpha = x_1(x_2(A, B), x_2(A, B), x_2(A, B))$

$x_1$ ist bedingt irrelevant => Vereinfachung: $\alpha = x_2(A, B)$

Allgemein:

• Sei $\tilde{x}$ Weg zu Nichtendknoten $x_t$
• Baum dort $\alpha/\tilde{x} = x_t(\alpha_1, \ldots, \alpha_{m_t})$
• $x_t$ ist bedingt irrelevant unter der Bedingung $\tilde{x}$, wenn $\alpha_1 = \alpha_2 = \ldots = \alpha_{m_t}$
• Vereinfachung: Ersetze in $\alpha/\tilde{x}$ den Test $x_t$ durch $\alpha_1$

Anmerkung: Der durch das Entfernen von bedingt irrelevanten Attributen entstandene Baum hat exakt die selbe Aussage (Klassifikation) wie der Baum vor dem Pruning.

Anmerkung: $x_1$ im obigen Beispiel ist sogar global irrelevant, da es sich hier um die Wurzel des Baumes handelt. Der Weg $\tilde{x}$ ist in diesem Fall der leere Weg ...

Pruning: Bedingt redundante Attribute

Baum: $\alpha = x_1(\ast, \ast, x_2(A, B))$

$x_1$ ist bedingt redundant => Vereinfachung: $\alpha = x_2(A, B)$

Allgemein:

• Sei $\tilde{x}$ Weg zu Nichtendknoten $x_t$
• Baum dort $\alpha/\tilde{x} = x_t(\ast, \ldots, \ast, \alpha_i, \ast, \ldots, \ast)$ (mit $\alpha_i \neq \ast$)
• $x_t$ ist bedingt redundant unter der Bedingung $\tilde{x}$
• Vereinfachung: Ersetze in $\alpha/\tilde{x}$ den Test $x_t$ durch $\alpha_i$

Anmerkung: Der durch das Entfernen von bedingt redundanten Attributen entstandene Baum hat eine etwas andere Klassifikation als der Baum vor dem Pruning. Wo vorher ein * ausgegeben wurde, wird nach dem Pruning u.U. ein Klassensymbol ausgegeben. Der Klassifikationsfehler erhöht sich aber nicht, da hier ein * wie ein falsches Klassensymbol zu werten ist.

Anmerkung: $x_1$ im obigen Beispiel ist sogar global redundant, da es sich hier um die Wurzel des Baumes handelt. Der Weg $\tilde{x}$ ist in diesem Fall der leere Weg ...

Allgemeine Transformationsregel

Wrap-Up

• Pruning: Entfernen bedingt redundanter und irrelevanter Tests
• Transformationsregel zum Umbauen von Entscheidungsbäumen

CAL3

CAL3: Erweiterung von CAL2 für nicht-disjunkte Klassen

1. Anfangsschritt: $\alpha^{(0)} = \ast$ (totales Unwissen)

2. $n$-ter Lernschritt: Objekt $v$ mit Klasse $k$

   • Rückweisung (Endknoten mit $\ast$): Ersetze $\ast$ durch Vereinigungsklasse $/k1/$

   • Endknoten mit Vereinigungsklasse:

     • Zähler für $k$ erhöhen, bzw.
     • $k$ mit Anzahl $1$ in Vereinigungsklasse einfügen

   Falls nun die Summe aller Klassen am Endknoten größer/gleich $S_1$ (Statistikschwelle):

   • Für genau eine Klasse gilt: $P(k | \tilde{x}) \ge S_2$: => Abschluss: Ersetze Vereinigungsklasse durch $k$ (für immer!)

   • Für alle Klassen gilt: $P(k | \tilde{x}) < S_2$: => Differenzierung: Ersetze Vereinigungsklasse durch neuen Test: $\kappa \gets x_{t+1}(\ast, \ldots, \ast, /k1/, \ast, \ldots, \ast)$

     $x_{t+1}$: nächstes Attribut, auf dem aktuellen Pfad $\tilde{x}$ noch nicht verwendet Symbol $k$ mit Anzahl 1 an Position $i$ wenn $x_{t+1}(v) = i$

Beispiel mit CAL3

• $S_1 = 4, S_2 = 0.7$

Ergebnis: $x_1(A, x_2(B, A))$

Trainingsfehler: $1/5 = 0.2 < 1-S_2 = 1-0.7 = 0.3$

Hinweis: Bei nicht überlappenden Klassen erzeugt CAL3 u.U. andere Bäume als CAL2 ...

CAL3: Abbruchbedingungen und Parameter

• Parameter:

  • $S_1$: Statistikschwelle, problemabhängig wählen
  • $S_2$: $0.5 < S_2 \le 1.0$
  • Klassifikationsfehler kleiner als $1-S_2$
    • kleiner Fehler => großer Baum
    • großer Fehler => kleiner Baum

• Abbruch:

  • Alle Trainingsobjekte richtig klassifiziert => Kein Fehler in einem kompletten Durchlauf
  • Alle Endknoten mit eindeutigen Klassensymbolen belegt
  • Differenzierung nötig, aber alle Merkmale verbraucht
  • Lernschrittzahl überschritten

Wrap-Up

• CAL3: Erweiterung von CAL2 für überlappende Klassen
  • Parameter $S_1$ (Anzahl Objekte bis Entscheidung), $S_2$ (Dominanz?)
  • Trainingsfehler wg. überlappender Klassen!

Entropie

Wie Attribute wählen?

Erinnerung: CAL2/CAL3

• Zyklische Iteration durch die Trainingsmenge
• Ausschließlich aktuelles Objekt betrachtet
• Reihenfolge der "richtigen" Attributwahl bei Verzweigung unklar

=> Betrachte stattdessen die komplette Trainingsmenge!

Relevanz => Informationsgehalt

• Shannon/Weaver (1949): Entropie
  • Maß für die Unsicherheit einer Zufallsvariablen
  • Anzahl der Bits zur Darstellung der Ergebnisse eines Zufallsexperiments

Beispiele

• Münze, die immer auf dem Rand landet: keine Unsicherheit, 0 Bit
• Faire Münze: Kopf oder Zahl: Entropie 1 Bit
• Fairer 4-seitiger Würfel: 4 mögliche Ausgänge: Entropie 2 Bit
• Münze, die zu 99% auf einer Seite landet: Entropie nahe Null

=> Anzahl der Ja/Nein-Fragen, um zur gleichen Information zu kommen

Definition der Entropie $H(V)$ für Zufallsvariable $V$

• Zufallsvariable $V$ => mögliche Werte $v_k$
• Wahrscheinlichkeit für $v_k$ sei $p_k = P(v_k)$

• Nur eine Klasse: $\log_2 1 = 0$ => $H(V) = 0$ Bit
• Zwei Klassen, gleichwahrscheinlich: $\log_2 0.5 = -1$ => $H(V) = 1$ Bit

Beispiele Entropie: faire Münze

Beispiele Entropie: unfaire Münze

Beispiele Entropie: 4-seitiger Würfel

Entropie der Trainingsmenge: Häufigkeit der Klassen zählen

Mittlere Entropie nach Betrachtung von Attribut $A$

• Auswahl von Attribut $A$ partitioniert die Trainingsmenge: Je Ausprägung $v$ von $A$ erhält man eine Submenge $S_v$

• $R(S, A)$ berechnet die mittlere Entropie der Trainingsmenge, nachdem Attribut $A$ ausgewählt wurde: Unsicherheit/nötige Bits nach Auswahl von Attribut $A$

Entropie der Trainingsmenge nach Attributwahl

Ausblick: Gini Impurity

Wir haben hier die Entropie als Maß für den Informationsgehalt einer Trainingsmenge genutzt. $R(S,A)$ als die mittlere Entropie nach Betrachtung von Attribut $A$ wird von typischen Entscheidungsbaumverfahren wie ID3 und C4.5 genutzt, um bei einer Verzweigung das nächste möglichst aussagekräftige Merkmal auszuwählen.

In anderen Entscheidungsbaumlernern wird stattdessen die Gini Impurity zur Bestimmung des Informationsgehalts eingesetzt (u.a. CART). Dieses Maß sagt aus, wie oft man ein zufällig gezogenes Element des Datensatzes falsch klassifizieren würde, wenn man es mit einer zufälligen Klasse basierend auf der Verteilung der Klassen im Datensatz labeln würde.

Hierzu drei lesenswerte Blog-Einträge:

• Deep dive into the basics of Gini Impurity in Decision Trees with math Intuition
• Decision Trees, Explained
• Decision Tree Algorithm With Hands-On Example

Wrap-Up

• Begriff und Berechnung der Entropie: Maß für die Unsicherheit
• Begriff und Berechnung des Informationsgewinns
  • Entropie für eine Trainingsmenge
  • Mittlere Entropie nach Wahl eines Attributs

ID3 und C4.5

Wie Attribute wählen?

Erinnerung: CAL2/CAL3

• Zyklische Iteration durch die Trainingsmenge
• Ausschließlich aktuelles Objekt betrachtet
• Reihenfolge der "richtigen" Attributwahl bei Verzweigung unklar

=> Betrachte stattdessen die komplette Trainingsmenge!

Erinnerung Entropie: Maß für die Unsicherheit

• Entropie $H(S)$ der Trainingsmenge $S$: relative Häufigkeit der Klassen zählen

• Mittlere Entropie nach Betrachtung von Attribut $A$

  $$ R(S, A) = \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v) $$

• Informationsgewinn durch Betrachtung von Attribut $A$

  $$ \begin{array}{rcl} \operatorname{Gain}(S, A) &=& H(S) - R(S, A)\\[5pt] &=& H(S) - \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v) \end{array} $$

$R(S,A)$ ist die Unsicherheit/nötige Bits nach Auswahl von Attribut A. Je kleiner $R(S,A)$, um so kleiner die verbleibende Unsicherheit bzw. um so kleiner die Anzahl der nötigen Bits zur Darstellung der partitionierten Trainingsmenge nach Betrachtung von Attribut $A$ ...

=> Je kleiner $R(S,A)$, um so größer der Informationsgewinn

Informationsgewinn: Kriterium zur Auswahl von Attributen

1. Informationsgewinn für alle Attribute berechnen
2. Nehme Attribut mit größtem Informationsgewinn als nächsten Test

Informationsgewinn für $x_2$ am höchsten => wähle $x_2$ als nächsten Test

Entscheidungsbaumlerner ID3 (Quinlan, 1986)

def ID3(examples, attr, default):
    # Abbruchbedingungen
    if examples.isEmpty():  return default
    if examples.each(class == A):  return A  # all examples have same class
    if attr.isEmpty():  return examples.MajorityValue()

    # Baum mit neuem Test erweitern
    test = MaxInformationGain(examples, attr)
    tree = new DecisionTree(test)
    m = examples.MajorityValue()
    for v_i in test:
        ex_i = examples.select(test == v_i)
        st = ID3(ex_i, attr - test, m)
        tree.addBranch(label=v_i, subtree=st)
    return tree

[Russell2020]: Man erhält aus dem "Learn-Decision-Tree"-Algorithmus [Russell2020, S. 678, Fig. 19.5] den hier vorgestellten ID3-Algorithmus, wenn man die Funktion $\operatorname{Importance}(a, examples)$ als $\operatorname{InformationGain}(examples, attr)$ implementiert/nutzt.

Hinweis: Mit der Zeile if examples.each(class == A): return A soll ausgedrückt werden, dass alle ankommenden Trainingsbeispiele die selbe Klasse haben und dass diese dann als Ergebnis zurückgeliefert wird. Das "A" steht im obigen Algorithmus nur symbolisch für die selbe Klasse! Es kann also auch ein anderes Klassensymbol als "A" sein ...

Beispiel ID3

• $x2$ höchsten Information Gain
• $x2=0$ => Beispiele 1,2 => A
• $x2=1$ => Beispiele 3,4,5,6 => Information Gain berechnen, weiter teilen und verzweigen

Beobachtung: $\operatorname{Gain}$ ist bei mehrwertigen Attributen höher

• Faire Münze:

  • Entropie = $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \operatorname{Bit}$

• 4-seitiger Würfel:

  • Entropie = $H(\operatorname{Dice}) = -4\cdot(0.25 \log_2 0.25) = 2 \operatorname{Bit}$

=> $\operatorname{Gain}$ ist bei mehrwertigen Attributen höher

Damit würden Attribute bei der Wahl bevorzugt, nur weil sie mehr Ausprägungen haben als andere.

Anmerkung: Im obigen Beispiel wurde einfach die Entropie für zwei "Attribute" mit unterschiedlich vielen Ausprägungen betrachtet, das ist natürlich kein $\operatorname{Gain}(S, A)$. Aber es sollte deutlich machen, dass Merkmale mit mehr Ausprägungen bei der Berechnung des Gain für eine Trainingsmenge einfach wegen der größeren Anzahl an Ausprägungen rechnerisch bevorzugt würden.

C4.5 als Verbesserung zu ID3

Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A)$

C4.5 kann zusätzlich u.a. auch noch mit kontinuierlichen Attributen umgehen, vgl. en.wikipedia.org/wiki/C4.5_algorithm.

In einem Paper (DOI 10.1007/s10115-007-0114-2) wurde der Algorithmus zu den "Top 10 algorithms in data mining" ausgewählt.

Im Wikipedia-Artikel Information Gain finden Sie weitere Informationen zum "Informationsgewinn" (Information Gain).

Ein anderer, relativ ähnlich arbeitender Entscheidungsbaumlerner ist der CART (Classification And Regression Tree)-Algorithmus, wobei der Begriff "CART" allerdings oft auch einfach allgemein für "Entscheidungsbaumlerner" genutzt wird.

Hierzu drei lesenswerte Blog-Einträge:

• Deep dive into the basics of Gini Impurity in Decision Trees with math Intuition
• Decision Trees, Explained
• Decision Tree Algorithm With Hands-On Example

Beispiele zur Normierung bei C4.5

• Faire Münze:

  • Entropie = $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \operatorname{Bit}$
  • Normierung: $1/(0.5 \log_2 (1/0.5) + 0.5 \log_2 (1/0.5)) = 1/(0.5 \cdot 1 + 0.5 \cdot 1) = 1$
  • Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A) = 1 \operatorname{Bit} \cdot 1 = 1 \operatorname{Bit}$

• 4-seitiger Würfel:

  • Entropie = $H(\operatorname{Dice}) = -4\cdot(0.25 \log_2 0.25) = 2 \operatorname{Bit}$
  • Normierung: $1/(4\cdot 0.25 \log_2 (1/0.25)) = 1/(4\cdot 0.25 \cdot 2) = 0.5$
  • Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A) = 2 \operatorname{Bit} \cdot 0.5 = 1 \operatorname{Bit}$

=> Normierung sorgt für fairen Vergleich der Attribute

Anmerkung: Auch hier ist die Entropie natürlich kein $\operatorname{Gain}(S, A)$. Das Beispiel soll nur übersichtlich deutlich machen, dass der "Vorteil" von Attributen mit mehr Ausprägungen durch die Normierung in C4.5 aufgehoben wird.

Wrap-Up

• Entscheidungsbaumlerner ID3
  • Nutze Information Gain zur Auswahl des nächsten Attributs
  • Teile die Trainingsmenge entsprechend auf ("nach unten hin")
• Verbesserung durch Normierung des Information Gain: C4.5