Zalety podejścia do problemu poprzez sformułowanie funkcji kosztu, którą można zoptymalizować globalnie

To dość ogólne pytanie (tj. Niekoniecznie specyficzne dla statystyki), ale zauważyłem trend w uczeniu maszynowym i literaturze statystycznej, w którym autorzy wolą stosować następujące podejście:

Podejście 1 : uzyskanie rozwiązania praktycznego problemu poprzez sformułowanie funkcji kosztu, dla której możliwe jest (np. Z obliczeniowego punktu widzenia) znalezienie globalnie optymalnego rozwiązania (np. Poprzez sformułowanie wypukłej funkcji kosztu).

zamiast:

Podejście 2 : uzyskaj rozwiązanie tego samego problemu, formułując funkcję kosztów, dla której możemy nie być w stanie uzyskać globalnie optymalnego rozwiązania (np. Możemy uzyskać tylko optymalne lokalnie rozwiązanie).

Zauważ, że rygorystycznie rzecz biorąc oba problemy są różne; założeniem jest, że możemy znaleźć globalnie optymalne rozwiązanie dla pierwszego, ale nie dla drugiego.

Pomijając inne kwestie (np. Szybkość, łatwość wdrożenia itp.), Szukam:

Wyjaśnienie tej tendencji (np argumenty matematyczne lub historyczne)
Korzyści (praktyczne i / lub teoretyczne) wynikające z zastosowania podejścia 1 zamiast 2 przy rozwiązywaniu praktycznego problemu.

optimization function

— Amelio Vazquez-Reina
źródło

Odpowiedzi:

Uważam, że celem powinna być optymalizacja funkcji, która cię interesuje. Jeśli tak się dzieje, to liczba błędnych klasyfikacji - a nie dwumianowe prawdopodobieństwo, powiedzmy - to powinieneś spróbować zminimalizować liczbę błędnych klasyfikacji. Jednak z wielu wymienionych przyczyn praktycznych (szybkość, wdrożenie, niestabilność itp.) Może to nie być tak łatwe, a nawet niemożliwe. W takim przypadku decydujemy się na przybliżenie rozwiązania.

Znam w zasadzie dwie strategie aproksymacyjne; albo wymyślimy algorytmy, które próbują bezpośrednio przybliżyć rozwiązanie pierwotnego problemu, albo przeformułujemy pierwotny problem jako bardziej bezpośrednio do rozwiązania (np. wypukłe rozluźnienia).

Matematyczny argument za preferowanie jednego podejścia nad innymi jest to, czy możemy zrozumieć a) właściwości roztworu faktycznie obliczane i b), jak również rozwiązanie jest zbliżona do rozwiązania problemu jesteśmy rzeczywiście zainteresowany.

Znam wiele wyników w statystykach, w których możemy udowodnić właściwości rozwiązania problemu optymalizacji. Wydaje mi się, że trudniej jest przeanalizować rozwiązanie algorytmu, w którym nie masz matematycznego sformułowania tego, co oblicza (np. Że rozwiązuje dany problem optymalizacji). Z pewnością nie twierdzę, że nie możesz, ale wydaje się to teoretyczną korzyścią , jeśli możesz podać jasne matematyczne sformułowanie tego, co obliczasz.

Nie jest dla mnie jasne, czy takie argumenty matematyczne dają jakieś praktyczne korzyści dla Podejścia 1 nad Podejście 2. Na pewno jest ktoś, kto nie boi się funkcji utraty wypukłości .

— NRH
źródło

Dzięki za odniesienie do przemówienia Yanna LeCuna. Nie mogę się doczekać, aby to obejrzeć.

— Amelio Vazquez-Reina

@NRH udzielił odpowiedzi na to pytanie (ponad 5 lat temu), więc po prostu zaoferuję Podejście 3, które łączy Podejście 1 i 2.

Podejście 3 :

Sformułuj i rozwiąż do globalnej optymalności wypukły, aw każdym razie globalnie optymalizowany (niekoniecznie wypukły) problem, który jest „bliski” problemowi, który naprawdę chcesz rozwiązać.
Użyj globalnie optymalnego rozwiązania od kroku 1 jako początkowego (początkowego) rozwiązania niewypukłego problemu optymalizacji, który naprawdę chcesz rozwiązać (lub więcej chcesz rozwiązać niż problem rozwiązany w kroku 1). Mam nadzieję, że twoje początkowe rozwiązanie znajduje się w „regionie przyciągania” do globalnego optimum w stosunku do metody rozwiązania zastosowanej do rozwiązania niewypukłego problemu optymalizacji, który naprawdę chcesz rozwiązać.

— Mark L. Stone
źródło

Proszę podać konkretny przykład.

— horaceT,

Nie jest to dokładnie przypadek Marka, ale powszechnym podejściem w wielu problemach z widzeniem komputerowym jest stosowanie stopniowanej niewypukłości w celu uzyskania sekwencji „dobrych” lokalnych optymów dotyczących powiązanych problemów. Konkretnym przykładem jest przepływ optyczny zgrubny do drobnego, gdzie dla pary obrazów stosuje się wyrównanie zgrubne w celu zaszczepienia wyszukiwania w dokładniejszych skalach, przechodząc przez parę piramid obrazu .

— GeoMatt22,

@horaceT Powiedzmy, że chcesz rozwiązać nieliniowy problem najmniejszych kwadratów

y

$y$ ~

a e^{b x}

$ae^{bx}$ , który nie jest wypukły. Jako krok 1 możesz rozwiązać liniowy problem najmniejszych kwadratów

y

$y$ ~

a a + b b x

$aa + bb x$ , który jest wypukły i można go rozwiązać z optymalizacją globalną. Następnie w kroku 2 użyj

a = e^{a a_{o p t i m a l}}, b = b b_{o p t i m a l}

$a = e^{aa_{optimal}}, b = bb_{optimal}$ jako wartości początkowe dla nieliniowych najmniejszych kwadratów. Problemy są podobne, ale błędy są traktowane inaczej. Istnieje wiele problemów, w których pożądana jest kara niewypukła (za krok 2), ale można ją zastąpić karą wypukłą za krok 1. Możliwa jest także wielokrotna iteracja.

— Mark L. Stone,

@ GeoMatt22 To, co opisałeś, jest podobne w duchu i pokrywa się z tak zwanymi metodami homotopii, w których ścieżka do rozwiązania problemu, który naprawdę chcesz rozwiązać, jest wytyczona przez rozwiązanie szeregu problemów, w których parametr, taki jak ograniczenie jest stopniowo zmieniane i rozwiązywane kolejne problemy, dla których pierwszy problem jest łatwy do rozwiązania od zera. Może rzeczywiście być tak, że pierwszy problem jest wypukły lub w inny sposób nadaje się do rozwiązania, ale późniejsze problemy mogą nie być, nawet jeśli ich optymalne rozwiązanie może być ciągłe w parametrze.

— Mark L. Stone,