Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Incremental Parallel Support Vector Machines for Classifying Large-Scale Multi-class Image Datasets

  • Conference paper
  • First Online:
Future Data and Security Engineering (FDSE 2016)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 10018))

Included in the following conference series:

  • 1483 Accesses

Abstract

In this paper, we propose an incremental parallel support vector machines (SVM) training with stochastic gradient descent (SGD) for dealing with the very large number of images and large-scale multi-class on standard personal computers (PCs). The two-class SVM-SGD algorithm is extended in several ways to develop the new incremental parallel multi-class SVM-SGD in large-scale classifications. We propose the balanced batch SGD of SVM (BBatch-SVM-SGD) for trainning two-class classifiers used in the one-versus-all strategy of the multi-class problems and the incremental training process of classifiers in parallel way on multi-core computers. The numerical test results on ImageNet datasets show that our algorithm is efficient compared to the state-of-the-art linear SVM classifiers in terms of training time, correctness and memory requirements.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Sivic, J., Zisserman, A.: Video google: A text retrieval approach to object matching in videos. In: 9th IEEE International Conference on Computer Vision (ICCV 2003), 14–17, October 2003, Nice, France, pp. 1470–1477 (2003)

    Google Scholar 

  2. Li, F., Perona, P.: A bayesian hierarchical model for learning natural scene categories. In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), 20–26 June 2005, San Diego, CA, USA, pp. 524–531 (2005)

    Google Scholar 

  3. Lowe, D.G.: Object recognition from local scale invariant features. In: Proceedings of the 7th International Conference on Computer Vision, pp. 1150–1157 (1999)

    Google Scholar 

  4. Lowe, D.G.: Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vis. 60(2), 91–110 (2004)

    Article  Google Scholar 

  5. MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, vol. 1, pp. 281–297. University of California Press, January 1967

    Google Scholar 

  6. Vapnik, V.: The Nature of Statistical Learning Theory. Springer-Verlag, New York (1995)

    Book  MATH  Google Scholar 

  7. Platt, J.: Fast training of support vector machines using sequential minimal optimization. In: Schölkopf, B., Burges, C., Smola, A. (eds.) Advances in Kernel Methods Support Vector Learning, pp. 185–208 (1999)

    Google Scholar 

  8. Boser, B., Guyon, I., Vapnik, V.: An training algorithm for optimal margin classifiers. In: Proceedings of 5th ACM Annual Workshop on Computational Learning Theory of 5th ACM Annual Workshop on Computational Learning Theory, pp. 144–152. ACM (1992)

    Google Scholar 

  9. Syed, N., Liu, H., Sung, K.: Incremental learning with support vector machines. In: Proceedings of the ACM SIGKDD International Conference on KDD. ACM (1999)

    Google Scholar 

  10. Do, T.N., Poulet, F.: Incremental SVM and visualization tools for bio-medical data mining. In: Proceedings of the European Workshop on Data Mining and Text Mining for Bioinformatics, pp. 14–19 (2003)

    Google Scholar 

  11. Yu, H., Hsieh, C., Chang, K., Lin, C.: Large linear classification when data cannot fit in memory. ACM Trans. Knowl. Discov. Data 5(4), 23: 1–23: 23 (2012)

    Article  Google Scholar 

  12. Doan, T.N., Do, T.N., Poulet, F.: Large scale classifiers for visual classification tasks. Multimedia Tools Appl. 74(4), 1199–1224 (2015)

    Article  Google Scholar 

  13. Poulet, F., Do, T.N.: Mining very large datasets with support vector machine algorithms. In: Camp, O., Filipe, J., Hammoudi, S., Piattini, M. (eds.) Enterprise Information Systems V, pp. 177–184 (2004)

    Google Scholar 

  14. Do, T.N., Poulet, F.: Classifying one billion data with a new distributed svm algorithm. In: RIVF, pp. 59–66 (2006)

    Google Scholar 

  15. Do, T.N., Nguyen, V.H.: A novel speed-up svm algorithm for massive classification tasks. In: IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2008, pp. 215–220. IEEE (2008)

    Google Scholar 

  16. Tong, S., Koller, D.: Support vector machine active learning with applications to text classification. In: proceedings of the 17th International Conference on Machine Learning, pp. 999–1006. ACM (2000)

    Google Scholar 

  17. Do, T.N., Poulet, F.: Mining very large datasets with SVM and visualization. In: proceedings of 7th International Conference on Entreprise Information Systems, pp. 127–134 (2005)

    Google Scholar 

  18. Bordes, A., Ertekin, S., Weston, J., Bottou, L.: Fast kernel classifiers with online and active learning. J. Mach. Learn. Res. 6, 1579–1619 (2005)

    MathSciNet  MATH  Google Scholar 

  19. Do, T.N., Le Thi, H.A.: Massive classification with support vector machines. In: Nguyen, N.T. (ed.) Transactions on Computational Collective Intelligence XVIII. LNCS, vol. 9240, pp. 147–165. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48145-5_8

    Chapter  Google Scholar 

  20. Segata, N., Blanzieri, E.: Fast local support vector machines for large datasets. In: Perner, P. (ed.) MLDM 2009. LNCS (LNAI), vol. 5632, pp. 295–310. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03070-3_22

    Chapter  Google Scholar 

  21. Do, T.-N.: Non-linear classification of massive datasets with a parallel algorithm of local support vector machines. In: Le Thi, H.A., Nguyen, N.T., Do, T.V. (eds.) Advanced Computational Methods for Knowledge Engineering. AISC, vol. 358, pp. 231–241. Springer, Heidelberg (2015)

    Google Scholar 

  22. Do, T.-N., Poulet, F.: Random local SVMs for classifying large datasets. In: Dang, T.K., Wagner, R., Küng, J., Thoai, N., Takizawa, M., Neuhold, E. (eds.) FDSE 2015. LNCS, vol. 9446, pp. 3–15. Springer, Heidelberg (2015). doi:10.1007/978-3-319-26135-5_1

    Chapter  Google Scholar 

  23. Shalev-Shwartz, S., Singer, Y., Srebro, N.: Pegasos: primal estimated sub-gradient solver for SVM. In: Proceedings of the Twenty-Fourth International Conference Machine Learning, pp. 807–814. ACM (2007)

    Google Scholar 

  24. Bottou, L., Bousquet, O.: The tradeoffs of large scale learning. In: Platt, J., Koller, D., Singer, Y., Roweis, S. (eds.) Advances in Neural Information Processing Systems, vol. 20, pp. 161–168 (2008)

    Google Scholar 

  25. Sánchez, J., Perronnin, F.: High-dimensional signature compression for large-scale image classification. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1665–1672 (2011)

    Google Scholar 

  26. Do, T.N.: Parallel multiclass stochastic gradient descent algorithms for classifying million images with very-high-dimensional signatures into thousands classes. Vietnam J. Comput. Sci. 1(2), 107–115 (2014)

    Article  Google Scholar 

  27. Do, T.-N., Poulet, F.: Parallel multiclass logistic regression for classifying large scale image datasets. In: Le Thi, H.A., Nguyen, N.T., Do, T.V. (eds.) Advanced Computational Methods for Knowledge Engineering. AISC, vol. 358, pp. 255–266. Springer, Heidelberg (2015)

    Google Scholar 

  28. Li, F.F., Fergus, R., Perona, P.: Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 object categories. Comput. Vis. Image Underst. 106(1), 59–70 (2007)

    Article  Google Scholar 

  29. Griffin, G., Holub, A., Perona, P.: Caltech-256 Object Category Dataset. Technical Report CNS-TR-2007-001. California Institute of Technology (2007)

    Google Scholar 

  30. Deng, J., Berg, A.C., Li, K., Li, F.F.: What does classifying more than 10, 000 image categories tell us? In: European Conference on Computer Vision, pp. 71–84 (2010)

    Google Scholar 

  31. Doan, T.-N., Do, T.-N., Poulet, F.: Large scale image classification with many classes, multi-features and very high-dimensional signatures. In: Nguyen, N.T., van Do, T., Thi, H.A. (eds.) ICCSAMA 2013. SCI, vol. 479, pp. 105–116. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  32. Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, New York (2000)

    Book  MATH  Google Scholar 

  33. Ben-Akiva, M., Lerman, S.: Discrete Choice Analysis: Theory and Application to Travel Demand. The MIT Press, Cambridge (1985)

    Google Scholar 

  34. Weston, J., Watkins, C.: Support vector machines for multi-class pattern recognition. In: Proceedings of the Seventh European Symposium on Artificial Neural Networks, pp. 219–224 (1999)

    Google Scholar 

  35. Guermeur, Y.: VC theory of large margin multi-category classifiers. J. Mach. Learn. Res. 8, 2551–2594 (2007)

    MathSciNet  MATH  Google Scholar 

  36. Kreßel, U.: Pairwise classification and support vector machines, Advances in Kernel Methods: Support Vector Learning, pp. 255–268 (1999)

    Google Scholar 

  37. Vural, V., Dy, J.: A hierarchical method for multi-class support vector machines. In: Proceedings of the Twenty-First International Conference on Machine Learning, pp. 831–838 (2004)

    Google Scholar 

  38. Benabdeslem, K., Bennani, Y.: Dendogram-based svm for multi-class classification. J. Comput. Inf. Technol. 14(4), 283–289 (2006)

    Article  Google Scholar 

  39. Do, T.N., Lenca, P., Lallich, S.: Classifying many-class high-dimensional fingerprint datasets using random forest of oblique decision trees. Vietnam J. Comput. Sci. 2(1), 3–12 (2015)

    Article  Google Scholar 

  40. Fan, R., Chang, K., Hsieh, C., Wang, X., Lin, C.: LIBLINEAR: a library for large linear classification. J. Mach. Learn. Res. 9(4), 1871–1874 (2008)

    MATH  Google Scholar 

  41. Chang, C.C., Lin, C.J.: LIBSVM : a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2(27), 1–27 (2011)

    Article  Google Scholar 

  42. Japkowicz, N. (ed.): AAAI’Workshop on Learning from Imbalanced Data Sets. Number WS-00-05 in AAAI Tech Report (2000)

    Google Scholar 

  43. Weiss, G.M., Provost, F.: Learning when training data are costly: the effect of class distribution on tree induction. J. Artif. Intell. Res. 19, 315–354 (2003)

    MATH  Google Scholar 

  44. Visa, S., Ralescu, A.: Issues in mining imbalanced data sets - a review paper. In: Midwest Artificial Intelligence and Cognitive Science Conference, Dayton, USA, pp. 67–73 (2005)

    Google Scholar 

  45. Chawla, N.V., Lazarevic, A., Hall, L.O., Bowyer, K.W.: SMOTEBoost: improving prediction of the minority class in boosting. In: Lavrač, N., Gamberger, D., Todorovski, L., Blockeel, H. (eds.) PKDD 2003. LNCS (LNAI), vol. 2838, pp. 107–119. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  46. Liu, X.Y., Wu, J., Zhou, Z.H.: Exploratory undersampling for class-imbalance learning. IEEE Trans. Syst. Man Cybern. Part B 39(2), 539–550 (2009)

    Article  Google Scholar 

  47. Ricamato, M.T., Marrocco, C., Tortorella, F.: Mcs-based balancing techniques for skewed classes: an empirical comparison. In: ICPR, pp. 1–4 (2008)

    Google Scholar 

  48. Domingos, P.: Metacost: a general method for making classifiers cost sensitive. In: International Conference on Knowledge Discovery and Data Mining, pp. 155–164 (1999)

    Google Scholar 

  49. Zhou, Z.H., Liu, X.Y.: On multi-class cost-sensitive learning. In: 21st National Conference on Artificial Intelligence, Boston, MA, USA, pp. 567–572 (2006)

    Google Scholar 

  50. Wang, B.X., Japkowicz, N.: Boosting support vector machines for imbalanced data sets. Knowl. Inf. Syst. 25(1), 1–20 (2010)

    Article  Google Scholar 

  51. Cotter, A., Shamir, O., Srebro, N., Sridharan, K.: Better mini-batch algorithms via accelerated gradient methods. In: Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, pp. 1647–1655 (2011)

    Google Scholar 

  52. Li, M., Zhang, T., Chen, Y., Smola, A.J.: Efficient mini-batch training for stochastic optimization. In: The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014, pp. 661–670 (2014)

    Google Scholar 

  53. Franc, V., Sonnenburg, S.: Optimized cutting plane algorithm for large-scale risk minimization. J. Mach. Learn. Res. 10, 2157–2192 (2009)

    MathSciNet  MATH  Google Scholar 

  54. Vedaldi, A., Zisserman, A.: Efficient additive kernels via explicit feature maps. IEEE Trans. Pattern Anal. Mach. Intell. 34(3), 480–492 (2012)

    Article  Google Scholar 

  55. Wu, J.: Power mean svm for large scale visual classification. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 2344–2351 (2012)

    Google Scholar 

  56. Berg, A., Deng, J., Li, F.F.: Large scale visual recognition challenge 2010, Technical report (2010)

    Google Scholar 

  57. Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: cluster computing with working sets. In: Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, USENIX Association (2010)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Information Technology, Can Tho University, Can Tho, 92100, Vietnam

    Thanh-Nghi Do & Minh-Thu Tran-Nguyen

  2. UMI UMMISCO 209 (IRD/UPMC), Can Tho, Vietnam

    Thanh-Nghi Do

Authors
  1. Thanh-Nghi Do
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Minh-Thu Tran-Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thanh-Nghi Do .

Editor information

Editors and Affiliations

  1. University of Technology, Ho Chi Minh City, Vietnam

    Tran Khanh Dang

  2. Johannes Kepler University , Linz, Austria

    Roland Wagner

  3. Johannes Kepler University , Linz, Austria

    Josef Küng

  4. University of Technology, Ho Chi Minh City, Vietnam

    Nam Thoai

  5. Hosei University , Tokyo, Japan

    Makoto Takizawa

  6. University of Vienna , Wien, Austria

    Erich Neuhold

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing AG

About this paper

Cite this paper

Do, TN., Tran-Nguyen, MT. (2016). Incremental Parallel Support Vector Machines for Classifying Large-Scale Multi-class Image Datasets. In: Dang, T., Wagner, R., Küng, J., Thoai, N., Takizawa, M., Neuhold, E. (eds) Future Data and Security Engineering. FDSE 2016. Lecture Notes in Computer Science(), vol 10018. Springer, Cham. https://doi.org/10.1007/978-3-319-48057-2_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-48057-2_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-48056-5

  • Online ISBN: 978-3-319-48057-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation