http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=256331 2026-06-11T16:46:38Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73213 2020-03-23T16:15:26Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов]].<br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов (локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторных представлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие, как строки, множества, картинки, тексты, графы, 3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие, как строки (число совместно встречающихся подстрок) или множества (напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах&lt;ref&gt;[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]&lt;/ref&gt;.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> <br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$&lt;ref&gt;https://en.wikipedia.org/wiki/Polynomial_kernel - Polynomial kernel&lt;/ref&gt;<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF (Radial basis function)&lt;ref&gt;[https://en.wikipedia.org/wiki/Radial_basis_function_kernel - RBF]&lt;/ref&gt; $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответствует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3. '''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличие от предыдущих 3-х не является ядром Мерсера (не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4. '''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> <br /> == Использование ядер в коде ==<br /> <br /> В библиотеке языка Python {{---}} sklearn.clustering&lt;ref&gt;https://scikit-learn.org/stable/modules/classes.html#module-sklearn.cluster - sklearn.cluster&lt;/ref&gt;, есть функции и классы которые используют ядра для кластеризации, например SVM(Support vector machines).<br /> <br /> * Подключаем библиотеки:<br /> '''import''' svm model<br /> '''from''' sklearn '''import''' svm<br /> <br /> * Создаём классификатор svm {{---}} Classifier. В данном случае используется линейное ядро. Так же можно использовать 'polynomial' и 'rbf' [[Ядро#Некоторые часто используемые ядра|(см. используемые ядра)]].<br /> <br /> clf = svm.SVC(kernel='linear')<br /> <br /> *Тренируем модель используя заданные сеты и смотрим на предсказанные ответы:<br /> clf.'''fit'''(X_train, y_train)<br /> y_pred = clf.'''predict'''(X_test)<br /> <br /> Кроме того, у этой функции так же присутствует гипперпараметры {{---}} '''регуляризация''' (англ. regularization), который отвечает за размер штрафа и гамма, которая отвечает за приближенность результирующей функций к датасету. Здесь нужно помнить, что при больших значениях гамма возможно [[Переобучение|переобучение]].<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> * [[Линейная регрессия]]<br /> * [[Логистическая регрессия]]<br /> * [[Регуляризация]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> #[https://www.datacamp.com/community/tutorials/svm-classification-scikit-learn-python#kernels datacamp.com — Support Vector Machines with Scikit-learn]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]<br /> [[Категория: Регрессия]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73211 2020-03-23T15:27:24Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов]].<br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов (локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторных представлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие, как строки, множества, картинки, тексты, графы, 3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие, как строки (число совместно встречающихся подстрок) или множества (напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах&lt;ref&gt;[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]&lt;/ref&gt;.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> <br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$&lt;ref&gt;https://en.wikipedia.org/wiki/Polynomial_kernel - Polynomial kernel&lt;/ref&gt;<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF (Radial basis function)&lt;ref&gt;[https://en.wikipedia.org/wiki/Radial_basis_function_kernel - RBF]&lt;/ref&gt; $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответствует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3. '''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличие от предыдущих 3-х не является ядром Мерсера (не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4. '''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> <br /> == Использование ядер в коде ==<br /> <br /> В библиотеке языка Python {{---}} sklearn.clustering&lt;ref&gt;https://scikit-learn.org/stable/modules/classes.html#module-sklearn.cluster - sklearn.cluster&lt;/ref&gt;, есть функции и классы которые используют ядра для кластеризации. <br /> <br /> * Подключаем библиотеки:<br /> '''import''' numpy '''as''' np<br /> '''from''' sklearn.datasets '''import''' make_blobs<br /> '''from''' sklearn.cluster '''import''' mean_shiftU<br /> <br /> * Генерируем данные:<br /> <br /> centers = [['''1''', '''1'''], ['''-1''', '''-1'''], ['''1''', '''-1''']]<br /> X, _ = make_blobs(n_samples='''10000''', centers=centers, cluster_std='''0.6''')<br /> <br /> * Посчтитаем кластеризацию с помощью MeanShift&lt;ref&gt;https://scikit-learn.org/stable/modules/generated/sklearn.cluster.MeanShift.html#sklearn.cluster.MeanShift - Meanshift documentaion&lt;/ref&gt;, находим разделяющуу полосу, добавляя в качестве первого парамента значение для пропускной способности ядра: <br /> <br /> bandwidth = estimate_bandwidth(X, quantile='''0.2''', n_samples='''500''')<br /> ms = MeanShift(bandwidth=bandwidth, bin_seeding='''True''')<br /> ms.'''fit'''(X)<br /> labels = ms.labels_<br /> cluster_centers = ms.cluster_centers_<br /> labels_unique = np.'''unique'''(labels)<br /> n_clusters_ = '''len'''(labels_unique)<br /> print(&quot;number of estimated clusters : %d&quot; % n_clusters_)<br /> <br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> * [[Линейная регрессия]]<br /> * [[Логистическая регрессия]]<br /> * [[Регуляризация]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]<br /> [[Категория: Регрессия]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73210 2020-03-23T15:23:00Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов]].<br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов (локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторных представлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие, как строки, множества, картинки, тексты, графы, 3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие, как строки (число совместно встречающихся подстрок) или множества (напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах&lt;ref&gt;[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]&lt;/ref&gt;.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> <br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$&lt;ref&gt;https://en.wikipedia.org/wiki/Polynomial_kernel - Polynomial kernel&lt;/ref&gt;<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF (Radial basis function)&lt;ref&gt;[https://en.wikipedia.org/wiki/Radial_basis_function_kernel - RBF]&lt;/ref&gt; $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответствует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3. '''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличие от предыдущих 3-х не является ядром Мерсера (не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4. '''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> <br /> == Использование ядер в коде ==<br /> <br /> В библиотеке языка Python {{---}} sklearn.clustering&lt;ref&gt;https://scikit-learn.org/stable/modules/classes.html#module-sklearn.cluster - sklearn.cluster&lt;/ref&gt;, есть функции и классы которые используют ядра для кластеризации. <br /> <br /> * Подключаем библиотеки:<br /> '''import''' numpy '''as''' np<br /> '''from''' sklearn.datasets '''import''' make_blobs<br /> '''from''' sklearn.cluster '''import''' mean_shiftU<br /> <br /> * Генерируем данные:<br /> <br /> centers = [['''1''', '''1'''], ['''-1''', '''-1'''], ['''1''', '''-1''']]<br /> X, _ = make_blobs(n_samples='''10000''', centers=centers, cluster_std='''0.6''')<br /> <br /> * Посчтитаем кластеризацию с помощью MeanShift&lt;ref&gt;https://scikit-learn.org/stable/modules/generated/sklearn.cluster.MeanShift.html#sklearn.cluster.MeanShift - Meanshift documentaion&lt;/ref&gt;, находим разделяющуу полосу, добавляя в качестве первого парамента значение для пропускной способности ядра: <br /> <br /> bandwidth = estimate_bandwidth(X, quantile='''0.2''', n_samples='''500''')<br /> ms = MeanShift(bandwidth=bandwidth, bin_seeding='''True''')<br /> ms.fit(X)<br /> labels = ms.labels_<br /> cluster_centers = ms.cluster_centers_<br /> labels_unique = np.unique(labels)<br /> n_clusters_ = '''len'''(labels_unique)<br /> print(&quot;number of estimated clusters : %d&quot; % n_clusters_)<br /> <br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> * [[Линейная регрессия]]<br /> * [[Логистическая регрессия]]<br /> * [[Регуляризация]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]<br /> [[Категория: Регрессия]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73200 2020-03-23T12:19:25Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов (локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторных представлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие, как строки, множества, картинки, тексты, графы, 3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие, как строки (число совместно встречающихся подстрок) или множества (напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах&lt;ref&gt;[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]&lt;/ref&gt;.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> <br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$&lt;ref&gt;https://en.wikipedia.org/wiki/Polynomial_kernel - Polynomial kernel&lt;/ref&gt;<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF (Radial basis function)&lt;ref&gt;[https://en.wikipedia.org/wiki/Radial_basis_function_kernel - RBF]&lt;/ref&gt; $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответствует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3. '''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличие от предыдущих 3-х не является ядром Мерсера (не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4. '''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> * [[Линейная регрессия]]<br /> * [[Логистическая регрессия]]<br /> * [[Регуляризация]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]<br /> [[Категория: Регрессия]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73199 2020-03-23T12:16:56Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов (локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторных представлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие, как строки, множества, картинки, тексты, графы, 3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие, как строки (число совместно встречающихся подстрок) или множества (напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах&lt;ref&gt;[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]&lt;/ref&gt;.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$&lt;ref&gt;https://en.wikipedia.org/wiki/Polynomial_kernel - Polynomial kernel&lt;/ref&gt;<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF (Radial basis function)&lt;ref&gt;[https://en.wikipedia.org/wiki/Radial_basis_function_kernel - RBF]&lt;/ref&gt; $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3. '''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличие от предыдущих 3-х не является ядром Мерсера (не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4. '''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> * [[Линейная регрессия]]<br /> * [[Логистическая регрессия]]<br /> * [[Регуляризация]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]<br /> [[Категория: Регрессия]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73198 2020-03-23T12:13:13Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов (локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторных представлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие, как строки, множества, картинки, тексты, графы, 3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие, как строки (число совместно встречающихся подстрок) или множества (напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах&lt;ref&gt;[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]&lt;/ref&gt;.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$&lt;ref&gt;https://en.wikipedia.org/wiki/Polynomial_kernel - Polynomial kernel&lt;/ref&gt;<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF (Radial basis function)&lt;ref&gt;[https://en.wikipedia.org/wiki/Radial_basis_function_kernel - RBF]&lt;/ref&gt; $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3. '''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера (не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4. '''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> * [[Линейная регрессия]]<br /> * [[Логистическая регрессия]]<br /> * [[Регуляризация]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]<br /> [[Категория: Регрессия]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73195 2020-03-23T11:30:23Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов(локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторныхпредставлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие как строки, множества, картинки, тексты, графы,3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие как строки(число совместно встречающихся подстрок) или множества(напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3. '''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера(не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4. '''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73194 2020-03-23T11:29:39Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов(локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторныхпредставлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие как строки, множества, картинки, тексты, графы,3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие как строки(число совместно встречающихся подстрок) или множества(напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве $y$ выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF $K(x, x') = exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3.'''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера(не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4.'''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73193 2020-03-23T11:28:39Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов(локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторныхпредставлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие как строки, множества, картинки, тексты, графы,3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие как строки(число совместно встречающихся подстрок) или множества(напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1. Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ {{---}} функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3.'''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера(не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4.'''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73192 2020-03-23T11:26:58Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов(локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторныхпредставлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений размерностей.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра {{---}} признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие как строки, множества, картинки, тексты, графы,3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие как строки(число совместно встречающихся подстрок) или множества(напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ - функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3.'''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера(не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4.'''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73191 2020-03-23T11:01:14Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': На первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов(локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторныхпредставлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений D.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра - признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие как строки, множества, картинки, тексты, графы,3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие как строки(число совместно встречающихся подстрок) или множества(напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ - функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3.'''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера(не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4.'''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73190 2020-03-23T11:00:10Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': на первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом[[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> * Обобщение линейных методов на нелинейный случай:<br /> <br /> а) с сохранением вычислительной эффективности линейных методов.<br /> <br /> б) с сохранением преимуществ линейных методов(локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение).<br /> <br /> * Объекты для которых не существует векторныхпредставлений фиксированной длины.<br /> <br /> * Ускоренное вычисление скалярных произведений для высоких значений D.<br /> <br /> '''Недостатки'''<br /> <br /> * Вычислительно сложно проверять принадлежность функции ядру.<br /> <br /> * Поиск подходящего ядра экспоненциально сложен из-за их большого многообразия.<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности.<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра - признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины.<br /> <br /> Такие как строки, множества, картинки, тексты, графы,3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения.<br /> <br /> Такие как строки(число совместно встречающихся подстрок) или множества(напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно.<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ - функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3.'''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера(не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4.'''Строковое'''<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73169 2020-03-23T00:02:21Z

<p>256331: </p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк''' (англ. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> '''Пример''': на первой картинке справа можно увидеть, что 2 класса не разделимы линейно, но после преобразования появляется разделяющая плоскость.<br /> <br /> <br /> == Описание ==<br /> {{Определение<br /> |definition=<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''' (англ. kernel), если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$, где $H$ {{---}} пространство со скалярным произведением.<br /> }}<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом [[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> *обобщение линейных методов на нелинейный случай<br /> <br /> а)с сохранением вычислительной эффективности линейных методов<br /> <br /> б)с сохранением преимуществ линейных методов(локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение)<br /> <br /> *объекты для которых не существует векторныхпредставлений фиксированной длины<br /> <br /> *ускоренное вычисление скалярных произведений для высоких значений D<br /> <br /> '''Недостатки'''<br /> <br /> *вычислительно сложно проверять принадлежность функции ядру<br /> <br /> *поиск подходящего ядра экспоненциально сложен из-за их большого многообразия<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности<br /> <br /> Например все полиномы до степени $M$, для случая Гаусовского ядра - признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины<br /> <br /> Такие как строки, множества, картинки, тексты, графы,3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения<br /> <br /> Такие как строки(число совместно встречающихся подстрок) или множества(напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$).<br /> <br /> * Скалярное произведение может быть подсчитано эффективно<br /> <br /> == Выбор функции ядра ==<br /> {{Теорема<br /> |id=merser<br /> |author=Мерсера<br /> |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$ <br /> |proof = <br /> }}<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ - функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' (англ. linear) $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' (англ. polynomial) $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' (англ. gaussian) ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3.'''Сигмоидальное''' (англ. sigmoid) ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера(не выполняет условие теоремы), но при этом на практике работает хорошо.<br /> <br /> 4.'''Строковое''' ядро<br /> <br /> Строковые ядра &lt;ref&gt;[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 - Строковое ядро]&lt;/ref&gt; это различные ядерные функции для вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Kernel2_3.png&diff=73168 2020-03-22T23:25:14Z

<p>256331: Точки в двухмерном пространстве линейно не разделимы. Но при переходе в трёхмерное появляется разделяющая плоскость.</p> <hr /> <div>Точки в двухмерном пространстве линейно не разделимы. Но при переходе в трёхмерное появляется разделяющая плоскость.</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73167 2020-03-22T23:23:57Z

<p>256331: Добавлено 2 пунткта, изменена картинка</p> <hr /> <div>[[File:kernel2_3.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк'''(анг.-- ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> <br /> == Определение ==<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''', если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$,где $H$ {{---}} пространство со скалярным произведением.<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом [[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> <br /> == Преимущества и недостатки ==<br /> <br /> '''Преимущества'''<br /> <br /> *обобщение линейных методов на нелинейный случай<br /> <br /> ** с сохранением вычислительной эффективности линейных методов<br /> <br /> **с сохранением преимуществ линейных методов(локальный оптимум является глобальным, нет локальных оптимумов=&gt;меньше переобучение)<br /> <br /> *объекты для которых не существует векторныхпредставлений фиксированной длины<br /> <br /> *ускоренное вычисление скалярных произведений для высоких значений D<br /> <br /> '''Недостатки'''<br /> <br /> *вычислительно сложно проверять принадлежность функции ядру<br /> <br /> *поиск подходящего ядра экспоненциально сложен из-за их большого многообразия<br /> <br /> == Характерные случаи применения ==<br /> * Признаковое пространство высокой размерности<br /> <br /> Например все полиномы до степени M, для случая Гаусовского ядра - признаковое пространство бесконечной размерности.<br /> <br /> * Случай, когда сложно представить объекты векторами фиксированной длины<br /> <br /> Такие как строки, множества, картинки, тексты, графы,3D-структуры и т.д.<br /> <br /> * Существование естественного определения скалярного произведения<br /> <br /> Такие как строки(число совместно встречающихся подстрок) или множества(напр. для множеств $S_1$ и $S_2$ ядром будет являться $K(S_1, S_2) = 2^{|S_1\cap S_2|}$)<br /> <br /> * Скалярное произведение может быть подсчитано эффективно<br /> <br /> == Выбор функции ядра ==<br /> '''Теорема Мерсера''': Функция $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$<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ - функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые ядра ==<br /> <br /> 0. '''Линейное''' $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' ядро $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> 3.'''Сигмоидальное''' ядро $tangh (\gamma \langle x, x'\rangle + r)$ <br /> <br /> В отличии от предыдущих 3-х не является ядром Мерсера.<br /> <br /> 4.'''Строковое''' ядро<br /> <br /> &lt;ref&gt;[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 - Строковые ядра]&lt;/ref&gt; это разлиные вариации вычисления расстояний между двумя строками.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> #[http://www.machinelearning.ru/wiki/images/7/78/Kitov-ML-09-Kernel_methods.pdf www.machinelearning.ru — Виктор Китов Ядерные методы]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73144 2020-03-22T21:05:19Z

<p>256331: Исправлены опечатки</p> <hr /> <div>[[File:kernel3_2.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк'''(анг.-- ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> <br /> == Определение ==<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''', если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$,где $H$ {{---}} пространство со скалярным произведением.<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$. Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта информация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом [[Метод опорных векторов (SVM) | опорных векторов ]].<br /> <br /> == Выбор функции ядра ==<br /> '''Теорема Мерсера''': Функция $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$<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая (обычно по критерию скользящего контроля). Такое решение не будет оптимальным, и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ где $z$ - функция ядра {{---}} являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые функции ==<br /> <br /> 0. '''Линейное''' $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1. '''Полиномиальное''' ядро $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2. '''Гаусово''' ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73082 2020-03-22T00:53:42Z

<p>256331: Добавлено описание ядер, подредактированы формулы</p> <hr /> <div>[[File:kernel3_2.png|500px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк'''(анг. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> <br /> == Определение ==<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''', если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$,где H {{---}} пространство со скалярным произведением.<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$ Более того, можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объектов. Во многих практических задачах объекты изначально задаются информацией об их попарном взаимоотношении, например, отношении сходства. Если эта инфор-мация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяющей аксиомам скалярного произведения, то задача может решаться методом [[Метод опорных векторов (SVM) | SVM ]].<br /> <br /> == Выбор функции ядра ==<br /> '''Теорема Мерсера''': Функция 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$<br /> <br /> Таким образом мы видим, что класс ядер достаточно широк.<br /> <br /> Проверка неотрицательной определённости функции в реальных задачах может быть сложной. Чаще всего ограничиваются перебором конечного числа функций, про которые известно, что они являются ядрами. Среди них выбирается лучшая(обычно по критерию скользящего контроля). Такое решение не будет оптимальным и на сегодняшний день проблема выбора ядра, оптимального для данной конкретной задачи, остаётся открытой.<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение $K(x,x′) =\psi(x)\psi(x')${{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами $K(x,x')=\alpha_1K_1(x,x') +\alpha_2K_2(x,x')$является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядра $K_0$ является ядром: $K(x,x')=K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Если $s:X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int_Xs(x,z)s(x',z)dz$ является ядром.<br /> <br /> 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$ неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 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}$ от ядра являются ядрами.<br /> <br /> <br /> == Некоторые часто используемые функции ==<br /> <br /> 0.Линейное $K(x, x')= \langle x, x'\rangle$<br /> Используется в алгоритме [[Метод опорных векторов (SVM) | SVM ]] по умолчанию.<br /> <br /> 1.Полиномиальное ядро $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> Используется когда необходимо получить полином $p(y)$, где в качестве y выступает скалярное произведение $\langle x, x' \rangle$. Поскольку в конструктивных возможностях у нас есть умножение ядер, умножение на коэффициент и сложение, то любой многочлен так же является ядром.<br /> <br /> 2.Гаусово ядро RBF K(x, x') = $exp(-\frac{\parallel x - x'\parallel^2}{2\sigma^2})$<br /> <br /> Такое ядро соответсвует бесконечномерному пространству. Поскольку оно является пределом последовательности полиномиальных ядер при стремлении степени ядра к бесконечности.<br /> <br /> == См. также ==<br /> * [[Метод опорных векторов (SVM)]]<br /> <br /> == Примечания ==<br /> &lt;references/&gt;<br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> #[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem12_linear.pdf github.com/esokolov/ml-course-msu — Евгений Соколов Ядра и их применение в машинном обучении]<br /> #[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 — Ядерный метод]<br /> <br /> [[Категория: Машинное обучение]]<br /> [[Категория: Классификация]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Kernel3_2.png&diff=73081 2020-03-21T23:41:44Z

<p>256331: В правом пространстве объекты внутри овала линейно не отделимы от наружних. После применения ядра слева появляется разделяющая плоскость.</p> <hr /> <div>В правом пространстве объекты внутри овала линейно не отделимы от наружних. После применения ядра слева появляется разделяющая плоскость.</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73080 2020-03-21T23:38:58Z

<p>256331: </p> <hr /> <div>[[File:kernel3_2.png|600px|thumb|right|Пример использования ядерного трюка]]<br /> '''Ядерный трюк'''(анг. ''kernel function'') метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство пространство. Такое пространство называют '''спрямляющим'''. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.<br /> <br /> <br /> == Определение ==<br /> Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется '''ядром''', если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$,где H {{---}} пространство со скалярным произведением.<br /> <br /> Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$ Более того, можно вообще не строить спрямляющее пространствоHв явномвиде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.<br /> <br /> Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объек-тов. Во многих практических задачах объекты изначально задаются информациейоб их попарном взаимоотношении, например, отношении сходства. Если эта инфор-мация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяю-щей аксиомам скалярного произведения, то задача может решаться методом [[Метод опорных векторов (SVM) | SVM ]].<br /> <br /> == Теорема Мерсера ==<br /> Функция K(x,y) является ядром тогда и только тогда, когда:<br /> <br /> Она симметрична: $K(x,y)=K(y,x)$<br /> <br /> Она неотрицательно определена, то есть $\forall g: X \rightarrow \mathbb{R}, \int_X \int_X K(x, x')g(x)g(x')dxdx' \geqslant 0$<br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.<br /> <br /> 2. Константа $K(x,x') = 1$ является ядром.<br /> <br /> 3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.<br /> <br /> 4. Для любой функции $\psi :X\rightarrow R$ произведение &lt;tex&gt;K(x,x′) =\psi(x)\psi(x′)&lt;/tex&gt;{{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентами K(x,x′) ==\alpha_1K_1(x,x') +\alpha_2K_2(x,x')является ядром.<br /> <br /> 6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядраK0является ядром: $K(x,x') =K_0(\varphi(x),\varphi(x'))$.<br /> <br /> 7. Еслиs:$X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int Xs(x,z)s(x',z)$dzявляется ядром.//TODO<br /> <br /> 8. Функция вида K(x,x') = k(x−x)является ядром тогда и только тогда, когдаФурье-образ F[k](\omega) = (2\Pi)n_2∫Xe−i〈\owmega,x〉k(x)dx неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 10. Композиция произвольного ядраK0и произвольной функции ''f'':R\rightarrow R, представимой в виде сходящегося степенного ряда с неотрицательными коэффициентами $K(x,x') = f(K_0(x,x'))$, является ядром. В частности, функции $f(z) =e^z$ и f(z) =1/{1−z} от ядра являются ядрами.<br /> <br /> <br /> == Ядерный трюк ==<br /> Поскольку для обучения зачастую необходима уже функция &quot;расстояния&quot; между элементами в новом пространстве, то вместо явного нахождения ядра {{---}} его можно зашить внутрь соответсвующей функции k(x, x'). Такую функцию k называют '''ядерной функцией'''<br /> <br /> <br /> == Некоторые часто используемые функции ==<br /> 0.Линейное $K(x, x')= \langle x, x'\rangle$<br /> <br /> 1.Полиномиальное ядро $K(x, x') = (\langle x, x' \rangle + R)^d$<br /> <br /> 2.Гаусово ядро RBF K(x, x') = exp(-\gamma ||x - x'||^2)<br /> <br /> <br /> <br /> == Источники информации ==<br /> <br /> #[http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам]<br /> <br /> [[Категория: Машинное обучение]]</div>

256331 http://neerc.ifmo.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE&diff=73055 2020-03-21T16:33:45Z

<p>256331: Новая страница: «'''Ядро(Kernel) в машинном обучении''' - функция x-&gt;\fi(x), которая позволяет совершить преобразов…»</p> <hr /> <div>'''Ядро(Kernel) в машинном обучении''' - функция x-&gt;\fi(x), которая позволяет совершить преобразование признаков и получить линейно разделимое пространство.<br /> <br /> <br /> == Определение ==<br /> Функция K(x,x′):X×X-&gt;R называется ядром, если она может быть представлена в виде K(x,x')=&lt;\fi(x),\fi(x')&gt;_H для какой либо функции \fi(x):X-&gt;H.<br /> <br /> <br /> == Теорема Мерсера ==<br /> Функция K(x,y) является ядром тогда и только тогда, когда:<br /> <br /> Она симметрична: K(x,y)=K(y,x)<br /> <br /> Она неотрицательно определена, то есть для любой конечной выборки матрица K=(K(x_i,x_j))^l_{i,j=1} неотрицательно определена <br /> <br /> == Конструктивные способы построения ядер ==<br /> 1.Произвольное скалярное произведениеK(x,x') =&lt;x,x'&gt;является ядром.<br /> <br /> 2. КонстантаK(x,x') = 1 является ядром.<br /> <br /> 3. Произведение ядер &lt;tex&gt;K(x,x') =K_1(x,x')K_2(x,x')&lt;tex&gt;является ядром.<br /> <br /> 4. Для любой функции &lt;tex&gt;\psi :X-&gt;R&lt;tex&gt; произведение &lt;tex&gt;K(x,x′) =\psi(x)\psi(x′)&lt;tex&gt;{{---}} ядро.<br /> <br /> 5. Линейная комбинация ядер с неотрицательными коэффициентамиK(x,x′) ==\alpha_1K_1(x,x') +\alpha_2K_2(x,x')является ядром.<br /> <br /> 6. Композиция произвольной функции \fi:X-&gt;X и произвольного ядраK0является ядром: K(x,x') =K_0(\fi(x),\fi(x')).<br /> <br /> 7. Еслиs:X×X→R произвольная симметричная интегрируемая функция, тоK(x,x′) =∫Xs(x,z)s(x′,z)dzявляется ядром.//TODO<br /> <br /> 8. Функция вида K(x,x') = k(x−x)является ядром тогда и только тогда, когдаФурье-образ F[k](\omega) = (2\Pi)n_2∫Xe−i〈\owmega,x〉k(x)dx неотрицателен.<br /> <br /> 9. Предел локально-равномерно сходящейся последовательности ядер {{---}} ядро.<br /> <br /> 10. Композиция произвольного ядраK0и произвольной функции ''f'':R-&gt;R, представимой в виде сходящегося степенного ряда с неотрицательными коэффици-ентамиK(x,x') =f(K_0(x,x')), является ядром. В частности, функцииf(z) =e^z и f(z) =1/{1−z} от ядра являются ядрами<br /> <br /> <br /> == Ядерный трюк ==<br /> Поскольку для обучения зачастую необходима уже функция &quot;расстояния&quot; между элементами в новом пространстве, то вместо явного нахождения ядра {{---}} его можно зашить внутрь соответсвующей функции k(x, x'). Такую функцию k называют '''ядерной функцией'''<br /> <br /> <br /> == Некоторые часто используемые функции ==<br /> 0.Линейное K(x, x')=&lt;x, x'&gt;<br /> <br /> 1.Полиномиальное ядро K(x, x') = (&lt;x, x'&gt; + R)^d<br /> <br /> 2.Гаусово ядро RBF K(x, x') = exp(-\gamma ||x - x'||^2)</div>

256331