Какая интуиция стоит за СВД?

50

Я читал о разложении сингулярных значений (SVD). Почти во всех учебниках упоминается, что она разбивает матрицу на три матрицы с заданной спецификацией.

Но какова интуиция, лежащая в основе разделения матрицы в такой форме? PCA и другие алгоритмы уменьшения размерности интуитивно понятны в том смысле, что алгоритм обладает хорошим свойством визуализации, но с SVD это не так.

ШАШАНК ГУПТА
источник
4
Возможно, вы захотите начать с интуиции разложения по собственному значению на собственный вектор, поскольку SVD является его расширением для всех видов матриц, а не только для квадратных.
JohnK
В интернете есть множество заметок и ответов на вопросы о СВД и его работе.
Владислав Довгальец
2
SVD можно рассматривать как алгоритм сжатия / обучения. Это линейный компрессор-декомпрессор. Матрица M может быть представлена ​​умножением SVD. S - компрессор. V определяет, какую ошибку вы хотели бы иметь (сжатие с потерями), а D - декомпрессор. Если вы сохраняете все диагональные значения V, то у вас есть компрессор без потерь. Если вы начнете отбрасывать небольшие сингулярные значения (обнулять их), то вы не сможете восстановить исходную матрицу точно, но все равно будете близки. Здесь термин близкий измеряется по норме Фробениуса.
Кагдас Озгенц
2
@Cagdas, если вы сделаете это, пожалуйста, тщательно определите, что вы принимаете "S", "V" и "D", чтобы быть математически. Я не видел инициалов, перегруженных в самой нотации ранее (в которой, к примеру, есть особые значения?). Кажется, это может быть источником путаницы,
Glen_b
3
Знаете ли вы, как оценить PCA с SVD? Если да, то можете ли вы объяснить, почему вы чувствуете, что чего-то не хватает в вашем понимании SVD? Смотрите это
Аксакал

Ответы:

63

Запишите SVD матрицы (вещественное, n × p ) как X = U D V T, где U - n × p , D - диагональ p × p, а V T - p × p . В терминах столбцов матриц U и V мы можем записать X = p i = 1 d i u i v T iXn×p

X=UDVT
Un×pDp×pVTp×pUVX=i=1pdiuiviT, Это показывает, что записано в виде суммы p рангов-1 матриц. Как выглядит матрица ранга 1? Давайте посмотрим: ( 1 2 3 ) ( 4 5 6 ) = ( 4 5 6 8 10 12 12 15 18 ) Строки пропорциональны, а столбцы пропорциональны.Xp
(123)(456)=(45681012121518)

Теперь представьте, что содержит значения черно-белого изображения в оттенках серого, каждая запись в матрице представляет один пиксель. Например, следующая картина бабуина:X

образ бабуина

Затем прочитайте это изображение в R и получите матричную часть полученной структуры, возможно, используя библиотеку pixmap.


Если вы хотите получить пошаговое руководство по воспроизведению результатов, вы можете найти код здесь .


Рассчитаем СВД:

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

в результате чего получаются следующие два изображения:

ранг один и ранг 20 реконструкция образа бабуина

Слева мы можем легко увидеть вертикальные / горизонтальные полосы на изображении ранга 1.

20

изображение остатков от реконструкции павиана 20 ранга

Что довольно интересно: мы видим части исходного изображения, которые трудно представить как суперпозицию вертикальных / горизонтальных линий, в основном волосы диагонального носа и некоторую текстуру, а также глаза!

Къетил б Халворсен
источник
11
Я думаю, что вы имели в виду реконструкцию низкого ранга, а не низкого диапазона. Неважно. Это очень хорошая иллюстрация (+1). Вот почему это линейный компрессор-декомпрессор. Изображение аппроксимируется линиями. Если вы на самом деле выполняете аналогичный авто-кодер с нейронной сетью с функциями линейной активации, вы фактически увидите, что он также допускает линии с любым наклоном, а не только вертикальные и горизонтальные линии, что делает его немного более мощным, чем SVD.
Кагдас Озгенц
X=UΣVn×pXUn×nΣn×pVp×p
1
См. Math.stackexchange.com/questions/92171/… для других примеров
kjetil b halvorsen
@ kjetil-b-halvorsen Мне интересно знать, как изменится расшифровка, если бы я использовал PCA для отклонения заявки. Буду признателен, если вы ответите на мой вопрос здесь stats.stackexchange.com/questions/412123/…
Кумар
@CowboyTrader интересное наблюдение. Мое понимание машинного обучения / нейронной сети довольно ограничено. Итак, я не понимаю, что если у кого-то будет один шумный образ и больше нечего тренироваться, как будет работать нейронная сеть?
Душянт Кумар
4

Am×nmnvA

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

Пусть (поэтому количественно определяет взрывную силу в направлении ). Предположим, что единичные векторы определены так, что Уравнения (2) могут быть кратко выражены с использованием матричной записи в виде где - матрица , й столбец которой равен , - матрица чья столбец иσi=Avi2σiAviui

(2)Avi=σiuifor i=1,,n.
(3)AV=UΣ,
Vn×niviUm×niuiΣэто диагональная матрица, й диагональный элемент которой равен . Матрица ортогональна, поэтому мы можем умножить обе части (3) на чтобы получить Может показаться, что теперь мы вывели SVD из с почти нулевым усилием. Ни один из шагов до сих пор не был сложным. Однако важная часть картины отсутствует - мы еще не знаем, что ортогонально.n×niσiVVT
A=UΣVT.
AU

Вот ключевой факт, отсутствующий фрагмент: оказывается, что ортогонален : Я утверждаю, что если это не так, то не будет оптимальным для задачи (1). Действительно, если бы (4) не было выполнено, то можно было бы улучшить , немного его возмутив в направлении .Av1Av2

(4)Av1,Av2=0.
v1 v1v2

Предположим (для противоречия), что (4) не выполняется. Если слегка возмущается в ортогональном направлении , норма не изменяется (или, по крайней мере, изменение нормы незначительно). Когда я иду по поверхности земли, мое расстояние от центра Земли не меняется. Однако, когда возмущается в направлении , вектор возмущается в неортогональном направлении , и поэтому изменение нормы является пренебрежимо малым . Нормаv1v2v1v1v1v2Av1Av2Av1Av1может быть увеличено на незначительную сумму. Это означает, что не является оптимальным для задачи (1), что противоречит. Мне нравится этот аргумент, потому что: 1) интуиция очень ясна; 2) интуиция может быть преобразована непосредственно в строгое доказательство.v1

Аналогичный аргумент показывает, что является ортогональным как к и к , и так далее. Векторы попарно ортогональны. Это означает, что единичные векторы могут быть выбраны попарно ортогональными, что означает, что матрица выше является ортогональной матрицей. Это завершает наше открытие СВД.Av3Av1Av2Av1,,Avnu1,,unU


Чтобы преобразовать приведенный выше интуитивный аргумент в строгое доказательство, мы должны учитывать тот факт, что если возмущен в направлении , возмущенный вектор действительно не является единичным вектором. (Его норма .) Чтобы получить строгое доказательство, определите Вектор действительно является единичным вектором. Но, как вы можете легко показать, если (4) не выполняется, то для достаточно малых значений имеем (при условии, что знакv1v2

v~1=v1+ϵv2
1+ϵ2
v¯1(ϵ)=1ϵ2v1+ϵv2.
v¯1(ϵ)ϵ
f(ϵ)=Av¯1(ϵ)22>Av122
ϵвыбран правильно). Чтобы показать это, просто проверьте, что . Это означает, что не является оптимальным для задачи (1), что противоречит.f(0)0v1

(Кстати, я рекомендую прочитать объяснение Qiaochu Юаня из СВДА здесь . В частности, обратите внимание на «Key лемме # 1», которая является то , что мы обсуждали выше. Как Qiaochu говорит, ключевая лемму # 1 является «техническим сердцем разложения по сингулярным числам ".)

littleO
источник
0

Чувак, потрать час своего дня и посмотри эту лекцию: https://www.youtube.com/watch?v=EokL7E6o1AE

Этот парень очень прямолинеен, важно не пропускать ничего из этого, потому что в конце концов все сводится вместе. Даже если вначале это может показаться немного медленным, он пытается определить критическую точку, что он и делает!

Я подведу итог для вас, вместо того, чтобы просто дать вам три матрицы, которые все делают (потому что это сбивало меня с толку, когда я читал другие описания). Откуда взялись эти матрицы и почему мы так настроили их? Лекция прибивает это! Каждая матрица (когда-либо существовавшая в истории вечности) может быть построена из базовой матрицы с одинаковыми размерами, затем повернуть ее и растянуть (это основная теорема линейной алгебры). Каждая из этих трех матриц, которые бросают люди, представляет собой исходную матрицу (U), матрицу масштабирования (сигма) и матрицу вращения (V).

Матрица масштабирования показывает, какие векторы вращения являются доминирующими, они называются сингулярными значениями. Разложение является решающим для U, сигма и V.

Тим Джонсен
источник