Dlaczego wartość k-średnich nie jest zoptymalizowana przy użyciu opadania gradientu?

Wiem, że k-średnie jest zwykle optymalizowane przy użyciu Maksymalizacji oczekiwań . Jednak moglibyśmy zoptymalizować jego funkcję utraty w ten sam sposób, w jaki zoptymalizowaliśmy każdy inny!

Znalazłem kilka artykułów, które faktycznie używają stochastycznego spadku gradientu dla dużych k-średnich, ale nie mogłem uzyskać odpowiedzi na moje pytanie.

Czy ktoś wie, dlaczego tak jest? Czy to dlatego, że maksymalizacja oczekiwań zbiega się szybciej ? Czy ma jakąś szczególną gwarancję? Czy jest to powód historyczny ?

— elsonidoq
źródło

Krok maksymalizacji już osiąga gradient prawdopodobieństwa (zależny od wartości wybranych przez krok oczekiwania), prawda?

— David J. Harris,

@ DavidJ.Harris Nie sądzę, że OP kwestionuje to, że EM zachowuje się tak, jak robi, ale pyta, dlaczego jedna metoda wydaje się być powszechnie stosowana, a inna nie jest tak często stosowana. Twój komentarz nie wydaje się bezpośrednio odnosić do tego, dlaczego EM może być preferowany.

— Glen_b

Cześć @ DavidJ.Harris, to jest jak Glen_b, rozumiem, że oba algorytmy optymalizują prawdopodobieństwo (EM) lub prawdopodobieństwo dziennika (spadek gradientu). Po zagłębieniu się w google i znajomych, dostałem ten papierowy link, czy to pytanie jest rozwiązane. Jeśli nie przegapiłem zrozumienia, EM osiąga lepsze rozwiązanie niż spadek gradientu.

— elsonidoq,

Jaka jest funkcja celu k-średnich do optymalizacji? Czy to jest różnicowalne?

— Vladislavs Dovgalecs

Jest płynnie różnicowalny w parametrach (oznacza klaster), ale na pewno nie w przypisaniach klastra (które są wielomianowymi zmiennymi wskaźnikowymi)?

— Ruben van Bergen,

Odpowiedzi:

Jak wspomina PO, możliwe jest rozwiązanie k-średnich za pomocą opadania gradientu, co może być przydatne w przypadku problemów na dużą skalę.

Z pewnością istnieją historyczne powody występowania algorytmów w stylu EM do rozwiązywania średnich k (tj. Algorytmu Lloyda). Algorytm Lloyda jest tak popularny, że ludzie nazywają go czasem „algorytmem k-średnich”, a nawet nie zdają sobie sprawy z istnienia innych podejść. Ale ta popularność nie jest niezasłużona.

Bottou i Bengio (1995) wykazali, że algorytm Lloyda jest równoważny z optymalizacją funkcji kosztu k-średnich metodą Newtona. W ogólnych problemach z optymalizacją metody drugiego rzędu, takie jak metoda Newtona, mogą zbiegać się szybciej niż metody pierwszego rzędu, takie jak opadanie gradientu, ponieważ wykorzystują informacje na temat krzywizny funkcji celu (a metody pierwszego rzędu nie). W eksperymencie na znanym zestawie danych Iris wykazano, że algorytm Lloyda rzeczywiście zbiegał się szybciej niż spadek gradientu. Byłoby interesujące zobaczyć to porównanie w szerszej gamie zestawów danych.

Bibliografia:

Bottou and Bengio (1995) . Właściwości zbieżności algorytmów k-średnich.

— user20160
źródło

K-oznacza, że grupowanie nie jest nadzorowane, a najbliższą nienadzorowaną techniką wykorzystującą EM jest klastrowanie oparte na modelach (modele mieszanki Gaussa, GMM). Irytujący problem z klastrowaniem opartym na modelu GMM występuje, gdy wiele cech jest skorelowanych, co powoduje prawie osobliwość w macierzy kowariancji (korelacji) opartej na cechach. W tej sytuacji funkcja prawdopodobieństwa staje się niestabilna, a indeksy warunków osiągają nieskończoność, powodując całkowity rozkład GMM.

Zatem porzućcie ideę EM i kNN - ponieważ opiera się ona na macierzach kowariancji (korelacji) do analizy bez nadzoru. Twoje zapytanie dotyczące optymalizacji przypomina mapowanie Sammon oraz klasyczne metryczne i niemetryczne skalowanie wielowymiarowe (MDS). Mapowanie Sammona jest oparte na iteracji pochodnych, podczas gdy różne formy MDS są zwykle iteracyjnymi lub jednoetapowymi kompozycjami eigend, które można jednak zoptymalizować podczas jednoetapowej operacji macierzowej.

Spoglądając jeszcze raz na twoją prośbę: odpowiedź brzmi: zostało to już zrobione w mapowaniu Sammon.

— JoleT
źródło