Как сделать сингулярное разложение матрицы
Сингулярное разложение
Материал из MachineLearning.
Содержание
Сингулярное разложение (Singular Value Decomposition, SVD) декомпозиция вещественной матрицы с целью ее приведения к каноническому виду. Сингулярное разложение является удобным методом при работе с матрицами. Оно показывает геометрическую структуру матрицы и позволяет наглядно представить имеющиеся данные. Сингулярное разложение используется при решении самых разных задач от приближения методом наименьших квадратов и решения систем уравнений до сжатия изображений. При этом используются разные свойства сингулярного разложения, например, способность показывать ранг матрицы, приближать матрицы данного ранга. SVD позволяет вычислять обратные и псевдообратные матрицы большого размера, что делает его полезным инструментом при решении задач регрессионного анализа.
Матрицы и выбираются так, чтобы диагональные элементы матрицы имели вид
Столбцы матриц и называются соответственно левыми и правыми сингулярными векторами, а значения диагонали матрицы называются сингулярными числами.
имеет сингулярное разложение
Легко увидеть, что матрицы и ортогональны,
также и сумма квадратов значений их столбцов равна единице.
Геометрический смысл SVD
Пусть матрице поставлен в соответствие линейный оператор. Cингулярное разложение можно переформулировать в геометрических терминах. Линейный оператор, отображающий элементы пространства в себя представим в виде последовательно выполняемых линейных операторов вращения, растяжения и вращения. Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отображении линейным оператором множества векторов из векторного пространства в себя или в векторное пространство другой размерности.
Пространства матрицы и SVD
Сингулярное разложение позволяет найти ортогональные базисы различных векторных пространств разлагаемой матрицы
Для прямоугольных матриц существует так называемое экономное представление сингулярного разложения матрицы.
Согласно этому представлению при n» alt= «m>n» />, диагональная матрица имеет пустые строки (их элементы равны нулю), а при пустые столбцы. Поэтому существует еще одно экономное представление
SVD и собственные числа матрицы
Умножая оба выражения справа соответственно на и получаем
SVD и норма матриц
Евклидова норма матрицы есть максимальный коэффициент растяжения произвольного вектора заданной матрицей
Альтернативой Евклидовой норме является норма Фробениуса:
Сингулярные числа матрицы это длины осей эллипсоида, заданного множеством
Нахождение псевдообратной матрицы с помощью SVD
матрица такая матрица, для которой выполняются условия
Пусть найдено разложение матрицы вида
Метод наименьших квадратов и число обусловленности
вектора невязки, Решение
задачи наименьших квадратов
Из формулы Евклидовой нормы матрицы и предыдущей формулы следует, что число обусловленности матрицы есть отношение ее первого сингулярного числа к последнему.
Усеченное SVD при обращении матриц
Определим усеченную псевдообратную матрицу как
Нежное введение в разложение по сингулярным числам для машинного обучения
Дата публикации 2018-02-26
Матричная декомпозиция, также известная как матричная факторизация, включает описание данной матрицы с использованием ее составляющих элементов.
В этом уроке вы обнаружите метод разложения по сингулярным значениям для разложения матрицы на составляющие ее элементы.
После завершения этого урока вы узнаете:
Обзор учебника
Этот урок состоит из 5 частей; они есть:
Разложение по сингулярному значению
Для случая простоты мы сосредоточимся на SVD для вещественных матриц и проигнорируем случай для комплексных чисел.
Разложение по сингулярным значениям является основным моментом линейной алгебры.
Диагональные значения в сигма-матрице называются сингулярными значениями исходной матрицы A. Столбцы матрицы U называются лево-сингулярными векторами A, а столбцы V называются правосингулярными векторами A.
SVD рассчитывается с помощью итерационных численных методов. Мы не будем вдаваться в подробности этих методов. Каждая прямоугольная матрица имеет разложение по сингулярным значениям, хотя результирующие матрицы могут содержать комплексные числа, а ограничения арифметики с плавающей запятой могут привести к тому, что некоторые матрицы не будут аккуратно разлагаться.
Разложение по сингулярным значениям (SVD) предоставляет еще один способ разложить матрицу на сингулярные векторы и сингулярные значения. SVD позволяет нам обнаруживать некоторую информацию того же вида, что и собственное разложение. Тем не менее, SVD является более общим.
SVD широко используется как при вычислении других матричных операций, таких как обратная матрица, так и в качестве метода сокращения данных в машинном обучении. SVD также может быть использован в линейной регрессии наименьших квадратов, сжатии изображений и шумоподавлении данных.
Рассчитать разложение по сингулярному значению
SVD можно рассчитать, вызвав функцию svd ().
Функция принимает матрицу и возвращает элементы U, Sigma и V ^ T. Диагональная матрица Сигмы возвращается как вектор сингулярных значений. Матрица V возвращается в транспонированной форме, например, Электронная лампа
В приведенном ниже примере определяется матрица 3 × 2 и вычисляется разложение по сингулярному значению.
При выполнении примера сначала печатается определенная матрица 3 × 2, затем матрица 3 × 3 U, вектор Sigma с 2 элементами и матричные элементы 2 × 2 V ^ T, вычисленные из разложения.
Восстановить Матрицу из СВД
Исходная матрица может быть восстановлена из элементов U, Sigma и V ^ T.
Элементы U, s и V, возвращаемые из svd (), не могут быть умножены напрямую.
Вектор s должен быть преобразован в диагональную матрицу с помощью функции diag (). По умолчанию эта функция создаст квадратную матрицу размером m x m относительно нашей исходной матрицы. Это вызывает проблему, поскольку размеры матриц не соответствуют правилам умножения матриц, где число столбцов в матрице должно соответствовать количеству строк в последующей матрице.
После создания квадратной диагональной матрицы Сигмы размеры матриц соответствуют исходной матрице m x n, которую мы разлагаем, следующим образом:
Где, на самом деле, мы требуем:
Мы можем достичь этого путем создания новой сигма-матрицы со всеми нулевыми значениями, которая равна m x n (например, больше строк), и заполнить первую n x n часть матрицы квадратной диагональной матрицей, вычисленной с помощью diag ().
При выполнении примера сначала печатается исходная матрица, а затем матрица, восстановленная из элементов SVD.
Вышеупомянутое усложнение с диагональю сигмы существует только в случае, когда m и n не равны. Диагональная матрица может быть использована непосредственно при восстановлении квадратной матрицы следующим образом.
При выполнении примера печатается исходная матрица 3 × 3 и версия, восстановленная непосредственно из элементов SVD.
СВД для псевдообратного
Он также называется инверсией Мура-Пенроуза после двух независимых исследователей метода или Обобщенной инверсией.
Инверсия матриц не определена для матриц, которые не являются квадратными. […] Когда A имеет больше столбцов, чем строк, то решение линейного уравнения с использованием псевдообратного представления дает одно из многих возможных решений.
Псевдообращение вычисляется с использованием сингулярного разложения A:
Или без точечной записи:
Мы можем получить U и V из операции SVD.
D ^ + можно рассчитать путем создания диагональной матрицы из Sigma, вычисления обратной величины каждого ненулевого элемента в Sigma и выполнения транспонирования, если исходная матрица была прямоугольной.
Псевдообращение обеспечивает один из способов решения уравнения линейной регрессии, в частности, когда строк больше, чем столбцов, что часто имеет место.
NumPy предоставляет функцию pinv () для вычисления псевдообращения прямоугольной матрицы.
Пример ниже определяет матрицу 4 × 2 и вычисляет псевдообратную форму.
При выполнении примера сначала печатается определенная матрица, а затем вычисленная псевдообратная.
Мы можем вычислить псевдообращение вручную через SVD и сравнить результаты с функцией pinv ().
Сначала мы должны рассчитать СВД. Далее мы должны вычислить обратную величину каждого значения в массиве s. Затем массив s можно преобразовать в диагональную матрицу с добавленным рядом нулей, чтобы сделать его прямоугольным. Наконец, мы можем вычислить псевдообратное по элементам.
Полный пример приведен ниже.
При выполнении примера сначала печатается определенная прямоугольная матрица, а псевдообратная функция, которая соответствует приведенным выше результатам, получается из функции pinv ().
SVD для уменьшения размерности
Популярное применение SVD для уменьшения размерности.
Данные с большим количеством объектов, таких как больше объектов (столбцов), чем наблюдений (строк), могут быть уменьшены до меньшего подмножества объектов, которые наиболее актуальны для проблемы прогнозирования.
В результате получается матрица с более низким рангом, которая, как говорят, аппроксимирует исходную матрицу.
Приближенный B исходного вектора A может быть восстановлен.
В обработке естественного языка этот подход может использоваться для матриц вхождений слов или частот слов в документах и называется скрытым семантическим анализом или скрытым семантическим индексированием.
На практике мы можем сохранить и работать с описательным подмножеством данных, называемым T. Это плотная сводка матрицы или проекции.
Кроме того, это преобразование может быть вычислено и применено к исходной матрице A, а также к другим аналогичным матрицам.
Пример ниже демонстрирует сокращение данных с SVD.
Сначала определяется матрица 3 × 10 с большим количеством столбцов, чем строк. SVD рассчитывается и выбираются только первые две функции. Элементы рекомбинированы для точного воспроизведения исходной матрицы. Наконец, преобразование рассчитывается двумя разными способами.
При выполнении примера сначала печатается определенная матрица, а затем восстановленное приближение, за которым следуют два эквивалентных преобразования исходной матрицы.
Scikit-learn предоставляет класс TruncatedSVD, который напрямую реализует эту возможность.
Может быть создан класс TruncatedSVD, в котором необходимо указать количество желаемых функций или компонентов, например, например. 2. После создания вы можете подогнать преобразование (например, вычислите V ^ Tk), вызвав функцию fit (), затем примените ее к исходной матрице, вызвав функцию transform (). Результатом является преобразование A, названное T выше.
В приведенном ниже примере демонстрируется класс TruncatedSVD.
При выполнении примера сначала печатается определенная матрица, а затем преобразованная версия матрицы.
Мы видим, что значения соответствуют значениям, вычисленным вручную выше, за исключением знака некоторых значений. Мы можем ожидать некоторую нестабильность, когда дело доходит до знака, учитывая природу выполняемых вычислений и различия в используемых библиотеках и методах. Эта нестабильность знака не должна быть проблемой на практике, пока преобразование обучено для повторного использования.
расширения
В этом разделе перечислены некоторые идеи по расширению учебника, которые вы, возможно, захотите изучить.
Если вы исследуете какое-либо из этих расширений, я хотел бы знать.
Дальнейшее чтение
Этот раздел предоставляет больше ресурсов по теме, если вы хотите углубиться.
книги
статьи
Резюме
В этом уроке вы обнаружили метод разложения по сингулярным значениям для разложения матрицы на составляющие ее элементы.
В частности, вы узнали:
У вас есть вопросы?
Задайте свои вопросы в комментариях ниже, и я сделаю все возможное, чтобы ответить.
Как уменьшить количество измерений и извлечь из этого пользу
Сначала я хотел честно и подробно написать о методах снижения размерности данных — 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 слой. Благодаря ему с некоторой вероятностью нейроны будут находиться в «выключенном» состоянии, что а) будет вносить искажения в обрабатываемый образ; б) будет служить своеобразной регуляризацией при обучении.
Еще одно интересное применение автоэнкодера — определение аномалий в данных по ошибке реконструкции образов. В целом, если подавать на вход автоэнкодера данные не из обучающей выборки, то, понятно, ошибка реконструкции каждого образа из новой выборки будет выше таковой из тренировочной выборки, но более-менее одного порядка. При наличии аномалий эта ошибка будет в десятки, а то и сотни раз больше.
Русские Блоги
Статья, чтобы понять принцип и применение разложения по сингулярным числам (SVD)
1. Введение
2 Собственные значения и собственные векторы
Прежде чем приступить к выводу SVD, давайте сначала разберемся с определением собственного значения и собственного вектора:
A x = λ x Ax=\lambda x A x = λ x
Каковы преимущества нахождения собственных значений и собственных векторов? То есть мы можем разложить матрицу A по собственному усмотрению.
То есть информация матрицы A может быть представлена ее собственными значениями и собственными векторами.
Таким образом, наше выражение для собственного разложения можно записать как 
Подводя итог, можно сказать, что при разложении по собственным значениям можно получить собственные значения и собственные векторы. Собственное значение указывает, насколько важна эта функция, а собственный вектор указывает, что это за функция. Однако разложение по собственным значениям также имеет много ограничений. Например, преобразованная матрица должна бытьфаланга。
3 Разложение SVD
Мы вычислили как U, так и V, и теперь нет матрицы сингулярных значений Σ, которая не была бы вычислена. Поскольку Σ равно 0, за исключением сингулярного значения на диагонали, нам нужно только найти каждое сингулярное значение σ Ладно.
Мы заметили: 
Таким образом мы можем найти каждое из наших сингулярных значений, а затем найти матрицу сингулярных значений Σ.
Кроме того, мы также можем видеть, что наша матрица собственных значений равна квадрату матрицы сингулярных значений, что означает, что собственное значение и сингулярное значение удовлетворяют следующему соотношению: 
Другими словами, нам не нужно σ i = A v i u i \sigma_=\frac
4 Пример расчета СВД
Для сингулярного значения матрицы A мы можем сначала вычислить его по вольфрамальфе: 
Шаги расчета вручную: 
Как показано на приведенном выше рисунке, мы можем видеть, что SVD может делить матрицу на разные матрицы и складывать их, а коэффициент перед делением является значением SVD. Для сингулярных значений он аналогичен собственным значениям в нашем разложении на собственные числа, и он также находится в матрице сингулярных значений. Расположены в порядке убывания, и особые значения уменьшаются очень быстро. Во многих случаях сумма верхних 10% или даже 1% сингулярных значений составляет более 99% всех сингулярных значений.
Другими словами, мы также можем аппроксимировать матрицу с наибольшими k сингулярными значениями и соответствующими левыми и правыми сингулярными векторами.
Благодаря этому важному свойству SVD можно использовать для уменьшения размерности PCA, чтобыСжатие данных и шумоподавление, Может также использоваться в алгоритме рекомендации для разложения матрицы, соответствующей пользователю и предпочтению, а затем получения неявного запроса пользователя на рекомендацию.
5 СВД используется для PCA
Другими словами, наш алгоритм PCA может быть выполнен без декомпозиции признаков, но с SVD.Этот метод эффективен при большом размере выборки.
Фактически,Реальная реализация алгоритма PCA scikit-learn заключается в использовании SVD.Мы думаем, что вместо насильственного разложения признаков.
С другой стороны, обратите внимание, что PCA использует только правую сингулярную матрицу нашего SVD, а не левую сингулярную матрицу, так в чем же польза от левой сингулярной матрицы?
Предположим, что наш образец m × n m×n m × n Матрица X, если найти матрицу через СВД X X T XX^
может получить один d × n d×n d × n X ’, эта матрица такая же, как и наша исходная m × n m×n m × n По сравнению с матрицей выборки измерений X количество строк уменьшено с m до k, что показывает, что количество строк сжато.
Левая сингулярная матрица может использоваться для сжатия строк.
Правую сингулярную матрицу можно использовать для сжатия количества столбцов, то есть размера объекта, который является нашим уменьшением размерности PCA.
6 Резюме
1. SVD-декомпозиция состоит в том, чтобы разложить матрицу на ее левую матрицу собственного подпространства и правую матрицу собственного подпространства, а матрица собственных значений в середине представляет вес, поэтому нам нужно только каждый раз выбирать эти важные характеристики и сохранять их. Восстановить исходную матрицу практически без потерь;
2. SVD-декомпозицию можно рассматривать как своеобразную исходную матрицуВыражение низкого ранга；
3. SVD может использоваться для шумоподавления данных;
4. SVD можно использовать для сжатия размеров элементов;