4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 33: | Строка 33: | ||
Правило обновления (1) послужило моделью для целого семейства ''алгоритмов мультипликативных обновлений''. К примеру, Кивинен и Вармут [7] предложили алгоритм потенцирования градиента Exponentiated Gradient, представляющий собой Winnow, модифицированный для прогнозирования в случае с непрерывными значениями, и | Правило обновления (1) послужило моделью для целого семейства ''алгоритмов мультипликативных обновлений''. К примеру, Кивинен и Вармут [7] предложили алгоритм потенцирования градиента (Exponentiated Gradient), представляющий собой Winnow, модифицированный для прогнозирования в случае с непрерывными значениями, и показали, как он может быть обусловлен принципом минимизации относительной энтропии. | ||
Рассмотрим класс функций 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], позволив в результате получить шумоустойчивое обобщение алгоритма деления пополам. | ||
правок