Professur für
Theoretische Informatik

• Veranstaltungen im SoSe 20
• Komplexitätstheorie
• Seminar Algorithmen und Komplexität
• Veranstaltungen im WS 19/20
• Diskrete Modellierung
• Seminar Algorithmen und Komplexität
• Veranstaltungskatalog
• Approximationsalgorithmen
• Comp. Learning Theory
• Datenstrukturen
• Diskrete Modellierung
• Effiziente Algorithmen
• Internet Algorithmen
• Komplexitätstheorie
• Parallel and Distributed Algorithms
• Theoretische Informatik 1
• Theoretische Informatik 2
• Organisatorisches
• Mündliche Prüfung
• Abschlussarbeiten

Logbuch "Computational Learning Theory" (SoSe18)

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.

• Di, 10.07.2018

  Connectionist Temporal Classification (CTC) (die Loss-Funktion, die Netzarchitektur, Durchführung des stochastischen Gradientenabstiegs); Berechnung der Wahrscheinlichkeit p_w(y|x); Bestimmung der partiellen Ableitung von p_w(y|x); Bestimmung einer guten Transkription (BeamSearch);
  RNN-Transducer (akustisches Netz, linguistisches Netz, Loss-Funktion -ln p_v,w^*(y|x), Definition von p_v,w^*(y|x) durch die Wahrscheinlichkeit von Wegen auf einem Gitter); Baidu: Deep Speech 2
  Neural Machine Translation (Encoder, Decoder, Aufmerksamkeitsmodell); GNMT

  Material:
  • Vortragsfolien:
    • Neuronale Netzwerke (Seite 119-140) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 12.4.2 und 12.4.3
• Mo, 09.07.2018

  Das ASR-System von Google Home (Akustisches Modell (Grid-LSTM, Dimensionsreduktion, Verarbeitung durch weitere vollständig verknüpfte LSTMs), Aussprachenmodell, Sprachenmodell), CTC (Connectionist Temporal Classification: die Unabhängigkeitsannahme, die von Netz_w bestimmte Wahrscheinlichkeit p_w(y|x) einer Transkription y für eine gegebene Eingabe x)

  Material:
  • Vortragsfolien:
    • Neuronale Netzwerke (Seite 105-118) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 12.4.2.2 und 12.4.2.3
• Di, 03.07.2018

  visuelle Objekterkennung (ResNet), Automatic Speech Recognition (ASR), die Schritte eines traditionellen ASR-Systems: vom Audiosignal zu Fourier-Koeffizienten, ein akustisches Modell, ein Aussprachemodell, ein Sprachmodell (Trigramme), Word-Error-Rate (Levenshtein-Distanz),

  das Problem explodierender bzw. verschwindender Gradienten, LSTM-Blöcke als eine Datenstruktur für die Erinnerung (Input-, Forget-, Speicher-, Output-Gatter, Truncated Backpropagation), GRUs

  Material:
  • Vortragsfolien:
    • Neuronale Netzwerke (Seite 92-104) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitt 12.4.2.1
• Di, 02.07.2018

  Alpha-Zero als Anwendung von Loss-Funktionen
  Backpropagation als effiziente Implementierung von SGD, die Rückwärtsphase von Backpropagation und die Bestimmung der Fehlersignale, lineare Laufzeit für die Berechnung des Gradienten
  Anwendungen: Convolutional Neural Nets (Faltungsschichten, Poolingschichten, vollständig verbundene Schichten, Softmax-Gatter), Shared Weights, lokale Verbindungen, große Tiefe, neuronale Netze für visuelle Objekterkennung (LeNet, AlexNet, GoogLeNet)

  Material:
  • Vortragsfolien:
    • Neuronale Netzwerke (Seite 68-91) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitt 12.2.3 und 12.4.1
  • Weitere Lektüre:
    • [MRT] Kapitel 6
    • LeCun et al. "Learning algorithms for classification: A comparison on handwritten digit recognition" Neural networks: the statistical mechanics perspective 261 (1995): 276. Seite 8.
• Di, 26.06.2018

  stochastischer Gradientenabstieg (SGD) (Auswertung für konvexe quadratische Zielfunktionen mit vorgegebener Konditionszahl, Konvergenzgeschwindigkeit für SGD, Konvergenzgeschwindigkeit Θ(1/k) ist optimal für SGD, Konvergenzgeschwindigkeit für SGD + Momentum ist Θ(1/k²): quadratischer Geschwindigkeitsgewinn bei großen Konditionszahlen); Loss-Funktionen (quadratischer Loss, Log-Loss und Cross-Entropie)

  Material:
  • Vortragsfolien:
    • Neuronale Netzwerke (Seite 50-67) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 12.2.2.1 und 12.2.2.2.
  • Weitere Lektüre:
    • [GBC] Abschnitt 7.11
• Mo, 25.06.2018

  Lineare Konvergenzgeschwindigkeit für das Gradientenabstiegsverfahren bei hinreichend kleiner Schritt-weite (Analyse für stark konvexe Funktionen, die L-glatt sind; wenn die Funktion "nur" konvex ist, sinkt die Geschwindigkeit auf 1/k für die k-te Iteration bei Nesterovs Accelerated-Gradient-Descent-Verfahren steigt die Geschwindigkeit auf 1/k², auch das Momentum-Verfahren kann das Gradientenabstiegsverfahren erheblich beschleunigen); SGD für Feedforward-Netzwerke (das konventionelle Gradientenabstiegs-verfahren verschlingt zu viel Zeit)

  Material:
  • Vortragsfolien:
    • Neuronale Netzwerke (Seite 38-49) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitt 12.2.2
  • Weitere Lektüre:
    • [SB] Kapitel 14, Abschnitte 20.5 und 20.6
    • [GBC] Abschnitte 5.9 und 6.5
    • [Nat] Yann LeCun, Yoshua Bengio, Geoffrey Hinton: Nature-Artikel über Deep Learning
• Di, 19.06.2018

  Beispielkomplexität (Interpolation durch ReLU-Gatter, VC-Dimension eines Threshold-Schaltkreises ist O(|E| log|E|), für Standard-Sigmoid-Schaltkreise steigt die VC-Dimension auf Ω(|E|²));
  Bestimmung einer ERM-Hypothese führt auf ein Minimierungsproblem ohne Restriktionen; lokale Suche mithilfe des Gradienten; die Minimierung konvexer Funktionen als Experimentierfeld (starke Konvexität und Krümmung)

  Material:
  • Vortragsfolien:
    • Neuronale Netzwerke (Seite 25-37) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 12.1.3, 12.3 und 12.2.1
  • Weitere Lektüre:
    • [SB] Abschnitte 20.3 und 20.4
• Mo, 18.06.2018

  Berechnungskraft (Negation, Disjunktion, Konjunktion, Vergleich zweier Binärzahlen, Parität, Sortieren in fünf Schichten; Neuronale Netzwerke als Number Cruncher; Beispielkomplexität (neuronale Netze der Größe O(|S|) können eine beliebige Klassifizierung der Beispielmenge S wiedergeben)

  Material:
  • Vortragsfolien:
    • Neuronale Netzwerke (Seite 12-24) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 12.1 und 12.3
  • Weitere Lektüre:
    • [SB] Abschnitte 20.1 bis 20.3
    • [GBC] Kapitel 6 bis inkl. 6.1
• Di, 12.06.2018

  Hard-Margin-Fall (Dualitätssatz, die verallgemeinerte Lagrange-Funktion, das Einsetzen der KKT-Bedingungen in die Zielfunktion beseitigt die Abhängigkeit vom Gewichtsvektor w und Schwellenwert t, konvexe Minimierung im niedrigdimensionalen Beispielraum mit s Unbestimmten und s+1 Nebenbedingungen; Supportvektoren bestimmen den optimalen Gewichtsvektor und den optimalen Schwellenwert; wenige Support-Vektoren machen erfolgreiches Lernen hochwahrscheinlich (Occam-Prinzip)); Soft-Margin-Fall (ein Unterschreiten des Margins wird mit einem Strafterm geahndet)

  Neuronale Netze (Architektur und Feed-Forward-Netzwerk bzw. rekurrentes neuronales Netzwerk, Aktivierungsfunktionen)

  Material:
  • Vortragsfolien:
    • Support-Vektor-Maschinen (Seite 56-62) [ Druckversion | Bildschirmversion ]
    • Neuronale Netzwerke (Seite 1-12) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 11.4.2, 11.4.3 und Anfang von Kapitel 12
  • Weitere Lektüre:
    • [SB] Abschnitte 15.3 und 15.4
    • [MRT] Abschnitte 4.2 und 4.3
• Mo, 11.06.2018

  Folgerungen aus dem Satz von Mercer (Kerne sind abgeschlossen unter Polynomen und Potenzreihen mit nicht-negativen Koeffizienten), Gauß-Kern, Grundlagen der konvexen Minimierung (Lagrange-Multiplikatoren, Karush-Kuhn-Tucker-Bedingungen (KKT), Dualitätssatz (starke Dualität))

  Material:
  • Vortragsfolien:
    • Support-Vektor-Maschinen (Seite 38-55) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 11.2 (ab S. 172), 11.4 (bis S. 179)
  • Weitere Lektüre:
    • [SB] Kapitel 16, Abschnitte 15.3 und 15.4
    • [MRT] Abschnitt 5.2
• Di, 05.06.2018

  Verallgemeinerungsfehler für SVMs im Soft- und Hard-Margin-Fall), SVM-Anwendungen (Bag-of-Words-Ansatz, Bilderkennung, Ziffernerkennung), Kerne (Gram-Matrix und Satz von Mercer, Abschluss der Kerneigenschaft unter nicht-negativer Addition und Multiplikation)

  Material:
  • Vortragsfolien:
    • Support-Vektor-Maschinen (Seite 21-37) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 11.1.4, 11.1.5, 11.1.6, 11.2 (bis S. 171), 11.3
  • Weitere Lektüre:
    • [SB] Abschnitt 15.2
    • [MRT] Abschnitte 4.3 und 5.1
• Mo, 04.06.2018

  Feature-Funktionen (Bag of Words, Interpolation), die Grundidee der Support-Vektor-Maschinen: trenne die positiven von den negativen Beispielen mit möglichst großem Margin und wende für eine effiziente Implementierung den Kernel-Trick an, die Suche nach einer Trennung mit möglichst großem Margin führt auf ein mathematisches Programm mit linearen Nebenbedingungen und einer konvexen, quadratischen Zielfunktion, Lernen ist garantiert, wenn der empirische Margin-Loss klein ist und die Beispielzahl sehr viel größer als (R/(ε⋅ρ))² ist.

  Material:
  • Vortragsfolien:
    • Support-Vektor-Maschinen (Seite 4-20) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 11.1.1 bis 11.1.4
  • Weitere Lektüre:
    • [SB] Abschnitt 15.1
    • [MRT] Abschnitte 4.1 und 4.2.1
    • IEEE Spectrum: Human-Level AI Is Right Around the Corner — or Hundreds of Years Away
• Di, 29.05.2018

  Validierung (Hold-out-Set, k-fache Kreuzvalidierung), nicht-binäre Lernprobleme (One-versus-All, All-Pairs, ERM-Algorithmen mit möglicherweise völlig unterschiedlichen Beispielzahlen, VC-Dimension gibt zu schwache Voraussagen für die Beispielzahl), Nearest-Neighbor
  Support-Vektor-Machinen (Feature-Funktionen, Feature-Vektoren, Feature-Räume); Bag of Words

  Material:
  • Vortragsfolien:
    • Grundlegende Methoden (Seite 4-26) [ Druckversion | Bildschirmversion ]
    • Support-Vektor-Maschinen (Seite 1-3) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 9.1 und 9.2
  • Weitere Lektüre:
    • [SB] Kapitel 11
• Mo, 28.05.2018

  Perzeptron: vollständige Trennbarkeit, Abhängigkeit von Margin und Beispiel-Norm, Unabhängigkeit von Dimension, partielle Trennbarkeit für den Perzeptron-Algorithmus (Norm des Fehlervektors), Winnow vs. Perzeptron, Zusammenfassung Online-Algorithmen

  Grundlegende Methoden: Welche Fragen sind zu klären?

  Material:
  • Vortragsfolien:
    • Online-Algorithmen (Seite 59-77) [ Druckversion | Bildschirmversion ]
    • Grundlegende Methoden (Seite 1-3) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 8.2.2.2, 8.2.3 und 8.3 sowie Kapitel 9 (S. 153-154)
  • Weitere Lektüre:
    • [MRT] Abschnitt 7.3
• Di, 22.05.2018

  Winnow und Weighted Majority, Analyse von Winnow (Potential-Funktion: Veränderung des Potentials), Winnow und Disjunktionen, der Perzeptron-Algorithmus

  Material:
  • Vortragsfolien:
    • Online-Algorithmen (Seite 47-58) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitt 8.2.1 und 8.2.2
  • Weitere Lektüre:
    • [MRT] Abschnitt 7.3
    • [SB] Abschnitt 21.4
• Di, 15.05.2018

  Analyse des Winnow-Algorithmus für monotone Disjunktionen und weitere Anwendungen (DNFs), einige Grundlagen aus der analytischen Geometrie, der Margin für eine Beispiel-Menge, das Lernen von Threshold-Funktionen (mit und ohne Schwellenwert, monotone Gewichte),
  Der Winnow-Algorithmus für monotone Threshold-Funktionen

  Material:
  • Vortragsfolien:
    • Online-Algorithmen (Seite 32-46) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitt 8.2.1
  • Weitere Lektüre:
    • [MRT] Abschnitt 7.3.2
• Mo, 14.05.2018

  Für jede Konzeptklasse C ist Tiefe(C) = Gegenbeispiel(C),
  Auswahl von Experten: der Weighted-Majority-Algorithmus (deterministische und randomisierte Variante, Analyse beider Varianten), Universal-Portfolio-Algorithmus, der Winnow-Algorithmus für monotone Disjunktionen

  Material:
  • Vortragsfolien:
    • Online-Algorithmen (Seite 10-31) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 8.1 und 8.2.1.1
  • Weitere Lektüre:
    • [MRT] Abschnitte 7.2.2, 7.2.3 und 7.3.2
• Di, 08.05.2018

  Schwierigkeit des Lernens von Schaltkreisen und neuronalen Netzen für die Gleichverteilung, Schwierigkeit des Lernens von endlichen Automaten, Schwierigkeit des Lernens eines Durchschnitts von Halbräumen, Zusammenfassung

  Online-Algorithmen (Gegenbeispielkomplexität, VC-Dimension und der Logarithmus von |C|, Halbierungsalgorithmus)

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seite 147-160) [ Druckversion | Bildschirmversion ]
    • Online-Algorithmen (Seite 1-9) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 6.2, 6.3 und 7.1
  • Weitere Lektüre:
    • [MRT] Abschnitte 7.2.2 und 7.4
    • [SB] Abschnitt 21.2.1 (Seiten 252-254)
• Mo, 07.05.2018

  Schwierigkeit des Lernproblems unabhängig von der Hypothesenklasse (RSA-Kryptosystem, die Konzeptklasse RSA, jeder effizienter PAC-Algorithmus für RSA widerlegt die RSA-Hypothese, die Konzeptklasse RSA besitzt keine effizienten PAC-Algorithmen, wenn die RSA-Hypothese richtig ist);

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seite 137-146) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 6.2 und 6.3
  • Weitere Lektüre:
    • [MRT] Seiten 147-150
    • [SB] Seiten 245-248
• Mo, 30.04.2018

  Charakterisierung der (agnostischen) PAC-Lernbarkeit (endliche VC-Dimension), effiziente PAC-Algorithmen (Monome, symmetrische Funktionen, Rechtecke und Halbräume), das Konsistenzproblem (ein NP-vollständiges Konsistenzproblem schließt erfolgreiches Lernen vermutlich aus); NP-Vollständigkeit des Konsistenzproblems für 3-KLAUSEL-KNF

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seiten 117-136) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 5.3 und 6.1
  • Weitere Lektüre:
    • [SB] Abschnitt 8.3
• Di, 24.04.2018

  scharfe Schranke für die Beispielzahl, wenn VC(C) ≈ log(|C|); No-Free-Lunch-Theorem, obere Schranke für die Beispielzahl (die Anzahl der Konzepte "auf" einer Beispielmenge: Sauers Lemma, Fehlerregionen und ε-Netze, die Ereignisse A_s und B_s, prob[A_s] ≤ 2 prob[B_s], Großexperimente und eine Reduktion auf Sauers Lemma)

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seiten 98-116) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 5.3
  • Weitere Lektüre:
    • [SB] Abschnitte 8.1
• Mo, 23.04.2018

  KUGELN, SINUS, VC-Dimension für bestimmte Konzeptklassen; untere Schranken für die notwendige Beispielzahl mithilfe der VC-Dimension

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seiten 86-97) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 5.2 und 5.3
  • Weitere Lektüre:
    • [MRT] Abschnitte 3.3. und 3.4
    • [SB] Kapitel 6
• Di, 17.04.2018

  Occam-Algorithmen (erfolgreiche Hypothesen komprimieren die Beispiele); VC-Dimension (BOOLEAN, RECHTECK, HALBRAUM)

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seiten 67-85) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 4.2 und 5.1
  • Weitere Lektüre:
    • [MRT] Abschnitte 3.2 und 3.3
    • [SB] Abschnitte 6.1, 6.2 und 6.3
• Mo, 16.04.2018

  Beispielzahl bei Existenz einer Hypothese mit kleinem Fehler; das agnostische PAC-Modell (Funktionen mit beliebigem Wertebereich Y, Verteilungen auf X × Y, Loss-Funktionen); Loss-Funktionen (0-1-Loss, quadratischer Loss, erwarteter (oder wahrer) Loss, empirischer Loss (oder Trainingsfehler)); agnostische PAC-Algorithmen (Approximationsfehler, Schätzfehler, epsilon-approximative Beispielmengen); Argumentation (der Erwartungswert des empirischen Losses ist der wahre Loss, der emprische Loss ist eine Folge unabhängiger Zufallsvariablen, eine pro Beispiel, Ungleichung von Hoeffding)

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seiten 43 bis 66) [ Druckversion | Bildschirmversion ]
  • Skript:Abschnitte 4.1.2 und 4.1.3
  • Weitere Lektüre:
    • [MRT] Abschnitt 2.4
    • [SB] Abschnitt 3.2 bis Kapitel 4
• Di, 10.04.2018

  Beispielkomplexität für Konzeptklassen endlicher Größe (der Fall konsistenter Hypothesen), ERM-Hypothesen und ERM-Algorithmen

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seiten 29 bis 42) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitt 4.1.1
  • Weitere Lektüre:
    • [MRT] Abschnitte 2.2 und 2.3
    • [SB] Abschnitte 2.2 und 2.3
• Mo, 09.04.2018

  Organisatorisches: bitte unbedingt an den Übungen teilnehmen, der Übungsbetrieb beginnt in der dritten Vorlesungswoche, das erste Blatt erscheint am Montag der zweiten Vorlesungswoche.

  Das PAC-Modell:
  Beispiele, Konzepte und Hypothesen, Fehlermessung, Fehler- und Misstrauensparameter, PAC-Algorithmen (hochwahrscheinlich erfolgreiches Lernen für alle Konzepte der Klasse und alle Verteilungen)

  Material:
  • Vortragsfolien:
    • PAC-Modell (Seiten 1 bis 28) [ Druckversion | Bildschirmversion ]
  • Skript:
    • Kapitel 2.4 (Grundlagen aus der Stochastik)
    • Seiten 55 bis 57 und Kapitel 4.1 (Zentrale Fragestellungen)
  • Weitere Lektüre:
    • [MRT] Seiten 1 bis 13
    • [SB] Seiten 19 bis 35