Теорема Мерсера
Материал из MachineLearning.
(→Теорема Мерсера) |
|||
(2 промежуточные версии не показаны) | |||
Строка 4: | Строка 4: | ||
==Историческая справка== | ==Историческая справка== | ||
- | Теорема была опубликована английским математиком Джеймсом Мерсером (1883 — 1932) в статье | + | Теорема была опубликована английским математиком Джеймсом Мерсером (1883 — 1932) в статье «Functions of Positive and Negative Type and their Connection with the Theory of Integral Equations» в научном журнале ''The Royal Society'' в 1909 году. Доказанная теорема явилась основой для перехода в [[спрямляющее пространство]], примененного впервые Айзерманом. |
==Переход в спрямляющее пространство== | ==Переход в спрямляющее пространство== | ||
Строка 12: | Строка 12: | ||
Функция двух переменных <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> матрица | ||
Строка 30: | Строка 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] | ||
+ | |||
+ | [[Категория:Функциональный анализ]] | ||
+ | [[Категория:Линейные классификаторы]] |
Текущая версия
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта 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
- К.В. Воронцов, Машинное обучение (курс лекций)