4551
правка
Обучение, эффективное с точки зрения атрибутов: различия между версиями
Перейти к навигации
Перейти к поиску
Обучение, эффективное с точки зрения атрибутов (посмотреть исходный код)
Версия от 12:26, 12 сентября 2020
, 12 сентября 2020→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
== Применение == | == Применение == | ||
Эффективные с точки зрения атрибутов алгоритмы для классов простых функций имеют потенциально перспективное применение в качестве компонентов при обучении для классов более сложных функций. Например, любая монотонная k-членная ДНФ-формула над переменными | Эффективные с точки зрения атрибутов алгоритмы для классов простых функций имеют потенциально перспективное применение в качестве компонентов при обучении для классов более сложных функций. Например, любая монотонная 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] приводят разочаровывающие данные о вычислительной сложности для этого потенциального способа применения. | ||