Po co studiować optymalizację wypukłą dla teoretycznego uczenia maszynowego?

27

Pracuję nad teoretycznym uczeniem maszynowym - a konkretnie nad uczeniem się przez transfer - dla mojego doktoratu.

  • Z ciekawości, dlaczego powinienem wziąć kurs optymalizacji wypukłej?

  • Jakie wnioski z optymalizacji wypukłej mogę wykorzystać w swoich badaniach nad teoretycznym uczeniem maszynowym?

Upendra Pratap Singh
źródło
2
Nie jest jasne, czy sprzeciwiasz się części wypukłej, części optymalizacyjnej czy obu.
Mehrdad
Pamiętaj, że odpowiedź, którą zaakceptowałeś, jest po prostu błędna. Może jeszcze raz spojrzysz na to pytanie i wybierzesz odpowiedź, która ma o wiele większy sens.
Xji
Optymalizacja wypukła i optymalizacja matematyczna to narzędzie do budowania modeli - te techniki są używane do konstruowania modeli / kontrolowania / znajdowania parametrów zrozumiałych zjawisk do pewnego stopnia niepewności.
bruziuz
Uczenie maszynowe polega na budowaniu aproksymacji funkcji, takich jak metody sprzęgania, oraz, o ile znasz jedną z funkcji wyboru koncepcji, które w przybliżeniu minimalizują straty (które nie są wypukłe, a nawet najgorsze obejmują zmienne wskaźnikowe), więc ML gra się przyjemnie z niewypukłą optymalizacją.
bruziuz
FYI „Optymalizacja wypukła nie mogą być wykorzystywane do głębokiej nauki - S.Boyd” - youtu.be/uF3htLwUHn0?t=2810
bruziuz

Odpowiedzi:

59

Algorytmy uczenia maszynowego cały czas korzystają z optymalizacji. Minimalizujemy straty lub błędy lub maksymalizujemy niektóre funkcje oceniania. Zejście gradientowe to algorytm optymalizacji „witaj świecie”, który obejmuje prawdopodobnie każdy kurs uczenia maszynowego. Jest to oczywiste w przypadku modeli regresji lub klasyfikacji, ale nawet przy zadaniach takich jak klastrowanie szukamy rozwiązania, które optymalnie pasuje do naszych danych (np. K-średnie minimalizuje sumę kwadratów wewnątrz klastra). Jeśli więc chcesz zrozumieć, jak działają algorytmy uczenia maszynowego, lepiej poznaj optymalizację. Co więcej, jeśli musisz robić rzeczy takie jak dostrajanie hiperparametrów, wtedy bezpośrednio używasz optymalizacji.

Można argumentować, że optymalizacja wypukła nie powinna być tak interesująca dla uczenia maszynowego, ponieważ zamiast zajmować się funkcjami wypukłymi , często napotykamy powierzchnie strat takie jak ta poniżej, które są dalekie od wypukłych .

Przykład realnego, niewypukłego krajobrazu strat.

(źródło: https://www.cs.umd.edu/~tomg/projects/landscapes/ i arXiv: 1712.09913 )

Niemniej jednak, jak wspomniano w innych odpowiedziach, optymalizacja wypukła jest szybsza, prostsza i mniej wymagająca obliczeniowo, więc często łatwiej jest „wypuknąć” problem (uczynić go optymalizacją wypukłą), a następnie zastosować optymalizację niewypukłą. Na przykład algorytmy opadania gradientu i podobne algorytmy są powszechnie stosowane w uczeniu maszynowym, szczególnie w sieciach neuronowych, ponieważ „działają”, skalują się i są szeroko implementowane w różnych programach, niemniej jednak nie są to najlepsze osoby, które możemy zdobyć i mieć ich pułapki , zgodnie z dyskusją Ali Rahimi na NIPS 2017 .

Z drugiej strony, niewypukłe algorytmy optymalizacyjne, takie jak algorytmy ewolucyjne, wydają się zyskiwać coraz większe uznanie w społeczności ML, np. Szkolenie sieci neuronowych przez neuroewolucję wydaje się być najnowszym tematem badań (patrz także arXiv: 1712.07897 ).

Tim
źródło
5
odpowiedź wydaje się nie odnosić do „wypukłych”
Haitao Du
@ hxd1011 Skomentowałem to.
Tim
Świetna odpowiedź! Naprawdę odnosi się do tego, jak krytyczna jest optymalizacja ML i jak ML upraszcza się dzięki zastosowaniu wypukłych aproksymacji, które działają z opadaniem gradientu.
ChuckCottrill
To powinna być zaakceptowana odpowiedź.
Jan Kukacka
11

Myślę, że są tutaj dwa pytania.

  • Po co studiować optymalizację
  • Po co optymalizacja wypukła

Myślę, że @Tim ma dobrą odpowiedź na pytanie, dlaczego optymalizacja. Zdecydowanie się zgadzam i polecam wszystkim zainteresowanym uczeniem maszynowym opanowanie ciągłej optymalizacji. Ponieważ proces optymalizacji / znalezienie lepszego rozwiązania w czasie, jest procesem uczenia się komputera.

Chcę porozmawiać o tym, dlaczego interesują nas funkcje wypukłe. Powód jest prosty: optymalizacje wypukłe są „łatwiejsze do rozwiązania” i mamy wiele niezawodnych algorytmów do rozwiązania.

Ale czy świat jest wypukły? Nie. Dlaczego ma obsesję na punkcie wypukłości? Sprawdź tę metaforę

Policjant widzi pijanego mężczyznę szukającego czegoś pod latarnią i pyta, co pijak stracił. Mówi, że zgubił klucze i oboje patrzą razem pod światło uliczne. Po kilku minutach policjant pyta, czy jest pewien, że ich tu zgubił, a pijany odpowiada: nie i że zgubił je w parku. Policjant pyta, dlaczego tu szuka, a pijak odpowiada: „tu jest światło”.

Haitao Du
źródło
2
Ale metaforycznie, dlatego dostajesz latarkę. Poszukiwanie kluczy w ciemności jest trudne do niemożliwego, więc dostosowujesz problem do takiego, który wiesz jak rozwiązać. Jeśli pracujesz nad problemem z niewypukłymi algorytmami i opracujesz rozwiązanie, które będzie kosztować 3 miliony dolarów, a ja pracuję nad podobnym problemem z optymalizacją wypukłą, przyjmuję moją odpowiedź i znajduję rozwiązanie problemu niewypukłego, który kosztuje 2 milion dolarów, znalazłem lepszą odpowiedź.
prosfilaes
Ta odpowiedź jest błędna na wielu poziomach. Porównanie wypukłej analizy z efektem oświetlenia ulicznego jest po prostu błędne . Radzę zapoznać się ze wstępnym podręcznikiem Convex Optimization autorstwa Boyda i Vandenberghe, aby dowiedzieć się więcej na ten temat.
Digio
2

Najważniejsze jest to, że uczenie maszynowe jest stosowane do problemów, w których nie ma optymalnego rozwiązania. Najlepsze, co możesz zrobić, to znaleźć dobre przybliżenie.

Natomiast w przypadku problemu z optymalizacją istnieje optymalne rozwiązanie, ale zwykle nie można go znaleźć w rozsądnym czasie lub przy odpowiedniej mocy przetwarzania.

Narzędzia i algorytmy, których używasz, są zasadniczo różne. Więc chociaż powiedziałbym, że nie ma natychmiastowej korzyści z wzięcia udziału w lekcji optymalizacji, zawsze dobrze jest wiedzieć trochę o powiązanych polach. Jeśli potrafisz rozpoznać problem optymalizacji, będziesz wiedział, że nie powinieneś go rozwiązywać za pomocą algorytmów uczenia maszynowego, ale za pomocą algorytmów optymalizacji. Samo to jest warte dużo powiedziałbym.

Toby
źródło
33
Tak, w uczeniu maszynowym szukamy najlepszych przybliżeń. Ale mylisz się, mówiąc, że obie rzeczy są „zasadniczo różne”. Algorytmy ML wykorzystują optymalizację, aby zminimalizować funkcje strat i znaleźć optymalne parametry, biorąc pod uwagę dane i cel. Kiedy dostrajasz swoje hiperparametry, szukasz ich optymalnej kombinacji. W każdym z przypadków maksymalizujesz lub minimalizujesz coś, aby osiągnąć swój cel, więc używasz pewnego rodzaju optymalizacji.
Tim
@Tim: To prawda, powinienem to inaczej sformułować.
Toby
17
jeśli się zgadzasz, prawdopodobnie powinieneś to sformułować inaczej.
Tim
19
Ta odpowiedź jest ewidentnie błędna. Znaczna liczba problemów z uczeniem maszynowym sprowadza się do problemów z optymalizacją.
Przywróć Monikę
2
Twierdzenie, że w „problemach z optymalizacją zwykle nie można znaleźć optymalnego rozwiązania” jest błędne. Zwłaszcza w kontekście optymalizacji wypukłej (o którą prosi OP) łatwo można znaleźć optymalne rozwiązanie (na przykład zejście gradientu ze zmniejszającą się szybkością uczenia się gwarantuje osiągnięcie zbieżności z optymalną funkcją wypukłą). Dużym problemem jest to, że wiele problemów w uczeniu maszynowym jest niewypukłych .
Jan Kukacka
2

Jak powiedział hxd1011, wypukłe problemy są łatwiejsze do rozwiązania, zarówno teoretycznie, jak i (zwykle) w praktyce. Tak więc nawet w przypadku problemów niewypukłych wiele algorytmów optymalizacji rozpoczyna się od „kroku 1. zredukowania problemu do wypukłego” (być może wewnątrz pętli while).

Podobnie dzieje się z nieliniowym wyszukiwaniem korzeni. Zwykle rozwiązanie (np. Metodą Newtona) idzie „krok 1. Zmniejszyć do problemu liniowego, ponieważ wiemy, jak je rozwiązać”.

Federico Poloni
źródło
1

Jeśli twoje zainteresowania leżą w (wypukłej) optymalizacji zastosowanej do głębokiego uczenia się (wspominasz o uczeniu się przez przeniesienie, które jest szeroko stosowane w praktyce w sieciach neuronowych), gorąco zachęcam do rozważenia przeczytania rozdziału 8 (optymalizacja do szkolenia głębokich sieci neuronowych) http : //www.deeplearningbook.org/

Dyskutuje się na temat optymalizacji wypukłej i dlaczego nie odniosła ona jeszcze tak dużego sukcesu, gdy zastosowano głębokie sieci neuronowe. Oczywiście być może mógłbyś przeprowadzić badania w tej dziedzinie, które zmienią obecny konsensus!

FXQuantTrader
źródło
0

Jak słyszałem od Jerome H. Friedmana metody opracowane w uczeniu maszynowym w rzeczywistości same w sobie nie należą do społeczności uczącej się maszynowo.

Z mojego punktu widzenia Uczenie maszynowe bardziej przypomina zbiór różnych metod z innych dziedzin.

Z punktu widzenia nauki statystycznej trzy główne pytania dotyczące regresji i klasyfikacji to:

  1. Czym jest rodzina funkcji, z której pobierasz aproksymator

  2. Jakie są kryteria pobierania funkcji

  3. Jaka jest metoda znalezienia najlepszej funkcji


Aby działać w konstruktywny sposób na (1) - nie jest tak oczywiste, w jaki sposób może pomóc wykorzystanie optymalizacji matematycznej

Aby działać w konstruktywny sposób na (2) - oczywiste jest, że celem jest cel. I optymalizacja matematyki może w tym pomóc.

Aby działać w konstruktywny sposób na (3) - potrzebujesz optymalizacji matematycznej.


Istnieje kilka części optymalizacji matematycznej:

  1. Optymalizacja wypukła / Analiza wypukła - bardzo fajny obszar matematyki. Brak różnicowania nie stanowi problemu. I jest 50 uogólnień funkcji wypukłych, z których więcej dwóch użytecznych pod względem zastosowania jest quasiconvex i log-wklęsły.

Istnieją także sposoby radzenia sobie w jakiś sposób z „stochastycznością”, nawet „Nikt nie wie, jak rozwiązać stochastyczną optymalizację wypukłą”

  1. Optymalizacja bez wypukłości - zwykle oznacza to coś, co jest ciągłym celem, ale krzywizna może się różnić. Ludzie na tej planecie nie wiedzą, jak to dokładnie rozwiązać. I w rzeczywistości wszystkie mehtody wykorzystują (1)

  2. Kombinatoryczna optymalizacja - jest jeszcze bardziej dzika niż (2), teraz dla parametrów, których nawet nie można zastosować operatora minus. Jednym z przykładów są „regiony” w drzewach decyzyjnych. Są więc dwa sposoby, jak sobie z tym poradzić: a) Wyjaw problem i zastosuj metody z (1) b) Zrób brutalną siłę. Nie działa dla dużej liczby parametrów. c) Zrób brutalną siłę, ale z pewnymi chciwymi krokami. CART robi to.


Myślę więc, że przynajmniej przekonuję cię, że:

I) Optymalizacja wypukła jest kluczowa dla większości problemów związanych z optymalizacją.

II) „01:15 Optymalizacja jest w rzeczywistości tematem większym niż ML czy AI, ale w rzeczywistości jest większym przedmiotem”. ( https://www.youtube.com/watch?v=uF3htLwUHn0&t=992s )

bruziuz
źródło
Odpowiedź jest trochę krótka jak na standardy tej witryny - czy uważasz, że możesz ją rozwinąć? W przeciwnym razie najlepiej nadaje się jako komentarz.
Silverfish
Dobrze. Będę się rozwijał, ale tak naprawdę można napisać artykuł o połączeniu z różnymi dziedzinami. W rzeczywistości zapytałem Stephena P. Boyda o pytanie dotyczące tego, czy ludzie myśleli wcześniej i kiedy - youtu.be/XV1E-Jnc4SU?t=242 . Powiedział, że w dzisiejszych czasach świat jest rozbity.
bruziuz
1
@Silverfish zaktualizowałem, teraz jest to długi tekst zamiast jednego zdania.
bruziuz