4446
правок
Обучение, эффективное с точки зрения атрибутов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обучение, эффективное с точки зрения атрибутов (посмотреть исходный код)
Версия от 13:40, 2 октября 2020
, 2 октября 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
<math>w_{t + 1, i} = | <math>w_{t + 1, i} = | ||
\begin{cases} | \begin{cases} | ||
\alpha w_{t, i} \; if \; y_t = 1, \hat{y}_t = 0, x_{t, i} = 1 \\ | \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} / \alpha: \; if \; y_t = 0, \hat{y}_t = 1, x_{t, i} = 1 \\ | ||
w_{t, i} \; otherwise | w_{t, i}: \; otherwise | ||
\end{cases}</math> | \end{cases}</math> | ||
| Строка 27: | Строка 27: | ||
Основной результат Литлстоуна заключается в том, что при подходящем выборе <math>\theta</math> и <math>\alpha</math> алгоритм Winnow изучает класс монотонных дизъюнкций | Основной результат Литлстоуна заключается в том, что при подходящем выборе <math>\theta</math> и <math>\alpha</math> алгоритм Winnow изучает класс монотонных k-литеральных дизъюнкций с ошибкой, ограниченной O(k log n). Поскольку алгоритм меняет веса только в случае ошибки, эта ограниченность также гарантирует, что веса останутся достаточно малы, чтобы время вычислений оставалось полиномиальным относительно n. При помощи простых преобразований алгоритм Winnow также позволяет получить обучения алгоритмы, эффективные с точки зрения атрибутов, для дизъюнкций и конъюнкций общего вида. Также могут быть изучены различные подклассы ДНФ-формул и списков решений [8]. | ||