@Article{Franc-LearningM3N-CSC2011,
  IS = { zkontrolovano 21 Nov 2011 },
  UPDATE      = { 2011-11-13 },
  author =     {Franc, Vojt{\v e}ch and Laskov, Pavel},
  title =      {Learning Maximal Margin Markov Networks via Tractable Convex Optimization},
  year =       {2011},
  month =      {April},
  pages =      {25--34},
  journal =    {Control Systems and Computers},
  publisher =  {National Academy of Sciences of Ukraine},
  address =    {Kiev},
  issn =       {0130-5395},
  number =     {2},
  authorship = {60-40},
  annote =     { Learning of Markov networks constitutes a challenging
    optimization problem. Even the predictive step of a general Markov
    network involves solving an NP-complete max-sum problem. By using
    the discriminative approach, learning of the Markov networks from
    noisy examples can be transformed to a convex quadratic program
    with intractably large number of linear constraints. The
    intractable quadratic problem can be attacked by an approximate
    cutting plane (ACP) algorithm . The ACP requires repeatedly
    solving a predictive step for finding the most violated
    constraint. The intractable search for the most violated
    constraint is approximated by using an (approximate) solver for
    the max-sum problem. The use of the approximative max-sum solver
    inside the ACP algorithm brings two important problems. First, the
    ACP algorithm is not guaranteed to converge to the optimal
    solution. Second, the max-sum solvers are time consuming
    algorithms which forbids using the ACP algorithm to large scale
    problems.  In this paper, we show that learning of a general
    Markov network can be expressed as a convex optimization problem
    which is solvable efficiently without calling any external max-sum
    solver. The key idea is to use a linear programing relaxation of
    the max-sum problem directly in the formulation of the learning
    problem.  We show that the proposed learning problem can be solved
    efficiently by the Generalized Proximal Point Algorithm. The
    empirical evaluation shows that our algorithm speeds up learning
    of general Markov networks by a factor of up to 20 compared to the
    ACP algorithm.},
  keywords =   {Maximum Margin Markov Networks, Proximal Point Algorithm },
  project =    {1M0567, FP7-ICT-247525 HUMAVIPS only EU, PERG04-GA-2008-239455 SEMISOL},
  psurl  = {[PDF] },
}