Аппроксимации матриц низкого ранга - Low-rank matrix approximations

Аппроксимации матриц низкого ранга являются важными инструментами в применении методы ядра для крупномасштабного обучения проблемы.^[1]

Методы ядра (например, опорные векторные машины или же Гауссовские процессы^[2]) проецировать точки данных в многомерные или бесконечномерные пространство функций и найти оптимальную гиперплоскость расщепления. в ядерный метод данные представлены в виде матрица ядра (или же, Матрица Грама ). Многие алгоритмы могут решить машинное обучение проблемы с использованием матрица ядра. Основная проблема ядерный метод это высокий вычислительная стоимость связана с матрицы ядра. Стоимость как минимум квадратична по количеству точек данных обучения, но большинство методы ядра включать вычисление инверсия матриц или же разложение на собственные значения и стоимость становится кубической по количеству обучающих данных. Большие тренировочные наборы вызывают большие затраты на хранение и вычисления. Несмотря на методы разложения низкого ранга (Разложение Холецкого ) уменьшают эту стоимость, они по-прежнему требуют вычисления матрица ядра. Один из подходов к решению этой проблемы - матричные аппроксимации низкого ранга. Самые популярные из них: Метод Нистрома и случайные особенности. Оба они были успешно применены для эффективного обучения ядра.

Приближение Нистрома

Методы ядра становится неосуществимым, когда количество очков ${\displaystyle n}$ настолько велик, что матрица ядра ${\displaystyle {\hat {K}}}$ не могут быть сохранены в памяти.

Если ${\displaystyle n}$ количество обучающих примеров, стоимость хранения и вычислений требуется найти решение проблемы с помощью общих ядерный метод является ${\displaystyle O(n^{2})}$ и ${\displaystyle O(n^{3})}$ соответственно. Приближение Нистрома может позволить значительно ускорить вычисления.^[2][3] Это ускорение достигается за счет использования вместо матрица ядра его приближение ${\displaystyle {\tilde {K}}}$ из классифицировать ${\displaystyle q}$. Преимущество метода заключается в том, что нет необходимости вычислять или сохранять все матрица ядра, но только его размерный блок ${\displaystyle q\times n}$.

Это снижает требования к хранению и сложности до ${\displaystyle O(nq)}$ и ${\displaystyle O(nq^{2})}$ соответственно.

Теорема для ядерной аппроксимации

${\displaystyle {\hat {K}}}$ это матрица ядра для некоторых ядерный метод. Рассмотрим первый ${\displaystyle q<n}$ очков в тренировочной выборке. Тогда существует матрица ${\displaystyle {\tilde {K}}}$ из классифицировать ${\displaystyle q}$:

${\displaystyle {\tilde {K}}={\hat {K}}_{n,q}{\hat {K}}_{q}^{-1}{\hat {K}}_{n,q}^{\text{T}}}$ , куда

${\displaystyle ({\hat {K}}_{q})_{i,j}=K(x_{i},x_{j}),i,j=1,\dots ,q}$ ,

${\displaystyle {\hat {K}}_{q}}$ обратимая матрица

и

${\displaystyle ({\hat {K}}_{n,q})_{i,j}=K(x_{i},x_{j}),i=1,\dots ,n{\text{ and }}j=1,\dots ,q.}$

Доказательство

Приложение для разложения по сингулярным числам

Применение сингулярное разложение (СВД) в матрицу ${\displaystyle A}$ с размерами ${\displaystyle p\times m}$ производит особая система состоящий из сингулярные значения ${\displaystyle \{\sigma _{j}\}_{j=1}^{k},{\text{ }}(\sigma _{j}>0{\text{ }}\forall j=1,\dots ,k),}$ векторов ${\displaystyle \{v_{j}\}_{j=1}^{m}\in \mathbb {C} ^{m}}$ и ${\displaystyle \{u_{j}\}_{j=1}^{p}\in \mathbb {C} ^{p}}$ такие, что они образуют ортонормированные базы ${\displaystyle \mathbb {C} ^{m}}$ и ${\displaystyle \mathbb {C} ^{p}}$ соответственно:

${\displaystyle {\begin{cases}A^{\text{T}}Av_{j}=\sigma _{j}v_{j},{\text{ }}j=1,\dots ,k,\\A^{\text{T}}Av_{j}=0,{\text{ }}j=k+1,\dots ,m,\\AA^{\text{T}}u_{j}=\sigma _{j}u_{j},{\text{ }}j=1,\dots ,k,\\AA^{\text{T}}u_{j}=0,{\text{ }}j=k+1,\dots ,p.\end{cases}}}$

Если ${\displaystyle U}$ и ${\displaystyle V}$ матрицы с ${\displaystyle u}$'песок ${\displaystyle v}$В столбцах и ${\displaystyle \Sigma }$ это диагональ ${\displaystyle p\times m}$ матрица, имеющая сингулярные значения ${\displaystyle \sigma _{i}}$ во-первых ${\displaystyle k}$-записи по диагонали (все остальные элементы матрицы нулевые):

${\displaystyle {\begin{cases}Av_{j}={\sqrt {\sigma _{j}}}u_{j},{\text{ }}j=1,\dots ,k,\\Av_{j}=0,{\text{ }}j=k+1,\dots ,m,\\A^{\text{T}}u_{j}={\sqrt {\sigma _{j}}}v_{j},{\text{ }}j=1,\dots ,k,\\A^{\text{T}}u_{j}=0,{\text{ }}j=k+1,\dots ,p,\end{cases}}}$

тогда матрица ${\displaystyle A}$ можно переписать как:^[4]

${\displaystyle A=U\Sigma ^{1/2}V^{\text{T}}}$.

Дальнейшее доказательство

• ${\displaystyle {\hat {X}}}$ является ${\displaystyle n\times D}$ матрица данных
• ${\displaystyle {\hat {K}}={\hat {X}}{\hat {X}}^{\text{T}}}$
• ${\displaystyle {\hat {C}}={\hat {X}}^{\text{T}}{\hat {X}}}$

Применение сингулярного разложения к этим матрицам:

${\displaystyle {\hat {X}}={\hat {U}}{\hat {\Sigma }}^{1/2}{\hat {V}}^{\text{T}},{\text{ }}{\hat {K}}={\hat {U}}{\hat {\Sigma }}{\hat {U}}^{T},{\text{ }}{\hat {C}}={\hat {V}}{\hat {\Sigma }}{\hat {V}}^{\text{T}}.}$

• ${\displaystyle {\hat {X}}_{q}}$ это ${\displaystyle q\times D}$-мерная матрица, состоящая из первых ${\displaystyle q}$ строки матрицы ${\displaystyle {\hat {X}}}$
• ${\displaystyle {\hat {K}}_{q}={\hat {X}}_{q}{\hat {X}}_{q}^{\text{T}}}$
• ${\displaystyle {\hat {C}}={\hat {X}}^{\text{T}}{\hat {X}}}$

Применение сингулярного разложения к этим матрицам:

${\displaystyle {\hat {X}}_{q}={\hat {U}}_{q}{\hat {\Sigma }}_{q}^{1/2}{\hat {V}}_{q}^{\text{T}},{\text{ }}{\hat {K}}_{q}={\hat {U}}_{q}{\hat {\Sigma }}_{q}{\hat {U}}_{q}^{T},{\text{ }}{\hat {C}}_{q}={\hat {V}}_{q}{\hat {\Sigma }}_{q}{\hat {V}}_{q}^{\text{T}}.}$

С ${\displaystyle {\hat {U}},{\text{ }}{\hat {V}},{\hat {U}}_{q}{\text{ and }}{\hat {V}}_{q}}$ находятся ортогональные матрицы,

${\displaystyle {\hat {U}}={\hat {X}}{\hat {V}}{\hat {\Sigma }}^{-1/2},{\text{ }}{\hat {V}}_{q}={\hat {X}}_{q}^{\text{T}}{\hat {U}}_{q}{\hat {\Sigma }}_{q}^{-1/2}.}$

Замена ${\displaystyle {\hat {V}},{\text{ }}{\hat {\Sigma }}{\text{ by }}{\hat {V}}_{q}{\text{ and }}{\hat {\Sigma }}_{q}}$, приближение для ${\displaystyle {\hat {U}}}$ может быть получен:

${\displaystyle {\tilde {U}}={\hat {X}}{\hat {X}}_{q}^{\text{T}}{\hat {U}}_{q}{\hat {\Sigma }}_{q}^{-1}}$ ( ${\displaystyle {\tilde {U}}}$ не обязательно ортогональная матрица ).

Однако, определяя ${\displaystyle {\tilde {K}}={\tilde {U}}{\hat {\Sigma }}_{q}{\tilde {U}}^{\text{T}}}$, его можно вычислить следующим образом:

${\displaystyle {\begin{aligned}{\tilde {K}}={\tilde {U}}{\hat {\Sigma }}_{q}{\tilde {U}}^{\text{T}}={\hat {X}}{\hat {X}}_{q}^{\text{T}}{\hat {U}}_{q}{\hat {\Sigma }}_{q}^{-1}{\hat {\Sigma }}_{q}({\hat {X}}{\hat {X}}_{q}^{\text{T}}{\hat {U}}_{q}{\hat {\Sigma }}_{q}^{-1})^{\text{T}}\\={\hat {X}}{\hat {X}}_{q}^{\text{T}}{\big \{}{\hat {U}}_{q}({\hat {\Sigma }}_{q}^{-1})^{\text{T}}{\hat {U}}_{q}^{\text{T}}{\big \}}({\hat {X}}{\hat {X}}_{q}^{\text{T}})^{\text{T}}\\\end{aligned}}}$

По характеристике ортогональная матрица ${\displaystyle {\hat {U}}_{q}}$ : равенство ${\displaystyle ({\hat {U}}_{q})^{\text{T}}=({\hat {U}}_{q})^{-1}}$ держит. Затем, используя формулу, обратную матричное умножение ${\displaystyle (AB)^{-1}=B^{-1}A^{-1}}$ за обратимые матрицы ${\displaystyle A}$ и ${\displaystyle B}$, выражение в фигурных скобках можно переписать как:

${\displaystyle {\begin{aligned}{\hat {U}}_{q}({\hat {\Sigma }}_{q}^{-1})^{\text{T}}{\hat {U}}_{q}^{\text{T}}=({\hat {U}}_{q}{\hat {\Sigma }}_{q}^{\text{T}}{\hat {U}}_{q}^{\text{T}})^{-1}=({\hat {K}}_{q})^{-1}\end{aligned}}}$ .

Тогда выражение для ${\displaystyle {\tilde {K}}}$:

${\displaystyle {\begin{aligned}{\tilde {K}}=({\hat {X}}{\hat {X}}_{q}^{\text{T}}){\hat {K}}_{q}^{-1}({\hat {X}}{\hat {X}}_{q}^{\text{T}})^{\text{T}}\\\end{aligned}}}$.

Определение ${\displaystyle {\hat {K}}_{n,q}={\hat {X}}{\hat {X}}_{q}^{\text{T}}}$, доказательство окончено.

Общая теорема для аппроксимации ядра для карты признаков

Для карты характеристик ${\displaystyle \Phi :{\mathcal {X}}\rightarrow {\mathcal {F}}}$ с ассоциированным ядро ${\displaystyle K(x,x')=\langle \Phi (x),\Phi (x')\rangle _{\mathcal {F}}}$: равенство ${\displaystyle {\hat {K}}={\hat {K}}_{n,q}{\hat {K}}_{q}^{-1}{\hat {K}}_{n,q}^{\text{T}}}$ также следует заменой ${\displaystyle {\hat {X}}}$ оператором ${\displaystyle {\hat {\Phi }}:{\mathcal {F}}\rightarrow \mathbb {R} ^{n}}$ такой, что ${\displaystyle \langle {\hat {\Phi }}w\rangle _{i}=\langle \Phi (x_{i}),w\rangle _{\mathcal {F}}}$, ${\displaystyle {\text{ }}i=1,\dots ,n}$, ${\displaystyle w\in {\mathcal {F}}}$, и ${\displaystyle {\hat {X}}_{q}}$ оператором ${\displaystyle {\hat {\Phi }}_{q}:{\mathcal {F}}\rightarrow \mathbb {R} ^{q}}$ такой, что ${\displaystyle \langle {\hat {\Phi }}w\rangle _{i}=\langle \Phi (x_{i}),w\rangle _{\mathcal {F}}}$, ${\displaystyle {\text{ }}i=1,\dots ,q}$, ${\displaystyle w\in {\mathcal {F}}}$ . Еще раз, простая проверка показывает, что карта признаков нужна только для доказательства, а конечный результат зависит только от вычисления функции ядра.

Приложение для регуляризованных наименьших квадратов

В векторной и ядерной нотации проблема Регуляризованный метод наименьших квадратов можно переписать как:

${\displaystyle \min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\|{\hat {Y}}-{\hat {K}}c\|_{\mathbb {R} ^{n}}^{2}+\lambda \langle c,{\hat {K}}c\rangle _{\mathbb {R} ^{n}}}$.

Вычислив градиент и установив значение 0, можно получить минимум:

${\displaystyle {\begin{aligned}-{\frac {1}{n}}{\hat {K}}({\hat {Y}}-{\hat {K}}c)+\lambda {\hat {K}}c=0\Rightarrow {\hat {K}}({\hat {K}}+\lambda nI)c={\hat {K}}{\hat {Y}}\\\Rightarrow c=({\hat {K}}+\lambda nI)^{-1}{\hat {Y}},{\text{ where }}c\in \mathbb {R} ^{n}\\\end{aligned}}}$

Обратная матрица ${\displaystyle ({\hat {K}}+\lambda nI)^{-1}}$ можно вычислить, используя Тождество матрицы Вудбери:

${\displaystyle {\begin{aligned}({\hat {K}}+\lambda nI)^{-1}={\cfrac {1}{\lambda n}}{\bigg (}{\cfrac {1}{\lambda n}}{\hat {K}}+I{\bigg )}^{-1}\\={\cfrac {1}{\lambda n}}{\bigg (}I+{\hat {K}}_{n,q}({\lambda n}{\hat {K}}_{q})^{-1}{\hat {K}}_{n,q}^{\text{T}}{\bigg )}^{-1}\\={\cfrac {1}{\lambda n}}{\Big (}I-{\hat {K}}_{n,q}(\lambda n{\hat {K}}_{q}+{\hat {K}}_{n,q}^{\text{T}}{\hat {K}}_{n,q})^{-1}{\hat {K}}_{n,q}^{\text{T}}{\Big )}\\\end{aligned}}}$

Он имеет желаемые требования к хранению и сложности.

Аппроксимация случайных карт признаков

Позволять ${\displaystyle \mathbf {x} ,\mathbf {x'} \in \mathbb {R} ^{d}}$ - образцы данных, ${\displaystyle z:\mathbb {R} ^{d}\rightarrow \mathbb {R} ^{D}}$ - рандомизированный карта характеристик (отображает один вектор в вектор более высокой размерности), так что внутреннее произведение между парой преобразованных точек аппроксимирует их ядро оценка:

${\displaystyle K(\mathbf {x} ,\mathbf {x'} )=\langle \Phi (\mathbf {x} ),\Phi (\mathbf {x'} )\rangle \approx z(\mathbf {x} )^{\text{T}}z(\mathbf {x'} )}$,

куда ${\displaystyle \Phi }$ отображение, вложенное в Ядро RBF.

С ${\displaystyle z}$ низкоразмерен, ввод можно легко преобразовать с помощью ${\displaystyle z}$, после этого могут применяться различные методы линейного обучения для аппроксимации ответа соответствующего нелинейного ядра. Существуют различные рандомизированные карты функций для вычисления приближений к ядрам RBF. Например, Случайные особенности Фурье и случайные функции биннинга.

Случайные особенности Фурье

Случайные особенности Фурье карта производит Монте-Карло приближение к карте признаков. Метод Монте-Карло считается рандомизированным. Эти случайные особенности состоит из синусоид ${\displaystyle \cos(w^{\text{T}}\mathbf {x} +b)}$ случайно взятый из преобразование Фурье из ядро быть приближенным, где ${\displaystyle w\in \mathbb {R} ^{d}}$ и ${\displaystyle b\in \mathbb {R} }$ находятся случайные переменные. Линия выбирается случайным образом, затем точки данных проецируются на нее с помощью сопоставлений. Полученный скаляр пропускается через синусоиду. Произведение преобразованных точек будет приближать инвариантное к сдвигу ядро. Поскольку карта гладкая, случайные особенности Фурье хорошо работают с задачами интерполяции.

Возможности случайного биннинга

Карта случайного разбиения на части разделяет входное пространство с помощью случайно сдвинутых сеток с произвольно выбранными разрешениями и назначает входной точке двоичную битовую строку, которая соответствует ячейкам, в которые она попадает. Сетки построены так, что вероятность того, что две точки ${\displaystyle \mathbf {x} ,\mathbf {x'} \in \mathbb {R} ^{d}}$ присваиваются одному и тому же бункеру, пропорционально ${\displaystyle K(\mathbf {x} ,\mathbf {x'} )}$. Внутренний продукт между парой преобразованных точек пропорционален количеству раз, когда две точки объединяются вместе, и поэтому является несмещенной оценкой ${\displaystyle K(\mathbf {x} ,\mathbf {x'} )}$. Поскольку это сопоставление не является гладким и использует близость между входными точками, функции случайного объединения хорошо работают для аппроксимации ядер, которые зависят только от ${\displaystyle L_{1}}$ - расстояние между точками данных.

Сравнение методов аппроксимации

Подходы для крупномасштабного обучения ядра (Метод Нистрома и случайные признаки) отличается тем, что в методе Нюстрёма используются базисные функции, зависящие от данных, в то время как в подходе случайных признаков базисные функции выбираются из распределения, независимого от обучающих данных. Это различие приводит к улучшенному анализу подходов к обучению ядра, основанных на методе Нистрома. Когда есть большой разрыв в собственном спектре ядро матрица, подходы, основанные на методе Нистрома, могут дать лучшие результаты, чем Случайные особенности основанный подход.^[5]

Смотрите также

• Метод Нистрома
• Машина опорных векторов
• Ядро радиальной базисной функции
• Регуляризованный метод наименьших квадратов

внешняя ссылка

• Андреас Мюллер (2012). Аппроксимация ядра для эффективных SVM (и другие методы извлечения признаков).

Рекомендации

1. Фрэнсис Р. Бах и Майкл И. Джордан (2005). «Прогнозирующая низкоранговая декомпозиция для ядерных методов». ICML.
2. Уильямс, C.K.I. и Сигер М. (2001). «Использование метода Нистрома для ускорения ядерных машин». Достижения в системах обработки нейронной информации.
3. Петрос Дринес и Майкл В. Махони (2005). «О методе Нюстрёма для аппроксимации матрицы Грама для улучшенного обучения на основе ядра». Журнал исследований машинного обучения 6, стр. 2153–2175.
4. К. Эккарт, Г. Янг, Аппроксимация одной матрицы другой более низкого ранга. Психометрика, Том 1, 1936, страницы 211–8. Дои:10.1007 / BF02288367
5. Тяньбао Ян, Ю-Фэн ​​Ли, Мехрдад Махдави, Ронг Джин и Чжи-Хуа Чжоу (2012). "Метод Нистрома против случайных характеристик Фурье: теоретическое и эмпирическое сравнение". Достижения в системах обработки нейронной информации 25 (NIPS).