Теорема Мерсера
Материал из MachineLearning.
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта 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
- К.В. Воронцов, Машинное обучение (курс лекций)
