Algorytmy modelu statystycznego zapytania?

Zadałem to pytanie w sprawdzonych krzyżowo pytaniach i odpowiedziach, ale wydaje się, że jest ono bardziej związane z CS niż ze statystykami.

Czy możesz podać mi przykłady algorytmów uczenia maszynowego, które uczą się na podstawie właściwości statystycznych zestawu danych, a nie samych indywidualnych obserwacji, tj. Wykorzystują statystyczny model zapytań ?

Niemal każdy algorytm działający w modelu PAC (z wyjątkiem algorytmów uczących się przez kontrolę parzystości) może zostać przystosowany do pracy w modelu SQ. Patrz np. Ten artykuł Blum i in. w którym kilka popularnych algorytmów jest tłumaczonych na ich odpowiedniki SQ ( Practical Privacy: the SuLQ framework ). Artykuł zasadniczo dotyczy „prywatności”, ale można to zignorować - tak naprawdę jest to po prostu implementacja algorytmów z zapytaniami SQ.

Z drugiej strony uczenie się agnostyczne jest znacznie trudniejsze w modelu SQ: pomijając kwestie obliczeniowe (choć są one ważne), złożoność próby wymagana do uczenia agnostycznego jest mniej więcej taka sama, jak wymagana do dokładnego uczenia się, jeśli faktycznie masz dostęp do punkty danych. Z drugiej strony, uczenie się agnostyczne staje się znacznie trudniejsze w modelu SQ - zwykle będziesz musiał zadawać wiele wielobiegunowo zapytań, nawet dla klas tak prostych jak rozdźwięki monotoniczne. Zobacz ten artykuł Feldmana ( Pełna charakterystyka uczenia się zapytań statystycznych wraz z aplikacjami do ewolucji ) lub ten ostatni artykuł Gupty i in. ( Zwolnienia prywatne i bariera zapytań statystycznych )

Model SQ został opracowany w celu analizy uczenia się z tolerancją na hałas - mianowicie algorytm, który działa poprzez tworzenie zapytań statystycznych, będzie działał w ramach klasyfikacji hałasu. Jak powiedział Aaron, większość algorytmów PAC, które okazały się mieć odpowiedniki w modelu SQ. Jedynym wyjątkiem jest eliminacja Gaussa, która jest wykorzystywana w parytetach uczenia się (można nawet użyć sprytnej aplikacjinauczyć się logarytmów (n) parytetów wielkości loglogów (n) w modelu szumu klasyfikacyjnego). Wiemy również, że parzystości nie można się nauczyć za pomocą zapytań statystycznych i okazuje się, że najbardziej interesujące klasy, takie jak drzewa decyzyjne, mogą symulować funkcje parzystości. Dlatego w naszym dążeniu do uzyskania algorytmów uczenia się PAC dla wielu interesujących klas (takich jak drzewa decyzyjne, DNF itp.) Wiemy, że potrzebujemy zasadniczo nowych algorytmów uczenia się, które nie działają w statystycznym modelu zapytań.

Chciałbym nieco wyjaśnić odpowiedź Aarona. Niemal każdy algorytm agnostyczny (ponownie, z wyjątkiem czegokolwiek, co wykorzystuje eliminację Gaussa) może zostać uruchomiony w modelu SQ. Oczywiście uczenie się agnostyczne jest trudniejsze niż uczenie się bez agnostyki, ale jest to niezależne pytanie.