4.5 Perceptron

Kurz gesagt: Perceptron = lineare Regression + Vorzeichen-Aktivierung 📄 04_linear_methods_ws26.pdf, Folie 30.

Grundidee

📄 04_linear_methods_ws26.pdf, Folie 31

• Das Perceptron ist der einfachste Weg, mit einer linearen Maschine zu klassifizieren. Der andere Weg ist die logistische Regression (4.7).
• Es geht um binäre Klassifikation. Die Klassen werden der Bequemlichkeit halber mit $y_i = \pm 1$ kodiert (nicht mit 0/1). Das macht die Formeln unten kompakt.
• Es beruht auf dem geometrischen Konzept der Hyperebene: Die Klassen müssen durch eine Hyperebene (in 2D: eine Gerade) trennbar sein.
• Die Idee wird später zur Support Vector Machine erweitert (Kapitel 6).

Das Modell als Netz: Eingänge $1, x_1, \dots, x_m$, Gewichte $w_0, \dots, w_m$, eine Summe (net input function) und danach eine Sprungfunktion als Aktivierung:

$$z = \sum_{j=1}^d w_jx_j + b, \qquad \hat y = \operatorname{sign}(z) = \begin{cases} +1 & z \ge 0\\ -1 & z < 0\end{cases}$$

Die Entscheidungsgrenze (decision boundary) ist die Hyperebene $z = 0$. Der Vektor $(w_1, \dots, w_d)$ steht senkrecht auf ihr und zeigt zur Seite der Klasse $+1$ (Pfeil $(\beta_1, \beta_2)$ auf der Demo-Folie 📄 04_linear_methods_ws26.pdf, Folie 32). Die Demo verwendet übrigens die 0/1-Kodierung mit $\hat y = \text{step}(z)$, das ist inhaltlich dasselbe.

Warum nicht einfach lineare Regression auf $\pm1$? Auf Folie 31 ist die orange Linie die Entscheidungsgrenze einer linearen Regression auf die Klassenlabels, die blauen Linien sind Perceptron-Lösungen. Die Regression versucht, für jeden Punkt den Wert $\pm 1$ möglichst genau zu treffen. Punkte, die weit auf der richtigen Seite liegen, erzeugen dabei große Fehler und ziehen die Grenze zu sich, obwohl sie längst richtig klassifiziert sind. Das Perceptron kümmert sich nur um die falsch klassifizierten Punkte.

Die Verlustfunktion

📄 04_linear_methods_ws26.pdf, Folie 33

$z_i = \sum_{j=1}^d w_jx_{ij} + b$ ist (bis auf einen Faktor) der vorzeichenbehaftete Abstand (signed distance) von Punkt $i$ zur Hyperebene:

• Für Beispiele mit $y_i = +1$ sollte $z_i$ positiv sein.
• Für Beispiele mit $y_i = -1$ sollte $z_i$ negativ sein.

Beides zusammen: Richtig klassifiziert ⇔ $y_i z_i > 0$. Dafür ist die $\pm1$-Kodierung so praktisch.

Die Verlustfunktion ist nicht eindeutig festgelegt. Sie sollte 0 sein, wenn alle Beispiele richtig liegen, und positiv sonst. Eine mögliche Wahl (Rosenblatt):

$$\text{loss} = \sum_i \max(0, -y_iz_i) = \sum_{i\in\mathcal M} -y_iz_i$$

$\mathcal M$ ist die Menge der falsch klassifizierten Beispiele (misclassified).

• Richtig klassifizierte Punkte tragen 0 bei.
• Falsch klassifizierte Punkte tragen $-y_iz_i > 0$ bei, und zwar umso mehr, je weiter sie auf der falschen Seite liegen.
• Loss $= 0$ für eine trennende Ebene, $> 0$ für eine nicht trennende.

Die Grafik auf der Folie vergleicht drei Kandidaten als Funktion von $y_iz_i$:

Verlust	Formel	Eigenschaft
0-1-Verlust (Fehler zählen)	1 falls $y_iz_i$ kleiner als 0, sonst 0	stückweise konstant, Gradient überall 0 oder undefiniert, für Gradientenabstieg unbrauchbar
quadratisch	$\max(0, -y_iz_i)^2$	glatt, bestraft große Fehler stärker
Rosenblatt	$\max(0, -y_iz_i)$	stückweise linear, liefert einen konstanten Gradienten für falsche Punkte

Warum nicht direkt die Anzahl der Fehler minimieren? Weil der 0-1-Verlust flach ist: Verschiebt man die Gerade ein wenig, ändert sich die Fehlerzahl meist gar nicht. Gradientenabstieg bekommt keine Information, in welche Richtung er gehen soll. Der Rosenblatt-Verlust dagegen sagt „dieser Punkt liegt um so viel auf der falschen Seite“.

Gradient

Für ein falsch klassifiziertes Beispiel ist $-y_iz_i = -y_i(\sum_j w_jx_{ij} + b)$. Ableiten nach $w_j$ und $b$ (die Folie nennt den Verlust hier $D(w,b)$):

$$\frac{\partial D(w,b)}{\partial w_j} = -\sum_{i\in\mathcal M} y_ix_{ij}, \qquad \frac{\partial D(w,b)}{\partial b} = -\sum_{i\in\mathcal M} y_i$$

Die Lernregel

📄 04_linear_methods_ws26.pdf, Folie 34 Man geht die Punkte einzeln durch und macht für jeden falsch klassifizierten Punkt einen Gradientenschritt (also stochastischer Gradientenabstieg mit einem Punkt pro Schritt):

$$\boldsymbol w \leftarrow \boldsymbol w + \eta\,y_i\boldsymbol x_i, \qquad b \leftarrow b + \eta\,y_i$$

Im Code auf der Folie ist $\eta = 1$:

def update_params(X, y, w, b):
    didUpdate = False
    for ys, xs in zip(y, X):
        if ys * (np.dot(xs, w) + b) < 0:   # falsch klassifiziert
            w = w + ys * xs                # eta = 1
            b = b + ys * 1
            didUpdate = True
    return w, b, didUpdate

Man ruft update_params so lange auf, bis didUpdate falsch ist, also ein ganzer Durchlauf ohne Fehler bleibt.

Intuition: Ist ein Punkt der Klasse $+1$ falsch klassifiziert ($z_i$ zu klein), addiert man $\boldsymbol x_i$ zu $\boldsymbol w$. Beim nächsten Mal ist $z_i$ um $\lVert\boldsymbol x_i\rVert^2 + 1$ größer, der Punkt rückt auf die richtige Seite. Für einen falschen Punkt der Klasse $-1$ zieht man $\boldsymbol x_i$ ab. Die Ebene dreht und verschiebt sich also jedes Mal in Richtung „diesen Punkt richtig machen“.

Konvergenz: Der Algorithmus konvergiert in endlich vielen Schritten, wenn das Problem linear trennbar ist (Perceptron-Konvergenzsatz). Sonst gibt es in jedem Durchlauf wieder Fehler, und die Gewichte springen endlos hin und her.

Fallstrick: Start bei null und < 0

Startet man mit $\boldsymbol w = \boldsymbol 0$, $b = 0$, ist für alle Punkte $z_i = 0$ und damit $y_iz_i = 0$. Mit der Bedingung < 0 aus dem Folien-Code passiert dann nie ein Update, und der Algorithmus meldet fälschlich Konvergenz. Entweder zufällig initialisieren oder auf <= 0 prüfen (ein Punkt genau auf der Grenze zählt als falsch).

Unklarheit auf der Folie

Im Notebook-Ausschnitt auf Folie 34 steht als Gradient „$\partial l/\partial w = -y\cdot w$“. Gemeint ist $-y\cdot\boldsymbol x$, wie die Formel auf Folie 33 und auch der Code (w + ys*xs) zeigen.

Durchgerechnetes Beispiel

Ergänzung, nicht auf den Folien: Drei Punkte, $\eta = 1$, Start $\boldsymbol w = (0,0)$, $b = 0$, Bedingung für ein Update: $y_iz_i \le 0$.

• $P_1 = (1,2)$, $y = +1$
• $P_2 = (2,1)$, $y = -1$
• $P_3 = (0,0)$, $y = -1$

Epoche	Punkt	$z = \boldsymbol w\cdot\boldsymbol x + b$	$yz$	Update?	neues $\boldsymbol w$	neues $b$
1	$P_1$	0	0	ja, $+P_1$	$(1,2)$	1
1	$P_2$	$2+2+1 = 5$	$-5$	ja, $-P_2$	$(-1,1)$	0
1	$P_3$	0	0	ja, $-P_3$	$(-1,1)$	$-1$
2	$P_1$	$-1+2-1 = 0$	0	ja, $+P_1$	$(0,3)$	0
2	$P_2$	$0+3+0 = 3$	$-3$	ja, $-P_2$	$(-2,2)$	$-1$
2	$P_3$	$-1$	1	nein	$(-2,2)$	$-1$
3	$P_1$	$-2+4-1 = 1$	1	nein
3	$P_2$	$-4+2-1 = -3$	3	nein
3	$P_3$	$-1$	1	nein

In Epoche 3 gibt es kein Update mehr, fertig. Die Entscheidungsgrenze $-2x_1 + 2x_2 - 1 = 0$ ist die Gerade $x_2 = x_1 + 0{,}5$. $P_1$ liegt darüber (Klasse $+1$), $P_2$ und $P_3$ darunter.

Schwächen des Perceptrons

• Welche Trennlinie? Jede trennende Gerade hat Verlust 0. Welche man bekommt, hängt von Startwerten und Reihenfolge der Punkte ab (die zwei blauen Linien auf Folie 31). Oft liegt die Lösung knapp an einem Punkt (Folie 72, linkes Bild).
• Keine Sicherheit: Das Perceptron sagt nur $\pm1$, nicht „wie sicher“.
• Nicht trennbare Daten: keine Konvergenz.

Genau diese Fragen („Which of the separating lines? How sure is the classifier?“, 📄 04_linear_methods_ws26.pdf, Folie 38) motivieren die probabilistische Behandlung und die logistische Regression. Die Frage nach der „besten“ Trennlinie mit größtem Abstand beantwortet die SVM.

Geschichte

📄 04_linear_methods_ws26.pdf, Folie 35 Das Perceptron wurde 1957 von Frank Rosenblatt vorgestellt. Der Mark 1 Perceptron war ein Rechner, der als Perceptron fest verdrahtet war. Die Folie zeigt ihn neben dem Netzschema: Eingänge, Gewichte, Summe, Sprungfunktion. Das ist das Urbild des künstlichen Neurons.