Another Word For It Patrick Durusau on Topic Maps and Semantic Diversity

April 18, 2013

Distributed Dual Decomposition (DDD) in GraphLab

Filed under: GraphLab,Operations Research,Relaxation — Patrick Durusau @ 1:38 pm

Distributed Dual Decomposition (DDD) in GraphLab by Danny Bickson.

From the post:

Our collaborator Dhruv Batra, from Virginia Tech has kindly contributed DDD code for GraphLab. Here are some explanation about the method and how to deploy it.

The full documentation is found here.

Distributed Dual Decomposition

Dual Decomposition (DD), also called Lagrangian Relaxation, is a powerful technique with a rich history in Operations Research. DD solves a relaxation of difficult optimization problems by decomposing them into simpler subproblems, solving these simpler subproblems independently and then combining these solutions into an approximate global solution.

More details about DD for solving Maximum A Posteriori (MAP) inference problems in Markov Random Fields (MRFs) can be found in the following:

D. Sontag, A. Globerson, T. Jaakkola. Introduction to Dual Decomposition for Inference. Optimization for Machine Learning, editors S. Sra, S. Nowozin, and S. J. Wright: MIT Press, 2011.

Always bear in mind that string matching is only one form of subject identification.

Powered by WordPress