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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Теорема Мерсера)
 
(9 промежуточных версий не показаны.)
Строка 4: Строка 4:
==Историческая справка==
==Историческая справка==
-
Теорема была опубликована английским математиком Джеймсом Мерсером (1883 - 1932) в статье "Functions of Positive and Negative Type and their Connection with the Theory of Integral Equations" в научном журнале ''The Royal Society'' в 1909 году. Доказанная теорема явилась основой для перехода в [[спрямляющее пространство]], примененного впервые Айзерманом.
+
Теорема была опубликована английским математиком Джеймсом Мерсером (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>$\<x,x'\>$</tex>, а не от признаковых описаний объектов непосредственно. Значит, скалярное произведение можно всюду заменить [[Функция ядра|функцией ядра]] <tex>$K\(x,x'\)$</tex>. Таким образом происходит переход в [[спрямляющее пространство]]&nbsp;(Kernel trick). Если изначально выборка была линейно неразделимой, то при удачном выборе [[Функция ядра|ядра]] возможно избавиться от этой проблемы. Это, в свою очередь, позволяет применять линейные алгоритмы классификации ([[SVM]], в частности) в случаях, когда выборка не является линейно разделимой. А '''теорема Мерсера''' является критерием [[Функция ядра|функции ядра]].
==Теорема Мерсера==
==Теорема Мерсера==
Функция двух переменных <tex>$K\(x,x'\)$</tex> является [[Функция ядра|ядром]] тогда и только тогда, когда она
Функция двух переменных <tex>$K\(x,x'\)$</tex> является [[Функция ядра|ядром]] тогда и только тогда, когда она
*симметрична, то есть <tex>$K\(x,x'\) = 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>\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>$\left{x_1 ... x_n\right}$</tex> матрица
Строка 21: Строка 21:
.\\
.\\
.
.
-
\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><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
Строка 29: Строка 30:
==Ссылки==
==Ссылки==
*[http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf]
*[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]
*[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'\)$ часто является нелегкой задачей.

Литература

Ссылки

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