Professur für
Theoretische Informatik

• Aktuelle Veranstaltungen
• Theoretische Informatik 2
• Computational Learning Theory
• Veranstaltungen im WS 17/18
• Diskrete Modellierung
• Seminar 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, 25.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