Optimale Fehlergrenzen für transduktives Online-Lernen
Zachary Chase Steve Hanneke Shay Moran Jonathan Shafer

Abstract
Wir lösen ein 30 Jahre altes offenes Problem bezüglich der Leistungsfähigkeit von unbeschrifteten Daten im online Lernen, indem wir die Lücke zwischen transduktivem und standardmäßigem online Lernen präzise quantifizieren. Wir beweisen, dass für jede Konzeptklasse mit Littlestone-Dimension d die transduktive Fehlergrenze mindestens Ω(√d) beträgt. Damit wird eine exponentielle Verbesserung gegenüber früheren unteren Schranken von Ω(log log d), Ω(√d) und Ω(√log d), respektive, durch Ben-David, Kushilevitz und Mansour (1995, 1997) sowie Hanneke, Moran und Shafer (2023), erreicht. Außerdem zeigen wir, dass unsere Schranke scharf ist: Für jedes d existiert eine Klasse mit Littlestone-Dimension d, deren transduktive Fehlergrenze O(√d) beträgt. Unser obere Schranke verbessert zudem die bisher beste bekannte obere Schranke von (2/3)·d von Ben-David et al. (1997). Diese Ergebnisse demonstrieren eine quadratische Lücke zwischen transduktivem und standardmäßigem online Lernen und unterstreichen somit den Nutzen eines fortgeschrittenen Zugriffs auf die Folge der unbeschrifteten Instanzen. Dies steht im starken Gegensatz zur PAC-Schätzung, in der transduktives und standardmäßiges Lernen ähnliche Stichprobengrößen aufweisen.
KI mit KI entwickeln
Von der Idee bis zum Start — beschleunigen Sie Ihre KI-Entwicklung mit kostenlosem KI-Co-Coding, sofort einsatzbereiter Umgebung und den besten GPU-Preisen.