skip to main content
10.1145/1273496.1273508acmotherconferencesArticle/Chapter ViewAbstractPublication PagesicmlConference Proceedingsconference-collections
Article

Solving multiclass support vector machines with LaRank

Published: 20 June 2007 Publication History

Abstract

Optimization algorithms for large margin multiclass recognizers are often too costly to handle ambitious problems with structured outputs and exponential numbers of classes. Optimization algorithms that rely on the full gradient are not effective because, unlike the solution, the gradient is not sparse and is very large. The LaRank algorithm sidesteps this difficulty by relying on a randomized exploration inspired by the perceptron algorithm. We show that this approach is competitive with gradient based optimizers on simple multiclass problems. Furthermore, a single LaRank pass over the training examples delivers test error rates that are nearly as good as those of the final solution.

References

[1]
Bakir, G., Hofmann, T., Schölkopf, B., Smola, A. J., Taskar, B., & Vishwanathan, S. V. N. (Eds.). (2007). Predicting structured outputs. MIT Press. in press.
[2]
Bordes, A., & Bottou, L. (2005). The Huller: a simple and efficient online SVM. Machine Learning: ECML 2005 (pp. 505--512). Springer Verlag. LNAI 3720.
[3]
Bordes, A., Ertekin, S., Weston, J., & Bottou, L. (2005). Fast kernel classifiers with online and active learning. Journal of Machine Learning Research, 6, 1579--1619.
[4]
Collins, M. (2002). Discriminative training methods for hidden markov models: theory and experiments with perceptron algorithms. EMNLP '02: Proceedings of the ACL-02 conference on Empirical methods in natural language processing (pp. 1--8). Morristown, NJ: Association for Computational Linguistics.
[5]
Crammer, K., & Singer, Y. (2001). On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2, 265--292.
[6]
Crammer, K., & Singer, Y. (2003). Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research, 3, 951--991.
[7]
Denoyer, L., & Gallinari, P. (2006). The XML document mining challenge. Advances in XML Information Retrieval and Evaluation, 5th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2006. Schloß Dagsthul, Germany.
[8]
Freund, Y., & Schapire, R. E. (1998). Large margin classification using the perceptron algorithm. Machine Learning: Proceedings of the Fifteenth International Conference. San Francisco, CA: Morgan Kaufmann.
[9]
Graepel, T., Herbrich, R., & Williamson, R. C. (2000). From margin to sparsity. In Advances in neural information processing systems, vol. 13, 210--216. MIT Press.
[10]
Hildreth, C. (1957). A quadratic programming procedure. Naval Research Logistics Quarterly, 4, 79--85. Erratum, ibid. p361.
[11]
Hsu, C.-W., & Lin, C.-J. (2002). A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks, 13, 415--425.
[12]
LeCun, Y., Chopra, S., Hadsell, R., HuangFu, J., & Ranzato, M. (2007). A tutorial on energy-based learning. In (Bakir et al., 2007), 192--241. in press.
[13]
Platt, J. (1999). Fast training of support vector machines using sequential minimal optimization. Advances in Kernel Methods - Support Vector Learning (pp. 185--208). MIT Press.
[14]
Rifkin, R. M., & Klautau, A. (2004). In defense of one-vs-all classification. Journal of Machine Learning Research, 5, 101--141.
[15]
Schölkopf, B., & Smola, A. J. (2002). Learning with kernels. MIT Press.
[16]
Taskar, B. (2004). Learning structured prediction models: A large margin approach. Doctoral dissertation, Stanford University.
[17]
Taskar, B., Chatalbashev, V., Koller, D., & Guestrin, C. (2005). Learning structured prediction models: a large margin approach. International Conference on Machine Learning (ICML) (pp. 896--903).
[18]
Tsochantaridis, I., Joachims, T., Hofmann, T., & Altun, Y. (2005). Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6, 1453--1484.
[19]
Weston, J., & Watkins, C. (1998). Multi-class support vector machines (Technical Report CSD-TR-98-04). Department of Computer Science, Royal Holloway, University of London, Egham, UK.

Cited By

View all
  • (2024)Target anti-jamming acquisition method based on machine vision classification technologyAdvanced Fiber Laser Conference (AFL2023)10.1117/12.3023584(298)Online publication date: 18-Mar-2024
  • (2022)Comparative Analysis Of Optimization Techniques On Multi-class SVM2022 3rd International Conference for Emerging Technology (INCET)10.1109/INCET54531.2022.9824946(1-6)Online publication date: 27-May-2022
  • (2022)An Accelerated Coordinate Descent Method for Support Vector Machine2022 8th Iranian Conference on Signal Processing and Intelligent Systems (ICSPIS)10.1109/ICSPIS56952.2022.10043989(1-4)Online publication date: 28-Dec-2022
  • Show More Cited By
  1. Solving multiclass support vector machines with LaRank

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    ICML '07: Proceedings of the 24th international conference on Machine learning
    June 2007
    1233 pages
    ISBN:9781595937933
    DOI:10.1145/1273496
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    • Machine Learning Journal

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 20 June 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Qualifiers

    • Article

    Conference

    ICML '07 & ILP '07
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 140 of 548 submissions, 26%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Target anti-jamming acquisition method based on machine vision classification technologyAdvanced Fiber Laser Conference (AFL2023)10.1117/12.3023584(298)Online publication date: 18-Mar-2024
    • (2022)Comparative Analysis Of Optimization Techniques On Multi-class SVM2022 3rd International Conference for Emerging Technology (INCET)10.1109/INCET54531.2022.9824946(1-6)Online publication date: 27-May-2022
    • (2022)An Accelerated Coordinate Descent Method for Support Vector Machine2022 8th Iranian Conference on Signal Processing and Intelligent Systems (ICSPIS)10.1109/ICSPIS56952.2022.10043989(1-4)Online publication date: 28-Dec-2022
    • (2021)Advanced Intrusion Detection Using Deep Learning-LSTM Network On Cloud Environment2021 Fourth International Conference on Microelectronics, Signals & Systems (ICMSS)10.1109/ICMSS53060.2021.9673607(1-6)Online publication date: 18-Nov-2021
    • (2020)Model-Free Tracker for Multiple Objects Using Joint Appearance and Motion InferenceIEEE Transactions on Image Processing10.1109/TIP.2019.292812329(277-288)Online publication date: 2020
    • (2020)A Novel Pedestrian Orientation Estimation Method for Autonomous DrivingGreen, Smart and Connected Transportation Systems10.1007/978-981-15-0644-4_34(431-449)Online publication date: 24-Mar-2020
    • (2020)Online Budgeted Stochastic Coordinate Ascent for Large-Scale Kernelized Dual Support Vector Machine TrainingPattern Recognition Applications and Methods10.1007/978-3-030-40014-9_2(23-47)Online publication date: 25-Jan-2020
    • (2019)Learning to rank faulty source files for dependent bug reportsBig Data: Learning, Analytics, and Applications10.1117/12.2519226(10)Online publication date: 13-May-2019
    • (2019)Adaptive sampling for UAV trackingNeural Computing and Applications10.1007/s00521-018-03996-8Online publication date: 9-Jan-2019
    • (2019)Drift Detection Using SVM in Structured Object TrackingImage Analysis and Recognition10.1007/978-3-030-27202-9_6(67-76)Online publication date: 8-Aug-2019
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media