Czy optymalizacja PCA jest wypukła?

Funkcja celu w głównej analizie składników (PCA) polega na minimalizowaniu błędu rekonstrukcji w normie L2 (patrz sekcja 2.12 tutaj . Inny pogląd stara się zmaksymalizować wariancję projekcji. Mamy też doskonały post tutaj: Jaka jest funkcja celu PCA ? ).

Moje pytanie brzmi: czy wypukła jest optymalizacja PCA? (Znalazłem tutaj kilka dyskusji , ale chciałbym, aby ktoś mógł dostarczyć dobry dowód tutaj na CV).

Nie, zwykłe preparaty PCA nie są problemami wypukłymi. Ale można je przekształcić w wypukły problem optymalizacji.

Wgląd i radość z tego polega na śledzeniu i wizualizowaniu sekwencji transformacji, a nie tylko na uzyskiwaniu odpowiedzi: leży ona w podróży, a nie w miejscu docelowym. Główne kroki w tej podróży to

1. Uzyskaj proste wyrażenie dla funkcji celu.

2. Powiększ swoją domenę, która nie jest wypukła, do tej, która jest.

3. Zmodyfikuj cel, który nie jest wypukły, w taki, który w oczywisty sposób nie zmienia punktów, w których osiąga swoje optymalne wartości.

Jeśli będziesz uważnie obserwować, zobaczysz czające się mnożniki SVD i Lagrange'a - ale są one tylko pokazem pobocznym, które przyciągają uwagę i nie będę ich więcej komentował.

---

Standardowy preparat PCA maksymalizujący wariancję (lub przynajmniej jego kluczowy etap) to

$$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x=1\tag{*}$$

gdzie macierz jest symetryczną macierzą dodatnio-pół-skończoną zbudowaną z danych (zwykle jest to suma macierzy kwadratów i produktów, macierz kowariancji lub macierz korelacji).$n\times n$$\mathbb A$

(Równolegle możemy próbować zmaksymalizować nieograniczony cel . To nie tylko jest nieprzyjemne wyrażenie - nie jest to już funkcja kwadratowa - ale wykresy specjalnych przypadków będą szybko pokazuję, że nie jest to również funkcja wypukła. Zazwyczaj obserwuje się, że funkcja ta jest niezmienna przy ponownym skalowaniu a następnie redukuje ją do sformułowania ograniczonego .)x → λ x ( ∗ $x^\prime \mathbb{A} x / x^\prime x$$x\to \lambda x$$(*)$

Każdy problem optymalizacji można abstrakcyjnie sformułować jako

Znajdź co najmniej jeden , dzięki czemu funkcja tak duża, jak to możliwe. f : X → $x\in\mathcal{X}$$f:\mathcal{X}\to\mathbb{R}$

Przypomnij sobie, że problem optymalizacji jest wypukły, gdy ma dwie osobne właściwości:

1. Domeny jest wypukła. $\mathcal{X}\subset\mathbb{R}^n$ Można to sformułować na wiele sposobów. Jednym z nich jest to, że ilekroć i i , λ x + ( 1 - λ ) y ∈ X X y∈ X 0≤λ≤1$x\in\mathcal{X}$$y\in\mathcal{X}$$0 \le \lambda \le 1$$\lambda x + (1-\lambda)y\in\mathcal{X}$ również . Geometrycznie: gdy dwa punkty końcowe kłamstwie Odcinek , cała kłamstwa segmentów w .$\mathcal X$$\mathcal X$

2. Funkcja jest wypukła. $f$ x ∈ X y ∈ X 0 ≤ λ ≤ 1 f ( λ x + ( 1 - λ ) y ) ≥ λ f ( x ) + ( 1 - λ ) f ( y ) . X ¯ x y X f ( x , f ( x ) ) ( y , f ( y Można to również sformułować na wiele sposobów. Po pierwsze, za każdym razem, gdy i i ,(Potrzebowaliśmy wypukłości aby warunek ten miał jakikolwiek sens). Geometrycznie: ilekroć jest dowolnym segmentem linii w , wykres (ograniczony do tego segmentu) leży powyżej lub w segmencie łączącym i w .$x\in\mathcal{X}$$y\in\mathcal{X}$$0 \le \lambda \le 1$

   $$f(\lambda x + (1-\lambda)y) \ge \lambda f(x) + (1-\lambda) f(y).$$ $\mathcal X$$\bar{xy}$$\mathcal X$$f$$(x,f(x))$R n + $(y,f(y))$$\mathbb{R}^{n+1}$

   Archetyp funkcji wypukłej jest lokalnie wszędzie paraboliczny z nie dodatnim współczynnikiem wiodącym: w dowolnym segmencie linii można go wyrazić w postaci zaa ≤ $y\to a y^2 + b y + c$$a \le 0.$

Trudność z polega na tym, że jest sferą jednostkową , która zdecydowanie nie jest wypukła. X S n - 1 ⊂ R$(*)$$\mathcal X$$S^{n-1}\subset\mathbb{R}^n$ x λ f λ 2 0 < x ′ x < 1 x λ = 1 / √ Możemy jednak zmodyfikować ten problem, włączając mniejsze wektory. Dzieje się tak, ponieważ kiedy skalujemy współczynnik ,$x$$\lambda$$f$ jest mnożone przez . Gdy , możemy skalować do długości jednostki, mnożąc ją przez , zwiększając tym samym ale pozostając w piłka jednostkowa .$\lambda^2$$0 \lt x^\prime x \lt 1$$x$fDn={x∈ R n∣x′x≤1}(∗$\lambda=1/\sqrt{x^\prime x} \gt 1$$f$ $D^n = \{x\in\mathbb{R}^n\mid x^\prime x \le 1\}$ Przeformułujmy zatem jako$(*)$

$$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x\le1\tag{**}$$

Jego domeną jest która wyraźnie jest wypukła, więc jesteśmy w połowie drogi. Pozostaje rozważyć wypukłość wykresu .$\mathcal{X}=D^n$$f$

Dobry sposób na zastanowienie się nad problemem nawet jeśli nie zamierzasz wykonywać odpowiednich obliczeń - jest pod względem twierdzenia spektralnego. $(**)$ Mówi, że za pomocą transformacji ortogonalnejmożna znaleźć co najmniej jedną podstawęw którejjest przekątna: to znaczy,R n $\mathbb P$$\mathbb{R}^n$$\mathbb A$

$$\mathbb {A = P^\prime \Sigma P}$$

gdzie wszystkie wpisy o przekątnej poniżej P A x → x ′ A$\Sigma$ są zerowe. Taki wybór można sobie wyobrazić, że w ogóle nie zmienia nic w , a jedynie zmienia sposób jego opisu : po obróceniu punktu widzenia, osie poziomu hiperpowierzchni funkcji (które zawsze były elipsoidami) wyrównane z osiami współrzędnych.$\mathbb{P}$$\mathbb A$$x\to x^\prime \mathbb{A} x$

Od Σ P σ 1 ≥ σ 2 ≥ ⋯ ≥ σ n ≥ $\mathbb A$ jest dodatnio-pół-skończony, wszystkie wpisy po przekątnej muszą być nieujemne. $\Sigma$ Możemy dalej permutować osie (co jest po prostu kolejną transformacją ortogonalną, a zatem może zostać wchłonięte do ), aby zapewnić, że$\mathbb P$

$$\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0.$$

Jeśli pozwolimy x y = P x $x=\mathbb{P}^\prime y$ być nowymi współrzędnymi (pociągając za sobą ), funkcja jest$x$$y=\mathbb{P}x$$f$

$$f(y) = y^\prime \mathbb{A} y = x^\prime \mathbb{P^\prime A P} x = x^\prime \Sigma x = \sigma_1 x_1^2 + \sigma_2 x_2^2 + \cdots + \sigma_n x_n^2.$$

Ta funkcja zdecydowanie nie jest wypukła! Jego wykres wygląda jak część hiperparaboloidu: w każdym punkcie wnętrzaσ $\mathcal X$ fakt, że wszystkie są nieujemne, powoduje, że zwija się on w górę, a nie w dół . $\sigma_i$

Jednak możemy włączyć do wypukłej problem z jednym bardzo przydatna technika. $(**)$ Wiedząc, że maksimum wystąpi, gdy , odejmijmy stałą od , przynajmniej dla punktów na granicy . To nie zmieni lokalizacji żadnych punktów na granicy, w którychσ 1 f X f f σ $x^\prime x = 1$$\sigma_1$$f$$\mathcal{X}$$f$ jest zoptymalizowany, ponieważ obniża wszystkie wartości na granicy o tę samą wartość . Sugeruje to zbadanie funkcji$f$$\sigma_1$

$$g(y) = f(y) - \sigma_1 y^\prime y.$$

To faktycznie odejmuje stałą od w punktach granicznych i odejmuje mniejsze wartości w punktach wewnętrznych. Zapewni to, że , w porównaniu z , ma nową globalną maksima na wnętrze . f g f $\sigma_1$$f$$g$$f$$\mathcal X$

Sprawdźmy, co się stało z tym sztuczką polegającą na zastąpieniu przez . Ponieważ jest ortogonalny, - σ 1 y ′ y P y ′ y = x ′ x x $-\sigma_1$$-\sigma_1 y^\prime y$$\mathbb P$$y^\prime y = x^\prime x$ . (Jest to praktycznie definicja transformacji ortogonalnej.) Dlatego też, jeśli chodzi o współrzędne , można zapisać$x$$g$

$$g(y) = \sigma_1 x_1 ^2 + \cdots + \sigma_n x_n^2 - \sigma_1(x_1^2 + \cdots + x_n^2) = (\sigma_2-\sigma_1)x_2^2 + \cdots + (\sigma_n - \sigma_1)x_n^2.$$

Ponieważ dla wszystkich , każdy ze współczynników jest zerowy lub ujemny. W konsekwencji (a) jest wypukły, a (b) jest zoptymalizowany, gdy . ( następnie implikuje a optymalne osiąga się, kiedy i g g x 2 = x 3 = ⋯ = x n = 0 x ′ x = 1 x 1 = ± 1 y = P ( ± 1 , 0 , … , 0 ) ′ $\sigma_1 \ge \sigma_i$$i$$g$$g$$x_2=x_3=\cdots=x_n=0$$x^\prime x=1$$x_1=\pm 1$$y = \mathbb{P} (\pm 1,0,\ldots, 0)^\prime$ , czyli - do znak - pierwsza kolumna )$\mathbb P$

Podsumujmy logikę. Ponieważ jest zoptymalizowane na granicy gdzie , ponieważ różni się od jedynie stałą na tej granicy i ponieważ wartości są jeszcze bliższe wartościom we wnętrzu , maksima muszą pokrywać się z maksimami∂ D n = S n - 1 y ′ y = 1 f g σ $g$$\partial D^n=S^{n-1}$$y^\prime y = 1$$f$$g$$\sigma_1$f D n f $g$$f$$D^n$$f$$g$ .

Nie.

$k$$M$

$\hat{X} = \underset{rank(X) \leq k}{argmin} \| M - X\|_F^2$

( jest normą Frobeniusa ). Wyprowadzenie patrz twierdzenie Eckarta-Younga .$\|\cdot\|_F$

Chociaż norma jest wypukła, zestaw, w którym jest ona zoptymalizowana, nie jest wypukły.

---

Wypukły złagodzenie problemu PCA nazywa Convex Niski ranking Zbliżanie

$\hat{X} = \underset{\|X\|_* \leq c}{argmin} \| M - X\|_F^2$

( to norma jądrowa . wypukła relaksacja rangi - podobnie jak to wypukła relaksacja liczby elementów niezerowych dla wektorów) ‖ ⋅ ‖ $\|\cdot\|_*$$\|\cdot\|_1$

Szczegółowe informacje można znaleźć w Statystycznym uczeniu się ze sparsity , rozdział 6 (rozkład macierzy).

Jeśli interesują Cię bardziej ogólne problemy i ich związek z wypukłością, zobacz Uogólnione modele niskiej rangi .

Oświadczenie: poprzednie odpowiedzi całkiem dobrze wyjaśniają, w jaki sposób PCA w swoim oryginalnym sformułowaniu nie jest wypukła, ale można ją przekształcić w problem optymalizacji wypukłej. Moja odpowiedź jest przeznaczona tylko dla tych biednych dusz (takich jak ja), które nie są tak dobrze zaznajomione z żargonem Sfer Jednostkowych i SVD - co przy okazji warto wiedzieć.

Moim źródłem są notatki z wykładów prof. Tibshirani

Aby rozwiązać problem optymalizacji za pomocą wypukłych technik optymalizacji, istnieją dwa warunki wstępne.

1. Funkcja celu musi być wypukła.
2. Funkcje ograniczeń powinny być również wypukłe.

Większość formulacji PCA wiąże się z ograniczeniem rangi matrycy.

$rank(X) = k,$$J_{11}$$J_{22}$