Отступ

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

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

Перейти к: навигация, поиск

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

Статья написана с использованием LLM Gemini(PRO) и проверена участником ~~Danis Sabirov~~

Содержание

1 Отступ (Margin) в машинном обучении
2 Литература

Отступ (Margin) в машинном обучении

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

1. Математическая постановка и виды отступов

Рассмотрим задачу бинарной классификации. Пусть задана обучающая выборка $\mathcal{X} = \{(x_1, y_1), \dots, (x_N, y_N)\}$ , где $x_i \in \mathbf{R}^D$ — вектор признаков объекта, а $y_i \in \{-1, +1\}$ — его истинная метка класса.

Линейный классификатор задается вектором весов $w \in \mathbf{R}^D$ и смещением (порогом) $b \in \mathbf{R}$ . Решающее правило имеет вид:

$a(x) = \text{sign}(\langle w, x \rangle + b)$

Для оценки качества предсказания на конкретном объекте $x_i$ вводятся два связанных понятия отступа:

Функциональный отступ (Functional Margin):

$M_i = y_i (\langle w, x_i \rangle + b)$

Знак $M_i$ указывает на корректность классификации (если $M_i > 0$ , ответ верный), а абсолютная величина $|M_i|$ характеризует уверенность модели. Однако функциональный отступ можно сделать сколь угодно большим простым масштабированием параметров $(w, b) \to (c \cdot w, c \cdot b)$ при $c > 1$ , что не меняет саму разделяющую плоскость.

Геометрический отступ (Geometric Margin):

$\rho_i = \frac{y_i (\langle w, x_i \rangle + b)}{\|w\|} = \frac{M_i}{\|w\|}$

Это евклидово расстояние от точки $x_i$ до разделяющей гиперплоскости $\langle w, x \rangle + b = 0$ . Геометрический отступ инвариантен к масштабированию параметров и имеет строгий геометрический смысл.

2. Принцип maximal'ного отступа (Hard Margin SVM)

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

Зафиксируем функциональный отступ для объектов, лежащих на границе разделяющей полосы, равным единице: $\min_i M_i = 1$ . Тогда ширина полосы между классами составит $\frac{2}{\|w\|}$ . Задача максимизации полосы сводится к задаче квадратичного программирования:

$\min_{w, b} \frac{1}{2} \|w\|^2$

при ограничениях:

$y_i (\langle w, x_i \rangle + b) \geq 1, \quad \forall i \in \{1, \dots, N\}$

3. Мягкий отступ (Soft Margin SVM)

На практике данные редко бывают линейно разделимыми из-за шума и выбросов. Для допуска ошибок классификации вводится концепция «мягкого отступа» с использованием неотрицательных слабинных переменных (slack variables) $\xi_i \geq 0$ .

Оптимизационная задача модифицируется путем добавления штрафа за нарушение отступа:

$\min_{w, b, \xi} \left( \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{N} \xi_i \right)$

при ограничениях:

$y_i (\langle w, x_i \rangle + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad \forall i$

где гиперпараметр $C > 0$ контролирует баланс между максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки классификации на обучающей выборке.

4. Отступ и функции потерь (Margin-based Loss Functions)

В современном машинном обучении задача классификации часто формулируется как минимизация эмпирического риска с использованием аппроксимаций пороговой функции потерь. Различные алгоритмы оптимизируют разные функции отступа $\mathcal{L}(M_i)$ :

Кусочно-линейная функция (Hinge Loss): Используется в SVM.

$\mathcal{L}_{hinge}(M_i) = \max(0, 1 - M_i)$

Штрафует не только за ошибки ( $M_i < 0$ ), но и за неуверенные правильные ответы ( $0 < M_i < 1$ ).

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

$\mathcal{L}_{log}(M_i) = \log(1 + \exp(-M_i))$

Гладкая выпуклая оценка, асимптотически стремящаяся к нулю при $M_i \to +\infty$ .

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

$\mathcal{L}_{exp}(M_i) = \exp(-M_i)$

5. Теоретические гарантии обобщающей способности

Значимость геометрического отступа обосновывается теорией Вапника-Червоненкиса (VC-теория). Размерность Вапника-Червоненкиса $h$ для линейных классификаторов с геометрическим отступом не менее $\rho$ в пространстве, ограниченном сферой радиуса $R$ , ограничена сверху:

$h \leq \min\left(D, \left\lceil \frac{R^2}{\rho^2} \right\rceil \right) + 1$

Чем больше отступ $\rho$ , тем меньше емкость класса функций (VC-размерность), что приводит к более жесткой верхней оценке вероятности ошибки на новых данных.

6. Практические рекомендации и типичные ошибки

Обязательная стандартизация признаков: Поскольку геометрический отступ $\rho$ опирается на евклидову метрику в пространстве признаков, алгоритмы на базе отступа (особенно SVM) критически чувствительны к масштабу данных. Если признаки имеют разный масштаб, разделяющая гиперплоскость будет необоснованно смещена вдоль осей с наибольшей дисперсией. Матрицу $X$ необходимо стандартизировать до среднего $0$ и единичной дисперсии перед обучением.
Выбор ядра (Kernel Trick): Для нелинейно разделимых выборок скалярное произведение $\langle x_i, x_j \rangle$ заменяется ядерной функцией $K(x_i, x_j)$ . В таком нелинейном пространстве понятие отступа сохраняется, однако метрика расстояния искривляется в соответствии с выбранным ядром (например, RBF).

Литература

Cortes C., Vapnik V. Support-vector networks // Machine learning. — 1995. — Vol. 20, no. 3. — P. 273-297.
Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — 738 p.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — Springer, 2009. — 745 p.
Воронцов К. В. Математические методы обучения по прецедентам (курс лекций). — МФТИ, 2011.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9E%D1%82%D1%81%D1%82%D1%83%D0%BF»

@@ Строка 1: / Строка 1: @@
-{{Шаблон:Философия ИИ/Статья создана с помощью ИИ|модель=Gemini Pro|проверка=Укажите_ваше_имя}}
+{{well|Статья написана с использованием LLM '''Gemini(PRO)''' и проверена участником ~~Danis Sabirov~~}}
 == Отступ (Margin) в машинном обучении ==
@@ Строка 6: / Строка 6: @@
 === 1. Математическая постановка и виды отступов ===
-Рассмотрим задачу бинарной классификации. Пусть задана обучающая выборка <tex>$\mathcal{X} = \{(x_1, y_1), \dots, (x_N, y_N)\}$</tex>, где <tex>x_i \in \mathbf{R}^D</tex> — вектор признаков объекта, а <tex>y_i \in \{-1, +1\}</tex> — его истинная метка класса.
+Рассмотрим задачу бинарной классификации. Пусть задана обучающая выборка <tex>\mathcal{X} = \{(x_1, y_1), \dots, (x_N, y_N)\}</tex>, где <tex>x_i \in \mathbf{R}^D</tex> — вектор признаков объекта, а <tex>y_i \in \{-1, +1\}</tex> — его истинная метка класса.
 Линейный классификатор задается вектором весов <tex>w \in \mathbf{R}^D</tex> и смещением (порогом) <tex>b \in \mathbf{R}</tex>. Решающее правило имеет вид:
@@ Строка 15: / Строка 15: @@
 * '''Функциональный отступ (Functional Margin):'''
 :<tex>M_i = y_i (\langle w, x_i \rangle + b)</tex>
-:: Знак <tex>M_i</math> указывает на корректность классификации (если <tex>M_i > 0</tex>, ответ верный), а абсолютная величина <tex>|M_i|</tex> характеризует уверенность модели. Однако функциональный отступ можно сделать сколь угодно большим простым масштабированием параметров <tex>(w, b) \to (c \cdot w, c \cdot b)</tex> при <tex>c > 1</tex>, что не меняет саму разделяющую плоскость.
+:: Знак <tex>M_i</tex> указывает на корректность классификации (если <tex>M_i > 0</tex>, ответ верный), а абсолютная величина <tex>|M_i|</tex> характеризует уверенность модели. Однако функциональный отступ можно сделать сколь угодно большим простым масштабированием параметров <tex>(w, b) \to (c \cdot w, c \cdot b)</tex> при <tex>c > 1</tex>, что не меняет саму разделяющую плоскость.
 * '''Геометрический отступ (Geometric Margin):'''
@@ Строка 21: / Строка 21: @@
 :: Это евклидово расстояние от точки <tex>x_i</tex> до разделяющей гиперплоскости <tex>\langle w, x \rangle + b = 0</tex>. Геометрический отступ инвариантен к масштабированию параметров и имеет строгий геометрический смысл.
-=== 2. Принцип максимального отступа (Hard Margin SVM) ===
+=== 2. Принцип maximal'ного отступа (Hard Margin SVM) ===
-Если выборка линейно разделима, существует бесконечное множество гиперплоскостей, безошибочно разделяющих классы. Метод опорных векторов (Vapnik, Cortes, 1995) постулирует выбор такой гиперплоскостей, которая максимизирует минимальный геометрический отступ по всей обучающей выборке.
+Если выборка линейно разделима, существует бесконечное множество гиперплоскостей, безошибочно разделяющих классы. Метод опорных векторов (Vapnik, Cortes, 1995) постулирует выбор такой гиперплоскости, которая максимизирует минимальный геометрический отступ по всей обучающей выборке.
-Зафиксируем функциональный отступ для объектов, лежащих на границе разделяющей полосы, равным единице: <tex>\min_i M_i = 1</tex>. Тoгда ширина полосы между классами составит <tex>\frac{2}{\|w\|}</tex>. Задача максимизации полосы сводится к задаче квадратичного программирования:
+Зафиксируем функциональный отступ для объектов, лежащих на границе разделяющей полосы, равным единице: <tex>\min_i M_i = 1</tex>. Тогда ширина полосы между классами составит <tex>\frac{2}{\|w\|}</tex>. Задача максимизации полосы сводится к задаче квадратичного программирования:
 :<tex>\min_{w, b} \frac{1}{2} \|w\|^2</tex>
 при ограничениях:
@@ Строка 36: / Строка 36: @@
 при ограничениях:
 :<tex>y_i (\langle w, x_i \rangle + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad \forall i</tex>
-где гиперпараметр <tex>C > 0</tex> контролирует баланс между
+где гиперпараметр <tex>C > 0</tex> контролирует баланс между максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки классификации на обучающей выборке.
+=== 4. Отступ и функции потерь (Margin-based Loss Functions) ===
+В современном машинном обучении задача классификации часто формулируется как минимизация эмпирического риска с использованием аппроксимаций пороговой функции потерь. Различные алгоритмы оптимизируют разные функции отступа <tex>\mathcal{L}(M_i)</tex>:
+* '''Кусочно-линейная функция (Hinge Loss):''' Используется в SVM.
+:<tex>\mathcal{L}_{hinge}(M_i) = \max(0, 1 - M_i)</tex>
+:: Штрафует не только за ошибки (<tex>M_i < 0</tex>), но и за неуверенные правильные ответы (<tex>0 < M_i < 1</tex>).
+* '''Логистическая функция (Logistic Loss):''' Используется в логистической регрессии.
+:<tex>\mathcal{L}_{log}(M_i) = \log(1 + \exp(-M_i))</tex>
+:: Гладкая выпуклая оценка, асимптотически стремящаяся к нулю при <tex>M_i \to +\infty</tex>.
+* '''Экспоненциальная функция (Exponential Loss):''' Используется в алгоритме AdaBoost.
+:<tex>\mathcal{L}_{exp}(M_i) = \exp(-M_i)</tex>
+=== 5. Теоретические гарантии обобщающей способности ===
+Значимость геометрического отступа обосновывается теорией Вапника-Червоненкиса (VC-теория). Размерность Вапника-Червоненкиса <tex>h</tex> для линейных классификаторов с геометрическим отступом не менее <tex>\rho</tex> в пространстве, ограниченном сферой радиуса <tex>R</tex>, ограничена сверху:
+:<tex>h \leq \min\left(D, \left\lceil \frac{R^2}{\rho^2} \right\rceil \right) + 1</tex>
+Чем больше отступ <tex>\rho</tex>, тем меньше емкость класса функций (VC-размерность), что приводит к более жесткой верхней оценке вероятности ошибки на новых данных.
+=== 6. Практические рекомендации и типичные ошибки ===
+* '''Обязательная стандартизация признаков:''' Поскольку геометрический отступ <tex>\rho</tex> опирается на евклидову метрику в пространстве признаков, алгоритмы на базе отступа (особенно SVM) критически чувствительны к масштабу данных. Если признаки имеют разный масштаб, разделяющая гиперплоскость будет необоснованно смещена вдоль осей с наибольшей дисперсией. Матрицу <tex>X</tex> необходимо стандартизировать до среднего <tex>0</tex> и единичной дисперсии перед обучением.
+* '''Выбор ядра (Kernel Trick):''' Для нелинейно разделимых выборок скалярное произведение <tex>\langle x_i, x_j \rangle</tex> заменяется ядерной функцией <tex>K(x_i, x_j)</tex>. В таком нелинейном пространстве понятие отступа сохраняется, однако метрика расстояния искривляется в соответствии с выбранным ядром (например, RBF).
+== Литература ==
+* ''Cortes C., Vapnik V.'' Support-vector networks // Machine learning. — 1995. — Vol. 20, no. 3. — P. 273-297.
+* ''Bishop C. M.'' Pattern Recognition and Machine Learning. — Springer, 2006. — 738 p.
+* ''Hastie T., Tibshirani R., Friedman J.'' The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — Springer, 2009. — 745 p.
+* ''Воронцов К. В.'' Математические методы обучения по прецедентам (курс лекций). — МФТИ, 2011.