Spadek współrzędnych a gradient

Zastanawiałem się, jakie są różne przypadki użycia dla dwóch algorytmów: zejścia współrzędnych i zejścia gradientu .

Wiem, że opadanie współrzędnych ma problemy z nie płynnymi funkcjami, ale jest używane w popularnych algorytmach, takich jak SVM i LASSO.

Uważam jednak, że zejście gradientowe jest szerzej stosowane, zwłaszcza przy odradzaniu się ANN i wielu innych zadaniach uczenia maszynowego.

Moje pytanie brzmi: jaki rodzaj problemów pasuje do jednego, ale nie do drugiego, i w związku z tym, co sprawia, że ​​dopasowanie opadania współrzędnych dla SVM i LASSO, a dopasowanie gradientu opadania dla ANN?

Jak wybrać między tymi dwoma, wybierając algorytm optymalizacji?

Myślę, że zazwyczaj jest to kwestia tego, jak łatwo / łatwo jest obliczyć gradient gładkiej części funkcji i / lub bliższego operatora kary.

Czasami o wiele łatwiej jest znaleźć dokładne rozwiązanie problemu w przypadku jednej pojedynczej zmiennej (lub bloku lub zmiennych), niż wypracowanie go dla wszystkich zmiennych jednocześnie. Innym razem obliczenie gradientu jest po prostu zbyt drogie w porównaniu do poszczególnych instrumentów pochodnych. Również zbieżność opadania współrzędnych jest taka sama jak dla ista, , gdzie jest liczbą iteracji, ale czasami może działać lepiej w porównaniu z ISTA i FISTA, patrz np. Http: //statweb.stanford .edu / ~ tibs / Porównanie.txt .$1/k^2$$k$

Takie rzeczy wpłyną na przykład na wybór zejścia współrzędnych vs. ISTA / FISTA.

Zejście współrzędnych aktualizuje jeden parametr na raz, podczas gdy zejście gradientu próbuje zaktualizować wszystkie parametry jednocześnie.

Trudno dokładnie określić , kiedy jeden algorytm będzie działał lepiej od drugiego. Na przykład byłem bardzo zszokowany, gdy dowiedziałem się, że zejście ze współrzędnymi było najnowszym osiągnięciem LASSO. I nie byłem jedyny; patrz slajd 17 .

To powiedziawszy, istnieją pewne cechy, które mogą sprawić, że problem będzie bardziej poprawny w celu koordynowania zniżania:

(1) Szybkie aktualizacje warunkowe. Jeśli z jakiegoś powodu problem pozwala na bardzo szybką indywidualną optymalizację parametrów, może to wykorzystać opadanie współrzędnych. Na przykład można zaktualizować niektóre parametry, używając tylko podzbioru danych, co znacznie zmniejsza koszty obliczeniowe tych aktualizacji. Innym przypadkiem jest rozwiązanie formy zamkniętej dla pojedynczego parametru, zależnie od wartości wszystkich pozostałych parametrów.

(2) Względnie niezależne tryby parametrów. Jeśli optymalna wartość jednego parametru jest całkowicie niezależna od innych wartości parametrów, wówczas jedna runda opadania współrzędnych doprowadzi do rozwiązania (zakładając, że każda aktualizacja współrzędnych znajdzie aktualny tryb). Z drugiej strony, jeśli tryb dla danego parametru jest bardzo silnie zależny od innych wartości parametru, bardzo prawdopodobne jest, że zejście współrzędnych będzie się zmieniać wraz z bardzo małymi aktualizacjami w każdej rundzie.

Niestety, w przypadku większości problemów (2) nie ma zastosowania, więc rzadkie jest, że opadanie współrzędnych dobrze porównuje alternatywne algorytmy. Uważam, że powodem, dla którego działa on dobrze dla LASSO, jest to, że istnieje wiele sztuczek, których można użyć do wprowadzenia warunku (1).

$\alpha$

Zdaję sobie sprawę, że to stare pytanie i ma kilka bardzo dobrych odpowiedzi. Chciałbym podzielić się praktycznymi osobistymi doświadczeniami.

$k$

• Wszystkie prawdopodobieństwa muszą być dodatnie.
• Wszystkie elementy zestawu prawdopodobieństwa muszą sumować się do jednego

To w rzeczywistości dużo wymaga. Z opadaniem gradientu zwykle radzimy sobie z ograniczeniami poprzez funkcję kary. Tutaj to nie zadziała. Gdy tylko wartość narusza jedno z tych ograniczeń, Twój kod zwykle generuje rodzaj błędu liczbowego. Tak więc trzeba sobie poradzić z ograniczeniami, nigdy nie pozwalając algorytmowi optymalizacji na przemierzanie go.

Istnieje wiele transformacji, które możesz zastosować do swojego problemu, aby spełnić ograniczenia i umożliwić opadanie gradientu. Jeśli jednak szukasz najłatwiejszego i najbardziej leniwego sposobu na wdrożenie tej metody, możesz wybrać zejście współrzędnych:

$p_i$

• $p_i^{k+1} = p_i^{k} - \eta \frac{\partial J}{\partial p_i}$
• $p_i = \min(\max(p_i,0),1)$
• Zaktualizuj wszystkie p_i:$\mathbf{P}^{j+1} = \mathbf{P}^j \cdot \frac{1}{\sum_{i=1}^n p_i}$

Dla kogoś takiego jak ja, który pracuje w Pythonie, zwykle oznacza to, że muszę użyć dodatkowej pętli for, która ma negatywny wpływ na wydajność. Zejście gradientowe pozwala mi korzystać z Numpy, który jest zoptymalizowany pod kątem wydajności. Można przy tym uzyskać bardzo dobrą prędkość, jednak nie jest to możliwe przy zejściu ze współrzędnymi, więc zwykle używam techniki transformacji.

Wniosek jest naprawdę taki, że opadanie współrzędnych jest najłatwiejszą opcją do radzenia sobie z bardzo ścisłymi ograniczeniami, takimi jak parametr częstości w rozkładzie Poissona. Jeśli stanie się ujemny, kod narzeka itp.

Mam nadzieję, że to dodało trochę wglądu.