Структурная минимизация риска

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

Версия от 07:17, 16 июня 2026; Platon Usaсhev (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Статья написана с использованием LLM OpenAI GPT-5 и проверена участником Platon Usaсhev 11:17, 16 июня 2026 (MSD)


Структурная минимизация риска (СМР, англ. structural risk minimization, SRM) — принцип выбора модели в статистической теории обучения, предложенный В. Н. Вапником и А. Я. Червоненкисом. Он обобщает минимизацию эмпирического риска: вместо того чтобы выбирать самый точный алгоритм на обучающей выборке из одного большого семейства, рассматривают вложенную последовательность семейств возрастающей сложности и выбирают компромисс между ошибкой на обучении и оценкой сложности.

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

Содержание

Риск и эмпирический риск

Пусть объекты и ответы порождаются неизвестным распределением P(x,y). Для алгоритма или функции f задаётся функция потерь L(y,f(x)). Истинный риск равен математическому ожиданию потерь:

R(f)=E_{(x,y)\sim P} L(y,f(x)).

Распределение P неизвестно, поэтому напрямую минимизировать R(f) нельзя. На обучающей выборке

S=\{(x_i,y_i)\}_{i=1}^{m}

минимизируют эмпирический риск

R_{emp}(f)= \frac{1}{m}\sum_{i=1}^{m}L(y_i,f(x_i)).

Принцип минимизации эмпирического риска выбирает

\hat f=\arg\min_{f\in F}R_{emp}(f).

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

Структура семейств

В СМР задаётся последовательность вложенных классов функций

F_1\subset F_2\subset \cdots \subset F_k\subset\cdots,

где сложность классов возрастает. Например, F_k может быть:

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

Для каждого класса находится функция с малым эмпирическим риском:

\hat f_k=\arg\min_{f\in F_k}R_{emp}(f).

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

k^*=\arg\min_k [ R_{emp}(\hat f_k)+\Omega(F_k,m) ].

Здесь \Omega(F_k,m) — верхняя оценка возможного расхождения между эмпирическим и истинным риском. Чем больше обучающая выборка, тем меньше этот штраф; чем сложнее класс функций, тем он больше.

VC-оценка

Классическая форма СМР опирается на VC-размерность. Для бинарной классификации с функцией потерь 0/1 одна из стандартных оценок имеет вид: с вероятностью не меньше 1-\eta для всех f\in F

R(f)\leq R_{emp}(f)+ \sqrt{ \frac{ h(\ln\frac{2m}{h}+1)-\ln\frac{\eta}{4} }{m} },

где h — VC-размерность класса F, m — размер обучающей выборки. Точная форма констант зависит от варианта теоремы, но смысл оценки одинаков: риск ограничивается суммой наблюдаемой ошибки и члена, растущего со сложностью класса.

Для структурной последовательности F_k с VC-размерностями h_k получают семейство оценок

R(\hat f_k)\leq R_{emp}(\hat f_k)+ \Omega(h_k,m,\eta_k),

где уровни доверия \eta_k выбираются так, чтобы \textstyle\sum_k\eta_k\leq\eta. Это позволяет одновременно сравнивать много классов и сохранять вероятностную гарантию.

Геометрическая интерпретация

СМР можно понимать как выбор точки на кривой «качество на обучении — сложность». При переходе от F_1 к более богатым классам эмпирический риск обычно убывает: модель получает больше степеней свободы. Но оценка сложности растёт. Суммарная верхняя оценка истинного риска часто имеет U-образную форму: сначала уменьшается, затем начинает расти.

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

Связь с регуляризацией

Во многих практических алгоритмах СМР проявляется как регуляризация. Если структурные классы задаются ограничением

F_c=\{f:\Omega_0(f)\leq c\},

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

\min_f [ R_{emp}(f)+\lambda\Omega_0(f) ].

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

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

Метод опорных векторов

Классический пример реализации идеи СМР — метод опорных векторов. Для линейных разделяющих поверхностей в пространстве признаков важна не только размерность этого пространства, но и геометрический зазор между классами. Если объекты лежат внутри шара радиуса R, а классификатор имеет зазор \rho, то сложность семейства можно связать с величиной порядка

\frac{R^2}{\rho^2}.

Поэтому максимизация зазора уменьшает оценку сложности и улучшает верхнюю оценку риска. В мягком варианте SVM оптимизация совмещает штраф за ошибки классификации с контролем нормы весов:

\frac{1}{2}w^T w+C\sum_{i=1}^{m}\xi_i\to\min.

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

Сравнение с выбором по контрольной выборке

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

На практике VC-оценки часто слишком пессимистичны, поэтому в прикладном машинном обучении параметры сложности чаще выбирают по контрольной выборке, кросс-валидации или информационным критериям. Тем не менее СМР остаётся важным теоретическим принципом: он объясняет, почему минимальная ошибка на обучении сама по себе не является критерием хорошей модели.

Практическое использование

Идея структурной минимизации риска применяется при выборе:

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

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

Ограничения

Главное ограничение классической СМР состоит в завышенности теоретических верхних оценок. VC-bound даёт гарантию для широкого класса распределений и поэтому часто оказывается слишком осторожным для конкретной задачи. Если использовать такую оценку буквально, можно выбрать чрезмерно простую модель.

Другие ограничения:

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

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

См. также

Литература

  • Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.
  • Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
  • Vapnik V. N. The Nature of Statistical Learning Theory. — Springer, 1995.
  • Vapnik V. N. Statistical Learning Theory. — Wiley, 1998.
  • 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.
  • Burges C. J. C. A tutorial on support vector machines for pattern recognition // Data Mining and Knowledge Discovery. — 1998. — Vol. 2. — P. 121–167.
  • Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — 2nd ed. — Springer, 2009.
Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%80%D0%B8%D1%81%D0%BA%D0%B0»