Теорема Мерсера
Материал из MachineLearning.
(→Теорема Мерсера) |
|||
| Строка 23: | Строка 23: | ||
\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> | ||
Нужно отметить, что на практике проверка неотрицательной определенности функции <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 | ||
Версия 16:24, 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
- К.В. Воронцов, Машинное обучение (курс лекций)
