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

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

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

Правило обновления (1) послужило моделью для целого семейства мультипликативных алгоритмов обновления. К примеру, Кивинен и Вармут [ ] предложили алгоритм потенцирования градиента Exponentiated Gradient, представляющий собой Winnow, модифицированный для прогнозирования в случае с непрерывными значениями, и показывают, как он может быть обусловлен принципом минимизации относительной энтропии.

Рассмотрим класс функций C, где каждая функция может быть закодирована с использованием O(p(k)log n) бит для некоторого полиномиального значения p. Примером могут служить булевы формулы с k релевантными переменными в случае, когда размер формулы ограничен p(k), игнорируя размер, определяемый переменными. В этом случае мощность C равна |C| = 2O(p(k) log n). Классический алгоритм деления пополам (см. обсуждение и ссылки в работе [ ]) обучает любой класс, состоящий из m булевых функций, с границей ошибки log2 m и, таким образом, формирует эффективный с точки зрения атрибутов алгоритм для такого класса С. Однако время выполнения не будет полиномиальным. Еще один серьезный недостатое алгоримта деления пополам заключается в том, что он не допускает наличия шума. Любопытно, что мультипликативное обновление, схожее с (1), было применено в алгоритме взвешенного большинства Литтлстоуна и Вармута (Weighted Majority) [ ], а также в алгоритме агрегации Вовка (Aggregating Algorithm) [ ] для выполнения шумоустойчивого обобщения алгоритма деления пополам.

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