Обучение, эффективное с точки зрения атрибутов

Ключевые слова и синонимы

Обучение с нерелевантными атрибутами

Постановка задачи

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

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

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

Основные результаты

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

Базовая версия алгоритма Winnow поддерживает вектор весов wt = (wt;1 ; wt;n) 2 Rn. Прогноз для входных данных xt 2 f0; 1gn задается формулой

где 9 – параметр алгоритма. Изначально w1 = (1; 1); после попытки t каждый компонент вектора wt обновляется согласно правилу

if yt = \y yt = 0 and xt;i = 1

if yt = 0, yt = 1 and xt;i = 1 (1)

в противном случае

где a > 1 – параметр скорости обучения.

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

Применение

Эффективные с точки зрения атрибутов алгоритмы для классов простых функций имеют потенциально перспективное применение в качестве компонентов при обучении для классов более сложных функций. Например, любая монотонная k-членная ДНФ-формула над переменными x1,...xn может быть представлена как монотонная дизъюнкция с k литералами над 2n переменными zA, где zA = Qi2Axi для A С f1 ng. Выполнение алгоритма Winnow с преобразованными входными данными z 2 f0; 1g2n дает нам границу ошибки O(k log2 n) = O(kn). К сожалению, время выполнения будет линейным относительно 2n – по крайней мере, для наивной реализации алгоритма. Хардон и др. [ ] приводят разочаровывающие данные о вычислительной сложности для этого потенциального способа применения.

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

См. также

• Усиление степени сжатия текста
• Обучение работе с ДНФ-формулами

Литература

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)