nips nips2010 nips2010-165 knowledge-graph by maker-knowledge-mining

165 nips-2010-MAP estimation in Binary MRFs via Bipartite Multi-cuts

Source: pdf

Author: Sashank J. Reddi, Sunita Sarawagi, Sundar Vishwanathan

Abstract: We propose a new LP relaxation for obtaining the MAP assignment of a binary MRF with pairwise potentials. Our relaxation is derived from reducing the MAP assignment problem to an instance of a recently proposed Bipartite Multi-cut problem where the LP relaxation is guaranteed to provide an O(log k) approximation where k is the number of vertices adjacent to non-submodular edges in the MRF. We then propose a combinatorial algorithm to efﬁciently solve the LP and also provide a lower bound by concurrently solving its dual to within an approximation. The algorithm is up to an order of magnitude faster and provides better MAP scores and bounds than the state of the art message passing algorithm of [1] that tightens the local marginal polytope with third-order marginal constraints. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Our relaxation is derived from reducing the MAP assignment problem to an instance of a recently proposed Bipartite Multi-cut problem where the LP relaxation is guaranteed to provide an O(log k) approximation where k is the number of vertices adjacent to non-submodular edges in the MRF. [sent-12, score-0.352]

2 We then propose a combinatorial algorithm to efﬁciently solve the LP and also provide a lower bound by concurrently solving its dual to within an approximation. [sent-13, score-0.125]

3 The algorithm is up to an order of magnitude faster and provides better MAP scores and bounds than the state of the art message passing algorithm of [1] that tightens the local marginal polytope with third-order marginal constraints. [sent-14, score-0.306]

4 , xn expressed as a graph G = (V, E) and an energy function E(x|θ) whose parameters θ decompose over its vertices and edges as: E(x|θ) = θi (xi ) + i∈V θij (xi , xj ) + θconst (1) (i,j)∈E ∗ Our goal is to ﬁnd a x = argminx∈{0,1}n E(x|θ). [sent-18, score-0.336]

5 This is called the MAP assignment problem in graphical models and for general graphs and arbitrary parameters is NP complete. [sent-19, score-0.108]

6 Both these methods ﬁnd the exact MAP when the edge parameters are submodular. [sent-23, score-0.113]

7 More principled methods to improve the solution output by the relaxed LP are based on progressively tightening the relaxation with violated constraints. [sent-28, score-0.167]

8 Cycle constraints [15, 16, 17, 18, 1, 19] and higher order marginal constraints [17, 1, 20] are two such types of constraints. [sent-29, score-0.145]

9 In this paper we propose a new relaxation of the MAP estimation problem via reduction to a recently proposed Bipartite Multi-cut problem in undirected graphs [21]. [sent-31, score-0.144]

10 We propose a combinatorial algorithm to efﬁciently solve this LP by casting it as a Multi-cut problem on a specially constructed graph, the dual of which is a multi-commodity ﬂow problem. [sent-34, score-0.125]

11 The algorithm, adapted from [22, 23], simultaneously updates the primal and dual solutions, and thus at any point provides both a candidate solution and a lower bound to the energy function. [sent-35, score-0.239]

12 It is guaranteed to provide an - approximate solution of the primal LP in O( −2 (|V|+|E|)2 ) time but in practice terminates much faster. [sent-36, score-0.127]

13 No such guarantees exist for any of the existing algorithms for tightening the MAP LP based on cycle or higher order marginals constraints. [sent-37, score-0.191]

14 Empirically, this algorithm is an order of magnitude faster than the state of the art message passing algorithm[1] while yielding the same or better MAP values and bounds. [sent-38, score-0.118]

15 We show that our LP is a relaxation of the LP with cycle constraints, but we still yield better and faster bounds because our combinatorial algorithm solves the LP within a guaranteed approximation. [sent-39, score-0.326]

16 Symmetric, that is for {xi , xj } ∈ {0, 1} θij (xi , xj ) = θij (xi , xj ) where xi = 1 − xi , 2. [sent-41, score-0.249]

17 xi ,xj xi It is easy to see that any energy function over binary variables can be reparameterized in this form2 . [sent-43, score-0.22]

18 Our starting point is the LP relaxation proposed in [13] for approximating MAP x∗ = argminx E(x|θ) as the minimum s-t cut in a suitably constructed graph H = (V H , E H ). [sent-44, score-0.208]

19 1 Graph cut-based relaxation of [13] For ease of notation, ﬁrst augment the n variables with a special “0” variable that always takes a label of 0 and has an edge to all n variables. [sent-47, score-0.277]

20 This enables us to redeﬁne the node parameters θi (xi ) as edge parameters θ0i (0, xi ). [sent-48, score-0.196]

21 For each edge (i, j) ∈ E, add an edge between i0 and j0 with weight θij (0, 1) if the edge is submodular, else add edge (i0 , j1 ) with weight θij (0, 0). [sent-50, score-0.504]

22 For every vertex i, if θi (1) is non-zero add an edge between 00 and i0 with weight θi (1) else add edge between 01 and i0 with weight θi (0). [sent-51, score-0.278]

23 (i,j)∈E 2 variables are further constrained to take integral values (with D(i0 ) ≡ xi ). [sent-55, score-0.121]

24 ) e∈E H we de de + D(is ) − D(jt ) ≥ 0 ∀e = (is , jt ) ∈ E H de + D(jt ) − D(is ) ≥ 0 ∀e = (is , jt ) ∈ E H D(00 ) = 0 D(is ) ∈ [0, 1] ∀is ∈ V H de ∈ [0, 1] ∀e ∈ E H D(i0 ) + D(i1 ) = 1 ∀i ∈ {0, . [sent-57, score-0.482]

25 Given an undirected graph J = (N , A) with non-negative edge weights, the s-t Min-cut problem ﬁnds the subset of edges with minimum total weight, whose deletion disconnects s and t. [sent-66, score-0.285]

26 (sk , tk )}, and the goal is ﬁnd a subset of vertices M ⊂ N such that | {si , ti } ∩ M |= 1 and the total weight of edges from M to the remaining vertices N − M is minimized. [sent-70, score-0.281]

27 The BMC problem is also related to the more popular Multi-cut problem where the goal is to identify the smallest weight set of edges such that every si and ti are separated. [sent-72, score-0.133]

28 To see this, consider a graph over six vertices (s1 , s2 , s3 , t1 , t2 , t3 ) and three edges (s1 , s3 ), (t1 , t2 ), (s2 , t3 ). [sent-74, score-0.246]

29 We reduce the MAP estimation problem to the Bipartite Multi-cut problem on an optimized version of graph H constructed so that the set of variables R adjacent to non-submodular edges is minimized. [sent-78, score-0.244]

30 The remaining variables j ∈ V − R do not need the j1 copy of j in H since there have no edges adjacent to j1 . [sent-85, score-0.178]

31 The MAP labeling x∗ is obtained from M by setting xi = s if is ∈ M and xi = s if ¯ is ∈ V H − M . [sent-88, score-0.136]

32 , k0 , k1 } and js ∈ V H we deﬁne new variables Du (js ) and use these to augment the Min-cut LP with additional 3 constraints as follows: min de ,Du (. [sent-94, score-0.251]

33 ) e∈E H we de de + Du (is ) − Du (jt ) ≥ 0 de + Du (jt ) − Du (is ) ≥ 0 ∀e = (is , jt ) ∈ E H , ∀u ∈ {00 , 01 . [sent-95, score-0.241]

34 , k} Di0 (j1 ) = Di1 (j0 ) A useful interpretation of the above LP is provided by viewing variables de as the distance between is and jt for any edge e = (is , jt ), and variables Du (js ) as the distance between u and js . [sent-107, score-0.793]

35 These, along with the constraint Di0 (i1 ) ≥ 1 ensure that for every ST pair (i0 , i1 ), any path P from i0 to i1 has e∈P de ≥ 1. [sent-109, score-0.112]

36 Later, in Section 5 we will establish a connection between these constraints and cycle constraints [15, 16, 17, 18, 19]. [sent-111, score-0.233]

37 When the variables are not integral, [21] suggests a region growing approach for rounding them so as to get a O(log k) approximation of the optimal objective. [sent-113, score-0.107]

38 In practice, we found that ICM starting with fractional node assignments xi = D00 (i0 ) gave better results. [sent-114, score-0.114]

39 3 Reducing the size of ST set In the LP above, for every edge that is non-submodular we add a terminal pair to ST corresponding to any of its two endpoints. [sent-116, score-0.172]

40 The problem of minimizing the size of the ST set is equivalent to the problem of ﬁnding the minimum set R of variables of G such that all cycles with an odd number of non-submodular edges are covered. [sent-117, score-0.187]

41 It is easy that see that in any such cycle, it is always possible to ﬂip the variables such that any one selected edge is non-submodular and the rest are submodular. [sent-118, score-0.159]

42 First, we pick the set of variables to ﬂip so as to minimize the number of non-submodular edges, and then obtain a vertex cover of the reduced non-submodular edges using a greedy algorithm. [sent-120, score-0.152]

43 Thus, if an edge is submodular and both variables attached to it are ﬂipped (i. [sent-122, score-0.189]

44 With the above LP formulation, we were able to obtain exact solutions for most 20x20 grids and 25 node clique graphs. [sent-126, score-0.126]

45 However, the LP does not scale beyond 30x30 grid and 50 node clique graphs. [sent-127, score-0.126]

46 1 Garg’s algorithm for the Multi-cut problem Recall that in the Multi-cut problem, the goal is to remove the minimum weight set of edges so as to separate each (si , ti ) pair in ST. [sent-134, score-0.133]

47 This problem is formulated as the followed primal dual LP pair in [22]. [sent-135, score-0.17]

48 Multi-cut LP: Primal min d Multi-cut LP: Dual we de max f e∈E H de ≥ 1 fP P ∈P fP ≤ we ∀P ∈ P ∀e ∈ EH P ∈Pe e∈P de ≥ 0 fP ≥ 0 ∀e ∈ E H ∀P ∈ P where P denotes all paths between a pair of vertices in ST and Pe denotes the set of paths in P which contain edge e. [sent-136, score-0.295]

49 Garg’s algorithm [22, 23] simultaneously solves the primal and dual so that they are within an factor of each other for any user-provided > 0. [sent-137, score-0.17]

50 The algorithm starts by setting all dual variables ﬂow variables to zero and all primal variables de = δ where δ is (1 + )/((1 + )L)1/ , and L is the maximum number of edges for any path in P. [sent-138, score-0.526]

51 It then iteratively updates the variables by ﬁrst ﬁnding the shortest path P ∈ P which violates the e∈P de ≥ 1 constraint and then, modifying f variables as fP = mine∈P we i. [sent-139, score-0.244]

52 At any point a feasible e solution can be obtained by rescaling all the primal and dual variables. [sent-141, score-0.244]

53 Termination is reached when the rescaled primal objective is within (1 + ) of the rescaled dual objective for error parameter . [sent-142, score-0.226]

54 2 Solving the BMC LP We ﬁrst modify the edge weights on graph H constructed for the BMC LP so that for all edges e = (is , jt ) and its complement e = (is , jt ), the weights are equal, that is, we = we . [sent-145, score-0.796]

55 This can be ¯ ¯ ¯ ¯ easily ensured by setting we = we = average of previous edge weights of e and e in H. [sent-146, score-0.113]

56 For any path P in H we deﬁne its complementary path P to be the path obtained by reversing the order of edges and complementing all edges in P . [sent-149, score-0.578]

57 For example, the complement of path (20 , 11 , 30 , 21 ) is (20 , 31 , 10 , 21 ). [sent-150, score-0.141]

58 Next, we consider the following alternative LP called BMC-Sym LP for BMC on symmetric graphs, that is, graphs where we = we ¯ min we de e∈E H de ≥ 1 ∀P ∈ P (BMC-Sym LP) e∈P de ≥ 0, de = de ∀e ∈ E H Lemma 1 When H is symmetric, the BMC-Sym LP, BMC LP, and Multi-cut LP are equivalent. [sent-151, score-0.111]

59 P ROOF Any feasible solution of BMC-Sym LP can be used to obtain a solution to BMC LP with the same objective as follows: Set de variables unchanged, this keeps the objective intact. [sent-152, score-0.204]

60 Set Du (is ) as the length of the shortest path between u and is that is, Du (is ) = minP ∈paths(u,is ) e∈P de . [sent-153, score-0.152]

61 This yields a feasible solution — the constraints de + Du (is ) − Du (jt ) ≥ 0 hold because Du (is ) variables are the shortest path between u and is . [sent-154, score-0.326]

62 The constraints Di0 (i1 ) ≥ 1 hold because all paths between i0 and i1 have a distance ≥ 1 in BMC-Sym LP. [sent-155, score-0.108]

63 We next show that any feasible solution of BMC LP gives a feasible solution to Multi-cut LP with the same de and objective value. [sent-157, score-0.176]

64 For any pair (p0 , p1 ) ∈ ST the constraint Dp0 (p1 ) ≥ 1 along with repeated application of de +Dp0 (is )−Dp0 (jt ) ≥ 0 ensures that e∈P de ≥ 1 for any path between p0 and p1 . [sent-158, score-0.137]

65 Finally, we show that if {de } is a feasible solution to Multi-cut LP then it can be used to construct a feasible solution {de } to BMC-Sym LP without changing the value of the objective function using 5 de = de = (de + de )/2. [sent-159, score-0.176]

66 The path constraints e∈P de ≥ 1 hold ∀P ∈ P because both path P and its complementary path P are in P and we know that e∈P de ≥ 1 and e∈P de = e∈P de ≥ 1. [sent-161, score-0.42]

67 We modify Garg’s algorithm [22, 23] to exploit the fact that the graph is symmetric so that at each iteration we push twice the ﬂow while keeping the approximation guarantees intact. [sent-162, score-0.131]

68 The key change we make is that when augmenting ﬂow f in some path P , we augment the same ﬂow f to the complementary path P as outlined in our ﬁnal algorithm in Figure 1. [sent-163, score-0.299]

69 Lemma 2 Suppose H is a symmetric graph then de = de ∀ e ∈ E H at the end of each iteration of the while loop in algorithm in Figure 1. [sent-165, score-0.131]

70 Let Pi denote the path selected in the ith iteration of the algorithm. [sent-168, score-0.137]

71 These paths Pn+1 and P n+1 do not share any edge because this would imply that there is another pair (j0 , j1 ) of shorter length, and we would choose Pn+1 to be this path instead. [sent-171, score-0.279]

72 P ROOF Suppose, we do not augment the ﬂow in the complementary path P while augmenting P . [sent-175, score-0.187]

73 In the next iteration the original algorithm of [22, 23] picks P or any path with the same path length since the path length of P and P is equal before the iteration and they do not share any common edges. [sent-176, score-0.386]

74 Input: Graphical model G with reparameterized energy function E, approximation guarantee Create symmetric graph H from G and E Initialize de = δ (δ derived from as shown in Section 3. [sent-178, score-0.178]

75 1), and f = 0, fe = 0, x=arbitrary initial labeling of graphical model G. [sent-179, score-0.179]

76 e e∈P Repeat above for the complement path P x = current solution after rounding, x =better of x and x end if end while Return bound = D(f, {fe }) + θconst , MAP = x. [sent-181, score-0.169]

77 Our algorithm in addition to updating the primal and dual solutions at each iteration, also keeps track of the primal objective obtained with the current best rounding (x in Figure 1). [sent-183, score-0.358]

78 Often, the rounded variables yielded lower primal objective values and led to early termination. [sent-184, score-0.173]

79 5 200 0 50 Time in seconds 100 150 200 (c) Edge strength = 2 Figure 3: Comparing convergence rates of BMC and MPLP for three different clique graphs. [sent-207, score-0.119]

80 4 Experiments We compare our proposed algorithm (called BMC here) with MPLP, a state-of-art message passing algorithm [1] that tightens the standard MAP LP with third order marginal constraints, which are equivalent to cycle constraints for binary MRFs. [sent-208, score-0.333]

81 MPLP was run with edge clusters until convergence (up to a precision of 2 × 10−4 ) or for at most 1000 iterations, whichever comes ﬁrst. [sent-213, score-0.113]

82 Our experiments were performed on two kinds of datasets: (1) Clique graph based binary MRFs of various sizes generated as per the method of [17] where edge potentials are Potts sampled from U [−σ, σ] (our default setting was σ = 0. [sent-214, score-0.179]

83 In the graphs in Figure 2 we compare BMC, MPLP, and TRW-S with increasing clique size averaged over ﬁve seeds. [sent-219, score-0.165]

84 We observe that BMC provides much higher MAP scores and slightly tighter bounds than MPLP. [sent-220, score-0.125]

85 In Figures 3(a), (b), and (c) we show the MAP and Upper bounds for different times in the execution of the algorithm on cliques of size 50 and different edge strengths. [sent-224, score-0.155]

86 BMC, whose bounds and MAP appear as the two short arcs in-between the MAP scores and bounds of MPLP, converges signiﬁcantly faster and terminates well before MPLP while providing same or better MAP scores and bounds for all edge strengths. [sent-225, score-0.353]

87 The upper bounds achieved by MPLP are signiﬁcantly tighter than TRW-S, showing that with proper rounding MPLP is likely to produce good MAP scores, but BMC provides even tighter bounds in 3 http://biqmac. [sent-230, score-0.229]

88 The running time for BMC is signiﬁcantly lower than MPLP for dense graphs but for sparse graphs (10% edges) it requires the same time as MPLP. [sent-253, score-0.142]

89 Thus, overall we ﬁnd that BMC achieves tighter bounds and better MAP solutions at a signiﬁcantly faster rate than the state-of-the-art method for tightening LPs. [sent-254, score-0.182]

90 For sparse graphs many algorithms work, for example recently [8, 26] reported excellent results on planar, or nearly planar graphs and [27] show that even local search works when the graph is sparse. [sent-256, score-0.253]

91 5 Discussion and Conclusion We put our tightening of the basic MAP LP (Marginal LP in Equation 2 or the Min-cut LP) in perspective with other proposed tightenings based on cycle constraints [17, 18, 1, 19] and higher order marginal constraints [17, 1, 20]. [sent-257, score-0.371]

92 For binary MRFs cycle constraints are equivalent to adding marginal consistency constraints among triples of variables [28]. [sent-258, score-0.316]

93 We show the relationship between cycle constraints and our constraints. [sent-259, score-0.179]

94 Let S = (VS , ES ) denote the minimum cut graph created from G as shown in Section 2. [sent-260, score-0.11]

95 1 but without the i1 vertices for (1 ≤ i ≤ n) so that weights of non-submodular edges in S will be negative. [sent-261, score-0.18]

96 The LP relaxation of MAP based on cycle constraints is deﬁned as: we de min d e∈ES (1 − de ) + e∈F de ≥ 1 ∀C ∈ C, F ⊆ C and | F | is odd ∈ [0 . [sent-262, score-0.287]

97 Suppose we construct our symmetric minimum cut graph H with edges (is , jt ) corresponding to all four possible values of (s, t) for each edge (i, j) ∈ E, instead of two that we currently get due to zero-normalized edge potentials. [sent-266, score-0.723]

98 Then, BMC-Sym LP along with the constraints dis jt + dis jt = 1 ∀(is , jt ) ∈ EH is equivalent to the cycle LP above. [sent-267, score-0.902]

99 Our main contribution is that by relaxing the cycle LP to the Bipartite Multi-cut LP we have been able to design a combinatorial algorithm which is guaranteed to provide an approximation to the LP in polynomial time. [sent-269, score-0.179]

100 Since we solve the LP and its dual better than any of the earlier methods of enforcing cycle constraints, we are able to obtain tighter bounds and MAP scores at a considerable faster speed. [sent-270, score-0.353]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('lp', 0.49), ('bmc', 0.45), ('mplp', 0.339), ('jt', 0.241), ('map', 0.163), ('ij', 0.127), ('cycle', 0.125), ('bipartite', 0.116), ('edge', 0.113), ('path', 0.112), ('du', 0.11), ('fe', 0.108), ('edges', 0.106), ('js', 0.106), ('fp', 0.1), ('primal', 0.099), ('clique', 0.094), ('garg', 0.08), ('vertices', 0.074), ('relaxation', 0.073), ('st', 0.072), ('graphs', 0.071), ('dual', 0.071), ('tightening', 0.066), ('const', 0.066), ('graph', 0.066), ('rounding', 0.061), ('mrfs', 0.058), ('ow', 0.055), ('constraints', 0.054), ('paths', 0.054), ('combinatorial', 0.054), ('roof', 0.053), ('biqmac', 0.053), ('bombay', 0.053), ('naveen', 0.053), ('sundar', 0.053), ('xi', 0.051), ('xj', 0.049), ('relaxations', 0.049), ('message', 0.049), ('fleischer', 0.046), ('feasible', 0.046), ('variables', 0.046), ('augment', 0.045), ('planar', 0.045), ('cut', 0.044), ('tommi', 0.043), ('tighter', 0.042), ('bounds', 0.042), ('energy', 0.041), ('scores', 0.041), ('symmetric', 0.04), ('iit', 0.04), ('vladimir', 0.04), ('wp', 0.04), ('shortest', 0.04), ('pn', 0.04), ('sontag', 0.038), ('marginal', 0.037), ('graphical', 0.037), ('passing', 0.037), ('multicommodity', 0.035), ('sashank', 0.035), ('tightenings', 0.035), ('odd', 0.035), ('labeling', 0.034), ('terminal', 0.033), ('node', 0.032), ('faster', 0.032), ('amir', 0.032), ('fractional', 0.031), ('tightens', 0.031), ('talya', 0.031), ('maxcut', 0.031), ('reparameterized', 0.031), ('sunita', 0.031), ('globerson', 0.03), ('submodular', 0.03), ('complementary', 0.03), ('complement', 0.029), ('ipped', 0.028), ('solution', 0.028), ('objective', 0.028), ('ti', 0.027), ('meltzer', 0.027), ('reparameterization', 0.027), ('eh', 0.027), ('tighten', 0.027), ('minp', 0.027), ('adjacent', 0.026), ('add', 0.026), ('mrf', 0.026), ('argminx', 0.025), ('nikos', 0.025), ('ensures', 0.025), ('seconds', 0.025), ('iteration', 0.025), ('integral', 0.024), ('mine', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000008 165 nips-2010-MAP estimation in Binary MRFs via Bipartite Multi-cuts

Author: Sashank J. Reddi, Sunita Sarawagi, Sundar Vishwanathan

2 0.39229834 164 nips-2010-MAP Estimation for Graphical Models by Likelihood Maximization

Author: Akshat Kumar, Shlomo Zilberstein

Abstract: Computing a maximum a posteriori (MAP) assignment in graphical models is a crucial inference problem for many practical applications. Several provably convergent approaches have been successfully developed using linear programming (LP) relaxation of the MAP problem. We present an alternative approach, which transforms the MAP problem into that of inference in a mixture of simple Bayes nets. We then derive the Expectation Maximization (EM) algorithm for this mixture that also monotonically increases a lower bound on the MAP assignment until convergence. The update equations for the EM algorithm are remarkably simple, both conceptually and computationally, and can be implemented using a graph-based message passing paradigm similar to max-product computation. Experiments on the real-world protein design dataset show that EM’s convergence rate is signiﬁcantly higher than the previous LP relaxation based approach MPLP. EM also achieves a solution quality within 95% of optimal for most instances. 1

3 0.14307968 288 nips-2010-Worst-case bounds on the quality of max-product fixed-points

Author: Meritxell Vinyals, Jes\'us Cerquides, Alessandro Farinelli, Juan A. Rodríguez-aguilar

Abstract: We study worst-case bounds on the quality of any ﬁxed point assignment of the max-product algorithm for Markov Random Fields (MRF). We start providing a bound independent of the MRF structure and parameters. Afterwards, we show how this bound can be improved for MRFs with speciﬁc structures such as bipartite graphs or grids. Our results provide interesting insight into the behavior of max-product. For example, we prove that max-product provides very good results (at least 90% optimal) on MRFs with large variable-disjoint cycles1 . 1

4 0.13263662 169 nips-2010-More data means less inference: A pseudo-max approach to structured learning

Author: David Sontag, Ofer Meshi, Amir Globerson, Tommi S. Jaakkola

Abstract: The problem of learning to predict structured labels is of key importance in many applications. However, for general graph structure both learning and inference are intractable. Here we show that it is possible to circumvent this difﬁculty when the distribution of training examples is rich enough, via a method similar in spirit to pseudo-likelihood. We show that our new method achieves consistency, and illustrate empirically that it indeed approaches the performance of exact methods when sufﬁciently large training sets are used. Many prediction problems in machine learning applications are structured prediction tasks. For example, in protein folding we are given a protein sequence and the goal is to predict the protein’s native structure [14]. In parsing for natural language processing, we are given a sentence and the goal is to predict the most likely parse tree [2]. In these and many other applications, we can formalize the structured prediction problem as taking an input x (e.g., primary sequence, sentence) and predicting ˆ y (e.g., structure, parse) according to y = arg maxy∈Y θ · φ(x, y ), where φ(x, y) is a function that ˆ maps any input and a candidate assignment to a feature vector, Y denotes the space of all possible assignments to the vector y, and θ is a weight vector to be learned. This paper addresses the problem of learning structured prediction models from data. In particular, given a set of labeled examples {(xm , y m )}M , our goal is to ﬁnd a vector θ such that for each m=1 example m, y m = arg maxy∈Y θ · φ(xm , y), i.e. one which separates the training data. For many structured prediction models, maximization over Y is computationally intractable. This makes it difﬁcult to apply previous algorithms for learning structured prediction models, such as structured perceptron [2], stochastic subgradient [10], and cutting-plane algorithms [5], which require making a prediction at every iteration (equivalent to repeatedly solving an integer linear program). Given training data, we can consider the space of parameters Θ that separate the data. This space can be deﬁned by the intersection of a large number of linear inequalities. A recent approach to getting around the hardness of prediction is to use linear programming (LP) relaxations to approximate the maximization over Y [4, 6, 9]. However, separation with respect to a relaxation places stronger constraints on the parameters. The target solution, an integral vertex in the LP, must now distinguish itself also from possible fractional vertexes that arise due to the relaxation. The relaxations can therefore be understood as optimizing over an inner bound of Θ. This set may be empty even if the training data is separable with exact inference [6]. Another obstacle to using LP relaxations for learning is that solving the LPs can be very slow. In this paper we ask whether it is possible to learn while avoiding inference altogether. We propose a new learning algorithm, inspired by pseudo-likelihood [1], that optimizes over an outer bound of Θ. Learning involves optimizing over only a small number of constraints per data point, and thus can be performed quickly, even for complex structured prediction models. We show that, if the data available for learning is “nice”, this algorithm is consistent, i.e. it will ﬁnd some θ ∈ Θ. This is an example of how having the right data can circumvent the hardness of learning for structured prediction. 1 We also investigate the limitations of the proposed method. We show that the problem of even deciding whether a given data set is separable is NP-hard, and thus learning in a strict sense is no easier than prediction. Thus, we should not expect for our algorithm, or any other polynomial time algorithm, to always succeed at learning from an arbitrary ﬁnite data set. To our knowledge, this is the ﬁrst result characterizing the hardness of exact learning for structured prediction. Finally, we show empirically that our algorithm allows us to successfully learn the parameters for both multi-label prediction and protein side-chain placement. The performance of the algorithm is improved as more data becomes available, as our theoretical results anticipate. 1 Pseudo-Max method We consider the general structured prediction problem. The input space is denoted by X and the set of all possible assignments by Y. Each y ∈ Y corresponds to n variables y1 , . . . , yn , each with k possible states. The classiﬁer uses a (given) function φ(x, y) : X , Y → Rd and (learned) weights θ ∈ Rd , and is deﬁned as y(x; θ) = arg maxy∈Y f (ˆ ; x, θ) where f is the discriminant function y ˆ f (y; x, θ) = θ · φ(x, y). Our analysis will focus on functions φ whose scope is limited to small sets of the yi variables, but for now we keep the discussion general. Given a set of labeled examples {(xm , y m )}M , the goal of the typical learning problem is to ﬁnd m=1 weights θ that correctly classify the training examples. Consider ﬁrst the separable case. Deﬁne the set of separating weight vectors, Θ = θ | ∀m, y ∈ Y, f (y m ; xm , θ) ≥ f (y; xm , θ)+e(y, y m ) . e is a loss function (e.g., zero-one or Hamming) such that e(y m , y m ) = 0 and e(y, y m ) > 0 for y = y m , which serves to rule out the trivial solution θ = 0.1 The space Θ is deﬁned by exponentially many constraints per example, one for each competing assignment. In this work we consider a much simpler set of constraints where, for each example, we only consider the competing assignments obtained by modifying a single label yi , while ﬁxing the other labels to their value at y m . The pseudo-max set, which is an outer bound on Θ, is given by Here ym −i m Θps = θ | ∀m, i, yi , f (y m ; xm , θ) ≥ f (y m , yi ; xm , θ) + e(yi , yi ) . −i denotes the label y m (1) without the assignment to yi . When the data is not separable, Θ will be the empty set. Instead, we may choose to minimize the hinge loss, (θ) = m maxy f (y; xm , θ) − f (y m ; xm , θ) + e(y, y m ) , which can be shown to be an upper bound on the training error [13]. When the data is separable, minθ (θ) = 0. Note that regularization may be added to this objective. The corresponding pseudo-max objective replaces the maximization over all of y with maximization over a single variable yi while ﬁxing the other labels to their value at y m :2,3 M ps (θ) n = m=1 i=1 m max f (y m , yi ; xm , θ) − f (y m ; xm , θ) + e(yi , yi ) . −i yi Analogous to before, we have minθ ps (θ) (2) = 0 if and only if θ ∈ Θps . The objective in Eq. 2 is similar in spirit to pseudo-likelihood objectives used for maximum likelihood estimation of parameters of Markov random ﬁelds (MRFs) [1]. The pseudo-likelihood estimate is provably consistent when the data generating distribution is a MRF of the same structure as used in the pseudo-likelihood objective. However, our setting is different since we only get to view the maximizing assignment of the MRF rather than samples from it. Thus, a particular x will always be paired with the same y rather than samples y drawn from the conditional distribution p(y|x; θ). The pseudo-max constraints in Eq. 1 are also related to cutting plane approaches to inference [4, 5]. In the latter, the learning problem is solved by repeatedly looking for assignments that violate the separability constraint (or its hinge version). Our constraints can be viewed as using a very small 1 An alternative formulation, which we use in the next section, is to break the symmetry by having part of the input not be multiplied by any weight. This will also rule out the trivial solution θ = 0. P 2 It is possible to use maxi instead of i , and some of our consistency results will still hold. 3 The pseudo-max approach is markedly different from a learning method which predicts each label yi independently, since the objective considers all i simultaneously (both at learning and test time). 2 x2 0.2 J ∗ + x1 = 0 y = (0, 1) y = (1, 1) g(J12) x2 = 0 x1 J ∗ + x1 + x2 = 0 y = (0, 0) c1=0 c1=1 c1= 1 0.15 0.1 J + x2 = 0 ∗ 0.05 y = (1, 0) x1 = 0 0 1 0.5 0 J 0.5 1 Figure 1: Illustrations for a model with two variables. Left: Partitioning of X induced by conﬁgurations y(x) for some J ∗ > 0. Blue lines carve out the exact regions. Red lines denote the pseudo-max constraints that hold with equality. Pseudo-max does not obtain the diagonal constraint coming from comparing conﬁgurations y = (1, 1) and (0, 0), since these differ by more than one coordinate. Right: One strictly-convex component of the ps (J ) function (see Eq. 9). The function is shown for different values of c1 , the mean of the x1 variable. subset of assignments for the set of candidate constraint violators. We also note that when exact maximization over the discriminant function f (y; x, θ) is hard, the standard cutting plane algorithm cannot be employed since it is infeasible to ﬁnd a violated constraint. For the pseudo-max objective, ﬁnding a constraint violation is simple and linear in the number of variables.4 It is easy to see (as will be elaborated on next) that the pseudo-max method does not in general yield a consistent estimate of θ, even in the separable case. However, as we show, consistency can be shown to be achieved under particular assumptions on the data generating distribution p(x). 2 Consistency of the Pseudo-Max method In this section we show that if the feature generating distribution p(x) satisﬁes particular assumptions, then the pseudo-max approach yields a consistent estimate. In other words, if the training data is of the form {(xm , y(xm ; θ ∗ ))}M for some true parameter vector θ ∗ , then as M → ∞ the m=1 minimum of the pseudo-max objective will converge to θ ∗ (up to equivalence transformations). The section is organized as follows. First, we provide intuition for the consistency results by considering a model with only two variables. Then, in Sec. 2.1, we show that any parameter θ ∗ can be identiﬁed to within arbitrary accuracy by choosing a particular training set (i.e., choice of xm ). This in itself proves consistency, as long as there is a non-zero probability of sampling this set. In Sec. 2.2 we give a more direct proof of consistency by using strict convexity arguments. For ease of presentation, we shall work with a simpliﬁed instance of the structured learning setting. We focus on binary variables, yi ∈ {0, 1}, and consider discriminant functions corresponding to Ising models, a special case of pairwise MRFs (J denotes the vector of “interaction” parameters): f (y; x, J ) = ij∈E Jij yi yj + i yi xi (3) The singleton potential for variable yi is yi xi and is not dependent on the model parameters. We could have instead used Ji yi xi , which would be more standard. However, this would make the parameter vector J invariant to scaling, complicating the identiﬁability analysis. In the consistency analysis we will assume that the data is generated using a true parameter vector J ∗ . We will show that as the data size goes to inﬁnity, minimization of ps (J ) yields J ∗ . We begin with an illustrative analysis of the pseudo-max constraints for a model with only two variables, i.e. f (y; x, J) = Jy1 y2 + y1 x1 + y2 x2 . The purpose of the analysis is to demonstrate general principles for when pseudo-max constraints may succeed or fail. Assume that training samples are generated via y(x) = argmaxy f (y; x, J ∗ ). We can partition the input space X into four regions, ˆ ˆ {x ∈ X : y(x) = y } for each of the four conﬁgurations y , shown in Fig. 1 (left). The blue lines outline the exact decision boundaries of f (y; x, J ∗ ), with the lines being given by the constraints 4 The methods differ substantially in the non-separable setting where we minimize ps (θ), using a slack variable for every node and example, rather than just one slack variable per example as in (θ). 3 in Θ that hold with equality. The red lines denote the pseudo-max constraints in Θps that hold with equality. For x such that y(x) = (1, 0) or (0, 1), the pseudo-max and exact constraints are identical. We can identify J ∗ by obtaining samples x = (x1 , x2 ) that explore both sides of one of the decision boundaries that depends on J ∗ . The pseudo-max constraints will fail to identify J ∗ if the samples do not sufﬁciently explore the transitions between y = (0, 1) and y = (1, 1) or between y = (1, 0) and y = (1, 1). This can happen, for example, when the input samples are dependent, giving only rise to the conﬁgurations y = (0, 0) and y = (1, 1). For points labeled (1, 1) around the decision line J ∗ + x1 + x2 = 0, pseudo-max can only tell that they respect J ∗ + x1 ≥ 0 and J ∗ + x2 ≥ 0 (dashed red lines), or x1 ≤ 0 and x2 ≤ 0 for points labeled (0, 0). Only constraints that depend on the parameter are effective for learning. For pseudo-max to be able to identify J ∗ , the input samples must be continuous, densely populating the two parameter dependent decision lines that pseudo-max can use. The two point sets in the ﬁgure illustrate good and bad input distributions for pseudo-max. The diagonal set would work well with the exact constraints but badly with pseudo-max, and the difference can be arbitrarily large. However, the input distribution on the right, populating the J ∗ + x2 = 0 decision line, would permit pseudo-max to identify J ∗ . 2.1 Identiﬁability of True Parameters In this section, we show that it is possible to approximately identify the true model parameters, up to model equivalence, using the pseudo-max constraints and a carefully chosen linear number of data points. Consider the learning problem for structured prediction deﬁned on a ﬁxed graph G = (V, E) where the parameters to be learned are pairwise potential functions θij (yi , yj ) for ij ∈ E and single node ﬁelds θi (yi ) for i ∈ V . We consider discriminant functions of the form f (y; x, θ) = ij∈E θij (yi , yj ) + i θi (yi ) + i xi (yi ), (4) where the input space X = R|V |k speciﬁes the single node potentials. Without loss of generality, we remove the additional degrees of freedom in θ by restricting it to be in a canonical form: θ ∈ Θcan if for all edges θij (yi , yj ) = 0 whenever yi = 0 or yj = 0, and if for all nodes, θi (yi ) = 0 when yi = 0. As a result, assuming the training set comes from a model in this class, and the input ﬁelds xi (yi ) exercise the discriminant function appropriately, we can hope to identify θ ∗ ∈ Θcan . Indeed, we show that, for some data sets, the pseudo-max constraints are sufﬁcient to identify θ ∗ . Let Θps ({y m , xm }) be the set of parameters that satisfy the pseudo-max classiﬁcation constraints m Θps ({y m , xm }) = θ | ∀m, i, yi = yi , f (y m ; xm , θ) ≥ f (y m , yi ; xm , θ) . −i (5) m e(yi , yi ), For simplicity we omit the margin losses since the input ﬁelds xi (yi ) already sufﬁce to rule out the trivial solution θ = 0. Proposition 2.1. For any θ ∗ ∈ Θcan , there is a set of 2|V |(k − 1) + 2|E|(k − 1)2 examples, {xm , y(xm ; θ ∗ )}, such that any pseudo-max consistent θ ∈ Θps ({y m , xm }) ∩ Θcan is arbitrarily close to θ ∗ . The proof is given in the supplementary material. To illustrate the key ideas, we consider the simpler binary discriminant function discussed in Eq. 3. Note that the binary model is already in the canonical form since Jij yi yj = 0 whenever yi = 0 or yj = 0. For any ij ∈ E, we show how to choose two input examples x1 and x2 such that any J consistent with the pseudo-max constraints for these ∗ ∗ two examples will have Jij ∈ [Jij − , Jij + ]. Repeating this for all of the edge parameters then gives the complete set of examples. The input examples we need for this will depend on J ∗ . For the ﬁrst example, we set the input ﬁelds for all neighbors of i (except j) in such a way that ∗ we force the corresponding labels to be zero. More formally, we set x1 < −|N (k)| maxl |Jkl | for k 1 k ∈ N (i)\j, resulting in yk = 0, where y 1 = y(x1 ). In contrast, we set x1 to a large value, e.g. j ∗ 1 ∗ x1 > |N (j)| maxl |Jjl |, so that yj = 1. Finally, for node i, we set x1 = −Jij + so as to obtain a j i 1 slight preference for yi = 1. All other input ﬁelds can be set arbitrarily. As a result, the pseudo-max constraints pertaining to node i are f (y 1 ; x1 , J ) ≥ f (y 1 , yi ; x1 , J ) for yi = 0, 1. By taking into −i 1 account the label assignments for yi and its neighbors, and by removing terms that are the same on both sides of the equation, we get Jij + x1 + x1 ≥ Jij yi + yi x1 + x1 , which, for yi = 0, implies i j i j ∗ that Jij + x1 ≥ 0 or Jij − Jij + ≥ 0. The second example x2 differs only in terms of the input i ∗ 2 ∗ ﬁeld for i. In particular, we set x2 = −Jij − so that yi = 0. This gives Jij ≤ Jij + , as desired. i 4 2.2 Consistency via Strict Convexity In this section we prove the consistency of the pseudo-max approach by showing that it corresponds to minimizing a strictly convex function. Our proof only requires that p(x) be non-zero for all x ∈ Rn (a simple example being a multi-variate Gaussian) and that J ∗ is ﬁnite. We use a discriminant function as in Eq. 3. Now, assume the input points xm are distributed according to p(x) and that y m are obtained via y m = arg maxy f (y; xm , J ∗ ). We can write the ps (J ) objective for ﬁnite data, and its limit when M → ∞, compactly as: 1 m m = max (yi − yi ) xm + Jki yk ps (J ) i M m i yi k∈N (i) p(x) max (yi − yi (x)) xi + → yi i Jki yk (x) dx (6) k∈N (i) ∗ where yi (x) is the label of i for input x when using parameters J . Starting from the above, consider the terms separately for each i. We partition the integral over x ∈ Rn into exclusive regions according to the predicted labels of the neighbors of i (given x). Deﬁne Sij = {x : yj (x) = 1 and yk (x) = 0 for k ∈ N (i)\j}. Eq. 6 can then be written as ps (J ) = gi ({Jik }k∈N (i) ) + ˆ i gik (Jik ) , (7) k∈N (i) where gik (Jik ) = x∈Sik p(x) maxyi [(yi −yi (x))(xi +Jik )]dx and gi ({Jik }k∈N (i) ) contains all of ˆ the remaining terms, i.e. where either zero or more than one neighbor is set to one. The function gi ˆ is convex in J since it is a sum of integrals over convex functions. We proceed to show that gik (Jik ) is strictly convex for all choices of i and k ∈ N (i). This will show that ps (J ) is strictly convex since it is a sum over functions strictly convex in each one of the variables in J . For all values xi ∈ (−∞, ∞) there is some x in Sij . This is because for any ﬁnite xi and ﬁnite J ∗ , the other xj ’s can be chosen so as to give the y conﬁguration corresponding to Sij . Now, since p(x) has full support, we have P (Sij ) > 0 and p(x) > 0 for any x in Sij . As a result, this also holds for the marginal pi (xi |Sij ) over xi within Sij . After some algebra, we obtain: gij (Jij ) = P (Sij ) ∞ p(x)yi (x)(xi + Jij )dx pi (xi |Sij ) max [0, xi + Jij ] dxi − −∞ x∈Sij The integral over the yi (x)(xi + Jij ) expression just adds a linear term to gij (Jij ). The relevant remaining term is (for brevity we drop P (Sij ), a strictly positive constant, and the ij index): h(J) = ∞ pi (xi |Sij ) max [0, xi + J] dxi = −∞ ∞ ˆ pi (xi |Sij )h(xi , J)dxi (8) −∞ ˆ ˆ where we deﬁne h(xi , J) = max [0, xi + J]. Note that h(J) is convex since h(xi , J) is convex in J for all xi . We want to show that h(J) is strictly convex. Consider J < J and α ∈ (0, 1) and deﬁne ˆ ˆ the interval I = [−J, −αJ − (1 − α)J ]. For xi ∈ I it holds that: αh(xi , J) + (1 − α)h(xi , J ) > ˆ i , αJ + (1 − α)J ) (since the ﬁrst term is strictly positive and the rest are zero). For all other x, h(x ˆ this inequality holds but is not necessarily strict (since h is always convex in J). We thus have after integrating over x that αh(J) + (1 − α)h(J ) > h(αJ + (1 − α)J ), implying h is strictly convex, as required. Note that we used the fact that p(x) has full support when integrating over I. The function ps (J ) is thus a sum of strictly convex functions in all its variables (namely g(Jik )) plus other convex functions of J , hence strictly convex. We can now proceed to show consistency. By strict convexity, the pseudo-max objective is minimized at a unique point J . Since we know that ps (J ∗ ) = 0 and zero is a lower bound on the value of ps (J ), it follows that J ∗ is the unique minimizer. Thus we have that as M → ∞, the minimizer of the pseudo-max objective is the true parameter vector, and thus we have consistency. As an example, consider the case of two variables y1 , y2 , with x1 and x2 distributed according to ∗ N (c1 , 1), N (0, 1) respectively. Furthermore assume J12 = 0. Then simple direct calculation yields: 2 2 2 c1 + J12 −c1 1 1 √ (9) e−x /2 dx − √ e−c1 /2 + √ e−(J12 +c1 ) /2 2π 2π 2π −J12 −c1 which is indeed a strictly convex function that is minimized at J = 0 (see Fig. 1 for an illustration). g(J12 ) = 5 3 Hardness of Structured Learning Most structured prediction learning algorithms use some form of inference as a subroutine. However, the corresponding prediction task is generally NP-hard. For example, maximizing the discriminant function deﬁned in Eq. 3 is equivalent to solving Max-Cut, which is known to be NP-hard. This raises the question of whether it is possible to bypass prediction during learning. Although prediction may be intractable for arbitrary MRFs, what does this say about the difﬁculty of learning with a polynomial number of data points? In this section, we show that the problem of deciding whether there exists a parameter vector that separates the training data is NP-hard. Put in the context of the positive results in this paper, these hardness results show that, although in some cases the pseudo-max constraints yield a consistent estimate, we cannot hope for a certiﬁcate of optimality. Put differently, although the pseudo-max constraints in the separable case always give an outer bound on Θ (and may even be a single point), Θ could be the empty set – and we would never know the difference. Theorem 3.1. Given labeled examples {(xm , y m )}M for a ﬁxed but arbitrary graph G, it is m=1 NP-hard to decide whether there exists parameters θ such that ∀m, y m = arg maxy f (y; xm , θ). Proof. Any parameters θ have an equivalent parameterization in canonical form (see section Sec. 2.1, also supplementary). Thus, the examples will be separable if and only if they are separable by some θ ∈ Θcan . We reduce from unweighted Max-Cut. The Max-Cut problem is to decide, given an undirected graph G, whether there exists a cut of at least K edges. Let G be the same graph as G, with k = 3 states per variable. We construct a small set of examples where a parameter vector will exist that separates the data if and only if there is no cut of K or more edges in G. Let θ be parameters in canonical form equivalent to θij (yi , yj ) = 1 if (yi , yj ) ∈ {(1, 2), (2, 1)}, 0 if yi = yj , and −n2 if (yi , yj ) ∈ {(1, 3), (2, 3), (3, 1), (3, 2)}. We ﬁrst construct 4n + 8|E| examples, using the technique described in Sec. 2.1 (also supplementary material), which when restricted to the space Θcan , constrain the parameters to equal θ. We then use one more example (xm , y m ) where y m = 3 (every node is in state 3) and, for all i, xm (3) = K−1 and xm (1) = xm (2) = 0. The ﬁrst i i i n two states encode the original Max-Cut instance, while the third state is used to construct a labeling y m that has value equal to K − 1, and is otherwise not used. Let K ∗ be the value of the maximum cut in G. If in any assignment to the last example there is a variable taking the state 3 and another variable taking the state 1 or 2, then the assignment’s value will be at most K ∗ − n2 , which is less than zero. By construction, the 3 assignment has value K − 1. Thus, the optimal assignment must either be 3 with value K − 1, or some combination of states 1 and 2, which has value at most K ∗ . If K ∗ > K − 1 then 3 is not optimal and the examples are not separable. If K ∗ ≤ K − 1, the examples are separable. This result illustrates the potential difﬁculty of learning in worst-case graphs. Nonetheless, many problems have a more restricted dependence on the input. For example, in computer vision, edge potentials may depend only on the difference in color between two adjacent pixels. Our results do not preclude positive results of learnability in such restricted settings. By establishing hardness of learning, we also close the open problem of relating hardness of inference and learning in structured prediction. If inference problems can be solved in polynomial time, then so can learning (using, e.g., structured perceptron). Thus, when learning is hard, inference must be hard as well. 4 Experiments To evaluate our learning algorithm, we test its performance on both synthetic and real-world datasets. We show that, as the number of training samples grows, the accuracy of the pseudo-max method improves and its speed-up gain over competing algorithms increases. Our learning algorithm corresponds to solving the following, where we add L2 regularization and use a scaled 0-1 loss, m m e(yi , yi ) = 1{yi = yi }/nm (nm is the number of labels in example m): min θ C m nm M nm m=1 i=1 m max f (y m , yi ; xm , θ) − f (y m ; xm , θ) + e(yi , yi ) + θ −i yi 2 . (10) We will compare the pseudo-max method with learning using structural SVMs, both with exact inference and LP relaxations [see, e.g., 4]. We use exact inference for prediction at test time. 6 (a) Synthetic (b) Reuters 0.4 exact LP−relaxation pseudo−max 0.15 Test error Test error 0.2 0.1 0.05 0 1 10 2 10 0.2 0.1 0 1 10 3 10 Train size exact LP−relaxation pseudo−max 0.3 2 10 3 10 4 10 Train size Figure 2: Test error as a function of train size for various algorithms. Subﬁgure (a) shows results for a synthetic setting, while (b) shows performance on the Reuters data. In the synthetic setting we use the discriminant function f (y; x, θ) = ij∈E θij (yi , yj ) + xi θi (yi ), which is similar to Eq. 4. We take a fully connected graph over n = 10 binary labels. i For a weight vector θ ∗ (sampled once, uniformly in the range [−1, 1], and used for all train/test sets) we generate train and test instances by sampling xm uniformly in the range [−5, 5] and then computing the optimal labels y m = arg maxy∈Y f (y; xm , θ ∗ ). We generate train sets of increasing size (M = {10, 50, 100, 500, 1000, 5000}), run the learning algorithms, and measure the test error for the learned weights (with 1000 test samples). For each train size we average the test error over 10 repeats of sampling and training. Fig. 2(a) shows a comparison of the test error for the three learning algorithms. For small numbers of training examples, the test error of pseudo-max is larger than that of the other algorithms. However, as the train size grows, the error converges to that of exact learning, as our consistency results predict. We also test the performance of our algorithm on a multi-label document classiﬁcation task from the Reuters dataset [7]. The data consists of M = 23149 training samples, and we use a reduction of the dataset to the 5 most frequent labels. The 5 label variables form a fully connected pairwise graph structure (see [4] for a similar setting). We use random subsamples of increasing size from the train set to learn the parameters, and then measure the test error using 20000 additional samples. For each sample size and learning algorithm, we optimize the trade-off parameter C using 30% of the training data as a hold-out set. Fig. 2(b) shows that for the large data regime the performance of pseudo-max learning gets close to that of the other methods. However, unlike the synthetic setting there is still a small gap, even after seeing the entire train set. This could be because the full dataset is not yet large enough to be in the consistent regime (note that exact learning has not ﬂattened either), or because the consistency conditions are not fully satisﬁed: the data might be non-separable or the support of the input distribution p(x) may be partial. We next apply our method to the problem of learning the energy function for protein side-chain placement, mirroring the learning setup of [14], where the authors train a conditional random ﬁeld (CRF) using tree-reweighted belief propagation to maximize a lower bound on the likelihood.5 The prediction problem for side-chain placement corresponds to ﬁnding the most likely assignment in a pairwise MRF, and ﬁts naturally into our learning framework. There are only 8 parameters to be learned, corresponding to a reweighting of known energy terms. The dataset consists of 275 proteins, where each MRF has several hundred variables (one per residue of the protein) and each variable has on average 20 states. For prediction we use CPLEX’s ILP solver. Fig. 3 shows a comparison of the pseudo-max method and a cutting-plane algorithm which uses an LP relaxation, solved with CPLEX, for ﬁnding violated constraints.6 We generate training sets of increasing size (M = {10, 50, 100, 274}), and measure the test error for the learned weights on the remaining examples.7 For M = 10, 50, 100 we average the test error over 3 random train/test splits, whereas for M = 274 we do 1-fold cross validation. We use C = 1 for both algorithms. 5 The authors’ data and results are available from: http://cyanover.fhcrc.org/recomb-2007/ We signiﬁcantly optimized the cutting-plane algorithm, e.g. including a large number of initial cuttingplanes and restricting the weight vector to be positive (which we know to hold at optimality). 7 Speciﬁcally, for each protein we compute the fraction of correctly predicted χ1 and χ2 angles for all residues (except when trivial, e.g. just 1 state). Then, we compute the median of this value across all proteins. 6 7 Time to train (minutes) Test error (χ1 and χ2) 0.27 0.265 pseudo−max LP−relaxation Soft rep 0.26 0.255 0.25 0 50 100 150 200 Train size 250 250 200 pseudo−max LP−relaxation 150 100 50 0 0 50 100 150 200 Train size 250 Figure 3: Training time (for one train/test split) and test error as a function of train size for both the pseudomax method and a cutting-plane algorithm which uses a LP relaxation for inference, applied to the problem of learning the energy function for protein side-chain placement. The pseudo-max method obtains better accuracy than both the LP relaxation and HCRF (given roughly ﬁve times more data) for a fraction of the training time. The original weights (“Soft rep” [3]) used for this energy function have 26.7% error across all 275 proteins. The best previously reported parameters, learned in [14] using a Hidden CRF, obtain 25.6% error (their training set included 55 of these 275 proteins, so this is an optimistic estimate). To get a sense of the difﬁculty of this learning task, we also tried a random positive weight vector, uniformly sampled from the range [0, 1], obtaining an error of 34.9% (results would be much worse if we allowed the weights to be negative). Training using pseudo-max with 50 examples, we learn parameters in under a minute that give better accuracy than the HCRF. The speed-up of training with pseudo-max (using CPLEX’s QP solver) versus cutting-plane is striking. For example, for M = 10, pseudo-max takes only 3 seconds, a 1000-fold speedup. Unfortunately the cutting-plane algorithm took a prohibitive amount of time to be able to run on the larger training sets. Since the data used in learning for protein side-chain placement is both highly non-separable and relatively little, these positive results illustrate the potential wide-spread applicability of the pseudo-max method. 5 Discussion The key idea of our method is to ﬁnd parameters that prefer the true assignment y m over assignments that differ from it in only one variable, in contrast to all other assignments. Perhaps surprisingly, this weak requirement is sufﬁcient to achieve consistency given a rich enough input distribution. One extension of our approach is to add constraints for assignments that differ from y m in more than one variable. This would tighten the outer bound on Θ and possibly result in improved performance, but would also increase computational complexity. We could also add such competing assignments via a cutting-plane scheme so that optimization is performed only over a subset of these constraints. Our work raises a number of important open problems: It would be interesting to derive generalization bounds to understand the convergence rate of our method, as well as understanding the effect of the distribution p(x) on these rates. The distribution p(x) needs to have two key properties. On the one hand, it needs to explore the space Y in the sense that a sufﬁcient number of labels need to be obtained as the correct label for the true parameters (this is indeed used in our consistency proofs). On the other hand, p(x) needs to be sufﬁciently sensitive close to the decision boundaries so that the true parameters can be inferred. We expect that generalization analysis will depend on these two properties of p(x). Note that [11] studied active learning schemes for structured data and may be relevant in the current context. How should one apply this learning algorithm to non-separable data sets? We suggested one approach, based on using a hinge loss for each of the pseudo constraints. One question in this context is, how resilient is this learning algorithm to label noise? Recent work has analyzed the sensitivity of pseudo-likelihood methods to model mis-speciﬁcation [8], and it would be interesting to perform a similar analysis here. Also, is it possible to give any guarantees for the empirical and expected risks (with respect to exact inference) obtained by outer bound learning versus exact learning? Finally, our algorithm demonstrates a phenomenon where more data can make computation easier. Such a scenario was recently analyzed in the context of supervised learning [12], and it would be interesting to combine the approaches. Acknowledgments: We thank Chen Yanover for his assistance with the protein data. This work was supported by BSF grant 2008303 and a Google Research Grant. D.S. was supported by a Google PhD Fellowship. 8 References [1] J. Besag. The analysis of non-lattice data. The Statistician, 24:179–195, 1975. [2] M. Collins. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In EMNLP, 2002. [3] G. Dantas, C. Corrent, S. L. Reichow, J. J. Havranek, Z. M. Eletr, N. G. Isern, B. Kuhlman, G. Varani, E. A. Merritt, and D. Baker. High-resolution structural and thermodynamic analysis of extreme stabilization of human procarboxypeptidase by computational protein design. Journal of Molecular Biology, 366(4):1209 – 1221, 2007. [4] T. Finley and T. Joachims. Training structural SVMs when exact inference is intractable. In Proceedings of the 25th International Conference on Machine Learning 25, pages 304–311. ACM, 2008. [5] T. Joachims, T. Finley, and C.-N. Yu. Cutting-plane training of structural SVMs. Machine Learning, 77(1):27–59, 2009. [6] A. Kulesza and F. Pereira. Structured learning with approximate inference. In Advances in Neural Information Processing Systems 20, pages 785–792. 2008. [7] D. Lewis, , Y. Yang, T. Rose, and F. Li. RCV1: a new benchmark collection for text categorization research. JMLR, 5:361–397, 2004. [8] P. Liang and M. I. Jordan. An asymptotic analysis of generative, discriminative, and pseudolikelihood estimators. In Proceedings of the 25th international conference on Machine learning, pages 584–591, New York, NY, USA, 2008. ACM Press. [9] A. F. T. Martins, N. A. Smith, and E. P. Xing. Polyhedral outer approximations with application to natural language parsing. In ICML 26, pages 713–720, 2009. [10] N. Ratliff, J. A. D. Bagnell, and M. Zinkevich. (Online) subgradient methods for structured prediction. In AISTATS, 2007. [11] D. Roth and K. Small. Margin-based active learning for structured output spaces. In Proc. of the European Conference on Machine Learning (ECML). Springer, September 2006. [12] S. Shalev-Shwartz and N. Srebro. SVM optimization: inverse dependence on training set size. In Proceedings of the 25th international conference on Machine learning, pages 928–935. ACM, 2008. [13] B. Taskar, C. Guestrin, and D. Koller. Max margin Markov networks. In Advances in Neural Information Processing Systems 16, pages 25–32. 2004. [14] C. Yanover, O. Schueler-Furman, and Y. Weiss. Minimizing and learning energy functions for side-chain prediction. Journal of Computational Biology, 15(7):899–911, 2008. 9

5 0.084517717 31 nips-2010-An analysis on negative curvature induced by singularity in multi-layer neural-network learning

Author: Eiji Mizutani, Stuart Dreyfus

Abstract: In the neural-network parameter space, an attractive ﬁeld is likely to be induced by singularities. In such a singularity region, ﬁrst-order gradient learning typically causes a long plateau with very little change in the objective function value E (hence, a ﬂat region). Therefore, it may be confused with “attractive” local minima. Our analysis shows that the Hessian matrix of E tends to be indeﬁnite in the vicinity of (perturbed) singular points, suggesting a promising strategy that exploits negative curvature so as to escape from the singularity plateaus. For numerical evidence, we limit the scope to small examples (some of which are found in journal papers) that allow us to conﬁrm singularities and the eigenvalues of the Hessian matrix, and for which computation using a descent direction of negative curvature encounters no plateau. Even for those small problems, no efﬁcient methods have been previously developed that avoided plateaus. 1

6 0.083942905 254 nips-2010-Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models

7 0.083043411 63 nips-2010-Distributed Dual Averaging In Networks

8 0.078715988 181 nips-2010-Network Flow Algorithms for Structured Sparsity

9 0.07708849 176 nips-2010-Multiple Kernel Learning and the SMO Algorithm

10 0.076855741 102 nips-2010-Generalized roof duality and bisubmodular functions

11 0.075105555 162 nips-2010-Link Discovery using Graph Feature Tracking

12 0.073055848 58 nips-2010-Decomposing Isotonic Regression for Efficiently Solving Large Problems

13 0.071934976 78 nips-2010-Error Propagation for Approximate Policy and Value Iteration

14 0.071801156 49 nips-2010-Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning

15 0.069901668 2 nips-2010-A Bayesian Approach to Concept Drift

16 0.069708236 174 nips-2010-Multi-label Multiple Kernel Learning by Stochastic Approximation: Application to Visual Object Recognition

17 0.067233816 13 nips-2010-A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Structured Prediction

18 0.066890806 150 nips-2010-Learning concept graphs from text with stick-breaking priors

19 0.066755399 283 nips-2010-Variational Inference over Combinatorial Spaces

20 0.066668198 80 nips-2010-Estimation of Renyi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.17), (1, 0.044), (2, 0.068), (3, 0.053), (4, -0.07), (5, -0.078), (6, 0.019), (7, 0.021), (8, 0.236), (9, 0.036), (10, -0.213), (11, -0.074), (12, 0.11), (13, 0.076), (14, -0.084), (15, -0.071), (16, -0.124), (17, -0.135), (18, 0.022), (19, -0.003), (20, 0.124), (21, -0.015), (22, -0.105), (23, 0.207), (24, 0.068), (25, -0.161), (26, -0.139), (27, 0.1), (28, -0.108), (29, 0.049), (30, -0.088), (31, 0.028), (32, -0.02), (33, 0.098), (34, 0.187), (35, -0.088), (36, 0.068), (37, 0.081), (38, -0.026), (39, -0.05), (40, 0.043), (41, -0.085), (42, -0.064), (43, 0.025), (44, 0.018), (45, -0.046), (46, 0.026), (47, -0.065), (48, 0.058), (49, 0.038)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96191466 165 nips-2010-MAP estimation in Binary MRFs via Bipartite Multi-cuts

Author: Sashank J. Reddi, Sunita Sarawagi, Sundar Vishwanathan

2 0.87095654 164 nips-2010-MAP Estimation for Graphical Models by Likelihood Maximization

Author: Akshat Kumar, Shlomo Zilberstein

3 0.76389337 288 nips-2010-Worst-case bounds on the quality of max-product fixed-points

Author: Meritxell Vinyals, Jes\'us Cerquides, Alessandro Farinelli, Juan A. Rodríguez-aguilar

4 0.5111168 90 nips-2010-Fast Large-scale Mixture Modeling with Component-specific Data Partitions

Author: Bo Thiesson, Chong Wang

Abstract: Remarkably easy implementation and guaranteed convergence has made the EM algorithm one of the most used algorithms for mixture modeling. On the downside, the E-step is linear in both the sample size and the number of mixture components, making it impractical for large-scale data. Based on the variational EM framework, we propose a fast alternative that uses component-speciﬁc data partitions to obtain a sub-linear E-step in sample size, while the algorithm still maintains provable convergence. Our approach builds on previous work, but is signiﬁcantly faster and scales much better in the number of mixture components. We demonstrate this speedup by experiments on large-scale synthetic and real data. 1

5 0.48887432 169 nips-2010-More data means less inference: A pseudo-max approach to structured learning

Author: David Sontag, Ofer Meshi, Amir Globerson, Tommi S. Jaakkola

6 0.43705943 58 nips-2010-Decomposing Isotonic Regression for Efficiently Solving Large Problems

7 0.38899288 234 nips-2010-Segmentation as Maximum-Weight Independent Set

8 0.38327107 102 nips-2010-Generalized roof duality and bisubmodular functions

9 0.37674019 49 nips-2010-Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning

10 0.35765985 77 nips-2010-Epitome driven 3-D Diffusion Tensor image segmentation: on extracting specific structures

11 0.35653415 198 nips-2010-Optimal Web-Scale Tiering as a Flow Problem

12 0.34380099 84 nips-2010-Exact inference and learning for cumulative distribution functions on loopy graphs

13 0.33863124 254 nips-2010-Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models

14 0.33414599 105 nips-2010-Getting lost in space: Large sample analysis of the resistance distance

15 0.33140805 283 nips-2010-Variational Inference over Combinatorial Spaces

16 0.3233881 31 nips-2010-An analysis on negative curvature induced by singularity in multi-layer neural-network learning

17 0.30230632 150 nips-2010-Learning concept graphs from text with stick-breaking priors

18 0.30036595 126 nips-2010-Inference with Multivariate Heavy-Tails in Linear Models

19 0.29338303 215 nips-2010-Probabilistic Deterministic Infinite Automata

20 0.27661869 190 nips-2010-On the Convexity of Latent Social Network Inference

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.038), (17, 0.014), (27, 0.032), (30, 0.069), (45, 0.152), (50, 0.039), (52, 0.019), (60, 0.447), (77, 0.048), (78, 0.016), (90, 0.021)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.91017872 223 nips-2010-Rates of convergence for the cluster tree

Author: Kamalika Chaudhuri, Sanjoy Dasgupta

Abstract: For a density f on Rd , a high-density cluster is any connected component of {x : f (x) ≥ λ}, for some λ > 0. The set of all high-density clusters form a hierarchy called the cluster tree of f . We present a procedure for estimating the cluster tree given samples from f . We give ﬁnite-sample convergence rates for our algorithm, as well as lower bounds on the sample complexity of this estimation problem. 1

same-paper 2 0.87392056 165 nips-2010-MAP estimation in Binary MRFs via Bipartite Multi-cuts

Author: Sashank J. Reddi, Sunita Sarawagi, Sundar Vishwanathan

3 0.86197013 278 nips-2010-Universal Consistency of Multi-Class Support Vector Classification

Author: Tobias Glasmachers

Abstract: Steinwart was the ﬁrst to prove universal consistency of support vector machine classiﬁcation. His proof analyzed the ‘standard’ support vector machine classiﬁer, which is restricted to binary classiﬁcation problems. In contrast, recent analysis has resulted in the common belief that several extensions of SVM classiﬁcation to more than two classes are inconsistent. Countering this belief, we prove the universal consistency of the multi-class support vector machine by Crammer and Singer. Our proof extends Steinwart’s techniques to the multi-class case. 1

4 0.81388092 104 nips-2010-Generative Local Metric Learning for Nearest Neighbor Classification

Author: Yung-kyun Noh, Byoung-tak Zhang, Daniel D. Lee

Abstract: We consider the problem of learning a local metric to enhance the performance of nearest neighbor classiﬁcation. Conventional metric learning methods attempt to separate data distributions in a purely discriminative manner; here we show how to take advantage of information from parametric generative models. We focus on the bias in the information-theoretic error arising from ﬁnite sampling effects, and ﬁnd an appropriate local metric that maximally reduces the bias based upon knowledge from generative models. As a byproduct, the asymptotic theoretical analysis in this work relates metric learning with dimensionality reduction, which was not understood from previous discriminative approaches. Empirical experiments show that this learned local metric enhances the discriminative nearest neighbor performance on various datasets using simple class conditional generative models. 1

5 0.75760096 62 nips-2010-Discriminative Clustering by Regularized Information Maximization

Author: Andreas Krause, Pietro Perona, Ryan G. Gomes

Abstract: Is there a principled way to learn a probabilistic discriminative classiﬁer from an unlabeled data set? We present a framework that simultaneously clusters the data and trains a discriminative classiﬁer. We call it Regularized Information Maximization (RIM). RIM optimizes an intuitive information-theoretic objective function which balances class separation, class balance and classiﬁer complexity. The approach can ﬂexibly incorporate different likelihood functions, express prior assumptions about the relative size of different classes and incorporate partial labels for semi-supervised learning. In particular, we instantiate the framework to unsupervised, multi-class kernelized logistic regression. Our empirical evaluation indicates that RIM outperforms existing methods on several real data sets, and demonstrates that RIM is an effective model selection method. 1

6 0.6856693 229 nips-2010-Reward Design via Online Gradient Ascent

7 0.56670183 164 nips-2010-MAP Estimation for Graphical Models by Likelihood Maximization

8 0.55775762 80 nips-2010-Estimation of Renyi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs

9 0.54812503 193 nips-2010-Online Learning: Random Averages, Combinatorial Parameters, and Learnability

10 0.53892589 270 nips-2010-Tight Sample Complexity of Large-Margin Learning

11 0.53780252 75 nips-2010-Empirical Risk Minimization with Approximations of Probabilistic Grammars

12 0.53615963 102 nips-2010-Generalized roof duality and bisubmodular functions

13 0.53552008 31 nips-2010-An analysis on negative curvature induced by singularity in multi-layer neural-network learning

14 0.53531027 196 nips-2010-Online Markov Decision Processes under Bandit Feedback

15 0.53509539 4 nips-2010-A Computational Decision Theory for Interactive Assistants

16 0.53174126 222 nips-2010-Random Walk Approach to Regret Minimization

17 0.52940536 138 nips-2010-Large Margin Multi-Task Metric Learning

18 0.52745098 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

19 0.52637315 163 nips-2010-Lower Bounds on Rate of Convergence of Cutting Plane Methods

20 0.52608126 263 nips-2010-Switching state space model for simultaneously estimating state transitions and nonstationary firing rates