Czy techniki uczenia maszynowego są „algorytmami aproksymacyjnymi”?

Niedawno pojawiło się pytanie typu ML dotyczące wymiany stosu cstheory, a ja opublikowałem odpowiedź zalecającą metodę Powella, pochodzenie gradientu, algorytmy genetyczne lub inne „algorytmy aproksymacyjne”. W komentarzu ktoś powiedział mi, że te metody to „heurystyka”, a nie „algorytmy aproksymacyjne” i często nie zbliżały się do teoretycznego optimum (ponieważ „często utknęły w lokalnych minimach”).

Czy inni się z tym zgadzają? Wydaje mi się również, że istnieje poczucie, że algorytmy heurystyczne mogą być bliskie teoretycznym optymalnym, jeśli są skonfigurowane do eksploracji dużej części przestrzeni wyszukiwania (np. Ustawianie parametrów / małych rozmiarów kroków), chociaż nie mam nie widziałem tego w gazecie. Czy ktoś wie, czy zostało to wykazane lub udowodnione w gazecie? (jeśli nie dla dużej klasy algorytmów, może dla małej klasy powiedz NN itp.)

Myślę, że łączysz wiele ważnych pojęć. Pozwól, że wyjaśnię kilka rzeczy:

• Istnieją metody metaheurystyczne, które są iteracyjnymi próbami ulepszenia rozwiązania kandydującego. Przykładami tego są wyszukiwanie tabu, symulowane wyżarzanie, algorytmy genetyczne itp. Zauważ, że chociaż może być wiele przypadków, w których te metody działają dobrze, nie ma głębokiego zrozumienia, kiedy te metody działają, a kiedy nie. A co ważniejsze, gdy nie dojdą do rozwiązania, możemy być arbitralnie daleko od niego. Problemy rozwiązywane metodami metaheurystycznymi mają z natury charakter dyskretny, ponieważ istnieją o wiele lepsze narzędzia do radzenia sobie z ciągłymi problemami. Ale od czasu do czasu widzisz także metaheurystykę ciągłych problemów.

• Istnieją numeryczne metody optymalizacji, ludzie w tej społeczności dokładnie badają naturę funkcji, która ma być zoptymalizowana, i ograniczenia rozwiązania (w grupach takich jak optymalizacja wypukła, programowanie kwadratowe, programowanie liniowe itp.) I stosują algorytmy, które zostały pokazane do pracy dla tego typu funkcji i tego rodzaju ograniczeń. Kiedy ludzie w tym obszarze mówią „pokazani do pracy”, mają na myśli dowód. Sytuacja polega na tym, że tego rodzaju metody działają w ciągłych problemach. Ale kiedy twój problem należy do tej kategorii, jest to zdecydowanie narzędzie do użycia.

• Istnieją dyskretne metody optymalizacji, które są z natury rzeczy związane z algorytmami dobrze zbadanymi dyskretnymi problemami: takimi jak najkrótsze ścieżki, maksymalny przepływ itp. Ludzie w tym obszarze dbają również o to, by ich algorytmy naprawdę działały (dowody). W tej grupie jest grupa osób, które badają naprawdę trudne problemy, dla których nie oczekuje się szybkiego algorytmu. Następnie badają algorytmy aproksymacyjne, które są szybkimi algorytmami, dla których są w stanie wykazać, że ich rozwiązanie mieści się w stałym współczynniku prawdziwego optimum. Nazywa się to „algorytmami aproksymacyjnymi”. Ci ludzie pokazują również swoje wyniki jako dowody.

Więc ... aby odpowiedzieć na twoje pytanie, nie sądzę, że metaheurystyki są algorytmami aproksymacyjnymi. Nie wydaje mi się to czymś związanym z opinią, to po prostu fakt.

Uczenie maszynowe często zajmuje się optymalizacją funkcji, która ma wiele lokalnych minimów. Dobrym przykładem są sprzężone sieci neuronowe z ukrytymi jednostkami. Niezależnie od tego, czy funkcje te są dyskretne czy ciągłe, nie ma metody, która osiąga globalne minimum i zatrzymuje się. Łatwo jest udowodnić, że nie ma ogólnego algorytmu znajdowania globalnego minimum funkcji ciągłej, nawet jeśli jest ona jednowymiarowa i gładka (ma nieskończenie wiele pochodnych). W praktyce wszystkie algorytmy uczenia sieci neuronowych utknęły w lokalnym minimum. Łatwo to sprawdzić: utwórz losową sieć neuronową, zrób duży zestaw jej odpowiedzi na losowe dane wejściowe, a następnie spróbuj nauczyć się innej sieci neuronowej o tej samej architekturze, aby skopiować odpowiedzi. Chociaż istnieje idealne rozwiązanie, ani propagacja wsteczna, ani żaden inny algorytm uczenia się nie będzie w stanie go wykryć,

Niektóre metody uczenia się, takie jak symulowane algorytmy wyżarzania lub algorytmy genetyczne, badają wiele lokalnych minimów. Dla funkcji ciągłych istnieją metody takie jak opadanie gradientu, które znajdują najbliższe lokalne minimum. Są znacznie szybsze, dlatego są szeroko stosowane w praktyce. Ale biorąc pod uwagę wystarczającą ilość czasu, pierwsza grupa metod przewyższa późniejszą pod względem błędu zestawu treningowego. Ale przy rozsądnych ograniczeniach czasowych w przypadku problemów w świecie rzeczywistym ta druga grupa jest zwykle lepsza.

W przypadku niektórych modeli, takich jak regresja logistyczna, istnieje jedno lokalne minimum, funkcja jest wypukła, minimalizacja zbiega się do minimum, ale same modele są uproszczone.

To gorzka prawda.

Należy również zauważyć, że dowód na zbieżność i dowód na najlepsze rozwiązanie to dwie różne rzeczy. Algorytm K-średnich jest tego przykładem.

Wreszcie, w przypadku niektórych modeli wcale nie wiemy, jak się uczyć. Na przykład, jeśli dane wyjściowe są dowolną funkcją obliczeniową danych wejściowych, nie znamy dobrych algorytmów, które w rozsądnym czasie znajdują maszynę Turinga lub równoważną maszynę realizującą tę funkcję. Na przykład, jeśli f (1) = 2, f (2) = 3, f (3) = 5, f (4) = 7, ..., f (10) = 29 (dziesięć pierwszych liczb pierwszych) nie zna żadnego algorytmu uczenia się, który byłby w stanie przewidzieć w rozsądnym czasie, że f (11) = 31, chyba że zna już pojęcie liczb pierwszych.