Funkcje, które nie są wydajnie obliczalne, ale można się ich nauczyć

Wiemy, że (patrz np. Twierdzenia 1 i 3 z [1]), z grubsza mówiąc, w odpowiednich warunkach, funkcje, które mogą być skutecznie obliczone przez maszynę Turinga w czasie wielomianowym („wydajnie obliczalne”), mogą być wyrażone przez wielomianowe sieci neuronowe z rozsądnymi rozmiarami, a zatem można się go nauczyć z wielomianową złożonością próbki („możliwą do nauczenia”) w dowolnych dystrybucjach wejściowych.

Tutaj „możliwe do nauczenia się” dotyczy tylko złożoności próbki, niezależnie od złożoności obliczeniowej.

Zastanawiam się nad bardzo ściśle powiązanym problemem: czy istnieje funkcja, która nie może być skutecznie obliczona przez maszynę Turinga w czasie wielomianowym („nie wydajnie obliczalna”), ale tymczasem można się jej nauczyć z wielomianową złożonością próbki („możliwą do nauczenia”) pod jakimikolwiek dystrybucjami wejściowymi?

[1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, „ O wydajności obliczeniowej szkoleniowych sieci neuronowych ”, 2014

cc.complexity-theory np-hardness machine-learning turing-machines lg.learning Minkov
źródło

Mam problem z „i dzięki temu można się nauczyć”. Istnieją bardzo wydajne funkcje obliczeniowe (powiedzmy, DFA), które są BARDZO trudne do nauczenia, nawet w przybliżeniu.

Aryeh

Prawdopodobnie nie ma to sensu, ale co z klasą (powiedzmy) -obsługowych funkcji logicznych? (Tj. Mniej więcej przypadkowa funkcja z każdą wartością niezależnie z prawdopodobieństwem ). Dla każdego nauka PAC w jednolitym rozkładzie jest trywialna (potrzebna jest próbka 0, stała funkcja jest dobrą hipotezą), ale wydaje się, że każdy algorytm oceny musiałby spędzić czas wielobiegunowy (ponieważ funkcja nie ma struktury). Najprawdopodobniej jednak nie rozumiem pytania.

2^{- \sqrt{n}}

$2^{-\sqrt{n}}$

1

$1$

2^{- \sqrt{n}}

$2^{-\sqrt{n}}$

ε > 2^{- \sqrt{n}}

$\varepsilon > 2^{-\sqrt{n}}$

0

$0$

Clement C.

Twoja terminologia jest nieco myląca. Kiedy mówimy „sprawnie się uczy”, zwykle mamy na myśli wydajność obliczeniową. Samo powiedzenie „do nauczenia się” jest wystarczające, aby sugerować wydajność próbki.

Lev Reyzin

@Minkov Aby nauczyć się PAC, powinieneś uczyć się w odniesieniu do każdej dystrybucji. W przeciwnym razie pytanie nie jest interesujące (jak zauważa Clement).

Lew Reyzin

Dlaczego ludzie głosują na zakończenie? Myślę, że to głębokie i subtelne pytanie!

Aryeh,

Odpowiedzi:

Sformalizuję wariant tego pytania, w którym „wydajność” zostaje zastąpiona przez „obliczalność”.

Niech będzie klasą koncepcyjną wszystkich języków rozpoznawalną przez maszyny Turinga na stanach lub mniej. Ogólnie rzecz biorąc, dla i problem oceny jest nierozstrzygalny. $C_n$ $L\subseteq\Sigma^*$ $n$ $x\in\Sigma^*$ $f\in C_n$ $f(x)$

Załóżmy jednak, że mamy dostęp do (właściwej, możliwej do zrealizowania) wyroczni uczenia się PAC dla . Oznacza to, że dla każdego wyrocznia żąda oznaczonej próbki o wielkości takiej, że przy założeniu, że taka próbka została pobrana z nieznanego rozkładu , wyrocznia wypisuje hipotezę która z prawdopodobieństwem co najmniej ma błąd generalizacji nie większy niż . Pokażemy, że ta wyrocznia nie jest obliczalna przez Turinga. $A$ $C_n$ $\epsilon,\delta>0$ $m_0(n,\epsilon,\delta)$ $D$ $A$ $\hat f\in C_n$ $1-\delta$ $D$ $\epsilon$

Faktycznie, pokażemy, że prostszym problemem jest nierozstrzygalny: Jeden z określenia, biorąc pod uwagę oznaczone próbki , czy istnieje zgodny z . Załóżmy (aby uzyskać sprzeczność), że jest maszyną Turinga, która decyduje o problemie konsystencji. $S$ $f\in C_n$ $S$ $K$

Tworzymy następujące konwencje notacyjne. Zidentyfikuj pomocą za pomocą zwykłego porządku leksykograficznego. Dla mówimy, że TM „S-drukuje” jeśli przyjmuje wszystkie ciągi w odpowiadające indeksom st i nie zaakceptuj (prawdopodobnie nie zatrzymując) dowolny ciąg odpowiadający indeksom . Ponieważ (z założenia) jest rozstrzygalne, wynika z tego, że funkcja , zdefiniowana jako najmniejsza taka, że niektóre TM w $\Sigma^*$ $\mathbb{N}=\{0,1,2,\ldots\}$ $x\in\{0,1\}^*$ $M$ $x$ $\Sigma^*$ $i$ $x_i=1$ $x_i=0$ $K$ $\tilde K:x\mapsto k$ $k$ $C_k$ S-print , jest obliczalny przez Turinga. Wynika z tego, że funkcja , która odwzorowuje na najmniejszy (leksykograficzny) ciąg taki, że , jest również obliczalna. $x$ $g:k\mapsto x$ $k\in\mathbb{N}$ $x\in\{0,1\}^*$ $\tilde K(x)>k$

Teraz zdefiniuj TM w następujący sposób: S-drukuje , gdzie to kodowanie , oznacza Długość łańcucha i rekursja twierdzenie powołano się wskazanie na istnienie takiej . Zatem ma pewną długość kodowania,, i S-drukuje jakiś ciąg, . Z konstrukcji , a więc nie może być wydrukowany w S przez żadną TM o długości opisu $M$ $M$ $g(|\langle M\rangle|)$ $\langle M\rangle$ $M$ $|x|$ $M$ $M$ $\ell=|\langle M\rangle|$ $x_M\in\{0,1\}^*$ $\tilde K(x_M)>\ell$ $x_M$ $\ell$ lub krócej. A jednak jest to zdefiniowane jako wydruk S-print TM o długości opisu --- sprzeczność. $\ell$

Aryeh
źródło

Wyzwanie: przekonwertować mój argument „nieskończony” poprzez obliczalność na finalny poprzez wydajność. Myślę, że odpowiedź na pytanie @ minkov jest przecząca: nie można skutecznie nauczyć się klasy funkcji, której nie można skutecznie ocenić. Myślę, że tak będzie nadal, jeśli wyjdziesz poza właściwy lub możliwy do zrealizowania PAC.

Aryeh