Просмотр кода страницы Обучение, эффективное с точки зрения атрибутов

== Ключевые слова и синонимы ==
Обучение с нерелевантными атрибутами

== Постановка задачи ==
В данной статье приводится базовая формулировка, использующая ''онлайновую модель с ограниченной ошибкой'', которая была использована Литтлстоуном [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> обновляется согласно правилу (1)

<math>w_{t + 1, i} =
\begin{cases}
\alpha w_{t, i}: \; if \; y_t = 1, \hat{y}_t = 0, x_{t, i} = 1 \\
w_{t, i} / \alpha: \; if \; y_t = 0, \hat{y}_t = 1, x_{t, i} = 1 \\
w_{t, i}: \; otherwise
\end{cases}</math>

где <math>\alpha > 1</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 является суммой ошибок атрибута отдельных пар <math>(x_t, y_t)</math>. Предполагая, что ошибка атрибута последовательности попыток не превышает A в отношении некоторой дизъюнкции из k литералов, Ауэр и Вармут [1] показали, что 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], позволив в результате получить шумоустойчивое обобщение алгоритма деления пополам.


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

== Применение ==
Эффективные с точки зрения атрибутов алгоритмы для классов простых функций имеют потенциально перспективное применение в качестве компонентов при обучении для классов более сложных функций. Например, любая монотонная k-членная ДНФ-формула над переменными <math>x_1,..., x_n</math> может быть представлена как монотонная дизъюнкция с k литералами над <math>2^n</math> переменными <math>z_A</math>, где <math>z_A = \prod_{i \in A} x_i</math> для <math>A \subseteq \{ 1, ..., n \}</math>. Выполнение алгоритма Winnow с преобразованными входными данными <math>z \in \{0, 1 \}^{2^n}</math> дает нам границу ошибки <math>O(k \; log \; 2^n) = O(kn)</math>. К сожалению, время выполнения будет линейным относительно <math>2^n</math> – по крайней мере, для наивной реализации алгоритма. Хардон и др. [6] приводят разочаровывающие данные о вычислительной сложности для этого потенциального способа применения.


Онлайновые алгоритмы обучения естественным образом находят применение в обработке сигналов. Предположим, что отправитель излучает истинный сигнал <math>y_t</math> в момент времени t, для t = 1, 2, 3... . В некоторый более поздний момент времени (t + d) приемник получает сигнал <math>z_t</math>, представляющий собой сумму исходного сигнала <math>y_t</math> и различных эхо предыдущих сигналов <math>y_t', t' < t</math>, все они искажены случайным шумом. Задача заключается в восстановлении истинного сигнала <math>y_t</math> на основе полученных сигналов <math>z_t, z_{t - 1}, ..., z_{t - l}</math> за некоторый отрезок времени <math>l</math>. В настоящее время эффективные с точки зрения атрибутов алгоритмы для таких задач не используются, предварительные результаты см. в работе [11].


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

== См. также ==
* [[Усиление степени сжатия текста]]
* [[Обучение работе с ДНФ-формулами]]

== Литература ==
1.	Auer, P., Warmuth, M.K.: Tracking the best disjunction. Mach. Learn. 32(2), 127-150(1998)

2.	Blum, A., Hellerstein, L., Littlestone, N.: Learning in the presence of finitely or infinitely many irrelevant attributes. J. Comp. Syst. Sci. 50(1), 32^0 (1995)

3.	Bshouty, N., Hellerstein, L.: Attribute-efficient learning in query and mistake-bound models. J. Comp. Syst. Sci. 56(3), 310-319 (1998)

4.	Dhagat, A., Hellerstein, L.: PAC learning with irrelevant attributes. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, pp 64-74. IEEE Computer Society, Los Alamitos (1994)

5.	Gentile, C., Warmuth, M.K.: Linear hinge loss and average margin. In: Kearns, M.J., Solla, S.A., Cohn, D.A. (eds.) Advances in neural information processing systems 11, p. 225-231. MIT Press, Cambridge (1999)

6.	Khardon, R., Roth, D., Servedio, R.A.: Efficiency versus convergence of boolean kernels for on-line learning algorithms. J. Artif. Intell. Res. 24, 341-356 (2005)

7.	Kivinen,J., Warmuth, M.K.: Exponentiated gradient versus gradient descent for linear predictors. Inf. Comp. 132(1), 1-64 (1997)

8.	Klivans, A.R. Servedio, R.A.: Toward attribute efficient learning of decision lists and parities. J. Mach. Learn. Res. 7(Apr), 587-602 (2006)

9.	Littlestone, N.: Learning quickly when irrelevant attributes abound: A new linear threshold algorithm. Mach. Learn. 2(4), 285-318(1988)

10.	Littlestone, N., Warmuth, M.K.: The weighted majority algorithm. Inf. Comp. 108(2), 212-261 (1994)

11.	Martin, R.K., Sethares, W.A., Williamson, R.C., Johnson, Jr., C.R.: Exploiting sparsity in adaptive filters. IEEE Trans. Signal Process. 50(8), 1883-1894 (2002)

12.	Mossel, E., O'Donnell, R., Servedio, R.A.: Learning functions of к relevant variables. J. Comp. Syst. Sci. 69(3), 421-434 (2004)

13.	Ng, A.Y.: Feature selection, Ц vs. L2 regularization, and rotational invariance.In:Greiner, R., Schuurmans, D. (eds.) Proceedings of the 21st International Conference on Machine Learning, pp 615-622. The International Machine Learning Society, Princeton (2004)

14.	Vovk, V.: Aggregating strategies. In: Fulk, M., Case, J. (eds.) Proceedings of the 3rd Annual Workshop on Computational Learning Theory, p. 371-383. Morgan Kaufmann, San Mateo (1990)