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

6.7.1. Метод Nystroem для приближения ядер

Метод 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].

Мы можем построить разложение по собственным значениям матрицы ядра \(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.

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

Класс RBFSampler строит приближённое отображение для ядра радиальной базисной функции, также известного как случайные кухонные раковины [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

6.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], а также [VVZ2010] для объединения с RBFSampler.

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

Кососимметричное ядро хи-квадрат задается следующим образом:

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

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

6.7.5. Приближение полиномиального ядра с помощью тензорного наброска

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

где:

• 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.

Примеры

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

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

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

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

Ссылки