Mein Python-Code ist ein neuronales Netz

 (blog.gabornyeki.com)
2 Punkte von GN⁺ 2024-07-02 | 1 Kommentare | Auf WhatsApp teilen
  • Programme zur Extraktion mehrdeutiger Informationen werden leicht zu Spaghetti-Code, je mehr Ausnahmeregeln sich ansammeln, und eine solche zustandsbasierte Logik lässt sich als rekurrentes neuronales Netz (RNN) neu denken
  • Das Beispiel, in Code-Review-Nachrichten C-Code-Referenzen zu finden, wird als handgeschriebener Klassifikator implementiert, der Token-Muster wie identifier–open_paren–close_paren als Zustände verfolgt
  • Diese Regel zeigt im Beispiel 100 % Präzision, übersieht aber Fälle wie if (err) goto cleanup;, sodass der Recall bei 50 % bleibt; mit jeder zusätzlichen Regel werden State und Verzweigungen komplexer
  • Dieselbe Zustandsmaschine lässt sich in verborgene Zustände und Schichtberechnungen eines RNN kodieren; damit sie lernfähig wird, braucht es statt binärer Indikatorfunktionen ReLU bzw. Sigmoid sowie lernbare Gewichte und Biases
  • Implementierungen in PyTorch wie Elman-RNN, GRU und LSTM sowie das Problem des verschwindenden Gradienten bei langen Token-Sequenzen begrenzen das tatsächliche Training; schon der Prozess, Datensätze, Labels und Verlustfunktion festzulegen, hilft aber auch beim Entwurf handgeschriebener Regeln

Wie mehrdeutige Datenextraktion zu Spaghetti-Code wird

  • Forschungsprogramme, die Informationen aus Rohdaten extrahieren, werden schnell komplex, wenn die Daten keiner klaren Spezifikation folgen oder ungewöhnliche Formen haben
  • Beispielaufgaben sind das Identifizieren von Unternehmen und Führungskräften in Nachrichtenartikeln, das Labeln öffentlicher Beschaffungsverträge nach Dienstleistungsart und die Entscheidung, ob eine Nachricht von Ingenieuren Programmcode enthält
  • Wenn man perfekte Ausgaben will, kann man jede Beobachtung sorgfältig prüfen und Unit-Tests für repräsentative Fälle schreiben
    • Sowohl R als auch Python bieten dafür Testbibliotheken
  • In Situationen, die komplexe Entscheidungsregeln erfordern, etwa bei Spitznamen, Synonymen oder der Grenze zwischen Englisch und Code, geraten handgeschriebene Regeln leicht ins Wanken
  • Lernalgorithmen für neuronale Netze verwandeln das Problem, statt dass Menschen diese Regelkombinationen ständig nachpflegen, in eine Suche in den Daten

Code-Referenzen in Code-Review-Nachrichten finden

  • Das Ziel ist zu erkennen, ob eine während eines Code-Reviews gesendete Nachricht Programmcode explizit referenziert
  • Es wird angenommen, dass die beobachtete Codebasis in C geschrieben ist
  • Repräsentative Nachrichten enthalten Code-Referenzen wie die folgenden
    • render_ipa_alloc()
    • FTPSACK
    • debug_error()
    • NULL
    • IS_ERROR()
    • aarch64, amd64
    • if (err) goto cleanup;
  • Einfache Regelkandidaten scheitern jeweils auf unterschiedliche Weise
    • Die Regel, ein Wort mit nachfolgender Klammer als Code zu behandeln, erfasst Fälle wie render_ipa_alloc(), übersieht aber if (err) goto cleanup;
    • Die Regel, vollständig großgeschriebene Wörter als Code zu behandeln, erfasst FTPSACK und IS_ERROR(), produziert aber Fehlalarme bei Abkürzungen wie AFAICT
    • Die Regel, nicht-englische Wörter als Code zu behandeln, kann auch Engineering-Begriffe oder Architekturnamen fälschlich als Code markieren
  • Um Regel 2 und Regel 3 zu verbessern, braucht man Listen mit Abkürzungen und Fachbegriffen wie AFAICT, LGTM, USD, COVID, aarch64, amd64

Ein Klassifikator als handgeschriebene Zustandsmaschine

  • Ein einfacher Algorithmus entscheidet in zwei Schritten, ob eine Nachricht Code enthält
    • Vorverarbeitung: Die Nachricht wird in eine Token-Sequenz umgewandelt, die die Syntaxelemente von C-Code widerspiegelt
    • Inferenz: Es wird geprüft, ob die Token-Sequenz die Regeln erfüllt
  • Regel 1 bewertet das Muster underscore_identifier–open_paren–close_paren als Code-Referenz
  • Die Python-Implementierung speichert den Zustand des vorherigen Tokens in einer State-Datenklasse
    • previous_was_identifier
    • previous_was_open_paren
    • previous_previous_was_identifier
    • seen_code
  • contains_code läuft die Tokens durch, ruft dabei process auf und gibt am Ende state.seen_code zurück
  • process setzt seen_code auf True, wenn das aktuelle Token close_paren ist, das vorherige open_paren und das davor ein Bezeichner
  • Dieser Klassifikator erzeugt im Beispiel keine Fehlalarme und erreicht 100 % Präzision, übersieht aber viele Fälle, sodass der Recall bei 50 % bleibt
  • Fügt man Regel 2 hinzu, nehmen die Felder in State und die if/elif/else-Verzweigungen zu, und je weiter die Regeln verfeinert werden, desto schwieriger wird die Wartung

Die Zustandsmaschine in ein RNN überführen

  • contains_code und process sind eine Zustandsmaschine, und eine Zustandsmaschine lässt sich als rekurrentes neuronales Netz (RNN) kodieren
  • Ein RNN verarbeitet Token-Sequenzen nacheinander und approximiert die bedingte Wahrscheinlichkeit, dass eine Nachricht Code enthält
  • Die Werte, die in Python dem State entsprechen, werden als verborgener Zustand des RNN dargestellt
    • State_0 ist der Anfangszustand
    • Jeder State_t wird berechnet, indem das aktuelle Token und der vorherige Zustand in eine Funktion f gegeben werden
    • Der Endzustand wird durch eine Ausgabeschicht g zum Klassifikationsergebnis
  • Das Beispiel-RNN verwendet drei verborgene Schichten
    • Die erste Schicht speichert oder kopiert das aktuelle Token und den vorherigen Zustand
    • Die zweite Schicht prüft das Muster, das Regel 1 entspricht
    • Die dritte Schicht merkt sich, ob schon einmal ein Code-Muster gesehen wurde
  • Tokens werden als binäre Vektoren in One-Hot-Darstellung repräsentiert
  • Um den handgeschriebenen Algorithmus direkt nachzuahmen, kann man die binäre Indikatorfunktion 1{x > 0} verwenden
    • Die verborgenen Schichten können als Binärwerte erhalten bleiben
    • Da die Ableitung aber fast überall 0 ist, ist sie zum Lernen ungeeignet
  • Man könnte das Muster auch als Produkt von identifier, open_paren und close_paren prüfen, aber in binären verborgenen Schichten lässt sich dieselbe Prüfung auch als Summe ausdrücken
  • Giles et al. (1992) knüpft daran an als Beispiel für den Einsatz von second-order RNNs zur Entdeckung von Zustandsmaschinen

In ein lernfähiges Netzwerk umwandeln

  • Zum Lernen verwendet man statt der binären Indikatorfunktion ReLU
  • Numerische Konstanten werden durch Gewichte und Biases ersetzt, und Gradientenabstieg schätzt diese Parameter
  • Die Ausgabeschicht berechnet mit der Sigmoid-Aktivierungsfunktion den endgültigen Wahrscheinlichkeitswert
  • Diese Form lässt sich in PyTorch einspeisen und trainieren, aber das Training liefert in dieser Form keine herausragende Leistung
  • Ein Grund für die schwächere Leistung ist, dass die Architektur nicht allgemein üblich ist und daher ein größerer Teil des Trainingsablaufs im Python-Verkettungscode läuft und die C++-Bibliotheksimplementierungen von PyTorch weniger genutzt werden

PyTorch-Implementierung und Grenzen langer Nachrichten

  • torch.nn.RNN in PyTorch bietet eine Implementierung auf Basis des Elman-RNN
  • Die Beispielarchitektur und das Elman-RNN unterscheiden sich in der Art der Verbindungen zwischen den verborgenen Schichten
    • In der Beispielarchitektur erhält die erste Schicht von Token t die dritte Schicht von Token t-1 als Eingabe, und jede Schicht erhält nur die direkt vorherige Schicht als Eingabe
    • Im Elman-RNN erhält jede verborgene Schicht auch den Zustand derselben Schicht aus dem vorherigen Zeitschritt als Eingabe
    • Die erste verborgene Schicht des Elman-RNN erhält nicht die Endschicht des vorherigen Zeitschritts als Eingabe
  • Echte Code-Review-Nachrichten können lang sein, und lange Nachrichten führen zu langen Token-Sequenzen
  • In langen Sequenzen kann es selbst dann, wenn Gradientenabstieg theoretisch funktioniert, wegen des verschwindenden Gradienten zu Problemen mit der numerischen Stabilität kommen
  • Auch Elman-RNNs können dafür anfällig sein, und GRU oder LSTM könnten bei der Aufgabe der Code-Erkennung besser funktionieren

Datenbasierte Disziplin

  • RNNs machen aus Regelkombinationen, die sich von Hand schwer beherrschen lassen, ein Lernproblem und zwingen dazu, die Problemdefinition klarer zu formulieren
  • Um ein Netzwerk zu trainieren, braucht man Folgendes
    • Auswahl eines Trainingsdatensatzes und eines Validierungsdatensatzes
    • Vorab-Labeling
    • Eine Verlustfunktion, die explizit festlegt, was der Klassifikator erreichen und vermeiden soll
  • Dieser Prozess macht unerwartete Grauzonen sichtbar und schärft die Entscheidungskriterien
  • Diese datenbasierte Disziplin ist nicht nur bei neuronalen Netzen nützlich, sondern auch bei Problemen, die mit handgeschriebenen Algorithmen gelöst werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-02
Hacker-News-Kommentare

  • Der Artikel behandelt Tests oder die Beschaffung von Trainingsdaten kaum, dabei scheint genau das der Kernpunkt zu sein
    Code, den man zu verstehen glaubt, hat man zumindest informell für sich selbst deshalb „bewiesen“, weil er auf alle Eingaben generalisiert. Ein Sortieralgorithmus sortiert zum Beispiel nicht nur die getesteten Listen, sondern jede Liste
    Das Unsichere bei neuronalen Netzen ist, dass man nicht weiß, wie sie generalisieren werden. Schon wenn sich ungesehene Eingaben nur leicht unterscheiden, gibt es keine garantierten Eigenschaften, und möglicherweise ist es von vornherein ein Problem, bei dem sich die gewünschten Eigenschaften nur schwer mathematisch spezifizieren lassen
    Wenn sich eine Eigenschaft klar genug definieren lässt, um sie als eigenschaftsbasierten Test wie mit QuickCheck zu formulieren, kann man durch Zufallsgenerierung große Mengen an Tests oder Trainingsdaten erzeugen. Man kann mit einem gewünschten Beispiel anfangen und Tests schreiben, die mögliche Variationen positiver und negativer Beispiele erzeugen
    Das ist kein Beweis, aber ein Ausgangspunkt. Wenn man es überhaupt beweisen kann, weiß man zumindest, was bewiesen werden müsste
    Wenn so etwas möglich ist, wirkt es ziemlich ähnlich, ob man sich auf Spaghetti-Code oder auf ein neuronales Netz verlässt. Wenn man weitere Eigenschaften erfüllen will, schreibt man einfach noch einen eigenschaftsbasierten Test dazu. Ein neuronales Netz ließe sich statt direkter Änderungen trainieren, aber auch zum Ändern von Code gibt es KI-Unterstützung
    Trotzdem würde ich Code eher vertrauen. Zumindest kann man ihn debuggen

  • Als Beschreibung dafür, wie man ein neuronales Netz baut, das praktische Aufgaben erledigt, ist das ein interessanter Artikel. Wenn man diesem Ansatz aber beim nächsten Parsen von Eingaben direkt folgen wollte, wüsste ich ehrlich gesagt nicht, was ich dazu sagen soll
    Der Autor nimmt das schwierige Problem des Parsens beliebiger Eingaben mit locker definierten Mustern und sagt zu Recht, dass das wahrscheinlich schwer lesbaren Spaghetti-Code erzeugt
    Als Alternative schlägt er dann aber Code vor, der so schwer lesbar ist, dass man noch immer erforscht, wie er überhaupt funktioniert: ein neuronales Netz
    Ich kann das nachvollziehen, aber man sollte etwas völlig Uninterpretierbares nicht überbewerten, nur weil es weniger „hässlich“ ist. Für manche Aufgaben mag ein Machine-Learning-Modell passend sein, aber in vielen Fällen ist etwas, das man mit Mühe lesen und darauf prüfen kann, warum es so funktioniert, besser als etwas Unverständliches

    • Ich finde, dass der Autor mit Spaghetti-Code eher vom eigentlichen Punkt ablenkt. Wenn die Ausgabe eines Algorithmus nicht als Funktion der Eingabe exakt definiert ist, man aber Beispiele zeigen kann, dann ist genau das ein Fall, in dem Machine Learning nützlich ist
      Letztlich bietet Machine Learning nur eine weitere Option. Ob sie passt, hängt von den Evaluationsergebnissen und vom Maß an Determinismus und Erklärbarkeit ab, das der gewählte Algorithmus braucht
      Auffällig ist eher die Frage, ob RNNs hier die richtige Wahl sind. Dafür ist Training nötig, und womöglich braucht man viel mehr Beispiele als vorhanden. Allerdings könnte man auf Basis bekannter Regeln synthetische Daten mit positiven und negativen Fällen erzeugen
    • Der Spaghetti-Code-Ansatz ist im Grunde ein Expertensystem. Man könnte ihn als altmodische algorithmische KI sehen. Außerhalb begrenzter Domänen haben solche Systeme nie besonders gut funktioniert, und die Realität ist einfach zu unordentlich
      Ein System, bei dem man sehen kann, warum es so arbeitet, ist schön, aber wenn es ständig falsche Antworten liefert, bringt das wenig. Im praktischen Einsatz ist es oft wichtiger, die richtige Antwort zu bekommen, als zu wissen, wie sie zustande kam
    • Das klingt, als wolle man hässlichen Spaghetti-Code einfach hinter einer sauberen 1000x1000-Gleitkomma-Matrix verstecken

  • Für neuronale Netze gibt es das Universal Approximation Theorem. Es besagt, dass man eine beliebige Funktion bis zu einem gewünschten Genauigkeitsniveau darstellen oder encodieren kann[0]
    Es gibt aber keinen Satz darüber, dass man eine solche Approximation auch lernen kann oder wie man sie lernt
    [0] https://en.m.wikipedia.org/wiki/Universal_approximation_theo...

    • Dieser Beweis wird oft angeführt, aber was er tatsächlich zeigt, ist eher, dass neuronale Netze einer Lookup-Tabelle entsprechen. Eine Lookup-Tabelle mit genügend Speicher kann jede Funktion approximieren
      Das ist weit davon entfernt zu erklären, wie realistische und nützliche neuronale Netze wie Convolutional Neural Networks, Transformer oder LSTMs tatsächlich funktionieren
    • Nebenbei bemerkt gibt es viele Algorithmen, bei denen schon lange vor neuronalen Netzen bewiesen wurde, dass sie universelle Funktionsapproximatoren sind. Neuronale Netze sind weder die einzigen noch die ersten. In vielen Fällen gibt es durchaus Verfahren, die viel besser geeignet sind als neuronale Netze
    • Es geht nicht um wirklich beliebige Funktionen. Für die Funktionstypen, auf die das Universal Approximation Theorem anwendbar ist, gibt es Einschränkungen
      Interessanterweise betrifft dieser Satz Netzwerke mit nur einer Schicht. In der Praxis funktionieren mehrere Schichten jedoch deutlich besser
    • Man kann nur stetige Funktionen modellieren, genauer gesagt lässt sich jede stetige Funktion auf einer kompakten Teilmenge von ℝⁿ mit genügend Neuronen auf beliebige Genauigkeit approximieren
    • Dann fragt man sich, was „Lernen“ eigentlich bedeutet

  • Wirklich ein großartiger Artikel, und auch wenn ich die tieferen mathematischen Konzepte rund um RNNs nicht vollständig verstanden habe, bringt er viele Gedanken in Gang
    Das fühlt sich ähnlich an wie etwas, das ich in letzter Zeit erforsche: Apps in Verbindung mit einem Forward-Chaining-Algorithmus zu bauen. Der Autor verwendet RNNs, ich baue gerade etwas mit dem Rete-Algorithmus
    Ich halte auch die Idee für stark, Eingabestrings Zeichen für Zeichen zu verarbeiten. Dann überlässt man die Inferenzlogik dem Algorithmus, und wir schreiben nur eine sehr dünne Ein-/Ausgabelogik, während der Rest vom Algorithmus erledigt wird

  • Das Gute an diesem Artikel ist, dass er über Lernerfahrungen vermittelt, was es in der Praxis wirklich bedeutet, eine Funktion in ein RNN umzusetzen, und das mit den in PyTorch enthaltenen „batteries included“-RNNs vergleicht
    Die Frage ist: Es heißt, um den Zustand zu modellieren, müsse man dem Netzwerk drei verborgene Schichten hinzufügen — warum gerade drei? Ist das eine Folge der konkret umzusetzenden Regeln, oder ist das allgemein die übliche Schichtzahl, wenn man solche Regeln mit dieser Architektur implementiert? Und wäre es mit einer Elman-Architektur vielleicht auch mit weniger Schichten gegangen?

    • Zur ersten Frage: Mit drei verborgenen Schichten wird etwas klarer, was das Netzwerk jeweils tut. Jede Schicht übernimmt einen Schritt der Berechnung
      Die erste Schicht sammelt, was man aus dem aktuellen Token erkennen kann, und was nach der Berechnung des vorherigen Tokens bekannt war. Die zweite Schicht prüft, ob die Entscheidungsregeln erfüllt sind, und beurteilt, ob das aktuelle Token wie Programmcode aussieht. Die dritte Schicht vergleicht diese Entscheidung mit den Entscheidungen zu den vorherigen Tokens
      Das ließe sich vermutlich auch in eine einzelne verborgene Schicht komprimieren. ReLU scheint ausreichend zu sein, um die Nichtlinearität abzubilden. Zur Entsprechung mit der Elman-Architektur habe ich mir das noch nicht genau genug angesehen, um darauf eine Antwort zu haben

  • Ist RNN vollständig im Transformer aufgegangen? Ich frage mich, ob man vergessen kann, wie man mit RNNs arbeitet, und sich nur noch auf Transformer konzentrieren sollte

    • Um diese Frage noch komplizierter zu machen: Das Paper „Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention“ ist einen Blick wert – https://arxiv.org/pdf/2006.16236
      Dort wird gezeigt, dass eine bestimmte enge Definition von Transformern, nämlich Transformer mit kausalem Masking, zu RNNs äquivalent ist und umgekehrt
      Ähnlich hat auch Mamba(https://arxiv.org/abs/2312.00752), eine aktuell viel diskutierte Architektur, Einheiten, die zu RNNs mit Gating äquivalent sind. Soweit ich weiß, wird aus Leistungsgründen beim Training ein äquivalentes CNN und bei der Inferenz ein RNN verwendet
    • Transformer haben endlichen Kontext, RNNs dagegen nicht. In der Praxis ist das Gradientensignal von RNNs wegen Backpropagation Through Time jedoch begrenzt und schwächt sich ab
      Das ist tatsächlich der Hauptvorteil von Transformern. Beziehungen über kurze und große Distanzen sind nicht unterschiedlich schwer oder leicht. Theoretisch kann sich ein RNN aber an eine unendlich weit zurückliegende Vergangenheit erinnern
    • Wenn du ML-PhD oder Forscher werden willst, nein; ansonsten ja
      Ich habe in den letzten 7 Jahren als Research Engineer mit Machine Learning/LLMs gearbeitet und auch in einem FAANG-Forschungslabor, aber obwohl ich immer dachte, ich sollte RNNs lernen, habe ich es nie tatsächlich gelernt und auch nie gebraucht

  • Wenn dich das interessiert, lohnt sich ein Blick auf genetische Programmierung. Ich halte das für einen einfacheren Ansatz für dasselbe Problem, und man braucht keine Mathematik dafür
    Dabei werden Programme anhand ihres abstrakten Syntaxbaums rekombiniert, und mit einer geeigneten Heuristik werden Programme nach diesem Kriterium optimiert. Die Magie steckt in der Heuristikfunktion: Man kann Geschwindigkeit, Programmlänge, die Minimierung komplexer Strukturen oder Funktionsaufrufe, Netzwerkeffizienz oder eine Kombination davon als Optimierungsziel wählen
    https://youtu.be/tTMpKrKkYXo

    • Ich möchte auch die Humies Awards ergänzen, die Resultate auf menschlichem Wettbewerbsniveau zeigen. Schon das grobe Durchsehen der eingereichten Arbeiten lehrt einen viel darüber, was in diesem Bereich möglich und unmöglich ist
      https://www.human-competitive.org/

  • Ich habe kürzlich einen Blogbeitrag geschrieben, in dem ich die Idee untersucht habe, für solche vagen Aufgaben mit einem lokalen LLM zu interagieren
    Das erscheint mir sinnvoller, als ein neuronales Netz direkt zu programmieren. Praktischer wirkt es, mit etwas wie llama.cpp zu testen, ob ein kleines Modell das Problem direkt lösen kann, und wenn nicht, es feinzujustieren und dann mit dem gewünschten Wrapper programmatisch an llama.cpp anzubinden

  • Rekurrente neuronale Netze können für beliebige Berechnungen verwendet werden, und ihre Äquivalenz zu Turing-Maschinen ist auch bewiesen. Für diese Aufgabe ist das aber völlig unrealistisch
    Der Ansatz in diesem Beitrag wirkt irgendwie wie eine gelernte Zustandsmaschine. Der Beitrag könnte von einer längeren Zusammenfassung profitieren, und „Python“ scheint überhaupt nicht relevant zu sein. Echte Python-Semantik zu lernen wäre wegen der Eigenschaften der Sprache ziemlich schwierig. Es gibt keinen Standard; die Sprache ist im Grunde das, was CPython tut

    • Karpathys RNN-Beitrag von 2015[1] zeigte, dass ein zeichenweise auf Shakespeare trainiertes RNN Text im Shakespeare-Stil erzeugen kann, auch wenn ihm die erzählerische Kohärenz eines LLM fehlt
      Warum sollte es dann nicht auch formale natürliche Sprache wie Code-Review-Kommentare verarbeiten können?
      In diesem Fall wurde die Inferenz mit zufälliger Eingabe ausgeführt, um zufälligen „Shakespeare“ zu erzeugen, aber die Sprachstruktur und der Stil wurden trotzdem vom RNN gelernt. Vielleicht könnte man es auch zur Klassifikation verwenden
      1. https://karpathy.github.io/2015/05/21/rnn-effectiveness/

  • Man muss Python zuerst in ein neuronales Netz kompilieren und es dann auf ein Transformer-basiertes neuronales Netz zurechtbiegen
    Dann kann die Transformer Virtual Machine (TVM) beliebige Programme ausführen
    Mit Transfer Learning, also indem man Gewichte übereinanderlegt, könnte ein LLM „geboren“ werden, das Algorithmen tief eingebettet mitbringt