Uczenie się agnostyczne nad dowolnymi rozkładami

Niech będzie rozkładem na pary łańcuchów bitów / etykiet i niech będzie zbiorem funkcji o wartościach logicznych . Dla każdej funkcji , niech: $D$ $\{0,1\}^d\times \{0,1\}$ $C$ $f:\{0,1\}^d\rightarrow\{0,1\}$ $f \in C$ i niech: Powiedz, że algorytmagnostycznie uczy sięna dowolnym rozkładzie, jeśli dla dowolnegomoże ona z prawdopodobieństwemznajduje się funkcjaw taki sposób,

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)$

A

$A$

C

$C$

D

$D$

2 / 3

$2/3$

f

$f$

, biorąc pod uwagę czas i liczbę próbek z

które są ograniczone wielomianem

oraz

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$

Pytanie: Jakie klasy funkcji są znane z agnostycznego uczenia się w dowolnych rozkładach? $C$

Żadna klasa nie jest zbyt prosta! Wiem, że nawet monotoniczne sprzężenia nie są znane z agnostycznego uczenia się w dowolnych rozkładach, więc szukam po prostu nietrywialnych klas funkcji.

reference-request machine-learning lg.learning Aaron Roth
źródło

warto zwrócić uwagę na niewtajemniczonych, że uczenie się agnostyczne koncentruje się na przypadku, gdy OPT (C, D)> 0 (tj. masz niewłaściwą klasę hipotez

Suresh Venkat,

Słuszna uwaga. W szczególnym przypadku, gdy OPT (C, D) = 0, jest to nauka PAC i jest znacznie łatwiejsza. W przypadku uczenia agnostycznego gwarancja musi obowiązywać niezależnie od tego, jaka jest opcja OPT (C, D).

Aaron Roth,

Istnieje również przypadek „PAC z szumem klasyfikacyjnym”, w którym OPT (C, D)> 0, i mimo że masz odpowiednią klasę hipotez (możliwe do wykonania ustawienie), występuje pewien błąd, ponieważ etykiety są losowo odwracane z powodu hałasu ... I chciałbym, aby nazwy różnych ustawień były mniej mylące.

Lev Reyzin

to brzmi jak uczenie się agnostyczne z górną granicą OPT (C, D)

Suresh Venkat

Niezupełnie, ponieważ hałas nie może być arbitralny w klasyfikacyjnym modelu hałasu. Tak więc, jeśli istniał jakiś przeciwny wzorzec hałasu, który utrudniał uczenie się (lub znajdowanie empirycznego minimalizatora ryzyka) w modelu agnostycznym, może to nie występować często w modelu szumu klasyfikacyjnego (tj. Wpaść w parametr delta PAC).

Lev Reyzin

Odpowiedzi:

Jeśli żadna klasa nie jest zbyt prosta, oto niektóre agnostycznie możliwe do nauczenia klasy PAC. W odpowiedzi na komentarze przekreślono klasy o wielomianowo wielu hipotezach:

~~drzewa decyzyjne o stałej głębokości (i inne klasy mające tylko wiele hipotez)~~
~~$R^2$ $O(n^2)$~~
związki interwałów (programowanie dynamiczne)
$\log(k)\log\log(k)$ $n$
~~inne klasy hipotez w warunkach niskiego wymiaru.~~

Prawie wszystko inne jest trudne do (przynajmniej właściwie) agnostycznie nauki PAC.

Samouczek Adama Kalai na temat nauki agnostycznej może Cię również zainteresować.

Lew Reyzin
źródło

Dzięki. Tak więc drzewa decyzyjne o stałej głębokości, 2-wymiarowe hiperpłaszczyzny (zakładam, że inne ustawienia niskiego wymiaru, o których mówisz) należą do kategorii posiadającej tylko wielomianowo wiele funkcji, których można się nauczyć przez wyczerpanie. Parzystości w logach (k) loglog (k) bitach i związkach przedziałów są interesujące, ponieważ zawierają one wielobiegunowo wiele funkcji. Czy są tacy inni?

Aaron Roth,

Racja, chociaż w nieskończenie wiele jest hiperpłaszczyzn, po prostu O (n ^ 2) inaczej klasyfikuje punkty danych. Nie znam żadnych innych interesujących zajęć z góry mojej głowy, ale jeśli wymyślę / znajdę jakieś, zredaguję moją odpowiedź.

Lew Reyzin

więc chcesz mieć nieograniczone klasy wymiarów VC?

Suresh Venkat

nieograniczony wymiar VC z pewnością byłby interesujący, ale duże, skończone (dla ustalonych d) klasy są już niezwykle interesujące (i wydają się rzadkie)

Aaron Roth

@LevReyzin Link do wykładów Kalai nie działa. Czy mógłbyś to naprawić? Szukałem w sieci, ale nie mogłem tego znaleźć.

Anirbit