Funkcja celu PCA: jaki jest związek między maksymalizacją wariancji a minimalizacją błędu?

32

Algorytm PCA można sformułować w kategoriach macierzy korelacji (załóżmy, że dane X zostały już znormalizowane i rozważamy jedynie rzut na pierwszy komputer). Funkcję celu można zapisać jako:

maxw(Xw)T(Xw)s.t.wTw=1.

To jest w porządku i używamy mnożników Lagrangian, aby go rozwiązać, tj. Przepisując go jako:

maxw[(Xw)T(Xw)λwTw],

co jest równoważne z

maxw(Xw)T(Xw)wTw,

i stąd ( patrz tutaj na Mathworld ) wydaje się być równa

maxwi=1n(distance from point xi to line w)2.

Ale to mówi, aby zmaksymalizować odległość między punktem i linią, a z tego, co tu przeczytałem , jest to niepoprawne - powinno to być min , a nie max . Gdzie jest mój błąd?

Czy ktoś może mi pokazać związek między maksymalizowaniem wariancji w rzutowanej przestrzeni a minimalizowaniem odległości między punktem a linią?

Cam.Davidson.Pilon
źródło
Myślę, że minimalna odległość jest stosowana, aby spełnić kryterium ortogonalności dla komponentów. Punkty są rzutowane na komputery, które są do siebie prostopadłe, ale w każdym kolejnym składniku pozostała wariancja jest zmaksymalizowana.
Michael R. Chernick,
Wskazówka: Co się stanie, gdy weźmiesz pod uwagę najpierw najmniejszą wartość własną, a nie największą?
whuber
@whuber Najmniejsza wartość własna prawdopodobnie ma komputer, który jest rozwiązaniem ostatecznej funkcji celu. Ale ten komputer nie maksymalizuje oryginalnej funkcji celu.
Cam.Davidson.Pilon
2
Nie jestem pewien, co rozumiesz przez „ostateczną” i „oryginalną” funkcję celu, Cam. PCA nie jest (koncepcyjnie) programem optymalizacyjnym. Jego wynikiem jest zestaw głównych kierunków, a nie tylko jeden. Jest (interesującym) twierdzeniem matematycznym, że kierunki te można znaleźć, rozwiązując sekwencję ograniczonych programów kwadratowych, ale nie jest to podstawowa koncepcja ani praktyka PCA. Sugeruję jedynie, że skupiając się na najmniejszej wartości własnej, a nie na największej, możesz pogodzić dwie idee (1) minimalizacji odległości i (2) biorąc pod uwagę optymalizację PCA.
whuber
1
W porządku - twoją odpowiedzią była niepoprawna wersja tego, co próbowałem zrobić.
Cam.Davidson.Pilon

Odpowiedzi:

42

Niech będzie wyśrodkowaną macierzą danych o nXn obserwacjami w rzędach. Niech będzie jego macierzą kowariancji. Niech będzie wektorem jednostkowym określającym oś w przestrzeni zmiennych. Chcemy, aby była pierwszą osią główną.w wΣ=XX/(n1)ww

Zgodnie z pierwszym podejściem pierwsza oś główna maksymalizuje wariancję rzutu (wariancja pierwszego głównego elementu). Ta odmiana jest podana przezV a r ( X w ) = wXX w / ( n - 1 ) = w Σ w .Xw

Var(Xw)=wXXw/(n1)=wΣw.

Zgodnie z drugim podejściem pierwsza oś główna minimalizuje błąd rekonstrukcji międzyX w ww X - X w w2X a jego rekonstrukcją , tj. Sumą kwadratów odległości między oryginalnymi punktami i ich rzutami na . Kwadrat błędu rekonstrukcji podaje Xwww

XXww2=tr((XXww)(XXww))=tr((XXww)(XwwX))=tr(XX)2tr(XwwX)+tr(XwwwwX)=consttr(XwwX)=consttr(wXXw)=constconstwΣw.

Zwróć uwagę na znak minus przed terminem głównym. Z tego powodu minimalizacja błędu rekonstrukcji sprowadza się do maksymalizacji , co jest wariantem. Zatem minimalizacja błędu rekonstrukcji jest równoważna maksymalizacji wariancji; oba preparaty dają to samowΣww .

ameba mówi Przywróć Monikę
źródło
Coś, co zauważyłem, to nie wypukła funkcja (W odniesieniu do jak to PSD? Jak to możliwe, aby zmaksymalizować to?wTΣwwΣ
Royi
@amoeba czy możesz wyjaśnić, jak przejść z tr () do const w ostatnim kroku?
alberto,
1
@alberto W śladzie znajduje się liczba (macierz 1x1); śladem liczby jest sam ten numer, więc ślad można usunąć. Stała pojawia się, ponieważ jest równa , więc istnieje ten współczynnik . ΣXX/n1/n
ameba mówi Przywróć Monikę
1
@Leullame Obliczenia będą zawierać dosłownie jeśli jest to macierz z kolumnami ortonormalnymi. Potrzebujesz aby przejść z linii nr 3 do linii nr 4. Jeśli macierz ma kolumny ortonormalne, to rzeczywiście będzie rzutem na podprzestrzeń rozciągniętą przez kolumny (tutaj jest wektorem wiersza). WWW=IWxWWxWx
ameba mówi Przywróć Monikę
1
@ DanielLópez Cóż, szukamy 1-wymiarowej podprzestrzeni minimalizującej błąd rekonstrukcji. Do 1-wymiarowe podprzestrzeń może być określona przez jednostkę-normy wektorowej skierowaną w jej stronę, która jest, co przyjmuje się. Ma konstrukcję według normy jednostkowej. w
ameba mówi Przywróć Monikę