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

— Haitao Du
źródło

Nie. Maksymalizujesz funkcję wypukłą (pod ograniczeniami).

— user603

Myślę, że musisz sprecyzować, co rozumiesz przez „optymalizację PCA”. Jednym ze standardowych sformułowań jest maksymalizacja zastrzeżeniem . Problem polega na tym, że wypukłość nawet nie ma sensu: domena jest kulą, a nie przestrzenią euklidesową.

x^{'} A x

$x^\prime\mathbb{A}x$

x^{'} x = 1

$x^\prime x=1$

x^{'} x = 1

$x^\prime x=1$

— whuber

@ dziękuję za komentarz, może nie mogę wyjaśnić pytania z powodu ograniczonej wiedzy. Mogę poczekać, aż niektóre odpowiedzi pomogą mi wyjaśnić pytanie w tym samym czasie.

— Haitao Du

Odsyłam cię do każdej znanej Ci definicji „wypukłej”. Czy nie wszystkie zawierają koncepcję punktów w dziedzinie funkcji leżącej „między” innymi punktami? Warto o tym pamiętać, ponieważ przypomina o rozważeniu geometrii dziedziny funkcji, a także wszelkich właściwości algebraicznych lub analitycznych wartości funkcji. W tym świetle mi do głowy, że formułę maksymalizującą wariancję można nieznacznie zmodyfikować, aby domena była wypukła: po prostu wymagaj zamiast . Rozwiązanie jest takie samo - a odpowiedź staje się dość jasna.

x^{'} x \leq 1

$x^\prime x\le1$

x^{'} x = 1

$x^\prime x=1$

— whuber

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

Uzyskaj proste wyrażenie dla funkcji celu.
Powiększ swoją domenę, która nie jest wypukła, do tej, która jest.
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

\begin{matrix} (*) & Maximize f (x) = x^{'} A x subject to x^{'} x = 1 \end{matrix}

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

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\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$
Funkcja jest wypukła. $f$ 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 (λ x + (1 - λ) y) \geq λ f (x) + (1 - λ) f (y) .$ $f(\lambda x + (1-\lambda)y) \ge \lambda f(x) + (1-\lambda) f(y).$ $\mathcal X$ $\bar{xy}$ $\mathcal X$ $f$ $(x,f(x))$ $(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 za $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. $(*)$ $\mathcal X$ $S^{n-1}\subset\mathbb{R}^n$ 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$ $\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 $(*)$

\begin{matrix} (**) & Maximize f (x) = x^{'} A x subject to x^{'} x \leq 1 \end{matrix}

$\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, $\mathbb P$ $\mathbb{R}^n$ $\mathbb A$

A = P^{'} Σ P

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

gdzie wszystkie wpisy o przekątnej poniżej $\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 $\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$

σ_{1} \geq σ_{2} \geq \dots \geq σ_{n} \geq 0.

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

Jeśli pozwolimy $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^{'} A y = x^{'} P^{'} A P x = x^{'} Σ x = σ_{1} x_{1}^{2} + σ_{2} x_{2}^{2} + \dots + σ_{n} x_{n}^{2} .

$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 $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) - σ_{1} y^{'} y .

$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 . $\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, $-\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) = σ_{1} x_{1}^{2} + \dots + σ_{n} x_{n}^{2} - σ_{1} (x_{1}^{2} + \dots + x_{n}^{2}) = (σ_{2} - σ_{1}) x_{2}^{2} + \dots + (σ_{n} - σ_{1}) x_{n}^{2} .

$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 $\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 $g$ $\partial D^n=S^{n-1}$ $y^\prime y = 1$ $f$ $g$ $\sigma_1$ $g$ $f$ $D^n$ $f$ $g$ .

— Whuber
źródło

+1 Bardzo miło. Zredagowałem, aby naprawić jedną formułę zgodnie z moim zamierzeniem (ale proszę sprawdzić). Poza tym stwierdziłem, że zdanie „To nie zmieni żadnych wartości granicznych, przy których f jest zoptymalizowany” jest początkowo mylące, ponieważ wartości graniczne się zmieniają: odejmujesz . Może warto trochę przeformułować?

σ_{1}

$\sigma_1$

— ameba mówi Przywróć Monikę

@amoeba Pod każdym względem; Dziękuję Ci. Wzmocniłem dyskusję na ten temat.

— whuber

(+1) W swojej odpowiedzi wydaje się, że definiujesz funkcję wypukłą jako coś, co większość ludzi uważa za funkcję wklęsłą (być może ponieważ problem optymalizacji wypukłej ma domenę wypukłą i funkcję wklęsłą, nad którą obliczane jest maksimum (lub wypukły funkcji na której minimalna jest obliczana))

— user795305

@amoeba To subtelny argument. Zauważ jednak, że nowe maksima - te - występują tylko na granicy. To wyklucza twoje kontrprzykłady. Inną kwestią wartą odnotowania jest to, że ostatecznie nie obchodzi nas, czy nowe lokalne (a nawet globalne) maksima pojawią się we wnętrzu , ponieważ pierwotnie martwimy się tylko o lokalne maksima na jego granicy. W związku z tym możemy dowolnie zmieniać w sposób, który nie spowoduje przesunięcia lub zniknięcia tych maksymalnych granic lokalnych.

g

$g$

X

$\mathcal X$

f

$f$

— whuber

Tak, zgadzam się. Nie ma znaczenia, jak

f

$f$

g

$g$

g

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

— Jakub Bartczuk
źródło

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.

Funkcja celu musi być wypukła.
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}$

— Pszczoła
źródło

X

$X$

k

$k$

X

$X$

k

$k$