Сингулярное разложение
Материал из MachineLearning.
Содержание
Сингулярное разложение (Singular Value Decomposition, SVD) декомпозиция вещественной матрицы с целью ее приведения к каноническому виду. Сингулярное разложение является удобным методом при работе с матрицами. Оно показывает геометрическую структуру матрицы и позволяет наглядно представить имеющиеся данные. Сингулярное разложение используется при решении самых разных задач от приближения методом наименьших квадратов и решения систем уравнений до сжатия изображений. При этом используются разные свойства сингулярного разложения, например, способность показывать ранг матрицы, приближать матрицы данного ранга. SVD позволяет вычислять обратные и псевдообратные матрицы большого размера, что делает его полезным инструментом при решении задач регрессионного анализа.
Матрицы и выбираются так, чтобы диагональные элементы матрицы имели вид
Столбцы матриц и называются соответственно левыми и правыми сингулярными векторами, а значения диагонали матрицы называются сингулярными числами.
имеет сингулярное разложение
Легко увидеть, что матрицы и ортогональны,
также и сумма квадратов значений их столбцов равна единице.
Геометрический смысл SVD
Пусть матрице поставлен в соответствие линейный оператор. Cингулярное разложение можно переформулировать в геометрических терминах. Линейный оператор, отображающий элементы пространства в себя представим в виде последовательно выполняемых линейных операторов вращения, растяжения и вращения. Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отображении линейным оператором множества векторов из векторного пространства в себя или в векторное пространство другой размерности.
Пространства матрицы и SVD
Сингулярное разложение позволяет найти ортогональные базисы различных векторных пространств разлагаемой матрицы
Для прямоугольных матриц существует так называемое экономное представление сингулярного разложения матрицы.
Согласно этому представлению при n» alt= «m>n»/>, диагональная матрица имеет пустые строки (их элементы равны нулю), а при пустые столбцы. Поэтому существует еще одно экономное представление
SVD и собственные числа матрицы
Умножая оба выражения справа соответственно на и получаем
SVD и норма матриц
Евклидова норма матрицы есть максимальный коэффициент растяжения произвольного вектора заданной матрицей
Альтернативой Евклидовой норме является норма Фробениуса:
Сингулярные числа матрицы это длины осей эллипсоида, заданного множеством
Нахождение псевдообратной матрицы с помощью SVD
матрица такая матрица, для которой выполняются условия
Пусть найдено разложение матрицы вида
Метод наименьших квадратов и число обусловленности
вектора невязки, Решение
задачи наименьших квадратов
Из формулы Евклидовой нормы матрицы и предыдущей формулы следует, что число обусловленности матрицы есть отношение ее первого сингулярного числа к последнему.
Усеченное SVD при обращении матриц
Определим усеченную псевдообратную матрицу как
Рекомендательные системы: SVD, часть I
Продолжаем разговор о рекомендательных системах. В прошлый раз мы сделали первую попытку определить схожесть между пользователями и схожесть между продуктами. Сегодня мы подойдём к той же задаче с другой стороны – попытаемся обучить факторы, характеризующие пользователей и продукты. Если Васе из предыдущего поста нравятся фильмы о тракторах и не нравятся фильмы о поросятах, а Петру – наоборот, было бы просто замечательно научиться понимать, какие фильмы «о поросятах», и рекомендовать их Петру, а какие фильмы – «о тракторах», и рекомендовать их Васе.
Напоминаю ещё раз (и, видимо, буду напоминать до конца времён), что у нас есть матрица, состоящая из рейтингов (лайков, фактов покупки и т.п.), которые пользователи (строки матрицы) присвоили продуктам (столбцы матрицы). Давайте присмотримся к матрице 
, в которой записаны известные нам рейтинги. Как правило, один пользователь не сможет оценить значительную долю продуктов, и вряд ли будет много продуктов, которые готова оценить значительная доля пользователей. Это значит, что матрица R разреженная (sparse); нельзя ли этим как-нибудь воспользоваться?
Главным инструментом для нас станет так называемое сингулярное разложение матрицы R:
Сингулярное разложение – это достаточно простой, но очень мощный инструмент. Собственно, это один из главных с практической точки зрения результатов линейной алгебры, и результат уже весьма не новый (свойства SVD были изучены самое позднее в 1930-х годах), – и тем удивительнее бывает, когда университетские курсы линейной алгебры, довольно подробные в каких-то других аспектах, совершенно обходят SVD стороной.
Если у вас есть три минуты, можете насладиться ярким образчиком математического юмора; юмор, конечно, математический, так что не то чтобы смешно, но суть изложена доходчиво, а музыка наверняка понравится любителям… хм, на хабре, наверное, лучше будет сказать, что понравится любителям Fallout:
На случай, если трёх минут всё-таки не нашлось, я выделю главное для нас свойство: если R – матрица большого размера , но малого ранга f (в частности, разреженные матрицы часто бывают малого ранга), её можно разложить в произведение матрицы и матрицы , тем самым резко сократив число параметров, c NM до (N+M)f (чтобы понять, что это большой прогресс, представьте, что, как это обычно бывает на практике, N и M измеряются сотнями тысяч и миллионами, а f меньше десятка).
SVD очень широко употребляется в машинном обучении; фактически, если вы хотите что-то чем-то приблизить, не исключено, что вам где-то по дороге встретится SVD. Классический пример применения SVD – шумоподавление, например, в изображениях. Рассмотрим (чёрно-белое) изображение как матрицу X размера , элементы которой – интенсивности каждого пикселя. Теперь попробуем выбрать f столбцов пикселей из изображения, счесть их «репрезентативными» и представить каждый из оставшихся столбцов в виде линейной комбинации этих. Я не буду сейчас углубляться в математику, но в результате, когда вы найдёте оптимальные представления каждого столбца, получится, что вы представили исходную матрицу в виде произведения матриц размера и , то есть как раз приблизили матрицу X матрицей малого ранга f.
Основное же свойство SVD – в том, что SVD даёт оптимальное такое приближение, если в матрице D просто оставить ровно f первых диагональных элементов, а остальные занулить:
В диагональной матрице D, которая в середине сингулярного разложения, элементы упорядочены по размеру: , так что обнулить последние элементы – это значит обнулить наименьшие элементы.
Если хорошо подобрать f, то в результате изображение и в весе потеряет, и шума на нём станет меньше. А f в данном случае можно подбирать, исходя из размера сингулярных значений матрицы, т.е. тех самых диагональных элементов матрицы D: желательно отбрасывать как можно больше, но при этом как можно более маленьких таких элементов.
Но мы отвлеклись. В случае рекомендательных систем получается, что мы представляем каждого пользователя вектором из f факторов и представляем каждый продукт вектором из f факторов , а потом, чтобы предсказать рейтинг пользователя i товару j, берём их скалярное произведение . Можно сказать, что вектор факторов пользователя показывает, насколько пользователю нравится или не нравится тот или иной фактор, а вектор факторов продукта показывает, насколько тот или иной фактор в продукте выражен. Линейная же алгебра подсказывает нам, что для разреженной матрицы рейтингов такое разложение часто возможно и имеет содержательный смысл.
Может оказаться, кстати, что некоторые факторы легко будет понять человеческим умом: для фильмов может выделиться что-нибудь в духе «комедия–драма», «доля action’а», «доля романтики» и т.п., а факторы пользователей, соответственно, будут показывать, насколько соответствующие характеристики фильма им по вкусу. Но может и не выделиться ничего содержательного – тут гарантий нет, формально мы просто жонглируем цифрами.
В следующий раз мы превратим эту базовую идею – приблизить матрицу рейтингов матрицей малого ранга посредством SVD – в хорошо поставленную задачу оптимизации и научимся её решать.
Как уменьшить количество измерений и извлечь из этого пользу
Сначала я хотел честно и подробно написать о методах снижения размерности данных — PCA, ICA, NMF, вывалить кучу формул и сказать, какую же важную роль играет SVD во всем этом зоопарке. Потом понял, что получится текст, похожий на вырезки из опусов от Mathgen, поэтому количество формул свел к минимуму, но самое любимое — код и картинки — оставил в полном объеме.
Еще думал написать об автоэнкодерах. В R же, как известно, беда с нейросетевыми библиотеками: либо медленные, либо глючные, либо примитивные. Это и понятно, ведь без полноценной поддержки GPU (и в этом огромный минус R по сравнению с Python) работа со сколь-нибудь сложными нейронными сетями — и в особенности с Deep Learning — практически бессмысленна (хотя есть подающий надежды развивающийся проект MXNet ). Интересен также относительно свежий фреймворк h2o, авторов которого консультирует небезызвестный Trevor Hastie, а Cisco, eBay и PayPal даже используют его для создания своих планов по порабощению человечества. Фреймворк написан на Java (да-да, и очень любит оперативную память). К сожалению, он тоже не поддерживает работу с GPU, т.к. имеет несколько иную целевую аудиторию, но зато отлично масштабируется и предоставляет интерфейс к R и Python (хотя любители мазохизма могут воспользоваться и висящем по дефолту на localhost:54321 web-интерфейсом).
Так вот, если уж возник вопрос о количестве измерений в наборе данных, то это значит, что их, ну, скажем так, довольно много, из-за чего применение алгоритмов машинного обучения становится не совсем удобным. А иногда часть данных — всего лишь информационный шум, бесполезный мусор. Поэтому лишние измерения желательно убрать, вытащив из них по возможности все самое ценное. Кстати, может возникнуть и обратная задача — добавить еще измерений, а попросту — больше интересных и полезных фич. Выделенные компоненты могут быть полезны и для целей визуализации (t-SNE на это, например, и ориентирован). Алгоритмы декомпозиции интересны и сами по себе в качестве машинных методов обучения без учителя, что, согласитесь, иногда может и вовсе привести к решению первичной задачи.
Матричные разложения
В принципе, для сокращения размерности данных с той или иной эффективностью можно приспособить большинство методов машинного обучения — этим, собственно, они и занимаются, отображая одни многомерные пространства в другие. Например, результаты работы PCA и K-means в некотором смысле эквивалентны. Но обычно хочется сокращать размерность данных без особой возни с поиском параметров модели. Самым важным среди таких методов, конечно же, является SVD. «Почему SVD, а не PCA?» — спросите вы. Потому что SVD, во-первых, само по себе является отдельной важной методикой при анализе данных, а полученные в результате разложения матрицы имеют вполне осмысленную интерпретацию с точки зрения машинного обучения; во-вторых, его можно использовать для PCA и с некоторыми оговорками для NMF (как и других методов факторизации матриц); в-третьих, SVD можно приспособить для улучшения результатов работы ICA. Кроме того, у SVD нет таких неудобных свойств, как, например, применимость только к квадратным (разложения LU, Schur) или квадратным симметричным положительно определенным матрицам (Cholesky), или только к матрицам, элементы которых неотрицательны (NMF). Естественно, за универсальность приходится платить — сингулярное разложение довольно медленное; поэтому, когда матрицы слишком большие, применяют рандомизированные алгоритмы.
Что будет, если из исходного изображения вычесть средние значения каждого столбца, разделить полученную матрицу на корень квадратный из количества столбцов в исходной матрице, а потом выполнить сингулярное разложение? Оказывается, что столбцы матрицы V в полученном разложении в точности будут соответствовать главным компонентам, которые получаются при PCA (к слову, в R для PCA можно использовать функцию prcomp() )
Вернемся к вопросу выбора количества главных компонент. Капитанское правило такое: чем больше компонент, тем больше дисперсии они описывают. Andrew Ng, например, советует ориентироваться на >90% дисперсии. Другие исследователи утверждают, что это число может быть и 50%. Даже придуман так называемый параллельный анализ Хорна, который основывается на симуляции Монте-Карло. В R для этого и пакет есть. Совсем простой подход — использовать scree plot: на графике надо искать «локоть» и отбрасывать все компоненты, которые формируют пологую часть этого «локтя». На рисунке ниже, я бы сказал, надо учитывать 6 компонент:
В общем, как вы видите. вопрос неплохо проработан. Также бытует мнение, что PCA применим только для нормально распределенных данных, но Wiki с этим не согласна, и SVD/PCA можно использовать с данными любого распределения, но, конечно, не всегда результативно (что выясняется эмпирически).
Еще одно интересное разложение — это факторизация неотрицательных матриц, которая, как следует из названия, применяется для разложения неотрицательных матриц на неотрицательные матрицы:
X=WH.
В целом, такая задача не имеет точного решения (в отличие от SVD), и для ёё вычисления используют численные алгоритмы. Задачу можно сформулировать в терминах квадратичного программирования — и в этом смысле она будет близка к SVM. В проблеме же сокращения размерности пространства важным является вот что: если матрица Х имеет размерность m x n, то соответственно матрицы W и H имеют размерности m x k и k x n, и, выбирая k намного меньше самих m и n, можно значительно урезать эту самую исходную размерность. NMF любят применят для анализа текстовых данных, там, где неотрицательные матрицы хорошо согласуются с самой природой данных, но в целом спектр применения методики не уступает PCA. Разложение первой картинки в R дает такой результат:
Если требуется что-то более экзотичное
Какое отношение имеет ICA к задаче уменьшения размерности данных? Попробуем представить данные — вне зависимости от их природы — как смесь компонент, тогда можно будет разделить эту смесь на то количество «сигналов», которое нам подходит. Особого критерия, как в случае с PCA, по выбору количества компонент нет — оно подбирается экспериментально.
В самом простом представлении автоэнкодер можно смоделировать как многослойный перцептрон, в котором количество нейронов в выходном слое равно количеству входов. Из рисунка ниже понятно, что, выбирая промежуточный скрытый слой малой размерности, мы тем самым «сжимаем» исходные данные.
Вышеозначенный автоэнкодер несложно превратить в denoising autoencoder. Так как такому автокодировщику на вход надо подавать искаженные образы, перед первым скрытым слоем достаточно разместить dropout слой. Благодаря ему с некоторой вероятностью нейроны будут находиться в «выключенном» состоянии, что а) будет вносить искажения в обрабатываемый образ; б) будет служить своеобразной регуляризацией при обучении.
Еще одно интересное применение автоэнкодера — определение аномалий в данных по ошибке реконструкции образов. В целом, если подавать на вход автоэнкодера данные не из обучающей выборки, то, понятно, ошибка реконструкции каждого образа из новой выборки будет выше таковой из тренировочной выборки, но более-менее одного порядка. При наличии аномалий эта ошибка будет в десятки, а то и сотни раз больше.
Сингулярное разложение
Материал из MachineLearning.
Содержание
Сингулярное разложение (Singular Value Decomposition, SVD) декомпозиция вещественной матрицы с целью ее приведения к каноническому виду. Сингулярное разложение является удобным методом при работе с матрицами. Оно показывает геометрическую структуру матрицы и позволяет наглядно представить имеющиеся данные. Сингулярное разложение используется при решении самых разных задач от приближения методом наименьших квадратов и решения систем уравнений до сжатия изображений. При этом используются разные свойства сингулярного разложения, например, способность показывать ранг матрицы, приближать матрицы данного ранга. SVD позволяет вычислять обратные и псевдообратные матрицы большого размера, что делает его полезным инструментом при решении задач регрессионного анализа.
Матрицы и выбираются так, чтобы диагональные элементы матрицы имели вид
Столбцы матриц и называются соответственно левыми и правыми сингулярными векторами, а значения диагонали матрицы называются сингулярными числами.
имеет сингулярное разложение
Легко увидеть, что матрицы и ортогональны,
также и сумма квадратов значений их столбцов равна единице.
Геометрический смысл SVD
Пусть матрице поставлен в соответствие линейный оператор. Cингулярное разложение можно переформулировать в геометрических терминах. Линейный оператор, отображающий элементы пространства в себя представим в виде последовательно выполняемых линейных операторов вращения, растяжения и вращения. Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отображении линейным оператором множества векторов из векторного пространства в себя или в векторное пространство другой размерности.
Пространства матрицы и SVD
Сингулярное разложение позволяет найти ортогональные базисы различных векторных пространств разлагаемой матрицы
Для прямоугольных матриц существует так называемое экономное представление сингулярного разложения матрицы.
Согласно этому представлению при n» alt= «m>n»/>, диагональная матрица имеет пустые строки (их элементы равны нулю), а при пустые столбцы. Поэтому существует еще одно экономное представление
SVD и собственные числа матрицы
Умножая оба выражения справа соответственно на и получаем
SVD и норма матриц
Евклидова норма матрицы есть максимальный коэффициент растяжения произвольного вектора заданной матрицей
Альтернативой Евклидовой норме является норма Фробениуса:
Сингулярные числа матрицы это длины осей эллипсоида, заданного множеством
Нахождение псевдообратной матрицы с помощью SVD
матрица такая матрица, для которой выполняются условия
Пусть найдено разложение матрицы вида
Метод наименьших квадратов и число обусловленности
вектора невязки, Решение
задачи наименьших квадратов
Из формулы Евклидовой нормы матрицы и предыдущей формулы следует, что число обусловленности матрицы есть отношение ее первого сингулярного числа к последнему.
Усеченное SVD при обращении матриц
Определим усеченную псевдообратную матрицу как
Простой итерационный алгоритм сингулярного разложения
Материал из MachineLearning.
Простой итерационный алгоритм сингулярного разложения матриц допускает простую высокопараллельную (в том числе, нейросетевую) реализацию. Сингулярное разложение матриц (англ. Singular value decomposition) необходимо для решения многих задач анализа данных. В том числе, анализ главных компонент сводится к сингулярному разложению матрицы центрированных данных.
Содержание
Идея сингулярного разложения матрицы данных
Пусть — ранг матрицы данных. Сингулярное разложение матрицы данных — это её представление в виде
Простой итерационный алгоритм сингулярного разложения
Аналогично, при фиксированном векторе определяются значения :
Существуют различные модификации базового алгоритма, улучшающие точность и устойчивость. Например, векторы главных компонент при разных должны быть ортогональны «по построению», однако при большом числе итерации (большая размерность, много компонент) малые отклонения от ортогональности накапливаются и может потребоваться специальная коррекция на каждом шаге, обеспечивающая его ортогональность ранее найденным главным компонентам.
Для квадратных симметричных положительно определённых матриц описанный алгоритм превращается в метод прямых итераций для поиска собственных векторов.
Сингулярное разложение тензоров и тензорный метод главных компонент
Это многокомпонентное сингулярное разложение (тензорный метод главных компонент) успешно применяется при обработка изображений, видеосигналов, и, шире, любых данных, имеющих табличную или тензорную структуру.
