Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы машинного обученияВ 28-й статье поговорим об алгоритме SVD.
Полное английское название SVD — Singular Value Decomposition, что переводится каксингулярное разложение. На самом деле это алгоритм линейной алгебры, используемый для разделения матрицы. После разделения можно извлечь ключевую информацию, тем самым уменьшив масштаб исходных данных. Поэтому он широко используется в различных областях, таких как обработка сигналов, финансы и статистика. Этот алгоритм также используется во многих областях машинного обучения, таких какрекомендательная система, поисковая системасжатие данных и т. д.
Введение в СВД
Мы предполагаем, что исходная матрица набора данных D представляет собой матрицу mxn, тогда с помощью алгоритма SVD мы можем разложить ее на три части:
Среди этих трех матриц U представляет собой матрицу размера m x n,
представляет собой диагональную матрицу размера m x n, за исключением того, что все диагональные элементы равны 0,Диагональные элементы являются сингулярными значениями матрицы. V — матрица размера n x n. И U, и VУнитарная матрица, то есть удовлетворить
. То есть умножение его на его транспонирование равно единичной диагональной матрице.
Мы можем посмотреть на рисунок ниже, чтобы интуитивно понять эти три матрицы.
Кратко выведем процесс решения СВД, он выглядит очень сложным и имеет много концепций, но решить его несложно. потребуетсяИспользуйте разложение матрицы по собственному значениюЕсли вы не знакомы с соответствующими понятиями, вы можете сначала просмотреть соответствующее содержание темы линейной алгебры, чтобы сделать обзор:
Основы линейной алгебры — собственные значения и собственные векторы матриц
Во-первых, если мы вычислим
Можно получить квадратную матрицу размера n x n. Для квадратной матрицы мы можем разложить ее по собственным числам, предполагая, что собственные значения равны
, собственные векторы
, подставив в свойства собственных значений можно получить:
Всего будет n таких собственных значений и собственных векторов, мыобъединить все свои собственные векторы, вы можете получить n x n матрицу V. Это также V после нашего результата разложения SVD, поэтому в некоторых книгах его называют правым сингулярным вектором.
Аналогично вычисляем
Мы можем получить квадратную матрицу m x m, мыЕго также можно разложить на собственные значения, получите матрицу признаков U. U должна быть матрицей размера m x m, которая равна U в формуле SVD, и мы можем назвать ее левым сингулярным вектором матрицы A.
U и V есть, нам осталось только
Еще не просил. Поскольку это диагональная матрица, все элементы, кроме диагональных, равны 0, поэтому мыПросто запросите каждый диагональный элемент в нем, то есть сингулярное значение прекрасно, мы предполагаем, что сингулярное значение равно
, деформируем формулу СВД:
В этом выводе используется то свойство, что V является унитарной матрицей, поэтому мы умножаем ее на V, чтобы исключить ее, и выводим формулу для сингулярных значений:
Матрицу найти не сложно.
Весь процесс вывода не сложен, но есть одна проблема, которая не решена,Почему
Матрица признаков - матрица U в СВД.Какой принцип?? Как появился этот шаг? Честно говоря, я не знаю, как гениальные математики вывели этот шаг, я действительно не могу понять, каким образом они думали, чтобы получить этот результат, но доказать его правильность несложно.
Здесь также используются свойства унитарных матриц и свойства диагонального умножения матриц. Мы видим, что U действительно
Матрица, составленная из собственных векторов, также может доказать V. На самом деле, если у вас острый глаз, вы можете найтиМатрица собственных значений равна квадрату матрицы сингулярных значений,так
Итак, решаем
Матрица может быть вычислена без проблем с передачей матрицы, но может быть вычислена с помощью
Собственные значения находятся путем извлечения квадратного корня.
Назначение СВД
Мы вывели так много формул, так какой же смысл в этом алгоритме SVD?
Кажется, что толку от него нет, потому что мы превратили одну матрицу в три, и масштаб этих трех матриц не уменьшился, а увеличился. Но если вы изучите разложенные сингулярные значения, вы обнаружите, что сингулярные значения очень быстро уменьшаются.Пока 10% или даже 1% сингулярных значений составляют более 99% суммы всех сингулярных значенийпропорция.
Другими словами, мыПолный результат разложения SVD не требуется, но нужно только отфильтровать несколько k сингулярных значений, и соответствующие левые и правые сингулярные векторы могут приблизительно описать исходную матрицу.
Давайте посмотрим на рисунок ниже, что эквивалентно фильтрации небольшой части разложенной матрицы для замены целого и сохранению информации, приближенной к целому.
Выписываем формулу:
Здесь k намного меньше n, поэтому мы можем значительно уменьшить количество параметров матрицы, получаемых после SVD-разложения.
То есть мы разлагаем большую матрицу размера m x n на три матрицы гораздо меньшего размера с помощью SVD-разложения. И через эти три маленькие матрицы мы можем восстановить большую часть информации исходной матрицы. Я не знаю, есть ли у вас идеи? да, этоОн точно такой же, как алгоритм PCA, который мы представили ранее.. Не только идеи похожи, но даже процесс расчета имеет очень высокую степень совпадения.На самом деле, один из методов решения алгоритма PCA заключается в разложении матрицы SVD.
СВД и ППШ
Давайте кратко рассмотрим связь между SVD и PCA.
Сначала рассмотрим алгоритм PCA, мы сначалаВычислите ковариационную матрицу X исходных данных, снова
Выполните матричную факторизацию, чтобы найти самые большие собственные значения K. Затем используйте матрицу, состоящую из собственных векторов, соответствующих собственным значениям K, для выполнения матричного преобразования исходных данных.
В ходе этого процесса мынужно рассчитать
, когда масштаб X очень велик, вычислительные затраты также очень велики. Обратите внимание, что когда мы вычисляем матрицу V в SVD, мы также используем
Разложение матрицы по собственным значениям. Но ключНекоторые алгоритмы вычисления SVD могут обойтись без предварительного нахождения ковариационной матрицы
V также можно получить, минуя этот дорогостоящий шаг.
Таким образом, текущий популярный PCA почти полностью реализован с использованием SVD в качестве базового механизма, например, инструмент PCA в библиотеке sklearn использует SVD.
Код
Что касается алгоритма SVD, нам не нужно реализовывать его самим, потому что в numpyИнкапсулирует готовые методы декомпозиции SVD.
Мы можем напрямую вызвать интерфейс np.linalg.svd для завершения декомпозиции матрицы:
Здесь Sigma возвращает вектор, а не диагональную матрицу, что экономит ресурсы хранения. Мы можем найти наименьшее K так, чтобы сингулярные значения K занимали более 95% от общего числа сингулярных значений. Здесь видно, что мы выбрали 5 сингулярных значений, которые занимают более 99% суммы всех сингулярных значений:
Суммировать
Сегодня мы поделились с вами принципом алгоритма SVD, а также обычным методом расчета. СВД, как и ППШ, основана на линейной работе матрицы.Благодаря свойствам СВД мы можемСжимайте и преобразовывайте необработанные данные. На основе этого выведено множество алгоритмов и сценариев применения, наиболее классическими из которых являютсяСовместная фильтрация в рекомендательных системах. Из-за нехватки места мы поделимся этим с вами в следующей статье, чтобы на самом деле понять применение SVD и углубить наше понимание.
Поскольку SVD может выполнять параллельные вычисления, на практике он более популярен. Но СВД не панацея.Один из ее больших минусов это то что она такая же как и ППШ.плохо объяснено, у нас нет возможности узнать какие-то ценности или причины каких-то явлений. Об этом мы также поговорим в следующей статье.
Сегодняшняя статья здесь, если вам понравилась эта статья, пожалуйста, приходите на волнукачество три, поддержите меня (Подписывайтесь, делайте репосты, лайкайте).
В этой статье используетсяmdniceнабор текста