4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 27: | Строка 27: | ||
Основной результат Литлстоуна заключается в том, что при подходящем выборе | Основной результат Литлстоуна заключается в том, что при подходящем выборе <math>\theta</math> и <math>\alpha</math> алгоритм Winnow изучает класс монотонных дизъюнкций k литералов с ошибкой, ограниченной O(k log n). Поскольку алгоритм меняет веса только в случае ошибки, эта ограниченность также гарантирует, что веса останутся достаточно малы, чтобы время вычислений осталось полиномиальным относительно n. При помощи простых преобразований алгоритм Winnow также позволяет получить обучения алгоритмы, эффективные с точки зрения атрибутов, для дизъюнкций и конъюнкций общего вида. Также могут быть изучены различные подклассы ДНФ-формул и списков решений [8]. | ||
Winnow достаточно устойчив к шумам, т.е. к ошибкам во входных данных. Это чрезвычайно важно для практического применения алгоритма. Теперь исключим предположение о том, что целевая функция | 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]. | ||
Правило обновления (1) послужило моделью для целого семейства мультипликативных | Правило обновления (1) послужило моделью для целого семейства ''алгоритмов мультипликативных обновлений''. К примеру, Кивинен и Вармут [7] предложили алгоритм потенцирования градиента Exponentiated Gradient, представляющий собой Winnow, модифицированный для прогнозирования в случае с непрерывными значениями, и показывают, как он может быть обусловлен принципом минимизации относительной энтропии. | ||
Рассмотрим класс функций C, где каждая функция может быть закодирована с использованием O(p(k)log n) бит для некоторого полиномиального значения p. Примером могут служить булевы формулы с k релевантными переменными в случае, когда размер формулы ограничен p(k), игнорируя размер, определяемый переменными. В этом случае мощность C равна |C| = | Рассмотрим класс функций C, где каждая функция может быть закодирована с использованием O(p(k)log n) бит для некоторого полиномиального значения p. Примером могут служить булевы формулы с k релевантными переменными в случае, когда размер формулы ограничен p(k), игнорируя размер, определяемый переменными. В этом случае мощность C равна <math>|C| = 2^{O(p(k) \; log \; n)}</math>. Классический алгоритм деления пополам (см. обсуждение и ссылки в работе [9]) обучает любой класс, состоящий из m булевых функций, с границей ошибки <math>log_2 \; m</math> и, таким образом, формирует эффективный с точки зрения атрибутов алгоритм для такого класса С. Однако время выполнения не будет полиномиальным. Еще один серьезный недостатое алгоримта деления пополам заключается в том, что он не допускает наличия шума. Любопытно, что мультипликативное обновление, схожее с (1), было применено в алгоритме взвешенного большинства Литтлстоуна и Вармута (Weighted Majority) [10], а также в алгоритме агрегации Вовка (Aggregating Algorithm) [14] для выполнения шумоустойчивого обобщения алгоритма деления пополам. | ||
Обучение, эффективное с точки зрения атрибутов, также изучалось в других моделях обучения помимо модели с ограниченной ошибкой – таких как вероятно приближенно корректное обучение [4], обучение с равномерным распределением [ ] и обучение с запросами на членство [ ]. Эта идея впоследствии была развита в обучение с потенциально бесконечным числом атрибутов [ ]. | Обучение, эффективное с точки зрения атрибутов, также изучалось в других моделях обучения помимо модели с ограниченной ошибкой – таких как вероятно приближенно корректное обучение [4], обучение с равномерным распределением [12] и обучение с запросами на членство [3]. Эта идея впоследствии была развита в обучение с потенциально бесконечным числом атрибутов [2]. | ||
== Применение == | == Применение == |
правка