Обучение, эффективное с точки зрения атрибутов: различия между версиями

Базовая версия алгоритма Winnow поддерживает вектор весов <math>w_t = (w_{t, 1}, ..., w_{t, n}) \in \mathbb{R}^n</math>. Прогноз для входных данных <math>x_t \in \{ 0, 1 \}^n</math> задается формулой <math>\hat{y}_t = sign \bigg( \sum_{i = 1}^n w_{t, i} \; x_{t, i} - \theta \bigg),</math> где <math>\theta</math> – параметр алгоритма. Изначально <math>w_1 = (1, ..., 1)</math>; после попытки t каждый компонент вектора <math>w_{t, i}</math> обновляется согласно правилу

Основной результат Литлстоуна заключается в том, что при подходящем выборе <math>\theta</math> и <math>\alpha</math> алгоритм Winnow изучает класс монотонных k-литеральных дизъюнкций с ошибкой, ограниченной O(k log n). Поскольку алгоритм меняет веса только в случае ошибки, эта ограниченность также гарантирует, что веса останутся достаточно малы, чтобы время вычислений оставалось полиномиальным относительно n. При помощи простых преобразований алгоритм Winnow также позволяет получить обучения алгоритмы, эффективные с точки зрения атрибутов, для дизъюнкций и конъюнкций общего вида. Также могут быть изучены различные подклассы ДНФ-формул и списков решений [8].

Winnow достаточно устойчив к шумам, т.е. к ошибкам во входных данных. Это чрезвычайно важно для практического применения алгоритма. Теперь исключим предположение о том, что целевая функция <math>f_* \in C</math> удовлетворяет условию <math>y_t = f_* (x_t)</math> для всех t. Определим ''ошибку атрибута'' пары (x, y) по отношению к функции f как минимальное расстояние Хэмминга между x и x', такими, что f(x') = y. Ошибка атрибута последовательности попыток по отношению к f является суммой ошибок атрибута отдельных пар (xt, yt). Предполагая, что ошибка атрибута в последовательности попыток не превышает A в отношении некоторой дизъюнкции из k литералов, Ауэр и Вармут [ ] показали, что Winnow совершает O(A + k log n) ошибок. Также можно проанализировать шумный сценарий с точки зрения ''кусочно-линейной функции потерь'' [5].