R. Ferber: Data Mining & Information Retrieval 1.5.4.3.2

4.4.1.2: Koeffizientenbestimmung

Auch bei der Bestimmung der Koeffizienten kann man wieder verschiedene Verfahren und verschiedene Gütefunktionen verwenden. Für die binäre Entscheidung mit einer LTU verwendeten Brodley und Utgoff das klassische Verfahren der (rekursiven) Methode der kleinsten Fehlerquadrate ( Recursive Least Squares RLS). Ziel ist es dabei die Summe

_{_dT}(d·x-z_d)²

der Quadrate der Abweichungen des Skalarprodukts für das Beispiel d von dem vorgegebenen Entscheidungswert z_d{-1,1} zu minimieren. Dazu werden Methoden aus der linearen Algebra verwendet. Zu dem Koeffizientenvektor x einer linearen Schwellwertfunktion wird für jedes Beispiel d=(w₀,...,w_n) der Vektor

Dx=-P_jd(d·x-z_d)

addiert. P_j bezeichnet dabei die Fehlerkovarianzmatrix, die nach jedem Schritt neu berechnet wird (siehe Brodley und Utgoff 1995 [->]) und den Einfluss der Veränderungen kleiner werden lässt. Die RLS ist verhältnismäßig aufwendig, garantiert aber bei linear separierbaren Beispielen ein richtiges Ergebnis (wenn auch eventuelle erst nach mehreren Durchgängen).

Es gibt auch einfachere Methoden die Koeffizientenvektoren einer linearen Schwellwertfunktion oder einer linearen Maschine zu ändern. Um zu erreichen, dass ein bisher falsch klassifiziertes Beispiel in einer binären linearen Maschine richtig klassifiziert wird, kann man zu dem Koeffizientenvektor x der Menge, in die das Beispiel gehört, ein skalares Vielfaches des Beispielvektors d addieren und von dem Koeffizientenvektor y der Menge, der es fälschlich zugewiesen wurde, den selben Korrekturvektor abziehen. Den skalaren Faktor kann man aus der Beziehung (x+cd)*d-(y-cd)*d=0 folgendermaßen herleiten: (x+cd)*d-(y-cd)*d=(x-y)*d+2cd*d und damit

Weiter kann man eine kleine positive Zahl e zu dem Faktor hinzuaddieren. Dadurch liegt das Beispiel nicht genau auf der Grenze der beiden Entscheidungsmengen.

Man kann nun sequentiell die Beispiele durchgehen und immer dann, wenn ein Beispiel von der aktuellen Entscheidungsfunktion falsch zugeordnet wird, diese so ändern, dass es richtig zugeordnet wird. Wenn die Mengen der Beispiele aber nicht linear separabel sind, kann dieses Verfahren nicht konvergieren. Man kann aber versuchen den Einfluss von einigen wenigen Ausreissern zu verringern. Dazu kann man den skalaren Faktor mit einer zeitlichen Dämpfung versehen, sodass die Korrekturen im Laufe des Algorithmus immer geringer werden.

Eine anderes Verfahren wird im Pocket Algorithmus von Gallant verwendet: Hier werden zunächst alle Koeffizienten auf Null gesetzt. Mit dieser Entscheidungsfunktion werden dann solange zufällig ausgewählte Beispiele des Trainingsets klassifiziert, bis ein Beispiel falsch klassifiziert wird. Die Anzahl der bis dahin richtig klassifizierten Beispiele wird zusammen mit den Koeffizientenvektoren in der "Pocket" P gespeichert und ein Lernschritt ausgeführt, sodaß das fehlerhafte Beispiel richtig klassifiziert wird. Dann werden mit dieser neuen Entscheidungsfunktion wieder zufällig ausgewählte Beispiele klassifiziert bis ein Fehler auftritt. Ist die Anzahl der so richtig klassifizierten Beispiele größer als die der Funktion die in P gepeichert ist, wird diese durch die aktuelle Funktion ersetzt. Durch die zufällige Auswahl der Beispiele soll so in einem Hill-Climbing Prozess eine möglichst gute Entscheidungsfunktion ermittelt werden.