6.7. Аппроксимация ядра (Kernel Approximation)

Этот подмодуль содержит функции, аппроксимирующие отображения признаков, соответствующие определенным ядрам, которые используются, например, в методе опорных векторов (см. Метод опорных векторов (Support Vector Machines - SVM)).

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

Преимущество использования приближенного явного мепинга признаков по сравнению с ядерным трюком, который использует мепинг признаков неявно, заключается в том, что явный мепинг может лучше подходить для онлайн-обучения и могут значительно снизить стоимость обучения на очень больших наборах данных.

Стандартные SVM с ядрами не очень хорошо масштабируются для больших наборов данных, но, используя приблизительный мепинг ядра, можно использовать гораздо более эффективные линейные SVM.

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

Поскольку эмпирических работ с использованием приближенных вкраплений было не так много, рекомендуется по возможности сравнивать результаты с точными ядерными методами.

См. также

Полиномиальная регрессия: расширение линейных моделей базисными функциями для точного полиномиального преобразования.

6.7.1. Метод Nystroem для аппроксимации ядра

Метод Найстрома, реализованный в Nystroem, является общим методом аппроксимации ядер с пониженным рангом. Он достигает этого путем подвыборки без замены строк/столбцов данных, на которых оценивается ядро. В то время как вычислительная сложность точного метода составляет \(\mathcal{O}(n^3_{\text{samples}})\), сложность аппроксимации составляет \(\mathcal{O}(n^2_{\text{components}} \cdot n_{\text{samples}})\), где можно задать \(n_{\text{components}} \ll n_{\text{samples}}\) без существенного снижения производительности [WS2001].

Мы можем построить cпектральное разложение матрицы ядра \(K\), основываясь на особенностях данных, а затем разделить ее на выборочные и невыборочные точки данных.

\[\begin{split}K = U \Lambda U^T = \begin{bmatrix} U_1 \\ U_2\end{bmatrix} \Lambda \begin{bmatrix} U_1 \\ U_2 \end{bmatrix}^T = \begin{bmatrix} U_1 \Lambda U_1^T & U_1 \Lambda U_2^T \\ U_2 \Lambda U_1^T & U_2 \Lambda U_2^T \end{bmatrix} \equiv \begin{bmatrix} K_{11} & K_{12} \\ K_{21} & K_{22} \end{bmatrix}\end{split}\]

где:

  • \(U\) ортонормирован

  • \(\Lambda\)- диагональная матрица собственных значений

  • \(U_1\) ортонормированая матрица образцов, которые были выбраны

  • \(U_2\) ортонормированая матрица образцов, которые небыли выбраны

Учитывая, что \(U_1 \Lambda U_1^T\) может быть получено ортонормированием матрицы \(K_{11}\), а \(U_2 \Lambda U_1^T\) может быть оценено (как и его транспонирование), остается выяснить только \(U_2 \Lambda U_2^T\). Для этого мы можем выразить его в терминах уже оцененных матриц:

\[\begin{split}\begin{align} U_2 \Lambda U_2^T &= \left(K_{21} U_1 \Lambda^{-1}\right) \Lambda \left(K_{21} U_1 \Lambda^{-1}\right)^T \\&= K_{21} U_1 (\Lambda^{-1} \Lambda) \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} U_1 \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} K_{11}^{-1} K_{21}^T \\&= \left( K_{21} K_{11}^{-\frac12} \right) \left( K_{21} K_{11}^{-\frac12} \right)^T .\end{align}\end{split}\]

Во время fit класс Nystroem оценивает базис \(U_1\) и вычисляет константу нормализации, \(K_{11}^{-\frac12}\). Позже, во время transform, определяется матрица ядра между базисом (заданным атрибутом components_) и новыми точками данных, X. Затем эта матрица умножается на матрицу normalization_ для получения окончательного результата.

По умолчанию Nystroem использует ядро rbf, но может использовать любую функцию ядра или предварительно вычисленную матрицу ядра. Количество используемых образцов, которое также является размерностью вычисляемых признаков, задается параметром n_components.

6.7.2. Ядро радиальной базисной функции

RBFSampler строит приближенное преобразование для ядра радиальной базисной функции, также известной как Random Kitchen Sinks [RR2007]. Это преобразование можно использовать для явного моделирования карты ядра перед применением линейного алгоритма, например, линейного SVM:

>>> from sklearn.kernel_approximation import RBFSampler
>>> from sklearn.linear_model import SGDClassifier
>>> X = [[0, 0], [1, 1], [1, 0], [0, 1]]
>>> y = [0, 0, 1, 1]
>>> rbf_feature = RBFSampler(gamma=1, random_state=1)
>>> X_features = rbf_feature.fit_transform(X)
>>> clf = SGDClassifier(max_iter=5)
>>> clf.fit(X_features, y)
SGDClassifier(max_iter=5)
>>> clf.score(X_features, y)
1.0

Это преобразование опирается на аппроксимацию значений ядра методом Монте-Карло. Функция fit выполняет выборку Монте-Карло, в то время как метод transform выполняет отображение данных. Из-за присущей этому процессу случайности результаты могут отличаться при разных вызовах функции fit.

Функция fit принимает два аргумента: n_components, который является целевой размерностью преобразования признаков, и gamma, параметр RBF-ядра. Большее значение n_components приведет к лучшей аппроксимации ядра и даст результаты, более похожие на те, что дает ядро SVM. Обратите внимание, что “обучение” функции признаков фактически не зависит от данных, передаваемых функции fit. Используется только размерность данных. Подробности о методе можно найти в [RR2007].

Для заданного значения n_components RBFSampler часто менее точен, чем Nystroem. Однако RBFSampler дешевле в вычислении, что делает использование больших пространств признаков более эффективным.

../_images/sphx_glr_plot_kernel_approximation_002.png

Сравнение точного RBF-ядра (слева) с аппроксимацией (справа)

6.7.3. Аддитивное ядро хи-квадрат

Аддитивное ядро хи-квадрат - это ядро на гистограммах, часто используемое в компьютерном зрении.

Аддитивное ядро хи-квадрат, используемое здесь, имеет вид

\[k(x, y) = \sum_i \frac{2x_iy_i}{x_i+y_i}\]

Это не совсем то же самое, что и sklearn.metrics.pairwise.additive_chi2_kernel. Авторы [VZ2010] предпочитают версию выше, поскольку она всегда положительно определенная.

Поскольку ядро аддитивно, можно рассматривать все компоненты \(x_i\) отдельно для встраивания. Это делает возможной выборку преобразования Фурье через регулярные интервалы, вместо аппроксимации с помощью выборки Монте-Карло.

Класс AdditiveChi2Sampler реализует эту компонентную детерминированную выборку. Каждый компонент сэмплируется \(n\) раз, что дает \(2n+1\) измерений на входное измерение (кратность двум обусловлена вещественной и комплексной частью преобразования Фурье).

В литературе \(n\) обычно выбирается равным 1 или 2, преобразуя набор данных до размера n_samples * 5 * n_features (в случае \(n=2\)).

Приблизительная карта признаков, предоставляемая AdditiveChi2Sampler, может быть объединена с приблизительной картой признаков, предоставляемой RBFSampler, чтобы получить приблизительную карту признаков для экспоненциального ядра хи-квадрат. Подробности см. в [VZ2010], а также в [VVZ2010] о сочетании с RBFSampler.

6.7.4. Перекошенное хи-квадратное ядро

Перекошенное ядро хи-квадрат имеет вид:

\[k(x,y) = \prod_i \frac{2\sqrt{x_i+c}\sqrt{y_i+c}}{x_i + y_i + 2c}\]

Оно имеет свойства, схожие с экспоненциальным хи-квадрат ядром, часто используемым в компьютерном зрении, но позволяет проводить простую аппроксимацию карты признаков методом Монте-Карло.

Использование SkewedChi2Sampler аналогично использованию, описанному выше для RBFSampler. Единственное отличие заключается в свободном параметре, который называется \(c\). Мотивацию этого отображения и математические подробности см. в [LS2010].

6.7.5. Аппроксимация полиномиального ядра через тензорный эскиз (Tensor Sketch)

полиномиальное ядро - это популярный тип ядровой функции, задаваемой:

\[k(x, y) = (\gamma x^\top y +c_0)^d\]

где:

  • x, y входные векторы

  • d это степень ядра

Интуитивно понятно, что пространство признаков полиномиального ядра степени d состоит из всех возможных произведений степени d между входными признаками, что позволяет алгоритмам обучения, использующим это ядро, учитывать взаимодействие между признаками.

Метод TensorSketch [PP2013], реализованный в PolynomialCountSketch, является масштабируемым, независимым от входных данных методом аппроксимации полиномиального ядра. Он основан на концепции Count sketch [WIKICS] [CCF2002], технике снижения размерности, похожей на хеширование признаков, в которой вместо этого используется несколько независимых хеш-функций. TensorSketch получает граф-эскиз внешнего произведения двух векторов (или вектора с самим собой), который можно использовать в качестве аппроксимации пространства признаков полиномиального ядра. В частности, вместо явного вычисления внешнего произведения TensorSketch вычисляет Count Sketch векторов, а затем использует полиномиальное умножение с помощью быстрого преобразования Фурье для вычисления Count Sketch их внешнего произведения.

Удобно, что фаза обучения TensorSketch состоит просто в инициализации некоторых случайных переменных. Таким образом, он не зависит от входных данных, то есть зависит только от количества входных признаков, но не от значений данных. Кроме того, этот метод может преобразовывать выборки за \(\mathcal{O}(n_{\text{samples}}(n_{\text{features}} + n_{\text{components}} \log(n_{\text{components}})))\) времени, где \(n_{\text{components}}\) - желаемая размерность выходного сигнала, определяемая n_components.

6.7.6. Математические детали

Ядерные методы, такие как методы опорных векторов или PCA с ядрами, опираются на свойство воспроизведения гильбертовых пространств ядра. Для любой положительно определенной функции ядра \(k\) (так называемого ядра Мерсера) гарантируется, что существует отображение \(\phi\) в гильбертово пространство \(\mathcal{H}\), такое, что

\[k(x,y) = \langle \phi(x), \phi(y) \rangle\]

, где \(\langle \cdot, \cdot \rangle\) обозначает внутреннее произведение в гильбертовом пространстве.

Если алгоритм, например, линейная машина векторов поддержки или PCA, опирается только на скалярное произведение точек данных \(x_i\), можно использовать значение \(k(x_i, x_j)\), которое соответствует применению алгоритма к сопоставленным точкам данных \(\phi(x_i)\).

Преимущество использования \(k\) заключается в том, что отображение \(\phi\) никогда не нужно вычислять явно, что позволяет использовать произвольно большие функции (даже бесконечные).

Один из недостатков корневых методов заключается в том, что при оптимизации может потребоваться хранить множество значений ядер \(k(x_i, x_j)\). Если ядерный классификатор применяется к новым данным \(y_j\), \(k(x_i, y_j)\) необходимо вычислить, чтобы сделать предсказания, возможно, для многих различных \(x_i\) в обучающем множестве.

Классы этого подмодуля позволяют аппроксимировать вложение \(\phi\), тем самым явно работая с представлениями \(\phi(x_i)\), что избавляет от необходимости применять ядро или хранить обучающие примеры.