Классификатор маржи

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

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

Опорное векторное машинное определение поля

Подробности см . в разделе «Машины опорных векторов» и «Гиперплоскость с максимальным запасом» .

Запас на буст алгоритмов

Запас для алгоритма итеративного повышения с учетом набора примеров с двумя классами можно определить следующим образом. Классификатору предоставляется пара примеров, где — доменное пространство, а — метка примера. Затем алгоритм итеративного повышения на каждой итерации выбирает классификатор, где находится пространство возможных классификаторов, которые прогнозируют реальные значения. Затем эта гипотеза взвешивается по выбору алгоритма повышения. Таким образом, на итерации граница примера может быть определена как ${\displaystyle (x,y)}$ ${\displaystyle x\in X}$ ${\displaystyle y\in Y=\{-1,+1\}}$ ${\displaystyle h_{j}\in C}$ ${\displaystyle j}$ ${\displaystyle C}$ ${\displaystyle \alpha _{j}\in R}$ ${\displaystyle t}$ ${\displaystyle x}$

${\displaystyle {\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}.}$

Согласно этому определению, запас положителен, если пример помечен правильно, и отрицателен, если пример помечен неправильно.

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

Примеры алгоритмов на основе маржи

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

Многие алгоритмы повышения полагаются на понятие запаса для придания веса примерам. Если используется выпуклая потеря (как в AdaBoost , LogitBoost и всех членах семейства алгоритмов AnyBoost), то пример с более высоким запасом получит меньший (или равный) вес, чем пример с меньшим запасом. Это приводит к тому, что алгоритм повышения фокусирует внимание на примерах с низкой маржой. В невыпуклых алгоритмах (например , BrownBoost ) запас по-прежнему определяет вес примера, хотя взвешивание немонотонно по отношению к запасу. Существуют алгоритмы повышения, которые, вероятно, максимизируют минимальную маржу (см., например, ^[2] ).

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

Алгоритм проголосовавшего перцептрона — это алгоритм максимизации запаса, основанный на итеративном применении классического алгоритма перцептрона .

Границы ошибки обобщения

Одной из теоретических причин использования классификаторов маржи является то, что их ошибка обобщения может быть связана с параметрами алгоритма и термином маржи. Примером такой границы является алгоритм AdaBoost. ^[1] Пусть это набор примеров, выбранных независимо случайным образом из распределения . Предположим, что VC-размерность базового классификатора равна и . Тогда с вероятностью мы имеем оценку ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle D}$ ${\displaystyle d}$ ${\displaystyle m\geq d\geq 1}$ ${\displaystyle 1-\delta }$

${\displaystyle P_{D}\left({\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}\leq 0\right)\leq P_{S}\left({\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}\leq \theta \right)+O\left({\frac {1}{\sqrt {m}}}{\sqrt {d\log ^{2}(m/d)/\theta ^{2}+\log(1/\delta )}}\right)}$

для всех . ${\displaystyle \theta >0}$

Рекомендации

1. Роберт Э. Шапир, Йоав Фройнд, Питер Бартлетт и Ви Сан Ли. (1998) «Повышение разницы: новое объяснение эффективности методов голосования», The Annals ofStatistics , 26 (5): 1651–1686.
2. Манфред Вармут, Карен Глосер и Гуннар Рэтч. Повышение алгоритмов для максимизации мягкой маржи. В Proceedings of Advance in Neural Information Processing Systems 20, 2007, стр. 1585–1592.