Простой итерационный алгоритм сингулярного разложения
Материал из MachineLearning.
(Новая: '''Простой итерационный алгоритм сингулярного разложения матриц''' допускает простую высокопараллель...) |
|||
Строка 1: | Строка 1: | ||
'''Простой итерационный алгоритм сингулярного разложения матриц''' допускает простую высокопараллельную (в том числе, нейросетевую) реализацию. [[Сингулярное разложение]] матриц необходимо для решения многих задач анализа данных. В том числе, [[Метод главных компонент|анализ главных компонент]] сводится к сингулярному разложению матрицы центрированных данных. | '''Простой итерационный алгоритм сингулярного разложения матриц''' допускает простую высокопараллельную (в том числе, нейросетевую) реализацию. [[Сингулярное разложение]] матриц необходимо для решения многих задач анализа данных. В том числе, [[Метод главных компонент|анализ главных компонент]] сводится к сингулярному разложению матрицы центрированных данных. | ||
- | + | == Идея сингулярного разложения матрицы данных == | |
Если <tex>\operatorname{X}=\left\{x_1,..., x_m \right\}^T</tex> — матрица, составленная из векторов-строк центрированных данных, то <tex> C = \operatorname{X}^T\operatorname{X}</tex> и задача о спектральном разложении ковариационной матрицы <tex> C </tex> превращается в задачу о ''сингулярном разложении'' (англ. [http://en.wikipedia.org/wiki/Singular_value_decomposition Singular value decomposition]) матрицы данных <tex>\operatorname{X}</tex>. | Если <tex>\operatorname{X}=\left\{x_1,..., x_m \right\}^T</tex> — матрица, составленная из векторов-строк центрированных данных, то <tex> C = \operatorname{X}^T\operatorname{X}</tex> и задача о спектральном разложении ковариационной матрицы <tex> C </tex> превращается в задачу о ''сингулярном разложении'' (англ. [http://en.wikipedia.org/wiki/Singular_value_decomposition Singular value decomposition]) матрицы данных <tex>\operatorname{X}</tex>. | ||
Строка 16: | Строка 16: | ||
Теория сингулярного разложения была создана Дж. Дж. Сильвестром (англ.[http://en.wikipedia.org/wiki/James_Joseph_Sylvester J. J. Sylvester]}}) в 1889 г. и изложена во всех подробных руководствах по теории матриц <ref>''Гантмахер Ф. Р.'', Теория матриц. — М.: Наука, 1966. — 576 стр.</ref>. | Теория сингулярного разложения была создана Дж. Дж. Сильвестром (англ.[http://en.wikipedia.org/wiki/James_Joseph_Sylvester J. J. Sylvester]}}) в 1889 г. и изложена во всех подробных руководствах по теории матриц <ref>''Гантмахер Ф. Р.'', Теория матриц. — М.: Наука, 1966. — 576 стр.</ref>. | ||
- | + | == Простой итерационный алгоритм сингулярного разложения == | |
Основная процедура — поиск наилучшего приближения произвольной <tex>m \times n</tex> матрицы <tex>X=(x_{ij})</tex> матрицей вида <tex>b \otimes a = (b_i a_j)</tex> (где <tex>b</tex> — <tex>m</tex>-мерный вектор, а <tex>a</tex> — <tex>n</tex>-мерный вектор) методом наименьших квадратов: | Основная процедура — поиск наилучшего приближения произвольной <tex>m \times n</tex> матрицы <tex>X=(x_{ij})</tex> матрицей вида <tex>b \otimes a = (b_i a_j)</tex> (где <tex>b</tex> — <tex>m</tex>-мерный вектор, а <tex>a</tex> — <tex>n</tex>-мерный вектор) методом наименьших квадратов: |
Версия 21:36, 2 июля 2008
Простой итерационный алгоритм сингулярного разложения матриц допускает простую высокопараллельную (в том числе, нейросетевую) реализацию. Сингулярное разложение матриц необходимо для решения многих задач анализа данных. В том числе, анализ главных компонент сводится к сингулярному разложению матрицы центрированных данных.
Идея сингулярного разложения матрицы данных
Если — матрица, составленная из векторов-строк центрированных данных, то
и задача о спектральном разложении ковариационной матрицы
превращается в задачу о сингулярном разложении (англ. Singular value decomposition) матрицы данных
.
Число называется сингулярным числом матрицы
тогда и только тогда, когда существуют правый и левый сингулярные векторы: такие
-мерный вектор-строка
и
-мерный вектор-столбец
(оба единичной длины), что выполнено два равенства:
Пусть — ранг матрицы данных. Сингулярное разложение матрицы данных
— это её представление в виде
где — сингулярное число,
— соответствующий правый сингулярный вектор-столбец, а
— соответствующий левый сингулярный вектор-строка (
). Правые сингулярные векторы-столбцы
, участвующие в этом разложении, являются векторами главных компонент и собственными векторами эмпирической ковариационной матрицы
, отвечающими положительным собственным числам
.
Хотя формально задачи сингулярного разложения матрицы данных и спектрального разложения ковариационной матрицы совпадают, алгоритмы вычисления сингулярного разложения напрямую, без вычисления спектра ковариационной матрицы, более эффективны и устойчивы [1].
Теория сингулярного разложения была создана Дж. Дж. Сильвестром (англ.J. J. Sylvester}}) в 1889 г. и изложена во всех подробных руководствах по теории матриц [1].
Простой итерационный алгоритм сингулярного разложения
Основная процедура — поиск наилучшего приближения произвольной матрицы
матрицей вида
(где
—
-мерный вектор, а
—
-мерный вектор) методом наименьших квадратов:
Решение этой задачи дается последовательными итерациями по явным формулам. При фиксированном векторе значения
, доставляющие минимум форме
, однозначно и явно определяются из равенств
:
Аналогично, при фиксированном векторе определяются значения
:
B качестве начального приближения вектора возьмем случайный вектор единичной длины, вычисляем вектор
, далее для этого вектора
вычисляем вектор
и т. д. Каждый шаг уменьшает значение
. В качестве критерия остановки используется малость относительного уменьшения значения минимизируемого функционала
за шаг итерации (
) или малость самого значения
.
В результате для матрицы получили наилучшее приближение матрицей
вида
(здесь верхним индексом обозначен номер итерации). Далее, из матрицы
вычитаем полученную матрицу
, и для полученной матрицы уклонений
вновь ищем наилучшее приближение
этого же вида и т. д., пока, например, норма
не станет достаточно малой. В результате получили итерационную процедуру разложения матрицы
в виде суммы матриц ранга 1, то есть
. Полагаем
и нормируем векторы
:
В результате получена аппроксимация сингулярных чисел
и сингулярных векторов (правых —
и левых —
).
К достоинствам этого алгоритма относится его исключительная простота и возможность почти без изменений перенести его на данные с пробелами[1], а также взвешенные данные.
Существуют различные модификации базового алгоритма, улучшающие точность и устойчивость. Например, векторы главных компонент при разных
должны быть ортогональны «по построению», однако при большом числе итерации (большая размерность, много компонент) малые отклонения от ортогональности накапливаются и может потребоваться специальная коррекция
на каждом шаге, обеспечивающая его ортогональность ранее найденным главным компонентам.
Для квадратных симметричных положительно определённых матриц описанный алгоритм превращается в метод прямых итераций для поиска собственных векторов.
Примечания