Focus of Attention for Linear Predictors
  We present a method to stop the evaluation of a prediction process when the
result of the full evaluation is obvious. This trait is highly desirable in
prediction tasks where a predictor evaluates all its features for every example
in large datasets. We observe that some examples are easier to classify than
others, a phenomenon which is characterized by the event when most of the
features agree on the class of an example. By stopping the feature evaluation
when encountering an easy- to-classify example, the predictor can achieve
substantial gains in computation. Our method provides a natural attention
mechanism for linear predictors where the predictor concentrates most of its
computation on hard-to-classify examples and quickly discards easy-to-classify
ones. By modifying a linear prediction algorithm such as an SVM or AdaBoost to
include our attentive method we prove that the average number of features
computed is O(sqrt(n log 1/sqrt(delta))) where n is the original number of
features, and delta is the error rate incurred due to early stopping. We
demonstrate the effectiveness of Attentive Prediction on MNIST, Real-sim,
Gisette, and synthetic datasets.
