Jakie jest intuicyjne wyjaśnienie, w jaki sposób PCA zmienia się z problemu geometrycznego (z odległościami) w problem algebry liniowej (z wektorami własnymi)?

Dużo czytałem o PCA, w tym różne tutoriale i pytania (takie jak ten , ten , ten i ten ).

Geometryczny problem, który PCA próbuje zoptymalizować, jest dla mnie jasny: PCA próbuje znaleźć pierwszy główny składnik, minimalizując błąd rekonstrukcji (projekcji), który jednocześnie maksymalizuje wariancję rzutowanych danych.

Kiedy po raz pierwszy to przeczytałem, od razu pomyślałem o regresji liniowej; w razie potrzeby możesz to rozwiązać za pomocą opadania gradientu.

Jednak wtedy mój umysł był oszołomiony, gdy przeczytałem, że problem optymalizacji rozwiązano za pomocą algebry liniowej i znalezienia wektorów własnych i wartości własnych. Po prostu nie rozumiem, jak to zastosowanie algebry liniowej wchodzi w grę.

Moje pytanie brzmi zatem: w jaki sposób PCA może zmienić problem optymalizacji geometrycznej w problem algebry liniowej? Czy ktoś może podać intuicyjne wyjaśnienie?

Nie szukam odpowiedzi takiej jak ta, która mówi: „Kiedy rozwiążesz matematyczny problem PCA, kończy się to równoważeniem znalezienia wartości własnych i wektorów własnych macierzy kowariancji”. Wyjaśnij, dlaczego wektory własne okazują się głównymi składnikami i dlaczego wartości własne okazują się wariancją rzutowanych na nie danych

Nawiasem mówiąc, jestem inżynierem oprogramowania, a nie matematykiem.

Uwaga: powyższy rysunek został pobrany i zmodyfikowany w tym samouczku PCA .

Opis problemu

Geometryczny problem, który PCA próbuje zoptymalizować, jest dla mnie jasny: PCA próbuje znaleźć pierwszy główny składnik, minimalizując błąd rekonstrukcji (projekcji), który jednocześnie maksymalizuje wariancję rzutowanych danych.

Zgadza się. Wyjaśniam związek między tymi dwoma sformułowaniami w mojej odpowiedzi tutaj (bez matematyki) lub tutaj (z matematyki).

$\mathbf C$$\mathbf w$$\|\mathbf w\|=1$$\mathbf w^\top \mathbf{Cw}$

(Na wszelki wypadek, gdy nie jest to jasne: jeśli jest wyśrodkowaną macierzą danych, to rzut jest podawany przez a jego wariancja to ).$\mathbf X$$\mathbf{Xw}$$\frac{1}{n-1}(\mathbf{Xw})^\top \cdot \mathbf{Xw} = \mathbf w^\top\cdot (\frac{1}{n-1}\mathbf X^\top\mathbf X)\cdot \mathbf w = \mathbf w^\top \mathbf{Cw}$

Z drugiej strony wektorem własnym jest z definicji dowolny wektor taki, że .$\mathbf C$$\mathbf v$$\mathbf{Cv}=\lambda \mathbf v$

Okazuje się, że pierwszy główny kierunek jest nadawany przez wektor własny o największej wartości własnej. To nietrywialne i zaskakujące stwierdzenie.

Dowody

Jeśli otworzysz jakąkolwiek książkę lub samouczek na temat PCA, znajdziesz tam prawie jednoliniowy dowód powyższego stwierdzenia. Chcemy zmaksymalizować pod warunkiem, że ; można tego dokonać wprowadzając mnożnik Lagrange'a i maksymalizując ; różnicując, otrzymujemy , co jest równaniem wektora własnego. Widzimy, że musi być największą wartością własną, zastępując to rozwiązanie funkcją celu, co daje$\mathbf w^\top \mathbf{Cw}$$\|\mathbf w\|=\mathbf w^\top \mathbf w=1$$\mathbf w^\top \mathbf{Cw}-\lambda(\mathbf w^\top \mathbf w-1)$$\mathbf{Cw}-\lambda\mathbf w=0$$\lambda$$\mathbf w^\top \mathbf{Cw}-\lambda(\mathbf w^\top \mathbf w-1) = \mathbf w^\top \mathbf{Cw} = \lambda\mathbf w^\top \mathbf{w} = \lambda$ . Z uwagi na fakt, że tę funkcję celu należy zmaksymalizować, musi być największą wartością własną, QED.$\lambda$

Dla większości ludzi nie jest to zbyt intuicyjne.

Lepszy dowód (patrz np. Ta zgrabna odpowiedź @cardinal ) mówi, że ponieważ jest macierzą symetryczną, jest ona diagonalna w swojej wektorze własnym. (Tak naprawdę nazywa się to twierdzeniem spektralnym .) Możemy więc wybrać podstawę ortogonalną, mianowicie tę podaną przez wektory własne, gdzie jest przekątna, a na jego przekątnej mają wartości własne . Na tej podstawie upraszcza do , lub innymi słowy, wariancja jest dana przez ważoną sumę wartości własnych. Jest niemal natychmiastowe, że aby zmaksymalizować to wyrażenie, wystarczy wziąć$\mathbf C$$\mathbf C$$\lambda_i$$\mathbf w^\top \mathbf{C w}$$\sum \lambda_i w_i^2$$\mathbf w = (1,0,0,\ldots, 0)$, tj. pierwszy wektor własny, dający wariancję (w rzeczywistości odejście od tego rozwiązania i „wymiana” części największej wartości własnej na części mniejszych doprowadzi tylko do mniejszej ogólnej wariancji). Zauważ, że wartość nie zależy od podstawy! Przejście na podstawę wektora własnego oznacza obrót, więc w 2D można sobie wyobrazić po prostu obrócenie kawałka papieru za pomocą wykresu rozrzutu; oczywiście nie może to zmienić żadnych odchyleń.$\lambda_1$$\mathbf w^\top \mathbf{C w}$

Myślę, że jest to bardzo intuicyjny i bardzo użyteczny argument, ale opiera się na twierdzeniu spektralnym. Myślę więc, że prawdziwym problemem jest: jaka jest intuicja stojąca za twierdzeniem spektralnym?

Twierdzenie spektralne

Wziąć symetryczną matrycą . Weź swój wektor własny z największą wartością własną . Ustaw ten wektor własny jako pierwszy wektor podstawowy i wybierz losowo inne wektory podstawowe (tak, aby wszystkie z nich były ortonormalne). Jak będzie wyglądać na tej podstawie?$\mathbf C$$\mathbf w_1$$\lambda_1$$\mathbf C$

Będzie miał w lewym górnym rogu, ponieważ na tej podstawie i musi być równy .$\lambda_1$$\mathbf w_1=(1,0,0\ldots 0)$$\mathbf {Cw}_1=(C_{11}, C_{21}, \ldots C_{p1})$$\lambda_1\mathbf w_1 = (\lambda_1,0,0 \ldots 0)$

Pod tym samym argumentem będzie miał zera w pierwszej kolumnie pod .$\lambda_1$

Ale ponieważ jest symetryczny, również będzie miał zera w pierwszym rzędzie po . Będzie to wyglądać tak:$\lambda_1$

gdzie pusta przestrzeń oznacza, że ​​jest tam blok niektórych elementów. Ponieważ macierz jest symetryczna, ten blok również będzie symetryczny. Możemy więc zastosować do niego dokładnie ten sam argument, skutecznie wykorzystując drugi wektor własny jako drugi wektor podstawowy i uzyskując i na przekątnej. Można to kontynuować, dopóki będzie przekątna. Jest to zasadniczo twierdzenie spektralne. (Zwróć uwagę, jak to działa tylko dlatego, że jest symetryczny).$\lambda_1$$\lambda_2$$\mathbf C$$\mathbf C$

Oto bardziej abstrakcyjne przeformułowanie dokładnie tego samego argumentu.

Wiemy, że , więc pierwszy wektor własny definiuje 1-wymiarową podprzestrzeń, w której działa jak zwielokrotnienie skalarne. Weźmy teraz dowolny wektor ortogonalny do . Zatem jest niemal natychmiastowe, że jest również ortogonalny do . W rzeczy samej:$\mathbf{Cw}_1 = \lambda_1 \mathbf w_1$$\mathbf C$$\mathbf v$$\mathbf w_1$$\mathbf {Cv}$$\mathbf w_1$

Oznacza to, że działa na całą pozostałą podprzestrzeń prostopadłą do tak że pozostaje oddzielony od . Jest to kluczowa właściwość macierzy symetrycznych. Możemy więc znaleźć tam największy wektor własny, , i postępować w ten sam sposób, ostatecznie konstruując ortonormalną podstawę wektorów własnych.$\mathbf C$$\mathbf w_1$$\mathbf w_1$$\mathbf w_2$

Jest wynik z 1936 r. Autorstwa Eckarta i Younga ( https://ccrma.stanford.edu/~dattorro/eckart%26young.1936.pdf ), który stwierdza, co następuje

$\sum_1^r d_k u_k v_k^T = arg min_{\hat{X} \epsilon M(r)} ||X-\hat{X}||_F^2$

gdzie M (r) jest zbiorem macierzy ranga-r, co w zasadzie oznacza, że ​​pierwsze r składowe SVD X dają najlepsze przybliżenie macierzy X rangi niskiej, a najlepsze jest zdefiniowane w kategoriach kwadratu normy Frobeniusa - sumy kwadratu elementy macierzy.

Jest to ogólny wynik dla matryc i na pierwszy rzut oka nie ma nic wspólnego z zestawami danych ani redukcją wymiarów.

Jeśli jednak nie myślisz o jako macierzy, a raczej o kolumnach macierzy reprezentujących wektory punktów danych, to jest przybliżeniem z minimalnym błędem reprezentacji pod względem kwadratowych różnic błędów.$X$$X$$\hat{X}$

To jest moje zdanie na temat algebry liniowej za PCA. W algebrze liniowej jednym z kluczowych twierdzeń jest . Stwierdza, że ​​jeśli S jest dowolną symetryczną macierzą n na n o rzeczywistych współczynnikach, to S ma n wektorów własnych, przy czym wszystkie wartości własne są rzeczywiste. Oznacza to, że możemy napisać pomocą D macierzy diagonalnej z dodatnimi wartościami. To jest i nie ma nic złego w założeniu, że . A jest zmianą matrycy bazowej. To znaczy, jeśli naszą pierwotną podstawą było , to w odniesieniu do podstawy podanej przez$\textit{Spectral Theorem}$$S = ADA^{-1}$$D = \mbox{diag} (\lambda_1, \lambda_2, \ldots, \lambda_n)$$\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$$x_1,x_2, \ldots, x_n$$A(x_1), A(x_2), \ldots A(x_n)$, działanie S jest diagonalne. Oznacza to również, że można uznać za podstawę ortogonalną z Gdyby nasza macierz kowariancji dotyczyła n obserwacji n zmiennych, zrobilibyśmy to. Podstawą podaną przez jest podstawa PCA. Wynika to z faktów algebry liniowej. Zasadniczo jest to prawdą, ponieważ podstawa PCA jest podstawą wektorów własnych, a istnieją wektory własne n macierzy kwadratowej o rozmiarze n. Oczywiście większość macierzy danych nie jest kwadratowa. Jeśli X jest macierzą danych z n obserwacjami zmiennych p, to X ma rozmiar n przez p. Zakładam, że (więcej obserwacji niż zmiennych) i że$A(x_i)$$||A(x_i)|| = \lambda_i$$A(x_i)$
$n>p$$rk(X) = p$(wszystkie zmienne są liniowo niezależne). Żadne z tych założeń nie jest konieczne, ale pomoże intuicyjnie. Algebra liniowa ma uogólnienie na podstawie twierdzenia spektralnego zwanego rozkładem wartości osobliwych. Dla takiego X stwierdza, że z U, V macierzami ortonormalnymi (kwadratowymi) o rozmiarze nip oraz prawdziwa macierz diagonalna z tylko nieujemnymi wpisy na przekątnej. Ponownie możemy zmienić podstawę V, aby W kategoriach macierzowych oznacza to, że jeśli i jeśli . $X = U \Sigma V^{t}$$\Sigma = (s_{ij})$$s_{11} \geq s_{22} \geq \ldots s_{pp}> 0$$X(v_i) = s_{ii} u_i$$i \leq p$$s_{ii} = 0$$i> n$$v_i$dać rozkład PCA. Dokładniej jest rozkładem PCA. Dlaczego? Ponownie, algebra liniowa mówi, że mogą istnieć tylko wektory własne. SVD podaje nowe zmienne (podane przez kolumny V), które są ortogonalne i mają malejącą normę. $\Sigma V^{t}$

„co jednocześnie maksymalizuje wariancję prognozowanych danych”. Czy słyszałeś o ilorazie Rayleigha ? Może to jeden ze sposobów na to. Mianowicie współczynnik rayleigha macierzy kowariancji daje wariancję rzutowanych danych. (a strona wiki wyjaśnia, dlaczego wektory własne maksymalizują iloraz Rayleigha)

@amoeba daje staranne sformalizowanie i dowód:

Możemy sformalizować go w następujący sposób: biorąc pod uwagę macierz kowariancji C, szukamy wektora w o długości jednostkowej, ‖w‖ = 1, tak że w ^T Cw jest maksymalna.

Myślę jednak, że istnieje jeden intuicyjny dowód na:

Okazuje się, że pierwszy główny kierunek jest nadawany przez wektor własny o największej wartości własnej. To nietrywialne i zaskakujące stwierdzenie.

Możemy interpretować w ^T Cw jako iloczyn iloczynu między wektorem w i Cw, który jest uzyskiwany przez przejście przez transformację C:

w ^T Cw = ‖w‖ * ‖Cw‖ * cos (w, Cw)

Ponieważ w ma stałą długość, aby zmaksymalizować W ^T Cw, potrzebujemy:

1. maksymalizuj ‖Cw‖
2. maksymalizuj cos (w, Cw)

Okazuje się, że jeśli weźmiemy w jako wektor własny C o największej wartości własnej, możemy zarchiwizować oba jednocześnie:

1. ‖Cw‖ wynosi maksimum (jeśli w odbiegamy od tego wektora własnego, dekomponujemy go wzdłuż ortogonalnych wektorów własnych, powinieneś zobaczyć spadek ‖Cw‖).
2. w i Cw w tym samym kierunku, cos (w, Cw) = 1, max

Ponieważ wektory własne są ortogonalne, wraz z innymi wektorami własnymi C tworzą zestaw podstawowych składników X.

dowód 1

rozłożyć w na pierwotny i wtórny wektor własny v1 i v2 , zakładając , że ich długość wynosi odpowiednio v1 i v2. chcemy to udowodnić

(λ ₁ w) ² > ((λ ₁ v1) ² + (λ ₂ v2) ² )

od λ ₁ > λ ₂ mamy

((λ ₁ v1) ² + (λ ₂ v2) ² )

<((λ ₁ v1) ² + (λ ₁ v2) ² )

= (λ ₁ ) ² * (v1 ² + v2 ² )

= (λ ₁ ) ² * w ²