Низкоранговые матричные аппроксимации

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

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

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

Методы ядра становятся вычислительно неосуществимыми, когда количество точек настолько велико, что матрицу ядра невозможно сохранить в памяти. Д {\displaystyle D} К {\displaystyle К}

Если — число обучающих примеров, то затраты на хранение и вычисление, необходимые для нахождения решения задачи с использованием общего метода ядра , составляют и соответственно. Аппроксимация Нистрёма может позволить значительно ускорить вычисления. [2] [3] Это ускорение достигается за счет использования вместо матрицы ядра ее аппроксимации ранга . Преимущество метода заключается в том, что нет необходимости вычислять или хранить всю матрицу ядра, а только подматрицу размера . н {\displaystyle n} О ( Д 2 ) {\displaystyle O(D^{2})} О ( Д 3 ) {\displaystyle O(D^{3})} К ~ {\displaystyle {\тильда {К}}} г {\displaystyle д} г × Д {\displaystyle d\times D}

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

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

Ядерное приближение

[1] [4] : 357  [5]

Рассмотрим положительно-определенную функцию ядра . Имея некоторые точки данных , мы можем сформировать матрицу ядра, такую ​​что . к : Х × Х → Р {\displaystyle k:X\times X\to \mathbb {R} } х 1 , х 2 , … , х Д {\displaystyle x_{1},x_{2},\точки ,x_{D}} К ∈ Р Д × Д {\displaystyle K\in \mathbb {R} ^{D\times D}} К я дж := к ( х я , х дж ) {\displaystyle K_{ij}:=k(x_{i},x_{j})}

Теперь, пусть будет целым числом, тогда мы можем разделить матрицу ядра как , где — верхний левый угол. Также, установите, чтобы быть ее первыми столбцами. г ∈ 1 : Д {\displaystyle d\in 1:D} К = [ К 11 К 12 К 21 К 22 ] ∈ Р Д × Д {\textstyle K={\begin{bmatrix}K_{11}&K_{12}\\K_{21}&K_{22}\end{bmatrix}}\in \mathbb {R} ^{D\times D}} К 11 ∈ Р г × г {\textstyle K_{11}\in \mathbb {R} ^{d\times d}} С = [ К 11 К 21 ] {\textstyle C={\begin{bmatrix}K_{11}\\K_{21}\end{bmatrix}}} г {\displaystyle д}

Приближение Нистрёма в этом случае равно , где — псевдообратная матрица Мура–Пенроуза для , которая должна существовать, поскольку является положительно полуопределенной. К {\displaystyle К} К ~ = С К 11 + С Т = [ К 11 К 21 ] К 11 + [ К 11 К 12 ] {\displaystyle {\tilde {K}}=CK_{11}^{+}C^{T}={\begin{bmatrix}K_{11}\\K_{21}\end{bmatrix}}K_{11}^{+}{\begin{bmatrix}K_{11}&K_{12}\end{bmatrix}}} К 11 + {\displaystyle К_{11}^{+}} К 11 {\displaystyle К_{11}} К 11 {\displaystyle К_{11}}

Характеристики

По теореме Мерсера мы можем разложить матрицу ядра как матрицу Грама : , где . Пусть — левые столбцы . К = Х Т Х {\textstyle К=Х^{Т}Х} Х ∈ Р Н × Д {\textstyle X\in \mathbb {R} ^{N\times D}} Х ′ {\textstyle X'} г {\textstyle д} Х {\textstyle X}

Теорема  —  Мы имеем

  1. К ~ = [ К 11 К 12 К 21 К 21 К 11 + К 12 ] {\displaystyle {\tilde {K}}={\begin{bmatrix}K_{11}&K_{12}\\K_{21}&K_{21}K_{11}^{+}K_{12}\end{bmatrix}}}
  2. Приближение Нистрёма — это уникальная матрица, которая является симметричной, имеет те же первые столбцы, что и , и имеет пространство столбцов, охватываемое первыми столбцами . К ~ {\textstyle {\тильда {К}}} г {\textstyle д} К {\textstyle К} г {\textstyle д} К {\textstyle К}
  3. К ~ = ( П Х ) Т ( П Х ) {\textstyle {\tilde {K}}=(PX)^{T}(PX)} , где — матрица проекции, которая ортогонально проецируется в пространство, охватываемое первыми столбцами . П {\textstyle П} г {\textstyle д} Х {\textstyle X}
  4. К ~ {\textstyle {\тильда {К}}} является положительно полуопределенным.
  5. Если , то . классифицировать ⁡ ( К 11 ) = классифицировать ⁡ ( К ) {\textstyle \operatorname {ранг} (K_{11}) = \operatorname {ранг} (K)} К ~ = К {\textstyle {\тильда {К}}=К}
Доказательство
Доказательство

1. Верхний левый угол — по предложению о псевдообратном: . К 11 К 11 + К 11 = К 11 {\textstyle K_{11}K_{11}^{+}K_{11}=K_{11}}

Возьмем SVD , где полные квадраты, и имеет форму . Теперь оценим методом грубой силы верхний правый угол, который дает Count диагональных элементов, и увидим, что сигма-кластер оценивается как . Х ′ = У Σ В {\textstyle X'=U\Сигма V} У , В {\textstyle U,V} Σ {\textstyle \Сигма} Р Н × г {\textstyle \mathbb {R} ^{N\times d}} ( У Σ ( Σ Т Σ ) + ( Σ Т Σ ) В ) Т Х ″ {\displaystyle (U\Сигма (\Сигма ^{T}\Сигма )^{+}(\Сигма ^{T}\Сигма )V)^{T}X''} Σ {\textstyle \Сигма}

2. Из первых двух требований мы знаем, что . Из предыдущего расчета мы знаем, что , поэтому можем записать . Третье требование тогда подразумевает . К ~ = [ К 11 К 12 К 21 ? ] {\textstyle {\tilde {K}}={\begin{bmatrix}K_{11}&K_{12}\\K_{21}&?\end{bmatrix}}} К 11 К 11 + К 12 = К 12 {\textstyle K_{11}K_{11}^{+}K_{12}=K_{12}} К ~ = [ К 11 К 11 ( К 11 + К 12 ) К 21 ? ] {\textstyle {\tilde {K}}={\begin{bmatrix}K_{11}&K_{11}(K_{11}^{+}K_{12})\\K_{21}&?\end{ бматрица}}} К ~ = [ К 11 К 11 ( К 11 + К 12 ) К 21 К 21 ( К 11 + К 12 ) ] {\textstyle {\tilde {K}}={\begin{bmatrix}K_{11}&K_{11}(K_{11}^{+}K_{12})\\K_{21}&K_{21}( K_{11}^{+}K_{12})\end{bmatrix}}}

3. Оцените непосредственно в матричных блоках и получите К ~ = Х Т ( Х ′ ( Х ′ Т Х ′ ) + Х ′ Т ) Х {\displaystyle {\tilde {K}}=X^{T}(X'(X'^{T}X')^{+}X'^{T})X}

Возьмем SVD , где — полные квадраты, и имеет форму . Теперь оценим, где — матрица формы . Она диагональная. Ее первые элементы — 1, а остальные — 0. Х ′ = У Σ В {\textstyle X'=U\Сигма V} У , В {\textstyle U,V} Σ {\textstyle \Сигма} Р Н × г {\textstyle \mathbb {R} ^{N\times d}} Х ′ ( Х ′ Т Х ′ ) + Х ′ Т = У М У Т {\displaystyle X'(X'^{T}X')^{+}X'^{T}=UMU^{T}} М = Σ ( Σ Т Σ ) + Σ Т {\textstyle M=\Sigma (\Sigma ^{T}\Sigma )^{+}\Sigma ^{T}} R N × N {\textstyle \mathbb {R} ^{N\times N}} rank ⁡ ( X ′ ) {\textstyle \operatorname {rank} (X')}

Таким образом, является ортогональной проекцией на первые столбцы . U M U T {\textstyle UMU^{T}} rank ⁡ ( X ′ ) {\textstyle \operatorname {rank} (X')} U {\textstyle U}

(4) является следствием (3). (5) является следствием (2)

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

В векторной и ядерной нотации задачу регуляризованных наименьших квадратов можно переписать следующим образом: Вычислив градиент и установив его равным 0, можно получить минимум: Обратную матрицу можно вычислить с использованием тождества матрицы Вудбери : Она имеет желаемые требования к хранению и сложности. min c ∈ R n 1 n ‖ Y − K c ‖ R n 2 + λ ⟨ c , K c ⟩ R n . {\displaystyle \min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\|Y-Kc\|_{\mathbb {R} ^{n}}^{2}+\lambda \langle c,Kc\rangle _{\mathbb {R} ^{n}}.} − 1 n K ( Y − K c ) + λ K c = 0 ⇒ K ( K + λ n I ) c = K Y ⇒ c = ( K + λ n I ) − 1 Y ,  where  c ∈ R n {\displaystyle {\begin{aligned}&-{\frac {1}{n}}K(Y-Kc)+\lambda Kc=0\\\Rightarrow {}&K(K+\lambda nI)c=KY\\\Rightarrow {}&c=(K+\lambda nI)^{-1}Y,{\text{ where }}c\in \mathbb {R} ^{n}\end{aligned}}} ( K + λ n I ) − 1 {\displaystyle (K+\lambda nI)^{-1}} ( K + λ n I ) − 1 = 1 λ n ( 1 λ n K + I ) − 1 = 1 λ n ( I + K n , q ( λ n K q ) − 1 K n , q T ) − 1 = 1 λ n ( I − K n , q ( λ n K q + K n , q T K n , q ) − 1 K n , q T ) {\displaystyle {\begin{aligned}(K+\lambda nI)^{-1}&={\frac {1}{\lambda n}}\left({\frac {1}{\lambda n}}K+I\right)^{-1}\\&={\frac {1}{\lambda n}}\left(I+K_{n,q}({\lambda n}K_{q})^{-1}K_{n,q}^{\text{T}}\right)^{-1}\\&={\frac {1}{\lambda n}}\left(I-K_{n,q}(\lambda nK_{q}+K_{n,q}^{\text{T}}K_{n,q})^{-1}K_{n,q}^{\text{T}}\right)\end{aligned}}}

Рандомизированная аппроксимация карт признаков

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

K ( x , x ′ ) = ⟨ Φ ( x ) , Φ ( x ′ ) ⟩ ≈ z ( x ) T z ( x ′ ) , {\displaystyle K(\mathbf {x} ,\mathbf {x'} )=\langle \Phi (\mathbf {x} ),\Phi (\mathbf {x'} )\rangle \approx z(\mathbf {x} )^{\text{T}}z(\mathbf {x'} ),} где отображение встроено в ядро ​​RBF . Φ {\displaystyle \Phi }

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

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

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

Случайные особенности биннинга

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

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

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

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

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

Ссылки

  1. ^ ab Бах, Фрэнсис Р.; Джордан, Майкл И. (7–11 августа 2005 г.). Предиктивная низкоранговая декомпозиция для методов ядра. Международная конференция по машинному обучению. Бонн, Германия: ACM Press. стр.  33–40 . doi :10.1145/1102351.1102356. ISBN 978-1-59593-180-1.
  2. ^ ab Williams, CKI; Seeger, M. (2001). «Использование метода Нистрёма для ускорения ядерных машин». Достижения в области нейронных систем обработки информации . 13 .
  3. ^ ab Дринеас, Петрос; Махони, Майкл В. (2005), Ауэр, Питер; Мейр, Рон (ред.), «Аппроксимация матрицы Грама для улучшенного обучения на основе ядра», Теория обучения , т. 3559, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр.  323–337 , doi :10.1007/11503415_22, ISBN 978-3-540-26556-6, получено 20 января 2025 г.
  4. ^ Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2018). Основы машинного обучения . Адаптивные вычисления и машинное обучение (Второе изд.). Кембридж, Массачусетс: The MIT Press. ISBN 978-0-262-03940-6.
  5. ^ Гиттенс, Алекс; Махони, Майкл У. (3 июня 2013 г.), Пересмотр метода Нистрома для улучшения крупномасштабного машинного обучения, doi :10.48550/arXiv.1303.1849
  6. ^ Тяньбао Ян, Ю-Фэн ​​Ли, Мехрдад Махдави, Ронг Цзинь и Чжи-Хуа Чжоу (2012). «Метод Нистрёма против случайных признаков Фурье: теоретическое и эмпирическое сравнение». Достижения в области нейронных систем обработки информации 25 (NIPS) .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Low-rank_matrix_approximations&oldid=1270665500"