Теорема Мерсера
Материал из MachineLearning.
(→Теорема Мерсера) |
|||
| (9 промежуточных версий не показаны.) | |||
| Строка 4: | Строка 4: | ||
==Историческая справка== | ==Историческая справка== | ||
| - | Теорема была опубликована английским математиком Джеймсом Мерсером (1883 | + | Теорема была опубликована английским математиком Джеймсом Мерсером (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>$\<x,x'\>$</tex>, а не от признаковых описаний объектов непосредственно. Значит, скалярное произведение можно всюду заменить [[Функция ядра|функцией ядра]] <tex>$K\(x,x'\)$</tex>. Таким образом происходит переход в [[спрямляющее пространство]] (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] | ||
| + | |||
| + | [[Категория:Функциональный анализ]] | ||
| + | [[Категория:Линейные классификаторы]] | ||
Текущая версия
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта 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
- К.В. Воронцов, Машинное обучение (курс лекций)
