2008 TrainingStructuralSvmswithKerne

• (Yu et al., 2008) ⇒ Chun-Nam John Yu, and Thorsten Joachims. (2008). “Training Structural Svms with Kernels Using Sampled Cuts.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2008). doi:10.1145/1401890.1401985

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Training+structural+svms+with+kernels+using+sampled+cuts%22+2008
• http://portal.acm.org/citation.cfm?doid=1401890.1401985&preflayout=flat#citedby

Quotes

Abstract

Discriminative training for structured outputs has found increasing applications in areas such as natural language processing, bioinformatics, information retrieval, and computer vision. Focusing on large-margin methods, the most general (in terms of loss function and model structure) training algorithms known to date are based on cutting-plane approaches. While these algorithms are very efficient for linear models, their training complexity becomes quadratic in the number of examples when kernels are used. To overcome this bottleneck, we propose new training algorithms that use approximate cutting planes and random sampling to enable efficient training with kernels. We prove that these algorithms have improved time complexity while providing approximation guarantees. In empirical evaluations, our algorithms produced solutions with training and test error rates close to those of exact solvers. Even on binary classification problems where highly optimized conventional training methods exist (e.g. SVM-light), our methods are about an order of magnitude faster than conventional training methods on large datasets, while remaining competitive in speed on datasets of medium size.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 TrainingStructuralSvmswithKerne	Thorsten Joachims Chun-Nam John Yu			Training Structural Svms with Kernels Using Sampled Cuts				10.1145/1401890.1401985