Multiple Kernel Support Vector Machine Problem Is NP-Complete
2014
In this work a polynomial-time reduction to the NP-complete subset sum problem is followed in order to prove the complexity of Multiple Kernel Support Vector Machine decision problem. The Lagrangian function of the standard Support Vector Machine in its dual form was considered to derive the proof. Results of this derivation allow researchers to properly justify the use of approximate methods, such as heuristics and metaheuristics, when working with multiple kernel learning algorithms.
Keywords:
- Machine learning
- Artificial intelligence
- Structured support vector machine
- Relevance vector machine
- Kernel method
- Radial basis function kernel
- Kernel embedding of distributions
- Polynomial kernel
- Computer science
- Multiple kernel learning
- Least squares support vector machine
- Theoretical computer science
- String kernel
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
1
Citations
NaN
KQI