Dlaczego PCA maksymalizuje całkowitą wariancję projekcji?

Christopher Bishop pisze w swojej książce Pattern Recognition and Machine Learning dowód, że każdy kolejny główny składnik maksymalizuje wariancję projekcji do jednego wymiaru, po tym jak dane zostaną rzutowane do przestrzeni ortogonalnej na wcześniej wybrane komponenty. Inne pokazują podobne dowody.

Dowodzi to jednak tylko, że każdy kolejny element jest najlepszym rzutem na jeden wymiar, pod względem maksymalizacji wariancji. Dlaczego to oznacza, że wariancja rzutu mówiącego o 5 wymiarach jest maksymalizowana przy wybieraniu pierwszych takich elementów?

machine-learning variance pca dimensionality-reduction eigenvalues michal
źródło

Czy mógłbyś powiedzieć nam dokładnie, co rozumie się pod pojęciem „wariancji” pięciowymiarowego zestawu danych wynikającego z rzutowania zestawu danych na pięć wymiarów? (Aby taka ilość podlegała maksymalizacji, musiałaby to być pojedyncza liczba.)

whuber

Bardzo dobra uwaga. Chris Bishop w swojej książce odnosi się do minimalizacji wariancji projekcji i nie jest jasne, co to znaczy dla więcej niż 1 wymiaru. Chciałbym dowiedzieć się, w jakim stopniu wariancja jest zminimalizowana i dlaczego taka procedura wspólnie ją minimalizuje.

michal

@ user123675: W swoim ostatnim komentarzu prawdopodobnie masz na myśli „maksymalizację”, a nie „minimalizację”.

ameba

Tak masz rację. Przepraszam!

michal

Odpowiedzi:

To, co rozumie się przez wariancję w kilku wymiarach („wariancja całkowita”), jest po prostu sumą wariancji w każdym wymiarze. Matematycznie jest to ślad macierzy kowariancji: ślad jest po prostu sumą wszystkich elementów ukośnych. Ta definicja ma różne ładne właściwości, np. Ślad jest niezmienny w ortogonalnych transformacjach liniowych, co oznacza, że jeśli obrócisz osie współrzędnych, całkowita wariancja pozostanie taka sama.

W książce Bishopa (rozdział 12.1.1) udowodniono, że wiodący wektor własny macierzy kowariancji podaje kierunek maksymalnej wariancji. Drugi wektor własny podaje kierunek maksymalnej wariancji pod dodatkowym ograniczeniem, że powinien on być prostopadły do pierwszego wektora własnego itp. (Wierzę, że stanowi to ćwiczenie 12.1). Jeśli celem jest maksymalizacja całkowitej wariancji w podprzestrzeni 2D, ta procedura jest zachłanną maksymalizacją: najpierw wybierz jedną oś, która maksymalizuje wariancję, a następnie drugą.

Twoje pytanie brzmi: dlaczego ta zachłanna procedura osiąga globalne maksimum?

Oto miły argument, który @whuber zasugerował w komentarzach. Najpierw wyrównajmy układ współrzędnych z osiami PCA. Macierz kowariancji staje się diagonalna: . Dla uproszczenia rozważymy ten sam przypadek 2D, tj. Jaka jest płaszczyzna o maksymalnej całkowitej wariancji? Chcemy udowodnić, że jest to płaszczyzna podana przez dwa pierwsze wektory podstawowe (o całkowitej wariancji ). $\boldsymbol{\Sigma} = \mathrm{diag}(\lambda_i)$ $\lambda_1+\lambda_2$

Rozważ płaszczyznę rozpiętą na dwóch wektorach ortogonalnych i . Całkowita wariancja w tej płaszczyźnie wynosiJest to więc liniowa kombinacja wartości własnych ze współczynnikami, które wszystkie są dodatnie, nie przekraczają (patrz poniżej) i sumują się do . Jeśli tak, to prawie oczywiste jest, że maksimum osiągnięto w . $\mathbf{u}$ $\mathbf{v}$

u^{⊤} Σ u + v^{⊤} Σ v = \sum λ_{i} u_{i}^{2} + \sum λ_{i} v_{i}^{2} = \sum λ_{i} (u_{i}^{2} + v_{i}^{2}) .

$\mathbf{u}^\top\boldsymbol{\Sigma}\mathbf{u} + \mathbf{v}^\top\boldsymbol{\Sigma}\mathbf{v} = \sum \lambda_i u_i^2 + \sum \lambda_i v_i^2 = \sum \lambda_i (u_i^2+v_i^2).$

λ_{i}

$\lambda_i$

1

$1$

2

$2$

λ_{1} + λ_{2}

$\lambda_1 + \lambda_2$

Pozostaje tylko wykazać, że współczynniki nie mogą przekraczać . Zauważ, że , gdzie jest wektorem podstawowym. Wielkość ta jest kwadratową długością rzutu na płaszczyznę rozpiętą przez i . Dlatego musi być mniejsza niż kwadratowa długość która jest równa , QED. $1$ $u_k^2+v_k^2 = (\mathbf{u}\cdot\mathbf{k})^2+(\mathbf{v}\cdot\mathbf{k})^2$ $\mathbf{k}$ $k$ $\mathbf k$ $\mathbf u$ $\mathbf v$ $\mathbf k$ $|\mathbf{k}|^2=1$

Zobacz także odpowiedź @ kardynała na Jaka jest funkcja celu PCA? (kieruje się tą samą logiką).

ameba
źródło

(+1) Ale nie jest to intuicyjnie oczywiste, że dany zbiór portfeli różnych ilości gotówki (modelowanie nieujemne wartości własne), a stała liczba , że można podnieść, że wybierając najbogatsze portfele będą zmaksymalizować łącznie gotówkowy? Dowód, że ta intuicja jest prawidłowa, jest prawie trywialny: jeśli nie wziąłeś największego , możesz poprawić swoją sumę, wymieniając najmniejszą, którą wziąłeś na większą kwotę.

k

$k$

k

$k$

k

$k$

whuber

@amoeba: jeśli celem jest maksymalizacja sumy wariancji, a nie wariancji sumy, nie ma powodu, aby druga projekcja była prostopadła do pierwszej.

Innuo

Przepraszam - myślałem, że już opracowałeś analizę do tego stopnia, że rozpoznałeś, że całkowita wariancja w podprzestrzeni wymiarowej jest nieujemną liniową kombinacją wartości własnych, w której żaden ze współczynników nie może przekraczać i suma współczynników wynosi

k

$k$

1

$1$

k

$k$ . (To kwestia prostego mnożenia macierzy - mnożniki Lagrange'a nie są potrzebne.) To prowadzi nas do metafory portfela. Zgadzam się, że należy przeprowadzić taką analizę.

whuber

@amoeba: Mam na myśli problem w bazie składającej się z wektorów własnych (jest to podstawa u i v, jeśli obliczymy ich wariancję przez pomnożenie przez ukośną macierz kowariancji). u i v ostatecznie okażą się nimi, ale myślę, że na etapie tego dowodu nie powinniśmy tego zakładać. Czy nie należy raczej argumentować, że gdyby w dowolnym momencie suma była większa niż 1, wówczas 2 wektory nie byłyby już ortogonalne, ponieważ podstawa jest ortogonalna, a każdy z wektorów daje co najwyżej 1? Ale z drugiej strony, dlaczego ograniczamy się do wektorów ortogonalnych u i v?

michal

@Heisenberg: Ach, rozumiem! Nie, oczywiście, że nie miałem tego na myśli! Ale teraz rozumiem, dlaczego to było mylące. Ponownie przepisałem ten ostatni dowód, aby pozbyć się kroku „wyboru podstawy”. Proszę zobaczyć moją edycję. Dziękuję Ci.

ameba

Jeśli masz nieskorelowanych zmiennych losowych posortowanych w malejącej kolejności ich wariancji i poproszono Cię o wybranie z nich w taki sposób, aby wariancja ich sumy była zmaksymalizowana, czy zgodziłbyś się, że chciwe podejście polegające na wybraniu pierwszego osiągnęłoby to? $N$ $k$ $k$

Dane rzutowane na wektory własne macierzy kowariancji są zasadniczo nieskorelowanymi kolumnami danych i których wariancja jest równa odpowiednim wartościom własnym. $N$

Aby intuicja była bardziej zrozumiała, musimy powiązać maksymalizację wariancji z obliczeniem wektora własnego macierzy kowariancji o największej wartości własnej i powiązać rzut ortogonalny z usunięciem korelacji.

Druga zależność jest dla mnie jasna, ponieważ współczynnik korelacji między dwoma wektorami (średnia zero) jest proporcjonalny do ich iloczynu wewnętrznego.

Zależność między maksymalizacją wariancji a rozkładem własnym macierzy kowariancji jest następująca.

Załóżmy, że $D$ jest macierzą danych po wyśrodkowaniu kolumn. Musimy znaleźć kierunek maksymalnej wariancji. Dla dowolnego wektora jednostkowego wariancja po rzutowaniu wzdłuż wynosi $v$ $v$

$E[(Dv)^t Dv] = v^t E[D^tD] v = v^t Cov(D) v$

który jest maksymalizowany, jeżeli jest wektorem własnym odpowiadającym największej wartości własnej. $v$ $Cov(D)$

Innuo
źródło

Pierwotne pytanie brzmi raczej: wybierz ortogonalnych kombinacji liniowych (w przeciwieństwie do z nich) tak, aby suma ich wariancji była zmaksymalizowana. Czy nadal jest oczywiste, że osiąga to chciwe podejście do wybierania pierwszego ?

k

$k$

k

$k$

k

$k$

ameba

Znalezienie ortogonalnych kombinacji liniowych, a następnie wybranie pierwszego najbardziej wariantu z nich, opisuje ten proces (luźno). Moja odpowiedź twierdzi tylko, że ortogonalność jest wystarczająca, aby chciwy proces osiągnął cel maksymalizacji całkowitej wariancji.

N

$N$

k

$k$

Innuo

Nie jestem pewien, czy podążę za argumentem. Jak ważna jest ortogonalność? Jeśli masz zmiennych i musisz wybrać o największej wariancji całkowitej, powinieneś wybrać o największej wariancji (niezależnie od tego, czy są one skorelowane, czy nie).

N

$N$

k

$k$

k

$k$

ameba

Ach, rozumiem zamieszanie. W mojej odpowiedzi była literówka. Naprawiono teraz.

Innuo

Wydaje mi się, że mógłbyś tu coś zrobić, ale magiczny wygląd sumy wymaga wyjaśnienia. Jakie to ma znaczenie dla PCA, a nawet dla rozkładu widmowego?

whuber