Винноу (алгоритм)

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

Алгоритм

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

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

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

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

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

Типичное значение $α$ составляет 2.

Существует множество вариаций этого базового подхода. Веять2 ^[1] аналогичен, за исключением того, что на этапе понижения веса веса делятся на $α,$ а не устанавливаются равными 0. Сбалансированный веялка поддерживает два набора весов и, следовательно, две гиперплоскости. Затем это можно обобщить для классификации по нескольким меткам .

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

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

Ссылки

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

[littlestone88-1] Jump up to: ^а ^б Ник Литтлстоун (1988). «Быстрое обучение при наличии большого количества нерелевантных атрибутов: новый алгоритм с линейным порогом», Machine Learning 285–318 (2) .

[2] Ник Литтлстоун (1989). «Границы ошибок и логарифмические алгоритмы линейно-порогового обучения».Технический отчет UCSC-CRL-89-11, Калифорнийский университет, Санта-Круз.

[1]

[2]