Winnow (алгоритм) - Winnow (algorithm)

Алгоритм веять является методом от машинного обучения для обучения линейного классификатора из меченых примеров. Он очень похож на алгоритм перцептрона . Однако алгоритм перцептрона использует схему аддитивного обновления веса, в то время как Winnow использует мультипликативную схему, которая позволяет ему работать намного лучше, когда многие измерения не имеют значения (отсюда и его название winnow ). Это простой алгоритм, который хорошо масштабируется для данных большой размерности. Во время обучения Винноу показывают последовательность положительных и отрицательных примеров. Из них он узнает гиперплоскость принятия решений , которую затем можно использовать для обозначения новых примеров как положительных или отрицательных. Алгоритм также может использоваться в условиях онлайн-обучения , где этапы обучения и классификации четко не разделены.

Алгоритм

Базовый алгоритм Winnow1 выглядит следующим образом. Экземпляр пространства , то есть, каждый экземпляр описывается как набор булевозначных функций . Алгоритм поддерживает неотрицательные веса для , которые первоначально установлен в 1, один весовой коэффициент для каждой функции. Когда ученику дают пример , он применяет типичное правило прогнозирования для линейных классификаторов: ${\ Displaystyle Х = \ {0,1 \} ^ {п}}$ ${\ displaystyle w_ {i}}$${\ Displaystyle я \ в \ {1, \ ldots, п \}}$${\ displaystyle (x_ {1}, \ ldots, x_ {n})}$

• Если , то предсказать 1${\ displaystyle \ sum _ {я = 1} ^ {n} w_ {i} x_ {i}> \ Theta}$
• В противном случае прогнозируйте 0

Вот действительное число, которое называется порогом . Вместе с весами порог определяет разделяющую гиперплоскость в пространстве экземпляра. Хорошие оценки получаются, если (см. Ниже). ${\ displaystyle \ Theta}$${\ Displaystyle \ Theta = п / 2}$

Для каждого примера, с которым он представлен, учащийся применяет следующее правило обновления:

• Если пример классифицирован правильно, ничего не делайте.
• Если пример спрогнозирован неправильно и правильный результат был 0, для каждой функции соответствующий вес устанавливается на 0 (шаг понижения). ${\ displaystyle x_ {i} = 1}$${\ displaystyle w_ {i}}$

  ${\ displaystyle \ forall x_ {i} = 1, w_ {i} = 0}$

• Если пример предсказан неверно и правильный результат был равен 1, для каждой функции соответствующий вес умножается на α (этап продвижения). ${\ displaystyle x_ {i} = 1}$${\ displaystyle w_ {i}}$

  ${\ displaystyle \ forall x_ {i} = 1, w_ {i} = \ alpha w_ {i}}$

Типичное значение α равно 2.

Есть много вариантов этого базового подхода. Winnow2 аналогичен, за исключением того, что на шаге понижения веса делятся на α вместо того, чтобы быть равными 0. Balanced Winnow поддерживает два набора весов и, следовательно, две гиперплоскости. Затем это можно обобщить для классификации с несколькими метками .

Границы ошибки

При определенных обстоятельствах можно показать, что количество ошибок, которые Winnow делает при обучении, имеет верхнюю границу, которая не зависит от количества экземпляров, с которыми он был представлен. Если алгоритм использует Winnow1 и на целевой функции , которая является -literal монотонной дизъюнкции задается , то для любой последовательности случаев общее количество ошибок ограничено: . ${\ displaystyle \ alpha> 1}$${\ displaystyle \ Theta \ geq 1 / \ alpha}$${\ displaystyle k}$${\ displaystyle f (x_ {1}, \ ldots, x_ {n}) = x_ {i_ {1}} \ cup \ cdots \ cup x_ {i_ {k}}}$${\ Displaystyle \ альфа К (\ журнал _ {\ альфа} \ Theta +1) + {\ гидроразрыва {п} {\ Theta}}}$

Ссылки