Аноним

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

Материал из WEGA
м
Строка 3: Строка 3:


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




4551

правка