Изменения

[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]'''Ядерный трюк'''Ядро(Kernelангл. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'' - функция x->\fi(x)'. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, которая позволяет совершить преобразование признаков и получить линейно разделимое пространствоглавной проблемой становится его найти.

== Теорема Мерсера ==Функция Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,yx') является ядром тогда $. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и только тогда, когда:вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.

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

Она неотрицательно определена== Преимущества и недостатки == '''Преимущества''' * Обобщение линейных методов на нелинейный случай: а) с сохранением вычислительной эффективности линейных методов. б) с сохранением преимуществ линейных методов (локальный оптимум является глобальным, нет локальных оптимумов=>меньше переобучение). * Объекты для которых не существует векторных представлений фиксированной длины. * Ускоренное вычисление скалярных произведений для высоких значений размерностей. '''Недостатки''' * Вычислительно сложно проверять принадлежность функции ядру. * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия. == Характерные случаи применения ==* Признаковое пространство высокой размерности. Например все полиномы до степени $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_ix,x_jy)=K(y,x)^l_$ и неотрицательно определена, то есть $\forall g: X \rightarrow \mathbb{iR}, \int_X \int_X K(x,jx')g(x)g(x')dxdx' \geqslant 0$ |proof =1} неотрицательно определена } Таким образом мы видим, что класс ядер достаточно широк. Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах<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произведение $ K(x,x') =<\langle x,x'>\rangle $ является ядром.

2. КонстантаKКонстанта $K(x,x') = 1 $ является ядром.

3. Произведение ядер <tex>$K(x,x') =K_1(x,x')K_2(x,x')<tex>$является ядром.

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

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

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

7. ЕслиsЕсли $s:X×X→R X×X\rightarrow R$ произвольная симметричная интегрируемая функция, тоKто $K(x,x′) =∫Xs\int_Xs(x,z)s(x′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коэффициентами $K(x,x') =f(K_0(x,x'))$, является ядром. В частности, функцииfфункции $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> это различные ядерные функции для вычисления расстояний между двумя строками.  == Использование ядер в коде == В библиотеке языка Python {{---}} sklearn.clustering<ref>https://scikit-learn.org/stable/modules/classes.html#module-sklearn.cluster - sklearn.cluster</ref>, есть функции и классы которые используют ядра для кластеризации, например SVM(Support vector machines). * Подключаем библиотеки: '''import''' svm model '''from''' sklearn '''import''' svm * Создаём классификатор svm {{---}} Classifier. В данном случае используется линейное ядро. Так же можно использовать 'polynomial' и 'rbf' [[Ядро#Некоторые часто используемые ядра|(см. используемые ядра)]].  clf = svm.SVC(kernel='linear') *Тренируем модель используя заданные сеты и смотрим на предсказанные ответы: clf.'''fit'''(X_train, y_train) y_pred = clf.'''predict'''(X_test)

== Ядерный трюк См. также ==Поскольку для обучения зачастую необходима уже функция "расстояния" между элементами в новом пространстве, то вместо явного нахождения ядра {{---}} его можно зашить внутрь соответсвующей функции k* [[Метод опорных векторов (x, x'SVM). Такую функцию k называют '''ядерной функцией''']]* [[Линейная регрессия]]* [[Логистическая регрессия]]* [[Регуляризация]]

== Некоторые часто используемые функции Источники информации ==0.Линейное K(x, x')=<x, x'>

#[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.Полиномиальное ядро K(x, x') = (<x, x'> + R)^dpdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]#[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]#[https://ru.wikipedia.org/wiki/%D0%AF%D0%B4%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4#%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0:_%D1%8F%D0%B4%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D1%82%D1%80%D1%8E%D0%BA wikipedia.org — Ядерный метод]#[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]#[https://www.datacamp.com/community/tutorials/svm-classification-scikit-learn-python#kernels datacamp.com — Support Vector Machines with Scikit-learn]