Exkurs: Maschinelles Lernen - Delta-Regel nach Rosenblatt

Kommen wir nun zu der eigentlichen Stärke von Perzeptronen, dem so genannten maschinellen Lernen, durch das sich Perzeptronen ganz prinzipiell von herkömmlichen Algorithmen entscheiden.

Die Gewichte und Schwellenwerte von Perzeptronen mühsam per Hand zu justieren ist sehr arbeitsaufwendig. Daher hat Rosenblatt 1958 einen Algorithmus entwickelt, mit dessen Hilfe die Gewichte und Schwellenwerte von Perzeptronen automatisiert mittels so genannter Trainingsdaten bestimmt werden können. Dazu werden die Gewichte und Schwellenwerte zu Beginn des Lernprozesses einfach mit Zufallszahlen belegt und dann iterativ mittels vorklassifizierter Trainingsdaten sukzessive verbessert.

Um bei dem Beispiel mit den Tieren zu bleiben, kann man sich vorstellen, dass es eine Menge von Tieren gibt, die durch Menschen als gefährlich bzw. ungefährlich klassifiziert worden sind. Mit diesen Trainingsdaten werden Gewichte und Schwellenwert eines Perzeptron nun so trainiert (also sukzessive angepasst), dass das Perzeptron anschließend selbständig weitere, ihm bisher unbekannte, Tiere als gefährlich bzw. ungefährlich klassifizieren können soll.

Um den Lernalgorithmus nach Rosenblatt detailliert zu erläutern, betrachten wir zunächst wieder ein Perzeptron mit zwei Eingängen. Zur Veranschaulichung kann man sich vorstellen, dass es sich dabei wieder um die beiden Merkmale Zahn- und Augengröße handelt:

Statt die Gewichte $\overrightarrow{w}$ und den Schwellenwert $\mathrm{\Theta }$ mühsam per Hand zu justieren, soll das Perzeptron nun selbständig lernen, auf bestimmten Eingangsgrößen $\overrightarrow{x}$ mit einer jeweils vorgegebenen Ausgangsgröße $y\in \{0,1\}$ zu reagieren.

Bevor der Lernalgorithmus von Rosenblatt weiter unten formal in Pseudocode angegeben wird, kann man durch die folgende Klickstrecke schon mal ein Gefühl von der prinzipiellen Funktionsweise des Algorithmus' bekommen. Die rot dargestellten Punkte sollen durch die Separationsgerade von den grünen Punkten getrennt werden. Rote Punkte stellen gefährliche Tiere dar, so dass das Perzeptron in diesen Fällen feuern soll. Blau dargestellt ist jeweils die Separationsgerade mit angeheftetem Gewichtsvektor $\overrightarrow{w}$. Der Gewichtsvektor zeigt in den Halbraum, für den das Perzeptron feuert (also $y=1$ am Ausgang anliegt).

Klickstrecke: Grundsätzliche Idee des Algorithmus nach Rosenblatt

Führe aus, solange noch nicht alle Lernpunkte korrekt klassifiziert werden:
start:
    wähle zufällig einen beliebigen Lernpunkt $\overrightarrow{x}$ aus (jeweils gelb markiert)
test:
    if   Lernpunkt $\overrightarrow{x}$ noch auf der falschen Seite der Gerade   then   goto adapt
    goto test
adapt:
    Drehe und translatiere die Gerade so, dass sie den Punkt $\overrightarrow{x}$ besser repräsentiert als vorher
    (durch geschickte Veränderung des Gewichtsvektors $\overrightarrow{w}$ und des Schwellenwertes $\theta$)
    goto test

Previous

Next

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53

Nun wird der Lernalgorithmus nach Rosenblatt zunächst in Pseudocode angegeben und im Anschluss daran wird die Funktionsweise des Algorithmus' dann auch noch einmal graphisch veranschaulicht.

Sei eine Menge an Eingabevektoren $\mathrm{\Omega }$ gegeben, die in zwei disjunkte Teilmengen $\mathrm{\Omega }={\mathrm{\Omega }}_P\cap {\mathrm{\Omega }}_N$ zerfällt. Für einen Eingabevektor $\overrightarrow{x}\in {\mathrm{\Omega }}_P$ soll das Perzeptron feuern ($y=1$), für einen Eingabevektor $\overrightarrow{x}\in {\mathrm{\Omega }}_N$ soll es nicht feuern ($y=0$). Um bei dem gewählten Beispiel zu bleiben, kann man sich vorstellen, dass ${\mathrm{\Omega }}_P$ die Menge der gefährlichen und ${\mathrm{\Omega }}_N$ die Menge der ungefährlichen Tiere darstellt.

Anschaulich formulierter Lern-Algorithmus nach Rosenblatt:

start:
    wähle $\overrightarrow{w}(0)\in {\mathbb{R}}^2$ zufällig (Startgewichte)
    wähle $\mathrm{\Theta }(0)\in \mathbb{R}$ zufällig (Startschwellenwert)
    setzte $t:=0$
test:
    Solange noch nicht ausgewählt $\overrightarrow{x}$
    und solange noch nicht alle $\overrightarrow{x}$ das gewünschte Ergebnis $y$ liefern,
    wähle $\overrightarrow{x}\in \mathrm{\Omega }$ zufällig
    if $\overrightarrow{x}\in {\mathrm{\Omega }}_P$ and $y=1$ then goto test
    if $\overrightarrow{x}\in {\mathrm{\Omega }}_P$ and $y=0$ then goto add
    if $\overrightarrow{x}\in {\mathrm{\Omega }}_N$ and $y=0$ then goto test
    if $\overrightarrow{x}\in {\mathrm{\Omega }}_N$ and $y=1$ then goto sub
add:
    setzte $\overrightarrow{w}(t+1):=\overrightarrow{w}(t)+\overrightarrow{x}$
    setzte $\mathrm{\Theta }(t+1):=\mathrm{\Theta }(t)-1$
    setzte $t:=t+1$
    goto test
sub:
    setzte $\overrightarrow{w}(t+1):=\overrightarrow{w}(t)-\overrightarrow{x}$
    setzte $\mathrm{\Theta }(t+1):=\mathrm{\Theta }(t)+1$
    setzte $t:=t+1$
    goto test

Anmerkung:

Im Rosenblatt-Algorithmus erscheint es zunächst etwas seltsam, dass der Gewichtsvektor $\overrightarrow{w}$ ausgerechnet um den Eingangsvektor $\overrightarrow{x}$ und der Schwellenwert $\mathrm{\Theta }$ um $-1$ geändert werden. Das liegt aber dran, dass die so genannten partiellen Ableitungen der Progagierungsfunktion $u(\overrightarrow{x})=\overrightarrow{w}\cdot \overrightarrow{x}-\mathrm{\Theta }$ gegeben sind durch: $$\frac{\partial u}{\partial w_i}=x_i\frac{\partial u}{\partial \mathrm{\Theta }}=-1$$ Bei einer partiellen Ableitung wird nur nach der angegebenen Variablen abgeleitet, alles andere wird als fester Parameter angesehen. Die partielle Ableitung nach einer bestimmten Größe ist also ein Maß dafür, wie stark sich die Funktion mit dieser Größe ändert. Im Rosenblatt-Algorithmus wird also in jedem Schritt die Progagierungsfunktion ggf. in Richtung ihrer stärksten Änderung variiert.

Geometrische Veranschaulichung des Lernalgorithmus

Durch den Lernalgorithmus wird der Gewichtsvektor wie in der Abbildung gezeigt sukkzessive gedreht, bis schließlich alle Eingangsvektoren $\overrightarrow{x}$ korrekt klassifiziert werden. Beachte jedoch, dass die Abbildung insofern unvollständig ist, als die Updateregeln für den Schwellenwert $\mathrm{\Theta }$ nicht berücksichtigt wurden. (Die tatsächlichen Separationsgeraden liegen bei Berücksichtigung der jeweiligen Werte von $\mathrm{\Theta }$ daher lediglich parallel zu den eingezeichneten Geraden $g_1,g_2$ und $g_3$.)

Zusammenfassung des Lernalgorithmus in einer einzigen Lernregel

Betrachte einen Eingangsvektor $\overrightarrow{x}\in \mathrm{\Omega }$. Sei $Y(\overrightarrow{x})$ die zugehörige Sollausgabe, also $$\begin{array}{r}Y(\overrightarrow{x}):=\{\begin{array}{ll}1& \overrightarrow{x}\in {\mathrm{\Omega }}_P\\ 0& \overrightarrow{x}\in {\mathrm{\Omega }}_N\end{array},\end{array}$$ und setzte $\delta :=Y(\overrightarrow{x})-y(\overrightarrow{x})$ als die Abweichung von $y$ von der Sollausgabe $Y$. Dann lassen sich die Unterfälle des obigen Lernalgorithmus elegant zusammenfassen zu je einer einzigen Lernregel für $\overrightarrow{w}$ und für $\mathrm{\Theta }$ als $$\begin{array}{rcl}\overrightarrow{w}(t+1)& :=& \overrightarrow{w}(t)+\delta \overrightarrow{x}\\ \mathrm{\Theta }(t+1)& :=& \theta (t)+\delta \cdot (-1)\\ & =& \theta (t)-\delta \end{array}$$ Meist wird noch eine so genannte Lenrate $\eta >0$ (Lerngeschwindigkeit) eingeführt, so dass man als Lernregel für Perzeptronen erhält: $$\begin{array}{rcl}\overrightarrow{w}(t+1)& :=& \overrightarrow{w}(t)+\eta \delta \overrightarrow{x}\\ \mathrm{\Theta }(t+1)& :=& \theta (t)-\eta \delta \end{array}$$ Wenn die Menge $\mathrm{\Omega }$ eine sehr große Menge Eingangsvektoren enthält, wird sie oft aufgeteilt in zwei disjunkte Teilmengen $$\begin{array}{rcl}{\mathrm{\Omega }}_L& :& \text{learning batch}\\ {\mathrm{\Omega }}_T& :& \text{testing batch}\end{array}$$

Die Teilmenge ${\mathrm{\Omega }}_L$ wird dann zum Trainieren des Perzeptrons nach der Lernregel verwendet, während die anderen Teilmenge ${\mathrm{\Omega }}_T$ zum anschließenden Testen verwendet wird, um herauszufinden, wie gut die Gewichte und der Schwellenwert des Perzeptrons justiert wurden. Oft wird das zahlenmäßiges Verhältnis von $\mathrm{\#}{\mathrm{\Omega }}_L:\mathrm{\#}{\mathrm{\Omega }}_T$ als $80\mathrm{\%}:20\mathrm{\%}$ gewählt.

Abschließend wird die obige Lernregel noch auf den Fall von $n$-dimensionalen Eingangsvektoren erweitert, so dass man den vollständigen Lernalgorithmus erhält als:

Lernalgorithmus für Perzeptronen

start:
    wähle $\overrightarrow{w}(0)\in {\mathbb{R}}^n$ zufällig (Startgewichte)
    wähle $\mathrm{\Theta }(0)\in \mathbb{R}$ zufällig (Startschwellenwert)
    wähle $\eta >0$ (Lernrate)
    setzte $t:=0$
step:
    wähle $\overrightarrow{x}\in {\mathrm{\Omega }}_L$
    if $\overrightarrow{x}\in {\mathrm{\Omega }}_P$ setze $Y:=1$
    if $\overrightarrow{x}\in {\mathrm{\Omega }}_N$ setze $Y:=0$
    berechne $y(\overrightarrow{x})=f_{\theta }(\overrightarrow{w}\cdot \overrightarrow{x})$ (Ausgabegröße)
    berechne $\delta =Y-y$ (Fehler)
    update $\overrightarrow{w}(t+1):=\overrightarrow{w}(t)+\eta \delta \overrightarrow{x}$
    update $\mathrm{\Theta }(w+1):=\mathrm{\Theta }(t)-\eta \delta$
    setzte $t:=t+1$
end:
    Solange es noch $\overrightarrow{x}\in {\mathrm{\Omega }}_L$ gibt mit $\delta \ne 0$ goto step

Anmerkung

Wird der Schwellenwert $\mathrm{\Theta }$ wie oben beschrieben in den Gewichtsvektor integriert, so fällt in dem obigen Algorithums die entsprechenden Zeile zum Update des Schwellenwertes $\mathrm{\Theta }$ weg, da es dann bereits automatisch in dem Update des Gewichtsvektors enthalten ist.

Rosenblatt hat 1958 gezeigt, dass der obige Algorithmus terminiert, falls die Menge der Eingabegrößen separierbar ist. Auf die Wiedergabe des Beweises wird an dieser Stelle verzichtet.

Anwendung auf neue Eingabegrößen

Nachdem das Perzeptron mit Hilfe der obigen Lernregel trainiert worden ist, kann es anschließend auch auf Eingabevektoren $\overrightarrow{x}\notin \mathrm{\Omega }$ angewandt werden, die gar nicht in der ursprünglichen Menge $\mathrm{\Omega }$ enthalten waren und für die die tatsächliche Ausgabegröße $Y$ daher unter Umständen noch unbekannt ist. In diesem Sinne stellt $y(\overrightarrow{x})$ dann eine Vorhersage für den tatsächlichen Wert $Y(\overrightarrow{x})$ dar.

Man beachte jedoch, dass es sich dabei lediglich um eine Vorhersage handelt, die sich (mit einer gewissen Wahrscheinlichkeit) bei näherer Analyse dann aber durchaus auch als falsch erweisen kann. In dem oben gewählten Beispiel könnte das bedeuten, dass das Perzeptron ein Tier als ungefährlich einstuft, während es sich in Wirklichkeit um ein äußerst gefährliches Tier handelt. Zum Beispiel könnte das Tier weder große Zähne noch große Augen haben aber trotzdem hochgiftig sein. Ein blindes Vertrauen auf die Vorhersage des Perzeptrons könnte abhängig vom Anwednungsszenario also sehr dramatische Konsequenzen haben.

Bedeutung der Trainingsdaten

Im Unterschied zu herkömmlichen Algorithmen ist für automatisiertes maschinelles Lernen die Verfügbarkeit von vorklassifizierte Trainingsdaten unerlässlich. Ohne solche Trainingsdaten kann der oben beschriebene Lern-Algorithmus zwar implementiert, aber nicht trainiert werden.

Damit liegt die Kontrolle solcher maschinell lernenden Algorithmen bei denjenigen, die Zugriff auf geeignete vorklassifizierten Daten haben. Vor diesem Hintergrund wird auch verständlich, warum es heute so lukrativ geworden ist, möglichst viele Daten über möglichst viele Menschen zu sammeln.

Aufgabe 1:

Finde weitere Beispiele, bei denen ein blindes Vertrauen in die Klassifikationsvorhersage eines Perzeptrons unerwünschte Konsequenzen haben könnte.

Aufgabe 2:

Recherchiere, welche Konzerne im Moment als die wertvollsten der ganzen Welt gelten. Fallen dir Gemeinsamkeiten auf? Warum werden ausgerechnet diese Konzeren als so wertvoll eingeschätzt?

Aufgabe 3:

Implementiere den Lernalgorithmus für das maschinelle Erlernen der AND, OR, NAND und NOR-Verknüpfungen.