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

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

Данная статья является непроверенным учебным заданием.

Преподаватель: Участник:Константин Воронцов

Срок: 7 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Теорема Мерсера определяет необходимые и достаточные условия, которыми должна обладать функция $K$x,x'$$ для того, чтобы являться ядром.

Историческая справка

Теорема была опубликована английским математиком Джеймсом Мерсером (1883 — 1932) в статье «Functions of Positive and Negative Type and their Connection with the Theory of Integral Equations» в научном журнале The Royal Society в 1909 году. Доказанная теорема явилась основой для перехода в спрямляющее пространство, примененного впервые Айзерманом.

Переход в спрямляющее пространство

Линейные алгоритмы классификации зависят только от скалярных произведений $\<x,x'\>$ , а не от признаковых описаний объектов непосредственно. Значит, скалярное произведение можно всюду заменить функцией ядра $K$x,x'$$ . Таким образом происходит переход в спрямляющее пространство (Kernel trick). Если изначально выборка была линейно неразделимой, то при удачном выборе ядра возможно избавиться от этой проблемы. Это, в свою очередь, позволяет применять линейные алгоритмы классификации (SVM, в частности) в случаях, когда выборка не является линейно разделимой. А теорема Мерсера является критерием функции ядра.

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

Функция двух переменных $K$x,x'$$ является ядром тогда и только тогда, когда она

симметрична, то есть $K$x,x'$ = K$x',x$$ ;
неотрицательно определена, то есть $\int_X\int_X K$x,x'$g$x$g$x'$dxdx' \geq 0$ для любой функции $g: \ X \to \mathbb{R}$ ;

Последнее условие можно заменить эквивалентным: для произвольных наборов $\left{x_1 ... x_n\right}$ матрица $K = \left[\begin{array}{cccc} K$x_1,x_1$ & K$x_1,x_2$ & . & . & .\\ K$x_2,x_1$\\ .\\ .\\ . \end{array}\right]$ должна быть неотрицательно определенной, то есть $z^TKz \geq 0, \forall z \in R^n$ .

Нужно отметить, что на практике проверка неотрицательной определенности функции $K$x,x'$$ часто является нелегкой задачей.