Czy optymalizacja PCA jest wypukła?

13

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
3
Nie. Maksymalizujesz funkcję wypukłą (pod ograniczeniami).
user603
5
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ą. xAxxx=1xx=1
whuber
1
@ 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
3
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 = 1xx1xx=1
whuber

Odpowiedzi:

18

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

(*)Maximize f(x)= xAx  subject to  xx=1

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).An×nA

(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 ( )xAx/xxxλ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 : XRxXf:XR

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

  1. Domeny jest wypukła. XRn 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 XxXyX0λ1λx+(1λ)yX również . Geometrycznie: gdy dwa punkty końcowe kłamstwie Odcinek , cała kłamstwa segmentów w .XX

  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 .xXyX0λ1

    f(λx+(1λ)y)λf(x)+(1λ)f(y).
    Xxy¯Xf(x,f(x))R n + 1(y,f(y))Rn+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 0.yay2+by+ca0.

Trudność z polega na tym, że jest sferą jednostkową , która zdecydowanie nie jest wypukła. X S n - 1R n()XSn1Rn 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λ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 .λ20<xx<1xfDn={x R nxx1}()λ=1/xx>1f Dn={xRnxx1} Przeformułujmy zatem jako()

(**)Maximize f(x)= xAx  subject to  xx1

Jego domeną jest która wyraźnie jest wypukła, więc jesteśmy w połowie drogi. Pozostaje rozważyć wypukłość wykresu . fX=Dnf

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 APRnA

A=PΣP

gdzie wszystkie wpisy o przekątnej poniżej P A x x A xΣ 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.PAxxAx

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

σ1σ2σn0.

Jeśli pozwolimy x y = P x fx=Py być nowymi współrzędnymi (pociągając za sobą ), funkcja jestxy=Pxf

f(y)=yAy=xPAPx=xΣx=σ1x12+σ2x22++σnxn2.

Ta funkcja zdecydowanie nie jest wypukła! Jego wykres wygląda jak część hiperparaboloidu: w każdym punkcie wnętrzaσ iX fakt, że wszystkie są nieujemne, powoduje, że zwija się on w górę, a nie w dół . σ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 σ 1xx=1σ1fXf jest zoptymalizowany, ponieważ obniża wszystkie wartości na granicy o tę samą wartość . Sugeruje to zbadanie funkcjifσ1

g(y)=f(y)σ1yy.

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 Xσ1fgfX

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 gσ1σ1yyPyy=xx . (Jest to praktycznie definicja transformacji ortogonalnej.) Dlatego też, jeśli chodzi o współrzędne , można zapisaćxg

g(y)=σ1x12++σnxn2σ1(x12++xn2)=(σ2σ1)x22++(σnσ1)xn2.

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 ) Pσ1σiiggx2=x3==xn=0xx=1x1=±1y=P(±1,0,,0) , czyli - do znak - pierwsza kolumna )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 maksimamiD n = S n - 1 y y = 1 f g σ 1gDn=Sn1yy=1fgσ1f D n f ggfDnfg .

Whuber
źródło
4
+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
ameba mówi Przywróć Monikę
@amoeba Pod każdym względem; Dziękuję Ci. Wzmocniłem dyskusję na ten temat.
whuber
3
(+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
2
@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. X fgXf
whuber
2
Tak, zgadzam się. Nie ma znaczenia, jakfgg
6

Nie.

kM

X^=argminrank(X)kMXF2

( jest normą Frobeniusa ). Wyprowadzenie patrz twierdzenie Eckarta-Younga .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

X^=argminXcMXF2

( to norma jądrowa . wypukła relaksacja rangi - podobnie jak to wypukła relaksacja liczby elementów niezerowych dla wektorów)11

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
1

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,J11J22

Pszczoła
źródło
Xk
Xk