Теорема Мерсера

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Теорема Мерсера)
Строка 23: Строка 23:
\end{array}\right]$</tex> должна быть неотрицательно определенной, то есть <tex>$z^TKz \geq 0, \forall z \in R^n$</tex>.<br>
\end{array}\right]$</tex> должна быть неотрицательно определенной, то есть <tex>$z^TKz \geq 0, \forall z \in R^n$</tex>.<br>
Нужно отметить, что на практике проверка неотрицательной определенности функции <tex>$K\(x,x'\)$</tex> часто является нелегкой задачей.
Нужно отметить, что на практике проверка неотрицательной определенности функции <tex>$K\(x,x'\)$</tex> часто является нелегкой задачей.
 +
==Литература==
==Литература==
*''J. Mercer'', [http://rsta.royalsocietypublishing.org/content/209/441-458/415.full.pdf Functions of positive and negative type and their connection with the theory of integral equations], Philos. Trans. Roy. Soc. London 1909
*''J. Mercer'', [http://rsta.royalsocietypublishing.org/content/209/441-458/415.full.pdf Functions of positive and negative type and their connection with the theory of integral equations], Philos. Trans. Roy. Soc. London 1909

Версия 16:24, 4 января 2010

Данная статья является непроверенным учебным заданием.
Студент: Участник:Михаил
Преподаватель: Участник:Константин Воронцов
Срок: 7 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Теорема Мерсера определяет необходимые и достаточные условия, которыми должна обладать функция K\(x,x'\) для того, чтобы являться ядром.

Содержание

Историческая справка

Теорема была опубликована английским математиком Джеймсом Мерсером (1883 - 1932) в статье "Functions of Positive and Negative Type and their Connection with the Theory of Integral Equations" в научном журнале The Royal Society в 1909 году. Доказанная теорема явилась основой для перехода в спрямляющее пространство, примененного впервые Айзерманом.

Переход в спрямляющее пространство

Линейные алгоритмы классификации зависят только от скалярных произведений $\<x,x'\>$, а не от признаковых описаний объектов непосредственно. Значит, скалярное произведение можно всюду заменить функцией ядра $K\(x,x'\)$. Таким образом происходит переход в спрямляющее пространство (Kernel trick). Если изначально выборка была линейно неразделимой, то при удачном выборе ядра возможно избавиться от этой проблемы. Это, в свою очередь, позволяет применять линейные алгоритмы классификации (SVM, в частности) в случаях, когда выборка не является линейно разделимой.

Теорема Мерсера

Функция двух переменных $K\(x,x'\)$ является ядром тогда и только тогда, когда она

  • симметрична, то есть $K\(x,x'\) = K\(x',x\)$;
  • неотрицательно определена, то есть \int_X\int_X K\(x,x'\)g\(x\)g\(x'\)dxdx' \geq 0.

Последнее условие можно заменить эквивалентным: для произвольных наборов $\left{x_1 ... x_n\right}$ матрица $K = \left[\begin{array}{cccc}
K\(x_1,x_1\) & K\(x_1,x_2\) & . & . & .\\
K\(x_2,x_1\)\\
.\\
.\\
.
\end{array}\right]$ должна быть неотрицательно определенной, то есть $z^TKz \geq 0, \forall z \in R^n$.
Нужно отметить, что на практике проверка неотрицательной определенности функции $K\(x,x'\)$ часто является нелегкой задачей.

Литература

Ссылки

Личные инструменты