Минимизация эмпирического риска

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

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM Gemini 3.1 Pro Preview и проверена участником Polina Khadralinova

Содержание

1 Введение
2 Историческая справка
3 Ожидаемый и эмпирический риск
4 Условия состоятельности и переобучение
- 4.1 Зачем нужна состоятельность и равномерная сходимость?
- 4.2 Оценка Вапника — Червоненкиса
5 Регуляризация
6 Основные типы функций потерь
- 6.1 В задачах регрессии
- 6.2 В задачах классификации
7 Методы оптимизации
8 См. также
9 Примечания
10 Литература

Минимизация эмпирического риска (англ. Empirical Risk Minimization, ERM) — это фундаментальный принцип машинного обучения. Он заключается в том, что из заданного семейства моделей мы выбираем ту, которая показывает наименьшую ошибку на доступных тренировочных данных.

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

Введение

Задача машинного обучения с учителем формулируется так. У нас есть множество объектов $X$ (например, фотографии) и множество допустимых ответов $Y$ (например, метки «кошка» или «собака»). Существует скрытая закономерность — идеальное правило $y^*: X \to Y$ .

Мы не знаем эту закономерность целиком. Нам доступна лишь конечная обучающая выборка $X^{\ell} = \{ (x_i, y_i) \}_{i=1}^{\ell}$ .

Наша цель — найти такой алгоритм $a: X \to Y$ из заданного семейства моделей $A = \{ a(x, w) \mid w \in W \}$ , который не просто запомнит правильные ответы для обучающей выборки, но и сможет эффективно (с минимальным количеством ошибок) работать на новых данных. Ошибку модели на конкретном объекте мы измеряем с помощью функции потерь $\mathcal{L}(y, a(x))$ .

Историческая справка

Истоки принципа минимизации эмпирического риска восходят к философской концепции эмпирической индукции Фрэнсиса Бэкона (1620 г.), утверждавшего, что законы природы необходимо выводить путём обобщения фактов опыта, а не постулировать умозрительно.

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

Своё современное теоретико-вероятностное обоснование принцип ERM получил в конце 1960-х — начале 1970-х годов в трудах советских математиков В. Н. Вапника и А. Я. Червоненкиса. В рамках созданной ими статистической теории обучения (теории Вапника-Червоненкиса) были строго сформулированы условия состоятельности принципа минимизации эмпирического риска и получены оценки скорости сходимости ошибки.

Ожидаемый и эмпирический риск

В теории машинного обучения мы считаем, что данные не появляются из ниоткуда. Существует неизвестное вероятностное распределение $P(x, y)$ на пространстве $X \times Y$ . Все наши объекты и ответы генерируются независимо из этого распределения.

В идеальном мире мы хотели бы создать модель, которая ошибается как можно реже на любых возможных данных. Эта идеальная мера ошибки называется ожидаемым риском (или истинным риском). Математически это математическое ожидание функции потерь по всему распределению:

$R(a) = \mathbb{E}_{x,y \sim P} [\mathcal{L}(y, a(x))] = \int_{X \times Y} \mathcal{L}(y, a(x)) dP(x, y)$

Интуитивная аналогия: Представьте, что вы готовитесь к сложному экзамену. Ожидаемый риск — это ваша реальная оценка на самом экзамене, где вам может попасться абсолютно любой билет по предмету. Мы хотим сдать экзамен на «отлично», то есть свести ожидаемый риск $R(a)$ к минимуму.

Проблема в том, что заранее узнать все вопросы экзамена (распределение $P(x, y)$ ) невозможно. Поэтому вычислить ожидаемый риск $R(a)$ напрямую нельзя.

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

Поскольку у нас нет всех данных мира, мы используем билеты прошлых лет — нашу обучающую выборку $X^{\ell}$ . Закон больших чисел говорит нам, что теоретическое математическое ожидание можно оценить на практике, просто усреднив ошибку на всех доступных данных. Так мы получаем эмпирический риск:

$Q(a, X^{\ell}) = \frac{1}{\ell} \sum_{i=1}^{\ell} \mathcal{L}(y_i, a(x_i))$

В нашей аналогии эмпирический риск $Q(a, X^{\ell})$ — это доля ошибок, которые вы делаете, решая старые билеты дома.

Метод минимизации эмпирического риска делает логичный шаг. Раз мы не можем минимизировать ошибку на всех данных мира, давайте найдём алгоритм $a^*$ (или вектор весов $w^*$ ), который доставляет минимум этому функционалу на обучающей выборке:

$a^* = \arg\min_{a \in A} Q(a, X^{\ell})$$

Условия состоятельности и переобучение

Главной проблемой принципа ERM является явление переобучения (overfitting). Возвращаясь к нашей аналогии: если вы просто зазубрите наизусть ответы к билетам прошлых лет, ваш эмпирический риск дома будет равен нулю. Но на реальном экзамене при малейшем изменении формулировки вопроса вы провалитесь (истинный риск $R(a)$ окажется высоким). Модель теряет способность к обобщению.

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

Зачем нужна состоятельность и равномерная сходимость?

Метод ERM называется строго состоятельным, если при увеличении объёма данных до бесконечности ( $\ell \to \infty$ ) ошибка на обучении гарантированно приближается к реальной ошибке в жизни.

Однако простой сходимости для одной фиксированной модели недостаточно. Поскольку во время обучения мы ищем лучшую модель среди огромного семейства $A$ , всегда есть риск найти «везучую» модель, которая случайно показала нулевую ошибку на тренировке, но будет бесполезна в реальности.

Чтобы исключить фактор случайного везения, сходимость должна быть равномерной по всему семейству моделей. Математически это означает, что даже для самой «везучей» модели разница между тренировочной и реальной ошибкой должна стремиться к нулю. Это записывается через предел супремума:

$\lim_{\ell \to \infty} \mathbb{P} \left( \sup_{a \in A} |R(a) - Q(a, X^\ell)| > \epsilon \right) = 0$

Оценка Вапника — Червоненкиса

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

Согласно теореме, для конечной выборки объёмом $\ell$ с вероятностью не менее $1 - \delta$ для любого алгоритма $a \in A$ справедливо неравенство:

$R(a) \le Q(a, X^{\ell}) + \sqrt{\frac{h \left( \ln\left(\frac{2\ell}{h}\right) + 1 \right) - \ln\left(\frac{\delta}{4}\right)}{\ell}}$ ,

где $h$ — VC-размерность (мера сложности) семейства моделей.

Правое слагаемое с квадратным корнем выступает в роли «штрафа за сложность» модели. Из него легко увидеть два фундаментальных правила:

Влияние объёма данных: Чем больше у нас данных $\ell$ , тем меньше штрафной корень. При $\ell \to \infty$ этот корень стремится к нулю, математически доказывая вышеописанный предел равномерной сходимости.
Влияние сложности модели: Чем сложнее семейство моделей $h$ , тем больше штрафной корень и тем выше риск переобучения при фиксированном объёме данных.

Регуляризация

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

Оптимизируемый функционал принимает вид:

$Q_{\text{reg}}(w, X^{\ell}) = \sum_{i=1}^{\ell} \mathcal{L}(y_i, a(x_i, w)) + \tau \mathcal{R}(w) \to \min_{w}$ ,

где $\mathcal{R}(w)$ — функция-регуляризатор, запрещающая параметрам модели принимать слишком большие или сложные значения, а $\tau > 0$ — коэффициент регуляризации.

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

$L_2$ -регуляризация (гребневая, Ridge): $\mathcal{R}(w) = \|w\|_2^2 = \sum_{j=1}^n w_j^2$ . Не даёт весам модели неограниченно расти.
$L_1$ -регуляризация (Lasso): $\mathcal{R}(w) = \|w\|_1 = \sum_{j=1}^n |w_j|$ . Способна занулять малозначимые признаки, упрощая итоговую модель.

Основные типы функций потерь

Выбор функции потерь $\mathcal{L}(y, a(x))$ строго зависит от типа решаемой задачи и природы данных.

В задачах регрессии

В задачах регрессии мы предсказываем действительные числа ( $Y = \mathbb{R}$ ). Типичные функции потерь:

Квадратичная функция потерь (MSE, метод наименьших квадратов):

$\mathcal{L}(y, a(x)) = (a(x) - y)^2$

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

Абсолютная ошибка (MAE, модуль отклонения):

$\mathcal{L}(y, a(x)) = |a(x) - y|$

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

В задачах классификации

В бинарной классификации ответом является класс ( $Y = \{-1, +1\}$ ). Самый естественный выбор — пороговая функция потерь, которая просто штрафует на единицу за несовпадение ответов и даёт ноль при правильном предсказании:

$\mathcal{L}(y, a(x)) = [a(x) \neq y]$

Однако минимизация такой функции на конечной выборке является дискретной NP-полной задачей комбинаторной оптимизации, так как функция потерь имеет вид «ступеньки» (у неё нулевой градиент почти везде, и её невозможно продифференцировать).

Для линейного классификатора $a(x) = \text{sign}(\langle w, x \rangle)$ вводится понятие отступа (margin): $M = y \langle w, x \rangle$ . Пороговая функция потерь выражается через отступ как $[M < 0]$ . Чтобы применить методы градиентной оптимизации, пороговую функцию заменяют её гладкими или кусочно-гладкими верхними оценками $\mathcal{L}(M)$ :

Логистическая функция потерь (применяется в логистической регрессии):

$\mathcal{L}(M) = \log_2(1 + e^{-M})$

Особенности: Гладкая функция. Она плавно штрафует модель даже за правильные, но неуверенные предсказания (когда отступ $M$ положителен, но мал). Это заставляет классификатор не просто угадывать класс, а делать это с максимальной уверенностью.

Кусочно-линейная функция потерь (Hinge loss, применяется в методе опорных векторов, SVM):

$\mathcal{L}(M) = \max(0, 1 - M)$

Особенности: Даёт ровно нулевую ошибку, если объект классифицирован правильно и с хорошим запасом (когда отступ $M \ge 1$ ). Это свойство приводит к тому, что оптимальное решение зависит только от небольшой доли объектов выборки (опорных векторов), делая решение разреженным.

Экспоненциальная функция потерь (применяется в алгоритме AdaBoost):

$\mathcal{L}(M) = e^{-M}$

Особенности: Очень жестко (экспоненциально) наказывает за ошибки (когда отступ $M < 0$ ). Позволяет быстро настраивать композиции алгоритмов, но крайне неустойчива к сильному шуму в данных.

Методы оптимизации

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

Классический градиентный спуск

Исторически базовым алгоритмом является градиентный спуск (Gradient Descent, GD):

$w_t = w_{t-1} - h \nabla_w Q(w_{t-1}, X^{\ell})$

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

$w_t = w_{t-1} - \frac{h}{\ell} \sum_{i=1}^{\ell} \nabla_w \mathcal{L}(y_i, a(x_i, w_{t-1}))$

Разберём, из чего состоит это выражение:

$w_{t-1}$ — вектор весов на предыдущем шаге оптимизации;
$h$ — размер шага (темп обучения, learning rate);
$\nabla_w \mathcal{L}(y_i, a(x_i, w_{t-1}))$ — вектор частных производных (градиент) функции потерь на конкретном $i$ -м объекте. Он показывает направление наискорейшего роста ошибки на этом объекте. Знак «минус» перед ним заставляет нас двигаться в противоположную сторону — в сторону уменьшения ошибки.

Почему классический градиентный спуск работает медленно?

Обрати внимание на знак суммы $\sum_{i=1}^{\ell}$ в формуле выше. Чтобы сделать всего один маленький шаг обновления весов $w_t$ , компьютер вынужден совершить так называемый «полный проход по всей выборке» (full batch pass). То есть процессор должен:

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

Если наш датасет огромен (например, в эпохе Big Data выборка составляет $\ell = 1\,000\ 000$ объектов), то для совершения одной крошечной итерации компьютеру придётся проделать один миллион тяжелых математических операций вычисления градиентов. Классический градиентный спуск в таких условиях работает катастрофически медленно.

Почему стохастический метод (SGD) работает быстрее?

В индустрии машинного и глубокого обучения повсеместно применяется стохастический градиентный спуск (Stochastic Gradient Descent, SGD).

Идея метода заключается в том, что вместо вычисления точного среднего градиента по миллиону объектов, мы оцениваем его по одному случайно выбранному объекту $x_i$ . На каждом шаге веса обновляются мгновенно:

$w_t = w_{t-1} - h \nabla_w \mathcal{L}(y_i, a(x_i, w_{t-1}))$

Вместо вычисления 1 000 000 градиентов мы вычисляем всего один. Пока классический алгоритм будет делать один-единственный тяжелый шаг по всей выборке, метод SGD успеет сделать миллион быстрых шагов и уйти далеко вперёд в сторону оптимума. Хотя траектория движения SGD получается шумной и «скачущей» (стохастической), в среднем он сходится к решению в сотни раз быстрее.

На практике чаще всего используется промежуточный пакетный вариант (Mini-batch SGD). При нём шаг делается не по одному объекту, а по небольшой группе объектов (батчу, обычно от 32 до 256 штук). Это снижает случайный шум стохастического градиента и позволяет эффективно распараллеливать вычисления на видеокартах (GPU).

См. также

Примечания

Литература

Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. — 416 с.
Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning, 2nd edition. — Springer, 2009. — 745 с.
Воронцов К. В. Математические методы обучения по прецедентам. — М.: МФТИ, 2012.

Источник — «http://83.149.227.45/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%8D%D0%BC%D0%BF%D0%B8%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D1%80%D0%B8%D1%81%D0%BA%D0%B0»

Категории: Машинное обучение | Математические методы | Теория вычислительного обучения

@@ Строка 1: / Строка 1: @@
 {{well|Статья написана с использованием LLM '''Gemini 3.1 Pro Preview''' и проверена участником Polina Khadralinova}}
+{{TOCright}}
-'''Принцип эмпирической индукции Фрэнсиса Бэкона''' в контексте [[Машинное обучение|машинного обучения]] — это философско-методологическая основа извлечения закономерностей из данных. Сформулированный в XVII веке принцип перехода от частных наблюдений (прецедентов) к общим правилам сегодня является фундаментальной парадигмой [[Обучение по прецедентам|обучения по прецедентам]], математически выраженной через [[Минимизация эмпирического риска|минимизацию эмпирического риска]] (ERM).
+'''Минимизация эмпирического риска''' (англ. ''Empirical Risk Minimization, ERM'') — это фундаментальный принцип машинного обучения. Он заключается в том, что из заданного семейства моделей мы выбираем ту, которая показывает наименьшую ошибку на доступных тренировочных данных.
-С гносеологической точки зрения машинное обучение рассматривается не просто как набор алгоритмов, а как современная математическая технология автоматизации научного метода познания, у истоков которого стоял Фрэнсис Бэкон.
+Поскольку мы никогда не знаем всех возможных данных в природе, мы не можем измерить «истинную» ошибку модели. Принцип ERM постулирует, что вместо недоступной истинной ошибки мы можем опираться на её практическую оценку — эмпирический риск.
-== Исторический контекст ==
+== Введение ==
-Английский философ и политик Фрэнсис Бэкон (1561–1626) в своём фундаментальном труде «Новый Органон» (1620) подверг жёсткой критике формальную дедуктивную логику Аристотеля. Бэкон утверждал, что законы природы невозможно вывести из умозрительных, абстрактных аксиом; их необходимо «расшифровывать» исключительно из фактов опыта<ref>Бэкон Ф. Новый Органон, или Истинные указания для истолкования природы. — 1620.</ref>.
+Задача машинного обучения с учителем формулируется так. У нас есть множество объектов <tex>X</tex> (например, фотографии) и множество допустимых ответов <tex>Y</tex> (например, метки «кошка» или «собака»). Существует скрытая закономерность — идеальное правило <tex>y^*: X \to Y</tex>.
-Для систематизации наблюдений Бэкон предложил использовать так называемые «Таблицы открытия» (таблицы присутствия, отсутствия и степеней). Исследователь должен был фиксировать условия, при которых исследуемое свойство проявляется, отсутствует или меняет свою интенсивность. Исторически эти таблицы можно считать первым прообразом современных [[Выборка|обучающих выборок]] (датасетов) с признаковым описанием.
+Мы не знаем эту закономерность целиком. Нам доступна лишь конечная обучающая выборка <tex>X^{\ell} = \{ (x_i, y_i) \}_{i=1}^{\ell}</tex>.
-== Формализация идей Бэкона в машинном обучении ==
+Наша цель — найти такой алгоритм <tex>a: X \to Y</tex> из заданного семейства моделей <tex>A = \{ a(x, w) \mid w \in W \}</tex>, который не просто запомнит правильные ответы для обучающей выборки, но и сможет эффективно (с минимальным количеством ошибок) работать на новых данных. Ошибку модели на конкретном объекте мы измеряем с помощью функции потерь <tex>\mathcal{L}(y, a(x))</tex>.
-Современная математическая постановка задачи машинного обучения является прямой алгоритмической реализацией бэконовской эмпирической индукции. «Таблица открытия» Бэкона задаётся в машинном обучении как множество прецедентов:
+== Историческая справка ==
-:<tex>X^\ell = \{ x_i \mid i = 1, \dots, \ell \}</tex>,
-где <tex>\ell</tex> — количество доступных наблюдений (опытов).
-Свойства объектов, которые Бэкон призывал тщательно измерять и систематизировать, формализуются через измеряемые признаки (векторное представление):
+Истоки принципа минимизации эмпирического риска восходят к философской концепции [[Эмпирическая индукция|эмпирической индукции]] Фрэнсиса Бэкона (1620 г.), утверждавшего, что законы природы необходимо выводить путём обобщения фактов опыта, а не постулировать умозрительно.
-:<tex>f_j(x)</tex> — <tex>j</tex>-й признак объекта, где <tex>j = 1, \dots, n</tex>.
-Цель бэконовского исследования (поиск «формы» или истинного закона) сводится к предсказанию целевого свойства <tex>y_i</tex>. Алгоритм машинного обучения автоматизирует процесс индукции, подбирая параметрическую модель <tex>a(x, w)</tex>, которая наилучшим образом обобщает частные факты из <tex>X^\ell</tex> на всё пространство объектов <tex>X</tex>.
+В строгой математической форме этот принцип впервые был применён Карлом Фридрихом Гауссом в 1795 году при разработке [[Метод наименьших квадратов|метода наименьших квадратов]] для расчёта орбит небесных тел. Гаусс предложил искать параметры модели, минимизируя сумму квадратов отклонений предсказанных значений от наблюдаемых. Позже, в 1936 году, Рональд Фишер применил схожий принцип для задачи классификации ([[Линейный дискриминантный анализ|линейный дискриминантный анализ]]).
-== Машинное обучение как автоматизация научного метода ==
+Своё современное теоретико-вероятностное обоснование принцип ERM получил в конце 1960-х — начале 1970-х годов в трудах советских математиков В. Н. Вапника и А. Я. Червоненкиса. В рамках созданной ими статистической теории обучения ([[Теория Вапника-Червоненкиса|теории Вапника-Червоненкиса]]) были строго сформулированы условия состоятельности принципа минимизации эмпирического риска и получены оценки скорости сходимости ошибки.
-Индуктивный метод Бэкона тесно связан с современными концепциями [[Эпистемология|эпистемологии]] и философии науки. В парадигме искусственного интеллекта классические шаги научного познания формализуются через строгие математические операции<ref>Воронцов К. В. Философия. Введение в ИИ (курс лекций). — 2026.</ref>:
+== Ожидаемый и эмпирический риск ==
-# '''Наблюдения и измерения:''' Сбор сырых данных и формирование обучающей выборки <tex>X^\ell</tex>. Этот этап соответствует заполнению «Таблиц открытия».
+В теории машинного обучения мы считаем, что данные не появляются из ниоткуда. Существует неизвестное вероятностное распределение <tex>P(x, y)</tex> на пространстве <tex>X \times Y</tex>. Все наши объекты и ответы генерируются независимо из этого распределения.
-# '''Гипотеза (модель):''' Выбор параметрического семейства функций <tex>A = \{a(x, w) \mid w \in W\}</tex>. Модель выступает в роли научной теории, объясняющей данные.
-# '''Принцип верифицируемости (Фрэнсис Бэкон):''' Обучение модели (train) путём оптимизации её параметров. Система ищет подтверждение гипотезы на известных данных через [[Минимизация эмпирического риска|минимизацию функции потерь]] <tex>\mathcal{L}(w, x_i)</tex>.
-# '''Принцип фальсифицируемости (Карл Поппер):''' Проверка (test) обученной модели на новых, отложенных данных. Согласно Попперу, научная теория должна допускать возможность опровержения. В машинном обучении это реализуется через процедуру [[Скользящий контроль|кросс-валидации]]: если модель показывает плохую обобщающую способность на независимом тесте (происходит [[Переобучение|переобучение]]), гипотеза (текущие веса модели) отвергается.
-Таким образом, современные алгоритмы машинного обучения выступают вычислительными инструментами, которые масштабируют философский принцип эмпирической индукции на массивы данных, объём которых недоступен для ручного анализа человеком.
+В идеальном мире мы хотели бы создать модель, которая ошибается как можно реже на любых возможных данных. Эта идеальная мера ошибки называется '''ожидаемым риском''' (или истинным риском). Математически это математическое ожидание функции потерь по всему распределению:
+::<tex>R(a) = \mathbb{E}_{x,y \sim P} [\mathcal{L}(y, a(x))] = \int_{X \times Y} \mathcal{L}(y, a(x)) dP(x, y)</tex>
+'''Интуитивная аналогия:''' Представьте, что вы готовитесь к сложному экзамену. Ожидаемый риск — это ваша реальная оценка на самом экзамене, где вам может попасться абсолютно любой билет по предмету. Мы хотим сдать экзамен на «отлично», то есть свести ожидаемый риск <tex>R(a)</tex> к минимуму.
+Проблема в том, что заранее узнать все вопросы экзамена (распределение <tex>P(x, y)</tex>) невозможно. Поэтому вычислить ожидаемый риск <tex>R(a)</tex> напрямую нельзя.
+'''Зачем нам нужен показатель, который невозможно вычислить?''' Ожидаемый риск — это наш главный теоретический ориентир. Он показывает, насколько хорошо модель работает глобально. Хотя мы не можем рассчитать его напрямую, вся математическая теория машинного обучения построена на поиске путей приблизиться к нему.
+Поскольку у нас нет всех данных мира, мы используем билеты прошлых лет — нашу обучающую выборку <tex>X^{\ell}</tex>. Закон больших чисел говорит нам, что теоретическое математическое ожидание можно оценить на практике, просто усреднив ошибку на всех доступных данных. Так мы получаем '''эмпирический риск''':
+::<tex>Q(a, X^{\ell}) = \frac{1}{\ell} \sum_{i=1}^{\ell} \mathcal{L}(y_i, a(x_i))</tex>
+В нашей аналогии эмпирический риск <tex>Q(a, X^{\ell})</tex> — это доля ошибок, которые вы делаете, решая старые билеты дома.
+Метод минимизации эмпирического риска делает логичный шаг. Раз мы не можем минимизировать ошибку на всех данных мира, давайте найдём алгоритм <tex>a^*</tex> (или вектор весов <tex>w^*</tex>), который доставляет минимум этому функционалу на обучающей выборке:
+::<tex>a^* = \arg\min_{a \in A} Q(a, X^{\ell})$</tex>
+== Условия состоятельности и переобучение ==
+Главной проблемой принципа ERM является явление '''[[Переобучение|переобучения]]''' (overfitting). Возвращаясь к нашей аналогии: если вы просто зазубрите наизусть ответы к билетам прошлых лет, ваш эмпирический риск дома будет равен нулю. Но на реальном экзамене при малейшем изменении формулировки вопроса вы провалитесь (истинный риск <tex>R(a)</tex> окажется высоким). Модель теряет способность к обобщению.
+Чтобы гарантировать, что наш метод обучения на компьютере вообще работает и не является делом чистой случайности, математики ввели понятие состоятельности.
+=== Зачем нужна состоятельность и равномерная сходимость? ===
+Метод ERM называется '''строго состоятельным''', если при увеличении объёма данных до бесконечности (<tex>\ell \to \infty</tex>) ошибка на обучении гарантированно приближается к реальной ошибке в жизни.
+Однако простой сходимости для одной фиксированной модели недостаточно. Поскольку во время обучения мы ищем лучшую модель среди огромного семейства <tex>A</tex>, всегда есть риск найти «везучую» модель, которая случайно показала нулевую ошибку на тренировке, но будет бесполезна в реальности.
+Чтобы исключить фактор случайного везения, сходимость должна быть '''равномерной по всему семейству моделей'''. Математически это означает, что даже для самой «везучей» модели разница между тренировочной и реальной ошибкой должна стремиться к нулю. Это записывается через предел супремума:
+::<tex>\lim_{\ell \to \infty} \mathbb{P} \left( \sup_{a \in A} |R(a) - Q(a, X^\ell)| > \epsilon \right) = 0</tex>
+=== Оценка Вапника — Червоненкиса ===
+Связующим мостом между теорией бесконечных данных и реальной практикой является знаменитая теорема Вапника — Червоненкиса. Она не просто постулирует предел, а математически доказывает его и показывает, с какой скоростью мы к нему приближаемся.
+Согласно теореме, для конечной выборки объёмом <tex>\ell</tex> с вероятностью не менее <tex>1 - \delta</tex> для любого алгоритма <tex>a \in A</tex> справедливо неравенство:
+::<tex>R(a) \le Q(a, X^{\ell}) + \sqrt{\frac{h \left( \ln\left(\frac{2\ell}{h}\right) + 1 \right) - \ln\left(\frac{\delta}{4}\right)}{\ell}}</tex>,
+где <tex>h</tex> — [[Размерность Вапника-Червоненкиса|VC-размерность]] (мера сложности) семейства моделей.
+Правое слагаемое с квадратным корнем выступает в роли '''«штрафа за сложность»''' модели. Из него легко увидеть два фундаментальных правила:
+* '''Влияние объёма данных:''' Чем больше у нас данных <tex>\ell</tex>, тем меньше штрафной корень. При <tex>\ell \to \infty</tex> этот корень стремится к нулю, математически доказывая вышеописанный предел равномерной сходимости.
+* '''Влияние сложности модели:''' Чем сложнее семейство моделей <tex>h</tex>, тем больше штрафной корень и тем выше риск переобучения при фиксированном объёме данных.
+== Регуляризация ==
+Для борьбы с переобучением метод ERM модифицируется. Мы не просто минимизируем ошибку на данных, но и штрафуем модель за излишнюю сложность. Этот подход известен как принцип структурной минимизации риска.
+Оптимизируемый функционал принимает вид:
+::<tex>Q_{\text{reg}}(w, X^{\ell}) = \sum_{i=1}^{\ell} \mathcal{L}(y_i, a(x_i, w)) + \tau \mathcal{R}(w) \to \min_{w}</tex>,
+где <tex>\mathcal{R}(w)</tex> — функция-регуляризатор, запрещающая параметрам модели принимать слишком большие или сложные значения, а <tex>\tau > 0</tex> — коэффициент регуляризации.
+Наиболее часто используемые регуляризаторы:
+* '''<tex>L_2</tex>-регуляризация''' (гребневая, Ridge): <tex>\mathcal{R}(w) = \|w\|_2^2 = \sum_{j=1}^n w_j^2</tex>. Не даёт весам модели неограниченно расти.
+* '''<tex>L_1</tex>-регуляризация''' (Lasso): <tex>\mathcal{R}(w) = \|w\|_1 = \sum_{j=1}^n |w_j|</tex>. Способна занулять малозначимые признаки, упрощая итоговую модель.
+== Основные типы функций потерь ==
+Выбор функции потерь <tex>\mathcal{L}(y, a(x))</tex> строго зависит от типа решаемой задачи и природы данных.
+=== В задачах регрессии ===
+В задачах [[Регрессионный анализ|регрессии]] мы предсказываем действительные числа (<tex>Y = \mathbb{R}</tex>). Типичные функции потерь:
+* '''Квадратичная функция потерь''' (MSE, метод наименьших квадратов):
+:<tex>\mathcal{L}(y, a(x)) = (a(x) - y)^2</tex>
+:* ''Особенности:'' Очень чувствительна к аномалиям в данных (выбросам). Поскольку ошибка возводится в квадрат, алгоритм будет изо всех сил пытаться подстроиться под редкие опечатки или шумы в данных, жертвуя качеством на нормальных объектах.
+* '''Абсолютная ошибка''' (MAE, модуль отклонения):
+:<tex>\mathcal{L}(y, a(x)) = |a(x) - y|</tex>
+:* ''Особенности:'' Является робастной (устойчивой) функцией потерь. Она одинаково штрафует за малые и большие отклонения, поэтому просто игнорирует редкие аномальные выбросы, выстраивая наиболее устойчивую зависимость.
+=== В задачах классификации ===
+В бинарной [[Классификация|классификации]] ответом является класс (<tex>Y = \{-1, +1\}</tex>). Самый естественный выбор — пороговая функция потерь, которая просто штрафует на единицу за несовпадение ответов и даёт ноль при правильном предсказании:
+::<tex>\mathcal{L}(y, a(x)) = [a(x) \neq y]</tex>
+Однако минимизация такой функции на конечной выборке является дискретной NP-полной задачей комбинаторной оптимизации, так как функция потерь имеет вид «ступеньки» (у неё нулевой градиент почти везде, и её невозможно продифференцировать).
+Для линейного классификатора <tex>a(x) = \text{sign}(\langle w, x \rangle)</tex> вводится понятие отступа (margin): <tex>M = y \langle w, x \rangle</tex>. Пороговая функция потерь выражается через отступ как <tex>[M < 0]</tex>. Чтобы применить методы градиентной оптимизации, пороговую функцию заменяют её гладкими или кусочно-гладкими верхними оценками <tex>\mathcal{L}(M)</tex>:
+* '''Логистическая функция потерь''' (применяется в [[Логистическая регрессия|логистической регрессии]]):
+:<tex>\mathcal{L}(M) = \log_2(1 + e^{-M})</tex>
+:* ''Особенности:'' Гладкая функция. Она плавно штрафует модель даже за правильные, но неуверенные предсказания (когда отступ <tex>M</tex> положителен, но мал). Это заставляет классификатор не просто угадывать класс, а делать это с максимальной уверенностью.
+* '''Кусочно-линейная функция потерь''' (Hinge loss, применяется в [[Метод опорных векторов|методе опорных векторов]], SVM):
+:<tex>\mathcal{L}(M) = \max(0, 1 - M)</tex>
+:* ''Особенности:'' Даёт ровно нулевую ошибку, если объект классифицирован правильно и с хорошим запасом (когда отступ <tex>M \ge 1</tex>). Это свойство приводит к тому, что оптимальное решение зависит только от небольшой доли объектов выборки (опорных векторов), делая решение разреженным.
+* '''Экспоненциальная функция потерь''' (применяется в алгоритме AdaBoost):
+:<tex>\mathcal{L}(M) = e^{-M}</tex>
+:* ''Особенности:'' Очень жестко (экспоненциально) наказывает за ошибки (когда отступ <tex>M < 0</tex>). Позволяет быстро настраивать композиции алгоритмов, но крайне неустойчива к сильному шуму в данных.
+== Методы оптимизации ==
+Когда функция потерь непрерывна и имеет производные по параметрам <tex>w</tex> (или хотя бы субградиенты), задачу минимизации эмпирического риска решают методами численной оптимизации.
+=== Классический градиентный спуск ===
+Исторически базовым алгоритмом является '''градиентный спуск''' (Gradient Descent, GD):
+::<tex>w_t = w_{t-1} - h \nabla_w Q(w_{t-1}, X^{\ell})</tex>
+Распишем эту формулу подробнее, чтобы понять её физический смысл. Поскольку градиент суммы равен сумме градиентов, мы можем подставить формулу эмпирического риска прямо внутрь градиентного шага:
+::<tex>w_t = w_{t-1} - \frac{h}{\ell} \sum_{i=1}^{\ell} \nabla_w \mathcal{L}(y_i, a(x_i, w_{t-1}))</tex>
+Разберём, из чего состоит это выражение:
+* <tex>w_{t-1}</tex> — вектор весов на предыдущем шаге оптимизации;
+* <tex>h</tex> — размер шага (темп обучения, learning rate);
+* <tex>\nabla_w \mathcal{L}(y_i, a(x_i, w_{t-1}))</tex> — вектор частных производных (градиент) функции потерь на конкретном <tex>i</tex>-м объекте. Он показывает направление наискорейшего роста ошибки на этом объекте. Знак «минус» перед ним заставляет нас двигаться в противоположную сторону — в сторону уменьшения ошибки.
+=== Почему классический градиентный спуск работает медленно? ===
+Обрати внимание на знак суммы <tex>\sum_{i=1}^{\ell}</tex> в формуле выше. Чтобы сделать '''всего один маленький шаг''' обновления весов <tex>w_t</tex>, компьютер вынужден совершить так называемый «полный проход по всей выборке» (full batch pass). То есть процессор должен:
+# Вычислить градиенты функции потерь отдельно для каждого из <tex>\ell</tex> объектов нашей обучающей выборки.
+# Сложить все эти векторы градиентов между собой.
+# Разделить сумму на <tex>\ell</tex>, чтобы найти среднее направление спуска.
+Если наш датасет огромен (например, в эпохе Big Data выборка составляет <tex>\ell = 1\,000\ 000</tex> объектов), то для совершения одной крошечной итерации компьютеру придётся проделать один миллион тяжелых математических операций вычисления градиентов. Классический градиентный спуск в таких условиях работает катастрофически медленно.
+=== Почему стохастический метод (SGD) работает быстрее? ===
+В индустрии машинного и глубокого обучения повсеместно применяется '''[[Стохастический градиентный спуск|стохастический градиентный спуск]]''' (Stochastic Gradient Descent, SGD).
+Идея метода заключается в том, что вместо вычисления точного среднего градиента по миллиону объектов, мы оцениваем его по '''одному случайно выбранному''' объекту <tex>x_i</tex>. На каждом шаге веса обновляются мгновенно:
+::<tex>w_t = w_{t-1} - h \nabla_w \mathcal{L}(y_i, a(x_i, w_{t-1}))</tex>
+Вместо вычисления 1 000 000 градиентов мы вычисляем всего один. Пока классический алгоритм будет делать один-единственный тяжелый шаг по всей выборке, метод SGD успеет сделать миллион быстрых шагов и уйти далеко вперёд в сторону оптимума. Хотя траектория движения SGD получается шумной и «скачущей» (стохастической), в среднем он сходится к решению в сотни раз быстрее.
+На практике чаще всего используется промежуточный пакетный вариант (Mini-batch SGD). При нём шаг делается не по одному объекту, а по небольшой группе объектов (батчу, обычно от 32 до 256 штук). Это снижает случайный шум стохастического градиента и позволяет эффективно распараллеливать вычисления на видеокартах (GPU).
 == См. также ==
-* [[Обучение с учителем]]
+* [[Теория Вапника-Червоненкиса]]
-* [[Минимизация эмпирического риска]]
 * [[Переобучение]]
-* [[Скользящий контроль]]
+* [[Регуляризация]]
 == Примечания ==
@@ Строка 43: / Строка 151: @@
 == Литература ==
-* ''Бэкон Ф.'' Сочинения в двух томах. Т. 2. — М.: Мысль, 1978. (Включает «Новый Органон»).
+* {{книга | автор = Вапник В. Н., Червоненкис А. Я. | заглавие = Теория распознавания образов | место = М. | издательство = Наука | год = 1974 | страниц = 416 }}
-* ''Воронцов К. В.'' Математические методы обучения по прецедентам (теория обучения машин). — МФТИ, 2012.
+* {{книга | автор = Вапник В. Н. | заглавие = Восстановление зависимостей по эмпирическим данным | место = М. | издательство = Наука | год = 1979 | страниц = 448 }}
+* {{книга | автор = Hastie T., Tibshirani R., Friedman J. | заглавие = The Elements of Statistical Learning, 2nd edition | издательство = Springer | год = 2009 | страниц = 745 }}
+* {{книга | автор = Воронцов К. В. | заглавие = Математические методы обучения по прецедентам | место = М. | издательство = МФТИ | год = 2012 }}
 [[Категория:Машинное обучение]]
-[[Категория:Философия искусственного интеллекта]]
+[[Категория:Математические методы]]
+[[Категория:Теория вычислительного обучения]]