WikiDer > Теорема о представителях

Representer theorem

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

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

Следующая теорема о репрезентаторе и ее доказательство основаны на Schölkopf, Хербрих и Смола:

Теорема: Рассмотрим положительно определенное вещественное ядро на непустом множестве с соответствующим воспроизводящим ядром Гильбертово пространство . Пусть будет дано

  • обучающая выборка ,
  • строго возрастающая вещественная функция , и
  • произвольная функция ошибок ,

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

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

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

куда для всех .

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

(так что сама по себе карта ). С является воспроизводящим ядром, то

куда внутренний продукт на .

Учитывая любые , можно использовать ортогональную проекцию для разложения любого в сумму двух функций, одна из которых , а другой лежит в ортогональном дополнении:

куда для всех .

Указанное выше ортогональное разложение и воспроизводящая собственность вместе показать, что применение в любую точку тренировки производит

которое мы наблюдаем, не зависит от . Следовательно, значение функции ошибок in (*) также не зависит от . Для второго члена (члена регуляризации), поскольку ортогонален и строго монотонно, имеем

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

что и есть желаемый результат.

Обобщения

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

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

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

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

т.е. мы рассматриваем функции вида , куда и - непенализованная функция, лежащая в промежутке конечного множества действительных функций . В предположении, что матрица имеет звание , они показывают, что минимизатор в допускает представление в виде

куда и все однозначно определены.

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

Теорема: Позволять быть непустым множеством, положительно определенное действительное ядро ​​на с соответствующим воспроизводящим ядром Гильбертово пространство , и разреши - дифференцируемая функция регуляризации. Затем с учетом обучающей выборки и произвольная функция ошибок , минимизатор

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

куда для всех , тогда и только тогда, когда существует неубывающая функция для которого

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

Приложения

Теоремы-репрезентаторы полезны с практической точки зрения, поскольку они значительно упрощают регуляризованные минимизация эмпирического риска проблема . В наиболее интересных приложениях поисковый домен для минимизации будет бесконечномерное подпространство , и поэтому поиск (как написано) не допускает реализации на компьютерах с конечной памятью и конечной точностью. Напротив, представление доставляемая теоремой о представителе, сводит исходную (бесконечномерную) задачу минимизации к поиску оптимального -мерный вектор коэффициентов ; затем можно получить, применив любой стандартный алгоритм минимизации функции. Следовательно, теоремы о представителе обеспечивают теоретическую основу для сведения общей проблемы машинного обучения к алгоритмам, которые фактически могут быть реализованы на компьютерах на практике.

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

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

и функция регуляризации для некоторых . По теореме о представителе минимизатор

имеет форму

для некоторых . Отмечая, что

Мы видим, что имеет форму


куда и . Это можно исключить и упростить до


С положительно определен, действительно существует единственный глобальный минимум для этого выражения. Позволять и обратите внимание, что выпуклый. потом , глобальные минимумы, можно решить, задав . Вспоминая, что все положительно определенные матрицы обратимы, мы видим, что

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

Смотрите также

Рекомендации

  • Аргириу, Андреас; Micchelli, Charles A .; Понтил, Массимилиано (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.