Класс изучаемых функций

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

Определение

Фон

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

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

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

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

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

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

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

Класс изучаемых функций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Владимир Н. Вапник (17 апреля 2013 г.). Природа статистической теории обучения. Springer Science & Business Media. ISBN 978-1-4757-2440-0.
2. «Обучаемость, устойчивость и равномерная сходимость». Журнал исследований машинного обучения .
3. «Обучаемость в гильбертовых пространствах с воспроизводящимися ядрами». Журнал сложности .
4. Андрей Николаевич Тихонов; Василий Иванович Арсенин (1977). Решения некорректных задач. Уинстон. ISBN 978-0-470-99124-4.
5. AW van der vaart; Jon Wellner (9 марта 2013 г.). Слабая конвергенция и эмпирические процессы: с приложениями к статистике. Springer Science & Business Media. стр. 116–. ISBN 978-1-4757-2545-2.