A Novel Algorithm for Learning Support Vector Machines with Structured Output Spaces

Abstract

Keywords

Full Paper

Bibtex entry

@TechReport{Franc-CAK-2006-22,
  author =       {Franc, Vojt{\ve}ch and Hlav{\'a}{\vc}, V{\'a}clav},
  title =        {A Novel Algorithm for Learning Support Vector Machines with
                  Structured Output Spaces},
  institution =  {Department of Cybernetics, Faculty of Electrical Engineering
                  Czech Technical University},
  address =      {Prague, Czech Republic},
  year =         {2006},
  month =        {May},
  type =         {Research Report},
  number =       {{K333--22/06}, {CTU--CMP--2006--04}},
  pages =        {21},
  figures =      {6},
  psurl =        {[Franc-TR-2006-04.ps]},
  annote = {This report proposes a novel optimization algorithm for
    learning support vector machines (SVM) classifiers with structured
    output spaces introduced recently by Tsochantaridis
    et. al. Learning structural SVM classifier leads to a special
    instance of quadratic programming (QP) optimization with a huge
    number of constraints. The number of constraints is proportional
    to the cardinality of the output space which makes the QP task
    intractable by classical optimization methods. We propose a novel
    QP solver based on sequential minimal optimization (SMO). Unlike
    the original SMO, we propose a novel strategy for selecting
    variables to be optimized. The strategy aims at selecting such
    variables which yield the maximal improvement of optimization. We
    prove that the algorithm converges in a finite number of
    iterations to the solution which differs from the optimal one at
    most by a prescribed constant.  Experiments performed show that
    the proposed algorithm is very competitive to a cutting plane
    algorithm of Tsochantaridis et. al. The proposed algorithm can be
    easily implemented and it does not require any external QP solver
    in contrary to the cutting plain algorithm.  We demonstrated a
    capability of the algorithm on a problem of learning the Hidden
    Markov Network for color image segmentation and learning a
    structural classifier for car license plate recognition.  },
  keywords =     {support vector machines, structural classification,
                  quadratic programming},
}