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

Материал из 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'\)$ часто является нелегкой задачей.

Литература

Ссылки

Личные инструменты