Теорема Мерсера

Материал из MachineLearning.

Версия 23:29, 9 января 2010

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

Ссылки

• www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf
• en.wikipedia.org/wiki/Mercer%27s_theorem