Jaka jest intuicja stojąca za SVD?

50

Czytałem o rozkładzie wartości pojedynczej (SVD). W prawie wszystkich podręcznikach wspomniano, że rozkłada macierz na trzy macierze o podanej specyfikacji.

Ale jaka jest intuicja dzielenia macierzy w takiej formie? PCA i inne algorytmy redukcji wymiarów są intuicyjne w tym sensie, że algorytm ma ładną właściwość wizualizacji, ale w przypadku SVD tak nie jest.

SHASHANK GUPTA
źródło
4
Możesz zacząć od intuicji rozkładu wartości własnej i wektora własnego, ponieważ SVD jest jego rozszerzeniem dla wszystkich rodzajów matryc, a nie tylko kwadratowych.
JohnK
W Internecie jest wiele notatek i odpowiedzi na CV o SVD i jego funkcjonowaniu.
Vladislavs Dovgalecs
2
SVD można uważać za algorytm kompresji / uczenia się. Jest to dekompresor sprężarki liniowej. Macierz M może być reprezentowana przez pomnożenie SVD. S jest kompresorem V określa, ile błędów chciałbyś (kompresja stratna), a D jest dekompresorem. Jeśli zachowasz wszystkie wartości diagonalne V, masz sprężarkę bezstratną. Jeśli zaczniesz wyrzucać małe liczby pojedyncze (je zerujesz), nie możesz dokładnie zrekonstruować początkowej macierzy, ale nadal będzie blisko. Tutaj termin zamknięcia mierzy się normą Frobenius.
Cagdas Ozgenc
2
@ Cagdas, jeśli to zrobisz, proszę dokładnie zdefiniować, co bierzesz „S”, „V” i „D”, aby być matematycznym. Nigdy wcześniej nie widziałem, by inicjały były przeciążone w samej notacji (która zawiera na przykład osobliwe wartości?). Wydaje się, że może to być źródłem zamieszania,
Glen_b
3
Czy wiesz, jak oszacować PCA za pomocą SVD? Jeśli tak, to czy możesz wyjaśnić, dlaczego uważasz, że czegoś brakuje w twoim rozumieniu SVD? Zobacz to
Aksakal,

Odpowiedzi:

63

Zapisz SVD macierzy (rzeczywistej, n × p ) jako X = U D V T, gdzie U to n × p , D to przekątna p × p, a V T to p × p . Jeśli chodzi o kolumny macierzy U i V , możemy napisać X = p i = 1 d i u i v T iXn×p

X=UDVT
Un×pDp×pVTp×pUVX=i=1pdiuiviT. To pokazuje zapisany jako suma macierzy p rank-1. Jak wygląda matryca rangi 1? Zobaczmy: ( 1 2 3 ) ( 4 5 6 ) = ( 4 5 6 8 10 12 12 15 18 ) Wiersze są proporcjonalne, a kolumny proporcjonalne.Xp
(123)(456)=(45681012121518)

Pomyśl teraz o jako zawierającym wartości w skali szarości czarno-białego obrazu, każdy wpis w macierzy reprezentuje jeden piksel. Na przykład następujące zdjęcie pawiana:X

obraz pawiana

Następnie wczytaj ten obraz do R i pobierz część macierzową wynikowej struktury, być może używając biblioteki pixmap.


Jeśli potrzebujesz przewodnika krok po kroku, jak odtworzyć wyniki, możesz znaleźć kod tutaj .


Oblicz SVD:

baboon.svd  <-  svd(bab) # May take some time

512×512512512120

baboon.1  <-  sweep(baboon.svd$u[,1,drop=FALSE],2,baboon.svd$d[1],"*") %*%
                   t(baboon.svd$v[,1,drop=FALSE])

baboon.20 <-  sweep(baboon.svd$u[,1:20,drop=FALSE],2,baboon.svd$d[1:20],"*") %*%
                   t(baboon.svd$v[,1:20,drop=FALSE])

w wyniku czego powstają następujące dwa obrazy:

pozycja 1 i pozycja 20 rekonstrukcja obrazu pawiana

Po lewej stronie możemy łatwo zobaczyć pionowe / poziome paski na obrazie rangi 1.

20

obraz pozostałości z rekonstrukcji pawiana rangi 20

Co jest dość interesujące: widzimy fragmenty oryginalnego obrazu, które trudno jest przedstawić jako superpozycję pionowych / poziomych linii, głównie ukośne włosy na nosie i trochę tekstury oraz oczy!

kjetil b halvorsen
źródło
11
Myślę, że miałeś na myśli rekonstrukcję niskiej rangi, a nie niski zasięg. Nieważne. To bardzo dobra ilustracja (+1). Dlatego jest to dekompresor z kompresorem liniowym. Obraz jest przybliżony liniami. Jeśli faktycznie wykonasz podobny autoencoder z siecią neuronową z liniowymi funkcjami aktywacji, zobaczysz, że pozwala on również na linie o dowolnym nachyleniu nie tylko linii pionowych i poziomych, co czyni go nieco mocniejszym niż SVD.
Cagdas Ozgenc
X=UΣVn×pXUn×nΣn×pVp×p
1
Zobacz math.stackexchange.com/questions/92171/... niektórych innych przykładów
Kjetil b Halvorsen
@ kjetil-b-halvorsen Chciałbym wiedzieć, jak zmieniłaby się opis, gdybym użył PCA do odrzucenia wniosku. Byłbym wdzięczny, gdybyś mógł odpowiedzieć na moje pytanie tutaj stats.stackexchange.com/questions/412123/…
Dushyant Kumar
@CowboyTrader ciekawa obserwacja. Moje rozumienie uczenia maszynowego / sieci neuronowej jest dość ograniczone. Więc nie rozumiem, że jeśli ktoś ma jeden hałaśliwy obraz i nie ma nic innego do trenowania, jak działałaby sieć neuronowa?
Dushyant Kumar
3

Am×nmnvA

(1)v1=argmaxvRnAv2subject to v2=1.
v1A
v2=argmaxvRnAv2subject to v1,v=0,v2=1.
v1,,vnRnRnA

Niech (więc określa moc wybuchową w kierunku ). Załóżmy, że wektory jednostkowe są zdefiniowane tak, że Równania (2) można wyrazić zwięźle za pomocą notacji macierzowej jako gdzie jest macierzą , której ta kolumna to , jest macierzą , której kolumna to , aσi=Avi2σiAviui

(2)Avi=σiuifor i=1,,n.
(3)AV=UΣ,
Vn×niviUm×niuiΣjest macierzą diagonalną, której tym wpisem jest . Macierz jest ortogonalna, więc możemy pomnożyć obie strony (3) przez aby otrzymać Może się wydawać, że wyprowadziliśmy SVD z przy prawie zerowym wysiłku. Żaden z dotychczasowych kroków nie był trudny. Brakuje jednak kluczowego fragmentu obrazu - nie wiemy jeszcze, że jest ortogonalny.n×niσiVVT
A=UΣVT.
AU

Oto kluczowy fakt, brakujący element: okazuje się, że jest prostopadła do : Twierdzę, że jeśli to nie była prawda, to nie byłoby optymalne dla problemu (1). Rzeczywiście, jeśli (4) nie byłby spełniony, wówczas można by ulepszyć , zaburzając go nieco w kierunku .Av1Av2

(4)Av1,Av2=0.
v1 v1v2

Załóżmy (dla sprzeczności), że (4) nie jest spełniony. Jeśli jest lekko zaburzone w kierunku ortogonalnym , norma się nie zmienia (lub przynajmniej zmiana normy jest nieistotna). Kiedy chodzę po powierzchni ziemi, moja odległość od jej środka nie zmienia się. Jednakże, gdy jest zaburzone w kierunku , wektor jest zaburzony w nieortogonalnym kierunku , a zatem zmiana normy jest nieistotna . Normav1v2v1v1v1v2Av1Av2Av1Av1można zwiększyć o nie mniej znaczącą kwotę. Oznacza to, że nie jest optymalny dla problemu (1), co jest sprzecznością. Podoba mi się ten argument, ponieważ: 1) intuicja jest bardzo jasna; 2) intuicję można przekształcić bezpośrednio w rygorystyczny dowód.v1

Podobny argument pokazuje, że jest ortogonalny zarówno dla i i tak dalej. Wektory są parami ortogonalne. Oznacza to, że wektory jednostkowe mogą być wybrane jako pary ortogonalne, co oznacza, że ​​macierz powyżej jest macierzą ortogonalną. To kończy nasze odkrycie SVD.Av3Av1Av2Av1,,Avnu1,,unU


Aby przekonwertować powyższy intuicyjny argument na rygorystyczny dowód, musimy skonfrontować fakt, że jeśli jest zakłócony w kierunku , zaburzony wektor nie jest w rzeczywistości wektorem jednostkowym. (Jego normą jest .) Aby uzyskać dokładny dowód, zdefiniuj Wektor jest naprawdę wektorem jednostkowym. Ale jak można łatwo wykazać, jeśli (4) nie jest spełniony, to dla wystarczająco małych wartości mamy (przy założeniu, że znakv1v2

v~1=v1+ϵv2
1+ϵ2
v¯1(ϵ)=1ϵ2v1+ϵv2.
v¯1(ϵ)ϵ
f(ϵ)=Av¯1(ϵ)22>Av122
ϵjest wybrany poprawnie). Aby to pokazać, po prostu sprawdź, czy . Oznacza to, że nie jest optymalny dla problemu (1), co jest sprzecznością.f(0)0v1

(Nawiasem mówiąc, polecam czytanie wyjaśnienie Qiaochu juana z SVD tutaj . W szczególności przyjrzeć się „Key lemat # 1”, czyli to, co omówiono powyżej. Jak mówi Qiaochu, klucz lemat nr 1 to „serce techniczny o rozkładzie pojedynczej wartości ”.)

littleO
źródło
0

Koleś, poświęć godzinę dnia i obejrzyj ten wykład: https://www.youtube.com/watch?v=EokL7E6o1AE

Ten facet jest bardzo bezpośredni, ważne jest, aby nie pominąć żadnego z nich, ponieważ w końcu wszystko się łączy. Nawet jeśli na początku może się to wydawać trochę powolne, próbuje określić punkt krytyczny, co robi!

Podsumuję to dla ciebie, zamiast po prostu dać ci trzy matryce, które wszyscy robią (ponieważ to mnie pomyliło, gdy przeczytałem inne opisy). Skąd się biorą te matryce i dlaczego tak to konfigurujemy? Wykład to gwoździe! Każdą macierz (kiedykolwiek w historii wieczności) można zbudować z macierzy podstawowej o tych samych wymiarach, a następnie obrócić ją i rozciągnąć (jest to podstawowe twierdzenie algebry liniowej). Każda z tych trzech matryc, którymi ludzie się rzucają, reprezentuje macierz początkową (U), macierz skalowania A (sigma) i macierz obrotu (V).

Macierz skalowania pokazuje, które wektory obrotu dominują, są to tak zwane wartości osobliwe. Rozkład rozwiązuje się dla U, sigma i V.

Tim Johnsen
źródło