🤖 machine learning

Testing Distributions Against Bounded Distinguishers

Dieses Paper führt ein Framework für das Testen von Verteilungen gegen beschränkte Klassen von Distinguierern (Fooling Distance) ein, wobei es dessen Stichproben-Effizienz in hochdimensionalen Settings demonstriert und dessen Verbindungen zu Testable Learning, Verifikation und strukturiertem Distribution Testing nutzt, um neue Algorithmen und untere Schranken in diesen Feldern abzuleiten.

Ursprüngliche Autoren: Mark Bun, Rathin Desai, Renato Ferreira Pinto Jr

Veröffentlicht 2026-07-20

📖 8 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Mark Bun, Rathin Desai, Renato Ferreira Pinto Jr

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Detektiv, der herauszufinden versucht, ob eine Tüte voller Murmeln „fair“ ist. In der realen Welt bedeutet die Überprüfung, ob eine Tüte fair ist, normalerweise, dass man jede einzelne Murmel betrachtet, um zu sehen, ob die Farben perfekt gemischt sind. Aber was, wenn die Tüte Billionen von Murmeln oder sogar eine unendliche Anzahl von ihnen enthält, wie etwa Sandkörner an einem Strand? In der Welt der Informatik und Statistik ist das ein Albtraum. Zu versuchen, jedes einzelne Sandkorn zu prüfen, um zu sehen, ob die Verteilung „perfekt“ ist, ist unmöglich; man bräuchte mehr Zeit, als das Universum existiert hat. Dies ist das Problem des Verteilungstestens (Distribution Testing).

Jahrzehntelang haben Wissenschaftler versucht, dies zu lösen, indem sie entweder davon ausgingen, dass die Murmeln ordentlichen, einfachen Mustern folgen (wie „alle roten links, alle blauen rechts“) oder indem sie supermächtige Werkzeuge verwendeten, um einen speziellen Blick in die Tüte zu werfen. Aber was, wenn die Murmeln chaotisch, hochdimensional und die Muster komplex sind? Hier kommt eine neue Idee namens Fooling Distance (Täuschungsabstand) ins Spiel. Anstatt zu fragen: „Ist diese Tüte exakt dieselbe wie die perfekte Tüte?“ (was zu schwer ist), fragen wir eine weichere Frage: „Kann irgendeine einfache Regel, die ich mir vorstellen kann, den Unterschied zwischen dieser Tüte und der perfekten einen erkennen?“ Wenn eine einfache Regel – wie etwa „Zähle die roten Murmeln“ oder „Zähle die Murmeln mit einem Kratzer“ – keinen Unterschied feststellen kann, dann sind die Tüten aus praktischen Gründen identisch. Es ist, als würde man versuchen, einen einfach gestrickten Wächter zu täuschen; wenn der Wächter das Falsche nicht vom Echten unterscheiden kann, dann sind sie für die Zwecke des Wächters identisch.

Dieses Paper mit dem Titel „Testing Distributions Against Bounded Distinguishers“ ist eine Meisterklasse darin, wie man diese „Täuschungs“-Idee nutzt, um Probleme zu lösen, die zuvor als unmöglich galten. Die Autoren, Mark Bun, Rathin Desai und Renato Ferreira Pinto Jr., zeigen, dass wir durch eine leichte Lockerung der Regeln des Spiels nicht nur diese chaotischen, hochdimensionalen Murmeltüten testen können, sondern auch Geheimnisse in drei anderen Bereichen der Informatik entschlüsseln können, die völlig unzusammenhängend schienen: dem Lehren von Computern, der Überprüfung, ob das Lernen eines Computers ehrlich ist, und dem Testen spezifischer Arten von strukturierten Daten.

Die große Idee: Der „Fooling“-Test

Der Kern des Papers ist eine neue Art, Verteilungen zu testen, die F-Identitätstests genannt wird. Stellen Sie sich vor, Sie haben eine Referenzverteilung (nennen wir sie den „Goldstandard“) und eine unbekannte Verteilung (den „Geheimnisvollen Beutel“). Auf die alte, strenge Art der Dinge mussten Sie beweisen, dass der „Geheimnisvolle Beutel“ exakt derselbe wie der Goldstandard ist. Wenn der „Geheimnisvolle Beutel“ auch nur ein einziges Sandkorn an der falschen Stelle hatte, mussten Sie es erfassen. Dies ist bei riesigen, komplexen Datensätzen unmöglich.

Die Autoren schlagen einen klügeren Ansatz vor. Sie sagen: „Lassen Sie uns eine spezifische Menge einfacher Regeln oder ‚Distinguisher‘ (nennen wir diese Menge F) auswählen.“ Diese Regeln könnten Dinge sein wie „Ist die Zahl größer als 5?“ oder „Ist die Form ein Dreieck?“. Das Ziel ist es nicht, jeden möglichen Unterschied zu erfassen, sondern nur die Unterschiede, die diese spezifischen Regeln sehen können. Wenn der „Geheimnisvolle Beutel“ den Test für alle Regeln in F besteht, sagen wir, dass er einen kleinen Fooling Distance zum Goldstandard hat. Mit anderen Worten: Der „Geheimnisvolle Beutel“ ist „gut genug“, um unsere spezifischen Regeln zu täuschen.

Das Paper beweist, dass dieser „Fooling“-Test nicht nur ein billiger Trick ist, sondern ein mächtiges, mathematisch fundiertes Werkzeug. Sie zeigen, dass wir diese Verteilungen selbst in hochdimensionalen Räumen (wo Daten viele, viele Merkmale haben, wie etwa ein Foto mit Millionen von Pixeln) effizient testen können, sofern unsere Menge an Regeln F nicht zu kompliziert ist.

Die Verbindung von drei unzusammenhängenden Welten

Der aufregendste Teil des Papers ist, wie es als universeller Übersetzer fungiert, der drei Felder verbindet, die normalerweise nicht miteinander kommunizieren:

Testbares Lernen (Testable Learning): Stellen Sie sich einen Studenten vor, der versucht, ein Fach zu lernen. Normalerweise lernt er vielleicht das Material perfekt für ein bestimmtes Lehrbuch, scheitert aber, wenn der Lehrer die Fragen ändert. „Testbares Lernen“ ist eine Methode, bei der der Student sagen kann: „Ich kann das nicht lernen, weil die Fragen zu seltsam sind“, und aufhört, bevor er Zeit verschwendet. Die Autoren zeigen, dass, wenn man eine Verteilung mit der „Fooling“-Methode testen kann, man automatisch einen testbaren Lernalgorithmus bauen kann. Es ist, als hätte man einen Spickzettel, der einem sagt, ob die Testfragen fair sind, noch bevor man überhaupt mit dem Lernen beginnt. Sie nutzen dies, um neue, effiziente Wege zu finden, um über „Halbräume“ (einfache Trennlinien in Daten) und „Entscheidungsbäume“ (Flowcharts, die für Entscheidungen verwendet werden) zu lernen.
PAC-Verifikation (PAC Verification): Dies ist wie ein Chef, der die Hausaufgaben eines Arbeiters überprüft. Der Arbeiter (der Prover) behauptet, die beste Lösung gefunden zu haben, aber der Chef (der Verifier) ist zu beschäftigt, um alles zu überprüfen. Der Chef braucht einen schnellen Weg, um die Arbeit zu verifizieren, ohne die gesamte Mathematik durchzuführen. Das Paper zeigt, dass man, wenn man einen „Fooling“-Tester hat, ein Verifikationsprotokoll aufbauen kann, bei dem der Chef viel weniger Stichproben (Beispiele) benötigt, um sicher zu sein, dass der Arbeiter nicht schummelt. Sie beweisen, dass ein Arbeiter, der behauptet, ein komplexes Muster gelernt zu haben, der Chef viel schneller überprüfen kann, vorausgesetzt, der Arbeiter versucht nicht, den Chef mit einer Verteilung zu täuschen, die für den spezifischen Satz von Regeln des Chefs anders aussieht.
Testen strukturierter Verteilungen (Testing Structured Distributions): Manchmal wissen wir, dass die Daten einer bestimmten Struktur folgen müssen, wie etwa einem Entscheidungsbaum oder einem Polynom niedrigen Grades. Das Paper zeigt, dass für diese spezifischen Arten von Daten der „Fooling Distance“ tatsächlich genauso gut ist wie die strenge „Total Variation Distance“ (der superharte Test). Das bedeutet, wir können die leichten „Fooling“-Tests verwenden, um die schweren „Total Variation“-Probleme für diese spezifischen Fälle zu lösen. Es ist, als würde man erkennen, dass für ein bestimmtes Schloss ein einfacher Schlüssel genauso gut funktioniert wie ein Generalschlüssel.

Was sie fanden (und was sie nicht fanden)

Die Autoren liefern konkrete Ergebnisse, nicht nur vage Ideen. Sie beweisen:

Stichprobenkomplexität (Sample Complexity): Die Anzahl der Stichproben, die benötigt werden, um den „Fooling“-Test zu bestehen, hängt von etwas ab, das Rademacher-Komplexität genannt wird. Denken Sie dies als ein Maß dafür, wie „zappelig“ oder komplex Ihr Regelsatz ist. Wenn Ihre Regeln einfach sind, benötigen Sie sehr wenige Stichproben. Wenn sie komplex sind, benötigen Sie mehr. Sie zeigen, dass diese Beziehung eng ist: Man kann mit ihrer Formel nicht viel besser werden.
Neue Algorithmen: Sie haben nicht nur bewiesen, dass Dinge existieren; sie haben sie gebaut. Sie entwickelten effiziente Algorithmen, um Folgendes zu testen:
- Halbräume (Halfspaces): Einfache Linien oder Ebenen, die Daten teilen.
- Entscheidungsbäume (Decision Trees): Flowcharts, die zur Klassifizierung verwendet werden.
- Polynom-Verteilungen (Polynomial Distributions): Daten, die glatten, gekrümmten Mustern folgen.
- Vereinigungen von Rechtecken (Unions of Rectangles): Daten, die wie eine Ansammlung von zusammengefügten Boxen aussehen.
Eigenständiges Lernen (Proper Learning): Sie zeigten, dass man durch die Verwendung von „Membership Queries“ (dem Computer die Frage stellen: „Was ist das Label für diesen spezifischen Punkt?“) Lernalgorithmen „eigenständig“ machen kann. Das bedeutet, der Algorithmus rät nicht einfach eine seltsame, komplexe Antwort; er findet eine Antwort, die tatsächlich zu der Kategorie passt, in der er sein soll (wie das Finden eines echten Entscheidungsbaums statt eines zufälligen Durcheinanders von Regeln).

Was sie ausschlossen

Das Paper ist vorsichtig dabei zu sagen, was nicht funktioniert. Sie zeigen, dass man die alten, strengen „Total Variation“-Tests nicht einfach für hochdimensionale oder kontinuierliche Daten verwenden kann; dies ist mit einer angemessenen Anzahl von Stichproben mathematisch unmöglich. Man muss die Kriterien lockern, entweder indem man davon ausgeht, dass die Daten strukturiert sind, oder indem man die „Fooling Distance“ verwendet. Sie stellen auch klar, dass ihre Methoden zwar effizient für bestimmte Arten von Daten sind (wie Entscheidungsbäume), aber nicht magisch das Problem für jede mögliche Art von Daten lösen. Wenn die Daten völlig chaotisch sind und in keine einfache Struktur passen, könnte der „Fooling“-Test dennoch zu viele Stichproben erfordern.

Das Fazit

Dieses Paper ist ein wenig wie die Entdeckung eines neuen Typs von Schloss knackers. Jahrelang versuchten Schlossmacher (Informatiker), komplexe, hochdimensionale Schlösser (Verteilungen) mit einem Vorschlaghammer (Total Variation Testing) zu öffnen, was zu schwer und zu langsam war. Die Autoren erkannten, dass, wenn man das Schloss nur für eine bestimmte Menge von Schlüsseln (die begrenzten Distinguisher) öffnen muss, man ein viel leichteres, schnelleres Werkzeug (Fooling Distance) verwenden kann.

Nicht nur öffnet dieses Werkzeug die Schlösser schneller, sondern es stellt sich auch heraus, dass es dasselbe Werkzeug ist, das benötigt wird, um Studenten zu lehren (testable learning), Hausaufgaben zu kontrollieren (verification) und spezifische Arten von Rätseln zu testen (structured distributions). Die Autoren haben gezeigt, dass diese drei Felder eigentlich nur verschiedene Zimmer im selben Haus sind, und die „Fooling Distance“ ist der Flur, der sie alle verbindet.

Die Ergebnisse sind mathematisch bewiesen, was bedeutet, dass es sich um solide Fakten handelt, nicht nur um Vermutungen. Sie liefern spezifische Zahlen dafür, wie viele Stichproben benötigt werden (wie $O(\sqrt{k}/\epsilon^2)$ für Vereinigungen von $k$ Intervallen) und zeigen, dass diese Zahlen für bestimmte Arten von Problemen die bestmöglichen sind. Während sie nicht behaupten, alle Verteilungstests des Universums gelöst zu haben, haben sie einen leistungsstarken neuen Rahmen geschaffen, der das Unmögliche für eine Vielzahl wichtiger, realer Szenarien möglich macht.

Technisches Resümee: Testen von Verteilungen gegen beschränkte Unterscheidungsfunktionen

1. Problemstellung und Motivation

Die Arbeit befasst sich mit der grundlegenden Herausforderung des Verteilungstestens in hochdimensionalen und kontinuierlichen Domänen. Das Standard-Identitätstesten, das darauf abzielt, zwischen einer unbekannten Verteilung $P$ und einer Referenzverteilung $P_{\text{ref}}$ basierend auf der Totalvariation (TV)-Distanz zu unterscheiden, leidet unter prohibitiven unteren Schranken für die Stichprobenkomplexität (z. B. $\Theta(2^{n/2})$ für den booleschen Hyperwürfel) oder ist in kontinuierlichen Settings mit endlichen Stichproben unmöglich.

Bestehende Ansätze verlassen sich typischerweise auf stärkere Sampling-Orakel (z. B. bedingtes Sampling) oder setzen voraus, dass die Eingabe zu einer spezifischen Klasse strukturierter Verteilungen gehört. Dieses Paper schlägt eine dritte Relaxation vor: das Testen gegenüber einer beschränkten Klasse von Unterscheidungsfunktionen. Anstatt zu fordern, dass $P$ in der TV-Distanz nahe an $P_{\text{ref}}$ liegt, besteht das Ziel darin, zu bestimmen, ob sie durch eine spezifische Familie von booleschen Funktionen $\mathcal{F}$ ununterscheidbar sind.

Dies führt zur Definition des $\mathcal{F}$ -Identitätstestens:

Eingabe: Zugriff auf Stichproben einer unbekannten Verteilung $P$ und eine explizite Referenzverteilung $P_{\text{ref}}$ .
Unterscheidungsfunktionen: Eine Familie von booleschen Funktionen $\mathcal{F} = \{f: \mathcal{X} \to \{0, 1\}\}$ .
Metrik: Die Fooling-Distanz (eine Integral-Wahrscheinlichkeitsmetrik), definiert als:
$\text{dist}_{\mathcal{F}}(P, P_{\text{ref}}) := \sup_{f \in \mathcal{F}} | \mathbb{E}_P[f] - \mathbb{E}_{P_{\text{ref}}}[f] |$
Aufgabe: Zwischen $P = P_{\text{ref}}$ und $\text{dist}_{\mathcal{F}}(P, P_{\text{ref}}) > \epsilon$ zu unterscheiden.

Die Autoren argumentieren, dass dieser Rahmen nicht nur ein natürliches computergestütztes Problem darstellt, sondern auch als vereinendes Konzept dient, das testbares Lernen, PAC-Verifikation und das Testen strukturierter Verteilungen miteinander verbindet.

2. Methodik und Kernrahmen

Das Paper entwickelt einen theoretischen Rahmen, der auf der Fooling-Distanz basiert und Werkzeuge aus der Lerntheorie (Rademacher-Komplexität, VC-Dimension) sowie dem Verteilungstesten nutzt.

2.1 Schranken der Stichprobenkomplexität

Die Autoren etablieren enge Schranken für die Stichprobenkomplexität des $\mathcal{F}$ -Identitätstestens:

Verteilungsfreie Schranken: Unter Verwendung von Uniformer Konvergenz zeigen sie, dass $O(d/\epsilon^2)$ Stichproben ausreichen, wobei $d$ die VC-Dimension von $\mathcal{F}$ ist.
Verteilungsspezifische Schranken: Sie führen eine präzisere Charakterisierung basierend auf der Rademacher-Komplexität von $\mathcal{F}$ $F$ bezüglich der Referenzverteilung $P_{\text{ref}}$ $P_{ref}$ ein, bezeichnet als $\mathcal{R}_m(\mathcal{F}, P_{\text{ref}})$ $R_{m} (F, P_{ref})$ .
- Obere Schranke: Wenn $\mathcal{R}_m(\mathcal{F}, P_{\text{ref}}) \leq \epsilon/16$ , existiert ein Identitätstester mit Stichprobenkomplexität $m + O(\log(1/\delta)/\epsilon^2)$ .
- Untere Schranke: Wenn $\mathcal{R}_m(\mathcal{F}, P_{\text{ref}}) > 4\epsilon$ , benötigt jeder Tester $\Omega(\sqrt{m})$ Stichproben.
- Es gibt eine quadratische Lücke zwischen der oberen und unteren Schranke in Bezug auf $m$ , die die Autoren als notwendig erachten, wenn $\mathcal{F}$ die Menge aller booleschen Funktionen ist.

2.2 Verbindungen zu anderen Modellen

Der methodische Kernbeitrag ist die Demonstration bidirektionaler Reduktionen zwischen dem $\mathcal{F}$ -Identitätstesten und drei anderen Bereichen:

Testbares Lernen:
- Reduktion: Ein testbarer Lerner für $\mathcal{F}$ (der eine Hypothese lernt, falls der Rand "gut" ist, und andernfalls ablehnt) impliziert einen $\mathcal{F}$ -Identitätstester. Die Konstruktion erfolgt durch Erstellung einer Mischverteilung, bei der der optimale Klassifikationsfehler der Fooling-Distanz entspricht.
- Konverse: Ein $\mathcal{F}$ -Identitätstester kombiniert mit einem distributionsspezifischen agnostischen Lerner impliziert einen testbaren Abfrage-Lerner (testable query learner). Dies ermöglicht das propert Lernen (Ausgabe einer Hypothese innerhalb von $\mathcal{F}$ ) durch Nutzung von Membership-Abfragen, eine Fähigkeit, die bestimmten Klassen ohne Abfragen zuvor nicht zur Verfügung stand.
PAC-Verifikation:
- Äquivalenz: Das Paper stellt eine milde Äquivalenz zwischen $\mathcal{F}$ -Identitätstesten und PAC-Verifikation her.
- Lifting: Die Verifikation einer Hypothesenklasse $\mathcal{F}$ wird auf das Identitätstesten gegen eine "geliftete" Klasse $\tilde{\mathcal{F}}$ über der Domäne $\mathcal{X} \times \{0, 1\}$ reduziert, wobei $\tilde{f}(x, y) = \mathbb{1}[f(x) \neq y]$ .
- Ergebnis: Identitätstester für $\mathcal{F}$ liefern verteilungsfreie Verifikationsprotokolle mit stichprobeneffizienten Verifizierern. Umgekehrt implizieren testbare Verifikationsprotokolle untere Schranken für die Stichprobenkomplexität des $\mathcal{F}$ -Identitätstestens.
Testen strukturierter Verteilungen:
- Die Autoren zeigen, dass für bestimmte strukturierte Klassen von Verteilungen $\mathcal{D}$ die TV-Distanz zwischen zwei beliebigen Verteilungen in $\mathcal{D}$ durch die Fooling-Distanz gegenüber einer spezifischen Klasse von Unterscheidungsfunktionen (verwandt mit Scheffé-Mengen) erfasst wird.
- Durch Kombination von $\mathcal{F}$ -Identitätstestern mit der Reduktion auf testbares Lernen leiten sie computergestützte effiziente TV-Tester für strukturierte Verteilungen ab, wodurch die Unbehandbarkeit des allgemeinen TV-Testens umgangen wird.

3. Zentrale Beiträge und Ergebnisse

3.1 Testbares Proper Learning

Das Paper liefert neue Algorithmen für testbares proper learning (Lernen einer Hypothese innerhalb der Klasse $\mathcal{F}$ ) unter Verwendung von Membership-Abfragen:

Halbräume (Halfspaces): Ein testbarer proper query learner für Halbräume über $\mathbb{R}^n$ unter der Gauß-Verteilung mit Laufzeit $n^{\tilde{O}(1/\epsilon^2)}$ .
Entscheidungsbäume (Decision Trees): Ein testbarer proper query learner für Entscheidungsbäume der Größe $s$ über $\{0, 1\}^n$ unter der Gleichverteilung mit Laufzeit $(n/\epsilon)^{O(\log(s/\epsilon))}$ .
Semi-agnostisches Lernen: Die Autoren zeigen auch, dass testbares 3-semi-agnostisches proper learning (Fehlergarantie $3 \cdot \text{opt} + \epsilon$ ) im stichprobenbasierten Setting (ohativ Abfragen) für diese Klassen erreichbar ist.

3.2 PAC-Verifikationsprotokolle

Neue Verifikationsprotokolle werden abgeleitet für Klassen von Verteilungen:

Vereinigungen von Intervallen: Ein verteilungsfreies Verifikationsprotokoll für Vereinigungen von $k$ Intervallen auf $[0, 1]$ mit Verifizier-Stichprobenkomplexität $O(\sqrt{k}/\epsilon^2)$ .
Mehrdimensionale Rechtecke: Ein verteilungsfreies Verifikationsprotokoll für disjunkte Vereinigungen von achsenparallelen Rechtecken in $[0, 1]^n$ mit Verifizier-Stichprobenkomplexität $k^{6/7} \log^n(k) \cdot \text{poly}_n(1/\epsilon)$ .
Untere Schranken: Eine Rademacher-basierte untere Schranke für testbare Verifikation wird etabliert, die zeigt, dass die Verifizier-Stichprobenkomplexität $\Omega(\sqrt{m})$ beträgt, wenn $\mathcal{R}_m(\mathcal{F}, D_X) > 4\epsilon$ .

3.3 TV-Testing für strukturierte Verteilungen

Das Paper präsentiert computergestützte effiziente Identitätstester (gegen TV-Distanz) für:

Grad-2-Polynom-Verteilungen: Über $\{0, 1\}^n$ , mit Komplexität, die dem testbaren Lernen von Grad-2 PTFs entspricht ( $n^{\tilde{O}(1/\epsilon^9)}$ ).
Entscheidungsbaum-Verteilungen: Über $\{0, 1\}^n$ (stückweise gleichverteilt über die Blätter eines Baumes der Größe $s$ ), mit Komplexität $n^{O(\log(s/\epsilon))}$ .
Kontinuierliche Domänen: Stichprobeneffiziente Tester für Verteilungen mit Polynom-Dichten niedrigen Grades und Entscheidungsbaum-Dichten über $[0, 1]^n$ .

4. Bedeutung und Ansprüche

Die Autoren behaupten, dass diese Arbeit zwei Primärziele erreicht:

Machbarkeit in schwierigen Settings: Sie macht das Verteilungstesten in hochdimensionalen und kontinuierlichen Settings machbar, indem sie das Erfolgskriterium von der TV-Distanz auf die Fooling-Distanz lockert – eine Metrik, die für beschränkte Klassen von Unterscheidungsfunktionen handhabbar bleibt.
Vereinigung der Theorie: Sie offenbart tiefe, bisher unerkannte Verbindungen zwischen testbarem Lernen, PAC-Verifikation und dem Testen strukturierter Verteilungen. Der Rahmen des $\mathcal{F}$ -Identitätstestens fungiert als "Kernidee", die neue Ergebnisse in allen drei Bereichen ermöglicht.

Speziell behauptet das Paper:

Neue Algorithmen: Es liefert die ersten testbaren proper Lerner für Halbräume und Entscheidungsbäume (ohne Abfragen war die Eigenschaft "proper" nicht garantiert).
Verbesserte Verifikation: Es verbessert die Verifizier-Stichprobenkomplexität für die Verifikation von Vereinigungen von Intervallen und liefert die ersten Verifikationsprotokolle für mehrdimensionale Rechtecke.
Effizientes TV-Testing: Es schließt die Lücke zwischen der statistischen Machbarkeit des $\mathcal{F}$ -Identitätstestens und der computergestützten Effizienz des testbaren Lernens, um effiziente TV-Tester für strukturierte Klassen zu produzieren, bei denen Standard-TV-Testing unmöglich ist.

Das Paper schließt mit dem Hinweis auf offene Fragen, wie etwa der Verfeinerung der quadratischen Lücke in der Rademacher-Charakterisierung der Stichprobenkomplexität und der Charakterisierung, welche Verteilungs-/Familien-Paare computergestützte effiziente Tester zulassen.