Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Also Support-Vector-Machines sind eigentlich nicht so spannend, aber sind halt irgendwie wichtig, weil halt so ein Standard-Tool.

Was ist die Idee dahinter? Na ja, die Idee ist halt irgendwie, dass wenn wir so einen linearer Classifier wollen, über so irgendeinen Datensatz,

dann suchen wir uns halt irgendwie die lineare Funktion aus, die halt irgendwie den Abstand zu beiden Seiten halt möglichst maximalisiert.

Was natürlich den Vorteil hat, dass wenn wir zusätzliche Datenpunkte sammeln im Laufe der Zeit, dann lässt sich das Ganze natürlich deutlich besser verallgemeinern,

wenn wir irgendwo in der Mitte durchgehen, als wenn wir irgendwie so direkt am Rand kleben. Das ist natürlich nicht so ideal.

Das heißt, wir picken uns halt mehr oder minder die Extrempunkte aus, das sind unsere Support-Vektoren, und dann suchen wir irgendwie diese Linie in der Mitte.

Das lässt sich sehr angenehm machen, das ist einfach nur das übliche Blabla, indem wir diese eine dicke Funktion maximieren, die nennen wir SVM-Equation.

Ja, das ist eigentlich die gesamte Kernidee hinter der ganzen Geschichte. Und dann gibt es noch einen hübschen Trick, nämlich was machen wir,

wenn wir halt irgendwie so einen Datensatz haben, der sich nicht linear separieren lässt, wie zum Beispiel hier, wenn wir hier irgendwie so einen dicken Kreis haben,

und wir wollen die Punkte da drin finden. Was machen wir dann? Na ja, wir mappen irgendwie diesen ganzen zweidimensionalen Kram in einen höherdimensionalen Raum ein,

in dem Fall irgendwie in den dreidimensionalen, suchen uns eine Funktion, die das macht, in diesem Beispiel zum Beispiel die hier,

und dann machen wir halt einfach dasselbe im dreidimensionalen, da lässt sich das wunderbar linear separieren, indem wir hier halt eine Ebene durchziehen.

Und der Trick hinter der ganzen Geschichte ist im Prinzip, sich eine Einbettung in den dreidimensionalen Raum, oder halt je nach Datensatz in den höherdimensionalen,

uns eine Einbettung zu suchen, die halt irgendwie möglichst so schön ist, dass wenn wir das Ergebnis hinterher in diese Formel einsetzen,

also indem wir das Skalarprodukt hier ersetzen durch das Skalarprodukt von den höherdimensionalen Vektoren, dass sich das möglichst schön berechnen lässt.

Das nennt sich dann Kernelfunction, und der Trick dahinter ist, wenn wir uns eben eine Funktion suchen, die halt möglichst angenehm ist in der Hinsicht,

wie zum Beispiel hier mit diesem Wurzel 2x1x2, also die Wurzel sollte hier nach der 2 aufhören,

wenn wir uns diese Funktion hier zum Beispiel rauspicken, dann wird halt das Skalarprodukt aus den höherdimensionalen Vektoren simplifiziert,

sich einfach zum Quadrat von den einzelnen Skalarprodukten.

Deswegen steht da die Wurzel 2, dann ist es im Prinzip einfach nur, wie heißt sich das nochmal, quadratische Ergänzung, kennt ihr alle noch, hoffentlich vielleicht, binomische Formel rückwärts halt.

Genau, dann suchen wir uns halt eine von den Funktionen, die das schön macht, und dann reduziert sich das auf das hier,

und dann müssen wir auch tatsächlich nur noch das Quadrat von den einzelnen Skalarprodukten ausrechnen,

statt dass wir wirklich die Kernelfunktion angewandt auf die einzelnen Vektoren ausrechnen und dann das Skalarprodukt bilden.

Das ist so ein bisschen die Idee dahinter.

Das Schöne an dieser dicken Funktion, ich meine, wir werden jetzt nicht beweisen, dass das äquivalent ist zu der Standarddarstellung von linearen Funktionen, also zu dem Term,

das beweisen wir nicht, aber das dürft ihr mir ruhig glauben, bzw. ihr dürft das Russell und Norwick glauben, die behaupten das.

Das angenehme daran ist halt einfach, dass sie, wo war die Liste, dass sie konvex ist, das heißt wir bleiben schon mal nicht in irgendwelchen linearen Minima hängen, das ist natürlich ein großer Vorteil.

Der andere Vorteil ist, dass die Inputvektoren halt tatsächlich nur in der Form von Skalarprodukten auftauchen, bzw. unter Kernelfunktionen, aber die lässt sich halt idealerweise auch auf irgendwas angenehmes reduzieren.

Ja, und dann ist es nur noch ein Maximierungsproblem, und ein Maximierungsproblem ist relativ angenehm zu lösen.

Und wenn wir das gemacht haben, dann kommen wir am Schluss halt tatsächlich auf diesen Vektor alpha, der halt genau die Weights von unseren linearen Funktionen sind,

und dann können wir das am Schluss auch problemlos wieder umschreiben in eine lineare Funktion mit halt eben genau diesen Parametern.

Ja, so viel zu Support Vector Machines.

Gut, also hier nochmal Summary über diesen ganzen Lernkram, habe ich ja letztes Mal schon durchgenudelt, müssen wir jetzt glaube ich auch nicht nochmal machen.

Was ist an der ganzen Sache wichtig? Naja, okay, irgendwie halt überhaupt mal das allgemeine Modell, was Lernen überhaupt ist, oder was Lernen zumindest im Kontext von unseren Agenten ist.

So ein paar allgemeine Sachen, die natürlich irgendwie wichtig sind. Wie unsere Lernmethode aussieht, hängt natürlich tatsächlich von den Details des Problems ab, das wir lösen wollen, und von unserem Agentenmodell.

Logischerweise haben wir immer Occam's Razor, je simpler eine Hypothese, desto besser.

Ja, dann wir haben Decision Tree Learning durchgenudelt, da hatte jetzt auch ein Übungsblatt dazu, was einfach nur ein fancy way ist, um zu sagen, wir wollen Flowcharts bauen.

Ja, lineare Regression hatten wir, das taucht auch irgendwie in fast allen Lernmethoden letzten Endes auf. Ja, und Hard- und Soft-Thresholds, wobei natürlich im Allgemeinen Soft-Thresholds deutlich angenehmer sind zu behandeln, einfach weil sie sich differenzieren lassen.

Gut. So, dann haben wir uns Knowledge and Learning angeschaut, und warum es irgendwie praktisch ist, wenn wir Sachen lernen wollen, wenn wir bereits a priori Wissen haben und nicht tatsächlich jedes Mal wieder von Null anfangen müssen.

Das klingt so ultra trivial, aber ich meine, wenn man das Ganze formalisieren möchte, ist es natürlich nicht mehr unbedingt.

So, wie formalisieren wir den Kram überhaupt? Naja, wir benutzen halt natürlich Logik. Hat natürlich den schönen Vorteil, dass es 100 Logiken gibt, aber ich meine, wir reduzieren uns jetzt natürlich irgendwie auf First-order-Logik maximal.

So, die Idee ist natürlich, dass wir irgendwie die Sachen, die wir irgendwie trivialerweise von vorneherein schon wissen, bevor wir überhaupt angefangen, irgendein Problem oder irgendeine Funktion zu erlernen, wir dieses Wissen, das wir haben, möglichst ausnutzen wollen.

Dazu unterteilen wir irgendwie unsere Lernprobleme in, also ich meine, das hatten wir bei Decision Trees ja im Prinzip auch schon, wir haben halt irgendwie Descriptions und Classifications.

Bei Decision Trees sind Descriptions einfach nur alle Tabellen bis auf die letzte, die Klassifikation ist die letzte Tabellenspalte. Wir versuchen alles einfach irgendwie als logische Formeln auszudrücken.

Ja, und ich meine, in den meisten Fällen reicht es einfach uns auf First-order-Logik unter Umständen sogar ohne Quantoren zu reduzieren.

Quantoren sind natürlich praktisch, aber ich meine, wenn es ohne geht, ist es umso berechenbarer, also umso besser.

So, und dann gucken wir uns Logic-based and Active Learning an, wo wir versuchen, eine Hypothese H zu lernen, die zusammen mit den Descriptions des Problems, das wir lernen möchten, tatsächlich irgendwie die Klassifikation impliziert.

Ich hoffe, ihr kriegt nicht alle furchtbare Vietnam-Flashbacks zu letztem Semester oder so, wenn ihr jetzt wieder diese ganzen Symbol-Learning-Kupfen geworfen kriegt.

Ja, darauf sollte man vielleicht nochmal hinweisen, weil wenn wir das Ganze so formulieren, es ist klar, dass wenn H bereits, also wenn unsere Hypothese bereits die volle Klassifikation aller Beispiele, die wir soweit kennen, enthält, dann ist natürlich diese Implikation trivialerweise wahr, aber halt auch total unsinnig.