Sie sind hier: Wie erkläre ich dem Computer, ...

Wie erkläre ich dem Computer, was eine Lakritzschlange ist?

Mittwoch 17. Februar 2010 von
Simon Praetorius
Vorschaubild
Wenn man sich das nebenstehende Bild anschaut, ist es einem auf den ersten Blick klar, dass es sich um eine gerollte Schlange, ähnlich wie eine Lakritzschlange, handelt. Wie aber bringt man einem Computer bei zu erkennen, dass diese Punktwolke eine gewisse Struktur hat und nicht einfach zufällig platziert wurde, bzw. wenn man einen weiteren Punkt auf der Schlange zeichnet, soll der Computer zuverlässig sagen, ob der Punkt auf der Schlange liegt, oder daneben.

Das mit der schlangenförmigen Punktwolke ist natürlich nur ein Beispiel um die Fragestellung grafisch aufzubereiten. Wo gibt es solche ähnlichen Probleme in der Praxis? Es geht hier um Datenklassifikation, ich möchte von meinem Computer wissen, ob ein neues Datum zu einer Klasse von Daten gehört oder nicht, z.B. ob eine neu eingetroffene E-Mail Spam ist und aussortiert werden soll, oder ob die Mail in den Posteingang gelegt werden kann. In der heutigen Zeit, in der man mit Werbung überhäuft wird, ist dies ein wichtiges Problem und es gibt eine ganz Reihe von Lösungsansätzen, die mehr oder weniger gut funktionieren. Manch einer hat sicher in E-Mail-Programm schon Buttons gesehen, mit denen man E-Mail als unerwünscht oder erwünscht klassifizieren kann. Ich verwende das E-Mail-Programm Evolution unter Linux und da wird empfohlen erst 100 Mails als erwünscht und 100 als unerwünscht einzuordnen, bevor der Spamfilter richtig arbeiten kann, d.h. man muss dem Computer erst beibringen, was Werbung ist und was private/geschäftiliche E-Mails sind.

Einen Algorithmus zur Datenklassifikation, der z.B. zum Erkennen von Mustern oder Spam eingesetzt werden könnte, möchte ich hier vorstellen: Support Vector Data Description (SVDD). Ersteinmal arbeiten wir mit Zahlen/Vektoren, d.h. alle Daten müssen als Punkte x∈Rn dargestellt werden, z.B. indem man eine E-Mail auf Schlüsselwörtern untersucht und für ein Wort, wenn es im Text vorkommt, eine 1 setzt an einer Stelle im Vektor, sonst eine 0. Siehe dazu z.B. ein PDF über Dokument Klassifikation. Gesucht ist eine Funktion f:Rn→R, die angibt, ob ein Punkt x zu einer Klasse von Daten Ω gehört, oder nicht:

x∈Ω, falls f(x)≥0, x∉Ω, falls f(x)<0

Trainingsdaten umschlossen von einer KugelTrainingsdaten umschlossen von einer Kugel
Aus einer Menge von Trainingspunkten xi∈Ω0 soll nun diese Funktion f approximiert werden. Der Ansatz, der im SVDD-Verfahren gemacht wird, ist die Trainigspunkte durch eine Kugel zu umschließen. Alle Punkte die dann in der Kugel liegen gehören zu Ω, alle die außerhalb liegen nicht. Diese Kugel sollte aber ein möglichst kleines Volumen haben, damit nicht zuviele Punkte zur Klasse gezählt werden. Dies ergibt ein Minimierungsproblem:

min{1/2 R2} bei ||a-xi||2 ≤ R2 ∀i

Wobei a den Mittelpunkt und R den Radius des Kreises darstellt. (Warum gerade 1/2 R2 minimieren? Dies hat eher kosmetische Gründe, damit die Formeln am Ende wieder schön aussehen. Man könnte R minimieren, dann müsste aber zusätzlich noch gefordert werden, dass R≥0, denn negative Radien gibt es nicht.) Lässt man noch zu, dass sich in die Trainingsdaten ein paar Fehler eingeschlichen haben und will man diese tolerieren, ergibt sich ein angepasstes Optimierungsproblem mit Schlupfvariablen ξ:

min{1/2 R2 + C⋅∑i ξi} bei ||a-xi||2 ≤ R2 + ξi, ξi≥0 ∀i

Klassifikation für Spirale mit nichtlinearer "Kugel" als rote Linie angedeutetKlassifikation für Spirale mit nichtlinearer "Kugel" als rote Linie angedeutet
Über die Lagrange-funktion und duale Variablen kann man dieses Problem in ein Duales Problem überführen, bei dem die zu minimierende Funktion wieder eine quadratische funktion ist, nun aber einfachere Nebenbedingungen vorliegen: Außerdem werden die Trainingspunkte nicht mehr direkt verwendet, sondern nur Skalarprodukte von je zwe Trainingspunkten. Nutzt man anstatt des Skalarprodukts ⟨xi, xj eine Kernelabbildung k(xi, xj), die ein Skalarprodukt in einem anderen Raum (sogenannter Featureraum, in den man die Trainingspunkte abbilden kann) repräsentiert, so ist es nun möglich auch nichlineare Kugeln zu berechnen. Siehe dazu eine mögliche Klassifikation für unsere Lakritzschlange. das Duale Problem lautet wie folgt:

min{αTKα - αTb} bei 0≤α≤C, ∑i αi=1

Wobei die Matrix Kij=⟨xi, xj als Kernelmatrix bezeichnet wird und bi=⟨xi, xi die Diagonale der Kernelmatrix darstellt. Die Entscheidungsfunktion f, die angibt, ob ein Punkt z zu Ω gehört, oder nicht, lässt sich auch in den dualen Variablen αi darstellen:

f(z) = R2 - ⟨z, z⟩ + 2∑i αi⟨xi, z⟩ - ∑ij αi⟨xi, xj⟩αj

mit dem Radius R des Kreises, der sich defniert über einen Trainingspunkt xs, für den gilt: 0<αs<C:

R2 = ⟨xs, xs⟩ - 2∑i αi⟨xi, xs⟩ + ∑ij αi⟨xi, xj⟩αj

So, genug für heute mit Formeln herumgespielt. Es bleiben noch einige Fragen offen: wie kommt man von der ersten Formulierung mit Radius und Mittelpunkt, auf das duale Problem? Wie löst man das Minimierungsproblem der dualen Aufgabe? Was ist, wenn man sehr viele Trainingsdaten hat, und die Matrix K sehr groß wird? Kann man dann das Problem noch effizient lösen? Das sind alles Fragen, für die es Antworten gibt, die ich hier aber nicht geben möchte, weil sie den Rahmen dieses Weblogs absolut sprengen. Dem interessierten Leser seien entsprechende Fachartikel empfohlen, die über Google über die Suchwörter SVDD, one-class svm, support vector, o.Ä. gefunden werden können.

In einem Seminar am Institut für Numerik/Optimierung habe ich einen Vortrag gehalten, der auch SVDD kurz erläutert, allerdings auch noch weitere Ansätze aufzeigt.
Besucher: 9400 | Permalink | Kategorie: Nicht eingeordnet
Tags: , ,
Kommentar hinzufügen