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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

Ссылки

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

[Statistics_1686-1] Jump up to: ^а ^б Роберт Э. Шапире, Йоав Фройнд, Питер Бартлетт и Ви Сан Ли. (1998) « Повышение разницы: новое объяснение эффективности методов голосования », The Annals of Статистика , 26 (5): 1651–1686.

[2] Манфред Вармут, Карен Глосер и Гуннар Рэтч. Повышение алгоритмов для максимизации мягкой маржи. В Proceedings of Advance in Neural Information Processing Systems 20, 2007, стр. 1585–1592.

[1]

[2]