Jaka jest funkcja celu PCA?

Analiza głównych składników może wykorzystywać rozkład macierzy, ale to tylko narzędzie, aby się tam dostać.

Jak znalazłbyś główne składniki bez użycia algebry macierzowej?

Jaka jest funkcja celu (cel) i jakie są ograniczenia?

Bez próby uzyskania pełnego startera na PCA, z punktu widzenia optymalizacji, podstawową funkcją celu jest iloraz Rayleigha . Macierz, która zawiera iloraz, to (pewna wielokrotność) przykładowa macierz kowariancji w którym każdy jest wektorem funkcji i jest taki, że matryca ty rząd jest .xipXix T

$$\newcommand{\m}[1]{\mathbf{#1}}\newcommand{\x}{\m{x}}\newcommand{\S}{\m{S}}\newcommand{\u}{\m{u}}\newcommand{\reals}{\mathbb{R}}\newcommand{\Q}{\m{Q}}\newcommand{\L}{\boldsymbol{\Lambda}} \S = \frac{1}{n} \sum_{i=1}^n \x_i \x_i^T = \m{X}^T \m{X} / n$$ $\x_i$$p$$\m{X}$$i$$\x_i^T$

PCA dąży do rozwiązania sekwencji problemów optymalizacyjnych. Pierwszym w sekwencji jest nieograniczony problem

$$\begin{array}{ll} \text{maximize} & \frac{\u^T \S \u}{\u^T\u} \;, \u \in \reals^p \> . \end{array}$$

Ponieważ, powyższy nieograniczony problem jest równoważny ograniczonemu problemowi $\u^T \u = \|\u\|_2^2 = \|\u\| \|\u\|$

$$\begin{array}{ll} \text{maximize} & \u^T \S \u \\ \text{subject to} & \u^T \u = 1 \>. \end{array}$$

Tutaj pojawia się algebra macierzy. Ponieważ jest symetryczną dodatnią macierzą półfinałową (z konstrukcji!), Ma rozkład wartości własnej postaci gdzie jest macierz ortogonalna (więc ) i jest macierzą diagonalną z nieujemnymi wpisami przykład .$\S$

$$\S = \Q \L \Q^T \>,$$ $\Q$$\Q \Q^T = \m{I}$$\L$$\lambda_i$$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_p \geq 0$

Stąd, . Ponieważ jest ograniczony w tym problemie, aby mieć normę jeden, tak też jest ponieważ , ponieważ jest ortogonalny.$\u^T \S \u = \u^T \Q \L \Q^T \u = \m{w}^T \L \m{w} = \sum_{i=1}^p \lambda_i w_i^2$$\u$$\m{w}$$\|\m{w}\|_2 = \|\Q^T \u\|_2 = \|\u\|_2 = 1$$\Q$

Ale jeśli chcemy zmaksymalizować ilość pod ograniczeniami, że , to co możemy zrobić, to: ustaw , to znaczy i dla .$\sum_{i=1}^p \lambda_i w_i^2$$\sum_{i=1}^p w_i^2 = 1$$\m{w} = \m{e}_1$$w_1 = 1$$w_i = 0$$i > 1$

Teraz, wycofując odpowiednie , czego właśnie szukaliśmy, otrzymujemy, że gdzie oznacza pierwszą kolumnę , czyli wektor własny odpowiadający największej wartości własnej . Wartość funkcji celu można wtedy łatwo rozpoznać jako .$\u$

$$\u^\star = \Q \m{e}_1 = \m{q}_1$$ $\m{q}_1$$\Q$$\S$$\lambda_1$

---

Pozostałe główne wektory składowe można następnie znaleźć, rozwiązując sekwencję (indeksowaną przez ) problemów optymalizacyjnych Problem jest taki sam, z tym wyjątkiem, że dodajemy dodatkowe ograniczenie, że rozwiązanie musi być ortogonalne dla wszystkich poprzednich rozwiązań w sekwencji. Nie jest trudny do rozszerzenia argumentu powyżej indukcyjnie pokazują, że roztwór th problemem jest to, w rzeczywistości, , tym p wektor własny .$i$

$$\begin{array}{ll} \text{maximize} & \u_i^T \S \u_i \\ \text{subject to} & \u_i^T \u_i = 1 \\ & \u_i^T \u_j = 0 \quad \forall 1 \leq j < i\>. \end{array}$$ $i$$\m{q}_i$$i$$\S$

---

Roztwór PKD ulega także często ekspresji w odniesieniu do pojedynczej wartości rozkładu z . Zrozumieć, dlaczego pozwolić . Następnie i tak (ściśle mówiąc, do znaku flips) i .$\m{X}$$\m{X} = \m{U} \m{D} \m{V}^T$$n \S = \m{X}^T \m{X} = \m{V} \m{D}^2 \m{V}^T$$\m{V} = \m{Q}$$\L = \m{D}^2 / n$

Główne komponenty można znaleźć, rzutując na wektory głównych komponentów. Z właśnie podanego sformułowania SVD łatwo zauważyć, że $\m{X}$

$$\m{X} \m{Q} = \m{X} \m{V} = \m{U} \m{D} \m{V}^T \m{V} = \m{U} \m{D} \> .$$

Prostota reprezentacji zarówno wektorów głównych składników, jak i samych głównych składników w odniesieniu do SVD macierzy cech, jest jednym z powodów, dla których SVD wyróżnia się tak wyraźnie w niektórych zabiegach PCA.

Rozwiązanie przedstawione przez kardynała skupia się na macierzy kowariancji próbki. Kolejnym punktem wyjścia jest błąd rekonstrukcji danych przez q- wymiarową hiperpłaszczyznę. Jeśli p- wymiarowe punkty danych to celem jest rozwiązanie$x_1, \ldots, x_n$

$$\min_{\mu, \lambda_1,\ldots, \lambda_n, \mathbf{V}_q} \sum_{i=1}^n ||x_i - \mu - \mathbf{V}_q \lambda_i||^2$$

dla macierzy z kolumnami ortonormalnymi i . To daje najlepszą rangę rekonstrukcji q mierzoną przez normę euklidesową, a kolumny rozwiązania są pierwszymi q głównymi wektorami składowymi.$p \times q$$\mathbf{V}_q$$\lambda_i \in \mathbb{R}^q$$\mathbf{V}_q$

Dla naprawionego rozwiązaniem dla i (jest to regresja) są $\mathbf{V}_q$$\mu$$\lambda_i$

$$\mu = \overline{x} = \frac{1}{n}\sum_{i=1}^n x_i \qquad \lambda_i = \mathbf{V}_q^T(x_i - \overline{x})$$

Dla ułatwienia notacji załóżmy, że zostały wyśrodkowane w następujących obliczeniach. Następnie musimy zminimalizować $x_i$

$$\sum_{i=1}^n ||x_i - \mathbf{V}_q\mathbf{V}_q^T x_i||^2$$

over z kolumnami ortonormalnymi. Zauważ, że to rzut na q- wymiarową przestrzeń kolumny. Dlatego problem jest równoważny z minimalizowaniem na rang q występy . Oznacza to, że musimy zmaksymalizować stosunku do rzutów q q , gdzie to przykładowa macierz kowariancji. Teraz$\mathbf{V}_q$$P = \mathbf{V}_q\mathbf{V}_q^T$

$$\sum_{i=1}^n ||x_i - P x_i||^2 = \sum_{i=1}^n ||x_i||^2 - \sum_{i=1}^n||Px_i||^2$$ $P$ $$\sum_{i=1}^n||Px_i||^2 = \sum_{i=1}^n x_i^TPx_i = \text{tr}(P \sum_{i=1}^n x_i x_i^T) = n \text{tr}(P \mathbf{S})$$ $P$$\mathbf{S}$ $$\text{tr}(P\mathbf{S}) = \text{tr}(\mathbf{V}_q^T\mathbf{S}\mathbf{V}_q) = \sum_{i=1}^q u_i^T \mathbf{S} u_i$$ gdzie są (ortonormalnymi) w , a argumenty przedstawione w odpowiedzi @ kardynała pokazują, że maksimum uzyskuje się przyjmując ' s będzie wektorami własnymi dla z największymi wartościami własnymi.$u_1, \ldots, u_q$$q$$\mathbf{V}_q$$u_i$$q$$\mathbf{S}$$q$

Błąd rekonstrukcji sugeruje szereg użytecznych uogólnień, na przykład rzadkie główne elementy lub rekonstrukcje za pomocą niskowymiarowych rozmaitości zamiast hiperplanów. Aby uzyskać szczegółowe informacje, patrz sekcja 14.5 w Elementy uczenia statystycznego .

Zobacz NIPALS ( wiki ) dla jednego algorytmu, który nie używa jawnie rozkładu macierzy. Myślę, że właśnie to masz na myśli mówiąc, że chcesz uniknąć algebry macierzowej, ponieważ tak naprawdę nie możesz tutaj uniknąć algebry macierzowej :)