Теорема Мерсера
Материал из 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
- К.В. Воронцов, Машинное обучение (курс лекций)