Membership‑Abfragen können Testable Learning nicht beschleunigen

In der Welt des maschinellen Lernens gelten Membership‑Abfragen (MQ) oft als Turbo für Lernalgorithmen, besonders wenn die Datenverteilung bekannt ist. Ein neuer Beitrag auf arXiv zeigt jedoch, dass im sogenannten „testable learning“ – einem Modell, bei dem der Lernende eine Hypothese nur ausgeben darf, wenn die zugrunde liegende Verteilung eine gewünschte Eigenschaft erfüllt – MQ keine Zeitersparnis bringen.

Der Autor demonstriert, dass die Zeitkomplexität eines testable‑Learning‑Algorithmus mit MQ nicht unter die des reinen Sample‑Only‑Lernens fallen kann. Dazu wird eine allgemeine Reduktion von Sample‑basierten Refutationsaufgaben für boolesche Konzeptklassen auf das testable learning mit Abfragen (TL‑Q) vorgestellt. Diese Reduktion liefert unter anderem neue Untergrenzen für TL‑Q, indem sie die bekannten Lern‑zu‑Refutations‑Reduktionen nutzt.

Das Ergebnis ist klar: Für ein gegebenes Konzept und eine Verteilung gibt es keinen m‑Sample‑TL‑Q‑Algorithmus, der im Vergleich zum besten m‑Sample‑PAC‑Lernenden superpolynomial schneller arbeitet. Der Beitrag definiert zudem eine Klasse „statistischer“ MQ‑Algorithmen, die viele bekannte, verteilungs‑spezifische MQ‑Lernende einschließt. Für diese Klasse gilt, dass TL‑Q‑Algorithmen effiziente SQ‑Refutations‑ und Lernalgorithmen implizieren.

In Kombination mit bereits bekannten SQ‑Dimensions‑Unterschranken folgt daraus, dass effiziente Membership‑Query‑Lernende nicht in testable learning überführt werden können. Damit wird die Grenze für die Nutzung von MQ in diesem speziellen Lernmodell deutlich geklärt.