4446
правок
Обучение, эффективное с точки зрения атрибутов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обучение, эффективное с точки зрения атрибутов (посмотреть исходный код)
Версия от 14:55, 2 октября 2020
, 2 октября 2020→Постановка задачи
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
Переменная (или атрибут) <math>X_i</math> ''релевантна'' для функции <math>f: \{ 0, 1 \}^n \to \{ 0, 1 \}</math>, если <math>f(x_1, ..., x_i, ..., x_n) \ne f(x_1, ..., 1 - x_i, ..., x_n)</math> для некоторого <math>\vec x \in 0, 1^n</math>. Предположим теперь, что для некоторого значения <math>k \le n</math> каждая функция <math>f \in C</math> имеет не более k релевантных переменных. Утверждается, что алгоритм обучения изучает класс C ''эффективно с точки зрения атрибутов'', если он изучает C с ошибкой, ограниченной полиномом от k и log n. Кроме того, обычно требуется, чтобы время вычисления для каждой попытки было полиномиальным от n. | Переменная (или атрибут) <math>X_i</math> ''релевантна'' для функции <math>f: \{ 0, 1 \}^n \to \{ 0, 1 \}</math>, если <math>f(x_1, ..., x_i, ..., x_n) \ne f(x_1, ..., 1 - x_i, ..., x_n)</math> выполняется для некоторого <math>\vec x \in 0, 1^n</math>. Предположим теперь, что для некоторого значения <math>k \le n</math> каждая функция <math>f \in C</math> имеет не более k релевантных переменных. Утверждается, что алгоритм обучения изучает класс C ''эффективно с точки зрения атрибутов'', если он изучает C с ошибкой, ограниченной полиномом от k и log n. Кроме того, обычно требуется, чтобы время вычисления для каждой попытки было полиномиальным от n. | ||
==Основные результаты == | ==Основные результаты == | ||