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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Теорема Мерсера)
 
(13 промежуточных версий не показаны.)
Строка 1: Строка 1:
{{Задание|Михаил|Константин Воронцов|7 января 2010}}
{{Задание|Михаил|Константин Воронцов|7 января 2010}}
 +
'''Теорема Мерсера''' определяет необходимые и достаточные условия, которыми должна обладать функция
 +
<tex>K\(x,x'\)</tex> для того, чтобы являться [[Функция ядра|ядром]].
 +
 +
==Историческая справка==
 +
Теорема была опубликована английским математиком Джеймсом Мерсером (1883 — 1932) в статье «Functions of Positive and Negative Type and their Connection with the Theory of Integral Equations» в научном журнале ''The Royal Society'' в 1909 году. Доказанная теорема явилась основой для перехода в [[спрямляющее пространство]], примененного впервые Айзерманом.
 +
 +
==Переход в спрямляющее пространство==
 +
Линейные алгоритмы классификации зависят только от скалярных произведений <tex>$\<x,x'\>$</tex>, а не от признаковых описаний объектов непосредственно. Значит, скалярное произведение можно всюду заменить [[Функция ядра|функцией ядра]] <tex>$K\(x,x'\)$</tex>. Таким образом происходит переход в [[спрямляющее пространство]]&nbsp;(Kernel trick). Если изначально выборка была линейно неразделимой, то при удачном выборе [[Функция ядра|ядра]] возможно избавиться от этой проблемы. Это, в свою очередь, позволяет применять линейные алгоритмы классификации ([[SVM]], в частности) в случаях, когда выборка не является линейно разделимой. А '''теорема Мерсера''' является критерием [[Функция ядра|функции ядра]].
 +
 +
==Теорема Мерсера==
 +
Функция двух переменных <tex>$K\(x,x'\)$</tex> является [[Функция ядра|ядром]] тогда и только тогда, когда она
 +
*симметрична, то есть <tex>$K\(x,x'\) = K\(x',x\)$</tex>;
 +
*неотрицательно определена, то есть <tex>\int_X\int_X K\(x,x'\)g\(x\)g\(x'\)dxdx' \geq 0</tex> для любой функции <tex>g: \ X \to \mathbb{R}</tex>;
 +
 +
Последнее условие можно заменить эквивалентным: для произвольных наборов <tex>$\left{x_1 ... x_n\right}$</tex> матрица
 +
<tex>$K = \left[\begin{array}{cccc}
 +
K\(x_1,x_1\) & K\(x_1,x_2\) & . & . & .\\
 +
K\(x_2,x_1\)\\
 +
.\\
 +
.\\
 +
.
 +
\end{array}\right]$</tex> должна быть неотрицательно определенной, то есть <tex>$z^TKz \geq 0, \forall z \in R^n$</tex>.<br><br>
 +
Нужно отметить, что на практике проверка неотрицательной определенности функции <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. Suykens'', A short Introduction to Support Vector Machines and Kernelbased Learning, 2003
 +
*''К.В. Воронцов'', [[Машинное обучение (курс лекций, К.В.Воронцов)|Машинное обучение (курс лекций)]]
 +
==Ссылки==
 +
*[http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf]
 +
*[http://en.wikipedia.org/wiki/Mercer%27s_theorem en.wikipedia.org/wiki/Mercer%27s_theorem]
 +
 +
[[Категория:Функциональный анализ]]
 +
[[Категория:Линейные классификаторы]]

Текущая версия

Данная статья является непроверенным учебным заданием.
Студент: Участник:Михаил
Преподаватель: Участник:Константин Воронцов
Срок: 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 для любой функции g: \ X \to \mathbb{R};

Последнее условие можно заменить эквивалентным: для произвольных наборов $\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'\)$ часто является нелегкой задачей.

Литература

Ссылки

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