@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] }, }