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

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

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

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

См. Дополнительные сведения о машинах опорных векторов и гиперплоскости с максимальным запасом .

Маржа для алгоритмов повышения

Запас для итеративного алгоритма повышения с учетом набора примеров с двумя классами можно определить следующим образом. Классификатору дается пара примеров, где - доменное пространство, а - метка примера. Алгоритм итеративного повышения затем выбирает классификатор на каждой итерации, где есть пространство возможных классификаторов, которые предсказывают реальные значения. Затем эта гипотеза взвешивается по выбору алгоритма повышения. Таким образом , на итерации запас примера можно определить как ${\ Displaystyle (х, у)}$${\ displaystyle x \ in X}$${\ Displaystyle у \ в 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} |}}.}$

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

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

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

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

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

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

Голосовала-персептрон алгоритм представляет собой запас максимизируя алгоритм , основанный на итерационном применении классического персептрона алгоритма.

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

Одна теоретическая мотивация классификаторов маржи состоит в том, что их ошибка обобщения может быть связана с параметрами алгоритма и сроком маржи. Пример такой границы - для алгоритма AdaBoost. Позвольте быть набором примеров, отобранных независимо от распределения . Предположим, что размер VC базового классификатора равен и . Тогда с вероятностью верна оценка ${\ displaystyle S}$${\ displaystyle m}$${\ displaystyle D}$${\ displaystyle d}$${\ Displaystyle м \ 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} (м / д ) / \ theta ^ {2} + \ log (1 / \ delta)}} \ right)}$

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

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