Приближения матрицы низкого ранга

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

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

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

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

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

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

Метод назван «приближением Нистрема», потому что его можно интерпретировать как случай метода Нистрема из теории интегральных уравнений . ^[3]

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

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

${\tilde {K}}={\hat {K}}_{n,q}{\hat {K}}_{q}^{-1}{\hat {K}}_{n,q}^{\text{T}}$ , где

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

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

и

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

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

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

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

${\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}}$

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

${\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}}$

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

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

Еще одно доказательство

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

Применение разложения по сингулярным значениям к этим матрицам: ${\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}}.$

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

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

${\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}}.$

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

${\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}.$

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

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

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

${\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}}$

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

${\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}.$

Тогда выражение для ${\tilde {K}}$ : ${\tilde {K}}=({\hat {X}}{\hat {X}}_{q}^{\text{T}}){\hat {K}}_{q}^{-1}({\hat {X}}{\hat {X}}_{q}^{\text{T}})^{\text{T}}.$

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

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

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

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

В векторных и ядерных обозначениях задачу регуляризованных наименьших квадратов можно переписать как: $\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, можно получить минимум: ${\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}}$ Обратная матрица $({\hat {K}}+\lambda nI)^{-1}$ может быть вычислено с использованием матричного тождества Вудбери : ${\begin{aligned}({\hat {K}}+\lambda nI)^{-1}&={\frac {1}{\lambda n}}\left({\frac {1}{\lambda n}}{\hat {K}}+I\right)^{-1}\\&={\frac {1}{\lambda n}}\left(I+{\hat {K}}_{n,q}({\lambda n}{\hat {K}}_{q})^{-1}{\hat {K}}_{n,q}^{\text{T}}\right)^{-1}\\&={\frac {1}{\lambda n}}\left(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}}\right)\end{aligned}}$

Он имеет желаемые требования к объему памяти и сложности.

Аппроксимация рандомизированных карт объектов

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

$K(\mathbf {x} ,\mathbf {x'} )=\langle \Phi (\mathbf {x} ),\Phi (\mathbf {x'} )\rangle \approx z(\mathbf {x} )^{\text{T}}z(\mathbf {x'} ),$ где $\Phi$ — это отображение, встроенное в ядро RBF .

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

Случайные функции Фурье

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

Функции случайного группирования

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

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

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

См. также

Внешние ссылки

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

Ссылки

^ Фрэнсис Р. Бах и Майкл И. Джордан (2005). «Прогнозирующая низкоранговая декомпозиция для методов ядра» . ИКМЛ .
^ Jump up to: ^а ^б Уильямс, CKI; Сигер, М. (2001). «Использование метода Нистрема для ускорения работы машин с ядром» . Достижения в области нейронных систем обработки информации . 13 .
^ Jump up to: ^а ^б Петрос Дринеас и Майкл В. Махони (2005). «О методе Нистрема для аппроксимации матрицы Грамма для улучшения обучения на основе ядра». Журнал исследований машинного обучения 6 , стр. 2153–2175.
^ К. Эккарт, Г. Янг, Приближение одной матрицы другой более низкого ранга. Психометрика, том 1, 1936, страницы 211–8. дои : 10.1007/BF02288367
^ Тяньбао Ян, Ю-Фэн Ли, Мехрдад Махдави, Ронг Цзинь и Чжи-Хуа Чжоу (2012). «Метод Нистрема против случайных функций Фурье: теоретическое и эмпирическое сравнение». Достижения в области нейронных систем обработки информации 25 (NIPS) .

[1] Фрэнсис Р. Бах и Майкл И. Джордан (2005). «Прогнозирующая низкоранговая декомпозиция для методов ядра» . ИКМЛ .

[:2-2] Jump up to: ^а ^б Уильямс, CKI; Сигер, М. (2001). «Использование метода Нистрема для ускорения работы машин с ядром» . Достижения в области нейронных систем обработки информации . 13 .

[:4-3] Jump up to: ^а ^б Петрос Дринеас и Майкл В. Махони (2005). «О методе Нистрема для аппроксимации матрицы Грамма для улучшения обучения на основе ядра». Журнал исследований машинного обучения 6 , стр. 2153–2175.

[EYM-thm-4] К. Эккарт, Г. Янг, Приближение одной матрицы другой более низкого ранга. Психометрика, том 1, 1936, страницы 211–8. дои : 10.1007/BF02288367

[:3-5] Тяньбао Ян, Ю-Фэн Ли, Мехрдад Махдави, Ронг Цзинь и Чжи-Хуа Чжоу (2012). «Метод Нистрема против случайных функций Фурье: теоретическое и эмпирическое сравнение». Достижения в области нейронных систем обработки информации 25 (NIPS) .

[1]

[2]

[3]

[4]

[5]