Kernelised k Ближайший сосед

Я новичок в ядрах и попал в ловушку при попытке ядра KNN.

прелиминарии

Я использую ядро ​​с полиномами:
$K(\mathbf{x},\mathbf{y}) = (1 + \langle \mathbf{x},\mathbf{y} \rangle)^d$

Ваш типичный евклидов kNN использует следующую метрику расстояния:
$d(\mathbf{x}, \mathbf{y}) = \vert\vert \mathbf{x} - \mathbf{y} \vert\vert$

Пусть отображает в некоторое многомерное пространство признаков. Тогда квадрат указанной выше метрики расстояния в гильбертовом пространстве можно выразить внутренними произведениями: $f(\mathbf{x})$$\mathbf{x}$$d^2(f(x), f(y)) = K(\mathbf{x},\mathbf{x}) - 2K(\mathbf{x}, \mathbf{y}) + K(\mathbf{y} ,\mathbf{y})$

Обратите внимание, что если мы допустим вышеприведенное выродится в ваше стандартное евклидово расстояние.$d = 1$

Вопрос

Основная проблема, с которой я столкнулся, заключается в том, что я не могу понять, как при создании ядра kNN получаются лучшие результаты, как показано экспериментально, например, в этой статье (предупреждение, прямая ссылка в формате PDF!)

Теорема Обложки: Грубо говоря, она говорит, что при любом случайном наборе конечных точек (с произвольными метками), с высокой вероятностью эти точки можно сделать линейно отделимыми [1], сопоставив их с более высокой размерностью [2].

Вывод: Отлично, эта теорема говорит мне о том, что если я возьму свой набор данных и сопоставлю эти точки с более высоким измерением, то я легко найду линейный классификатор. Однако большинству классификаторов необходимо вычислять какое-то подобие, такое как скалярное произведение, и это означает, что временная сложность алгоритма классификации пропорциональна измерению точки данных. Таким образом, более высокая размерность означает большую временную сложность (не говоря уже о пространственной сложности для хранения этих больших размерных точек).

Уловка ядра: Пусть будет исходным измерением точек данных, а будет картой, которая отображает эти точки в пространство измерения . Теперь, если есть функция которая берет входные данные и из исходного пространства и вычисляет , то я могу вычислить скалярное произведение в многомерном пространстве, но по сложности вместо .$n$$f$$N (>> n)$$K$$x$$y$$K(x, y) = \langle f(x), f(y) \rangle$$O(n)$$O(N)$

Вывод: Итак, если алгоритм классификации зависит только от точечного произведения и не зависит от фактической карты , я могу использовать трюк с ядром для запуска алгоритма в многомерном пространстве практически без дополнительных затрат.$f$

Означает ли линейная отделимость, что точки из одного и того же класса станут ближе, чем точки из разных классов? Нет, такой гарантии как таковой нет. Линейная отделимость на самом деле не означает, что точка из одного и того же класса стала ближе или что точки из двух разных классов стали еще дальше.

Так почему же KNN работает? Это не нужно! Однако, если это так, то это чисто из-за ядра.

Что это значит? Рассмотрим вектор логических функций . Когда вы используете ядро ​​полинома второй степени, вектор элементов отображается на вектор$x = (x_1, x_2)$$x$$(x_1^2, \sqrt{2} x_1x_2, x_2^2)$, Из вектора булевых признаков, просто используя полином второй степени, мы получили вектор признаков "союзов". Таким образом, сами ядра производят некоторые блестящие функциональные карты. Если ваши данные имеют хорошие оригинальные функции и могут ли ваши данные извлечь пользу из карт характеристик, созданных этими ядрами. Под преимуществом я подразумеваю, что функции, создаваемые этими картами функций, могут приблизить точки одного и того же класса друг к другу и оттолкнуть точки от разных классов, тогда kNN выиграет от использования ядер. В противном случае результаты не будут отличаться от результатов, полученных при запуске kNN для исходных данных.

Тогда зачем использовать ядро ​​kNN? Мы показали, что сложность вычислений с использованием ядер чуть больше, чем у обычных kNN, и если данные выигрывают от использования ядер, то почему бы не использовать их в любом случае?

Есть ли статья, которая изучала, какой класс данных может извлечь выгоду из ядер в kNN? Насколько я знаю, нет.

[1] http://en.wikipedia.org/wiki/Linear_separability
[2] http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038449&tag=1