HyperAIHyperAI

Command Palette

Search for a command to run...

vor 2 Tagen

Optimale Fehlergrenzen für transduktives Online-Lernen

Zachary Chase Steve Hanneke Shay Moran Jonathan Shafer

Optimale Fehlergrenzen für transduktives Online-Lernen

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.

KI-Co-Coding
Sofort einsatzbereit GPUs
Beste Preise
Jetzt starten

Hyper Newsletters

Abonnieren Sie unsere neuesten Updates
Wir werden die neuesten Updates der Woche in Ihren Posteingang liefern um neun Uhr jeden Montagmorgen
Unterstützt von MailChimp
Optimale Fehlergrenzen für transduktives Online-Lernen | Forschungsarbeiten | HyperAI