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

Здесь приводится базовая формулировка, использующая онлайновую модель с ограниченной ошибкой, которая была использована Литтлстоуном [9] в его основополагающей работе.

Зафиксируем класс C булевых функций над n переменными. Для запуска сценария обучения выбирается ''целевая функция'' <math>f_* \in C</math>, однако она не раскрывается ''алгоритму обучения''. Затем выполняется обучение, состоящее из последовательности ''попыток''. В ходе попытки t алгоритму обучения подаются на вход данные <math>x_t \in \{ 0, 1 \}^n</math>. После этого алгоритм обучения выдает свой ''прогноз'' <math>\hat{y}_t</math>, который является его предположением о неизвестном значении <math>f_* (x_t)</math>. Затем ученику раскрывается правильное значение <math>y_t = f_* (x_t)</math>. Если <math>y_t \ne \hat{y}_t</math>, то алгоритм обучения допустил ''ошибку''. Мы говорим, что алгоритм обучения изучает C с ошибкой, ограниченной m, если количество ошибок никогда не превышает m независимо от того, сколько попыток было сделано и как были выбраны <math>f_*</math> и <math>x_1, x_2, ...</math>.

Переменная (или атрибут) <math>X_i</math> ''релевантна'' для функции <math>f: \{ 0, 1 \}^n \to \{ 0, 1 \}</math>, если <math>f(x_1, ..., x_i, ..., x_n) \ne f(x_1, ..., 1 - x_i, ..., x_n)</math> для некоторого <math>\vec x \in 0, 1^n</math>. Предположим теперь, что для некоторого значения <math>k \le n</math> каждая функция <math>f \in C</math> имеет не более k релевантных переменных. Утверждается, что алгоритм обучения изучает класс C ''эффективно с точки зрения атрибутов'', если он изучает C с ошибкой, ограниченной полиномом от k и log n. Кроме того, обычно требуется, чтобы время вычисления для каждой попытки было полиномиальным от n.

Основная часть нынешнего алгоритма обучения, эффективного с точки зрения атрибутов, основывается на алгоритме Литтлстоуна – Winnow [9].

Базовая версия алгоритма 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> обновляется согласно правилу

\alpha w_{t, i}, \; esli \; y_t = 1, \hat{y}_t = 0, x_{t, i} = 1 \\

w_{t, i} / \alpha, \; esli \; y_t = 0, \hat{y}_t = 1, x_{t, i} = 1 \\

w_{t, i} \; v \; protivnom \; sluchae

Основной результат Литлстоуна заключается в том, что при подходящем выборе <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].

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

Рассмотрим класс функций 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] для выполнения шумоустойчивого обобщения алгоритма деления пополам.

Онлайновые алгоритмы обучения естественным образом находят применение в обработке сигналов. Предположим, что отправитель излучает истинный сигнал yt в момент времени t, для t = 1, 2, 3. В некоторый более поздний момент времени (t + d) приемник получает сигнал zt, представляющий собой сумму исходного сигнала yt и различных эхо предыдущих сигналов yt0, t0 < t, все они искажены случайным шумом. Задача заключается в восстановлении истинного сигнала yt на основе полученных сигналов zt; Zt-i1...: ; Zt-i за некоторый отрезок времени l. В настоящее время эффективные с точки зрения атрибутов алгоритмы для таких задач не используются, предварительные результаты см. в работе [11].

Эффективные с точки зрения атрибутов алгоритмы обучения по духу схожи со статистическими методами, работающими с разреженными моделями. В частности, статистические алгоритмы, использующие регуляризацию L1, тесно связаны с мультипликативными алгоритмами, такими как Winnow и Exponentiated Gradient. Напротив, более классическая регуляризация L2 приводит к тому, что алгоритмы не являются эффективными с точки зрения атрибутов [13].