Ядро — различия между версиями
256331 (обсуждение | вклад) |
256331 (обсуждение | вклад) (Добавлено описание ядер, подредактированы формулы) |
||
| Строка 1: | Строка 1: | ||
| − | [[File:kernel3_2.png| | + | [[File:kernel3_2.png|500px|thumb|right|Пример использования ядерного трюка]] |
'''Ядерный трюк'''(анг. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти. | '''Ядерный трюк'''(анг. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти. | ||
| Строка 6: | Строка 6: | ||
Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''', если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$,где H {{---}} пространство со скалярным произведением. | Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''', если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$,где H {{---}} пространство со скалярным произведением. | ||
| − | Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$ Более того, можно вообще не строить спрямляющее | + | Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$ Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра. |
| − | Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний | + | Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта инфор-мация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом [[Метод опорных векторов (SVM) | SVM ]]. |
| − | == | + | == Выбор функции ядра == |
| − | Функция K(x,y) является ядром тогда и только тогда, когда: | + | '''Теорема Мерсера''': Функция 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$ |
| − | + | Таким образом мы видим, что класс ядер достаточно широк. | |
| − | + | Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая(обычно по критерию скользящего контроля). Такое решение не будет оптимальным и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой. | |
== Конструктивные способы построения ядер == | == Конструктивные способы построения ядер == | ||
| Строка 24: | Строка 24: | ||
3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром. | 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром. | ||
| − | 4. Для любой функции $\psi :X\rightarrow R$ произведение | + | 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро. |
| − | 5. Линейная комбинация ядер с неотрицательными коэффициентами K(x, | + | 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром. |
| − | 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного | + | 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$. |
| − | 7. | + | 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром. |
| − | 8. Функция вида K(x,x') = k(x−x)является ядром тогда и только тогда, | + | 8. Функция вида $K(x,x') = k(x−x)$ является ядром тогда и только тогда, когда Фурье-образ $F[k](\omega) = (2\pi)^{\frac{n}{2}}\int_Xe^{−i\langle\omega,x\rangle }k(x)dx$ неотрицателен. |
9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро. | 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро. | ||
| − | 10. Композиция произвольного | + | 10. Композиция произвольного ядра $K_0$ и произвольной функции $f:R\rightarrow R$, представимой в виде сходящегося степенного ряда с неотрицательными коэффициентами $K(x,x') = f(K_0(x,x'))$, является ядром. В частности, функции $f(z) =e^z$ и $f(z) =\frac{1}{1−z}$ от ядра являются ядрами. |
| − | == | + | == Некоторые часто используемые функции == |
| − | |||
| − | |||
| − | |||
0.Линейное $K(x, x')= \langle x, x'\rangle$ | 0.Линейное $K(x, x')= \langle x, x'\rangle$ | ||
| + | Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию. | ||
1.Полиномиальное ядро $K(x, x') = (\langle x, x' \rangle + R)^d$ | 1.Полиномиальное ядро $K(x, x') = (\langle x, x' \rangle + R)^d$ | ||
| − | 2.Гаусово ядро RBF K(x, x') = exp(-\ | + | Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром. |
| + | |||
| + | 2.Гаусово ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$ | ||
| + | |||
| + | Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности. | ||
| + | == См. также == | ||
| + | * [[Метод опорных векторов (SVM)]] | ||
| + | == Примечания == | ||
| + | <references/> | ||
== Источники информации == | == Источники информации == | ||
#[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам] | #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства 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 — Ядерный метод] | ||
[[Категория: Машинное обучение]] | [[Категория: Машинное обучение]] | ||
| + | [[Категория: Классификация]] | ||
Версия 03:53, 22 марта 2020
Ядерный трюк(анг. kernel function) метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство пространство. Такое пространство называют спрямляющим. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.
Содержание
Определение
Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется ядром, если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$,где H — пространство со скалярным произведением.
Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$ Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.
Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта инфор-мация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом SVM .
Выбор функции ядра
Теорема Мерсера: Функция 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$
Таким образом мы видим, что класс ядер достаточно широк.
Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая(обычно по критерию скользящего контроля). Такое решение не будет оптимальным и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.
Конструктивные способы построения ядер
1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.
2. Константа $K(x,x') = 1$ является ядром.
3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.
4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')$— ядро.
5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.
6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.
7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.
8. Функция вида $K(x,x') = k(x−x)$ является ядром тогда и только тогда, когда Фурье-образ $F[k](\omega) = (2\pi)^{\frac{n}{2}}\int_Xe^{−i\langle\omega,x\rangle }k(x)dx$ неотрицателен.
9. Предел локально-равномерно сходящейся последовательности ядер — ядро.
10. Композиция произвольного ядра $K_0$ и произвольной функции $f:R\rightarrow R$, представимой в виде сходящегося степенного ряда с неотрицательными коэффициентами $K(x,x') = f(K_0(x,x'))$, является ядром. В частности, функции $f(z) =e^z$ и $f(z) =\frac{1}{1−z}$ от ядра являются ядрами.
Некоторые часто используемые функции
0.Линейное $K(x, x')= \langle x, x'\rangle$ Используется в алгоритме SVM по умолчанию.
1.Полиномиальное ядро $K(x, x') = (\langle x, x' \rangle + R)^d$
Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.
2.Гаусово ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$
Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.
См. также
Примечания
