сингулярное разложение

Примеры значения «единственное значение»

Сингулярное значение матрицы — это понятие в математическом смысле, которое обычно получается разложением по сингулярным значениям (Singular Value Decomposition, сокращенно SVD). Если вы хотите спросить, какой физический смысл представляет сингулярное значение, то вы должны рассмотреть значение, соответствующее сингулярному значению в различных практических инженерных приложениях. Попробуем сначала избежать строгого математического вывода обозначений, начнем с картинки интуитивно, посмотрим, что означает единственное число.

Это фото высотой 450*шириной 333 пикселя.

Все мы знаем, что картинка на самом деле соответствует матрице, а размер матрицы это размер пикселя.Например, порядок матрицы, соответствующей этой картинке, равен 450.333 значение каждого элемента матрицы соответствует значению пикселя. Картинка фактически соответствует матрице, а размер матрицы - это количество пикселей, например, порядок матрицы, соответствующей этой картинке, равен 450.333 значение каждого элемента матрицы соответствует значению пикселя.

Теперь выполним сингулярное разложение матрицы. Интуитивно понятно, что разложение по сингулярным числам разлагает матрицу на сумму нескольких матриц первого ранга.

Так как сингулярные значения расположены в порядке убывания, естественно возникает вопрос, если сохранить только большие сингулярные значения и отбросить меньшие, то какая матрица получится, то есть изображение?

так что это сохраняет только первый член, а затем графики:

В результате мы вообще не можем видеть, что это такое... Мы пытаемся добавить еще несколько пунктов: В результате мы вообще не можем видеть, что это такое... Мы пытаемся добавить несколько больше предметов: Сделаем картинку:

Смутно различимо, что это лицо девушки, но всё равно очень расплывчато, ведь мы взяли всего 5 единичных значений. Возьмем на пробу 20 сингулярных значений, то есть взяв первые 20 пунктов в правой части уравнения, мы можем смутно определить, что это лицо девушки, но все равно очень расплывчато.Ведь мы только взяли 5 сингулярных значений. Возьмем 20 сингулярных значений и попробуем:

Мозаичное размытие все еще присутствует, но мы, наконец, можем сказать, что это лицо Юри-тян. Когда мы возьмем первые 50 членов в правой части уравнения: все еще есть некоторое мозаичное размытие, но мы, наконец, можем определить, что это лицо Юри-тян. Когда мы берем первые 50 членов в правой части уравнения:

Получаем изображение, мало чем отличающееся от исходного изображения. То есть, когда мы получаем изображение, мало чем отличающееся от исходного изображения. То есть, когда он продолжает увеличиваться с 1, он постоянно приближается. Вернемся к формуле

Матрица представляет собой матрицу 450*333, в которой необходимо сохранить значение каждого элемента.

450 соответственно1 и 333Вектор единиц с одним элементом на элемент. Если мы хотим хранить много изображений высокой четкости, но ограничены местом для хранения, исходя из предпосылки обеспечения максимальной точности распознавания изображений, мы можем сохранить несколько элементов с большими сингулярными значениями и отбросить меньшие. товар можно использовать. Например, в приведенном выше примере, если мы сохраняем только первые 50 элементов разложения по сингулярным значениям, элементы, которые необходимо сохранить, составляют 26% объема памяти по сравнению с сохранением исходной матрицы.

Сингулярные значения часто соответствуют важной информации, скрытой в матрице, и важность положительно коррелирует с размером сингулярных значений. Каждая матрица может быть представлена ​​как сумма ряда «малых матриц» ранга 1, а сингулярные числа измеряют вес этих «малых матриц» для пар.

В области обработки изображений сингулярные значения можно использовать не только для сжатия данных, но и для шумоподавления изображений. Если изображение содержит шум, у нас есть основания полагать, что эти меньшие сингулярные значения связаны с шумом. Когда мы приравняем эти меньшие сингулярные значения к 0, мы сможем убрать шум с изображения. Ниже приведено изображение 25 * 15.

Но часто мы можем получить только следующее изображение с шумом (по сравнению с изображением без шума некоторые белые сетки на изображении ниже серые):Путем разложения по сингулярным числам находим, что сингулярные значения матрицы от большего к меньшему составляют: 14,15, 4,67, 3,00, 0,21,..., 0,05. За исключением первых 3 сингулярных значений, которые больше, остальные сингулярные значения относительно малы. Приравняв эти малые сингулярные значения к 0, а затем построив новую матрицу только с первыми 3 сингулярными значениями, мы получим

Видно, что шум уменьшился (уменьшился серо-белый узор на белой сетке). Видно, что шум уменьшился (уменьшился серо-белый узор на белой сетке).

Декомпозиция по сингулярным значениям также широко используется в анализе основных компонентов (анализ основных компонентов, называемый PCA) и системах рекомендаций (таких как система рекомендаций фильмов Netflex) и т. д. В этих областях применения сингулярные значения также имеют соответствующее значение.

Рассмотрим вопрос: «Рассмотрим матрицу m*n как линейное отображение из m-мерного пространства в n-мерное пространство. Является ли оно: каждый сингулярный вектор является координатной осью, а сингулярное значение есть коэффициентом соответствующей координаты ?» Я думаю, субъект хочет знать больше. Это геометрический смысл сингулярных значений в математике, а не физический смысл в приложении. Ниже приводится краткое введение в геометрический смысл сингулярных чисел, основной ссылкой является статья на сайте Американской математической ассоциации [1].

Матричная сингулярная декомпозиция (SVD) и ее приложения

1. Базовые знания о сингулярных значениях и собственных значениях:

Разложение по собственным значениям и разложение по сингулярным значениям — это методы, широко используемые в области машинного обучения. Эти два имеют очень тесную связь.Я буду говорить об этом дальше.Цель разложения по собственным значениям и разложения по сингулярным значениям одна и та же, то есть извлечь наиболее важные особенности матрицы. Давайте сначала поговорим о разложении по собственным значениям:

1) собственные значения:

Если вектор v является собственным вектором квадратной матрицы A, он должен быть выражен в следующей форме:

В это время λ называется собственным значением, соответствующим собственному вектору v, а набор собственных векторов матрицы — набором ортогональных векторов. Разложение по собственным значениям заключается в разложении матрицы в следующую форму:Где Q — матрица, составленная из собственных векторов этой матрицы A, Σ — диагональная матрица, а каждый диагональный элемент — собственное значение. Я привел некоторые ссылки здесь, чтобы проиллюстрировать. Прежде всего, должно быть понятно, что матрица на самом деле является линейным преобразованием, потому что вектор, полученный путем умножения матрицы на вектор, фактически эквивалентен линейному преобразованию вектора. Например, следующая матрица:Фактически ему соответствует линейное преобразование следующего вида:

Потому что результат умножения этой матрицы M на вектор (x, y):

Приведенная выше матрица симметрична, поэтому это преобразование является преобразованием растяжения в направлении осей x и y (каждый элемент на диагонали будет растягиваться в одном измерении, а при значении > 1 это преобразование растяжения , длинный, укорачивается при значении

Описываемое им преобразование выглядит следующим образом:

На самом деле это растягивающее преобразование оси на плоскости (как показано синей стрелкой).На рисунке синяя стрелка – это основное направление изменения (может быть более одного направления изменения).Если мы Если вы хотите описать преобразование, то мы можем описать основное направление изменения преобразования. Оглядываясь назад на предыдущую формулу разложения собственных значений, разложенная матрица Σ представляет собой диагональную матрицу, а собственные значения в ней расположены от большего к меньшему.Собственные векторы, соответствующие этим собственным значениям, описывают направление изменения матрицы , (ранжируется от основного к второстепенному)

Когда матрица многомерна, то эта матрица представляет собой линейное преобразование в многомерном пространстве.Это линейное изменение может быть не представлено картинками, но можно предположить, что это преобразование также имеет много направлений преобразования. первые N собственных векторов, полученные в результате разложения по значениям, соответствуют наиболее важным N направлениям изменения этой матрицы. Мы можем аппроксимировать эту матрицу (преобразование), используя первые N направлений изменения. То есть: извлеките наиболее важные черты этой матрицы. Подводя итог, разложение по собственным значениям может получить собственные значения и собственные векторы. Собственные значения указывают, насколько важна функция, а собственные векторы указывают, что это за функция. Каждый собственный вектор можно понимать как линейное подпространство, мы можем сделать много вещей с этими линейными подпространствами. Однако разложение по собственным значениям также имеет много ограничений, например, преобразованная матрица должна быть квадратной матрицей.

2) Особые значения:

Поговорим о разложении по сингулярным числам. Разложение по собственным значениям — очень хороший метод извлечения матричных признаков, но он подходит только для квадратных матриц. В реальном мире большинство матриц, которые мы видим, не являются квадратными матрицами. Например, есть N учеников, у каждого ученика есть M предметов, поэтому сформированная таким образом матрица N*M не может быть квадратной матрицей.Как мы можем описать важные характеристики такой обычной матрицы? Для этого можно использовать разложение по сингулярным значениям.Разложение по сингулярным значениям — это метод декомпозиции, который можно применить к любой матрице:

Если предположить, что A является матрицей размера N * M, то полученное U является квадратной матрицей размера N * N (векторы внутри U ортогональны, а векторы в U называются левосингулярными векторами), а Σ является матрицей размера N * M (кроме что все элементы на диагонали равны 0, а элементы на диагонали называются сингулярными значениями), V' (транспонирование V) представляет собой матрицу N * N, векторы внутри также ортогональны, а внутри V вектор называется правым сингулярным вектором), из картинки для отражения размера нескольких перемножаемых матриц можно получить следующую картинку

Так как же соотносятся сингулярные значения и собственные значения? Во-первых, мы транспонируем матрицу A * A, мы получим квадратную матрицу, мы можем использовать эту квадратную матрицу, чтобы найти собственные значения, чтобы получить:

Полученный здесь v является нашим правым сингулярным вектором выше. Кроме того, мы также можем получить:

Здесь σ — упомянутое выше сингулярное значение, а u — упомянутый выше левый сингулярный вектор. Сингулярное значение σ аналогично собственному значению, и оно также располагается от большего к меньшему в матрице Σ, причем уменьшение σ происходит особенно быстро.Во многих случаях сумма первых 10 % или даже 1 % сингулярные значения составляют все сингулярные значения.Более 99% суммы. То есть мы также можем использовать сингулярные значения с наибольшим г для приблизительного описания матрицы, Здесь мы определяем частичное сингулярное разложение:

r — число, намного меньшее, чем m и n, поэтому умножение матриц выглядит так:Результатом умножения трех матриц справа будет матрица, близкая к A. Здесь, чем ближе r к n, тем ближе результат умножения к A. Сумма площадей этих трех матриц (с точки зрения памяти, чем меньше площадь матрицы, тем меньше емкость памяти) намного меньше, чем исходная матрица A. Если мы хотим сжать пространство для представления исходной матрицы A, мы храним здесь три матрицы: U, Σ, V в порядке.

Во-вторых, вычисление сингулярных значений:

Вычисление сингулярных значений является сложной задачей и представляет собой алгоритм O(N^3). В случае с одной машиной, конечно, нет проблем, Matlab может вычислить все сингулярные значения матрицы 1000*1000 за одну секунду, но при увеличении размера матрицы сложность расчета возрастает на требуется третья степень, просто параллельные вычисления. Когда г-н Ву Цзюнь из Google говорил о SVD в серии «Математическая красота», он упомянул, что Google реализовал алгоритм распараллеливания SVD, заявив, что это вклад в развитие человека, но он не указал конкретную шкалу расчета и не дал он дает слишком много ценной информации.

На самом деле СВД еще можно реализовать параллельно.При решении крупномасштабных матриц обычно используют итерационный метод.Когда масштаб матрицы очень велик (например, сотни миллионов), количество итераций может а также сотни миллионов.Во-вторых, если вы используете структуру Map-Reduce для решения проблемы, каждый раз, когда Map-Reduce завершается, он будет включать операции записи и чтения файлов. Лично я предполагаю, что помимо Map-Reduce в системе облачных вычислений Google должна быть модель вычислений, аналогичная MPI, то есть связь между узлами поддерживается, а данные резидентны в памяти.Эта модель вычислений более эффективна, чем Map-Reduce, когда количество итераций очень большое, это в разы быстрее.

Итерация Ланцоша — это метод решения некоторых собственных значений симметричной квадратной матрицы (как упоминалось ранее, собственное значение симметричной квадратной матрицы, полученное решением А'*А, является правым сингулярным вектором решения А), который преобразует симметричный уравнение в a Затем решается трехдиагональная матрица. Согласно некоторой литературе в Интернете, Google должен использовать этот метод для разложения по сингулярным числам. Посмотрите некоторые из цитируемых статей в Википедии, если вы понимаете эти статьи, вы можете «почти» сделать СВД.

Так как вычисление сингулярных значений очень скучный и чисто математический процесс, а предыдущие результаты исследования (в статье) дали почти блок-схему всей программы. Подробнее о вычислении сингулярных значений будет дано в следующих ссылках Я не буду здесь углубляться, но сосредоточусь на применении сингулярных значений.

3. Анализ сингулярных значений и главных компонентов (PCA):

Здесь мы в основном говорим о том, как использовать СВД для решения проблемы ППШ. Проблема PCA на самом деле заключается в базовом преобразовании, из-за которого преобразованные данные имеют наибольшую дисперсию. Размер дисперсии описывает количество информации о переменной.Когда мы говорим об устойчивости вещи, мы часто говорим, что дисперсия должна быть уменьшена.Если дисперсия модели велика, это означает, что модель нестабильна. . Но для данных, которые мы используем для машинного обучения (в основном данные для обучения), это имеет смысл только в том случае, если дисперсия велика.В противном случае, если все входные данные являются одной и той же точкой, дисперсия будет равна 0, так что несколько входных данных эквивалентны к одним данным. В качестве примера возьмем следующую картинку:

Это предположение состоит в том, что камера собирает изображение движущегося объекта, а точки выше представляют положение движения объекта.Если мы хотим совместить эти точки с прямой линией, какое направление мы выберем? Конечно, это линия, отмеченная сигналом на диаграмме. Если мы просто спроецируем эти точки на ось х или ось у, дисперсия, полученная по осям х и оси у, будет одинаковой (поскольку тенденция этих точек находится в направлении около 45 градусов, поэтому спроецируйте на ось x или ось y аналогична), если мы используем исходную систему координат xy для просмотра этих точек, легко не увидеть, каково реальное направление этих точек. Но если мы изменим систему координат, горизонтальная ось станет направлением сигнала, а вертикальная ось станет направлением шума, то легко найти, какое направление имеет большую дисперсию, а какое — маленькую.

Вообще говоря, направление большой дисперсии — это направление сигнала, а направление малой дисперсии — это направление шума. сигнал-шум. Для приведенного выше рисунка, если мы будем хранить данные только в направлении сигнала, мы также можем сделать хорошее приближение к исходным данным.

Проще говоря, вся работа PCA заключается в том, чтобы последовательно найти набор взаимно ортогональных координатных осей в исходном пространстве.Первая ось максимизирует дисперсию, а вторая ось ортогональна первой оси.В плоскости дисперсия является наибольшей, а третья ось имеет наибольшую дисперсию в плоскости, ортогональной первой и второй осям, поэтому, предполагая, что в N-мерном пространстве мы можем найти N таких координатных осей, мы берем первое r для аппроксимации этого пространства , таким образом сжимаясь из N-мерного пространства в r-мерное пространство, но выбранные нами координатные оси r могут сжимать пространство и минимизировать потерю данных.

Или предположим, что каждая строка нашей матрицы представляет собой выборку, а каждый столбец представляет собой признак, который выражается на языке матрицы, а координатная ось m * n-матрицы A изменена, а P — преобразованная матрица из пространство N. Преобразование в другое N-мерное пространство, и некоторые изменения, подобные вращению и растяжению, будут выполнены в пространстве.

И преобразуйте матрицу A m * n в матрицу m * r, что сделает исходные n признаков r признаками (r

Но как это относится к СВД? Как упоминалось ранее, сингулярные векторы, полученные с помощью SVD, также располагаются в порядке убывания сингулярных значений.С точки зрения PCA ось координат с наибольшей дисперсией является первым сингулярным вектором, а ось координат со второй по величине дисперсией - второй сингулярный вектор.Сингулярный вектор... Вспомним полученную ранее формулу SVD:Одновременно умножьте обе части матрицы на матрицу V. Поскольку V является ортогональной матрицей, V транспонируется и умножается на V, чтобы получить единичную матрицу I, поэтому ее можно преобразовать в следующую формулуСравните следующую формулу с формулой преобразования матрицы m * n A * P в матрицу m * r. Здесь V на самом деле представляет собой P, который является изменяющимся вектором. Вот сжать матрицу m*n в матрицу m*r, то есть сжать столбцы, если мы хотим сжать строки (с точки зрения PCA сжатие строк можно понимать как сжатие некоторых подобных сэмплы объединяются или удаляются сэмплы с небольшой ценностью) что делать? Также мы пишем общий пример сжатия строк:Таким образом, матрица из m строк сжимается в матрицу из r строк. То же самое верно и для SVD. Мы умножаем обе части формулы разложения SVD на транспонирование U' из U.

Это дает нам формулу сжатия строк. Видно, что PCA можно сказать почти обертка для SVD.Если мы реализуем SVD, то и PCA реализуется, а еще лучше, с SVD, мы можем получить PCA в двух направлениях., если мы разложим собственные значения АА, мы можем получить PCA только в одном направлении.

В-четвертых, единственное значение и латентный семантический индекс LSI:

Скрытое семантическое индексирование - это не то же самое, что PCA, по крайней мере, его можно использовать напрямую, если SVD не реализован, но LSI также является алгоритмом, который в значительной степени зависит от SVD. Ранее г-н Ву Цзюнь занимался проблемой классификации при вычислении матриц и обработка текста.

«Три матрицы имеют очень четкое физическое значение. Каждая строка в первой матрице X представляет класс слов, связанных по смыслу, и каждый ненулевой элемент в ней представляет важность (или связанность) каждого слова в этом классе слов. релевантность слов), чем больше значение, тем релевантнее. Каждый столбец в последней матрице Y представляет класс статей по одной и той же теме, а каждый элемент представляет релевантность каждой статьи в этом типе статей. Средняя матрица представляет класс слово и артикль класс Следовательно, нам нужно только выполнить разложение по сингулярным значениям на корреляционной матрице А, и мы можем одновременно завершить классификацию синонимов и артиклей (при этом мы можем получить корреляцию каждого типа артикля и каждого типа слова)».

Приведенный выше абзац может показаться непростым для понимания, но в этом суть LSI. Ниже я приведу пример для иллюстрации. Следующий пример взят из руководства по LSA. Конкретный URL будет указан в последней цитате:Это матрица, но разница в том, что здесь строка указывает, в каких заголовках встречается слово (строка — это одномерный признак, упомянутый ранее), а столбец указывает, какие слова есть в заголовке (эта матрица на самом деле наша Упомянутая ранее линия является транспонированной в виде образца, который изменит значение наших левого и правого сингулярных векторов, но не повлияет на наш процесс вычисления). Например, в названии T1 есть четыре слова guide, investing, market и stock, каждое из которых встречается по одному разу.Выполняем SVD на этой матрице, чтобы получить следующую матрицу:

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

Продолжая смотреть на эту матрицу, можно обнаружить некоторые интересные вещи.Во-первых, первый столбец левого сингулярного вектора указывает частоту встречаемости каждого слова.Хотя он не линейный, но его можно рассматривать как общее описание.Например , книга составляет 0,15, что соответствует документу 2 раза в документе, инвестирование составляет 0,74, что соответствует 9 раз в документе, богатство составляет 0,36, что соответствует 3 раза в документе;

Во-вторых, первая строка единицы в правом единственном векторе представляет приблизительное количество слов, которые появляются в каждом документе, например, T6 равно 0,49, и появляется 5 слов, а T2 равно 0,22, и появляется 2 слова.

Затем оглядываемся назад, мы можем взять левый сингулярный вектор и правый сингулярный вектор в последних 2-х измерениях (ранее это была 3-х мерная матрица), и спроецировать его на плоскость, мы можем получить:На графике каждая красная точка представляет слово, а каждая синяя точка представляет собой документ, так что мы можем сгруппировать эти слова и документы. Например, акции и рынок можно поместить в одну категорию, потому что они всегда появляются вместе, на самом деле и недвижимость можно поместить в одну категорию, папы, руководство немного обособлено, поэтому объединять их не будем. В соответствии с эффектом кластеризации синонимы в коллекции документов могут быть извлечены, так что, когда пользователь извлекает документ, для поиска используется семантический уровень (коллекция синонимов), а не уровень предыдущего слова. Это уменьшает наш объем поиска и хранения, потому что коллекция сжатых документов похожа на PCA, а во-вторых, это может улучшить наш пользовательский опыт.Когда пользователь вводит слово, мы можем найти его в коллекции синонимов этого слова, которая Традиционные индексы не могут этого сделать.

использованная литература:

[1] Мы рекомендуем разложение по единичным значениям (столбец характеристик из AMS) [2] Сюй Шуфан, Теория и метод матричных вычислений, издательство Пекинского университета.