HyperAIHyperAI

Command Palette

Search for a command to run...

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.


Build AI with AI

From idea to launch — accelerate your AI development with free AI co-coding, out-of-the-box environment and best price of GPUs.

AI Co-coding
Ready-to-use GPUs
Best Pricing

HyperAI 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 | Papers | HyperAI