Java Structural Support Vector Machine
This is a Java implementation of the Cutting Plane Optimization for Structural Support Vector Machines algorithm proposed by Joachims et al. [1]. It is heavily optimized to run on multi-core machines and uses the new Java 8 streams functionality to distribute computation across all available CPUs. In addition to the linear variant that uses explicit feature maps it also provides interfaces for implementing a kernelized variant based on Joint Tensor Kernels. This software relies on the QP solver provided by the ojAlgo library (www.optimatika.se) -- the only dependency of this implementation.
See the svm.instances package for some example uses of this library. If you want to use the linear variant, you have to implement the SVMStructInstance interface or extend the AbstractSVMStructInstance class. These provide methods for the explicit feature map phi, the loss function, the inference oracle and the separation oracle.
If you want to use the variant based on joint tensor kernels, you have to implement the SVMStructKernelInstance interface. This interface provides methods for a loss function and two kernels, one for the input structures and one for the output structures. As the inference problem and the separation oracle problems are both pre-image problem that depend only on the output kernel, the output kernel has to provide methods for solving said problems. If the output kernel has a sparse, explicitly known feature map, we can apply optimizations specifically for that by having the output kernel implement the AtomicKernel interface. For details on that, see [2].
[1] T. Joachims, T. Finley, and C. N. J. Yu, “Cutting-plane Training of Structural SVMs” Machine Learning Journal, vol. 77, pp. 27–59, 2009.
[2] L. Pfahler, “Explicit and Implicit Feature Maps for Structured Output Prediction”, Master Thesis, Technische Universität Dortmund, 2015.