8.7. Приближение ядер

8.7.1. Метод Нюстрёма для приближения ядер

Метод Нюстрёма, реализованный в 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].

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

где:

• \(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\). Для этого выразим её через уже вычисленные матрицы:

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

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

Примеры

• См. пример Создание признаков, связанных со временем, в котором показан эффективный конвейер машинного обучения с использованием ядра Nystroem.
• См. Приближение явного отображения признаков для ядер RBF — сравнение ядра Nystroem с RBFSampler.

8.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 обходятся дешевле, поэтому эффективнее использовать пространства признаков большей размерности.

Примеры

• См. Приближение явного отображения признаков для ядер RBF — сравнение ядра Nystroem с RBFSampler.

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

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

Используемое здесь аддитивное ядро хи-квадрат задаётся выражением

Это не совсем то же самое, что 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], а сочетание с RBFSampler описано в работе [VVZ2010].

8.7.4. Асимметричное ядро хи-квадрат

Асимметричное ядро хи-квадрат задаётся выражением:

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

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

8.7.5. Приближение полиномиального ядра с помощью Tensor Sketch

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

где:

• x, y — входные векторы
• d — степень ядра

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

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

Примеры

• Масштабируемое обучение с приближением полиномиального ядра

8.7.6. Математические подробности

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

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

Если алгоритм, например линейная машина опорных векторов или метод главных компонент, зависит только от скалярного произведения точек данных \(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)\), что избавляет от необходимости применять ядро или хранить обучающие примеры.

Литература