Kombinatorische Charakterisierung des exakten Lernens mit Mitgliedschaftsabfragen

Bearbeiten: Da ich seit einer Woche keine Antworten / Kommentare mehr erhalten habe, möchte ich hinzufügen, dass ich froh bin, etwas über das Problem zu hören. Ich arbeite nicht in der Gegend, auch wenn es eine einfache Beobachtung ist, weiß ich es vielleicht nicht. Sogar ein Kommentar wie "Ich arbeite in der Gegend, aber ich habe keine solche Charakterisierung gesehen" wäre hilfreich!

Hintergrund:

Es gibt mehrere gut untersuchte Lernmodelle in der Lerntheorie (z. B. PAC-Lernen, Online-Lernen, genaues Lernen mit Mitgliedschafts- / Äquivalenzabfragen).

Beispielsweise hat beim PAC-Lernen die Beispielkomplexität einer Konzeptklasse eine schöne kombinatorische Charakterisierung in Bezug auf die VC-Dimension der Klasse. Wenn wir also eine Klasse mit konstanter Genauigkeit und Sicherheit lernen wollen, kann dies mit $\Theta(d)$ Samples geschehen , wobei die VC-Dimension ist. (Beachten Sie, dass es sich um die Komplexität der Stichproben und nicht um die Komplexität der Zeit handelt.) Es gibt auch eine genauere Charakterisierung in Bezug auf Genauigkeit und Zuverlässigkeit. Ebenso hat das fehlergebundene Modell des Online-Lernens eine schöne kombinatorische Charakterisierung.$d$

Frage:

Ich möchte wissen, ob ein ähnliches Ergebnis für das Modell des exakten Lernens mit Mitgliedschaftsabfragen bekannt ist. Das Modell ist wie folgt definiert: Wir haben Zugriff auf eine Blackbox, die bei Eingabe von ergibt . Wir wissen, dass aus einer Konzeptklasse . Wir wollen mit möglichst wenigen Abfragen ermitteln.$x$$f(x)$$f$$C$$f$

Gibt es einen kombinatorischen Parameter einer Konzeptklasse , der die Anzahl der Abfragen kennzeichnet, die zum Erlernen eines Konzepts im Modell des exakten Lernens mit Mitgliedschaftsabfragen erforderlich sind?$C$

Was ich weiß:

Die beste derartige Charakterisierung, die ich gefunden habe, findet sich in diesem Aufsatz von Servedio und Gortler unter Verwendung eines Parameters, den sie Bshouty, Cleve, Gavaldà, Kannan und Tamon zuschreiben . Sie definieren einen kombinatorischen Parameter namens , wobei die Konzeptklasse ist, die die folgenden Eigenschaften aufweist. ( sei die optimale Anzahl von Abfragen, die zum Erlernen von in diesem Modell erforderlich sind .)$\gamma^C$$C$$Q_C$$C$

$Q_C = \Omega(1/\gamma^C)\qquad Q_C = \Omega(\log |C|) \qquad Q_C = O(\log |C|/\gamma^C)$

Diese Charakterisierung ist fast eng. Es könnte jedoch eine quadratische Lücke zwischen der oberen und unteren Grenze geben. Zum Beispiel, wenn , dann ist die Untergrenze Ω ( k ) , aber die Obergrenze ist O ( k 2 ) . (Ich denke auch, dass diese Lücke erreichbar ist, dh es gibt eine Konzeptklasse, für die die unteren Grenzen beide Ω ( k ) sind , aber die obere Grenze ist O ( k 2 ) .)$1/\gamma^C = \log |C| = k$$\Omega(k)$$O(k^2)$$\Omega(k)$$O(k^2)$

Um den Punkt des Beispiels eines anonymen Elches nach Hause zu fahren, betrachten Sie die Konzeptklasse, die aus Funktionen besteht, die 1 an nur einem Punkt in {0,1} ^ n ausgeben. Die Klasse hat die Größe 2 ^ n, und im schlimmsten Fall werden 2 ^ n Abfragen benötigt. Werfen Sie einen Blick auf die Worst-Case-Lehrdimension (Goldman & Schapire), die etwas Ähnliches wie das bietet, wonach Sie suchen.

Ich kenne eine solche Charakterisierung nicht. Es ist jedoch zu beachten, dass für fast jede Konzeptklasse alle Punkte abgefragt werden müssen. Betrachten Sie dazu die Konzeptklasse, die aus allen n-dimensionalen Booleschen Vektoren mit Hamming-Gewicht 1 besteht. Für diese Konzeptklasse sind offensichtlich n Abfragen erforderlich, was ihrer Kardinalität entspricht. Sie können diese Beobachtung wahrscheinlich verallgemeinern, um festzustellen, dass für fast jede Konzeptklasse auch alle Abfragen ausgeführt werden müssen.

Ich würde vermuten, dass es angesichts einer Konzeptklasse C als Eingabe schwierig ist, die Komplexität des genauen Lernens der Konzeptklasse mit Mitgliedschaftsabfragen zu bestimmen oder sie sogar zu einer Konstanten zu approximieren. Dies würde einen Hinweis darauf geben, dass es keine "gute" kombinatorische Charakterisierung gibt. Wenn Sie ein solches Ergebnis für die NP-Härte nachweisen möchten, aber versuchen, es nicht zu tun, können Sie es hier posten, und ich werde sehen, ob ich es herausfinden kann (ich habe einige Ideen).

Obwohl andere auf die Antwort hingewiesen haben. Ich dachte , ich kann es machen Selbst enthalten und zeigen , warum Lehre Dimension ist die Antwort.

$C$$X$$S\subseteq X$$f$$f$$C$$S$

$\mathcal{T}(f)$$f$$(f,C)=min\{\ |S|\ | \ S\in \mathcal{T}(f) \}$$f$$_{min}(f)$$\mathcal{T}(f)$$(C)=$$_{f\in C}$$(f,C)$$C$

$f$$(f,C)$$_{min}(f)$$(C)$$f$