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

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:

max_{w} (X w)^{T} (X w) s.t. w^{T} w = 1.

$\max_w (Xw)^T(Xw)\; \: \text{s.t.} \: \:w^Tw = 1.$

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

max_{w} [(X w)^{T} (X w) - λ w^{T} w],

$\max_w [(Xw)^T(Xw) - \lambda w^Tw],$

co jest równoważne z

max_{w} \frac{(X w)^{T} (X w)}{w^{T} w},

$\max_w \frac{ (Xw)^T(Xw) }{w^Tw},$

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

max_{w} \sum_{i = 1}^{n} {(distance from point x_{i} to line w)}^{2} .

$\max_w \sum_{i=1}^n \text{(distance from point $x_i$ 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ą?

pca optimization 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

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

W porządku - twoją odpowiedzią była niepoprawna wersja tego, co próbowałem zrobić.

Cam.Davidson.Pilon

Odpowiedzi:

Niech będzie wyśrodkowaną macierzą danych o $\newcommand{\X}{\mathbf X}\X$ $n$ 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ą. $\newcommand{\S}{\boldsymbol \Sigma}\S=\X^\top\X/(n-1)$ $\newcommand{\w}{\mathbf w}\w$ $\w$

Zgodnie z pierwszym podejściem pierwsza oś główna maksymalizuje wariancję rzutu (wariancja pierwszego głównego elementu). Ta odmiana jest podana przez $\X \w$

V a r (X w) = w^{⊤} X^{⊤} X w / (n - 1) = w^{⊤} Σ w .

$\mathrm{Var}(\X\w)=\w^\top\X^\top \X \w/(n-1)=\w^\top\S\w.$

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

\begin{aligned} ‖ X - X w w^{⊤} ‖^{2} & = t r ((X - X w w^{⊤}) (X - X w w^{⊤})^{⊤}) \\ = t r ((X - X w w^{⊤}) (X^{⊤} - w w^{⊤} X^{⊤})) \\ = t r (X X^{⊤}) - 2 t r (X w w^{⊤} X^{⊤}) + t r (X w w^{⊤} w w^{⊤} X^{⊤}) \\ = c o n s t - t r (X w w^{⊤} X^{⊤}) \\ = c o n s t - t r (w^{⊤} X^{⊤} X w) \\ = c o n s t - c o n s t \cdot w^{⊤} Σ w . \end{aligned}

$\begin{align}\newcommand{\tr}{\mathrm{tr}} \|\X-\X\w\w^\top\|^2 &=\tr\left((\X-\X\w\w^\top)(\X-\X\w\w^\top)^\top\right) \\ &=\tr\left((\X-\X\w\w^\top)(\X^\top-\w\w^\top\X^\top)\right) \\ &=\tr(\X\X^\top)-2\tr(\X\w\w^\top\X^\top)+\tr(\X\w\w^\top\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\X\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\w^\top\X^\top\X\w) \\ &=\mathrm{const} - \mathrm{const} \cdot \w^\top \S \w. \end{align}$

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 samo $\w^\top \S \w$ $\w$ .

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?

w^{T} Σ w

${w}^{T} \Sigma w$

w

$w$

Σ

$\Sigma$

Royi

@amoeba czy możesz wyjaśnić, jak przejść z tr () do const w ostatnim kroku?

alberto,

@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 .

Σ

$\Sigma$

X^{⊤} X / n

$X^\top X/n$

1 / n

$1/n$

ameba mówi Przywróć Monikę

@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).

W

$W$

W^{⊤} W = I

$W^\top W = I$

W

$W$

x W W^{⊤}

$xWW^\top$

x

$x$

W

$W$

x

$x$

ameba mówi Przywróć Monikę

@ 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

$w$

ameba mówi Przywróć Monikę