Alex Berg

Fast IKSVM and other Generalizations of Linear SVMs Alexander C. Berg

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.