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?

pca

— Neil McGuigan
źródło

Być może coś mi brakuje, więc popraw mnie, jeśli się mylę, ale powinno być możliwe (przynajmniej w zasadzie) skonstruowanie tego, co dzieje się w PCA przy użyciu macierzy jako (skomplikowanego) problemu programowania liniowego, ale nie wiedzieć, jak określić wszystkie wymagane ograniczenia. Nie jestem też pewien, czy byłoby to bardzo proste w porównaniu do zwykłego korzystania z PCA. Dlaczego starasz się unikać matryc?

— Chris Simokat

@Chris Nie rozumiem, jak można dostać się do problemu programowania liniowego. Nie rozumiałem też, że w obliczeniach należy unikać macierzy . Pytanie dotyczyło tego, jaki problem rozwiązuje PCA, a nie sposób, w jaki jest on wykonywany (na przykład przez obliczenie SVD). Rozwiązanie kardynała mówi, że znajdujesz kolejne ortogonalne kierunki maksymalnej wariancji . Rozwiązanie, które przedstawiłem, mówi, że znajdujesz hiperpłaszczyzny z minimalnym błędem rekonstrukcji.

— NRH

@chris Mam nadzieję znaleźć inny sposób, aby zobaczyć PCA, bez algebry macierzy, aby zwiększyć moje rozumienie tego.

— Neil McGuigan

@Chris masz funkcji kwadratowej obiektywnej oraz

ℓ_{2}

$\ell_2$ równości normą ograniczenie. Alternatywnie, na podstawie sformułowania w odpowiedzi @ NRH, masz ograniczenie macierzy rangi. To nie doprowadzi do problemu programowania liniowego. @NRH daje dobrą intuicję, a w rzeczywistości istnieje bardzo ścisły związek między dwiema przedstawionymi perspektywami PCA. Być może we współpracy z @NRH możemy dodać to do jego postu, aby pełny zestaw odpowiedzi był bardziej kompletny.

— kardynał

@NRH, Właściwie bardzo lubię ESL , ale myślę, że traktowanie tego tematu jest dość powierzchowne, tak jak w przypadku wielu tematów w książce. W szczególności nie dowodzą (ani nawet nie przypisują jako ćwiczenia) ważnej części rozwiązania problemu optymalizacji, który dajesz.

— kardynał

Odpowiedzi:

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 .

S = \frac{1}{n} \sum_{i = 1}^{n} x_{i} x_{i}^{T} = X^{T} X / n

$\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}

$\x_i$

p

$p$

X

$\m{X}$

i

$i$

x_{i}^{T}

$\x_i^T$

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

\begin{array}{ll} maximize & \frac{u^{T} S u}{u^{T} u}, u \in R^{p} . \end{array}

$\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} maximize & u^{T} S u \\ subject to & u^{T} u = 1 . \end{array}

$\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 Λ Q^{T},

$\S = \Q \L \Q^T \>,$

Q

$\Q$

Q Q^{T} = I

$\Q \Q^T = \m{I}$

Λ

$\L$

λ_{i}

$\lambda_i$

λ_{1} \geq λ_{2} \geq \dots \geq λ_{p} \geq 0

$\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^{⋆} = Q e_{1} = q_{1}

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

q_{1}

$\m{q}_1$

Q

$\Q$

S

$\S$

λ_{1}

$\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} maximize & u_{i}^{T} S u_{i} \\ subject to & u_{i}^{T} u_{i} = 1 \\ u_{i}^{T} u_{j} = 0 \forall 1 \leq j < i . \end{array}

$\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

$i$

q_{i}

$\m{q}_i$

i

$i$

S

$\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}$

X Q = X V = U D V^{T} V = U D .

$\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.

— kardynał
źródło

Jeśli potrzebnych jest tylko kilka pierwszych pojedynczych wartości / wektorów, Nash i Shlien podają algorytm przypominający zwykłą metodę mocy do obliczania dominujących wartości własnych. Może to być interesujące dla PO.

— JM nie jest statystykiem

@NRH, Dziękujemy za wyłapanie (i poprawienie) moich literówek, zanim udało mi się je zobaczyć!

— kardynał

Cześć @cardinal, dziękuję za odpowiedź. Wygląda jednak na to, że nie udało ci się udowodnić, dlaczego sekwencyjna optymalizacja prowadzi do globalnego optimum. Czy mógłbyś rozwinąć tę kwestię? Dzięki!

— Lifu Huang

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_{μ, λ_{1}, \dots, λ_{n}, V_{q}} \sum_{i = 1}^{n} | | x_{i} - μ - V_{q} λ_{i} | |^{2}

$\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$

μ = \bar{x} = \frac{1}{n} \sum_{i = 1}^{n} x_{i} λ_{i} = V_{q}^{T} (x_{i} - \bar{x})

$\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} - V_{q} V_{q}^{T} x_{i} | |^{2}

$\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} | | P x_{i} | |^{2}

$\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

$P$

\sum_{i = 1}^{n} | | P x_{i} | |^{2} = \sum_{i = 1}^{n} x_{i}^{T} P x_{i} = tr (P \sum_{i = 1}^{n} x_{i} x_{i}^{T}) = n tr (P S)

$\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

$P$

S

$\mathbf{S}$

tr (P S) = tr (V_{q}^{T} S V_{q}) = \sum_{i = 1}^{q} u_{i}^{T} S u_{i}

$\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}, \dots, u_{q}

$u_1, \ldots, u_q$

q

$q$

V_{q}

$\mathbf{V}_q$

u_{i}

$u_i$

q

$q$

S

$\mathbf{S}$

q

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

— NRH
źródło

(+1) Dobre punkty. Kilka sugestii: Dobrze byłoby zdefiniować i naprawdę miło byłoby podać krótki dowód wyniku. Lub, alternatywnie, może być związany z problemem optymalizacji związanym z ilorazami Rayleighta. Myślę, że dzięki temu odpowiedzi na to pytanie byłyby bardzo kompletne!

λ_{i}

$\lambda_i$

— kardynał

@ kardynał, uważam, że wykonałem brakujące kroki w przejściu od formuły odbudowy do rozwiązania problemu.

— NRH

Dobra robota. Uważam, że jedyną pozostałą luką jest twoje ostatnie oświadczenie. Nie jest od razu oczywiste, że optymalizacja sumy jest tym samym, co wykonanie sekwencji optymalizacji w mojej odpowiedzi. W zasadzie nie sądzę, że wynika to bezpośrednio. Ale tutaj też nie trzeba się tym zajmować.

— kardynał

@ kardynał, następuje indukcja. początek indukcji, a na etapie indukcji wybierasz wektory ortonormalne które maksymalizują sumę i je tak, aby był wektorem jednostkowym prostopadłym do . Następnie według twoich wyników i przez założenie indukcyjne . Oczywiście podstawa nie jest unikalną podstawą przestrzeni wymiarowej. Możesz także uogólnić „argument kombinacji wypukłej”, którego używasz do bezpośredniego udowodnienia.

w_{1}, \dots, w_{q}

$w_1, \ldots, w_q$

w_{q}

$w_q$

u_{1}, \dots, u_{q - 1}

$u_1, \ldots, u_{q-1}$

w_{q}^{T} S w_{q} \leq u_{q}^{T} S u_{q}

$w_q^T \mathbf{S} w_q \leq u_q^T \mathbf{S} u_q$

\sum_{i = 1}^{q - 1} w_{i}^{T} S w_{i} \leq \sum_{i = 1}^{q - 1} u_{i}^{T} S u_{i}

$\sum_{i=1}^{q-1} w_i^T \mathbf{S} w_i \leq \sum_{i=1}^{q-1}u_i^T \mathbf{S} u_i$

q

$q$

— NRH

@ cardinal, nie zmuszam do zagnieżdżenia, wykorzystuję jedynie rozważanie wymiarów. Jeśli mamy podprzestrzeń wymiarową, zawsze możesz wybrać w tej przestrzeni, tak aby była ona ortogonalna do podprzestrzeni . Następnie należy wypełnić ten -basis w jakikolwiek sposób chcesz.

q

$q$

w_{q}

$w_q$

(q - 1)

$(q-1)$

w

$w$

— NRH

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 :)

— JMS
źródło