Abstract
In this paper we present and evaluate a simple but effective machine learning algorithm that we call Bitvector Machine: Feature vectors are partitioned along component-wise quantiles and converted into bitvectors that are learned. It is shown that the method is efficient in both training and classification. The effectiveness of the method is analysed theoretically for best and worst-case scenarios. Experiments on high-dimensional synthetic and real world data show a huge speed boost compared to Support Vector Machines with RBF kernel. By tabulating kernel functions, computing medians in linear-time, and exploiting modern processor technology for advanced bitvector operations, we achieve a speed-up of 32 for classification and 48 for kernel evaluation compared to the popular LIBSVM. Although the method does not generally outperform a SVM with RBF kernel it achieves a high classification accuracy and has qualitative advantages over the linear classifier.
Chapter PDF
Similar content being viewed by others
References
Vapnik, V.N., Chervonenkis, A.Y.: Theory of Pattern Recognition. Nauka, USSR (1974) (in Russian)
Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press (2000)
Bordes, A., Ertekin, S., Weston, J., Bottou, L.: Fast Kernel Classifiers with Online and Active Learning. Journal of Machine Learning Research 6, 1579–1619 (2005)
Joachims, T.: Learning to Classify Text using Support Vector Machines. Kluwer (2002)
Tsang, I., Kocsor, A., Kwok, J.T.: Simpler core vector machines with enclosing balls. In: Ghahramani, Z. (ed.) 24th International Conference on Machine Learning (ICML), pp. 911–918. ACM, New York (2007)
Burges, C.J.C.: Simplified Support Vector Decision Rules. In: Proceedings of the Thirteenth International Conference on Machine Learning (ICML), pp. 71–77. Morgan Kaufmann (1996)
DeCoste, D.: Anytime Interval-Valued Outputs for Kernel Machines: Fast Support Vector Machine Classification via Distance Geometry. In: Proceedings of the International Conference on Machine Learning (ICML), pp. 99–106 (2002)
Decoste, D., Mazzoni, D.: Fast query-optimized kernel machine classification via incremental approximate nearest support vectors. In: International Conference on Machine Learning (ICML), pp. 115–122 (2003)
Chang, Y.W., Hsieh, C.J., Chang, K.W., Ringgaard, M., Lin, C.J.: Training and Testing Low-degree Polynomial Data Mappings via Linear SVM. Journal of Machine Learning Research 11, 1471–1490 (2010)
Zhang, K., Lan, L., Wang, Z., Moerchen, F.: Scaling up Kernel SVM on Limited Resources: A Low-rank Linearization Approach. In: International Conference on Artificial Intelligence and Statistics, AISTATS (2012)
Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U.: When Is Nearest Neighbor Meaningful? In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 217–235. Springer, Heidelberg (1998)
Aggarwal, C.C., Hinneburg, A., Keim, D.A.: On the Surprising Behavior of Distance Metrics in High Dimensional Space. In: Van den Bussche, J., Vianu, V. (eds.) ICDT 2001. LNCS, vol. 1973, pp. 420–434. Springer, Heidelberg (2000)
Lowe, D.G.: Object Recognition from Local Scale-Invariant Features. In: International Converence on Computer Vision (ICCV), pp. 1150–1157 (1999)
Stommel, M., Herzog, O.: Binarising SIFT-Descriptors to Reduce the Curse of Dimensionality in Histogram-Based Object Recognition. In: Ślęzak, D., Pal, S.K., Kang, B.-H., Gu, J., Kuroda, H., Kim, T.-h. (eds.) SIP 2009. CCIS, vol. 61, pp. 320–327. Springer, Heidelberg (2009)
Bay, H., Ess, A., Tuytelaars, T., Gool, L.J.V.: Speeded-Up Robust Features (SURF). Computer Vision and Image Understanding 110(3), 346–359 (2008)
Stommel, M., Langer, M., Herzog, O., Kuhnert, K.D.: A Fast, Robust and Low Bit-Rate Representation for SIFT and SURF Features. In: Proc. IEEE International Symposium on Safety, Security, and Rescue Robotics, pp. 278–283 (2011)
Summa, M.G., Bottou, L., Goldfarb, B., Murtagh, F., Pardoux, C., Touati, M. (eds.): Statistical Learning and Data Science. CRC Computer Science & Data Analysis. Chapman & Hall (2011)
Schoelkopf, S.: Learning with Kernels. MIT Press (2001)
Schneegaß, D., Schäfer, A.M., Martinetz, T.: The Intrinsic Recurrent Support Vector Machine. In: European Symposium on Artificial Neural Networks (ESANN), pp. 325–330 (2007)
Gudmundsson, S., Runarsson, T.P., Sigurdsson, S.: Support vector machines and dynamic time warping for time series. In: International Joint Conference on Neural Networks (IJCNN), pp. 2772–2776 (2008)
Permuter, H., Francos, J., Jermyn, I.H.: A study of Gaussian mixture models of colour and texture features for image classification and segmentation. Pattern Recognition 39(4), 695–706 (2006)
Blum, M., Floyd, R., Pratt, V., Rivest, R., Tarjan, R.: Time bounds for selection. J. Comput. System Sci. 7, 448–461 (1973)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)
Voloshynovskiy, S., Koval, O., Beekhof, F., Pun, T.: Random projections based item authentication. In: Proceedings of SPIE Photonics West, Electronic Imaging / Media Forensics and Security, vol. 7254 (2009)
Bentley, J.L.: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9), 509–517 (1975)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008)
Michalowicz, J.V., Nichols, J.M., Bucholtz, F.: Calculation of Differential Entropy for a Mixed Gaussian Distribution. Entropy 10(5), 200–206 (2008)
Silverman, B.W.: Density Estimation for Statistics and Data Analysis. Chapman and Hall, London (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Edelkamp, S., Stommel, M. (2012). The Bitvector Machine: A Fast and Robust Machine Learning Algorithm for Non-linear Problems. In: Flach, P.A., De Bie, T., Cristianini, N. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2012. Lecture Notes in Computer Science(), vol 7523. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33460-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-33460-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33459-7
Online ISBN: 978-3-642-33460-3
eBook Packages: Computer ScienceComputer Science (R0)