nips nips2007 nips2007-121 knowledge-graph by maker-knowledge-mining

121 nips-2007-Local Algorithms for Approximate Inference in Minor-Excluded Graphs

Source: pdf

Author: Kyomin Jung, Devavrat Shah

Abstract: We present a new local approximation algorithm for computing MAP and logpartition function for arbitrary exponential family distribution represented by a ﬁnite-valued pair-wise Markov random ﬁeld (MRF), say G. Our algorithm is based on decomposing G into appropriately chosen small components; computing estimates locally in each of these components and then producing a good global solution. We prove that the algorithm can provide approximate solution within arbitrary accuracy when G excludes some ﬁnite sized graph as its minor and G has bounded degree: all Planar graphs with bounded degree are examples of such graphs. The running time of the algorithm is Θ(n) (n is the number of nodes in G), with constant dependent on accuracy, degree of graph and size of the graph that is excluded as a minor (constant for Planar graphs). Our algorithm for minor-excluded graphs uses the decomposition scheme of Klein, Plotkin and Rao (1993). In general, our algorithm works with any decomposition scheme and provides quantiﬁable approximation guarantee that depends on the decomposition scheme.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We present a new local approximation algorithm for computing MAP and logpartition function for arbitrary exponential family distribution represented by a ﬁnite-valued pair-wise Markov random ﬁeld (MRF), say G. [sent-5, score-0.177]

2 Our algorithm is based on decomposing G into appropriately chosen small components; computing estimates locally in each of these components and then producing a good global solution. [sent-6, score-0.155]

3 We prove that the algorithm can provide approximate solution within arbitrary accuracy when G excludes some ﬁnite sized graph as its minor and G has bounded degree: all Planar graphs with bounded degree are examples of such graphs. [sent-7, score-0.869]

4 The running time of the algorithm is Θ(n) (n is the number of nodes in G), with constant dependent on accuracy, degree of graph and size of the graph that is excluded as a minor (constant for Planar graphs). [sent-8, score-1.054]

5 Our algorithm for minor-excluded graphs uses the decomposition scheme of Klein, Plotkin and Rao (1993). [sent-9, score-0.296]

6 In general, our algorithm works with any decomposition scheme and provides quantiﬁable approximation guarantee that depends on the decomposition scheme. [sent-10, score-0.391]

7 , Xn ) represented by a pair-wise (undirected) MRF with graph structure G = (V, E), where vertices V = {1, . [sent-15, score-0.284]

8 Similarly, computing marginal is equivalent to computing logpartition function, deﬁned as log Z = log . [sent-28, score-0.312]

9 x∈Σn exp i∈V φi (xi ) + (i,j)∈E ψij (xi , xj ) ˆ In this paper, we will ﬁnd ε-approximation solutions of MAP and log-partition function: that is, x ˆ ˆ and log Z such that: (1 − ε)H(x∗ ) ≤ H(ˆ ) ≤ H(x∗ ), x (1 − ε) log Z ≤ log Z ≤ (1 + ε) log Z. [sent-29, score-0.496]

10 Both problems are NP-hard for exact and even (constant) approximate computation for arbitrary graph G. [sent-34, score-0.328]

11 codes) so that such good graph structure emerges and use the simple algorithm or else use the algorithm as a heuristic. [sent-40, score-0.336]

12 Such an approach has resulted in many interesting recent results starting the Belief Propagation (BP) algorithm designed for Tree graph [1]. [sent-41, score-0.296]

13 The TRW algorithm provides provable upper bound on log-partition function for arbitrary graph [3]However, to the best of authors’ knowledge the error is not quantiﬁed. [sent-52, score-0.557]

14 The second is an approximation algorithm proposed by Globerson and Jaakkola [9] to compute log-partition function using Planar graph decomposition (PDC). [sent-56, score-0.458]

15 PDC uses techniques of [3] in conjunction with known result about exact computation of partition function for binary MRF when G is Planar and the exponential family has speciﬁc form. [sent-57, score-0.14]

16 Their algorithm provides provable upper bound for arbitrary graph. [sent-58, score-0.229]

17 We propose a novel local algorithm for approximate computation of MAP and logpartition function. [sent-62, score-0.133]

18 For any ε > 0, our algorithm can produce an ε-approximate solution for MAP and log-partition function for arbitrary MRF G as long as G excludes a ﬁnite graph as a minor (precise deﬁnition later). [sent-63, score-0.769]

19 For example, Planar graph excludes K3,3 , K5 as a minor. [sent-64, score-0.398]

20 The running time of the algorithm is Θ(n), with constant dependent on ε, the maximum vertex degree of G and the size of the graph that is excluded as minor. [sent-65, score-0.602]

21 Speciﬁcally, for a Planar graph with bounded degree, it takes ≤ C(ε)n time to ﬁnd ε-approximate solution with log log C(ε) = O(1/ε). [sent-66, score-0.535]

22 In general, our algorithm works for any G and we can quantify bound on the error incurred by our algorithm. [sent-67, score-0.191]

23 It is worth noting that our algorithm provides a provable lower bound on log-partition function as well unlike many of previous works. [sent-68, score-0.186]

24 Our algorithm is based on the following idea: First, decompose G into small-size connected components say G1 , . [sent-72, score-0.208]

25 We show that the error in the estimate depends only on the edges removed. [sent-78, score-0.157]

26 This error bound characterization is applicable for arbitrary graph. [sent-79, score-0.194]

27 Klein, Plotkin and Rao [10]introduced a clever and simple decomposition method for minorexcluded graphs to study the gap between max-ﬂow and min-cut for multicommodity ﬂows. [sent-80, score-0.271]

28 2 Preliminaries Here we present useful deﬁnitions and previous results about decomposition of minor-excluded graphs from [10,11]. [sent-86, score-0.229]

29 Now, if H is not a minor of G then we say that G excludes H as a minor. [sent-88, score-0.435]

30 The explanation of the following statement may help understand the deﬁnition: any graph H with r nodes is a minor of Kr , where Kr is a complete graph of r nodes. [sent-89, score-0.808]

31 This is true because one may obtain H by removing edges from Kr that are absent in H. [sent-90, score-0.126]

32 Let Kr,r denote a complete bipartite graph with r nodes in each partition. [sent-92, score-0.289]

33 An important implication of this is as follows: to prove property P for graph G that excludes H, of size r, as a minor, it is sufﬁcient to prove that any graph that excludes Kr,r as a minor has property P. [sent-94, score-1.104]

34 [10] to obtain a good decomposition scheme described next. [sent-97, score-0.189]

35 Deﬁnition 2 ((δ, ∆)-decomposition) Given graph G = (V, E), a randomly chosen subset of edges B ⊂ E is called (δ, ∆) decomposition of G if the following holds: (a) For any edge e ∈ E, Pr(e ∈ B) ≤ δ. [sent-99, score-0.528]

36 , SK be connected components of graph G = (V, E\B) obtained by removing edges of B from G. [sent-103, score-0.492]

37 Then, for any such component Sj , 1 ≤ j ≤ K and any u, v ∈ Sj the shortest-path distance between (u, v) in the original graph G is at most ∆ with probability 1. [sent-104, score-0.279]

38 The existence of (δ, ∆)-decomposition implies that it is possible to remove δ fraction of edges so that graph decomposes into connected components whose diameter is small. [sent-105, score-0.451]

39 We describe a simple and explicit construction of such a decomposition for minor excluded class of graphs. [sent-106, score-0.546]

40 DeC(G, r, ∆) (0) Input is graph G = (V, E) and r, ∆ ∈ N. [sent-108, score-0.256]

41 As stated above, the basic idea is to use the following step recursively (upto depth r of recursion): in each connected component, say S, choose a node arbitrarily and create a breadth-ﬁrst search tree, say T . [sent-131, score-0.152]

42 Clearly, the total running time of such an algorithm is O(r(n + |E|)) for a graph G = (V, E) with |V | = n; with possible parallel implementation across different connected components. [sent-137, score-0.39]

43 The algorithm DeC(G, r, ∆) is designed to provide a good decomposition for class of graphs that exclude Kr,r as a minor. [sent-138, score-0.373]

44 Figure 1 explains the algorithm for a line-graph of n = 9 nodes, which excludes K2,2 as a minor. [sent-139, score-0.182]

45 Lemma 1 If G excludes Kr,r as a minor, then algorithm DeC(G, r, ∆) outputs B which is (r/∆, O(∆))-decomposition of G. [sent-142, score-0.182]

46 It is known that Planar graph excludes K3,3 as a minor. [sent-143, score-0.398]

47 Corollary 1 Given a planar graph G, the algorithm DeC(G, 3, ∆) produces (3/∆, O(∆))decomposition for any ∆ ≥ 1. [sent-145, score-0.553]

48 3 Approximate log Z Here, we describe algorithm for approximate computation of log Z for any graph G. [sent-146, score-0.573]

49 The algorithm uses a decomposition algorithm as a sub-routine. [sent-147, score-0.242]

50 In what follows, we use term D ECOMP for a generic decomposition algorithm. [sent-148, score-0.162]

51 The key point is that our algorithm provides provable upper and lower bound on log Z for any graph; the approximation guarantee and computation time depends on the property of D ECOMP. [sent-149, score-0.339]

52 Planar graph with r = 3), we will use DeC(G, r, ∆) in place of D ECOMP. [sent-152, score-0.256]

53 (2) For each connected component Sj , 1 ≤ j ≤ K, do the following: (a) Compute partition function Zj restricted to Sj by dynamic programming(or exhaustive computation). [sent-158, score-0.201]

54 Then K K ˆ log ZLB = L ˆ ψij ; log ZUB = log Zj + j=1 j=1 (i,j)∈B U ψij . [sent-160, score-0.372]

55 log Zj + (i,j)∈B ˆ ˆ (4) Output: lower bound log ZLB and upper bound log ZUB . [sent-161, score-0.53]

56 In words, L OG PARTITION(G) produces upper and lower bound on log Z of MRF G as follows: decompose graph G into (small) components S1 , . [sent-162, score-0.571]

57 , SK by removing (few) edges B ⊂ E using D ECOMP(G). [sent-165, score-0.126]

58 To produce bounds ˆ ˆ log ZLB , log ZUB take the summation of thus computed component-wise log-partition function along with minimal and maximal effect of edges from B. [sent-167, score-0.385]

59 In the next section, we will specialize our analysis for minor excluded G when L OG PARTITION uses DeC as the D ECOMP algorithm. [sent-169, score-0.443]

60 ˆ ˆ Lemma 2 Given an MRF G described by (1), the L OG PARTITION produces log ZLB , log ZUB such that U L ˆ ˆ ˆ ˆ log ZLB ≤ log Z ≤ log ZUB , log ZUB − log ZLB = ψij − ψij . [sent-170, score-0.909]

61 (i,j)∈B 4 ∗ It takes O |E|KΣ|S | + TDECOMP time to produce this estimate, where |S ∗ | = maxK |Sj | with j=1 D ECOMP producing decomposition of G into S1 , . [sent-171, score-0.245]

62 Lemma 3 If G has maximum vertex degree D then, log Z ≥ 1 D+1 (i,j)∈E U L ψij − ψij . [sent-175, score-0.282]

63 Lemma 4 If G has maximum vertex degree D and the D ECOMP(G) produces B that is (δ, ∆)decomposition, then ˆ ˆ E log ZUB − log ZLB ≤ δ(D + 1) log Z, w. [sent-176, score-0.571]

64 Analysis of L OG PARTITION for Minor-excluded G : Here, we specialize analysis of L OG PAR TITION for minor exclude graph G. [sent-180, score-0.682]

65 For G that exclude minor Kr,r , we use algorithm DeC(G, r, ∆). [sent-181, score-0.407]

66 Theorem 1 Let G exclude Kr,r as minor and have D as maximum vertex degree. [sent-183, score-0.467]

67 Then, ε ˆ ˆ log ZLB ≤ log Z ≤ log ZUB ; ˆ ˆ E log ZUB − log ZLB ≤ ε log Z. [sent-185, score-0.744]

68 Corollary 2 For any ε > 0, the L OG PARTITION algorithm with DeC algorithm for constant degree ˆ ˆ Planar graph G based MRF, produces log ZLB , log ZUB so that ˆ ˆ (1 − ε) log Z ≤ log ZLB ≤ log Z ≤ log ZUB ≤ (1 + ε) log Z, in time O(nC(ε)) where log log C(ε) = O(1/ε). [sent-188, score-1.551]

69 As in L OG PARTITION, the computation time and performance of the algorithm depends on property of decomposition scheme. [sent-195, score-0.231]

70 We describe algorithm for any graph G; which will be specialized for Kr,r minor excluded G using DeC(G, r, ∆). [sent-196, score-0.68]

71 Later, we will specialize our analysis for minor excluded G when it uses DeC as the D ECOMP algorithm. [sent-204, score-0.443]

72 It takes O |E|KΣ|S | + TDECOMP time to produce this estimate, where |S ∗ | = maxK |Sj | with D ECOMP producing decomposition of G into j=1 S1 , . [sent-206, score-0.245]

73 Lemma 6 If G has maximum vertex degree D, then     1  1  U U L H(x∗ ) ≥ ψij  ≥ ψij − ψij  . [sent-210, score-0.158]

74 D+1 D+1 (i,j)∈E (i,j)∈E 5 Lemma 7 If G has maximum vertex degree D and the D ECOMP(G) produces B that is (δ, ∆)decomposition, then E H(x∗ ) − H(x∗ ) ≤ δ(D + 1)H(x∗ ), D∆ where expectation is w. [sent-211, score-0.199]

75 Analysis of M ODE for Minor-excluded G : Here, we specialize analysis of M ODE for minor exclude graph G. [sent-216, score-0.682]

76 For G that exclude minor Kr,r , we use algorithm DeC(G, r, ∆). [sent-217, score-0.407]

77 Theorem 2 Let G exclude Kr,r as minor and have D as the maximum vertex degree. [sent-219, score-0.467]

78 Corollary 3 For any ε > 0, the M ODE algorithm with DeC algorithm for constant degree Planar graph G based MRF, produces estimate x∗ so that (1 − ε)H(x∗ ) ≤ H(x∗ ) ≤ H(x∗ ), in time O(nC(ε)) where log log C(ε) = O(1/ε). [sent-224, score-0.683]

79 5 Experiments Our algorithm provides provably good approximation for any MRF with minor excluded graph structure, with planar graph as a special case. [sent-225, score-1.152]

80 Figure 2 shows a lattice or grid graph with n = 4 (on the left side). [sent-231, score-0.414]

81 Hence, we run our algorithms L OG PARTITION and M ODE, with decomposition scheme DeC(G, 3, ∆), ∆ ∈ {3, 4, 5}. [sent-251, score-0.189]

82 We consider two measures to evaluate performance: 1 1 error in log Z, deﬁned as n2 | log Z alg − log Z|; and error in H(x∗ ), deﬁned as n2 |H(xalg − H(x∗ )|. [sent-252, score-0.516]

83 We compare our algorithm for error in log Z with the two recently very successful algorithms – Tree re-weighted algorithm (TRW) and planar decomposition algorithm (PDC). [sent-253, score-0.694]

84 The Figure 3(A) plots error with respect to varying interaction while Figure 3(B) plots error with respect to varying ﬁeld strength. [sent-255, score-0.336]

85 Speciﬁcally, running time of our algorithm with a given parameter value ∆ scales linearly in n, while keeping the relative error bound exactly the same. [sent-258, score-0.218]

86 Note that error bound plot is the same for n = 100 (A) and n = 1000 (B). [sent-261, score-0.151]

87 We plot the theoretically evaluated bounds on the error in MAP in Figure 4 with tags (A), (B) and (C). [sent-265, score-0.169]

88 Again, the bound on MAP relative error for given ∆ parameter remains the same for all values of n as shown in (A) for n = 100 and (B) for n = 1000. [sent-266, score-0.151]

89 There is no change in error bound with respect to the ﬁeld strength (C). [sent-267, score-0.246]

90 Everything is exactly the same as the above setup with the only difference that grid graph is replaced by cris-cross graph which is obtained by adding extra four neighboring edges per node (exception of boundary nodes). [sent-269, score-0.775]

91 Figure 2 shows cris-cross graph with n = 4 (on the right side). [sent-270, score-0.256]

92 For cris-cross graph, we obtained its graph decomposition from the decomposition of its grid sub-graph. [sent-272, score-0.71]

93 graph Though the cris-cross graph is not planar, due to the structure of the cris-cross graph it can be shown (proved) that the running time of our algorithm will remain the same (in order) and error bound will become only 3 times weaker than that for the grid graph ! [sent-273, score-1.372]

94 We compute these theoretical error bounds for log Z and MAP which is plotted in Figure 5. [sent-274, score-0.223]

95 This ﬁgure is similar to the Figure 4 for grid graph. [sent-275, score-0.13]

96 This clearly exhibits the generality of our algorithm even beyond minor excluded graphs. [sent-276, score-0.424]

97 7 (1-A) Grid, N=7 (1-B) Gird, n=7 TRW TRW PDC PDC 3 3 4 Z Error Z Error 4 5 5 Interaction Strength Field Strength Figure 3: Comparison of TRW, PDC and our algorithm for grid graph with n = 7 with respect to error in log Z. [sent-327, score-0.622]

98 2 Field Strength Interaction Strength Figure 4: The theoretically computable error bounds for log Z and MAP under our algorithm for grid with n = 100 and n = 1000 under varying interaction and varying ﬁeld model. [sent-419, score-0.649]

99 2 Field Strength The theoretically computable error bounds for log Z and MAP under our algorithm for cris-cross with n = 100 and n = 1000 under varying interaction and varying ﬁeld model. [sent-493, score-0.519]

100 This clearly shows scalability of our algorithm and robustness to graph structure. [sent-494, score-0.322]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('og', 0.277), ('dec', 0.267), ('minor', 0.263), ('graph', 0.256), ('zlb', 0.233), ('zub', 0.233), ('planar', 0.216), ('ecomp', 0.212), ('trw', 0.185), ('ode', 0.169), ('decomposition', 0.162), ('ij', 0.159), ('mrf', 0.156), ('excludes', 0.142), ('grid', 0.13), ('sj', 0.129), ('cris', 0.127), ('tdecomp', 0.127), ('log', 0.124), ('excluded', 0.121), ('map', 0.113), ('partition', 0.111), ('pdc', 0.111), ('exclude', 0.104), ('vertex', 0.1), ('interaction', 0.098), ('strength', 0.095), ('edges', 0.085), ('bound', 0.079), ('rao', 0.078), ('plotkin', 0.074), ('error', 0.072), ('klein', 0.071), ('field', 0.068), ('provable', 0.067), ('graphs', 0.067), ('connected', 0.067), ('sk', 0.064), ('logpartition', 0.064), ('kr', 0.063), ('specialize', 0.059), ('degree', 0.058), ('kolmogorov', 0.048), ('setup', 0.048), ('lemma', 0.048), ('varying', 0.047), ('jaakkola', 0.046), ('decomposing', 0.045), ('implication', 0.045), ('arbitrary', 0.043), ('components', 0.043), ('multicommodity', 0.042), ('tition', 0.042), ('cross', 0.042), ('removing', 0.041), ('produces', 0.041), ('nc', 0.041), ('algorithm', 0.04), ('wainwright', 0.04), ('pr', 0.039), ('theoretically', 0.039), ('maxk', 0.037), ('devavrat', 0.037), ('tji', 0.037), ('bp', 0.036), ('xi', 0.034), ('propagation', 0.033), ('nodes', 0.033), ('tags', 0.031), ('upto', 0.031), ('shah', 0.031), ('takes', 0.031), ('zj', 0.03), ('say', 0.03), ('incident', 0.03), ('belief', 0.029), ('eld', 0.029), ('computation', 0.029), ('par', 0.028), ('lattice', 0.028), ('globerson', 0.028), ('randomness', 0.028), ('decompose', 0.028), ('vertices', 0.028), ('scheme', 0.027), ('running', 0.027), ('producing', 0.027), ('bounds', 0.027), ('scalability', 0.026), ('corollary', 0.026), ('stated', 0.025), ('edge', 0.025), ('correctness', 0.025), ('willsky', 0.025), ('computable', 0.025), ('produce', 0.025), ('gi', 0.024), ('tree', 0.024), ('li', 0.023), ('component', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 121 nips-2007-Local Algorithms for Approximate Inference in Minor-Excluded Graphs

Author: Kyomin Jung, Devavrat Shah

2 0.16177593 141 nips-2007-New Outer Bounds on the Marginal Polytope

Author: David Sontag, Tommi S. Jaakkola

Abstract: We give a new class of outer bounds on the marginal polytope, and propose a cutting-plane algorithm for efﬁciently optimizing over these constraints. When combined with a concave upper bound on the entropy, this gives a new variational inference algorithm for probabilistic inference in discrete Markov Random Fields (MRFs). Valid constraints on the marginal polytope are derived through a series of projections onto the cut polytope. As a result, we obtain tighter upper bounds on the log-partition function. We also show empirically that the approximations of the marginals are signiﬁcantly more accurate when using the tighter outer bounds. Finally, we demonstrate the advantage of the new constraints for ﬁnding the MAP assignment in protein structure prediction. 1

3 0.13104078 92 nips-2007-Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations

Author: Amir Globerson, Tommi S. Jaakkola

Abstract: We present a novel message passing algorithm for approximating the MAP problem in graphical models. The algorithm is similar in structure to max-product but unlike max-product it always converges, and can be proven to ﬁnd the exact MAP solution in various settings. The algorithm is derived via block coordinate descent in a dual of the LP relaxation of MAP, but does not require any tunable parameters such as step size or tree weights. We also describe a generalization of the method to cluster based potentials. The new method is tested on synthetic and real-world problems, and compares favorably with previous approaches. Graphical models are an effective approach for modeling complex objects via local interactions. In such models, a distribution over a set of variables is assumed to factor according to cliques of a graph with potentials assigned to each clique. Finding the assignment with highest probability in these models is key to using them in practice, and is often referred to as the MAP (maximum aposteriori) assignment problem. In the general case the problem is NP hard, with complexity exponential in the tree-width of the underlying graph. Linear programming (LP) relaxations have proven very useful in approximating the MAP problem, and often yield satisfactory empirical results. These approaches relax the constraint that the solution is integral, and generally yield non-integral solutions. However, when the LP solution is integral, it is guaranteed to be the exact MAP. For some classes of problems the LP relaxation is provably correct. These include the minimum cut problem and maximum weight matching in bi-partite graphs [8]. Although LP relaxations can be solved using standard LP solvers, this may be computationally intensive for large problems [13]. The key problem with generic LP solvers is that they do not use the graph structure explicitly and thus may be sub-optimal in terms of computational efﬁciency. The max-product method [7] is a message passing algorithm that is often used to approximate the MAP problem. In contrast to generic LP solvers, it makes direct use of the graph structure in constructing and passing messages, and is also very simple to implement. The relation between max-product and the LP relaxation has remained largely elusive, although there are some notable exceptions: For tree-structured graphs, max-product and LP both yield the exact MAP. A recent result [1] showed that for maximum weight matching on bi-partite graphs max-product and LP also yield the exact MAP [1]. Finally, Tree-Reweighted max-product (TRMP) algorithms [5, 10] were shown to converge to the LP solution for binary xi variables, as shown in [6]. In this work, we propose the Max Product Linear Programming algorithm (MPLP) - a very simple variation on max-product that is guaranteed to converge, and has several advantageous properties. MPLP is derived from the dual of the LP relaxation, and is equivalent to block coordinate descent in the dual. Although this results in monotone improvement of the dual objective, global convergence is not always guaranteed since coordinate descent may get stuck in suboptimal points. This can be remedied using various approaches, but in practice we have found MPLP to converge to the LP 1 solution in a majority of the cases we studied. To derive MPLP we use a special form of the dual LP, which involves the introduction of redundant primal variables and constraints. We show how the dual variables corresponding to these constraints turn out to be the messages in the algorithm. We evaluate the method on Potts models and protein design problems, and show that it compares favorably with max-product (which often does not converge for these problems) and TRMP. 1 The Max-Product and MPLP Algorithms The max-product algorithm [7] is one of the most often used methods for solving MAP problems. Although it is neither guaranteed to converge to the correct solution, or in fact converge at all, it provides satisfactory results in some cases. Here we present two algorithms: EMPLP (edge based MPLP) and NMPLP (node based MPLP), which are structurally very similar to max-product, but have several key advantages: • After each iteration, the messages yield an upper bound on the MAP value, and the sequence of bounds is monotone decreasing and convergent. The messages also have a limit point that is a ﬁxed point of the update rule. • No additional parameters (e.g., tree weights as in [6]) are required. • If the ﬁxed point beliefs have a unique maximizer then they correspond to the exact MAP. • For binary variables, MPLP can be used to obtain the solution to an LP relaxation of the MAP problem. Thus, when this LP relaxation is exact and variables are binary, MPLP will ﬁnd the MAP solution. Moreover, for any variable whose beliefs are not tied, the MAP assignment can be found (i.e., the solution is partially decodable). Pseudo code for the algorithms (and for max-product) is given in Fig. 1. As we show in the next sections, MPLP is essentially a block coordinate descent algorithm in the dual of a MAP LP relaxation. Every update of the MPLP messages corresponds to exact minimization of a set of dual variables. For EMPLP minimization is over the set of variables corresponding to an edge, and for NMPLP it is over the set of variables corresponding to all the edges a given node appears in (i.e., a star). The properties of MPLP result from its relation to the LP dual. In what follows we describe the derivation of the MPLP algorithms and prove their properties. 2 The MAP Problem and its LP Relaxation We consider functions over n variables x = {x1 , . . . , xn } deﬁned as follows. Given a graph G = (V, E) with n vertices, and potentials θij (xi , xj ) for all edges ij ∈ E, deﬁne the function1 f (x; θ) = θij (xi , xj ) . (1) ij∈E The MAP problem is deﬁned as ﬁnding an assignment xM that maximizes the function f (x; θ). Below we describe the standard LP relaxation for this problem. Denote by {µij (xi , xj )}ij∈E distributions over variables corresponding to edges ij ∈ E and {µi (xi )}i∈V distributions corresponding to nodes i ∈ V . We will use µ to denote a given set of distributions over all edges and nodes. The set ML (G) is deﬁned as the set of µ where pairwise and singleton distributions are consistent x ˆ xi µij (ˆi , xj ) = µj (xj ) , ˆ xj µij (xi , xj ) = µi (xi ) ∀ij ∈ E, xi , xj ˆ ML (G) = µ ≥ 0 ∀i ∈ V xi µi (xi ) = 1 Now consider the following linear program: MAPLPR : µL∗ = arg max µ∈ML (G) µ·θ. (2) where µ·θ is shorthand for µ·θ = ij∈E xi ,xj θij (xi , xj )µij (xi , xj ). It is easy to show (see e.g., [10]) that the optimum of MAPLPR yields an upper bound on the MAP value, i.e. µL∗ ·θ ≥ f (xM ). Furthermore, when the optimal µi (xi ) have only integral values, the assignment that maximizes µi (xi ) yields the correct MAP assignment. In what follows we show how the MPLP algorithms can be derived from the dual of MAPLPR. 1 P We note that some authors also add a term i∈V θi (xi ) to f (x; θ). However, these terms can be included in the pairwise functions θij (xi , xj ), so we ignore them for simplicity. 2 3 The LP Relaxation Dual Since MAPLPR is an LP, it has an equivalent convex dual. In App. A we derive a special dual of MAPLPR using a different representation of ML (G) with redundant variables. The advantage of this dual is that it allows the derivation of simple message passing algorithms. The dual is described in the following proposition. Proposition 1 The following optimization problem is a convex dual of MAPLPR DMAPLPR : min max xi i s.t. max βki (xk , xi ) (3) k∈N (i) xk βji (xj , xi ) + βij (xi , xj ) = θij (xi , xj ) , where the dual variables are βij (xi , xj ) for all ij, ji ∈ E and values of xi and xj . The dual has an intuitive interpretation in terms of re-parameterizations. Consider the star shaped graph Gi consisting of node i and all its neighbors N (i). Assume the potential on edge ki (for k ∈ N (i)) is βki (xk , xi ). The value of the MAP assignment for this model is max max βki (xk , xi ). This is exactly the term in the objective of DMAPLPR. Thus the dual xi k∈N (i) xk corresponds to individually decoding star graphs around all nodes i ∈ V where the potentials on the graph edges should sum to the original potential. It is easy to see that this will always result in an upper bound on the MAP value. The somewhat surprising result of the duality is that there exists a β assignment such that star decoding yields the optimal value of MAPLPR. 4 Block Coordinate Descent in the Dual To obtain a convergent algorithm we use a simple block coordinate descent strategy. At every iteration, ﬁx all variables except a subset, and optimize over this subset. It turns out that this can be done in closed form for the cases we consider. We begin by deriving the EMPLP algorithm. Consider ﬁxing all the β variables except those corresponding to some edge ij ∈ E (i.e., βij and βji ), and minimizing DMAPLPR over the non-ﬁxed variables. Only two terms in the DMAPLPR objective depend on βij and βji . We can write those as f (βij , βji ) = max λ−j (xi ) + max βji (xj , xi ) + max λ−i (xj ) + max βij (xi , xj ) i j xi where we deﬁned λ−j (xi ) = i xj k∈N (i)\j xi xi (4) λki (xi ) and λki (xi ) = maxxk βki (xk , xi ) as in App. A. Note that the function f (βij , βji ) depends on the other β values only through λ−i (xj ) and λ−j (xi ). j i This implies that the optimization can be done solely in terms of λij (xj ) and there is no need to store the β values explicitly. The optimal βij , βji are obtained by minimizing f (βij , βji ) subject to the re-parameterization constraint βji (xj , xi ) + βij (xi , xj ) = θij (xi , xj ). The following proposition characterizes the minimum of f (βij , βji ). In fact, as mentioned above, we do not need to characterize the optimal βij (xi , xj ) itself, but only the new λ values. Proposition 2 Maximizing the function f (βij , βji ) yields the following λji (xi ) (and the equivalent expression for λij (xj )) 1 −j 1 λji (xi ) = − λi (xi ) + max λ−i (xj ) + θij (xi , xj ) j 2 2 xj The proposition is proved in App. B. The λ updates above result in the EMPLP algorithm, described in Fig. 1. Note that since the β optimization affects both λji (xi ) and λij (xj ), both these messages need to be updated simultaneously. We proceed to derive the NMPLP algorithm. For a given node i ∈ V , we consider all its neighbors j ∈ N (i), and wish to optimize over the variables βji (xj , xi ) for ji, ij ∈ E (i.e., all the edges in a star centered on i), while the other variables are ﬁxed. One way of doing so is to use the EMPLP algorithm for the edges in the star, and iterate it until convergence. We now show that the result of 3 Inputs: A graph G = (V, E), potential functions θij (xi , xj ) for each edge ij ∈ E. Initialization: Initialize messages to any value. Algorithm: • Iterate until a stopping criterion is satisﬁed: – Max-product: Iterate over messages and update (cji shifts the max to zero) h i mji (xi )← max m−i (xj ) + θij (xi , xj ) − cji j xj – EMPLP: For each ij ∈ E, update λji (xi ) and λij (xj ) simultaneously (the update for λij (xj ) is the same with i and j exchanged) h i 1 1 λji (xi )← − λ−j (xi ) + max λ−i (xj ) + θij (xi , xj ) j i 2 2 xj – NMPLP: Iterate over nodes i ∈ V and update all γij (xj ) where j ∈ N (i) 2 3 X 2 γij (xj )← max 4θij (xi , xj ) − γji (xi ) + γki (xi )5 xi |N (i)| + 1 k∈N(i) • Calculate node “beliefs”: Set biP i ) to be the sum of incoming messages into node i ∈ V (x (e.g., for NMPLP set bi (xi ) = k∈N(i) γki (xi )). Output: Return assignment x deﬁned as xi = arg maxxi b(ˆi ). x ˆ Figure 1: The max-product, EMPLP and NMPLP algorithms. Max-product, EMPLP and NMPLP use mesP sages mij , λij and γij respectively. We use the notation m−i (xj ) = k∈N(j)\i mkj (xj ). j this optimization can be found in closed form. The assumption about β being ﬁxed outside the star implies that λ−i (xj ) is ﬁxed. Deﬁne: γji (xi ) = maxxj θij (xi , xj ) + λ−i (xj ) . Simple algebra j j yields the following relation between λ−j (xi ) and γki (xi ) for k ∈ N (i) i 2 λ−j (xi ) = −γji (xi ) + γki (xi ) (5) i |N (i)| + 1 k∈N (i) Plugging this into the deﬁnition of γji (xi ) we obtain the NMPLP update in Fig. 1. The messages for both algorithms can be initialized to any value since it can be shown that after one iteration they will correspond to valid β values. 5 Convergence Properties The MPLP algorithm decreases the dual objective (i.e., an upper bound on the MAP value) at every iteration, and thus its dual objective values form a convergent sequence. Using arguments similar to [5] it can be shown that MPLP has a limit point that is a ﬁxed point of its updates. This in itself does not guarantee convergence to the dual optimum since coordinate descent algorithms may get stuck at a point that is not a global optimum. There are ways of overcoming this difﬁculty, for example by smoothing the objective [4] or using techniques as in [2] (see p. 636). We leave such extensions for further work. In this section we provide several results about the properties of the MPLP ﬁxed points and their relation to the corresponding LP. First, we claim that if all beliefs have unique maxima then the exact MAP assignment is obtained. Proposition 3 If the ﬁxed point of MPLP has bi (xi ) such that for all i the function bi (xi ) has a unique maximizer x∗ , then x∗ is the solution to the MAP problem and the LP relaxation is exact. i Since the dual objective is always greater than or equal to the MAP value, it sufﬁces to show that there exists a dual feasible point whose objective value is f (x∗ ). Denote by β ∗ , λ∗ the value of the corresponding dual parameters at the ﬁxed point of MPLP. Then the dual objective satisﬁes λ∗ (xi ) = ki max i xi k∈N (i) ∗ max βki (xk , x∗ ) = i i k∈N (i) xk ∗ βki (x∗ , x∗ ) = f (x∗ ) k i i 4 k∈N (i) To see why the second equality holds, note that bi (x∗ ) = maxxi ,xj λ−j (xi ) + βji (xj , xi ) and i i bj (x∗ ) = maxxi ,xj λ−i (xj ) + βij (xi , xj ). By the equalization property in Eq. 9 the arguments of j j the two max operations are equal. From the unique maximum assumption it follows that x∗ , x∗ are i j the unique maximizers of the above. It follows that βji , βij are also maximized by x∗ , x∗ . i j In the general case, the MPLP ﬁxed point may not correspond to a primal optimum because of the local optima problem with coordinate descent. However, when the variables are binary, ﬁxed points do correspond to primal solutions, as the following proposition states. Proposition 4 When xi are binary, the MPLP ﬁxed point can be used to obtain the primal optimum. The claim can be shown by constructing a primal optimal solution µ∗ . For tied bi , set µ∗ (xi ) to 0.5 i and for untied bi , set µ∗ (x∗ ) to 1. If bi , bj are not tied we set µ∗ (x∗ , x∗ ) = 1. If bi is not tied but bj i i ij i j is, we set µ∗ (x∗ , xj ) = 0.5. If bi , bj are tied then βji , βij can be shown to be maximized at either ij i x∗ , x∗ = (0, 0), (1, 1) or x∗ , x∗ = (0, 1), (1, 0). We then set µ∗ to be 0.5 at one of these assignment i j i j ij ∗ pairs. The resulting µ∗ is clearly primal feasible. Setting δi = b∗ we obtain that the dual variables i (δ ∗ , λ∗ , β ∗ ) and primal µ∗ satisfy complementary slackness for the LP in Eq. 7 and therefore µ∗ is primal optimal. The binary optimality result implies partial decodability, since [6] shows that the LP is partially decodable for binary variables. 6 Beyond pairwise potentials: Generalized MPLP In the previous sections we considered maximizing functions which factor according to the edges of the graph. A more general setting considers clusters c1 , . . . , ck ⊂ {1, . . . , n} (the set of clusters is denoted by C), and a function f (x; θ) = c θc (xc ) deﬁned via potentials over clusters θc (xc ). The MAP problem in this case also has an LP relaxation (see e.g. [11]). To deﬁne the LP we introduce the following deﬁnitions: S = {c ∩ c : c, c ∈ C, c ∩ c = ∅} is the set of intersection between clusters ˆ ˆ ˆ and S(c) = {s ∈ S : s ⊆ c} is the set of overlap sets for cluster c.We now consider marginals over the variables in c ∈ C and s ∈ S and require that cluster marginals agree on their overlap. Denote this set by ML (C). The LP relaxation is then to maximize µ · θ subject to µ ∈ ML (C). As in Sec. 4, we can derive message passing updates that result in monotone decrease of the dual LP of the above relaxation. The derivation is similar and we omit the details. The key observation is that one needs to introduce |S(c)| copies of each marginal µc (xc ) (instead of the two copies in the pairwise case). Next, as in the EMPLP derivation we assume all β are ﬁxed except those corresponding to some cluster c. The resulting messages are λc→s (xs ) from a cluster c to all of its intersection sets s ∈ S(c). The update on these messages turns out to be:   1 1 λ−c (xs ) + max  λ−c (xs ) + θc (xc ) λc→s (xs ) = − 1 − ˆ s s ˆ |S(c)| |S(c)| xc\s s∈S(c)\s ˆ where for a given c ∈ C all λc→s should be updated simultaneously for s ∈ S(c), and λ−c (xs ) is s deﬁned as the sum of messages into s that are not from c. We refer to this algorithm as Generalized EMPLP (GEMPLP). It is possible to derive an algorithm similar to NMPLP that updates several clusters simultaneously, but its structure is more involved and we do not address it here. 7 Related Work Weiss et al. [11] recently studied the ﬁxed points of a class of max-product like algorithms. Their analysis focused on properties of ﬁxed points rather than convergence guarantees. Speciﬁcally, they showed that if the counting numbers used in a generalized max-product algorithm satisfy certain properties, then its ﬁxed points will be the exact MAP if the beliefs have unique maxima, and for binary variables the solution can be partially decodable. Both these properties are obtained for the MPLP ﬁxed points, and in fact we can show that MPLP satisﬁes the conditions in [11], so that we obtain these properties as corollaries of [11]. We stress however, that [11] does not address convergence of algorithms, but rather properties of their ﬁxed points, if they converge. MPLP is similar in some aspects to Kolmogorov’s TRW-S algorithm [5]. TRW-S is also a monotone coordinate descent method in a dual of the LP relaxation and its ﬁxed points also have similar 5 guarantees to those of MPLP [6]. Furthermore, convergence to a local optimum may occur, as it does for MPLP. One advantage of MPLP lies in the simplicity of its updates and the fact that it is parameter free. The other is its simple generalization to potentials over clusters of nodes (Sec. 6). Recently, several new dual LP algorithms have been introduced, which are more closely related to our formalism. Werner [12] presented a class of algorithms which also improve the dual LP at every iteration. The simplest of those is the max-sum-diffusion algorithm, which is similar to our EMPLP algorithm, although the updates are different from ours. Independently, Johnson et al. [4] presented a class of algorithms that improve duals of the MAP-LP using coordinate descent. They decompose the model into tractable parts by replicating variables and enforce replication constraints within the Lagrangian dual. Our basic formulation in Eq. 3 could be derived from their perspective. However, the updates in the algorithm and the analysis differ. Johnson et al. also presented a method for overcoming the local optimum problem, by smoothing the objective so that it is strictly convex. Such an approach could also be used within our algorithms. Vontobel and Koetter [9] recently introduced a coordinate descent algorithm for decoding LDPC codes. Their method is speciﬁcally tailored for this case, and uses updates that are similar to our edge based updates. Finally, the concept of dual coordinate descent may be used in approximating marginals as well. In [3] we use such an approach to optimize a variational bound on the partition function. The derivation uses some of the ideas used in the MPLP dual, but importantly does not ﬁnd the minimum for each coordinate. Instead, a gradient like step is taken at every iteration to decrease the dual objective. 8 Experiments We compared NMPLP to three other message passing algorithms:2 Tree-Reweighted max-product (TRMP) [10],3 standard max-product (MP), and GEMPLP. For MP and TRMP we used the standard approach of damping messages using a factor of α = 0.5. We ran all algorithms for a maximum of 2000 iterations, and used the hit-time measure to compare their speed of convergence. This measure is deﬁned as follows: At every iteration the beliefs can be used to obtain an assignment x with value f (x). We deﬁne the hit-time as the ﬁrst iteration at which the maximum value of f (x) is achieved.4 We ﬁrst experimented with a 10 × 10 grid graph, with 5 values per state. The function f (x) was 5 a Potts model: f (x) = The values for θij and θi (xi ) ij∈E θij I(xi = xj ) + i∈V θi (xi ). were randomly drawn from [−cI , cI ] and [−cF , cF ] respectively, and we used values of cI and cF in the range range [0.1, 2.35] (with intervals of 0.25), resulting in 100 different models. The clusters for GEMPLP were the faces of the graph [14]. To see if NMPLP converges to the LP solution we also used an LP solver to solve the LP relaxation. We found that the the normalized difference between NMPLP and LP objective was at most 10−3 (median 10−7 ), suggesting that NMPLP typically converged to the LP solution. Fig. 2 (top row) shows the results for the three algorithms. It can be seen that while all non-cluster based algorithms obtain similar f (x) values, NMPLP has better hit-time (in the median) than TRMP and MP, and MP does not converge in many cases (see caption). GEMPLP converges more slowly than NMPLP, but obtains much better f (x) values. In fact, in 99% of the cases the normalized difference between the GEMPLP objective and the f (x) value was less than 10−5 , suggesting that the exact MAP solution was found. We next applied the algorithms to the real world problems of protein design. In [13], Yanover et al. show how these problems can be formalized in terms of ﬁnding a MAP in an appropriately constructed graphical model.6 We used all algorithms except GNMPLP (since there is no natural choice for clusters in this case) to approximate the MAP solution on the 97 models used in [13]. In these models the number of states per variable is 2 − 158, and there are up to 180 variables per model. Fig. 2 (bottom) shows results for all the design problems. In this case only 11% of the MP runs converged, and NMPLP was better than TRMP in terms of hit-time and comparable in f (x) value. The performance of MP was good on the runs where it converged. 2 As expected, NMPLP was faster than EMPLP so only NMPLP results are given. The edge weights for TRMP corresponded to a uniform distribution over all spanning trees. 4 This is clearly a post-hoc measure since it can only be obtained after the algorithm has exceeded its maximum number of iterations. However, it is a reasonable algorithm-independent measure of convergence. 5 The potential θi (xi ) may be folded into the pairwise potential to yield a model as in Eq. 1. 6 Data available from http://jmlr.csail.mit.edu/papers/volume7/yanover06a/Rosetta Design Dataset.tgz 3 6 (a) (b) (c) 100 (d) 0.6 2000 0.04 0.4 0.02 −50 0 −0.02 −0.04 ∆(Value) 0 1000 ∆(Hit Time) ∆(Value) ∆(Hit Time) 50 0 MP TRMP GMPLP 0 −0.2 −1000 −0.4 −0.06 −100 0.2 MP TRMP GMPLP MP TRMP MP TRMP Figure 2: Evaluation of message passing algorithms on Potts models and protein design problems. (a,c): Convergence time results for the Potts models (a) and protein design problems (c). The box-plots (horiz. red line indicates median) show the difference between the hit-time for the other algorithms and NMPLP. (b,d): Value of integer solutions for the Potts models (b) and protein design problems (d). The box-plots show the normalized difference between the value of f (x) for NMPLP and the other algorithms. All ﬁgures are such that better MPLP performance yields positive Y axis values. Max-product converged on 58% of the cases for the Potts models, and on 11% of the protein problems. Only convergent max-product runs are shown. 9 Conclusion We have presented a convergent algorithm for MAP approximation that is based on block coordinate descent of the MAP-LP relaxation dual. The algorithm can also be extended to cluster based functions, which result empirically in improved MAP estimates. This is in line with the observations in [14] that generalized belief propagation algorithms can result in signiﬁcant performance improvements. However generalized max-product algorithms [14] are not guaranteed to converge whereas GMPLP is. Furthermore, the GMPLP algorithm does not require a region graph and only involves intersection between pairs of clusters. In conclusion, MPLP has the advantage of resolving the convergence problems of max-product while retaining its simplicity, and offering the theoretical guarantees of LP relaxations. We thus believe it should be useful in a wide array of applications. A Derivation of the dual Before deriving the dual, we ﬁrst express the constraint set ML (G) in a slightly different way. The deﬁnition of ML (G) in Sec. 2 uses a single distribution µij (xi , xj ) for every ij ∈ E. In what follows, we use two copies of this pairwise distribution for every edge, which we denote µij (xi , xj ) ¯ and µji (xj , xi ), and we add the constraint that these two copies both equal the original µij (xi , xj ). ¯ For this extended set of pairwise marginals, we consider the following set of constraints which is clearly equivalent to ML (G). On the rightmost column we give the dual variables that will correspond to each constraint (we omit non-negativity constraints). µij (xi , xj ) = µij (xi , xj ) ¯ µji (xj , xi ) = µij (xi , xj ) ¯ x xi µij (ˆi , xj ) = µj (xj ) ˆ ¯ µji (ˆj , xi ) = µi (xi ) ¯ x xj ˆ xi µi (xi ) = 1 ∀ij ∈ E, xi , xj ∀ij ∈ E, xi , xj ∀ij ∈ E, xj ∀ji ∈ E, xi ∀i ∈ V βij (xi , xj ) βji (xj , xi ) λij (xj ) λji (xi ) δi (6) ¯ We denote the set of (µ, µ) satisfying these constraints by ML (G). We can now state an LP that ¯ is equivalent to MAPLPR, only with an extended set of variables and constraints. The equivalent ¯ problem is to maximize µ · θ subject to (µ, µ) ∈ ML (G) (note that the objective uses the original ¯ µ copy). LP duality transformation of the extended problem yields the following LP min i δi s.t. λij (xj ) − βij (xi , xj ) ≥ 0 βij (xi , xj ) + βji (xj , xi ) = θij (xi , xj ) − k∈N (i) λki (xi ) + δi ≥ 0 ∀ij, ji ∈ E, xi , xj ∀ij ∈ E, xi , xj ∀i ∈ V, xi (7) We next simplify the above LP by eliminating some of its constraints and variables. Since each variable δi appears in only one constraint, and the objective minimizes δi it follows that δi = maxxi k∈N (i) λki (xi ) and the constraints with δi can be discarded. Similarly, since λij (xj ) appears in a single constraint, we have that for all ij ∈ E, ji ∈ E, xi , xj λij (xj ) = maxxi βij (xi , xj ) and the constraints with λij (xj ), λji (xi ) can also be discarded. Using the eliminated δi and λji (xi ) 7 variables, we obtain that the LP in Eq. 7 is equivalent to that in Eq. 3. Note that the objective in Eq. 3 is convex since it is a sum of point-wise maxima of convex functions. B Proof of Proposition 2 We wish to minimize f in Eq. 4 subject to the constraint that βij + βji = θij . Rewrite f as f (βij , βji ) = max λ−j (xi ) + βji (xj , xi ) + max λ−i (xj ) + βij (xi , xj ) j i xi ,xj xi ,xj (8) The sum of the two arguments in the max is λ−j (xi ) + λ−i (xj ) + θij (xi , xj ) i j (because of the constraints on β). Thus the minimum must be greater than −j −i 1 2 maxxi ,xj λi (xi ) + λj (xj ) + θij (xi , xj ) . One assignment to β that achieves this minimum is obtained by requiring an equalization condition:7 λ−i (xj ) + βij (xi , xj ) = λ−j (xi ) + βji (xj , xi ) = j i 1 θij (xi , xj ) + λ−j (xi ) + λ−i (xj ) i j 2 (9) which implies βij (xi , xj ) = 1 θij (xi , xj ) + λ−j (xi ) − λ−i (xj ) and a similar expression for βji . i j 2 The resulting λij (xj ) = maxxi βij (xi , xj ) are then the ones in Prop. 2. Acknowledgments The authors acknowledge support from the Defense Advanced Research Projects Agency (Transfer Learning program). Amir Globerson was also supported by the Rothschild Yad-Hanadiv fellowship. References [1] M. Bayati, D. Shah, and M. Sharma. Maximum weight matching via max-product belief propagation. IEEE Trans. on Information Theory (to appear), 2007. [2] D. P. Bertsekas, editor. Nonlinear Programming. Athena Scientiﬁc, Belmont, MA, 1995. [3] A. Globerson and T. Jaakkola. Convergent propagation algorithms via oriented trees. In UAI. 2007. [4] J.K. Johnson, D.M. Malioutov, and A.S. Willsky. Lagrangian relaxation for map estimation in graphical models. In Allerton Conf. Communication, Control and Computing, 2007. [5] V. Kolmogorov. Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10):1568–1583, 2006. [6] V. Kolmogorov and M. Wainwright. On the optimality of tree-reweighted max-product message passing. In 21st Conference on Uncertainty in Artiﬁcial Intelligence (UAI). 2005. [7] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988. [8] B. Taskar, S. Lacoste-Julien, and M. Jordan. Structured prediction, dual extragradient and bregman projections. Journal of Machine Learning Research, pages 1627–1653, 2006. [9] P.O. Vontobel and R. Koetter. Towards low-complexity linear-programming decoding. In Proc. 4th Int. Symposium on Turbo Codes and Related Topics, 2006. [10] M. J. Wainwright, T. Jaakkola, and A. S. Willsky. Map estimation via agreement on trees: messagepassing and linear programming. IEEE Trans. on Information Theory, 51(11):1120–1146, 2005. [11] Y. Weiss, C. Yanover, and T. Meltzer. Map estimation, linear programming and belief propagation with convex free energies. In UAI. 2007. [12] T. Werner. A linear programming approach to max-sum, a review. IEEE Trans. on PAMI, 2007. [13] C. Yanover, T. Meltzer, and Y. Weiss. Linear programming relaxations and belief propagation – an empirical study. Jourmal of Machine Learning Research, 7:1887–1907, 2006. [14] J.S. Yedidia, W.T. W.T. Freeman, and Y. Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Trans. on Information Theory, 51(7):2282–2312, 2005. 7 Other solutions are possible but may not yield some of the properties of MPLP. 8

4 0.11255074 123 nips-2007-Loop Series and Bethe Variational Bounds in Attractive Graphical Models

Author: Alan S. Willsky, Erik B. Sudderth, Martin J. Wainwright

Abstract: Variational methods are frequently used to approximate or bound the partition or likelihood function of a Markov random ﬁeld. Methods based on mean ﬁeld theory are guaranteed to provide lower bounds, whereas certain types of convex relaxations provide upper bounds. In general, loopy belief propagation (BP) provides often accurate approximations, but not bounds. We prove that for a class of attractive binary models, the so–called Bethe approximation associated with any ﬁxed point of loopy BP always lower bounds the true likelihood. Empirically, this bound is much tighter than the naive mean ﬁeld bound, and requires no further work than running BP. We establish these lower bounds using a loop series expansion due to Chertkov and Chernyak, which we show can be derived as a consequence of the tree reparameterization characterization of BP ﬁxed points. 1

5 0.10499038 128 nips-2007-Message Passing for Max-weight Independent Set

Author: Sujay Sanghavi, Devavrat Shah, Alan S. Willsky

Abstract: We investigate the use of message-passing algorithms for the problem of ﬁnding the max-weight independent set (MWIS) in a graph. First, we study the performance of loopy max-product belief propagation. We show that, if it converges, the quality of the estimate is closely related to the tightness of an LP relaxation of the MWIS problem. We use this relationship to obtain sufﬁcient conditions for correctness of the estimate. We then develop a modiﬁcation of max-product – one that converges to an optimal solution of the dual of the MWIS problem. We also develop a simple iterative algorithm for estimating the max-weight independent set from this dual solution. We show that the MWIS estimate obtained using these two algorithms in conjunction is correct when the graph is bipartite and the MWIS is unique. Finally, we show that any problem of MAP estimation for probability distributions over ﬁnite domains can be reduced to an MWIS problem. We believe this reduction will yield new insights and algorithms for MAP estimation. 1

6 0.092900209 75 nips-2007-Efficient Bayesian Inference for Dynamically Changing Graphs

7 0.089760706 187 nips-2007-Structured Learning with Approximate Inference

8 0.088646963 64 nips-2007-Cooled and Relaxed Survey Propagation for MRFs

9 0.081892304 120 nips-2007-Linear programming analysis of loopy belief propagation for weighted matching

10 0.070932455 20 nips-2007-Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis

11 0.065005027 97 nips-2007-Hidden Common Cause Relations in Relational Learning

12 0.062189557 157 nips-2007-Privacy-Preserving Belief Propagation and Sampling

13 0.059527282 94 nips-2007-Gaussian Process Models for Link Analysis and Transfer Learning

14 0.058022909 23 nips-2007-An Analysis of Convex Relaxations for MAP Estimation

15 0.055553969 68 nips-2007-Discovering Weakly-Interacting Factors in a Complex Stochastic Process

16 0.052141294 78 nips-2007-Efficient Principled Learning of Thin Junction Trees

17 0.050223008 204 nips-2007-Theoretical Analysis of Heuristic Search Methods for Online POMDPs

18 0.048975766 160 nips-2007-Random Features for Large-Scale Kernel Machines

19 0.04797883 48 nips-2007-Collective Inference on Markov Models for Modeling Bird Migration

20 0.046388242 115 nips-2007-Learning the 2-D Topology of Images

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.168), (1, -0.01), (2, -0.08), (3, 0.012), (4, -0.068), (5, -0.205), (6, -0.001), (7, 0.146), (8, 0.1), (9, -0.094), (10, -0.07), (11, 0.012), (12, -0.047), (13, 0.087), (14, 0.066), (15, -0.077), (16, 0.023), (17, 0.026), (18, -0.054), (19, 0.031), (20, 0.018), (21, 0.039), (22, 0.033), (23, -0.02), (24, -0.004), (25, -0.022), (26, 0.087), (27, -0.025), (28, -0.002), (29, -0.025), (30, 0.021), (31, 0.049), (32, -0.029), (33, 0.076), (34, -0.062), (35, 0.072), (36, 0.13), (37, 0.012), (38, 0.002), (39, -0.032), (40, 0.013), (41, 0.048), (42, 0.064), (43, -0.146), (44, -0.023), (45, -0.107), (46, 0.007), (47, -0.141), (48, -0.094), (49, -0.077)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95448148 121 nips-2007-Local Algorithms for Approximate Inference in Minor-Excluded Graphs

Author: Kyomin Jung, Devavrat Shah

2 0.85874796 141 nips-2007-New Outer Bounds on the Marginal Polytope

Author: David Sontag, Tommi S. Jaakkola

3 0.64391792 123 nips-2007-Loop Series and Bethe Variational Bounds in Attractive Graphical Models

Author: Alan S. Willsky, Erik B. Sudderth, Martin J. Wainwright

4 0.58693302 128 nips-2007-Message Passing for Max-weight Independent Set

Author: Sujay Sanghavi, Devavrat Shah, Alan S. Willsky

5 0.53334677 187 nips-2007-Structured Learning with Approximate Inference

Author: Alex Kulesza, Fernando Pereira

Abstract: In many structured prediction problems, the highest-scoring labeling is hard to compute exactly, leading to the use of approximate inference methods. However, when inference is used in a learning algorithm, a good approximation of the score may not be sufﬁcient. We show in particular that learning can fail even with an approximate inference method with rigorous approximation guarantees. There are two reasons for this. First, approximate methods can effectively reduce the expressivity of an underlying model by making it impossible to choose parameters that reliably give good predictions. Second, approximations can respond to parameter changes in such a way that standard learning algorithms are misled. In contrast, we give two positive results in the form of learning bounds for the use of LP-relaxed inference in structured perceptron and empirical risk minimization settings. We argue that without understanding combinations of inference and learning, such as these, that are appropriately compatible, learning performance under approximate inference cannot be guaranteed. 1

6 0.5184955 92 nips-2007-Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations

7 0.51438171 64 nips-2007-Cooled and Relaxed Survey Propagation for MRFs

8 0.48373815 120 nips-2007-Linear programming analysis of loopy belief propagation for weighted matching

9 0.47615373 75 nips-2007-Efficient Bayesian Inference for Dynamically Changing Graphs

10 0.41317162 20 nips-2007-Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis

11 0.39627436 78 nips-2007-Efficient Principled Learning of Thin Junction Trees

12 0.38398415 138 nips-2007-Near-Maximum Entropy Models for Binary Neural Representations of Natural Images

13 0.37992582 23 nips-2007-An Analysis of Convex Relaxations for MAP Estimation

14 0.37870729 157 nips-2007-Privacy-Preserving Belief Propagation and Sampling

15 0.35951629 97 nips-2007-Hidden Common Cause Relations in Relational Learning

16 0.34092373 77 nips-2007-Efficient Inference for Distributions on Permutations

17 0.32699674 68 nips-2007-Discovering Weakly-Interacting Factors in a Complex Stochastic Process

18 0.31341615 82 nips-2007-Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization

19 0.31077757 131 nips-2007-Modeling homophily and stochastic equivalence in symmetric relational data

20 0.30254066 94 nips-2007-Gaussian Process Models for Link Analysis and Transfer Learning

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(5, 0.042), (13, 0.023), (21, 0.042), (34, 0.487), (35, 0.019), (47, 0.054), (83, 0.146), (85, 0.023), (87, 0.011), (90, 0.047)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.82752138 121 nips-2007-Local Algorithms for Approximate Inference in Minor-Excluded Graphs

Author: Kyomin Jung, Devavrat Shah

2 0.82474989 17 nips-2007-A neural network implementing optimal state estimation based on dynamic spike train decoding

Author: Omer Bobrowski, Ron Meir, Shy Shoham, Yonina Eldar

Abstract: It is becoming increasingly evident that organisms acting in uncertain dynamical environments often employ exact or approximate Bayesian statistical calculations in order to continuously estimate the environmental state, integrate information from multiple sensory modalities, form predictions and choose actions. What is less clear is how these putative computations are implemented by cortical neural networks. An additional level of complexity is introduced because these networks observe the world through spike trains received from primary sensory afferents, rather than directly. A recent line of research has described mechanisms by which such computations can be implemented using a network of neurons whose activity directly represents a probability distribution across the possible “world states”. Much of this work, however, uses various approximations, which severely restrict the domain of applicability of these implementations. Here we make use of rigorous mathematical results from the theory of continuous time point process ﬁltering, and show how optimal real-time state estimation and prediction may be implemented in a general setting using linear neural networks. We demonstrate the applicability of the approach with several examples, and relate the required network properties to the statistical nature of the environment, thereby quantifying the compatibility of a given network with its environment. 1

3 0.79709488 126 nips-2007-McRank: Learning to Rank Using Multiple Classification and Gradient Boosting

Author: Ping Li, Qiang Wu, Christopher J. Burges

Abstract: We cast the ranking problem as (1) multiple classiﬁcation (“Mc”) (2) multiple ordinal classiﬁcation, which lead to computationally tractable learning algorithms for relevance ranking in Web search. We consider the DCG criterion (discounted cumulative gain), a standard quality measure in information retrieval. Our approach is motivated by the fact that perfect classiﬁcations result in perfect DCG scores and the DCG errors are bounded by classiﬁcation errors. We propose using the Expected Relevance to convert class probabilities into ranking scores. The class probabilities are learned using a gradient boosting tree algorithm. Evaluations on large-scale datasets show that our approach can improve LambdaRank [5] and the regressions-based ranker [6], in terms of the (normalized) DCG scores. An efﬁcient implementation of the boosting tree algorithm is also presented.

4 0.78147054 44 nips-2007-Catching Up Faster in Bayesian Model Selection and Model Averaging

Author: Tim V. Erven, Steven D. Rooij, Peter Grünwald

Abstract: Bayesian model averaging, model selection and their approximations such as BIC are generally statistically consistent, but sometimes achieve slower rates of convergence than other methods such as AIC and leave-one-out cross-validation. On the other hand, these other methods can be inconsistent. We identify the catch-up phenomenon as a novel explanation for the slow convergence of Bayesian methods. Based on this analysis we deﬁne the switch-distribution, a modiﬁcation of the Bayesian model averaging distribution. We prove that in many situations model selection and prediction based on the switch-distribution is both consistent and achieves optimal convergence rates, thereby resolving the AIC-BIC dilemma. The method is practical; we give an efﬁcient algorithm. 1

5 0.50761014 92 nips-2007-Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations

Author: Amir Globerson, Tommi S. Jaakkola

6 0.48555991 123 nips-2007-Loop Series and Bethe Variational Bounds in Attractive Graphical Models

7 0.47926903 83 nips-2007-Evaluating Search Engines by Modeling the Relationship Between Relevance and Clicks

8 0.45826882 128 nips-2007-Message Passing for Max-weight Independent Set

9 0.45739022 141 nips-2007-New Outer Bounds on the Marginal Polytope

10 0.45556578 41 nips-2007-COFI RANK - Maximum Margin Matrix Factorization for Collaborative Ranking

11 0.45191717 39 nips-2007-Boosting the Area under the ROC Curve

12 0.4516848 146 nips-2007-On higher-order perceptron algorithms

13 0.45023426 6 nips-2007-A General Boosting Method and its Application to Learning Ranking Functions for Web Search

14 0.43855289 149 nips-2007-Optimal ROC Curve for a Combination of Classifiers

15 0.43537635 187 nips-2007-Structured Learning with Approximate Inference

16 0.43409887 171 nips-2007-Scan Strategies for Meteorological Radars

17 0.42777926 142 nips-2007-Non-parametric Modeling of Partially Ranked Data

18 0.42002892 177 nips-2007-Simplified Rules and Theoretical Analysis for Information Bottleneck Optimization and PCA with Spiking Neurons

19 0.41793954 21 nips-2007-Adaptive Online Gradient Descent

20 0.41782987 147 nips-2007-One-Pass Boosting