On the Tightness of LP Relaxations for Structured Prediction.
Ofer MeshiMehrdad MahdaviDavid A. SontagPublished in: CoRR (2015)
Keyphrases
- structured prediction
- lp relaxation
- linear programming
- message passing
- linear program
- optimal solution
- maximum margin
- approximate inference
- lower bound
- integer programming
- knapsack problem
- conditional random fields
- feasible solution
- energy minimization
- latent variables
- integer program
- maximum a posteriori
- markov networks
- global constraints
- efficient learning
- objective function
- convex optimization
- belief propagation
- valid inequalities
- np hard
- distributed systems
- graphical models
- belief networks
- markov random field
- upper bound
- learning algorithm
- computer vision
- pairwise
- graph cuts
- energy function
- genetic algorithm