Das Perceptron von Grund auf: Was ein Neuron berechnet

Ein Perceptron nimmt die Messwerte, multipliziert jeden mit einer Zahl, die es selbst kontrolliert, addiert sie, addiert noch eine weitere Zahl und betrachtet das Vorzeichen.

Schreibe die Messwerte eines Teils als Vektor $\mathbf{x} = (x_1, x_2)$ — Breite und Gewicht. Das Perceptron hält einen Gewichtsvektor $\mathbf{w} = (w_1, w_2)$ und einen Bias $b$. Sein Score ist

und seine Antwort ist das Vorzeichen dieses Scores: annehmen, wenn $s(\mathbf{x}) \geq 0$, andernfalls ablehnen.

Das ist das gesamte Modell. Alles, was das Perceptron je über die Fabrik wissen wird, steckt in drei Zahlen.

Bei der Geometrie lohnt sich ein kurzer Halt, denn sie ist das Bild, das auch in den nächsten neunundzwanzig Kapiteln weiterträgt, selbst wenn die Gleichungen nicht mehr in eine Zeile passen. Die Menge der Punkte, für die $s(\mathbf{x}) = 0$ gilt — wo das Perceptron genau unentschieden ist —, ist eine Gerade in der Ebene. Auf der einen Seite ist der Score positiv und alles wird angenommen; auf der anderen ist er negativ und alles wird abgelehnt. Lernen bedeutet für ein Perceptron, diese Gerade zu verschieben.

Zwei Fakten über diese Gerade folgen direkt aus der Algebra, und beide werden später wichtig:

• $\mathbf{w}$ steht senkrecht auf ihr. Der Gewichtsvektor liegt nicht entlang der Grenze, er zeigt quer über sie hinweg, zur angenommenen Seite.
• $b$ verschiebt sie, ohne sie zu drehen. Ohne Bias müsste die Gerade durch den Ursprung verlaufen, was für eine Fabrik, die Millimeter und Gramm misst, eine absurde Einschränkung wäre — es würde bedeuten, dass ein Teil mit null Breite und null Gewicht genau auf dem Zaun sitzt.

Das Perceptron startet ohne Wissen: $\mathbf{w} = (0, 0)$ und $b = 0$. Jeder Score ist null, also nimmt es alles an.

Nun zeigst du ihm ein Beispiel nach dem anderen. Markiere die angenommenen Teile mit $y = +1$ und die abgelehnten mit $y = -1$. Stelle für jedes Beispiel eine Frage: Kam das Vorzeichen richtig heraus? Die kompakte Schreibweise für diese Frage ist zu prüfen, ob $y \cdot s(\mathbf{x})$ positiv ist — wenn Label und Score im Vorzeichen übereinstimmen, ist ihr Produkt positiv, und wenn sie nicht übereinstimmen, ist es negativ.

Wenn die Antwort ja ist, ändere nichts. Wenn die Antwort nein ist, schubse:

Das ist der ganze Algorithmus, und es lohnt sich zu verstehen, warum genau das der richtige Schubs ist, statt ihn auswendig zu lernen. Angenommen, ein Teil hätte angenommen werden sollen ($y = +1$), und der Score fiel negativ aus. Wenn du $\mathbf{x}$ zu $\mathbf{w}$ addierst, ändert sich der Score für genau dieses Teil um

was eine positive Zahl ist. Der Score für das Teil, das es gerade falsch bewertet hat, geht nach oben, also in die Richtung, in die er gehen musste. Die Regel ist keine Heuristik, die jemand geraten hat; sie ist die kleinste Änderung, die den Fall vor ihr nachweislich verbessert. Natürlich kann sie einen anderen Fall kaputtmachen, weshalb du noch einmal herumgehst.

Achte darauf, was fehlt. Es gibt nirgendwo eine Ableitung. Das ist kein Versehen, und es ist die erste wirklich wichtige Idee in diesem Kurs.

Das, was du differenzieren wollen würdest, ist der Fehler — die Anzahl falsch klassifizierter Teile. Aber diese Anzahl ist eine Treppe: Sie bleibt flach bei 4, während du die Gerade anstupst, und fällt dann in dem Moment auf 3, in dem die Gerade einen Punkt überquert. Ihre Ableitung ist fast überall null und an den Stufen undefiniert. Analysis findet keinen Halt. Die Perceptron-Regel arbeitet darum herum, indem sie gar nicht nach einer Steigung fragt: Sie fragt nur „richtig oder falsch?“ und bewegt sich in eine Richtung, die sie geometrisch begründen kann.

Das ist eine echte Lösung, und es ist auch eine Sackgasse. In Kapitel 2 werden wir einen Loss wollen, der irgendwoher kommt, statt gewählt zu werden, in Kapitel 4 ein Modell, das angibt, wie sicher es ist, und in Kapitel 5 etwas mit mehr als einer Schicht — und keines davon ist von einer Regel erreichbar, die nur „falsch“ kennt. Eine brauchbare Steigung zurückzubekommen, ist das, was die nächsten zwei Kapitel erzwingt. Aber das Perceptron darf etwas tun, was keiner seiner Nachfolger kann: ganz ohne Analysis lernen.

Pures Python, kein NumPy. Listen und eine Schleife. NumPy kommt im nächsten Kapitel, wenn die Arithmetik nicht mehr in eine Schleife passt, die du lesen möchtest; es jetzt einzuführen, würde die Arithmetik genau in dem Moment hinter einer Library verstecken, in dem du sie sehen willst.

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

Die vier hervorgehobenen Zeilen sind der Algorithmus. Alles andere ist Buchhaltung.

Und das Förderband mit acht gemessenen Teilen — vier, die ausgeliefert wurden, und vier, die zurückkamen:

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

Diese acht Teile sind durch eine Gerade trennbar — jedes angenommene Teil ist unter 22 mm, und jedes abgelehnte ist 23 mm oder mehr. Ein vertikaler Zaun bei 22 Millimetern erledigt den Job. Also sollte das Perceptron ihn finden.

Führe es aus:

None [-142.1, -13.0] 54.0

Zweihundert Epochen, 454 Korrekturen, und es ist nicht konvergiert. Die Gewichte sind groß und haben das falsche Vorzeichen. Etwas stimmt nicht — außer, dass nichts falsch ist, und der Grund ist das Nützlichste in diesem Kapitel.

Das Perceptron hat eine Garantie, bewiesen von Novikoff im Jahr 1962.¹ Wenn sich die Daten überhaupt durch eine Gerade trennen lassen, macht der Algorithmus höchstens

Korrekturen, bevor er keine mehr macht — wobei $R$ der Radius der Daten ist, die Länge des längsten Beispielvektors, und $\gamma$ die Margin: der Abstand von der trennenden Hyperebene zum nächsten Punkt im augmentierten Raum, in dem der Bias eine dritte Koordinate ist. Deshalb verändert das Zentrieren der Daten diesen Wert, obwohl der Abstand in Millimetern es nicht tut.

Die Garantie ist bedingungslos, und sie erwähnt weder Epochen noch Lernraten noch Glück. Sie erwähnt aber auch nicht Zeit, und genau diese Auslassung ist der Punkt.

Setzen wir unsere Zahlen ein. Direkt aus den acht Teilen gemessen, mit dem Bias als konstanter Feature-Komponente hineingefaltet:

Das Theorem wurde nie verletzt. Lässt du die rohe Version lange genug laufen, konvergiert sie tatsächlich — in Epoche 11.976, nach 29.870 Korrekturen — bequem innerhalb ihrer Schranke von 2.633.550, und diese Lücke ist selbst der Punkt: Das Theorem begrenzt den schlimmsten Fall, nicht den typischen. Es brauchte einfach sechzigmal mehr Epochen, als irgendjemand aussitzen würde.

Die zweite Zeile sind dieselben acht Teile, dieselben zwanzig Zeilen Code, mit drei hinzugefügten Zeilen, die von jedem Messwert die mittlere Breite und das mittlere Gewicht abziehen. Das ist alles. Das ist die gesamte Änderung. Sie verschiebt die Punktwolke so, dass sie den Ursprung überdeckt, statt draußen bei (22, 57) zu schweben, und die Wirkung auf die Schranke ist ein Faktor von fünfzehntausend, weil sich beide Terme zugleich verbessern: $R$ fällt von 74 auf 13, weil die Punkte nicht mehr von einem weit entfernten Ursprung aus gemessen werden, und $\gamma$ steigt von 0,045 auf 0,989, weil die Margin gegen einen Gewichtsvektor gemessen wird, der keinen riesigen Bias mehr tragen muss, um die Daten zu erreichen.

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

Konvergiert in zwei Epochen, nachdem es sich genau einmal korrigiert hat.

Hier steckt eine echte Lektion, und sie lautet nicht „denk daran, deine Inputs zu normalisieren“, obwohl du das tun solltest. Sie lautet: Eine Garantie darüber, ob ein Algorithmus fertig wird, sagt dir nichts darüber, ob du noch dabei bist, wenn er fertig wird, und die Lücke zwischen beidem ist meistens Geometrie. Das ist das erste Auftauchen eines Musters, das dir in Kapitel 6 bei Initialisierung, in Kapitel 10 bei Lernratenplänen und in Kapitel 13 bei Quantisierung wiederbegegnen wird: Die Mathematik sagt, dass die Sache möglich ist, und das Engineering entscheidet, ob sie praktisch ist. Ein Kurs, der dir nur das Theorem beibringt, gibt dir ein Modell, das drei Tage trainiert, und gibt dir die Schuld.

Jetzt der Fehlschlag, der die erste Ära neuronaler Netze beendete, und er passt in vier Zeilen.

Vergiss die Fabrik. Nimm zwei Inputs, die jeweils entweder 0 oder 1 sind, und verlange, dass die Antwort $+1$ ist, wenn genau einer von ihnen 1 ist:

Das ist XOR — exklusives Oder. Bevor du weiterliest, zeichne die vier Punkte auf Papier: drei Ecken eines Einheitsquadrats und die vierte. Markiere die zwei diagonalen Ecken $(0,1)$ und $(1,0)$ als angenommen, und $(0,0)$ und $(1,1)$ als abgelehnt. Zeichne jetzt eine Gerade, bei der die zwei angenommenen Punkte auf einer Seite und die zwei abgelehnten Punkte auf der anderen liegen.

Das geht nicht. Nicht, weil es schwierig wäre oder du einen clevereren Algorithmus bräuchtest; sondern weil diese Gerade nicht existiert. Drei Zeilen Algebra zeigen, warum. Wenn ein Perceptron alle vier richtig hätte, dann ergeben die vier Zeilen der Reihe nach

Addiere die mittleren zwei Ungleichungen: $w_1 + w_2 + 2b \geq 0$, also $w_1 + w_2 \geq -2b$. Die letzte sagt $w_1 + w_2 < -b$. Zusammen: $-2b \leq w_1 + w_2 < -b$, was $-2b < -b$ erfordert, was $b > 0$ erfordert. Und die erste Ungleichung sagt $b < 0$. Ein solches $b$ gibt es nicht, also gibt es auch keine solchen Gewichte. Kein Perceptron, mit welchen Zahlen auch immer, klassifiziert XOR.

Führe es trotzdem aus, denn einem Algorithmus beim Scheitern zuzusehen ist mehr wert, als nur gesagt zu bekommen, dass er scheitern wird:

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

Es divergiert nicht, und es zappelt auch nicht in der Nähe einer brauchbaren Antwort herum. Es zyklisiert: Es läuft eine kurze Schleife durch den Gewichtsraum und kehrt für immer exakt dorthin zurück, wo es angefangen hat, mit zwei von vier richtigen Antworten — was du auch durch Raten bekämst. Hunderttausend Epochen und hundert sind nicht zu unterscheiden, weil der Algorithmus keinen Fortschritt macht, den ein längerer Lauf abschließen könnte. Vergleiche das mit dem Förderband, das bei 200 Epochen festgefahren aussah und tatsächlich auf eine echte Antwort zumaulte. Von außen sehen beide in den ersten Sekunden ähnlich aus. Sie ohne das Theorem auseinanderzuhalten, ist unmöglich — ein weiteres Argument dafür, das Theorem zu kennen.

1969 veröffentlichten Marvin Minsky und Seymour Papert Perceptrons, eine buchlange mathematische Untersuchung dessen, was genau dieses Modell darstellen kann und was nicht.² XOR ist ihr meistzitiertes Ergebnis, und das Zitat wird gewöhnlich als Vorwurf eingesetzt: Das Buch habe aus Rivalität oder Bosheit die Forschung an neuronalen Netzen für fünfzehn Jahre getötet.

Die Mathematik im Buch ist korrekt, und sie ist interessanter als das XOR-Beispiel. Minsky und Papert interessierten sich nicht in erster Linie dafür, ob ein einzelnes Perceptron XOR kann; sie interessierten sich dafür, was passiert, wenn Perceptrons begrenzte rezeptive Felder erhalten — jede Einheit sieht nur einen Teil des Inputs —, und sie bewiesen, dass bestimmte globale Eigenschaften eines Bildes, etwa ob eine Figur zusammenhängend ist, auf diese Weise nicht berechnet werden können, egal wie viele Einheiten du verwendest. Das ist ein wirklich tiefes Ergebnis über Lokalität, und es hat nichts mit der populären Geschichte zu tun.

Die populäre Geschichte liegt auch historisch falsch. Minsky und Papert diskutieren mehrschichtige Perceptrons ausdrücklich und sagen, dass die Frage ihrer Leistungsfähigkeit offen ist — sie vermuteten, eine Erweiterung der Theorie wäre „steril“, was eine Vorhersage ist, kein Beweis, und sie war falsch. Was 1969 fehlte, war nicht die Idee, Schichten zu stapeln; es war eine Methode, einen Stapel zu trainieren. Die Perceptron-Regel kann das nicht: Sie muss wissen, wie falsch jede Einheit liegt, und für eine Einheit, die in der Mitte vergraben ist, gibt es kein Label, mit dem man vergleichen könnte. Diese Lücke blieb offen, bis backpropagation 1986 populär gemacht wurde,³ und sie zu schließen ist das, was Kapitel 5 tut.

Die ehrliche Zusammenfassung lautet also so. Das Buch bewies eine echte Grenze eines echten Modells. Der Einbruch der Finanzierung des Feldes in den Siebzigern hatte viele Ursachen, darunter die überzogenen Versprechen, die Anfang der Sechziger für Perceptrons gemacht worden waren. Und das technische Hindernis war lösbar, aber niemand hatte das Werkzeug dafür.

Das Perceptron ist achtundsechzig Jahre alt, und du hast gerade eines geschrieben. Es lohnt sich, genau zu sein, welche Teile davon noch in der Maschine stecken, die du am Ende dieses Kurses gebaut haben wirst, denn die Antwort lautet: mehr, als du vermuten würdest.

Das Perceptron blieb an zwei Dingen zugleich hängen, und sie stellen sich als dasselbe heraus.

Es kann XOR nicht darstellen, weil eine Gerade nicht reicht. Das zu beheben bedeutet, Schichten zu stapeln — eine erste Schicht, die den Raum biegt, eine zweite, die im gebogenen Raum die Gerade zieht. Das ist Kapitel 5.

Aber du kannst einen Stapel nicht mit der Perceptron-Regel trainieren, weil sie nur „falsch“ kennt, und eine Einheit in der Mitte eines Netzes hat kein eigenes Label, über das sie falsch liegen könnte. Um einen Stapel zu trainieren, musst du für jedes Gewicht wissen, wie falsch es ist und in welche Richtung — du brauchst eine Steigung. Und die Fehlerfunktion des Perceptrons, die Treppe, hat keine.

Vor dem Stapel muss es also eine Loss-Funktion mit einer brauchbaren Ableitung geben. Auch keine, die nur gewählt wurde, weil sie bequem zu differenzieren ist: eine, die irgendwoher kommt, die etwas Wahres über die Daten sagt und deren gradient aus dieser Bedeutung herausfällt, statt rückwärts konstruiert zu werden, damit sie sauber aussieht.

Das ist Kapitel 2, und es beginnt mit einer Frage, die das Perceptron nie beantworten musste: nicht „ist dieses Teil gut?“, sondern „wie wahrscheinlich sind diese Messwerte, wenn dies die Wahrheit ist?“

Ebenfalls lesenswert neben diesem Kapitel: Rosenblatts Originalarbeit The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), die lesbarer ist, als ihr Ruf vermuten lässt; McCulloch und Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), der Aufsatz, der ein Neuron erstmals als Schwellenwert über einer gewichteten Summe modellierte; der Perceptron-Abschnitt in Hal Daumé III, A Course in Machine Learning, der dasselbe Update mit anderer Schwerpunktsetzung herleitet; und Kapitel 2 und 3 von Deisenroth, Faisal und Ong, Mathematics for Machine Learning, für die lineare Algebra, falls die Box oben dir weniger gegeben hat, als du wolltest.