Fast Support Vector Machines for Structural Kernels
Abstract
In this paper, we propose three important enhancements of the approximate cutting plane algorithm (CPA) to train Support Vector Machines with structural kernels: (i) we exploit a compact yet exact representation of cutting plane models using directed acyclic graphs to speed up both training and classification, (ii) we provide a parallel implementation, which makes the training scale almost linearly with the number of CPUs, and (iii) we propose an alternative sampling strategy to handle class-imbalanced problem and show that theoretical convergence bounds are preserved. The experimental evaluations on three diverse datasets demonstrate the soundness of our approach and the possibility to carry out fast learning and classification with structural kernels.
Cite
Text
Severyn and Moschitti. "Fast Support Vector Machines for Structural Kernels." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2011. doi:10.1007/978-3-642-23808-6_12Markdown
[Severyn and Moschitti. "Fast Support Vector Machines for Structural Kernels." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2011.](https://mlanthology.org/ecmlpkdd/2011/severyn2011ecmlpkdd-fast/) doi:10.1007/978-3-642-23808-6_12BibTeX
@inproceedings{severyn2011ecmlpkdd-fast,
title = {{Fast Support Vector Machines for Structural Kernels}},
author = {Severyn, Aliaksei and Moschitti, Alessandro},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2011},
pages = {175-190},
doi = {10.1007/978-3-642-23808-6_12},
url = {https://mlanthology.org/ecmlpkdd/2011/severyn2011ecmlpkdd-fast/}
}