Kompression \(=\) Abstraktion

Kompression \(=\) Abstraktion \(=\) KI?

Beispiel: Hausaufgabenbetrug

Die derzeitige Definition von KI

KI als Mode-Erscheinung in der Informatik

Das ist nicht die erste KI-Modewelle

Sachliche Grundlagen der KI

Was machen wir dann in dieser VL?

Organisatorisches

Bei-Spiele für Aufgaben der KI

Nim

Go

Aufgaben

  1. Emacs: M-x doctor.

    (M-x: gesprochen: Meta x, getippt: ESC (tippen, nicht halten) x)

    Wann, von wem, warum wurde die ursprüngliche Version dieses Programm geschrieben?

    Welche Einschätzung gibt der Autor selbst? Hinweis https://web.archive.org/web/20050826094312/http://www.gslis.utexas.edu/~palmquis/courses/reviews/amy.htm

    Finden und lesen Sie den Quelltext (tatsächlich benutzte Version unter /usr/share/emacs, Repository: https://git.savannah.gnu.org/cgit/emacs.git)

  2. Nim: geben Sie den vollständigen Spielbaum an (besser: Darstellung als DAG) für die Startpositionen (Multimengen) \(\{2,2\}\), \(\{1,2,3\}\).

    Wie kann der erste Spieler in \(\{2,3,4\}\) gewinnen? (Dazu braucht man nicht den kompletten Baum.)

  3. Gomoku

    • Ziel: 5 in einer Reihe (waagerecht, senkrecht, diagonal)

    • (Brett und Steine wie Go, aber sonst keine Beziehung)

    • Gewinnen Sie gegen M-x gomoku? Auch, wenn der Computer beginnt?

    • Diese KI verwendet keine Spielbaumsuche, sonder nur eine einfache Heuristik zur Stellungsbewertung.

      Suchen Sie diese im Quelltext.

    • Lösen Sie Diagramm 3b, Diagramm 4 aus: Allis et al.: Go-Moku and Threat Space Search, 1993

      https://www.mimuw.edu.pl/~awojna/SID/referaty/Go-Moku.pdf

  4. Go

    im Pool installiert sind:

    zur Benutzung: allgmein: PATH, LD_LIBRARY_PATH richtig setzen, vgl. https://www.imn.htwk-leipzig.de/~waldmann/etc/pool, speziell:

    • q5go: starten und in Preferences/Computer Go eintragen:

      • Name: gnugo, Executable: gnugo, Arguments: --mode gtp --level 12

      • Name: katago, Executable: katago, Arguments: gtp, use for analysis.

      Im Fenster q5goClient: File-Menu: Play with program,

      • Spielen Sie (Schwarz) gegen gnugo (Weiß), auf \(9\times 9\), mit Vorgaben (Handicap)

        Taktische Übungen:

        • fangen Sie irgendeinen Stein (eine Kette) des Gegners,

        • lassen Sie sich nicht fangen,

        • verhindern Sie, daß der Gegner lebt

        • bleiben Sie selbst am Leben

        • opfern Sie eigene Steine, um an anderer Stelle Gewinn zu machen

        Vorsicht: diese Ziele widersprechen sich. Solche lokalen taktischen Aufgaben sind nützlich als Bausteine einer globalen Strategie, um das eigentliche Spielziel (mehr Gebiet) zu erreichen.

        Vorsicht: zum Leben braucht man zwei Augen oder Seki, beim Spielen gibt es evtl. Ko.

        Diese Begriffe und ihre Anwendung folgen aus den Regeln, sind aber am Anfang nicht offensichtlich. Siehe Tutorial.

    • Computer vs. computer play: gnugo gegen katago. Vorgaben variieren.

    • Learn Go \(\Rightarrow\) Tutorials \(\Rightarrow\) Rules, Life and Death, Tactics

      Zeigen Sie eine Beispiel-Aufgabe mit einer Treppe (engl. ladder). Was bedeutet die Existenz von Treppen für die (automatisierte) Bewertung von Spielsituationen durch lokale Mustererkennung?

Ergänzung zu Spielen (VL KW 15)

Neutrale Spiele

Nim und Schiebe-Nim

Gomoku-Heuristik

Optimierung

Motivation, Beispiel, Plan

Naive lokale Suche (allgemein)

Naive lokale Suche (für Gomoku-Heuristik)

Richtungs-Suche (Gradienten-Abstieg)

Anw: Matrix-Interpretationen (Bsp)

Matrix-Interpretationen (Def, Aufgaben)

Matrix-Interpretationen (Lösungsverfahren)

Lösungsverfahren, Diskussion

autotool-Aufgabe zu Matrix-Interpretationen

Aufgaben

  1. Parameter für Gomoku-Heuristik:

    • Probieren Sie lokale Suche ohne Vorwissen (\(p_0=[0,0,0,0,0,0,0,0,0]\)),

    • lokale Suche zur Verbesserung einer bekannten guten Lösung.

    • Für die angegebene Bewertung mit \((S,-\sum Z_V, \sum Z_G)\): vorhersagen und ausprobieren, wie sich das Verhalten ändert, wenn Komponenten dieses Tripels vertauscht oder gelöscht werden.

    • Welches ist die beste Anzahl von Spielen je Bewertung? (mehr \(\Rightarrow\) genauer, aber langsamer)

    • Gefundene Parameter in autotool eingeben oder in Issue schreiben, dann Turnier unter diesen Heuristiken.

  2. Matrix-Interpretationen für Termination:

    • Geben Sie kompatible Interpretationen an für \(ab\to bba\), für \(aa\to aba\). (Andere Beispiele auf Folie sind schwieriger)

    • Lösen Sie \(ab\to bba\) mit Ansatz \(\begin{pmatrix}* & * \\ 0 & 1\end{pmatrix}\) durch Gradienten-Abstieg von einem gewürfelten oder geratenen Startwert aus.

    • desgleichen für \(aa\to aba\). Vorsicht: das geht nicht (man braucht Dimension 3). Wie sehen die Gradienten aus?

    Symbolisches Rechnen mit

    $ rlwrap maxima
(%i1) a:matrix([p,q],[0,1]);
                                   [ p  q ]
(%o1)                              [      ]
                                   [ 0  1 ]
(%i2) b:matrix([r,s],[0,1]);
                                   [ r  s ]
(%o2)                              [      ]
                                   [ 0  1 ]
(%i3) a.b - b.a;
                           [ 0  p s - s - q r + q ]
(%o3)                      [                      ]
                           [ 0          0         ]
(%i9)  subst([p=1+d,q=1,r=1,s=1],a.b - b.a);
                                   [ 0  d ]
(%o9)                              [      ]
                                   [ 0  0 ]

  3. Gradienten-Abstieg: bestimmen Sie ein Minimum der Funktion \(x^2+y^2\) durch Gradienten-Abstieg von \((x=1,y=2)\) aus.

    Desgl. für \((x^2-y^2+1)^2\) oder eine andere selbst gewählte oder gefundene Funktion.

    Probieren Sie jeweils verschiedene Schrittweiten.

    Funktionsgraphen (Flächen) ansehen (und drehen!) mit

    $ gnuplot
gnuplot> splot [-2:2][-2:2] (x*x-y*y+1)**2

  4. Damit wir das Go-Spiel nicht vergessen: unter der Annahme, daß die äußeren Gruppen leben: was ist der Status der 4 schwarzen und 5 weißen Steine innen?

    [6] (2,0),(2,1),(2,2),(2,3),(2,4) ,(3,4),(4,3),(5,3),(5,2),(5,1),(5,0) (3,0),(3,1),(3,2),(3,3) ,(4,4),(5,4),(6,4),(6,3),(6,2),(6,1),(6,0)

Symbolische Differentiation

Motivation, Plan, Ausblick

Algebraische Repräsentation von Funktionen

Tricks für kurze Quelltexte

Symbolisches Differenzieren

Anwendung: Gradienten-Abstieg

Äquivalenzen, Normalformen

Kanonische Repräsentationen

Sharing, DAGs, Schaltkreise

Aufgaben

  1. probieren Sie weitere Normalisierungs-Regeln. Testen Sie an Beispielen, ob Ableitungen von Funktionen damit vernünftig aussehen.

  2. Wenden Sie das Verfahren des Gradiententabstiegs an zum Finden von Matrix-Interpretationen.

    • eine reelle Unbekannte mit einseitig beschränktem Bereich (z.B. \(x\ge 1\)) kann dargestellt werden als eine Funktion einer unbeschränkten reellen Unbekannten (\(x = 1 + y^2\)).

    • eine Bedingung \(A\ge B\) (für Ausdrücke \(A, B\)) kann mit einer neuen unbeschränkten Unbekannten \(h\) dargestellt werden als Gleichung \(A = B + h^2\).

    • die Erfüllung eines Gleichungssystems \(A_i=B_i\) kann als Minimierungsaufgabe für \(\sum_i (A_i-B_i)^2\) dargestellt werden.

    Durch die angegebenen Umformungen steigen die Anzahl der Unbekannten und der Grad der Polynome. Beides erschwert die Arbeit des Verfahrens.

    Probieren Sie zunächst, nach diesem Verfahren ein einfaches lineares Gleichungssystem zu lösen (\(2x+3y = 1, x-y= 1\)), dann ein lineares Ungleichungssystem, dann eine quadratische Gleichung \((x^2+x=1)\).

Differentiation regulärer Ausdrücke

Motivation

Reguläre Ausdrücke

Ableitung eines Produktes

Ableitung eines Sterns

Ableitung nach einem Wort

Algorithmus von Brzozowski

Aufgaben

  1. Untersuchen Sie (an Beispielen), ob der von unserer Implementierung des Algorithmus von Brzozowski berechnete DFA minimal ist.

  2. Diskutieren Sie Normalisierungs-Regeln und normalisierte Repräsentation für Dot.

Neuronale Netze

Zusammenfassung

Geschichte, Quellen

Definition

Modellierung von NN

Spezielle Formen neuronaler Netze

Parameterbestimmung für NN

Verfahren zur Gradientenbestimmung

Automatische Differentiation (AD)

Stochastischer Gradientenabstieg

Diskussion (Beispiel)

Diskussion (allgemein)

Gary Marcus: Deep Learning: A Critical Appraisal, 2018,

https://arxiv.org/abs/1801.00631

The real problem lies in misunderstanding what deep learning is, and is not, good for. The technique excels

Deviations from these assumptions can cause problems. Deep learning is just a statistical technique. All statistical techniques suffer from deviation from their assumptions.

Aufgaben

  1. zu den Quelltexten zu NN und AD: Parameterbestimmung für Repräsentation unterschiedlicher Boolesche Funktionen verschiedener Stelligkeit durch unterschiedlicher Netz-Topologie und unterschiedlichen Optimierungsverfahren: ausprobieren und Beobachtungen diskutieren.

  2. speziell: welche Form paßt zu dreistelligem XOR? dreistelligem exactly 2? vierstellig?

  3. implementieren Sie AD für die Normalisierung durch \(x\mapsto \max(0,\min(x,1))\), vergleichen Sie dann das Verhalten (in o.g. Anwendungen) mit Normalisierung durch \(x\mapsto 1/(1+\exp(-x))\).

  4. die zweite Variante der stochastischen Einschränkung implementieren (in jedem Schritt einige Parameter fixieren)

  5. für die Funktion \(g:x\mapsto 1/(1+\exp(-x))\): beweisen Sie, daß \(g\) durch 0 und 1 beschränkt ist, streng monoton steigt, durch \((0,1/2)\) verläuft und in diesem Punkt drehsymmetrisch ist.

  6. unter der Annahme, daß die äußeren Gruppen leben: was ist der Status innen?

    [3] (2,0),(2,1),(2,2),(3,2),(4,2),(5,2) ,(6,1),(7,1),(7,0),(8,1),(9,1),(9,0) (3,0),(3,1),(4,1),(5,1),(5,0) ,(6,2),(7,2),(8,2),(9,2),(10,2),(10,1),(10,0)

Neuronale Netze: (kleine) Beispiele

Motivation

Ein Neuron

Xor mit zwei Neuronen

4-stelliges Xor

Darstellungen einstelliger Funktionen

Mustererkennung durch Faltung

Rekurrente Netze

Aufgaben

  1. ist die (zweistellige) Implikation durch ein Neuron beliebig genau darstellbar? Falls ja: geben Sie für jedes \(\epsilon>0\) Parameter an, so daß die Ausgabe für alle (4) Eingaben einen absoluten Fehler \(<\epsilon\) hat.

  2. Falls (abweichend von unserer Darstellung) für die Normalisierung die Funktion \(x\mapsto \max(0,x)\) verwendet wird: zeigen Sie, daß die auf der Folie Ein Neuron genannte Monotonie-Eigenschaft nicht gilt. Das \(\textsf{Xor}_2\) ist trotzdem nicht durch ein solches Neuron darstellbar. Beweisen Sie das durch eine geeignete Monotonie-Aussage.

  3. effiziente Darstellungen von \(\textsf{Xor}_k\) für \(k\ge 4\)

  4. Geben Sie ein gute Darstellung der einstelligen Funktion \(x\mapsto x^2\) auf dem Intervall \([0,1]\) an. Welchen Absolutfehler erreichen Sie bei vollem Netz mit \(1, 2, 3\) Neuronen? Verwenden Sie als Zielwerte \(2, 3, 5, 9, \dots\) gleichmäßige Stützstellen

  5. folgendes Netz erkennt die Menge der 5-stelligen Binärzahlen, die durch 3 teilbar sind, mit Fehler \(< 0.1\).

    \(n_1=\textsf{Norm}(5-6x_1+6x_2-6x_3+6x_4-6x_5)\), \(n_2=\textsf{Norm}(-13+5x_1-5x_2+5x_3-5x_4+5x_5+16n_1)\).

    Warum funktioniert das? (ein Beispiel, allgemein) Verallgemeinerung auf mehr Stellen? auf Teilbarkeit durch 5?

  6. das rekurrente Netz für den binären Nachfolger bauen

Programmatische Beschreibung von Netzen

Verbesserter Gradientenabstieg

Große (Tiefe) Neuronale Netze

Motivation, Plan, Quelle

Tensoren

Tensor-Operationen

Die voll verbundende Schicht

Die Faltungs-(Konvolutions-)Schicht

Anwendung: einfache Mustererkennung

Anwendung: AlphaGo Zero

Aufgaben

  1. zu Adam/Adamax: begründen Sie anhand des Pseudocodes aus der Quelle (Abschnitt 7.1, Algorithm 2) diese Behauptungen (aus 1. Introduction)

    • the method computes individual adaptive learning rates for different parameters

    • the magnitudes of parameter updates are invariant to rescaling of the gradient

    • it naturally performs a form of step size annealing.

    Ändern Sie die Parameter \(\alpha,\beta_1,\beta_2\) im Quelltext, beobachten und diskutieren Sie die Auswirkungen

  2. Beschreiben Sie die folgende Verarbeitung durch Tensor-Operationen. Geben Sie für jede Operation (Schicht) die Anzahl der Paramater an sowie die Abmessungen des resultierenden Tensors.

    • es liegen Meßdaten für ein Volumen \(30\times 20\times 10\) vor (z.B. Luftdruck oder Luftfeuchte in verschiedener geografischer Position und Höhe)

    • 3D-Faltung mit Kernel (\(3\times 3\times 3\))

    • eine voll verbundene Schicht reduziert auf zwei Dimensionen (Projektion entlang der Höhe)

    • 2D-Faltung mit Kernel \(5\times 4\)

    Geben Sie für einen Ausgabe-Wert der letzten Schicht an, von welchen originalen Eingabe-Daten und welchen Parametern er abhängt.

  3. durch eine 1D-Faltung mit Kernel \(K\) entsteht aus Vektor \(v:T\) ein Vektor \(v':T-K+1\).

    Geben Sie Matrix und Verschiebungsvektor einer dazu äquivalenten voll verbundene Schicht an.

    (konkretes Beispiel: \(T=4, K=2\))

  4. Für eine der Abbildungen aus Fleuret: LBDL: geben Sie die exakten Abmessungen der Tensoren an (mit konkreten Zahlen)

  5. Für AlphaGo Zero, Katago: geben Sie die exakte Netzwerkstruktur an. Verwenden Sie Beschreibung oder Quelltext.

  6. (Erweiterung von: Anwendung: einfache Mustererkennung, siehe Quelltext im Repo) Es sollen volle horizontale Linien erkannt werden. Die Trainingsdaten bestehen aus vollen horizontalen und vertikalen Linien, denen möglicherweise auch ein Pixel fehlt. Benutzen Sie ein Netz mit mehreren Faltungsschichten mit Kernel \(3\times 3\) sowie Maximum über die letzte Schicht. Wieviele Schichten sind nötig? Können alle Schichten (alle Kernel) die gleichen Parameter benutzen?

Monte-Carlo-Baumsuche

Inhalt, Motivation

Spielstärken-Bezeichnungen im Go

Klassische Spielbaumsuche

UCB: Exploration und Exploitation

Monte-Carlo-Baumsuche (MCTS) für Go

MCTS Beispiel-Implementierung

Alpha(Go)Zero: MCTS und CNN

Einzelheiten zu AlphaGoZero

Aktuelle Entwicklungen Computer-Go (2018)

Aktuelle Entwicklungen Computer-Go (2023)

Aufgaben

  1. Welches Komi, welche Zeit-Regelung werden in der Bundesliga verwendet? oder auf anderen aktuellen Turnieren?

    Was ist Byoyomi?

  2. bestimmen Sie die Rang-Differenz zwischen Katago, Gnugo und Ihnen selbst (wieviele Vorgaben führen zu 50% Gewinn) auf Brettgrößen 19, 13, 9.

  3. Zur genaueren Messung der Spielstärke dient das ELO-System. Wie ist die Spielstärke nach ELO spezifiziert? Wie ist die Änderung der ELO-Zahl (durch Resultate von Turnier-Spielen) implementiert? Welche (empirische) Korrelation besteht zu kyu/dan-Graden?

  4. die Netz-Struktur aus der Katago-Beschreibung im Quelltext wiedererkennen

  5. zu Quelltext ki-ss23/alpha0:

    • explizite Heuristik verbessern (Schätzung für Spielwert hinzufügen, ist derzeit immer 0)

    • Heuristik aus Emacs-Gomoku übernehmen (gewichtete Anzahl der einfarbigen Blöcke)

    • (Projekt) Heuristik durch NN realisieren, lernen.

Analyse von Audio-Signalen

Grundlegende Methode, Anwendungen

Signale, Spektrogramme

Spektral-Analyse (DFT)

DFT, FFT, Spektrogramm

Spektralzerlegung zur Kompression

Audio Fingerprinting

Musikalische Merkmale im Spektrogramm

NMF-basierte Signalzerlegung

Vergleich NMF und NN

Die multiplikative Schrittregel für NMF

Beispiele Audiosignalzerlegung mit NMF

Aufgaben

  1. probieren Sie (extrem) geringe Bitraten für Audio-Repräsentation mit ffmpeg

    (siehe manpage, Option -b:a 128k o.ä.)

    mit einer verlustfrei kodierten Datei beginnen (wav, flac)!

  2. NMF: Gradienten für \(S\in 2\times 2, K\in 2\times 1, G\in 1\times 2\) mit Computeralgebra-System nachrechnen

    $ rlwrap maxima
s:matrix([s11,s12],[s21,s22]);
k:matrix([k11],[k21]);
g:matrix([g11,g12]);
d:s-k.g;
t: (d[1,1]^2+d[1,2]^2+d[2,1]^2+d[2,2]^2);
expand(diff(t,k11));

  3. NMF: für \(S=\begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}\) (oder andere Zahlenwerte)

    mit Verfahren von Lee und Seung:

    Matrizen \(K\in 2\times 1, G\in 1\times 2\) bestimmen mit \(KG\approx S\).

    Beginnen mit \(K^{(0)}=\begin{pmatrix}1 \\ 1\end{pmatrix}\), \(G^{(0)}=\begin{pmatrix}1 & 1\end{pmatrix}\)

  4. für NMF mit Implementierung computer-mu/struct: den Testfall test2 ausführen und erklären

    $ cabal repl exe:audio-struct --allow-newer  -w /opt/ghc/ghc-9.2.7/bin/ghc
ghci> test2

    den Parameter rank ändern. Für welchen Rang ist Fehler 0 (also \(S=K\cdot G\)) für diese Testdaten erreichbar?

Text-Modellierung und -Generierung

Ergänzen/Vorhersagen von Folgen (Spezif.)

Ergänzen/Vorhersagen von Folgen (Impl.)

Folgen-Vorhersage durch Markov-Kette

Vektor-Semantik

Einbettung von Wörtern (in Vektoren)

Berechnung von Einbettungen

Aufgaben

  1. Implementierung markov: verschiedene Eingabetexte und Kontextbreiten ausprobieren.

    Die Behandlung des initialen Prompts diskutieren. (Wenn der Prompt kürzer ist als die abgespeicherten Kontexte: welche Verteilung erhält man für die direkt folgenden Zeichen? welche wäre sinnvoll?)

  2. Optimierungsverfahren für word-vec:

    1. Für das Verfahren der Vektor-Verschiebung: ein Beispiel mit \(r<0\) probieren (kleine Dimension). Eine allgemeine Aussage beweisen.

    2. bei Mikolov werden neuronale Netze verwendet. Vergleichen Sie. Was ist hierarchical softmax?

    3. verwenden Sie NNMF nach Lee and Seung, um eine Einbettung zu bestimmen.

  3. Implementierung word-vec:

    1. warum steht Dieser Satz schafft Abstand im Trainingstext?

    2. verschiedene Eingabetexte und Dimensionen ausprobieren. Werden ähnliche Wörter erkannt? Ähnliche Wortverhältnisse?

    3. im Programmtext wird eine Bibliothek für k-d-Bäume benutzt: zur Lösung welcher Teilaufgabe? Wieviel Platz/Zeit benötigt/gewinnt man gegenüber einer naiven Lösung?

Bausteine für bessere Implementierungen

Überblick, Motivation

Quellen

Eingabezerlegung (Tokenization)

Ausgabe-Repräsentation und -Verwendung

Transformer (Encoder/Decoder-Netze)

Attention (Baustein)

Attention (Zusammenbau)

Positions-Kodierung

Attention (Training, Erzeugung)

Interpretation des Transformer-Modells

Aufgaben Kompression (Bigramm-Kodierung)

  1. Bigramm-Kodierung für Texte unterschiedlicher Sprachen (verwende z.B. https://gutenberg.org/)

    Bsp. Norwegisch, Finnisch, Estnisch, Isländisch, Esperanto

    welches sind häufige subword token? welche davon sind text-spezifisch, welche sprach-spezifisch?

    Vergleichen Sie häufige Bigramme/Teilwörter aus Übersetzungen des gleichen Urtextes in verschiedene Sprachen

  2. Def: Größe einer (singleton) CFG \(G=(\Sigma,V,S,R)\) (nur für diese Aufgabe) \(|G|:=\sum \{(|r|: (l\to r)\in R\}\) (Summe der Längen der rechten Seiten)

    Bsp: \(G_1=(\{0,1\},\{S,T\},\{S\to TT0T, T\to 01\})\), \(\operatorname{\textsf{Lang}}(G_1)=\{0101001\}\), \(|G_1|=4+2=6\), ist besser als die triviale \(G_0=(\{0,1\},\{S\},\{(S\to 0101001)\})\) mit \(\operatorname{\textsf{Lang}}(G_0)=\{0101001\}\) und \(|G_0|=7\).

    Finden Sie eine gute Kompression für \([0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,0]\)

    Zeigen Sie an einem Beispiel, daß der Greedy-Algorithmus (immer ein häufigstes Paar kodieren) nicht optimal ist.

    Läßt sich der Approximationsfehler beschränken?

    vgl. Bannai et al. The smallest grammar problem revisited, SPIRE 2016, https://arxiv.org/abs/1908.06428

Aufgaben Transformer

  1. Anzahl der Parameter einers Transformers diskutieren (abhängig von Anzahl Schichten, Köpfen usw.)

  2. Auswirkung des Temperatur-Parameters für Ausgabe, für innere Schichten beobachten.

    In der Literatur werden die Skalarprodukte (Query \(\times\) Key) normiert (Division durch \(\sqrt d\)), vergleiche mit Temperatur des Softmax

  3. Code ergänzen/Zweck diskutieren:

    • Positions-Kodierung (von links, von rechts, gelernt/fixiert)

    • Schicht-Normalisierung (auf Mittelwert 0, Varianz 1)

    • Beam-Suche

  4. Diskutiere die Beobachtung the location of the LayerNorm in this figure remains a hotly debated subject aus Sebastian Raschka: About LayerNorm Variants in the Original Transformer Paper, … https://magazine.sebastianraschka.com/p/why-the-original-transformer-figure

  5. Thesen aus Elhage et al. an einfachen Beispielen überprüfen.

  6. Schmidhuber et al. Linear Transformers Are Secretly Fast Weight Programmers https://arxiv.org/abs/2102.11174

  7. (Forschungsaufgabe) welche (formalen) Sprachen kann man mit Transformer/Attention (Ausgabe ist eine Zahl: Wsk für \(w\in L\)) exakt darstellen? Darunter nicht reguläre? nicht kontextfreie? Welches ist das dazu passende (exakte) Maschinennmodell? Welche Rolle spielen dabei: die Anzahl der Köpfe? der Schichten? Kann man die darstellbaren Sprachen tatsächlich auch (asymptotisch) exakt lernen?

  8. (Forschung) LSTM ist als mapAccumL darstellbar?

  9. (Forschung) Transformer für Bäume (anstatt Folgen)

Einschätzung, Ausblick

Struktur (tief) oder nicht (flach)

Beispiel: Presburger-Arithmetik (PA)

PA — Entscheidungsverfahren

PA: Addition, Gleichheit

PA: aussagenlogische Operationen

PA: Quantifikation

PA: eine konkrete Implementierung

PA: kleine Formel, große Modelle

Kann eine generative KI die Presburger-Arithmetik erfinden?

Die tatsächliche Qualität der Trainingsdaten

Auswirkungen der generativen KI