Overfitting

Einen Baum zu ‘Lernen’, der Trainingsdaten perfekt klassifiziert, wird nicht unbedingt zu dem Baum führen, der die beste Verallgemeinerung von unbemerkten Daten bietet.
• Es könnte Rauschen in den Trainingsdaten geben, die zu einem falschen Baum führen
• Der Algorithmus macht eventuell schlechte Entscheidungen an den Blättern des Baumes, die nur auf wenigen Daten basieren und so keine verlässlichen Trends zurückgeben-
Ein ‘Overfit’ der Trainingsdaten liegt dann vor, wenn eine Hypothese h gegenüber einer h’ geringere Fehler in den Trainingsdaten hat, aber größere bei unabhängigen Testdaten.
Kategorien oder Eigenschaftsrauschen kann leicht der Grund für ‘Overfitting’ sein Rauschen kann auch begründen, dass verschieden Beispiele des selben Eigenschaftsvektors
verschiedene Klassen haben. Es ist unmöglich diese Daten zu fitten, man muss die Blätter mit der
‚Überklasse‘ beschreiben.
Gegensätzliche Beispiele können auch auftauchen, wenn die Eigenschaften unvollständig oder inadäquat die Klasse zu bestimmen sind, oder wenn das Zielkonzept nicht deterministisch ist.

Overfitting Prevention (Pruning) Methods
• 2 grundlegende Ansätze für Entscheidungsbäume
o Prepruning: Stoppe das Wachsen des Baumes an einem Punkt während der top- down Konstruktion, an dem es keine weitere ausreichende Daten gibt, um verlässliche Entscheidungen zu fällen
o Postpruning: Lass den ganzen Baum wachsen, entferne dann Teilbäume, die keine ausreichenden Belege liefern.
• Beschreibe Blätter, entstanden durch das Kürzen,, mit der ‘Überklasse’ der verbleibenden Daten oder mit einer Klassen-Wahrscheinlichkeits-Verteilung.

• Methode um zu bestimmen welcher Teilbaum gekürzt wird
o Cross-validation: Reserviere etwas Trainingsdaten als hold-out Satz, um die Nützlichkeit der Teilbäume zu evaluieren.
o Statistical test: Signifikanztest auf Trainingsdaten, ob Zusammenhänge zufällig sind
o Minimum description length (MDL): Bestimme, ob weitere Komplexität der Hypothesen weniger komplex ist, als sich nur an Ausnahmen, die sich aus dem Kürzen gegeben haben, zu erinnern.

Reduced Error Pruning
A post-pruning, cross-validation approach:
• Teile die Trainingsdaten in ‘Wachstums’ und ‘Validierungs’ Sätze
• Baue einen kompletten Baum mit Hilfe der ‚Wachstums‘ Daten
• Bis die Genauigkeit des Validierungssatzes sinkt mache für jeden Knoten ohne Blatt n im Baum:
Kürze den Teilbaum unter n vorübergehend und ersetze ihn durch ein Blatt, beschrieben mit der aktuellen ‚Überklasse‘ an diesem Knoten. Miss und tracke die Genauigkeit des gekürzten Baumes mit dem Validierungssatz
Kürze den Knoten, der dauerhaft das größte Genauigkeitswachstum hat.
Probleme:
• Möglich, dass Trainingsdaten im Validierungssatz verschwendet werden.
• Härte des Problems ist abhängig davon, wo man sich auf der Lernkurve befindet
Cross-Validating without Losing Training Data
• Wenn der Algorithmus modifiziert ist, um den Baum zuerst in der Breite, dann in der Tiefe wachsen zu lassen, können wir das Wachsen nach einer spezifischen Baum-Komplexität stoppen.
• Mache erst einige Versuche, mit jeweils verschiedenen, zufälligen Splits in Wachstums und Validierungssätze.
• Tracke die Komplexität des gekürzten Baumes, erlernt in jedem Versuch. C=durchschnittlich gekürzte Bäume Komplexität
• Lass einen finale Baum (Breadth-first) aus allen Trainingsdaten bauen und stoppe, wenn C erreicht wurde

Neurale Netzwerke
Biological Inspiration
• Lernansatz basiert auf das modellieren im biologischen neuralen System
• Perceptron: Erster entwickelter Algorithmus um leichte Neurale Netzte zu modellieren.
• Backpropagation: Komplexerer Ansatz mit mehreren Schichten

Perceptron
Modelliere das Netzwerk als Graph mit Zellen als Knoten und synaptischen Verbindungen als gewichtetete Kanten von Knoten i zu j, wij

Algorithmus:
• Update die Gewichte wiederholend bis sie konvergieren
• Initialisiere Gewichte für zufällige Werte bis der Output von allen Trainingsbeispielen korrekt ist
Für jedes Trainingspaar E mache:
o Berechne den aktuellen Output oj für E gegeben der Inputs oi
o Vergleiche den aktuellen Output mit dem Zielwert, tj, für E
o Update die synaptischen Gewichte und Schwelle mit einer Lernregel
• Jede Ausführung des äußeren Kreislaufs wird gewöhnlich ‚epoch‘ genannt.
Definition Linear separierbar:
2 Sätze an Punkten in einem 2-D Raum sind linear separierbar, wenn sie von einer einzigen linearen Linie getrennt werden können. Im Allgemeinen, 2 Punktsätze sind linear separierbar im n-D Raum, wenn sie durch eine Hyperebene getrennt werden können.
• Da Perceptron eine lineare Schwellen Funktion nutzt, wird nach einem linearen Separator gesucht, der die Klassen diskriminiert.
• Können im Allgemeinen keine Gleichheitsfunktion lernen.

Grenzen: System kann keine Konzepte lernen, es kann nicht verkörpern-

Perceptron convergence theorem:
Wenn Daten linear separierbar sind und daher ein Satz von Gewichten existiert, die konsistent mit den Daten sind, dann wird der Algorithmus wahrscheinlich zu einem konsistenten Satz an Gewichten konvergieren.
Perceptron cycling theorem:
Wenn die Daten nicht linear separierbar sind, wird der Algorithmus wahrscheinlich ein Satz an Gewichten und die Schwelle am Ende Der Epoche ständig wiederholen und daher in einer unendlichen Schleife enden.

• Durch das checken der wiederholten Gewichte und Schwelle kann man garantieren, dass an einem positiven oder negativen Ergebnis abgebrochen wird.
Perceptron als Bergsteigeralgorithmus
• Der Hypothesenraum nach dem gesucht wird ist ein Satz an Gewichten und einer Schwelle
• Ziel ist es, den Klassifizierungsfehler der Trainingsdaten zu minimieren
• Perceptron macht dies effektiv, indem die Gewichte an jedem Punkt etwas geändert werden.
• Für ein einzelnes Modell Neuron gibt der Raum ein einzelnes Minimum

Multi-Layer Networks

• Können beliebige Funktionen repräsentieren, aber ein effektiver Lernalgorithmus ist schwer.
• Enthält typischerweise eine Input, eine verborgene und eine Output Schicht, jede komplett mit der nächsten verbunden

• Die Gewichte bestimmen die berechnete Funktion. Gegeben eine beliebige Anzahl an verborgener Einheiten, eine boolean-Funktion, kann mit einer einzigen verborgenen Schicht berechnet werden.
• Die normale lineare Schwellen Funktion ist nicht differenzierbar an der Schwelle.
• Jedoch brauchen wir den Output einer Einheit als differenzierbare Funktion der Inputs und Gewichte, um es ansteigender Abstammung machen zu können.
Differentiable Output Function
• Es wird eine nicht lineare Output Funktion benötigt, um sich außerhalb der linearen Funktion bewegen zu können
o Ein Viel-Schichten-Netzwerk ist immer noch linear
• Die Standardlösung ist, eine nicht-lineare, differenzierbare sigmoidal Funktion zu nutzen.