Представление теоремы

В информатике , в статистической теории обучения , теорема о представителе — это любой из нескольких связанных между собой результатов, утверждающих, что минимизатор $f^{*}$ регуляризованного эмпирического функционала риска, определенного в воспроизводящем ядерном гильбертовом пространстве, можно представить как конечную линейную комбинацию ядерных произведений, оцененных по входным точкам в данных обучающего набора.

Официальное заявление

Следующая теорема о представителе и ее доказательство принадлежат Шёлкопфу , Хербриху и Смоле:

Теорема: рассмотрим положительно определенное вещественное ядро. $k:{\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$ на непустом множестве ${\mathcal {X}}$ с соответствующим воспроизводящим ядром гильбертова пространства $H_{k}$. Пусть будет дано

• обучающая выборка $(x_{1},y_{1}),\dotsc ,(x_{n},y_{n})\in {\mathcal {X}}\times \mathbb {R}$,
• строго возрастающая действительная функция $g\colon [0,\infty )\to \mathbb {R}$, и
• произвольная функция ошибок $E\colon ({\mathcal {X}}\times \mathbb {R} ^{2})^{n}\to \mathbb {R} \cup \lbrace \infty \rbrace$,

которые вместе определяют следующий регуляризованный эмпирический функционал риска по $H_{k}$:

$f\mapsto E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+g\left(\lVert f\rVert \right).$

Тогда любой минимизатор эмпирического риска

$f^{*}={\underset {f\in H_{k}}{\operatorname {argmin} }}\left\lbrace E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+g\left(\lVert f\rVert \right)\right\rbrace ,\quad (*)$

допускает представление вида:

$f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),$

где $\alpha _{i}\in \mathbb {R}$ для всех $1\leq i\leq n$.

Доказательство: Определить сопоставление

${\begin{aligned}\varphi \colon {\mathcal {X}}&\to H_{k}\\\varphi (x)&=k(\cdot ,x)\end{aligned}}$

(так что $\varphi (x)=k(\cdot ,x)$ это сама карта ${\mathcal {X}}\to \mathbb {R}$). С $k$ является воспроизводящим ядром, то

$\varphi (x)(x')=k(x',x)=\langle \varphi (x'),\varphi (x)\rangle ,$

где $\langle \cdot ,\cdot \rangle$ является внутренним продуктом на $H_{k}$.

Учитывая любой $x_{1},\ldots ,x_{n}$, можно использовать ортогональную проекцию для разложения любого $f\in H_{k}$ в сумму двух функций, одна из которых лежит в $\operatorname {span} \left\lbrace \varphi (x_{1}),\ldots ,\varphi (x_{n})\right\rbrace$, а другой лежит в ортогональном дополнении:

$f=\sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v,$

где $\langle v,\varphi (x_{i})\rangle =0$ для всех $i$.

Вышеупомянутое ортогональное разложение и свойство воспроизведения вместе показывают, что применение $f$ в любой пункт обучения $x_{j}$ производит

$f(x_{j})=\left\langle \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v,\varphi (x_{j})\right\rangle =\sum _{i=1}^{n}\alpha _{i}\langle \varphi (x_{i}),\varphi (x_{j})\rangle ,$

которое мы наблюдаем, не зависит от $v$. Следовательно, значение функции ошибок $E$ в (*) также не зависит от $v$. Для второго члена (члена регуляризации), поскольку $v$ ортогонален $\sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})$ и $g$ строго монотонно, имеем

${\begin{aligned}g\left(\lVert f\rVert \right)&=g\left(\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v\rVert \right)\\&=g\left({\sqrt {\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})\rVert ^{2}+\lVert v\rVert ^{2}}}\right)\\&\geq g\left(\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})\rVert \right).\end{aligned}}$

Поэтому установка $v=0$ не влияет на первый член (*), но строго уменьшает второй член. Следовательно, любой минимизатор $f^{*}$ в (*) должно быть $v=0$, т. е. оно должно иметь вид

$f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),$

что является желаемым результатом.

Обобщения

Изложенная выше теорема является частным примером семейства результатов, которые вместе называются «теоремами о представителях»; здесь мы опишем несколько таких.

Первое утверждение теоремы о представителе принадлежит Кимельдорфу и Вахбе для особого случая, когда

${\begin{aligned}E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)&={\frac {1}{n}}\sum _{i=1}^{n}(f(x_{i})-y_{i})^{2},\\g(\lVert f\rVert )&=\lambda \lVert f\rVert ^{2}\end{aligned}}$

для $\lambda >0$. Шёлкопф, Хербрих и Смола обобщили этот результат, ослабив предположение о квадрате стоимости потерь и позволив регуляризатору быть любой строго монотонно возрастающей функцией. $g(\cdot )$ нормы гильбертова пространства.

Можно сделать дальнейшее обобщение, дополнив регуляризованный функционал эмпирического риска добавлением нештрафных условий компенсации. Например, Шёлкопф, Хербрих и Смола также рассматривают минимизацию

${\tilde {f}}^{*}=\operatorname {argmin} \left\lbrace E\left((x_{1},y_{1},{\tilde {f}}(x_{1})),\ldots ,(x_{n},y_{n},{\tilde {f}}(x_{n}))\right)+g\left(\lVert f\rVert \right)\mid {\tilde {f}}=f+h\in H_{k}\oplus \operatorname {span} \lbrace \psi _{p}\mid 1\leq p\leq M\rbrace \right\rbrace ,\quad (\dagger )$

т. е. мы рассматриваем функции вида ${\tilde {f}}=f+h$, где $f\in H_{k}$ и $h$ - нештрафованная функция, лежащая в промежутке конечного набора действительных функций. $\lbrace \psi _{p}\colon {\mathcal {X}}\to \mathbb {R} \mid 1\leq p\leq M\rbrace$. В предположении, что $n\times M$ матрица $\left(\psi _{p}(x_{i})\right)_{ip}$ имеет ранг $M$, они показывают, что минимизатор ${\tilde {f}}^{*}$ в $(\dagger )$допускает представление вида

${\tilde {f}}^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i})+\sum _{p=1}^{M}\beta _{p}\psi _{p}(\cdot )$

где $\alpha _{i},\beta _{p}\in \mathbb {R}$ и $\beta _{p}$ все определены однозначно.

Условия существования теоремы о представителе исследовались Аргириу, Микелли и Понтилем, которые доказали следующее:

Теорема: Пусть ${\mathcal {X}}$ быть непустым множеством, $k$ положительно определенное действительное ядро ​​на ${\mathcal {X}}\times {\mathcal {X}}$ с соответствующим гильбертовым пространством воспроизводящего ядра $H_{k}$, и пусть $R\colon H_{k}\to \mathbb {R}$ быть дифференцируемой функцией регуляризации. Затем, учитывая обучающую выборку $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\in {\mathcal {X}}\times \mathbb {R}$ и произвольная функция ошибок $E\colon ({\mathcal {X}}\times \mathbb {R} ^{2})^{m}\to \mathbb {R} \cup \lbrace \infty \rbrace$, минимизатор

$f^{*}={\underset {f\in H_{k}}{\operatorname {argmin} }}\left\lbrace E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+R(f)\right\rbrace \quad (\ddagger )$

регуляризованного эмпирического риска допускает представление в виде

$f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),$

где $\alpha _{i}\in \mathbb {R}$ для всех $1\leq i\leq n$, тогда и только тогда, когда существует неубывающая функция $h\colon [0,\infty )\to \mathbb {R}$ для чего

$R(f)=h(\lVert f\rVert ).$

По сути, этот результат обеспечивает необходимое и достаточное условие существования дифференцируемого регуляризатора. $R(\cdot )$ при котором соответствующая регуляризованная эмпирическая минимизация риска $(\ddagger )$ будет иметь теорему о представителе. В частности, это показывает, что широкий класс регуляризованных минимизаций риска (намного более широкий, чем те, которые первоначально рассматривались Кимельдорфом и Вахбой) имеет теоремы о представителях.

Приложения

Теоремы о репрезентаторах полезны с практической точки зрения, поскольку они значительно упрощают регуляризованную минимизации риска . эмпирическую задачу $(\ddagger )$. В большинстве интересных приложений домен поиска $H_{k}$ для минимизации будет бесконечномерное подпространство $L^{2}({\mathcal {X}})$, и поэтому поиск (как написано) не допускает реализации на компьютерах с конечной памятью и конечной точностью. Напротив, представление $f^{*}(\cdot )$ обеспечиваемая теоремой о представителе, сводит исходную (бесконечномерную) задачу минимизации к поиску оптимального $n$-мерный вектор коэффициентов $\alpha =(\alpha _{1},\ldots ,\alpha _{n})\in \mathbb {R} ^{n}$; $\alpha$ затем может быть получено применением любого стандартного алгоритма минимизации функции. Следовательно, теоремы о представителях обеспечивают теоретическую основу для сведения общей проблемы машинного обучения к алгоритмам, которые действительно могут быть реализованы на компьютерах на практике.

Ниже приведен пример того, как найти минимизатор, существование которого гарантируется теоремой о представителе. Этот метод работает для любого положительно определенного ядра. $K$и позволяет нам преобразовать сложную (возможно, бесконечномерную) задачу оптимизации в простую линейную систему, которую можно решить численно.

Предположим, что мы используем функцию ошибки наименьших квадратов

$E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]:=\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}$

и функция регуляризации $g(x)=\lambda x^{2}$для некоторых $\lambda >0$. По теореме о представителе минимизатор

$f^{*}={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}{\Big \{}E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]+g(\|f\|_{\mathcal {H}}){\Big \}}={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left\{\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}$

имеет форму

$f^{*}(x)=\sum _{i=1}^{n}\alpha _{i}^{*}k(x,x_{i})$

для некоторых $\alpha ^{*}=(\alpha _{1}^{*},\dots ,\alpha _{n}^{*})\in \mathbb {R} ^{n}$. отмечая, что

$\|f\|_{\mathcal {H}}^{2}={\Big \langle }\sum _{i=1}^{n}\alpha _{i}^{*}k(\cdot ,x_{i}),\sum _{j=1}^{n}\alpha _{j}^{*}k(\cdot ,x_{j}){\Big \rangle }_{\mathcal {H}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\alpha _{i}^{*}\alpha _{j}^{*}{\big \langle }k(\cdot ,x_{i}),k(\cdot ,x_{j}){\big \rangle }_{\mathcal {H}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\alpha _{i}^{*}\alpha _{j}^{*}k(x_{i},x_{j}),$

мы видим это $\alpha ^{*}$ имеет форму

$\alpha ^{*}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\sum _{i=1}^{n}\left(y_{i}-\sum _{j=1}^{n}\alpha _{j}k(x_{i},x_{j})\right)^{2}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\|y-A\alpha \|^{2}+\lambda \alpha ^{\intercal }A\alpha \right\}.$

где $A_{ij}=k(x_{i},x_{j})$ и $y=(y_{1},\dots ,y_{n})$. Это можно исключить и упростить до

$\alpha ^{*}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\alpha ^{\intercal }(A^{\intercal }A+\lambda A)\alpha -2\alpha ^{\intercal }Ay\right\}.$

С $A^{\intercal }A+\lambda A$ положительно определен, то для этого выражения действительно существует единственный глобальный минимум. Позволять $F(\alpha )=\alpha ^{\intercal }(A^{\intercal }A+\lambda A)\alpha -2\alpha ^{\intercal }Ay$ и обратите внимание, что $F$ является выпуклым. Затем $\alpha ^{*}$, глобальный минимум, можно решить, установив $\nabla _{\alpha }F=0$. Вспоминая, что все положительно определенные матрицы обратимы, видим, что

$\nabla _{\alpha }F=2(A^{\intercal }A+\lambda A)\alpha ^{*}-2Ay=0\Longrightarrow \alpha ^{*}=(A^{\intercal }A+\lambda A)^{-1}Ay,$

поэтому минимизатор можно найти с помощью линейного решения.

См. также

• Теорема Мерсера
• Методы ядра

Ссылки

• Аргириу, Андреас; Миккелли, Чарльз А.; Понтил, Массимилиано (2009). «Когда существует теорема о представителе? Векторные и матричные регуляризаторы». Журнал исследований машинного обучения . 10 (декабрь): 2507–2529 гг.
• Какер, Фелипе; Смейл, Стив (2002). «О математических основах обучения» . Бюллетень Американского математического общества . 39 (1): 1–49. дои : 10.1090/S0273-0979-01-00923-5 . МР   1864085 .
• Кимельдорф, Джордж С.; Вахба, Грейс (1970). «Соответствие между байесовской оценкой случайных процессов и сглаживанием сплайнами» . Анналы математической статистики . 41 (2): 495–502. дои : 10.1214/aoms/1177697089 .
• Шёлкопф, Бернхард; Хербрих, Ральф; Смола, Алекс Дж. (2001). «Обобщенная теорема о представителе». Вычислительная теория обучения . Конспекты лекций по информатике. Том. 2111. стр. 416–426. CiteSeerX   10.1.1.42.8617 . дои : 10.1007/3-540-44581-1_27 . ISBN  978-3-540-42343-0 .