Теорема Мерсера
Материал из MachineLearning.
| Строка 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>. Таким образом происходит переход в [[спрямляющее пространство]] (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>$\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> | ||
| + | Нужно отметить, что на практике проверка неотрицательной определенности функции <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] | ||
Версия 16:00, 4 января 2010
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Теорема Мерсера определяет необходимые и достаточные условия, которыми должна обладать функция
для того, чтобы являться ядром.
Содержание[убрать] |
Историческая справка
Теорема была опубликована английским математиком Джеймсом Мерсером (1883 - 1932) в статье "Functions of Positive and Negative Type and their Connection with the Theory of Integral Equations" в научном журнале The Royal Society в 1909 году. Доказанная теорема явилась основой для перехода в спрямляющее пространство, примененного впервые Айзерманом.
Переход в спрямляющее пространство
Линейные алгоритмы классификации зависят только от скалярных произведений , а не от признаковых описаний объектов непосредственно. Значит, скалярное произведение можно всюду заменить функцией ядра
. Таким образом происходит переход в спрямляющее пространство (Kernel trick). Если изначально выборка была линейно неразделимой, то при удачном выборе ядра возможно избавиться от этой проблемы. Это, в свою очередь, позволяет применять линейные алгоритмы классификации (SVM, в частности) в случаях, когда выборка не является линейно разделимой.
Теорема Мерсера
Функция двух переменных является ядром тогда и только тогда, когда она
- симметрична, то есть
;
- неотрицательно определена, то есть
.
Последнее условие можно заменить эквивалентным: для произвольных наборов матрица
должна быть неотрицательно определенной, то есть
.
Нужно отметить, что на практике проверка неотрицательной определенности функции часто является нелегкой задачей.
Литература
- J. Mercer, 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
- К.В. Воронцов, Машинное обучение (курс лекций)
