Сингулярное разложение матриц (SVD): математика рекомендательных систем и сжатия данных
Универсальный инструмент матричного анализа
В вычислительной линейной алгебре существует множество способов разложения матриц (LU, QR, спектральное разложение), однако Сингулярное Разложение (Singular Value Decomposition, SVD) занимает среди них абсолютно особое место. Если спектральное разложение применимо только к квадратным матрицам, то SVD позволяет разложить абсолютно любую прямоугольную матрицу. Эта математическая процедура стала одним из важнейших открытий XX века, заложив фундамент для современной науки о данных, обработки изображений и систем искусственного интеллекта.
Геометрический смысл сингулярного разложения потрясающе красив. Любое линейное преобразование (которое описывается матрицей) можно разбить на три простых последовательных шага. Первый шаг — это поворот исходного пространства. Второй шаг — масштабирование (растяжение или сжатие) пространства вдоль новых координатных осей. Третий шаг — еще один поворот. Матрица SVD буквально предоставляет нам матрицы этих поворотов (ортогональные матрицы сингулярных векторов) и коэффициенты растяжения (диагональную матрицу сингулярных чисел). Чем больше сингулярное число, тем больше информации или «энергии» несет соответствующее направление.
Сжатие информации и метод главных компонент (PCA)
Главная практическая ценность SVD заключается в возможности усечения. Если мы отсортируем сингулярные числа по убыванию, мы обнаружим, что во многих реальных данных первые несколько чисел огромны, а остальные быстро стремятся к нулю (шум). Если мы отбросим эти малые числа и соответствующие им векторы, мы получим матрицу меньшего ранга, которая почти идеально приближает исходную. Это математически строгий способ отделить полезный сигнал от шума.
Этот принцип лежит в основе Метод Главных Компонент (PCA) — важнейшего алгоритма снижения размерности данных. Например, черно-белое изображение лица размером 1000x1000 пикселей (миллион чисел) с помощью усеченного SVD можно сжать до передачи всего 50 векторов, и глаз человека не заметит разницы в качестве. В знаменитом конкурсе Netflix Prize с призовым фондом в миллион долларов, победу одержала команда, алгоритм которой базировался именно на SVD. Матрица, где строками были пользователи, а столбцами — фильмы, содержала огромное количество пропусков (никто не смотрел все фильмы). SVD позволило выявить скрытые (латентные) факторы вкусов пользователей и жанров фильмов, блестяще предсказывая оценки, которые пользователи поставили бы еще не просмотренным картинам.
