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

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

Алгоритм

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

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

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

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

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

  ${\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^[1] аналогичен, за исключением того, что на этапе понижения веса делятся на α вместо 0. Сбалансированный Winnow поддерживает два набора весов и, следовательно, две гиперплоскости. Затем это можно обобщить для классификация с несколькими этикетками.

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

В определенных обстоятельствах можно показать, что количество ошибок, которые Winnow делает в процессе обучения, имеет большое значение. верхняя граница это не зависит от количества экземпляров, с которыми он представлен. Если алгоритм Winnow1 использует ${\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 \alpha k(\log _{\alpha }\Theta +1)+{\frac {n}{\Theta }}}$.^[2]

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

1. Ник Литтлстоун (1988). «Быстрое обучение при большом количестве нерелевантных атрибутов: новый алгоритм с линейным порогом», Машинное обучение 285–318(2).
2. Ник Литтлстоун (1989). «Границы ошибок и логарифмические алгоритмы обучения с линейным порогом». Технический отчет UCSC-CRL-89-11, Калифорнийский университет, Санта-Крус.