Pytanie do nauki parzystości

Zdefiniujmy klasę funkcji w zbiorze bitów. Napraw dwa rozkłady które są „rozsądnie” różne od siebie (jeśli chcesz, ich odległość wariacyjna wynosi co najmniej lub coś podobnego). $n$ $p, q$ $\epsilon$

Teraz każda funkcja w tej klasie jest zdefiniowana przez zbiór indeksów i jest oceniana w następujący sposób: Jeśli parzystość wybranych bitów wynosi 0, zwróć losową próbkę z , w przeciwnym razie zwróć losową próbkę z . $f$ $k$ $S$ $p$ $q$

Problem : Załóżmy, że mam dostęp do wyroczni do niektórych z tej klasy i chociaż znam (lub inną miarę odległości), nie znam i . $f$ $\epsilon$ $p$ $q$

Czy są jakieś ograniczenia co do liczby połączeń, które muszę wykonać, aby PAC-learn ? Przypuszczalnie moja odpowiedź będzie w kategoriach i . $f$ $n, k$ $\epsilon$

Uwaga : nie określiłem domeny wyjściowej. Znowu jestem elastyczny, ale na razie powiedzmy, że i są zdefiniowane w domenie skończonej . Zasadniczo byłbym również zainteresowany przypadkiem, gdy są one zdefiniowane powyżej (na przykład, jeśli są Gaussowcami) $p$ $q$ $[1..M]$ ${\mathbb R}$

lg.learning

— Suresh Venkat
źródło

Nie jestem pewien, czy rozumiem model. Co określasz w wywołaniu wyroczni? Czy przykłady zawsze pochodzą z rozkładu określonego przez cel?

— Lew Reyzin

W wywołaniu wyroczni wywołujesz funkcję f (), która zwraca wartość.

— Suresh Venkat

Więc w zależności od funkcji docelowej

, do generowania przykładów zawsze używa się

lub

? (Zakładam, że uczysz się jakiejś klasy

)

f \in F

$f \in F$

p

$p$

q

$q$

F

$F$

— Lew Reyzin

Tak to jest poprawne. problemem jest to, aby dowiedzieć się, który z nich (lub nauki parzystości wykorzystywane)

— Suresh Venkat

Nie jestem pewien, w jaki sposób dostosowujesz model PAC do tego modelu. Wydaje się jednak, że wystarczy odróżnić

z prawdopodobieństwem

a następnie można uzyskać wartości

dla

liniowo niezależnego

i użyć eliminacji gaussowskiej, aby znaleźć

(ponieważ

jest liniowy). na przykład łatwe będzie rozróżnienie dwóch dobrze oddzielonych gaussów.

p

$p$

q

$q$

1 - 1 / (2 k)

$1 - 1/(2k)$

f (x)

$f(x)$

k

$k$

x

$x$

f

$f$

f

$f$

— Sasho Nikolov

Dyskusja w komentarzach poniżej wskazuje, że źle zrozumiałem pytanie. Moja odpowiedź jest oparta na Oracle sobą nie wejście i powrót , gdzie lub , w zależności od . Najwyraźniej nie o to pytano. $(x, f(x))$ $x \sim p$ $x \sim q$ $f \in F$

Ponieważ rozkład celu jest ustalony dla każdego celu , obowiązuje górna granica próbki PAC (wynika to z faktu, że rozkład celu dla tej granicy może nawet całkowicie zależeć od ). Stąd $f^* \in F$ $f^*$ przykłady powinny wystarczyć, aby znaleźć hipotezę błęduwp. Uwaga - po zapoznaniu się z tymi przykładami należy znaleźć spójną hipotezę zi może to nie być wykonalne.

m \leq \tilde{O} (\frac{1}{ϵ} (V C (F) + \log (1 / δ)))

$m \le \tilde{O}\left(\frac{1}{\epsilon}\left(\mathrm{VC}(F) + \log(1/\delta) \right) \right)$

\leq ϵ

$\le \epsilon$

\geq 1 - δ

$\ge 1-\delta$

F

$F$

Z drugiej strony, można uzyskać prawie pasującą dolną granicę, nawet w przypadku , rozkład równomierny, gdzie wciąż wymagane są przykłady (można to nieco poprawić) . $p=q=U$ $m \ge \Omega(\mathrm{VC}(F))$

Odległość wariacyjna między i , a także mogą odgrywać rolę w małej szczelinie między tymi granicami, ale wątpię w to. $p$ $q$ $k$

— Lew Reyzin
źródło

Typowe ustawienie uczenia PAC ma wyrocznię

która pobiera próbkę

z rozkładu

i zwraca

. To nie jest ustawienie opisane w pytaniu Suresha lub postu na blogu, który go zainspirował: bit.ly/YtwdST . W obu przypadkach wyrocznia jest funkcją

, a uczący się może przesłać dowolny element z zestawu instancji (ciągi bitów o długości

(f, D)

$(f,D)$

x

$x$

D

$D$

(x, f (x))

$(x, f(x))$

f

$f$

n

$n$ ). Lev, czy twoja odpowiedź zakłada wyrocznię pierwszego typu, czy drugiego typu? Jeśli drugi typ, nadal mówimy o uczeniu się PAC?

— Keki Burjorjee 10.04.13

Widzę. PAC, w "wyrocznią" zwykle są traktowane jako przycisk, który powraca

gdzie

. Opisać Oracle jest nazywany „query członków” do

. Moja odpowiedź dotyczy tylko tego pierwszego. Jeśli pytasz tylko o członkostwo, jak możesz znaleźć informacje na temat

lub

za pomocą frameworka Suresh? Powiedzmy

dla uproszczenia.

(x, f (x))

$(x, f(x))$

x \sim D

$x \sim D$

f

$f$

p

$p$

q

$q$

p = q

$p=q$

— Lew Reyzin

Dziękuję za to wyjaśnienie. Tak więc w przypadku opisanym przez Suresha wyrocznia „zapytanie członkostwa” działa w następujący sposób (zakładam, że umieściłeś ten byt w cudzysłowie, ponieważ wyrocznia może zwrócić prawdziwą wartość, a nie tylko wartość logiczną jest członkiem / nie-członkiem- odpowiedź członka): jeśli parzystość skutecznych atrybutów wynosi 1, wówczas zwracany wynik jest pobierany z rozkładu

. W przeciwnym razie wynik jest pobierany z rozkładu

. Jest dodatkowy zmarszczek. Wyrocznia pamięta wszystkie poprzednie odpowiedzi i zwraca je, jeśli zapytano o to samo wejście. Innymi słowy, jest deterministyczny.

p

$p$

q

$q$

— Keki Burjorjee

Nie rozumiem. Jeśli wyrocznia jest po prostu funkcją

a zapytasz ją, podając jej

, to czy nie zwraca po prostu

? W jaki sposób

lub

wchodzi do gry, jeśli uczeń sam generuje

? Myślę, że przez cały czas nie rozumiałem tego podstawowego punktu ...

f

$f$

x

$x$

f (x)

$f(x)$

p

$p$

q

$q$

x

$x$

— Lew Reyzin

Dla

pseudokod wyroczni dla problemu z „zmarszczeniem” podano na dole tego komentarza reddit: bit.ly/XvVMC4 ( ). Nie mogę wstawić kodu, ponieważ SE nie zezwala na nowe wiersze w komentarzach. Aby uzyskać wersję „bez pomarszczeń”, po prostu usuń wiersz .

p = N (+ 0.25, 1)

$p=\mathcal N(+0.25, 1)$

q = N (- 0.25, 1)

$q = \mathcal N(-0.25, 1)$ def fitness() ...random_number_generator.set_seed(x)

— Keki Burjorjee