O statusie zdolności uczenia się w

Próbuję zrozumieć złożoność funkcji wyrażanych przez bramki progowe, co doprowadziło mnie do . W szczególności interesuje mnie to, co obecnie wiadomo na temat uczenia się w , ponieważ nie jestem ekspertem w tej dziedzinie. $\mathsf{TC}^0$ $\mathsf{TC}^0$

Do tej pory odkryłem:

Wszystkie można wyciągnąć w quasipolynomial czasie w jednorodnym rozkładzie przez Linial-Mansour-Nisana . $\mathsf{AC}^0$
W ich pracy wskazano również, że istnienie generatora funkcji pseudolosowych uniemożliwia uczenie się, a to, w połączeniu z późniejszym wynikiem Naor-Reingolda, że dopuszcza PRFG, sugeruje, że reprezentuje granice uczenia się (przynajmniej w PAC -sens) $\mathsf{TC}^0$ $\mathsf{TC}^0$
Istnieje artykuł z 2002 roku autorstwa Jacksona / Klivansa / Servedio, który może nauczyć się fragmentu (z co najwyżej bramkami polilogarytmicznymi). $\mathsf{TC}^0$

Robiłem zwykle Google Scholaring, ale mam nadzieję, że zbiorowa mądrość cstheory może dać szybszą odpowiedź:

Czy to, co opisałem, jest najnowszym stanem wiedzy na temat złożoności uczenia się (w odniesieniu do których klas uczą efektywnych uczniów)? I czy istnieje dobra ankieta / odniesienie, która przedstawia aktualny stan krajobrazu?

cc.complexity-theory reference-request cr.crypto-security lg.learning boolean-functions Suresh Venkat
źródło

+1 fajne pytanie. Czy Lance nie miał kiedyś powiązanego posta na blogu?

Kaveh

Czy masz na myśli ten (gościnny post Ryana O'Donnella): blog.computationalcomplexity.org/2005/08/…

Suresh Venkat

Może ten: blog.computationalcomplexity.org/2013/08/…

Suresh Venkat

Jest prawdopodobne, że w NC0 są generatory pseudolosowe .

$\:$ (W szczególności uważam, że mało prawdopodobne jest, aby generator pseudolosowy uniemożliwiał naukę).

$\;\;\;$ Z drugiej strony istnienie map

x \mapsto F (r, x)

$\: x\mapsto F(r\hspace{-0.03 in},x) \:$ dla rodziny funkcji pseudolosowych

uniemożliwia naukę.

F

$F$

Linial-Mansour-Nisan pokazują, że

można się nauczyć w jednolitym rozkładzie w czasie quasipolynomialnym . Kharitinov wykazał, że gdyby quasipolynomial został ulepszony do wielomianu, dałoby to podwykładniczy algorytm czasowy do faktorowania liczb całkowitych Bluma.

{AC}^{0}

$\text{AC}^0$

Robin Kothari,

Odpowiedzi:

Najważniejsze, czego brakuje na twojej liście, to piękny artykuł Klivansa i Sherstova z 2006 roku . Pokazują tam, że uczenie się PAC nawet obwodów progowych na głębokości 2 jest tak trudne, jak rozwiązanie przybliżonego problemu najkrótszego wektora.

Scott Aaronson
źródło

Jaki jest najszybszy znany czas nauki takich obwodów LTF? (lub cokolwiek w

)

T C^{0}

$TC^0$

gradstudent

Głębokości-2 TC0 prawdopodobnie nie można się nauczyć PAC w podwykładniczym czasie w rozkładzie równomiernym z losowym dostępem do wyroczni. Nie znam odniesienia do tego, ale oto moje rozumowanie: wiemy, że parzystości można zaledwie nauczyć się w tym sensie, że klasa funkcji parzystości jest możliwa do nauczenia się sama w sobie, ale kiedy już to zrobisz, zrobisz prawie wszystko (takie jak ponieważ dodaje trochę losowego szumu), przestaje być możliwy do nauczenia. Ale TC0 głębokości-2 jest wystarczająco silny, aby reprezentować wszystkie funkcje parzystości i wystarczająco silny, aby reprezentować zaburzone wersje parzystości, więc myślę, że można bezpiecznie zgadywać, że TC0 głębokości-2 nie można się nauczyć.

Jednak parytetów i hałaśliwych parytetów można się nauczyć w czasie wielomianowym, jeśli otrzymamy wyrocznię członkowską. Warto więc sprawdzić, czy można nauczyć się głębi 2 TC0 za pomocą wyroczni członkowskiej. Nie byłbym całkowicie zaskoczony, jeśli odpowiedź brzmi „tak”. Z drugiej strony wątpię, aby TC0 o głębokości można było nauczyć się za pomocą zapytań członkowskich. Może warto zacząć od AC0 [6] (lub nawet AC0 [2]) i zacząć od tego miejsca. $O(1)$

pierożek Mobiusa
źródło