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

257 nips-2010-Structured Determinantal Point Processes

Source: pdf

Author: Alex Kulesza, Ben Taskar

Abstract: We present a novel probabilistic model for distributions over sets of structures— for example, sets of sequences, trees, or graphs. The critical characteristic of our model is a preference for diversity: sets containing dissimilar structures are more likely. Our model is a marriage of structured probabilistic models, like Markov random ﬁelds and context free grammars, with determinantal point processes, which arise in quantum physics as models of particles with repulsive interactions. We extend the determinantal point process model to handle an exponentially-sized set of particles (structures) via a natural factorization of the model into parts. We show how this factorization leads to tractable algorithms for exact inference, including computing marginals, computing conditional probabilities, and sampling. Our algorithms exploit a novel polynomially-sized dual representation of determinantal point processes, and use message passing over a special semiring to compute relevant quantities. We illustrate the advantages of the model on tracking and articulated pose estimation problems. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 The critical characteristic of our model is a preference for diversity: sets containing dissimilar structures are more likely. [sent-4, score-0.11]

2 Our model is a marriage of structured probabilistic models, like Markov random ﬁelds and context free grammars, with determinantal point processes, which arise in quantum physics as models of particles with repulsive interactions. [sent-5, score-0.525]

3 We extend the determinantal point process model to handle an exponentially-sized set of particles (structures) via a natural factorization of the model into parts. [sent-6, score-0.508]

4 We show how this factorization leads to tractable algorithms for exact inference, including computing marginals, computing conditional probabilities, and sampling. [sent-7, score-0.112]

5 Our algorithms exploit a novel polynomially-sized dual representation of determinantal point processes, and use message passing over a special semiring to compute relevant quantities. [sent-8, score-0.767]

6 We illustrate the advantages of the model on tracking and articulated pose estimation problems. [sent-9, score-0.18]

7 1 Introduction The need for distributions over sets of structures arises frequently in computer vision, computational biology, and natural language processing. [sent-10, score-0.11]

8 For example, in multiple target tracking, sets of structures of interest are multiple object trajectories [6]. [sent-11, score-0.288]

9 In gene ﬁnding, sets of structures of interest are multiple proteins coded by a single gene via alternative splicing [13]. [sent-12, score-0.11]

10 In machine translation, sets of structures of interest are multiple interpretations or parses of a sentence in a different language [12]. [sent-13, score-0.11]

11 We would like a distribution over sets of trajectories that (1) includes sets of different cardinality and (2) prefers sets of trajectories that are spread out in space-time, as objects are likely to be [11, 15]. [sent-17, score-0.42]

12 Determinantal point processes [10] are attractive models for distributions over sets, because they concisely capture probabilistic mutual exclusion between items via a kernel matrix that determines which items are similar and therefore less likely to appear together. [sent-18, score-0.267]

13 Intuitively, the model balances the diversity of a set against the quality of the items it contains (for example, observation likelihood of an object along the trajectory, or motion smoothness). [sent-19, score-0.293]

14 Remarkably, algorithms for computing certain marginal and conditional probabilities as well as sampling from this model are O(N 3 ), where N is total number of possible items, even though there are 2N possible subsets of a set of size N [7, 1] . [sent-20, score-0.143]

15 The problem, however, is that in our setting the total number of possible trajectories N is exponential in the number of time steps. [sent-21, score-0.153]

16 Our structured determinatal point process model (SDPP) captures such distributions by combining structured probabilistic models (e. [sent-25, score-0.159]

17 (b) The ﬁrst three steps of sampling a DPP on a set of onedimensional particle positions, from left to right. [sent-28, score-0.118]

18 The paper is organized as follows: we present background on determinantal processes in Section 2 and introduce our model in Section 3; we develop inference and sampling algorithms in Section 4, and we describe experiments in Section 5. [sent-34, score-0.525]

19 2 Background: determinantal point processes A point process P on a discrete set Y = {y1 , . [sent-35, score-0.456]

20 P is called a determinantal point process (DPP) if there exists a positive semideﬁnite matrix K indexed by the elements of Y such that if Y ∼ P then for every A ⊆ Y, we have Determinantal Point Process: P(A ⊆ Y ) = det(KA ) . [sent-39, score-0.47]

21 A few simple observations follow from Equation (1): P(yi ∈ Y ) P(yi , yj ∈ Y ) = Kii (2) = Kii Kjj − Kij Kji = P(yi ∈ Y )P(yj ∈ Y ) − 2 Kij . [sent-42, score-0.174]

22 (3) That is, the diagonal of K gives the marginal probabilities of inclusion for individual elements of Y, and the off-diagonal elements determine the (anti-) correlations between pairs of elements: large values of Kij imply that i and j tend not to co-occur. [sent-43, score-0.14]

23 Figure 1a shows the difference between sampling a set of points in the plane using a DPP (with Kij inversely related to the distance between points i and j), which leads to a set that is spread out with good coverage, and sampling points independently, where the points exhibit random clumping. [sent-45, score-0.246]

24 To get probabilities of item co-occurrence as in Equation (1), we can compute the marginal kernel K for the L-ensemble PL : L-ensemble marginal kernel: K = (L + I)−1 L. [sent-52, score-0.149]

25 (5) N k=1 λk vk vk by a simple Note that K can be computed from the eigen-decomposition of L = N λk re-scaling of eigenvalues: K = k=1 λk +1 vk vk . [sent-53, score-0.888]

26 To get a better understanding of how L affects marginals K, note that L can be written as a Gram matrix with L(yi , yj ) = q(yi )φ(yi ) φ(yj )q(yj ) for q(yi ) ≥ 0 and some “feature mapping” φ(y) : Y → RD , where D ≤ N and ||φ(yi )||2 = 1. [sent-54, score-0.271]

27 We can think of q(yi ) as the “quality score” for item yi and φ(yi ) φ(yj ) as normalized “similarity” between items yi and yj . [sent-55, score-0.893]

28 q 2 (yi ) , PL (Y ) ∝ det(φ(Y ) φ(Y )) L-ensemble (L=quality*similarity): (6) yi ∈Y where φ(Y ) is a D × |Y | matrix with columns φ(yi ), yi ∈ Y . [sent-56, score-0.664]

29 Roughly speaking, PL (yi ∈ Y ) increases monotonically with quality q(yi ) and PL (yi , yj ∈ Y ) decreases monotonically with similarity φ(yi ) φ(yj ). [sent-58, score-0.388]

30 We brieﬂy mention a few other efﬁciently computable quantities of DPPs [1]: L-ensemble conditionals: PL (Y = A ∪ B | A ⊆ Y ) = det(LA∪B ) , det(L + IY\A ) (7) where IY\A is the matrix with ones in the diagonal entries indexed by elements of Y \ A and zeros everywhere else. [sent-59, score-0.113]

31 Let L = k=1 λk vk vk be an orthonormal eigendecomposition, and let ei be the ith standard basis N -vector (all zeros except for a 1 in the ith position). [sent-62, score-0.564]

32 λk +1 ; while |V | > 0 do 1 Select a yi from Y with Pr(yi ) = |V | v∈V (v ei )2 ; Update Y = Y ∪ yi ; Compute V⊥ , an orthonormal basis for the subspace of V orthogonal to ei , and let V = V⊥ ; end Return Y ; Algorithm 1: Sampling algorithm for L-ensemble DPPs. [sent-64, score-0.784]

33 To get a feel for the sampling algorithm, it is useful to visualize the distributions used to select yi at each time step, and to see how they are inﬂuenced by previously chosen items. [sent-69, score-0.401]

34 Figure 1b shows this progression for a simple DPP where Y is the set of points in [0, 1], quality scores are uniformly 1, and the feature mapping is such that φ(yi ) φ(yj ) ∝ exp(−(yi − yj )2 )—that is, points are more similar the closer together they are. [sent-70, score-0.48]

35 Initially, the eigenvectors V give rise to a fairly uniform distribution over points in Y, but as each successive point is selected and V is updated, the distribution shifts to avoid points near those already chosen. [sent-71, score-0.183]

36 3 Symbol Y, Y, yi , N L, LY K, KA q(yi ), φ(yi ) B, C α, yiα , yα Meaning Y is the base set, Y is a subset of Y, yi is an element of Y, N is the size of |Y| L is a p. [sent-72, score-0.664]

37 3 Structured determinantal point processes DPPs are amazingly tractable distributions when N , the size of the base set Y, is small. [sent-79, score-0.493]

38 For example, consider the case where each yi is itself a sequence of length T : yi = (yi1 , . [sent-81, score-0.664]

39 In order to deﬁne a DPP over structures such as sequences or trees, we assume a factorization of the quality score q(yi ) and similarity score φ(yi ) φ(yj ) into parts, similar to a graphical model decomposition. [sent-88, score-0.542]

40 For a sequence, the scores can be naturally decomposed into factors that depend on the state yit at each time t and the states (yit , yit+1 ) for each transition (t, t + 1). [sent-89, score-0.228]

41 More generally, we assume a set of factors and use the notation yiα to refer to the α part of the structure yi (similarly, we use yα to refer to the α part of the structure y). [sent-90, score-0.39]

42 We assume that quality decomposes multiplicatively and similarity decomposes additively, as follows. [sent-91, score-0.34]

43 (As before, L(yi , yj ) = q(yi )φ(yi ) φ(yj )q(yj ). [sent-92, score-0.174]

44 Similarity scores can be thought of as dot products between features of the two labelings. [sent-96, score-0.154]

45 In our tracking example, the feature mapping φ(yit ) should reﬂect similarity between trajectories; e. [sent-97, score-0.149]

46 , features could track coarse-level position at time t, so that the model considers sets with trajectories that pass near or through the same states less likely. [sent-99, score-0.32]

47 The eigenvalues of C and L are identical, and the eigenvectors are related as follows: if C = k λk vk vk , then L = k λk (B vk ) (B vk ). [sent-107, score-0.956]

48 That is, if vk is the k-th eigenvector of C, B vk is the k-th eigenvector of L, and it has the same eigenvalue λk . [sent-108, score-0.542]

49 To compute C itself, we need to compute BB = 2 yi q (yi )φ(yi )φ(yi ) . [sent-111, score-0.402]

50 Assuming we can compute C efﬁciently, 4 Sampled particle trajectories (position vs. [sent-114, score-0.237]

51 The curves to the left indicate the quality scores for the possible initial positions. [sent-116, score-0.252]

52 we can eigen-decompose it as C = k λk vk vk in O(D3 ). [sent-117, score-0.444]

53 A naive algorithm can simply compute all O(T 2 ) pairwise marginals p(yα , yα ) and, by linearity of expectation, add up the contributions: C = Z α,α yα ,yα p(yα , yα )φ(yα )φ(yα ) . [sent-122, score-0.132]

54 However, we can use a much more efﬁcient O(D2 T ) algorithm based on second-order semiring message passing [9]. [sent-123, score-0.266]

55 The details are given in Appendix A of the supplementary material, but in short we apply the standard two-pass belief propagation algorithm for trees with a particular semiring in place of the usual sum-product or max-sum. [sent-124, score-0.169]

56 By performing message passing under this second-order semiring, one can efﬁciently compute any quantity of the form: a(yα ) p(yα ) y∈Y α α b(yα ) (12) α for functions p ≥ 0, a, and b in time O(T ). [sent-125, score-0.17]

57 Sampling As described in Section 3, the eigen-decomposition of C yields an implicit representation of L: for each eigenvalue/vector pair (λk , vk ) of C, (λk , B vk ) is a corresponding pair for L. [sent-127, score-0.471]

58 Then we have ˆ with the mapping V = {B v|v ∈ V (B vi ) (B vj ) = vi BB vj = vi Cvj . [sent-131, score-0.138]

59 This is sufﬁcient to compute the normalization for each eigenvector B v, as required to obtain an initial orthonormal basis. [sent-133, score-0.134]

60 Trivially, we can also compute (implicit) sums between vectors in V ; this combined with dot products is enough to perform the Gram-Schmidt ˆ ˆ orthonormalization needed to obtain V⊥ from V and the most recently selected yi at each iteration. [sent-134, score-0.453]

61 All that remains, then, is to choose a structure yi according to the distribution Pr(yi ) = ˆ 1/|V | v∈V ((B v) ei )2 . [sent-135, score-0.367]

62 (13) ˆ| |V ˆ v∈V 2 By assumption q (yi ) decomposes multiplicatively over parts of yi , and v φ(yi ) decomposes adˆ ditively. [sent-138, score-0.508]

63 We can therefore apply message passing in the second-order semiring to compute marginals of this distribution—that is, for each part yα we can compute 1 q 2 (y)(v φ(y))2 , (14) ˆ |V | y∼yα ˆ v∈V ˆ where the sum is over all structures consistent with the value of yα . [sent-140, score-0.534]

64 In fact, the message-passing computation of these marginals yields an efﬁcient algorithm for sampling individual full structures yi as required by Algorithm 1; the key is to pass normal messages forward, but conditional messages backward. [sent-142, score-0.683]

65 Suppose we have a sequence model; since the forward pass completes with correct marginals at the ﬁnal node, we can correctly sample its value before any backwards messages are sent. [sent-143, score-0.204]

66 Once the value of the ﬁnal node is ﬁxed, we pass a conditional message backwards; that is, we send zeros for all values other than the one just selected. [sent-144, score-0.145]

67 Furthermore, by applying the second-order semiring we are able to sample from a distribution quite different from that of a traditional graphical model. [sent-147, score-0.16]

68 5 Experiments We begin with a synthetic motion tracking task, where the goal is to follow a collection of particles as they travel in a one-dimensional space over time. [sent-149, score-0.165]

69 This is the structured analog of the setting shown in Figure 1b, where elements of Y are no longer single positions in [0, 1], but are now sequences of such positions over many time periods. [sent-150, score-0.258]

70 For our experiments, we modeled paths yi over T = 50 time steps, where at each time t a particle can be in one of 50 discretized positions, yit ∈ {1, . [sent-151, score-0.515]

71 50 The total number of possible trajectories is thus 5050 , and there are 250 possible sets of trajectories. [sent-155, score-0.191]

72 While a real tracking problem would involve quality scores q(y) that depend on some observations, e. [sent-156, score-0.345]

73 , measurements over time from a set of physical sensors, for simplicity we determine the quality of a trajectory using only its starting position and a measure of smoothness over time: q(y) = T q(y1 ) t=2 q(yt−1 , yt ). [sent-158, score-0.349]

74 The initial quality scores q(y1 ) depicted on the left of Figure 2 are high in the middle with secondary modes on each side. [sent-159, score-0.252]

75 The transition quality is given by q(yt−1 , yt ) = f (yt−1 − yt ), where f is the density function of the zero-mean Gaussian with unit variance. [sent-160, score-0.328]

76 We scale the quality scores so that the expected number of selected trajectories is 5. [sent-161, score-0.431]

77 We want trajectories to be considered similar if they travel through similar positions, so we deﬁne T a 50-dimensional feature vector φ(y) = t=1 φ(yt ) where φr (yt ) ∝ f (i − yt ) for r = 1, . [sent-162, score-0.269]

78 Intuitively, feature r is activated when the trajectory passes near position r, so trajectories passing through nearby positions will activate the same features and thus appear similar. [sent-166, score-0.421]

79 Sets of trajectories drawn independently according to quality score tend to cluster in the middle region (second 6 row). [sent-168, score-0.395]

80 The SDPP samples, however, are more diverse, tending to cover more of the space while still respecting the quality scores—they are still smooth, and still tend to start near the middle position. [sent-169, score-0.197]

81 For our purposes, each pose is a structure containing four parts (head, torso, right arm, and left arm), each of which takes a value consisting of a pixel location and an orientation (one of 24 discretized angles). [sent-175, score-0.137]

82 We use a standard pictorial strucure model [4, 5], treating each pose as a two-level tree with the torso as the root and the head and arms as leaves. [sent-178, score-0.282]

83 Our quality scores are derived from [14]; they factorize across the nodes (body parts) P and edges (joints) J as q(y) = γ( p∈P q(yp ) pp ∈J q(yp , yp ))β . [sent-179, score-0.385]

84 γ is a scale parameter that controls the expected number of poses in each sample, and β is a sharpness parameter that we found helpful in controlling the impact of the quality scores. [sent-180, score-0.259]

85 ) Each part receives a quality score q(yp ) given by a customized part detector previously trained on similar images. [sent-182, score-0.272]

86 The joint quality score q(yp , yp ) is given by a Gaussian “spring” that encourages, for example, the left arm to begin near the left shoulder. [sent-183, score-0.433]

87 Full details of the quality terms are provided in [14]. [sent-184, score-0.158]

88 , x32 , and use φ(y) = p∈P φ(yp ), where φr (yp ) ∝ f ( yp − xr 2 /σ). [sent-189, score-0.176]

89 Recall that f is the standard normal density function, and yp − xr 2 is the distance between the position of part p (ignoring angle) and the reference point xr . [sent-190, score-0.299]

90 The ﬁrst is an independent model which draws poses independently according to the distribution obtained by normalizing the quality scores. [sent-194, score-0.287]

91 The second is a simple non-maxima suppression model that iteratively selects successive poses using the normalized quality scores, but under the hard constraint that they do not overlap with any previously selected pose. [sent-195, score-0.314]

92 Using the training set, we select values for γ, β, and σ that optimize overall F1 score at radius 100 (see below), as well as distinct optimal values of β for the baselines. [sent-199, score-0.115]

93 ) We then use each model to sample 10 sets of poses for each test image, or 600 samples per model. [sent-201, score-0.139]

94 For our purposes, precision is the fraction of predicted parts where both endpoints are within a particular radius of the endpoints of an expert-labeled part of the same type (head, left arm, etc. [sent-203, score-0.225]

95 Correspondingly, recall is the fraction of expert-labeled parts within a given radius of a predicted part of the same type. [sent-205, score-0.174]

96 At tight tolerances the SDPP performs comparably to the independent samples (perhaps because the quality scores are only accurate at the mode, so diverse samples are not close enough to be valuable). [sent-210, score-0.28]

97 Figure 3b shows the curves for the arms alone; the arms tend to be more difﬁcult to locate accurately. [sent-212, score-0.114]

98 2 60 80 100 120 Match radius (in pixels) 140 (b) 40 60 80 100 120 Match radius (in pixels) 140 (c) Figure 3: Results for pose estimation. [sent-236, score-0.205]

99 Figure 4: Structured marginals for the pose estimation task on successive steps of the sampling algorithm, with already selected poses superimposed. [sent-239, score-0.409]

100 6 Conclusion We introduced the structured determinantal point process (SDPP), a probabilistic model over sets of structures such as sequences, trees, or graphs. [sent-243, score-0.594]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('determinantal', 0.392), ('yi', 0.332), ('dpp', 0.305), ('sdpp', 0.305), ('vk', 0.222), ('pl', 0.193), ('yj', 0.174), ('quality', 0.158), ('trajectories', 0.153), ('yit', 0.134), ('yp', 0.133), ('semiring', 0.131), ('det', 0.128), ('dpps', 0.109), ('poses', 0.101), ('kij', 0.1), ('marginals', 0.097), ('ly', 0.096), ('scores', 0.094), ('tracking', 0.093), ('pose', 0.087), ('sdpps', 0.087), ('yt', 0.085), ('kii', 0.077), ('factorization', 0.075), ('structures', 0.072), ('message', 0.071), ('sampling', 0.069), ('structured', 0.067), ('pictorial', 0.066), ('passing', 0.064), ('processes', 0.064), ('ka', 0.062), ('bb', 0.06), ('positions', 0.059), ('radius', 0.059), ('arms', 0.057), ('score', 0.056), ('similarity', 0.056), ('diversity', 0.055), ('trajectory', 0.055), ('items', 0.055), ('position', 0.051), ('orthonormal', 0.05), ('parts', 0.05), ('particle', 0.049), ('eigenvector', 0.049), ('dual', 0.047), ('arm', 0.047), ('indexed', 0.045), ('decomposes', 0.044), ('iy', 0.044), ('xr', 0.043), ('particles', 0.041), ('marginal', 0.04), ('sequences', 0.04), ('near', 0.039), ('pass', 0.039), ('head', 0.039), ('trees', 0.038), ('multiplicatively', 0.038), ('kjj', 0.038), ('sets', 0.038), ('pixels', 0.038), ('messages', 0.037), ('nt', 0.037), ('tractable', 0.037), ('recall', 0.036), ('ei', 0.035), ('concisely', 0.035), ('compute', 0.035), ('eigenvectors', 0.035), ('zeros', 0.035), ('probabilities', 0.034), ('eigenvalues', 0.033), ('dot', 0.033), ('torso', 0.033), ('grammars', 0.033), ('exclusion', 0.033), ('elements', 0.033), ('travel', 0.031), ('backwards', 0.031), ('endpoints', 0.03), ('conditionals', 0.03), ('part', 0.029), ('successive', 0.029), ('graphical', 0.029), ('bi', 0.029), ('vi', 0.028), ('independently', 0.028), ('diverse', 0.028), ('vj', 0.027), ('precision', 0.027), ('points', 0.027), ('representation', 0.027), ('products', 0.027), ('selected', 0.026), ('object', 0.025), ('probabilistic', 0.025), ('images', 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999976 257 nips-2010-Structured Determinantal Point Processes

Author: Alex Kulesza, Ben Taskar

2 0.17173639 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

3 0.15603884 239 nips-2010-Sidestepping Intractable Inference with Structured Ensemble Cascades

Author: David Weiss, Benjamin Sapp, Ben Taskar

Abstract: For many structured prediction problems, complex models often require adopting approximate inference techniques such as variational methods or sampling, which generally provide no satisfactory accuracy guarantees. In this work, we propose sidestepping intractable inference altogether by learning ensembles of tractable sub-models as part of a structured prediction cascade. We focus in particular on problems with high-treewidth and large state-spaces, which occur in many computer vision tasks. Unlike other variational methods, our ensembles do not enforce agreement between sub-models, but ﬁlter the space of possible outputs by simply adding and thresholding the max-marginals of each constituent model. Our framework jointly estimates parameters for all models in the ensemble for each level of the cascade by minimizing a novel, convex loss function, yet requires only a linear increase in computation over learning or inference in a single tractable sub-model. We provide a generalization bound on the ﬁltering loss of the ensemble as a theoretical justiﬁcation of our approach, and we evaluate our method on both synthetic data and the task of estimating articulated human pose from challenging videos. We ﬁnd that our approach signiﬁcantly outperforms loopy belief propagation on the synthetic data and a state-of-the-art model on the pose estimation/tracking problem. 1

4 0.13658966 221 nips-2010-Random Projections for $k$-means Clustering

Author: Christos Boutsidis, Anastasios Zouzias, Petros Drineas

Abstract: This paper discusses the topic of dimensionality reduction for k-means clustering. We prove that any set of n points in d dimensions (rows in a matrix A ∈ Rn×d ) can be projected into t = Ω(k/ε2 ) dimensions, for any ε ∈ (0, 1/3), in O(nd⌈ε−2 k/ log(d)⌉) time, such that with constant probability the optimal k-partition of the point set is preserved within a factor of 2 + √ The projection is done ε. √ by post-multiplying A with a d × t random matrix R having entries +1/ t or −1/ t with equal probability. A numerical implementation of our technique and experiments on a large face images dataset verify the speed and the accuracy of our theoretical results.

5 0.11615973 240 nips-2010-Simultaneous Object Detection and Ranking with Weak Supervision

Author: Matthew Blaschko, Andrea Vedaldi, Andrew Zisserman

Abstract: A standard approach to learning object category detectors is to provide strong supervision in the form of a region of interest (ROI) specifying each instance of the object in the training images [17]. In this work are goal is to learn from heterogeneous labels, in which some images are only weakly supervised, specifying only the presence or absence of the object or a weak indication of object location, whilst others are fully annotated. To this end we develop a discriminative learning approach and make two contributions: (i) we propose a structured output formulation for weakly annotated images where full annotations are treated as latent variables; and (ii) we propose to optimize a ranking objective function, allowing our method to more effectively use negatively labeled images to improve detection average precision performance. The method is demonstrated on the benchmark INRIA pedestrian detection dataset of Dalal and Triggs [14] and the PASCAL VOC dataset [17], and it is shown that for a signiﬁcant proportion of weakly supervised images the performance achieved is very similar to the fully supervised (state of the art) results. 1

6 0.10892656 98 nips-2010-Functional form of motion priors in human motion perception

7 0.1083729 209 nips-2010-Pose-Sensitive Embedding by Nonlinear NCA Regression

8 0.098431095 118 nips-2010-Implicit Differentiation by Perturbation

9 0.082694098 235 nips-2010-Self-Paced Learning for Latent Variable Models

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

11 0.073990874 6 nips-2010-A Discriminative Latent Model of Image Region and Object Tag Correspondence

12 0.070333801 230 nips-2010-Robust Clustering as Ensembles of Affinity Relations

13 0.068260573 205 nips-2010-Permutation Complexity Bound on Out-Sample Error

14 0.066614017 163 nips-2010-Lower Bounds on Rate of Convergence of Cutting Plane Methods

15 0.064980924 49 nips-2010-Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning

16 0.064526342 150 nips-2010-Learning concept graphs from text with stick-breaking priors

17 0.062799819 78 nips-2010-Error Propagation for Approximate Policy and Value Iteration

18 0.060683101 283 nips-2010-Variational Inference over Combinatorial Spaces

19 0.059891894 22 nips-2010-Active Estimation of F-Measures

20 0.059891704 131 nips-2010-Joint Analysis of Time-Evolving Binary Matrices and Associated Documents

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.205), (1, 0.05), (2, -0.002), (3, -0.032), (4, -0.061), (5, -0.043), (6, -0.025), (7, 0.021), (8, 0.057), (9, -0.001), (10, -0.111), (11, -0.147), (12, 0.055), (13, 0.071), (14, 0.061), (15, 0.029), (16, 0.02), (17, -0.014), (18, 0.002), (19, 0.08), (20, 0.026), (21, -0.018), (22, 0.098), (23, 0.026), (24, -0.03), (25, -0.019), (26, -0.065), (27, -0.267), (28, 0.13), (29, -0.124), (30, 0.111), (31, 0.003), (32, -0.068), (33, 0.027), (34, 0.09), (35, -0.022), (36, -0.035), (37, -0.134), (38, 0.089), (39, 0.004), (40, -0.118), (41, 0.033), (42, -0.013), (43, -0.044), (44, 0.041), (45, -0.054), (46, 0.074), (47, -0.128), (48, -0.12), (49, -0.095)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96098232 257 nips-2010-Structured Determinantal Point Processes

Author: Alex Kulesza, Ben Taskar

2 0.68276352 239 nips-2010-Sidestepping Intractable Inference with Structured Ensemble Cascades

Author: David Weiss, Benjamin Sapp, Ben Taskar

3 0.62982666 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

4 0.52888596 118 nips-2010-Implicit Differentiation by Perturbation

Author: Justin Domke

Abstract: This paper proposes a simple and eﬃcient ﬁnite diﬀerence method for implicit diﬀerentiation of marginal inference results in discrete graphical models. Given an arbitrary loss function, deﬁned on marginals, we show that the derivatives of this loss with respect to model parameters can be obtained by running the inference procedure twice, on slightly perturbed model parameters. This method can be used with approximate inference, with a loss function over approximate marginals. Convenient choices of loss functions make it practical to ﬁt graphical models with hidden variables, high treewidth and/or model misspeciﬁcation. 1

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

Author: Tamir Hazan, Raquel Urtasun

Abstract: In this paper we propose an approximated structured prediction framework for large scale graphical models and derive message-passing algorithms for learning their parameters efﬁciently. We ﬁrst relate CRFs and structured SVMs and show that in CRFs a variant of the log-partition function, known as the soft-max, smoothly approximates the hinge loss function of structured SVMs. We then propose an intuitive approximation for the structured prediction problem, using duality, based on a local entropy approximation and derive an efﬁcient messagepassing algorithm that is guaranteed to converge. Unlike existing approaches, this allows us to learn efﬁciently graphical models with cycles and very large number of parameters. 1

6 0.4878079 209 nips-2010-Pose-Sensitive Embedding by Nonlinear NCA Regression

7 0.48052663 221 nips-2010-Random Projections for $k$-means Clustering

8 0.46208915 240 nips-2010-Simultaneous Object Detection and Ranking with Weak Supervision

9 0.45678428 55 nips-2010-Cross Species Expression Analysis using a Dirichlet Process Mixture Model with Latent Matchings

10 0.45541036 163 nips-2010-Lower Bounds on Rate of Convergence of Cutting Plane Methods

11 0.45065427 126 nips-2010-Inference with Multivariate Heavy-Tails in Linear Models

12 0.42957795 235 nips-2010-Self-Paced Learning for Latent Variable Models

13 0.42841119 248 nips-2010-Sparse Inverse Covariance Selection via Alternating Linearization Methods

14 0.42505193 205 nips-2010-Permutation Complexity Bound on Out-Sample Error

15 0.42074519 45 nips-2010-CUR from a Sparse Optimization Viewpoint

16 0.41861114 255 nips-2010-Static Analysis of Binary Executables Using Structural SVMs

17 0.40886182 2 nips-2010-A Bayesian Approach to Concept Drift

18 0.39131963 58 nips-2010-Decomposing Isotonic Regression for Efficiently Solving Large Problems

19 0.37960732 158 nips-2010-Learning via Gaussian Herding

20 0.37903604 283 nips-2010-Variational Inference over Combinatorial Spaces

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(12, 0.185), (13, 0.057), (17, 0.043), (27, 0.062), (30, 0.083), (35, 0.021), (45, 0.234), (50, 0.071), (52, 0.027), (60, 0.037), (77, 0.057), (90, 0.026)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.92114627 95 nips-2010-Feature Transitions with Saccadic Search: Size, Color, and Orientation Are Not Alike

Author: Stella X. Yu

Abstract: Size, color, and orientation have long been considered elementary features whose attributes are extracted in parallel and available to guide the deployment of attention. If each is processed in the same fashion with simply a different set of local detectors, one would expect similar search behaviours on localizing an equivalent ﬂickering change among identically laid out disks. We analyze feature transitions associated with saccadic search and ﬁnd out that size, color, and orientation are not alike in dynamic attribute processing over time. The Markovian feature transition is attractive for size, repulsive for color, and largely reversible for orientation. 1

same-paper 2 0.87971359 257 nips-2010-Structured Determinantal Point Processes

Author: Alex Kulesza, Ben Taskar

3 0.82268643 155 nips-2010-Learning the context of a category

Author: Dan Navarro

Abstract: This paper outlines a hierarchical Bayesian model for human category learning that learns both the organization of objects into categories, and the context in which this knowledge should be applied. The model is ﬁt to multiple data sets, and provides a parsimonious method for describing how humans learn context speciﬁc conceptual representations.

4 0.81966388 49 nips-2010-Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning

Author: Matthias Broecheler, Lise Getoor

Abstract: Continuous Markov random ﬁelds are a general formalism to model joint probability distributions over events with continuous outcomes. We prove that marginal computation for constrained continuous MRFs is #P-hard in general and present a polynomial-time approximation scheme under mild assumptions on the structure of the random ﬁeld. Moreover, we introduce a sampling algorithm to compute marginal distributions and develop novel techniques to increase its efﬁciency. Continuous MRFs are a general purpose probabilistic modeling tool and we demonstrate how they can be applied to statistical relational learning. On the problem of collective classiﬁcation, we evaluate our algorithm and show that the standard deviation of marginals serves as a useful measure of conﬁdence. 1

5 0.81774557 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

Author: Rina Foygel, Mathias Drton

Abstract: Gaussian graphical models with sparsity in the inverse covariance matrix are of signiﬁcant interest in many modern applications. For the problem of recovering the graphical structure, information criteria provide useful optimization objectives for algorithms searching through sets of graphs or for selection of tuning parameters of other methods such as the graphical lasso, which is a likelihood penalization technique. In this paper we establish the consistency of an extended Bayesian information criterion for Gaussian graphical models in a scenario where both the number of variables p and the sample size n grow. Compared to earlier work on the regression case, our treatment allows for growth in the number of non-zero parameters in the true model, which is necessary in order to cover connected graphs. We demonstrate the performance of this criterion on simulated data when used in conjunction with the graphical lasso, and verify that the criterion indeed performs better than either cross-validation or the ordinary Bayesian information criterion when p and the number of non-zero parameters q both scale with n. 1

6 0.8175509 238 nips-2010-Short-term memory in neuronal networks through dynamical compressed sensing

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

8 0.81655049 148 nips-2010-Learning Networks of Stochastic Differential Equations

9 0.81561363 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

10 0.81416392 117 nips-2010-Identifying graph-structured activation patterns in networks

11 0.81331968 51 nips-2010-Construction of Dependent Dirichlet Processes based on Poisson Processes

12 0.81307381 92 nips-2010-Fast global convergence rates of gradient methods for high-dimensional statistical recovery

13 0.81287467 241 nips-2010-Size Matters: Metric Visual Search Constraints from Monocular Metadata

14 0.81280088 85 nips-2010-Exact learning curves for Gaussian process regression on large random graphs

15 0.81249946 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior

16 0.81199914 12 nips-2010-A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups

17 0.8112666 265 nips-2010-The LASSO risk: asymptotic results and real world examples

18 0.81110865 202 nips-2010-Parallelized Stochastic Gradient Descent

19 0.81041986 287 nips-2010-Worst-Case Linear Discriminant Analysis

20 0.81027746 70 nips-2010-Efficient Optimization for Discriminative Latent Class Models