Изменения

[[File:kernel3_2kernel2_3.png|600px500px|thumb|right|Пример использования ядерного трюка]]'''Ядерный трюк'''(ангангл. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.

Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение == Описание =={{Определение|definition=Функция $\langle K(x,x'):X×X\ranglerightarrow \mathbb{R}$ на ядро называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ Более того, можно вообще не строить спрямляющее пространствоHв явномвиде, и вместо подбора отображения при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ заниматься непосредственно подбором ядра{{---}} пространство со скалярным произведением.}}

Можно пойти ещё дальшеПоскольку для задачи линейного разделения объектов не требуется их признаковое описание, и вовсе отказаться от признаковых описаний объек-тов. Во многих практических задачах объекты изначально задаются информациейоб их попарном взаимоотношенииа достаточно скаляров, напримерто можно заменить скалярное произведение $\langle x, отношении сходства. Если эта инфор-мация допускает представление в виде двуместной функции x'\rangle$ на ядро $K(x,x')$. Более того, удовлетворяю-щей аксиомам скалярного произведенияможно вообще не строить спрямляющее пространство $H$ в явном виде, то задача может решаться методом [[Метод опорных векторов (SVM) | SVM ]]и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.

== Теорема Мерсера ==Функция Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,yx') является ядром тогда и только тогда$, удовлетворяющей аксиомам скалярного произведения, когда:то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов]].

Она симметрична: $K(x,y)=K(y,x)$= Преимущества и недостатки ==

Она '''Преимущества''' * Обобщение линейных методов на нелинейный случай: а) с сохранением вычислительной эффективности линейных методов. б) с сохранением преимуществ линейных методов (локальный оптимум является глобальным, нет локальных оптимумов=>меньше переобучение). * Объекты для которых не существует векторных представлений фиксированной длины. * Ускоренное вычисление скалярных произведений для высоких значений размерностей. '''Недостатки''' * Вычислительно сложно проверять принадлежность функции ядру. * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия. == Характерные случаи применения ==* Признаковое пространство высокой размерности. Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности. * Случай, когда сложно представить объекты векторами фиксированной длины. Такие, как строки, множества, картинки, тексты, графы, 3D-структуры и т.д. * Существование естественного определения скалярного произведения. Такие, как строки (число совместно встречающихся подстрок) или множества (напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$). * Скалярное произведение может быть подсчитано эффективно. == Выбор функции ядра =={{Теорема|id=merser|author=Мерсера|statement = Функция $K(x,y)$ является ядром тогда и только тогда, когда она симметрична: $K(x,y)=K(y,x)$ и неотрицательно определена, то есть $\forall g: X \rightarrow \mathbb{R}, \int_X \int_X K(x, x')g(x)g(x')dxdx' \geqslant 0$|proof = }} Таким образом мы видим, что класс ядер достаточно широк. Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах<ref>[https://www.researchgate.net/publication/221080223_An_Evolutionary_Approach_to_Automatic_Kernel_Construction - T.Howley, M.G.Madden — An Evolutionary Approach to Automatic Kernel Construction]</ref>.

1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.

4. Для любой функции $\psi :X\rightarrow R$ произведение <tex>$K(x,x′) =\psi(x)\psi(x′x')</tex>${{---}} ядро.

5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x′x') ==\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.

6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядраK0является ядра $K_0$ является ядром: $K(x,x') =K_0(\varphi(x),\varphi(x'))$.

7. ЕслиsЕсли $s:$X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int Xsint_Xs(x,z)s(x',z)dz$dzявляется является ядром.//TODO

8. Функция вида $K(x,x') = k(x−x')$ является ядром тогда и только тогда, когдаФурьекогда Фурье-образ $F[k](\omega) = (2\Pipi)n_2∫Xe−i〈^{\owmegafrac{n}{2}}\int_Xe^{−i\langle\omega,x〉kx\rangle }k(x)dx $ неотрицателен.

10. Композиция произвольного ядраK0и ядра $K_0$ и произвольной функции ''$f'':R\rightarrow R$, представимой в виде сходящегося степенного ряда с неотрицательными коэффициентами $K(x,x') = f(K_0(x,x'))$, является ядром. В частности, функции $f(z) =e^z$ и $f(z) =\frac{1/}{1−z} от $ где $z$ {{---}} функция ядра {{---}} являются ядрами.  == Некоторые часто используемые ядра == 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$ Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию. 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$<ref>https://en.wikipedia.org/wiki/Polynomial_kernel - Polynomial kernel</ref> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром. 2. '''Гаусово''' (англ. gaussian) ядро RBF (Radial basis function)<ref>[https://en.wikipedia.org/wiki/Radial_basis_function_kernel - RBF]</ref> $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$ Такое ядро соответствует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности. 3. '''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$  В отличие от предыдущих 3-х не является ядром Мерсера (не выполняет условие теоремы), но при этом на практике работает хорошо. 4. '''Строковое''' Строковые ядра <ref>[https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D1%80%D0%BE%D0%BA%D0%BE%D0%B2%D0%BE%D0%B5_%D1%8F%D0%B4%D1%80%D0%BE#%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 - Строковое ядро]</ref> это различные ядерные функции для вычисления расстояний между двумя строками.  == Использование ядер в коде ==

== Ядерный трюк ==* Подключаем библиотеки:Поскольку для обучения зачастую необходима уже функция "расстояния" между элементами в новом пространстве, то вместо явного нахождения ядра {{---}} его можно зашить внутрь соответсвующей функции k(x, x '). Такую функцию k называют ''import'ядерной функцией'' svm model '''from''' sklearn '''import'''svm

clf == Некоторые часто используемые функции ==0svm.Линейное $KSVC(x, xkernel='linear')= \langle x, x'\rangle$

1*Тренируем модель используя заданные сеты и смотрим на предсказанные ответы: clf.Полиномиальное ядро $K'''fit'''(xX_train, x'y_train) y_pred = clf.'''predict'''(\langle x, x' \rangle + RX_test)^d$

2.Гаусово ядро RBF K(xКроме того, x') = exp(у этой функции так же присутствует гипперпараметры {{--\gamma ||x - x}} '''регуляризация''' (англ. regularization), который отвечает за размер штрафа и гамма, которая отвечает за приближенность результирующей функций к датасету. Здесь нужно помнить, что при больших значениях гамма возможно [[Переобучение||^2)переобучение]].