Efficient Multiplicative Updates for Support Vector Machines

Vamsi K. Potluru, Sergie N Plis, Morten Mørup, Vince D. Calhoun

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    The dual formulation of the support vector machine (SVM) objective function is an instance of a nonnegative quadratic programming problem. We reformulate the SVM objective function as a matrix factorization problem which establishes a connection with the regularized nonnegative matrix factorization (NMF) problem. This allows us to derive a novel multiplicative algorithm for solving hard and soft margin SVM. The algorithm follows as a natural extension of the updates for NMF and semi-NMF. No additional parameter setting, such as choosing learning rate, is required. Exploiting the connection between SVM and NMF formulation, we show how NMF algorithms can be applied to the SVM problem. Multiplicative updates that we derive for SVM problem also represent novel updates for semi-NMF. Further this unified view yields algorithmic insights in both directions: we demonstrate that the Kernel Adatron algorithm for solving SVMs can be adapted to NMF problems. Experiments demonstrate rapid convergence to good classifiers. We analyze the rates of asymptotic convergence of the updates and establish tight bounds. We test them on several datasets using various kernels and report equivalent classification performance to that of a standard SVM.
    Original languageEnglish
    Title of host publicationProceedings of the Ninth SIAM International Conference on Data Mining
    Publication date2009
    Pages1220-1231
    Publication statusPublished - 2009
    EventSIAM International Conference on Data Mining 2009 -
    Duration: 1 Jan 2009 → …

    Conference

    ConferenceSIAM International Conference on Data Mining 2009
    Period01/01/2009 → …

    Fingerprint Dive into the research topics of 'Efficient Multiplicative Updates for Support Vector Machines'. Together they form a unique fingerprint.

    Cite this