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

Алгоритм машинного обучения

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

Понятие полей важно в нескольких алгоритмах классификации ML, поскольку его можно использовать для ограничения ошибки обобщения этих классификаторов. Эти границы часто показываются с использованием измерения 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 ), то образец с более высоким значением маржи получит меньший (или равный) вес, чем образец с более низким значением маржи. Это приводит к тому, что алгоритм повышения фокусирует вес на образцах с низким значением маржи. В невыпуклых алгоритмах (например, BrownBoost ) маржа по-прежнему диктует вес образца, хотя вес немонотонен по отношению к марже.

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

Одной из теоретических мотиваций для классификаторов с запасом является то, что их ошибка обобщения может быть связана параметрами алгоритма и термином запаса. Примером такой границы является алгоритм 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) «Увеличение разницы: новое объяснение эффективности методов голосования», Анналы статистики , 26(5):1651–1686