Efficient Multiplicative updates for Support Vector Machines

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 fac-torization (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. Exploit-ing the connection between SVM and NMF formulation, we show how NMF algorithms can be applied to the SVM prob-lem. Multiplicative updates that we derive for SVM problem also represent novel updates for semi-NMF. Further this uni-fied view yields algorithmic insights in both directions: we demonstrate that the Kernel Adatron algorithm for solv-ing SVMs can be adapted to NMF problems. Experiments demonstrate rapid convergence to good classifiers. We ana-lyze the rates of asymptotic convergence of the updates and establish tight bounds. We test them on several datasets us-ing various kernels and report equivalent classification per-formance to that of a standard SVM.