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

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].