Agnostisches Lernen über beliebige Verteilungen

$D$ $\{0,1\}^d\times \{0,1\}$ $C$ $f:\{0,1\}^d\rightarrow\{0,1\}$ $f \in C$

e r r (f, D) = \underset{(x, y) \sim D}{Pr} [f (x) \neq y]

$err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]$

O P T (C, D) = min_{f \in C} e r r (f, D)

$OPT(C,D) = \min_{f \in C}\ err(f,D)$ Angenommen, ein Algorithmus lernt

agnostisch über jede Verteilung, wenn er für jedes

mit einer Wahrscheinlichkeit von

eine Funktion

so dass

, gegebene Zeit und eine Anzahl von Proben aus

, die durch ein Polynom in

und

A

$A$

C

$C$

D

$D$

2 / 3

$2/3$

f

$f$

e r r (f, D) \leq O P T (C, D) + ϵ

$err(f,D) \leq OPT(C,D) + \epsilon$

D

$D$

d

$d$

1 / ϵ

$1/\epsilon$

Frage: Welche Funktionsklassen $C$ sind bekanntermaßen über beliebige Verteilungen agnostisch lernbar?

Keine Klasse ist zu einfach! Ich weiß, dass selbst monotone Konjunktionen nicht über beliebige Verteilungen agnostisch lernbar sind, deshalb suche ich nur nach nichttrivialen Funktionsklassen.

reference-request machine-learning lg.learning Aaron Roth
quelle

Für die Uneingeweihten ist es erwähnenswert, dass sich das agnostische Lernen auf den Fall konzentriert, wenn OPT (C, D)> 0 ist (dh Sie haben die falsche Hypothesenklasse

Suresh Venkat,

Guter Punkt. In dem speziellen Fall, wenn OPT (C, D) = 0 ist, ist dies PAC-Lernen und viel einfacher. Für agnostisches Lernen muss die Garantie unabhängig von OPT (C, D) gelten.

Aaron Roth

Es gibt auch den Fall "PAC mit Klassifizierungsrauschen", in dem OPT (C, D)> 0 ist, und obwohl Sie die richtige Hypothesenklasse haben (realisierbare Einstellung), gibt es einen Fehler, weil die Beschriftungen aufgrund von Rauschen zufällig umgedreht werden ... I. Ich wünschte, die Namen der verschiedenen Einstellungen wären weniger verwirrend.

Lev Reyzin

das klingt nach agnostischem Lernen mit einer Obergrenze für OPT (C, D)

Suresh Venkat

Nicht ganz, weil das Rauschen im Klassifizierungsrauschmodell nicht willkürlich sein darf. Wenn es also ein kontroverses Rauschmuster gibt, das das Lernen (oder das Finden des empirischen Risikominimierers) im agnostischen Modell erschwert, tritt es im Klassifizierungsrauschmodell möglicherweise nicht häufig auf (dh fällt in den PAC-Delta-Parameter).

Lev Reyzin

Antworten:

Wenn keine Klasse zu einfach ist, finden Sie hier einige agnostisch PAC-lernbare Klassen. In Reaktion auf die Kommentare werden die Klassen mit polynomiell vielen Hypothesen durchgestrichen:

~~Entscheidungsbäume mit konstanter Tiefe (und andere Klassen mit nur mehreren Hypothesen)~~
~~Hyperebenen in (nur -Hypothesen, die unterschiedliche Markierungen erzeugen) $R^2$ $O(n^2)$~~
Intervallverbände (dynamische Programmierung)
Parität auf einigen der ersten von Bits (siehe dies und das ) $\log(k)\log\log(k)$ $n$
~~andere Hypothesenklassen in niedrigdimensionalen Umgebungen.~~

So ziemlich alles andere ist NP-schwer (zumindest richtig) agnostisch PAC zu lernen.

Das Tutorial von Adam Kalai zum agnostischen Lernen könnte Sie ebenfalls interessieren.

Lev Reyzin
quelle

Vielen Dank. Entscheidungsbäume mit konstanter Tiefe, zweidimensionale Hyperebenen (ich nehme die anderen niedrigdimensionalen Einstellungen an, auf die Sie sich beziehen) fallen also alle in die Kategorie, nur polynomiell viele Funktionen zu haben, die durch Erschöpfung gelernt werden können. Paritäten auf log (k) loglog (k) -Bits und Intervallverbindungen sind insofern interessant, als sie superpolynomiell viele Funktionen enthalten. Gibt es andere wie diese?

Aaron Roth

Richtig, obwohl es in R ^ 2 unendlich viele Hyperebenen gibt, klassifiziert nur O (n ^ 2) die Datenpunkte unterschiedlich. Ich kenne keine anderen interessanten Klassen, aber wenn ich an eine denke / sie finde, werde ich meine Antwort bearbeiten.

Lev Reyzin

Sie möchten also unbegrenzte VC-Dimensionsklassen?

Suresh Venkat

Eine unbegrenzte VC-Dimension wäre sicherlich interessant, aber große endliche (für feste d) Klassen sind bereits äußerst interessant (und scheinen selten zu sein)

Aaron Roth,

@ LevReyzin Der Link zu den Kalai-Vorlesungen funktioniert nicht. Könnten Sie das bitte beheben? Ich habe im Internet gesucht, konnte dies aber auch nicht finden.

Anirbit