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

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

Winnow достаточно устойчив к шумам, т.е. к ошибкам во входных данных. Это чрезвычайно важно для практического применения алгоритма. Теперь исключим предположение о том, что целевая функция <math>f_* \in C</math> удовлетворяет условию <math>y_t = f_* (x_t)</math> для всех t. Определим ''ошибку атрибута'' пары (x, y) по отношению к функции f как минимальное расстояние Хэмминга между x и x', таким, что f(x') = y. Ошибка атрибута для последовательности попыток по отношению к f является суммой ошибок атрибута отдельных пар <math>(x_t, y_t)</math>. Предполагая, что ошибка атрибута для последовательности попыток не превышает A в отношении некоторой дизъюнкции из k литералов, Ауэр и Вармут [1] показали, что Winnow совершает O(A + k log n) ошибок. Также можно проанализировать шумный сценарий с точки зрения ''кусочно-линейной функции потерь'' [5].