Поймите интуицию алгоритма Singular Value Decomposition (SVD).

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

Прочитав эту статью, вы почувствуете, почему и какиспользовать SVD в различных приложениях.

Я мог бы кинуть определение СВД типа:

В линейной алгебре разложение по сингулярным числам (SVD) представляет собой факторизацию вещественной или комплексной матрицы. Он обобщает собственное разложение квадратной нормальной матрицы с ортонормированным собственным базисом на любую матрицу размером m x n. [1]

Хм. Что это такое? Это определение не будет иметь никакого смысла для новичка или человека, который не силен в математике. Многие люди переходят от программного обеспечения к машинному обучению и изо всех сил пытаются понять некоторые передовые математические концепции, используемые в машинном обучении. По крайней мере, я сделал.

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

Известные варианты использования SVD:

  • Псевдоинверсия - инверсия для матриц любого размера (обратная Мура-Пенроуза)
  • Уменьшение размерности (изображения, табличные данные и т.д.)
  • Механизмы рекомендаций (алгоритм FunkSVD и его производные)

Интуиция за СВД

Давайте сведем проблему к людям и их любимой еде. Предположим, у нас есть матрица A m x n, где m представляет количество людей, а n — количество возможных типов продуктов питания. Значения матрицы представляют, насколько человеку нравится тот или иной тип пищи, закодированный в виде рейтинга от 1 до 10.

Вот пример матрицы 3x4 с тремя людьми и четырьмя типами еды:

SVD разлагает любую матрицу m x n A на три матрицы: U, S,и V, где A = USVᵀ.

Как мы можем объяснить эту формулу на нашем примере с людьми и их любимыми видами еды?

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

Мы хотим выяснить, почему «человек 1» любит есть яблоки больше, чем сосиски.

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

Вот как выглядит разложенная матрица A = USVᵀ:

Алгоритм SVD создал набор признаков, описывающих взаимодействие между людьми и их любимыми видами еды.

В нашем случае алгоритм изучил функции «Здоровье», «Мясо» и «Приготовление». Они называются скрытыми функциями.

Примечание. Мы случайным образом обозначили скрытые функции Health, Meat и Cooked. Это абстрактные представления, мы назвали их, чтобы быстро понять концепцию, но у них может быть любое другое обозначение.

Матрица U представляет собой матрицу m x k, где k – это количество скрытых функций. Он показывает, как человек взаимодействует или «чувствует» скрытые функции , и математически описывает, нравится ли ему здоровая, мясная или приготовленная пища. Вообще говоря, он представляет собой отношение между строками матрицы А и скрытыми факторами.

Матрица S представляет собой диагональную матрицу k x k, которая информирует нас о важности каждой функции. В частности, он кодирует, какие функции «Здоровье», «Мясо» или «Приготовление» более важны. Более значительное значение означает, что конкретная скрытая функция несет больше информации и может лучше предсказать, какой тип пищи нравится человеку. Диагональные значения S упорядочены в порядке убывания, что означает, что всегда первый скрытый признак несет больше информации, чем другие признаки.

Матрица Vᵀ — это матрица k x n, котораяописывает, как скрытые функции взаимодействуют с типом пищи. Вообще говоря, он представляет собой отношение между скрытыми факторами и столбцами матрицы А.

Давайте больше заниматься математикой

Но мы по-прежнему будем сохранять концепции простыми и привязанными к нашему примеру.

Сжатие

Часто для сжатия используется СВД. Допустим, у нас есть 1 миллиард x 1 миллион матриц, что в некоторых случаях слишком велико для работы. Следовательно, с помощью SVD мы можем сжать эту матрицу и при этом вычислить ее приближение.

В нашем примере мы можем сжать матрицу А, сохранив только самое существенное скрытое свойство — «здоровую пищу». Теперь матрицы U, S и V выглядят так:

Умножая USVᵀ, мы все равно получим матрицу 3x4, аппроксимирующую исходную матрицу A, но только с использованием части наших исходных данных.

Поскольку мы продолжаем добавлять скрытые функции, аппроксимация будет более точной, но сжатие будет иметь меньший эффект.

Проекция

Матрицы U и Vᵀ ортогональны, поэтому мы можем использовать их в качестве новой системы отсчета в нашем вновь сгенерированном скрытом пространстве. Следовательно, с любой из этих двух матриц мы можем спроецировать матрицу A в пространство скрытых признаков. Умножая A на V, мы получаем A_projected = AV.

В нашем конкретном примере A_projected – этоматрица взаимодействий между людьми и вероятность того, что им понравится здоровая, мясная или приготовленная пища. . Таким образом, мы спроецировали матрицу А из видов продуктов питания в скрытое пространство. Сейчас каждый человек описывается скрытыми чертами.

Сжатие + проекция

Мы можем быстро реализовать алгоритм уменьшения размерности, комбинируя вышеупомянутые методы.

Давайте воспользуемся матрицей V, которая содержит только «Здоровые» скрытые признаки, и умножим ее на A.

A_projected будет матрицей 3x1, содержащей большую часть исходной информации, потому что скрытая функция «Здоровье» описывает большую часть дисперсии. Поэтому мы уменьшили матрицу с 4-х измерений до только одного измерения.

Как рассчитать СВД

Мы можем эффективно вычислить матрицы SVD с помощью Python и Scipy:

import numpy as np
import scipy
A = np.array(
    [[1, 5, 10, 9], [8, 9, 3, 4], [10, 8, 9, 19]], 
    dtype=int
)
U, s, V_T = scipy.linalg.svd(A)

Вы можете прочитать больше о том, как вычислить SVD, в [2] и [3].

Заключение

В статье мы рассмотрели значение матриц U, S и V, используя конкретные примеры между людьми и их любимыми видами пищи. Кроме того, мы представили некоторые варианты использования алгоритма, такие как сжатие и уменьшение размерности, на том же примере. В конце мы показали, как легко вычислять SVD с помощью Python и почему важно понимать интуицию, лежащую в основе алгоритма, а не столько сами вычисления.

Теперь вы быстро понимаете, почему SVD такая мощная, и глубже погружаетесь в ее математику.

🎉 Спасибо, что прочитали мою статью!

📢 Если вам понравилась эта статья и вы хотите поделиться своим опытом обучения искусственному интеллекту, машинному обучению и MLOps, вы также можете связаться со мной в LinkedIn:

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

[1] Сингулярное разложение, Википедия.

[2] Джейсон Браунли, доктор философии, Как рассчитать SVD с нуля с помощью Python, Мастерство машинного обучения, 2018.

[3] Учебное пособие по разложению по сингулярным значениям (SVD), Массачусетский технологический институт.