Multiplicative Updates for Nonnegative Quadratic Programming in Support Vector Machines
Fei Sha, Lawrence K. Saul, D. D. Lee · ScholarlyCommons (University of Pennsylvania) · 2002
Many problems in neural computation and statistical learning involve optimizations with nonnegativity constraints. In this paper, we study convex problems in quadratic programming where the optimization is confined to an axis-aligned region in the nonnegative orthant. For these problems, we derive multiplicative updates that improve the value of the objective function at each iteration and converge monotonically to the global minimum. The updates have a simple closed form and do not involve any heuristics or free parameters that must be tuned to ensure convergence. Despite their simplicity, they differ strikingly in form from other multiplicative updates used in machine learning. We provide complete proofs of convergence for these updates and describe their application to problems in signal processing and pattern recognition.
Cited by 144 works. Open-access PDF
Authors
References
- Maximum Likelihood from Incomplete Data Via the EM Algorithm
- Statistical Learning Theory
- A Tutorial on Support Vector Machines for Pattern Recognition
- UCI Repository of machine learning databases
- An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process
- Learning with Kernels
- Learning the parts of objects by non-negative matrix factorization
- Fast Training of Support Vector Machines Using Sequential Minimal Optimization
- Generalized Iterative Scaling for Log-Linear Models
- A TUTORIAL ON SUPPORT VECTOR MACHINES FOR PATTERN RECOGNITION, DATA MINING AND KNOWLEDGE DISCOVERY