[VASC Seminar]Fast IKSVM and other Generalizations of Linear SVMs

Title: Fast IKSVM and other Generalizations of Linear SVMs
Speaker: Alexander C. Berg, Yahoo! Research

Date: Monday, Jan 14


Abstract:

We show that one can build histogram intersection kernel SVMs (IKSVMs)
with runtime complexity of the classifier logarithmic in the number of
support vectors as opposed to linear for the standard approach. We
further show that by pre-computing auxiliary tables we can construct an
approximate classifier with constant runtime and space requirements,
independent of the number of support vectors, with negligible loss in
classification accuracy on various tasks.

This result is based on noticing that the IKSVM decision function is a sum
of piece-wise linear functions of each coordinate. We generalize this
notion and show that the resulting classifiers can be learned efficiently.

The practical results are classifiers strictly more general than linear
svms that in practice provide better classification performance for a
range of tasks all at reasonable computational cost.

We also introduce novel features based on multi-level histograms of
oriented edge energy and present experiments on various detection
datasets. On the INRIA pedestrian dataset an approximate IKSVM classifier
based on these features has a miss rate 13% lower at 10^-6 False Positive
Per Window than the linear SVM detector of Dalal and Triggs while being
only twice as slow for classification. On the Daimler Chrysler pedestrian
dataset IKSVM gives comparable accuracy to the best results (based on
quadratic SVMs), while being 15x faster. In these experiments our
approximate IKSVM is up to 2000x faster than a standard implementation and
requires 200x less memory. Finally we show that a 50x speed up is possible
using approximate IKSVM based on spatial pyramid features on the Caltech
101 dataset with negligible loss of accuracy.

Related Papers:
Histogram intersection kernel for image classification
Generalized Histogram Intersection Kernel for Image Recognition

Biography:
Alex Berg's research concerns computational visual recognition. He is a
research scientist at Yahoo! Research and a visiting scholar at U.C.
Berkeley. He has worked on general object recognition in images, action
recognition in video, human pose identification in images, image parsing,
face recognition, image search, and machine learning for computer vision.
His Ph.D. at U.C. Berkeley developed a novel approach to deformable
template matching. He earned a BA and MA in Mathematics from Johns
Hopkins University.