Transductive Supp ort Vector Machines for Structured Variables

Transductive Supp ort Vector Machines for Structured Variables
Alexander Zien - Max Planck Institute for Biological Cybernetics and Friedrich Miescher Laboratory, Germany Ulf Brefeld - Max Planck Institute for Computer Science, Germany Tobias Scheffer - Max Planck Institute for Computer Science, Germany
We study the problem of learning kernel machines transductively for structured output variables. Transductive learning can be reduced to combinatorial optimization problems over all possible labelings of the unlabeled data. In order to scale transductive learning to structured variables, we transform the corresponding non-convex, combinatorial, constrained optimization problems into continuous, unconstrained optimization problems. The discrete optimization parameters are eliminated and the resulting differentiable problems can be optimized efficiently. We study the effectiveness of the generalized TSVM on multiclass classification and labelsequence learning problems empirically.

Alexander Zien - Max Planck Institute for Biological Cybernetics and Friedrich Miescher Laboratory, Germany
Ulf Brefeld - Max Planck Institute for Computer Science, Germany
Tobias Scheffer - Max Planck Institute for Computer Science, Germany

We study the problem of learning kernel machines transductively for structured output variables. Transductive learning can be reduced to combinatorial optimization problems over all possible labelings of the unlabeled data. In order to scale transductive learning to structured variables, we transform the corresponding non-convex, combinatorial, constrained optimization problems into continuous, unconstrained optimization problems. The discrete optimization parameters are eliminated and the resulting differentiable problems can be optimized efficiently. We study the effectiveness of the generalized TSVM on multiclass classification and labelsequence learning problems empirically.