Abstract
Recent advances have enabled “oracle” classifiers that
can classify across many classes and input distributions
with high accuracy without retraining. However, these
classifiers are relatively heavyweight, so that applying
them to classify video is costly. We show that day-to-day
video exhibits highly skewed class distributions over the
short term, and that these distributions can be classified
by much simpler models. We formulate the problem
of detecting the short-term skews online and exploiting
models based on it as a new sequential decision making
problem dubbed the Online Bandit Problem, and present
a new algorithm to solve it. When applied to recognizing faces in TV shows and movies, we realize end-toend classification speedups of 2.4-7.8×/2.6-11.2× (on
GPU/CPU) relative to a state-of-the-art convolutional
neural network, at competitive accuracy