Niektóre tło: Chciałbym znaleźć „mniej znane” dolne granice (lub wyniki twardości) dla problemu Uczenie się z błędami (LWE) i ich uogólnienia, takie jak Uczenie się z błędami przez pierścienie. W celu uzyskania szczegółowych definicji itp. Oto miła ankieta przeprowadzona przez Regev:...
Dobrze wiadomo, że w przypadku klasy koncepcyjnej CC\mathcal{C} o wymiarze VC wystarczy uzyskać przykłady oznaczone PAC learn . Nie jest dla mnie jasne, czy algorytm uczenia się PAC (który wykorzystuje tak wiele próbek) jest właściwy, czy niewłaściwy? W podręcznikach Kearnsa i Vazirani oraz...
Oto problem o smaku podobnym do nauki junt: Dane wejściowe: Funkcja , reprezentowana przez wyrocznię członkowską, tzn. Wyrocznię, która dała , zwraca .x f ( x )fa: { 0 , 1 }n→ { - 1 , 1 }f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\}xxxfa( x )f(x)f(x) Cel: Znajdź podmoduł S.SS o wartości { 0 ,...
Niech będzie rozkładem na pary łańcuchów bitów / etykiet { 0 , 1 } d × { 0 , 1 } i niech C będzie zbiorem funkcji o wartościach logicznych f : { 0 , 1 } d → { 0 , 1 } . Dla każdej funkcji f ∈ C , niech: e r r ( f , D ) = Pr ( x , y )DDD{0,1}d×{0,1}{0,1}d×{0,1}\{0,1\}^d\times...
Moje pytanie jest trochę ogólne, więc wymyślam fajną historię, aby to uzasadnić. Zrób ze mną, jeśli to nie jest realistyczne ;-) Fabuła Pan X, szef działu bezpieczeństwa komputerowego w dużej firmie, jest nieco paranoiczny: wymaga od wszystkich pracowników zmiany hasła raz w miesiącu, aby...
Dane ze świata rzeczywistego czasami mają naturalną liczbę klastrów (próba klastrowania ich w liczbę klastrów mniejszą niż jakaś magiczna k spowoduje drastyczny wzrost kosztu klastrowania). Dzisiaj uczestniczyłem w wykładzie dr Adama Meyersona, który nazwał tego typu danymi „danymi możliwymi do...
Dana Angluin ( 1987 ; pdf ) definiuje model uczenia się z zapytaniami o członkostwo i teoriami (kontrprzykłady do proponowanej funkcji). Pokazuje, że zwykły język reprezentowany przez minimalny DFA z stanów jest możliwy do nauczenia się w czasie wielomianowym (gdzie proponowane funkcje to DFA) z...
Angluin i Laird ('88) sformalizowali uczenie się z przypadkowo uszkodzonymi danymi w modelu „PAC z losowym szumem klasyfikacyjnym” (lub hałaśliwym PAC). Model ten jest podobny do PAC uczenia , z wyjątkiem etykiet z przykładów podanych w uczącej są uszkodzone (grzbiet), niezależnie w sposób losowy,...
Ostatnio czytałem sporo artykułów CoLT. Chociaż nie walczę z poszczególnymi artykułami (przynajmniej nie bardziej niż zwykle walczę z innymi artykułami teoretycznymi), nie czuję, że dobrze rozumiem tę dziedzinę jako całość. Czy istnieje standardowy tekst, ankiety lub notatki z wykładów dotyczące...
Po pierwsze, wciąż nie jestem pewien, czy cstheory jest dobrze przystosowana do tego pytania, więc nie obrażę się, jeśli tłum uzna, że tak nie jest ... W marketingu w wyszukiwarkach interesujących jest kilka problemów. Zaprojektowanie uczciwych (i rentownych) mechanizmów aukcyjnych oraz...
Które klasyfikatory uczenia maszynowego są najbardziej równoległe? Jeśli miałbyś trudny problem z klasyfikacją, ograniczony czas, ale przyzwoitą sieć LAN komputerów do pracy, z jakimi klasyfikatorami byś spróbował? Z drugiej strony wygląda mi to na kilka standardowych klasyfikatorów, które znam w...
Jaki jest najnowszy wynik w zakresie złożoności zapytań dotyczących prawidłowych formuł uczenia się PAC 2-DNF z przykładowymi zapytaniami i w jednolitym rozkładzie ? A może jakieś nietrywialne ograniczenia? Ponieważ w ogóle nie znam teorii uczenia się, a to pytanie jest motywowane inną dziedziną,...
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).nnnp,qp,qp, qϵϵ\epsilon Teraz każda funkcja w tej klasie jest zdefiniowana przez zbiór indeksów i jest oceniana w...
Znam dobrze teorię VC-Dimension, ale teraz patrzę na ostatnie (ostatnie 10 lat) postępy w statystycznej teorii uczenia się: (lokalne) średnie Rademachera, Lemma klasy skończonej Massarta, Liczby obejmujące, Łańcuchy, Łańcuch Dudleya Twierdzenie, Pseudodimension, Fat Shattering Dimension, Numery...
Dobrze wiadomo, że do klasycznego uczenia się PAC, przykłady są konieczne, aby osiągnąć granicę błędu whp, gdzie jest wymiarem VC klasy koncepcyjnej.Ω ( d/ ε)Ω(re/ε)\Omega(d/\varepsilon)εε\varepsilonrered Czy wiadomo, że w przypadku agnostyki potrzebne są przykłady ?Ω ( d/...
W szczególności proszę o zasoby, aby dowiedzieć się o systemach uczenia maszynowego, które mogą aktualizować ich odpowiednie sieci przekonań (lub ich odpowiedniki) podczas pracy. Natknąłem się nawet na kilka, ale nie udało mi się ich dodać do zakładek. Jak można sobie wyobrazić, wyszukiwanie w...
Załóżmy, że mam punktów w . Indukują one diagram Voronoi. Jeśli przypiszę do każdego z punktów etykietę , wywołają one funkcję binarną na . Pytanie: jaki jest wymiar VC wszystkich takich możliwych funkcji binarnych indukowanych przez niektóre punkty i pewne oznakowanie tych...
Mam na myśli w szczególności rodziny języków, które dopuszczają dowolnie długie ciągi znaków - a nie koniunkcje na n bitach lub listach decyzyjnych lub jakimkolwiek innym „prostym” języku zawartym w {0,1} ^ n. Pytam o zwykłe języki „teoretyków automatycznych”, a nie teoretyków „logicznych”: coś w...
Losowe lasy mają wśród praktyków reputację jednych z najbardziej skutecznych technik klasyfikacji. Jednak nie spotykamy ich zbyt wiele w literaturze teoretycznej, z której, jak sądzę, brak głębokich wyników teoretycznych. Gdyby ktoś chciał zagłębić się w tę teorię, od czego by to się...