Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

HIPAD - A Hybrid Interior-Point Alternating Direction Algorithm for Knowledge-Based SVM and Feature Selection

  • Conference paper
  • First Online:

Abstract

We consider classification tasks in the regime of scarce labeled training data in high dimensional feature space, where specific expert knowledge is also available. We propose a new hybrid optimization algorithm that solves the elastic-net support vector machine (SVM) through an alternating direction method of multipliers in the first phase, followed by an interior-point method for the classical SVM in the second phase. Both SVM formulations are adapted to knowledge incorporation. Our proposed algorithm addresses the challenges of automatic feature selection, high optimization accuracy, and algorithmic flexibility for taking advantage of prior knowledge. We demonstrate the effectiveness and efficiency of our algorithm and compare it with existing methods on a collection of synthetic and real-world data.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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

Similar content being viewed by others

References

  1. G. J. Andersen, A., Meszaros, C., Xu, X.: Implementation of interior point methods for large scale linear programming. In: Terlaky, T. (ed.) Interior point methods in mathematical programming, pp. 189–252. Kluwer Academic Publishers (1996)

    Google Scholar 

  2. Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn.3(1), 1–122 (2011)

    Article  Google Scholar 

  3. Combettes, P., Pesquet, J.: Proximal splitting methods in signal processing. In: Bauschke, H.H., Burachik, R.S., Combettes, P.L., Elser, V., Luke, D.R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185–212. Springer, New York (2011)

    Chapter  Google Scholar 

  4. Eckstein, J., Bertsekas, D.: On the douglasrachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program.55(1), 293–318 (1992)

    Article MATH MathSciNet  Google Scholar 

  5. Fung, G, Mangasarian, O., Shavlik, J.: Knowledge-based support vector machine classifiers. In: Advances in Neural Information Processing Systems, pp. 537–544 (2003)

    Google Scholar 

  6. Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl.2(1), 17–40 (1976)

    Article MATH  Google Scholar 

  7. Gertz, E., Wright, S.: Object-oriented software for quadratic programming. ACM Trans. Math. Softw. (TOMS)29(1), 58–81 (2003)

    Article MATH MathSciNet  Google Scholar 

  8. Iman, R.L., Davenport, J.M.: Approximations of the critical region of the fbietkan statistic. Commun. Stat.-Theory Meth.9(6), 571–595 (1980)

    Article  Google Scholar 

  9. Koh, K., Kim, S., Boyd, S.: An interior-point method for large-scale l1-regularized logistic regression. J. Mach. learn. Res.8(8), 1519–1555 (2007)

    MATH MathSciNet  Google Scholar 

  10. Lauer, F., Bloch, G.: Incorporating prior knowledge in support vector machines for classification: a review. Neurocomputing71(7–9), 1578–1594 (2008)

    Article  Google Scholar 

  11. Lewis, D., Yang, Y., Rose, T., Li, F.: Rcv1: a new benchmark collection for text categorization research. J. Mach. Learn. Res.5, 361–397 (2004)

    Google Scholar 

  12. Mizuno, S.: Polynomiality of infeasible interior point algorithms for linear programming. Math. Program.67, 109–119 (1994)

    Article MATH MathSciNet  Google Scholar 

  13. Pardalos, P.M., Hansen, P.E.: Data Mining and Mathematical Programming. American Mathematical Society, Providence (2008)

    MATH  Google Scholar 

  14. Rockafellar, R.: The multiplier method of hestenes and powell applied to convex programming. J. Optim. Theory Appl.12(6), 555–562 (1973)

    Article MATH MathSciNet  Google Scholar 

  15. Ryali, S., Supekar, K., Abrams, D., Menon, V.: Sparse logistic regression for whole-brain classification of fmri data. NeuroImage51(2), 752–764 (2010)

    Article  Google Scholar 

  16. Shi, J., Yin, W., Osher, S., Sajda, P.: A fast hybrid algorithm for large-scale l 1-regularized logistic regression. J. Mach. Learn. Res.11, 713–741 (2010)

    MATH MathSciNet  Google Scholar 

  17. Sra, S., Nowozin, S., Wright, S.: Optimization for Machine Learning. MIT Press, Cambridge (2011)

    Google Scholar 

  18. Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Series B (Methodological)58(1), 267–288 (1996)

    MATH MathSciNet  Google Scholar 

  19. Vapnik, V.: The nature of statistical learning theory. Springer, New York (2000)

    Book MATH  Google Scholar 

  20. Wang, L., Zhu, J., Zou, H.: The doubly regularized support vector machine. Statistica Sinica16(2), 589–615 (2006)

    MATH MathSciNet  Google Scholar 

  21. Ye, G.-B., Chen, Y., Xie, X.: Efficient variable selection in support vector machines via the alternating direction method of multipliers. In: International Conference on Artificial Intelligence and Statistics, pp. 832–840 (2011)

    Google Scholar 

  22. Zou, H., Hastie, T.: Regularization and variable selection via the elastic net. J. R. Stat. Soc. Series B (Statistical Methodology)67(2), 301–320 (2005)

    Article MATH MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Columbia University, New York, NY, USA

    Zhiwei Qin

  2. Lehigh University, Bethlehem, PA, USA

    Xiaocheng Tang

  3. Siemens Corporation, Corporate Technology, Princeton, NJ, USA

    Ioannis Akrotirianakis & Amit Chakraborty

Authors
  1. Zhiwei Qin

    You can also search for this author inPubMed Google Scholar

  2. Xiaocheng Tang

    You can also search for this author inPubMed Google Scholar

  3. Ioannis Akrotirianakis

    You can also search for this author inPubMed Google Scholar

  4. Amit Chakraborty

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toIoannis Akrotirianakis.

Editor information

Editors and Affiliations

  1. Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida, USA

    Panos M. Pardalos

  2. AT&T Labs Research, Middletown, New Jersey, USA

    Mauricio G.C. Resende

  3. University of Florida, Gainesville, Florida, USA

    Chrysafis Vogiatzis

  4. Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida, USA

    Jose L. Walteros

Appendix

Appendix

figure c
figure d
Fig. 1.
figure 1

Illustration of the early convergence (in approximately 50 iterations) of the feature support for ADMM.

Rights and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper

Qin, Z., Tang, X., Akrotirianakis, I., Chakraborty, A. (2014). HIPAD - A Hybrid Interior-Point Alternating Direction Algorithm for Knowledge-Based SVM and Feature Selection. In: Pardalos, P., Resende, M., Vogiatzis, C., Walteros, J. (eds) Learning and Intelligent Optimization. LION 2014. Lecture Notes in Computer Science(), vol 8426. Springer, Cham. https://doi.org/10.1007/978-3-319-09584-4_28

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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

[8]ページ先頭
©2009-2025 Movatter.jp