Обучаемый класс функций

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

Определение

Фон

Позволять $\Omega ={\mathcal {X}}\times {\mathcal {Y}}=\{(x,y)\}$ быть пространством выборки, где $y$ это этикетки и $x$ являются ковариатами (предикторами). ${\mathcal {F}}=\{f:{\mathcal {X}}\mapsto {\mathcal {Y}}\}$ представляет собой совокупность рассматриваемых отображений (функций), связывающих $x$ к $y$ . $L:{\mathcal {Y}}\times {\mathcal {Y}}\mapsto \mathbb {R}$ — заранее заданная функция потерь (обычно неотрицательная). Учитывая распределение вероятностей $P(x,y)$ на $\Omega$ , определить ожидаемый риск $I_{P}(f)$ быть:

I_{P}(f)=\int L(f(x),y)dP(x,y)

Общая цель статистического обучения — найти функцию в ${\mathcal {F}}$ это минимизирует ожидаемый риск. То есть найти решение следующей проблемы: ^[1]

{\hat {f}}=\arg \min _{f\in {\mathcal {F}}}I_{P}(f)

Но на практике распределение $P$ неизвестно, и любая задача обучения может быть основана только на конечных выборках. Таким образом, вместо этого мы стремимся найти алгоритм, который асимптотически минимизирует эмпирический риск, т. е. найти последовательность функций $\{{\hat {f}}_{n}\}_{n=1}^{\infty }$ это удовлетворяет

\lim _{n\rightarrow \infty }\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0

Одним из обычных алгоритмов поиска такой последовательности является минимизация эмпирического риска .

Обучаемый класс функций

Мы можем усилить условие, данное в приведенном выше уравнении, потребовав, чтобы сходимость была равномерной для всех распределений вероятностей. То есть:

\lim _{n\rightarrow \infty }\sup _{P}\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0

( 1 )

Интуиция, лежащая в основе более строгих требований, такова: скорость, с которой последовательность $\{{\hat {f}}_{n}\}$ сходится к минимизатору ожидаемого риска, может сильно различаться для разных $P(x,y)$ . Потому что в реальном мире истинное распределение $P$ всегда неизвестен, мы хотели бы выбрать последовательность, которая хорошо работает во всех случаях.

Однако по теореме об отсутствии бесплатного обеда такая последовательность, удовлетворяющая ( 1 ), не существует, если ${\mathcal {F}}$ слишком сложно. Это означает, что нам нужно быть осторожными и не допускать слишком «много» функций в ${\mathcal {F}}$ если мы хотим, чтобы ( 1 ) было значимым требованием. В частности, классы функций, обеспечивающие существование последовательности. $\{{\hat {f}}_{n}\}$ которые удовлетворяют ( 1 ), известны как обучаемые классы . ^[1]

Стоит отметить, что, по крайней мере, для задач контролируемой классификации и регрессии, если класс функции является обучаемым, то минимизация эмпирического риска автоматически удовлетворяет ( 1 ). ^[2] Таким образом, в этих условиях мы не только знаем, что проблема, поставленная ( 1 ), разрешима, но и сразу же имеем алгоритм, который дает решение.

Интерпретации

Если истинные отношения между $y$ и $x$ является $y\sim f^{*}(x)$ , затем, выбрав соответствующую функцию потерь, $f^{*}$ всегда можно выразить как минимизатор ожидаемых потерь по всем возможным функциям. То есть,

f^{*}=\arg \min _{f\in {\mathcal {F}}^{*}}I_{P}(f)

Здесь мы позволяем ${\mathcal {F}}^{*}$ быть совокупностью всех возможных функций, отображающих ${\mathcal {X}}$ на ${\mathcal {Y}}$ . $f^{*}$ можно интерпретировать как реальный механизм генерации данных. Однако теорема об отсутствии бесплатного обеда говорит нам, что на практике с конечными выборками мы не можем надеяться на поиск ожидаемого минимизатора риска за ${\mathcal {F}}^{*}$ . Таким образом, мы часто рассматриваем подмножество ${\mathcal {F}}^{*}$ , ${\mathcal {F}}$ , для проведения поиска. Поступая так, мы рискуем $f^{*}$ может не быть элементом ${\mathcal {F}}$ . Этот компромисс можно математически выразить как

I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}^{*}}I_{P}(f)=\underbrace {I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)} _{(a)}+\underbrace {\inf _{f\in {\mathcal {F}}}I_{P}(f)-\inf _{f\in {\mathcal {F}}^{*}}I_{P}(f)} _{(b)}

( 2 )

В приведенном выше разложении часть $(b)$ не зависит от данных и не является стохастическим. Он описывает, насколько далеки наши предположения ( ${\mathcal {F}}$ ) от истины ( ${\mathcal {F}}^{*}$ ). $(b)$ будет строго больше 0, если мы сделаем слишком сильные предположения ( ${\mathcal {F}}$ слишком маленький). С другой стороны, если не установить достаточных ограничений на ${\mathcal {F}}$ приведет к тому, что его невозможно будет изучить, и часть $(a)$ не будет стохастически сходиться к 0. Это хорошо известная проблема переобучения в литературе по статистике и машинному обучению.

Пример: Тихоновская регуляризация

Хорошим примером использования обучаемых классов является так называемая тихоновская регуляризация при воспроизведении ядра гильбертова пространства (RKHS). Конкретно, пусть ${\mathcal {F^{*}}}$ быть RKHS, и $||\cdot ||_{2}$ быть нормой для ${\mathcal {F^{*}}}$ задано его внутренним продуктом. Это показано в ^[3] что ${\mathcal {F}}=\{f:||f||_{2}\leq \gamma \}$ является обучаемым классом для любого конечного положительного $\gamma$ . Алгоритм эмпирической минимизации двойственной формы этой задачи:

\arg \min _{f\in {\mathcal {F}}^{*}}\left\{\sum _{i=1}^{n}L(f(x_{i}),y_{i})+\lambda ||f||_{2}\right\}

Впервые это было предложено Тихоновым. ^[4] решать некорректные задачи. Многие алгоритмы статистического обучения можно выразить в такой форме (например, известная ридж-регрессия ).

Компромисс между $(a)$ и $(b)$ в ( 2 ) геометрически более интуитивно понятен с регуляризацией Тихонова в RKHS. Мы можем рассмотреть последовательность $\{{\mathcal {F}}_{\gamma }\}$ , которые по сути представляют собой шарики в ${\mathcal {F^{*}}}$ с центрами в 0. Поскольку $\gamma$ становится больше, ${\mathcal {F}}_{\gamma }$ приближается ко всему пространству и $(b)$ скорее всего, станет меньше. Однако мы также будем страдать от меньших темпов конвергенции в $(a)$ . Способ выбора оптимального $\gamma$ в условиях ограниченной выборки обычно осуществляется посредством перекрестной проверки .

Связь с теорией эмпирических процессов

Часть $(a)$ в ( 2 ) тесно связан с теорией эмпирических процессов в статистике, где эмпирический риск $\{\sum _{i=1}^{n}L(y_{i},f(x_{i})),f\in {\mathcal {F}}\}$ известны как эмпирические процессы. ^[5] В этом поле класс функции ${\mathcal {F}}$ который удовлетворяет стохастической сходимости

\sup _{P}\mathbb {E} \sup _{f\in {\mathcal {F}}}|\sum _{i=1}^{n}L(y_{i},f(x_{i}))-I_{P}(f)|=0

( 3 )

известны как равномерные классы Гливенко–Кантелли . Показано, что при определенных условиях регулярности обучаемые классы и равномерно классы Гливенко-Кантелли эквивалентны. ^[1] Взаимодействие между $(a)$ и $(b)$ в статистической литературе часто называют компромиссом смещения-дисперсии .

Однако обратите внимание, что в ^[2] авторы привели пример стохастической выпуклой оптимизации для общих условий обучения, где обучаемость не эквивалентна равномерной сходимости.

Ссылки

^ Jump up to: ^а ^б ^с Владимир Н. Вапник (17 апреля 2013 г.). Природа статистической теории обучения . Springer Science & Business Media. ISBN 978-1-4757-2440-0 .
^ Jump up to: ^а ^б «Обучаемость, стабильность и равномерная сходимость». Журнал исследований машинного обучения .
^ «Обучаемость в гильбертовых пространствах с воспроизводящими ядрами». Журнал сложности .
^ Andreĭ Nikolaevich Tikhonov; Vasiliĭ I︠A︡kovlevich Arsenin (1977). Solutions of ill-posed problems . Winston. ISBN 978-0-470-99124-4 .
^ А.В. ван дер Ваарт; Джон Веллнер (9 марта 2013 г.). Слабая сходимость и эмпирические процессы: с приложениями к статистике . Springer Science & Business Media. стр. 116–. ISBN 978-1-4757-2545-2 .

[Vapnik2013-1] Jump up to: ^а ^б ^с Владимир Н. Вапник (17 апреля 2013 г.). Природа статистической теории обучения . Springer Science & Business Media. ISBN 978-1-4757-2440-0 .

[:0-2] Jump up to: ^а ^б «Обучаемость, стабильность и равномерная сходимость». Журнал исследований машинного обучения .

[3] «Обучаемость в гильбертовых пространствах с воспроизводящими ядрами». Журнал сложности .

[TikhonovArsenin1977-4] Andreĭ Nikolaevich Tikhonov; Vasiliĭ I︠A︡kovlevich Arsenin (1977). Solutions of ill-posed problems . Winston. ISBN 978-0-470-99124-4 .

[vaartWellner2013-5] А.В. ван дер Ваарт; Джон Веллнер (9 марта 2013 г.). Слабая сходимость и эмпирические процессы: с приложениями к статистике . Springer Science & Business Media. стр. 116–. ISBN 978-1-4757-2545-2 .

[1]

[2]

[3]

[4]

[5]