4551
правка
Обучение, эффективное с точки зрения атрибутов: различия между версиями
Перейти к навигации
Перейти к поиску
Обучение, эффективное с точки зрения атрибутов (посмотреть исходный код)
Версия от 22:00, 11 сентября 2020
, 11 сентября 2020→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Обучение с нерелевантными атрибутами == Постановка задачи…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Здесь приводится базовая формулировка, использующая онлайновую модель с ограниченной ошибкой, которая была использована Литтлстоуном [ ] в его основополагающей работе. | Здесь приводится базовая формулировка, использующая онлайновую модель с ограниченной ошибкой, которая была использована Литтлстоуном [9] в его основополагающей работе. | ||
Зафиксируем класс C булевых функций над n переменными. Для запуска сценария обучения выбирается целевая функция | Зафиксируем класс 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>. | ||
Переменная (или атрибут) Xi релевантна для функции /: {0,1}" ^ {0,1}, если /(xi, ,*,■,*„) ф f(x 1 ; 1 — x i ; xn) выполняется для некоторого x € 0;1n. Предположим теперь, что для некоторых значений k < n каждая функция f 2 C имеет не более k релевантных переменных. Утверждается, что алгоритм обучения изучает класс C эффективно с точки зрения атрибута, если он изучает C с ошибкой, ограниченной полиномом от k и log n. Кроме того, как правило, требуется, чтобы время вычисления для каждой попытки было полиномом от n. | Переменная (или атрибут) Xi ''релевантна'' для функции /: {0,1}" ^ {0,1}, если /(xi, ,*,■,*„) ф f(x 1 ; 1 — x i ; xn) выполняется для некоторого x € 0;1n. Предположим теперь, что для некоторых значений k < n каждая функция f 2 C имеет не более k релевантных переменных. Утверждается, что алгоритм обучения изучает класс C эффективно с точки зрения атрибута, если он изучает C с ошибкой, ограниченной полиномом от k и log n. Кроме того, как правило, требуется, чтобы время вычисления для каждой попытки было полиномом от n. | ||
==Основные результаты == | ==Основные результаты == | ||