Czy jest jakaś praca łącząca uczenie maszynowe z bardziej egzotycznymi formami teorii złożoności?

13

Wydaje mi się, że eksperci od uczenia maszynowego / eksploracji danych znają P i NP, ale rzadko mówią o niektórych bardziej subtelnych klasach złożoności (np. NC, BPP lub IP) i ich implikacjach dla skutecznego analizowania danych. Czy jest jakaś ankieta na temat tej pracy?

cc.complexity-theory reference-request machine-learning Mike Izbicki
źródło
2
Nie znam żadnej ankiety, ale sprawdź ten wskaźnik do „uczenia się kwantowego” (# 5) z tego postu: blog.computationalcomplexity.org/2012/10/quantum-workshop.html
Suresh Venkat
Uczenie maszynowe regularnie atakuje bardzo trudne problemy, które są poza NP dla optymalizacji „globalnej”, ale wewnątrz NP lub mniej trudne niż dla optymalizacji „lokalnej”. więc cała koncepcja klasy złożoności staje się rozmyta, gdy optymalizuje się wyniki „wystarczająco dobre”, które są mierzone bardziej przez zależne od aplikacji pomiary jakości iw pewnym sensie nie są tak naprawdę znane z uruchamiania algorytmu (ów) ....
vzn
@vzn Dla mnie ta subtelność wydaje się tym bardziej powodem do zwracania uwagi na złożoność! Może dostarczyć bardzo interesujących informacji.
Mike Izbicki
z pewnością istnieją powiązania między teorią uczenia się, złożonością obwodu, kryptografią. ale jest to róg teorii uczenia się, który jest nieco usunięty z praktyki uczenia maszynowego. jeśli jesteś zainteresowany, mogę wymyślić kilka wskazówek
Sasho Nikolov
tak, inny przykład, BDD (diagramy decyzji binarnych) zostały użyte w algorytmach baz danych / eksploracji danych i mają silne powiązania ze złożonością obwodów. ale wydaje mi się, że całe pytanie może być nieco trudne, ponieważ wiele uczenia maszynowego jest pragmatyczne, a złożoność stosowanego ML jest często badana pośrednio / empirycznie poprzez analizę rzeczywistych implementacji algorytmów zamiast prób teoretycznego przewidywania lub ścisłej klasyfikacji.
vzn

Odpowiedzi:

3

Istnieje pewna nieodłączna różnica lub odmienność podejść między dwoma dziedzinami stosowanego uczenia maszynowego a TCS / teorią złożoności.

Oto ostatnie warsztaty na ten temat w Center for Computational Intractability, Princeton, z dużą ilością filmów.

Opis: Wiele obecnych podejść do uczenia maszynowego jest heurystycznych: nie możemy udowodnić, że są dobre ograniczenia zarówno pod względem wydajności, jak i czasu działania. Te małe warsztaty skupią się na projekcie algorytmów i podejść, których wydajność można dokładnie przeanalizować. Celem jest spojrzenie poza ustawienia, w których istnieją już możliwe do udowodnienia granice.

W TCS głównym obszarem badań nad „uczeniem się”, czasem nawet myląco nazywanym również „uczeniem maszynowym”, jest teoria PAC, która prawdopodobnie oznacza w przybliżeniu poprawność. jego początki lat 80. poprzedzają znacznie bardziej nowoczesne badania nad „uczeniem maszynowym”. wikipedia nazywa to częścią teorii komputerowego uczenia się w terenie . PAC często dotyczy wyników uczenia się wzorów logicznych przy danych próbkach rozkładów itp. Oraz osiągalnej dokładności uczenia się przy różnych algorytmach lub ograniczonych próbkach. Jest to badane w ścisły teoretyczny sposób z powiązaniami z klasami złożoności. Ale to nie tyle strona badań stosowanych i wikipedii na temat uczenia maszynowego nawet jej nie wymienia.

vzn
źródło
5
„połączenia z wikipedią”… czy rzeczywiście coś wiesz na ten temat? 1) wiki dla uczenia maszynowego ma sekcję Teoria, która prowadzi do teorii uczenia obliczeniowego strona 2) Praca teorii uczenia Valiant, Vapnik, Schapire, miała ogromny wpływ na praktykę uczenia maszynowego.
Sasho Nikolov