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

Переменная (или атрибут) <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.