Теория вычислительного обучения

Материал из MachineLearning.

Версия от 10:55, 19 июля 2026; Kseniia Karpeeva (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Теория вычислительного обучения (англ. computational learning theory) — раздел машинного обучения и теории сложности вычислений, посвящённый построению и математическому анализу алгоритмов обучения по конечным наборам примеров. Центральный вопрос этой области состоит в том, при каких условиях закономерность, найденная по обучающей выборке, позволяет делать точные предсказания для ранее не наблюдавшихся объектов.

Теория вычислительного обучения формализует понятия обобщающей способности (англ. generalization ability), обучаемости (англ. learnability), сложности выборки (англ. sample complexity) и вычислительной сложности обучения (англ. computational complexity of learning). Она позволяет оценивать число примеров, необходимое для достижения заданной точности, и определять, может ли требуемая модель быть построена за приемлемое время.

К основным направлениям относятся вероятно приближённо корректное обучение, теория Вапника—Червоненкиса, онлайн-обучение (англ. online learning), обучение с запросами (англ. query learning), PAC-байесовская теория (англ. PAC-Bayesian theory), анализ устойчивости алгоритмов и получение оценок обобщающей способности (англ. generalization bounds).

Содержание

1 Мотивация
2 Формальная постановка задачи
3 PAC-обучение
4 Теория Вапника—Червоненкиса
5 Равномерная сходимость
6 Другие меры сложности и методы анализа
7 Вычислительная сложность обучения
8 Основные модели обучения
9 Связь с практикой машинного обучения
10 История
11 Основные направления исследований
12 Смежные области
13 Конференции и публикации
14 См. также
15 Примечания
16 Литература
17 Ссылки

Мотивация

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

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

Теория вычислительного обучения рассматривает следующие вопросы:

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

Таким образом, обучаемость имеет по меньшей мере два аспекта.

Статистическая обучаемость (англ. statistical learnability) означает, что при увеличении объёма выборки можно получить достаточно точную модель.

Вычислительная обучаемость (англ. computational learnability) дополнительно требует, чтобы обучение выполнялось с допустимыми затратами времени и памяти.

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

Формальная постановка задачи

Объекты, ответы и гипотезы

Пусть $X$ — множество допустимых объектов, а $Y$ — множество ответов. В задаче бинарной классификации обычно полагают

$Y=�igl\{0,1\bigr\}$

или

$Y=�igl\{-1,+1\bigr\}.$

В задаче регрессии множество $Y$ , как правило, является подмножеством вещественных чисел.

Гипотезой (англ. hypothesis) называется функция

$h:X\to Y,$

сопоставляющая объекту предсказанный ответ. Множество допустимых гипотез $H$ называется классом гипотез (англ. hypothesis class) или семейством моделей.

Например, классом гипотез могут быть:

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

Алгоритм обучения получает на вход выборку

$S=((x_1,y_1),\ldots,(x_m,y_m))$

и возвращает некоторую гипотезу $h_S\in H$ . Индекс $S$ подчёркивает, что результат обучения зависит от наблюдавшихся данных.

В классической статистической постановке предполагается, что пары $(x_i,y_i)$ независимо получены из одного неизвестного распределения вероятностей $D$ :

$(x_i,y_i)\sim D.$

Это условие называется предположением о независимых одинаково распределённых наблюдениях (англ. independent and identically distributed, i.i.d.). Оно означает, что обучающие примеры не влияют друг на друга и порождаются тем же распределением, из которого будут поступать будущие объекты.

Функция потерь

Для измерения качества предсказания используется функция потерь (англ. loss function) $L$ . Величина $L(h(x),y)$ показывает, насколько предсказание $h(x)$ отличается от правильного ответа $y$ .

В бинарной классификации часто используется индикатор ошибки:

$L(h(x),y)=[h(x)\ne y],$

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

В регрессии распространена квадратичная функция потерь:

$L(h(x),y)=(h(x)-y)^2.$

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

Истинный и эмпирический риск

Истинным риском (англ. true risk, population risk) гипотезы $h$ называется ожидаемое значение потерь на новых объектах:

$R_D(h)={\rm E}_{(x,y)\sim D}L(h(x),y).$

Истинный риск характеризует среднее качество модели на всём распределении данных. Именно эту величину желательно минимизировать.

Распределение $D$ неизвестно, поэтому истинный риск обычно нельзя вычислить непосредственно. Вместо него используется эмпирический риск (англ. empirical risk):

$\widehat R_S(h)=\frac{1}{m}\sum_{i=1}^{m}L(h(x_i),y_i).$

Он представляет собой среднюю ошибку модели на доступной обучающей выборке.

Принцип минимизации эмпирического риска (англ. empirical risk minimization, ERM) состоит в выборе гипотезы

$\widehat h\in {\rm argmin}_{h\in H}\widehat R_S(h).$

Разность между истинным и эмпирическим рисками

$R_D(h)-\widehat R_S(h)$

называется разрывом обобщения (англ. generalization gap). Основная задача статистической части теории обучения состоит в определении условий, при которых этот разрыв мал для модели, выбранной по обучающей выборке.

Индуктивное смещение

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

Поэтому любой алгоритм обучения содержит индуктивное смещение (англ. inductive bias) — совокупность предположений, определяющих предпочтение одних решений другим.

Индуктивным смещением могут служить:

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

Без некоторого индуктивного смещения обобщение на новые объекты невозможно.

PAC-обучение

Основная идея

Одной из центральных моделей теории вычислительного обучения является вероятно приближённо корректное обучение (англ. probably approximately correct learning, PAC learning).

Модель была предложена Лесли Валиантом в работе 1984 года.^[1]

Название отражает два требования:

приближённо корректный — ошибка построенной модели не превосходит заданного значения $\varepsilon$ ;
вероятно — требуемое качество достигается с вероятностью не менее $1-\delta$ по случайному выбору обучающей выборки.

Параметр $\varepsilon>0$ определяет допустимую ошибку, а параметр $\delta\in(0,1)$ — допустимую вероятность неудачного обучения.

В PAC-постановке требуется, чтобы алгоритм по достаточно большой выборке возвращал гипотезу $h$ , для которой

${\rm P}_{S\sim D^m}\bigl\{R_D(h)\leq\varepsilon\bigr\}\geq 1-\delta.$

Вероятность здесь вычисляется относительно случайного выбора обучающей выборки $S$ .

Реализуемый случай

В классической реализуемой постановке (англ. realizable case) предполагается, что существует неизвестная целевая функция

$c\in C,$

которая безошибочно определяет правильные ответы:

$y=c(x).$

Кроме того, предполагается, что класс гипотез содержит функцию, полностью согласующуюся с данными. Иными словами, для некоторой гипотезы $h\in H$

$R_D(h)=0.$

Класс концепций $C$ называется PAC-обучаемым, если существует алгоритм, который для любых $\varepsilon$ , $\delta$ , распределения $D$ и целевой функции $c\in C$ возвращает гипотезу с ошибкой не более $\varepsilon$ и вероятностью успеха не менее $1-\delta$ .

Если время работы алгоритма и необходимое число примеров полиномиально зависят от параметров задачи, говорят об эффективной PAC-обучаемости (англ. efficient PAC learnability).

Свобода от распределения

Классическое PAC-обучение требует выполнения гарантии для любого распределения $D$ . Такое свойство называется свободой от распределения (англ. distribution-free learning).

Алгоритму не требуется знать вероятности появления отдельных объектов. Однако предполагается, что обучающие и будущие примеры поступают из одного распределения.

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

Агностическое обучение

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

В модели агностического обучения (англ. agnostic learning) не предполагается, что в классе $H$ существует идеальная гипотеза. Требуется найти модель, риск которой близок к наименьшему риску, достижимому внутри класса:

$R_D(h)\leq\inf_{g\in H}R_D(g)+\varepsilon.$

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

Сложность выборки

Сложностью выборки (англ. sample complexity) называется минимальное число примеров, достаточное для достижения заданной точности $\varepsilon$ с вероятностью не менее $1-\delta$ .

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

$m=O\left(\frac{\ln|H|+\ln(1/\delta)}{\varepsilon}\right)$

примеров.^[1]

В агностическом случае типичная оценка имеет вид

$m=O\left(\frac{\ln|H|+\ln(1/\delta)}{\varepsilon^2}\right).$

Величина $\ln|H|$ может интерпретироваться как мера информации, необходимой для выбора одной гипотезы из множества $H$ . Чем больше допустимых моделей, тем больше данных требуется для их надёжного сравнения.

Зависимость от $\ln(1/\delta)$ показывает, что значительное увеличение уверенности требует сравнительно небольшого увеличения выборки. Напротив, повышение точности может быть существенно дороже, особенно в агностическом случае, где возникает зависимость от $1/\varepsilon^2$ .

Теория Вапника—Червоненкиса

Для бесконечного класса гипотез величина $|H|$ не может использоваться как конечная мера сложности. Теория Вапника—Червоненкиса вводит комбинаторные характеристики, описывающие разнообразие решений, представимых классом моделей.

Основной такой характеристикой является размерность Вапника—Червоненкиса, или VC-размерность (англ. Vapnik–Chervonenkis dimension, VC dimension).

Теория была разработана Владимиром Вапником и Алексеем Червоненкисом при исследовании условий равномерной сходимости эмпирических частот к вероятностям.^[1]

Разбиение множества

Пусть $H$ — класс бинарных классификаторов, а $A=\{x_1,\ldots,x_n\}$ — конечное множество объектов.

Говорят, что класс $H$ разбивает множество $A$ (англ. shatters a set), если для любого назначения бинарных меток объектам из $A$ существует гипотеза $h\in H$ , реализующая это назначение.

Иначе говоря, класс должен уметь воспроизвести на множестве $A$ все $2^n$ возможных вариантов бинарной разметки.

VC-размерностью класса $H$ называется максимальное число объектов, которое может быть разбито этим классом:

${\rm VCdim}(H)=\max\{|A|:\ H\ {\rm разбивает}\ A\}.$

Если класс способен разбивать множества сколь угодно большого размера, его VC-размерность считается бесконечной.

Примеры

Пороговые классификаторы на вещественной прямой имеют VC-размерность 1. Одну точку можно отнести к любому классу, но не все разметки двух точек реализуются одним порогом.
Индикаторы интервалов на прямой имеют VC-размерность 2. Любая разметка двух точек реализуема, но чередующаяся разметка трёх точек одним интервалом не задаётся.
Аффинные линейные классификаторы в $\mathbb{R}^d$ имеют VC-размерность $d+1$ . В общем положении такой класс способен разбить $d+1$ точку.
Окружности на плоскости имеют VC-размерность 3. Три точки в общем положении могут быть размечены произвольно, но для четырёх точек это верно не всегда.

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

Функция роста

Более подробной характеристикой класса является функция роста (англ. growth function) $\Pi_H(n)$ , равная максимальному числу различных бинарных разметок множества из $n$ объектов, которые могут быть реализованы гипотезами из $H$ .

Всегда выполняется

$\Pi_H(n)\leq 2^n.$

Если класс разбивает некоторое множество из $n$ объектов, то

$\Pi_H(n)=2^n.$

Лемма Зауэра—Шелаха показывает, что при конечной VC-размерности $d$ функция роста увеличивается не быстрее полинома:

$\Pi_H(n)\leq\sum_{i=0}^{d}{n\choose i}.$

Этот результат связывает локальное свойство — возможность разбить конечное множество — с глобальным ограничением выразительности класса.

VC-размерность и обучаемость

Для бинарной классификации конечность VC-размерности является фундаментальным условием обучаемости. При стандартных условиях измеримости класс гипотез PAC-обучаем тогда и только тогда, когда его VC-размерность конечна.^[1]

Если $d={\rm VCdim}(H)$ , то в реализуемом случае стандартная верхняя оценка сложности выборки имеет порядок

$m=O\left(\frac{d\ln(1/\varepsilon)+\ln(1/\delta)}{\varepsilon}\right).$

В агностической постановке типичная оценка равна

$m=O\left(\frac{d+\ln(1/\delta)}{\varepsilon^2}\right).$

Эти оценки показывают, что необходимый объём данных определяется не только требуемой точностью, но и выразительностью класса моделей.

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

Равномерная сходимость

Один из основных способов доказательства обобщающей способности основан на равномерной сходимости (англ. uniform convergence):

$\sup_{h\in H}|R_D(h)-\widehat R_S(h)|\to 0$

при увеличении размера выборки.

Обычного закона больших чисел для отдельной фиксированной гипотезы недостаточно. Алгоритм выбирает модель после наблюдения данных, поэтому требуется одновременно контролировать отклонение эмпирического риска от истинного для всех гипотез из $H$ .

Если с вероятностью не менее $1-\delta$ выполняется

$\sup_{h\in H}|R_D(h)-\widehat R_S(h)|\leq\varepsilon,$

то любая гипотеза с малым эмпирическим риском имеет и относительно малый истинный риск.

Пусть $\widehat h$ минимизирует эмпирический риск, а $h^*$ минимизирует истинный риск внутри $H$ . Тогда из равномерной сходимости следует

$R_D(\widehat h)\leq R_D(h^*)+2\varepsilon.$

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

Другие меры сложности и методы анализа

Радемахерова сложность

VC-размерность предназначена прежде всего для бинарных функций и характеризует класс глобально. Для вещественнозначных функций и зависимых от выборки оценок применяется радемахерова сложность (англ. Rademacher complexity).

Для выборки $S=(x_1,\ldots,x_m)$ введём величину

$Q_S(h,\sigma)=\frac{1}{m}\sum_{i=1}^{m}\sigma_i h(x_i),$

где $\sigma_1,\ldots,\sigma_m$ — независимые случайные величины, принимающие значения $-1$ и $+1$ с одинаковой вероятностью. Эмпирическая радемахерова сложность определяется как

$\widehat{\mathcal R}_S(H)={\rm E}_{\sigma}\sup_{h\in H}Q_S(h,\sigma).$

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

В отличие от VC-размерности, эмпирическая радемахерова сложность зависит от расположения объектов конкретной выборки. Поэтому она может давать более точные оценки для фактически наблюдаемых данных.^[1]

Устойчивость алгоритма

Другой подход анализирует не весь класс гипотез, а поведение конкретного метода обучения.

Устойчивость алгоритма (англ. algorithmic stability) характеризует изменение результата обучения при небольшом изменении выборки, например при удалении или замене одного объекта.

Если замена одного примера не приводит к существенному изменению предсказаний, алгоритм считается устойчивым. Интуитивно устойчивый алгоритм не зависит критически от отдельных наблюдений и поэтому меньше склонен к переобучению.

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

Устойчивость лежит также в основе теоретического анализа оценки исключения по одному объекту (англ. leave-one-out estimate), являющейся частным случаем скользящего контроля.

PAC-байесовские оценки

В PAC-байесовском подходе (англ. PAC-Bayesian approach, PAC-Bayes) рассматриваются распределения над гипотезами.

До получения данных задаётся априорное распределение $P$ , а после обучения выбирается распределение $Q$ . Оценка обобщающей способности связывает эмпирический риск, объём выборки, требуемую вероятность и сложность перехода от $P$ к $Q$ .

Сложность перехода обычно измеряется дивергенцией Кульбака—Лейблера (англ. Kullback–Leibler divergence):

${\rm KL}(Q\Vert P).$

Чем сильнее апостериорное распределение $Q$ отличается от априорного $P$ , тем больше штраф за сложность.

PAC-байесовская теория использует распределения над моделями, но не совпадает с обычным байесовским выводом. В ней априорное распределение может рассматриваться как средство формулировки оценки сложности, а не обязательно как истинное вероятностное описание параметров.^[1]

Компрессия выборки

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

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

Примером служит метод опорных векторов, в котором решение определяется главным образом объектами, расположенными около разделяющей границы. Такие объекты называются опорными векторами.

Вычислительная сложность обучения

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

Алгоритм обычно называют эффективным, если его время работы полиномиально зависит от:

размера представления объектов;
числа признаков;
объёма обучающей выборки;
величины $1/\varepsilon$ ;
величины $\ln(1/\delta)$ ;
сложности представления гипотезы.

При анализе вычислительной обучаемости исследуются:

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

Правильным обучением (англ. proper learning) называется обучение, при котором итоговая гипотеза должна принадлежать исходному классу $H$ .

При неправильном обучении (англ. improper learning) алгоритм может возвращать гипотезу из более широкого класса. Иногда это существенно упрощает задачу.

Некоторые классы имеют конечную VC-размерность и потому обучаемы в статистическом смысле, но их эффективное обучение считается невозможным при стандартных криптографических предположениях.

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

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

Основные модели обучения

Пакетное обучение

В стандартной постановке алгоритм получает всю выборку целиком, после чего строит итоговую модель. Такая схема называется пакетным обучением (англ. batch learning).

Пакетная постановка удобна для теоретического анализа, поскольку выборка считается фиксированным конечным набором независимых наблюдений. Большая часть классической PAC-теории и VC-теории формулируется именно для этой схемы.

Онлайн-обучение

В онлайн-обучении (англ. online learning) объекты поступают последовательно. На шаге $t$ алгоритм получает объект $x_t$ , выдаёт предсказание, узнаёт правильный ответ или значение потерь и обновляет модель.

Вместо риска на фиксированном распределении часто анализируется сожаление (англ. regret) относительно лучшей постоянной гипотезы. Накопленная потеря алгоритма равна

$L_T=\sum_{t=1}^{T}L(h_t,z_t),$

а потеря лучшей фиксированной гипотезы из $H$ равна

$L_T^*=\inf_{h\in H}\sum_{t=1}^{T}L(h,z_t).$

Сожаление определяется разностью

${\rm Regret}_T=L_T-L_T^*.$

Алгоритм считается успешным, если ${\rm Regret}_T=o(T)$ . В этом случае средняя дополнительная потеря относительно лучшей гипотезы стремится к нулю.

Онлайн-постановка не всегда требует вероятностного предположения i.i.d. Последовательность объектов может формироваться адаптивно или даже противником.

Одним из ранних результатов этого направления стал алгоритм Winnow Ника Литтлстоуна, предназначенный для обучения в пространствах с большим числом нерелевантных признаков.^[1]

Комбинаторной характеристикой сложности онлайн-классификации является размерность Литтлстоуна (англ. Littlestone dimension).

Обучение с запросами

При обычном пассивном обучении алгоритм не управляет тем, какие объекты появляются в выборке.

В обучении с запросами (англ. query learning) алгоритм может получать дополнительную информацию о самостоятельно выбранных объектах или гипотезах.

Основные типы запросов:

запрос принадлежности (англ. membership query) — алгоритм выбирает объект и запрашивает его правильную метку;
запрос эквивалентности (англ. equivalence query) — алгоритм предлагает гипотезу и получает подтверждение либо контрпример;
запрос значения функции;
запрос статистической характеристики распределения.

Систематическая теория обучения концептов с помощью запросов была развита Даной Англуин.^[1]

Возможность задавать запросы может радикально изменить сложность задачи. Некоторые классы трудно обучать по случайным примерам, но относительно легко восстанавливать при наличии содержательных запросов.

Активное обучение

Активное обучение (англ. active learning) — постановка, в которой алгоритм выбирает объекты, для которых следует получить разметку.

Основной характеристикой становится сложность разметки (англ. label complexity) — число обращений к эксперту, необходимое для достижения заданной точности.

Активное обучение особенно полезно, когда неразмеченные объекты доступны в большом количестве, а получение правильных ответов требует дорогостоящей экспертной работы.

Типичные стратегии активного обучения:

выбор объектов, в которых модель наименее уверена;
выбор объектов, вызывающих максимальное несогласие между моделями;
выбор примеров, ожидаемо сильнее всего изменяющих модель;
выбор примеров, уменьшающих неопределённость относительно пространства гипотез.

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

Статистические запросы

В модели статистических запросов (англ. statistical query model) алгоритм не получает отдельные размеченные примеры. Вместо этого он запрашивает приближённые значения математических ожиданий функций от данных.

Запрос имеет вид

${\rm E}_{(x,y)\sim D}\varphi(x,y),$

а механизм ответов возвращает значение с некоторой допустимой погрешностью.

Модель была предложена Майклом Кернсом для анализа обучения при наличии случайного шума в метках.^[1]

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

Слабая и сильная обучаемость

При слабом обучении (англ. weak learning) требуется построить классификатор, качество которого лишь немного превосходит случайное угадывание. Для бинарной классификации слабый алгоритм может обеспечивать ошибку

$R_D(h)\leq\frac{1}{2}-\gamma,$

где $\gamma>0$ — небольшое преимущество над случайным классификатором.

При сильном обучении (англ. strong learning) ошибку требуется уменьшить до произвольно заданного значения $\varepsilon$ .

Теория бустинга (англ. boosting) показывает, что при определённых условиях слабую обучаемость можно преобразовать в сильную. Эта связь стала теоретической основой методов, объединяющих множество сравнительно неточных базовых алгоритмов в одну сильную композицию.

Связь с практикой машинного обучения

Отложенная выборка и скользящий контроль

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

Простейший способ — оценка на отложенной выборке (англ. hold-out validation). Исходные данные разделяются на обучающую часть, используемую для настройки модели, контрольную часть, используемую для выбора гиперпараметров, и тестовую часть, используемую для окончательной оценки качества.

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

При небольшом объёме данных применяется скользящий контроль (англ. cross-validation). Выборка разбивается на несколько частей; модель поочерёдно обучается на одних частях и проверяется на оставшейся.

Теоретические оценки и скользящий контроль решают разные задачи:

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

Ни один из подходов не заменяет другой.

Для несбалансированных задач классификации может использоваться стратифицированное разбиение (англ. stratified splitting), сохраняющее приблизительные доли классов в каждой части выборки.

Выбор сложности модели

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

Этот компромисс можно представить как взаимодействие двух составляющих:

ошибка аппроксимации (англ. approximation error) — ограничение, вызванное недостаточной выразительностью класса;
ошибка оценивания (англ. estimation error) — ошибка, возникающая из-за конечного объёма выборки.

Слишком простой класс имеет большую ошибку аппроксимации. Слишком сложный класс может иметь большую ошибку оценивания.

На практике сложность регулируется с помощью:

ограничения архитектуры модели;
штрафов за большие значения параметров;
ограничения глубины дерева;
ограничения нормы весов;
отбора признаков;
ранней остановки;
выбора гиперпараметров по контрольной выборке;
усреднения нескольких моделей;
ансамблирования.

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

Число параметров и фактическая сложность

Число параметров является важной, но не универсальной мерой сложности модели.

Для линейных классификаторов VC-размерность тесно связана с размерностью пространства признаков. Однако для современных нейронных сетей качество обобщения может зависеть не только от количества параметров, но и от нормы весов, архитектуры сети, величины отступов (англ. margins), способа инициализации, алгоритма оптимизации, устойчивости обучения, структуры данных и неявной регуляризации (англ. implicit regularization).

Современные модели нередко содержат больше параметров, чем имеется обучающих объектов, и при этом успешно обобщают. Поэтому прямое отождествление числа параметров с эффективной сложностью может быть неверным.

Оценки для худшего случая

Большинство классических теоретических оценок формулируется для худшего допустимого распределения данных и худшей целевой зависимости.

Такие оценки отвечают на вопрос: какое качество гарантировано без дополнительных сведений о задаче?

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

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

Нарушение предположения i.i.d.

Классические PAC- и VC-результаты обычно предполагают, что обучающие и будущие данные получены из одного распределения.

На практике это условие может нарушаться из-за изменения поведения пользователей, сезонности, изменения измерительных приборов, переноса модели в другую организацию или регион, изменения правил сбора данных, целенаправленного воздействия на модель или зависимости наблюдений во времени.

Изменение распределения называется сдвигом распределения (англ. distribution shift). Изменение зависимости между объектами и ответами во времени называется дрейфом концепции (англ. concept drift).

При наличии такого сдвига малая ошибка скользящего контроля на старых данных не гарантирует высокого качества после внедрения модели.

Теоретическая оценка всегда является условным утверждением: она справедлива только при выполнении предпосылок используемой модели.

История

Математические основы теории обучаемости формировались в математической статистике, распознавании образов, теории вероятностей и теоретической информатике.

В конце 1960-х годов Владимир Вапник и Алексей Червоненкис исследовали условия равномерной сходимости эмпирических частот событий к их вероятностям. Первые результаты были опубликованы на русском языке в 1968 году, а развёрнутая англоязычная статья вышла в 1971 году.^[1] Эти исследования привели к созданию теории Вапника—Червоненкиса и строгому анализу обобщающей способности методов минимизации эмпирического риска.

В 1984 году Лесли Валиант опубликовал работу «A Theory of the Learnable», в которой предложил вычислительную формализацию обучения.^[1] В ней были объединены требования к точности, вероятности успеха, объёму выборки и вычислительной эффективности. Эта работа положила начало PAC-теории.

Во второй половине 1980-х годов активно развивались теория обучения с запросами, модели последовательного предсказания, анализ числа ошибок онлайн-алгоритмов, связь PAC-обучаемости с VC-размерностью и теория слабой и сильной обучаемости.

В 1988 году состоялась первая конференция по вычислительной теории обучения. Впоследствии она стала ежегодной Conference on Learning Theory, COLT. Ранее конференция называлась Conference on Computational Learning Theory.^[1]

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

Параллельно проводилась европейская серия конференций European Conference on Computational Learning Theory, EuroCOLT. В 2001 году EuroCOLT была проведена совместно с COLT.^[1]

С конца 1990-х и в 2000-е годы получили развитие PAC-байесовские оценки, радемахеровы сложности, локальные меры сложности и теория устойчивости алгоритмов.

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

При этом классические вопросы — сколько данных требуется, что делает модель обучаемой и можно ли найти её эффективно — остаются центральными.

Основные направления исследований

К современным направлениям теории вычислительного обучения относятся:

PAC-обучение и агностическое обучение;
Теория Вапника-Червоненкиса;
VC-размерность;
сложность выборки;
оценки обобщающей способности;
равномерная сходимость;
радемахеровы и гауссовы сложности;
PAC-байесовские оценки;
устойчивость алгоритмов;
компрессия обучающих выборок;
онлайн-обучение и анализ сожаления;
активное обучение и обучение с запросами;
обучение при шуме;
теория статистических запросов;
вычислительные нижние оценки обучаемости;
теория бустинга;
обучение при изменении распределения;
теория многозадачного обучения;
метаобучение;
теоретический анализ нейронных сетей;
теория обучения с подкреплением;
конфиденциальность и устойчивость обучения.

Смежные области

Теория вычислительного обучения использует методы следующих дисциплин:

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

Граница между теорией вычислительного и статистического обучения не является строгой. Термин «теория статистического обучения» чаще подчёркивает вероятностные свойства оценивания и обобщения, тогда как «теория вычислительного обучения» традиционно уделяет больше внимания алгоритмической и вычислительной стороне обучаемости.

Конференции и публикации

Основной международной конференцией области является Conference on Learning Theory — COLT. Она проводится ежегодно с 1988 года и охватывает теоретические аспекты машинного обучения на пересечении информатики, статистики и прикладной математики.^[1]

Другой крупной конференцией является International Conference on Algorithmic Learning Theory — ALT, посвящённая алгоритмическим и математическим аспектам обучения.

Результаты по теории обучения также публикуются в журналах Journal of Machine Learning Research, Machine Learning, Journal of the ACM, Annals of Statistics, IEEE Transactions on Information Theory и в серии Proceedings of Machine Learning Research.

На MachineLearning.ru материалы по теме представлены в статьях PAC-обучение, Теория Валианта, Теория Вапника-Червоненкиса, Размерность Вапника-Червоненкиса, Минимизация эмпирического риска, Переобучение и Теория статистического обучения.

См. также

Примечания

Литература

Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.
Vapnik V. N. Statistical Learning Theory. — New York: Wiley, 1998. — ISBN 978-0-471-03003-4.
Kearns M. J., Vazirani U. V. An Introduction to Computational Learning Theory. — MIT Press, 1994. — ISBN 978-0-262-11193-5.
Shalev-Shwartz S., Ben-David S. Understanding Machine Learning: From Theory to Algorithms. — Cambridge University Press, 2014. — DOI: 10.1017/CBO9781107298019.
Mohri M., Rostamizadeh A., Talwalkar A. Foundations of Machine Learning. — 2nd ed. — MIT Press, 2018. — ISBN 978-0-262-03940-6.
Cesa-Bianchi N., Lugosi G. Prediction, Learning, and Games. — Cambridge University Press, 2006. — ISBN 978-0-521-84108-5.
Valiant L. G. A Theory of the Learnable // Communications of the ACM. — 1984. — Vol. 27, no. 11. — P. 1134–1142.
Vapnik V. N., Chervonenkis A. Ya. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities // Theory of Probability and Its Applications. — 1971. — Vol. 16, no. 2. — P. 264–280.
Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K. Learnability and the Vapnik–Chervonenkis Dimension // Journal of the ACM. — 1989. — Vol. 36, no. 4. — P. 929–965.
Bartlett P. L., Mendelson S. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results // Journal of Machine Learning Research. — 2002. — Vol. 3. — P. 463–482.
Bousquet O., Elisseeff A. Stability and Generalization // Journal of Machine Learning Research. — 2002. — Vol. 2. — P. 499–526.
Angluin D. Queries and Concept Learning // Machine Learning. — 1988. — Vol. 2. — P. 319–342.
Kearns M. Efficient Noise-Tolerant Learning from Statistical Queries // Journal of the ACM. — 1998. — Vol. 45, no. 6. — P. 983–1006.
Kearns M., Valiant L. G. Cryptographic Limitations on Learning Boolean Formulae and Finite Automata // Journal of the ACM. — 1994. — Vol. 41, no. 1. — P. 67–95.
Littlestone N. Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm // Machine Learning. — 1988. — Vol. 2. — P. 285–318.
McAllester D. A. PAC-Bayesian Model Averaging // Proceedings of the 12th Annual Conference on Computational Learning Theory. — 1999. — P. 164–170.

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D1%8F»

Категории: Машинное обучение | Теория вычислительного обучения | Вычислительная сложность | Энциклопедия анализа данных