Theorem
Number of errors bounded by:
Set q = n
Note: if
xi is an irrelevant feature, ui = 0.
Errors
grow logarithmically with irrelevant features. Empirically,
Perceptron errors grow linearly.
This is
optimal for k-monotone disjunctions:
f(x1, … xn) = xi1 V
xi2 V … V xik