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

102 nips-2010-Generalized roof duality and bisubmodular functions

Source: pdf

Author: Vladimir Kolmogorov

Abstract: ˆ Consider a convex relaxation f of a pseudo-boolean function f . We say that ˆ the relaxation is totally half-integral if f (x) is a polyhedral function with halfintegral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form xi = xj , xi = 1 − xj , and xi = γ where 1 γ ∈ {0, 1, 2 } is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-boolean functions f . We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-boolean functions. Our contributions are as follows. First, we provide a complete characterization ˆ of totally half-integral relaxations f by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Generalized roof duality and bisubmodular functions Vladimir Kolmogorov Department of Computer Science University College London, UK v. [sent-1, score-1.218]

2 uk Abstract ˆ Consider a convex relaxation f of a pseudo-boolean function f . [sent-5, score-0.167]

3 We say that ˆ the relaxation is totally half-integral if f (x) is a polyhedral function with halfintegral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form xi = xj , xi = 1 − xj , and xi = γ where 1 γ ∈ {0, 1, 2 } is a constant. [sent-6, score-0.722]

4 A well-known example is the roof duality relaxation for quadratic pseudo-boolean functions f . [sent-7, score-0.741]

5 We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-boolean functions. [sent-8, score-0.552]

6 First, we provide a complete characterization ˆ of totally half-integral relaxations f by establishing a one-to-one correspondence with bisubmodular functions. [sent-10, score-1.099]

7 Second, we give a new characterization of bisubmodular functions. [sent-11, score-0.726]

8 Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. [sent-12, score-0.913]

9 In this paper we consider convex relaxations ˆ f : K → R of f which we call totally half-integral: ˆ Deﬁnition 1. [sent-14, score-0.392]

10 (b) Function f : K → R is called totally half-integral if ˆ the form (x, f ˆ restrictions f : P → R are half-integral for all subsets P ⊆ K obtained from K by adding an arbitrary combination of constraints of the form xi = xj , xi = xj , and xi = γ for points x ∈ K. [sent-16, score-0.539]

11 2 A well-known example of a totally half-integral relaxation is the roof duality relaxation for quadratic pseudo-boolean functions f (x) = i ci x i + (i,j) cij xi xj studied by Hammer, Hansen and Simeone [13]. [sent-18, score-1.197]

12 It is known to possess the persistency property: for any half-integral minimizer ˆx x ∈ arg min f (ˆ) there exists minimizer x ∈ arg min f (x) such that xi = xi for all nodes i with ˆ ˆ integral component xi . [sent-19, score-0.535]

13 The goal of this paper is to generalize the roof duality approach to arbitrary pseudo-boolean functions. [sent-22, score-0.514]

14 1 We provide a complete characterization of totally half-integral relaxations. [sent-25, score-0.228]

15 Namely, we prove in secˆ tion 2 that if f : K → R is totally half-integral then its restriction to K1/2 is a bisubmodular function, and conversely any bisubmodular function can be extended to a totally half-integral relaxation. [sent-26, score-1.767]

16 Using this characterization, we then prove several results showing links with the roof duality relaxation (section 4). [sent-29, score-0.684]

17 For some vision applications the roof duality approach [13] has shown a good performance [30, 32, 23, 24, 33, 1, 16, 17]. [sent-38, score-0.536]

18 Therefore, studying generalizations of roof duality to arbitrary pseudo-boolean functions is an important task. [sent-40, score-0.582]

19 Indeed, ˆ ˆ in practice, the relaxation f is obtained as the sum of relaxations fC constructed for each term independently. [sent-42, score-0.345]

20 If c is sufﬁciently large, then applying the roof duality relaxation to these terms would yield constraints xi = xj and 1 x = xj present in the deﬁnition of total half-integrality. [sent-44, score-0.845]

21 Constraints xi = γ ∈ {0, 1, 2 } can also be simulated via the roof duality, e. [sent-45, score-0.424]

22 xi = xj , xi = xj for the same pair of nodes i, j implies xi = xj = 1 . [sent-47, score-0.44]

23 2 Related work Half-integrality There is a vast literature on using half-integral relaxations for various combinatorial optimization problems. [sent-49, score-0.217]

24 In many cases these relaxations lead to 2-approximation algorithms. [sent-50, score-0.197]

25 Hammer, Hansen and Simeone [13] established that these properties hold for the roof duality relaxation for quadratic pseudo-boolean functions. [sent-53, score-0.711]

26 (The relaxation in [25] relied on converting function f to a multinomial representation; see section 4 for more details. [sent-55, score-0.148]

27 Very recently, Iwata and Nagano [18] formulated a half-integral relaxation for the problem of minimizing submodular function f (x) under constraints of the form xi + xj ≥ 1. [sent-57, score-0.602]

28 2 In computer vision, several researchers considered the following scheme: given a function f (x) = fC (x), convert terms fC (x) to quadratic pseudo-boolean functions by introducing auxiliary binary variables, and then apply the roof duality relaxation to the latter. [sent-62, score-0.784]

29 To the best of our knowledge, all examples of totally half-integral relaxations proposed so far belong to the class of submodular relaxations, which is deﬁned in section 4. [sent-66, score-0.677]

30 They form a subclass of more general bisubmodular relaxations. [sent-67, score-0.674]

31 The notion of the Lov´ sz extension of a bisubmodular function introduced by Qi [29] a will be of particular importance for our work (see next section). [sent-71, score-0.757]

32 It has been shown that some submodular minimization algorithms can be generalized to bisubmodular functions. [sent-72, score-0.997]

33 A weakly polynomial combinatorial algorithm for minimizing bisubmodular functions was given by Fujishige and Iwata [12], and a strongly polynomial version was given by McCormick and Fujishige [26]. [sent-74, score-0.742]

34 Recently, we introduced strongly and weakly tree-submodular functions [22] that generalize bisubmodular functions. [sent-75, score-0.704]

35 If f : K → R is a totally half-integral relaxation then its restriction to K1/2 is bisubmodular. [sent-78, score-0.346]

36 Conversely, if function f : K1/2 → R is bisubmodular then it has a unique totally halfˆ integral extension f : K → R. [sent-79, score-0.926]

37 Under this change totally half-integral relaxations are transformed to totally integral relaxations: ˆ ˆ Deﬁnition 4. [sent-83, score-0.605]

38 (a) h is called integral if it is a convex ˆ polyhedral function such that all extreme points of the epigraph {(x, z) | x ∈ L, z ≥ h(x)} have the 1/2 ˆ ˆ form (x, h(x)) where x ∈ L . [sent-85, score-0.175]

39 (b) h is called totally integral if it is integral and for an arbitrary ordering of nodes the following functions of n − 1 variables (if n > 1) are totally integral: ˆ h (x1 , . [sent-86, score-0.617]

40 , xn−1 , γ) for any constant γ ∈ {−1, 0, 1} The deﬁnition of a bisubmodular function is adapted as follows: function h : L1/2 → R is bisubmodular if inequality (1) holds for all x, y ∈ L1/2 where operations , are deﬁned by tables (2) 1 after replacements 0 → −1, 2 → 0, 1 → 1. [sent-104, score-1.37]

41 To prove theorem 3, it sufﬁces to establish a link ˆ between totally integral relaxations h : L → R and bisubmodular functions h : L1/2 → R. [sent-105, score-1.155]

42 To each signed ordering ω we associate labelings x0 , x1 , . [sent-112, score-0.221]

43 Given a vector x ∈ R , select a signed ordering ω = (π, σ) as follows: (i) choose π so that values |xi |, i ∈ V are non-increasing, and rename nodes accordingly so that |x1 | ≥ . [sent-130, score-0.179]

44 It is not difﬁcult to check that n λi xi x= (4a) i=1 where labelings xi are deﬁned in (3) (with respect to the selected signed ordering) and λi = |xi | − |xi+1 | for i = 1, . [sent-134, score-0.376]

45 Function h is bisubmodular if and only if its Lov´ sz extension h is convex on a L. [sent-139, score-0.776]

46 , n − 1 there holds Li = {x ∈ Lω | xi = σi−1 σi xi−1 }, and for i = n we have Ln = {x ∈ Lω | xn = 0}. [sent-180, score-0.159]

47 Suppose function h : L → R with h(0) = 0 is totally integral. [sent-182, score-0.176]

48 If h : L1/2 → R with h(0) = 0 is bisubmodular then its Lov´ sz extension h : L → R is a totally integral. [sent-187, score-0.933]

49 It remains to show that functions h considered in deﬁnition 4 are V \{n} totally integral. [sent-199, score-0.206]

50 , xn−1 , γ) , γ ∈ {−1, 0, 1} It can be checked that these functions are bisubmodular, and their Lov´ sz extensions coincide with a ˆ respective functions h used in deﬁnition 4. [sent-218, score-0.163]

51 3 A new characterization of bisubmodularity In this section we give an alternative deﬁnition of bisubmodularity; it will be helpful later for describing a relationship to the roof duality. [sent-220, score-0.454]

52 The node i for i ∈ V is called the “mate” of i; intuitively, variable ui corresponds to the complement of ui . [sent-222, score-0.392]

53 Function f : X − → R is called bisubmodular if f (u v) + f (u v) ≤ f (u) + f (v) ∀ u, v ∈ X − (6) where u v = u ∧ v, u v = REDUCE(u ∨ v) and REDUCE(w) is the labeling obtained from w by changing labels (wi , wi ) from (1, 1) to (0, 0) for all i ∈ V . [sent-233, score-0.73]

54 For a labeling u ∈ X , deﬁne labeling u by (u )i = ui . [sent-236, score-0.263]

55 Labels (ui , ui ) are transformed according to the rules (0, 1) → (0, 1) (1, 0) → (1, 0) (0, 0) → (1, 1) (1, 1) → (0, 0) (7) Equivalently, this mapping can be written as (x, y) = (y, x). [sent-237, score-0.187]

56 Next, we deﬁne sets X − = {u ∈ X | u ≤ u } = {u ∈ X | (ui , ui ) = (1, 1) ∀i ∈ V } X + = {u ∈ X | u ≥ u } = {u ∈ X | (ui , ui ) = (0, 0) ∀i ∈ V } X◦ X = {u ∈ X | u = u } = {u ∈ X | (ui , ui ) ∈ {(0, 1), (1, 0)} = X− ∪ X+ ∀i ∈ V } = X − ∩ X + Clearly, u ∈ X − if and only if u ∈ X + . [sent-239, score-0.561]

57 4 Submodular relaxations and roof duality Consider a submodular function g : X → R satisfying the following “symmetry” condition: ∀u ∈ X g(u ) = g(u) (10) We call such function g a submodular relaxation of function f (x) = g(x, x). [sent-257, score-1.467]

58 Clearly, it satisﬁes conditions of proposition 10, so g is also a bisubmodular relaxation of f . [sent-258, score-0.822]

59 Review of roof duality Consider a quadratic pseudo-boolean function f : B → R: f (x) = fi (xi ) + i∈V fij (xi , xj ) (11) (i,j)∈E where (V, E) is an undirected graph and xi ∈ {0, 1} for i ∈ V are binary variables. [sent-261, score-0.873]

60 Hammer, Hansen and Simeone [13] formulated several linear programming relaxations of this function and 3 Denote u = 1 0 1 0 0 0 0 0 and v = 0 1 0 0 0 0 1 0 where the top and bottom rows correspond to the labelings of V and V \V respectively, with |V | = 4. [sent-262, score-0.332]

61 One of these formulations was called a roof dual. [sent-266, score-0.361]

62 An efﬁcient maxﬂowbased method for solving the roof duality relaxation was given by Hammer, Boros and Sun [5, 4]. [sent-267, score-0.662]

63 We will rely on this algorithmic description of the roof duality approach [4]. [sent-268, score-0.514]

64 Each variable xi is replaced with two binary variables ui and ui corresponding to xi and 1 − xi respectively. [sent-270, score-0.658]

65 If u ∈ X is a minimizer of g then the roof duality relaxation has a minimizer x with ˆ xi = 1 (ui + ui ) [4]. [sent-273, score-1.018]

66 ˆ 2 It is easy to check that g(u) = g(u ) for all u ∈ X , therefore g is a submodular relaxation. [sent-274, score-0.34]

67 Also, f and g are equivalent when ui = ui for all i ∈ V , i. [sent-275, score-0.374]

68 ∀x ∈ B g(x, x) = f (x) (13) Invariance to variable ﬂipping Suppose that g is a (bi-)submodular relaxation of function f : B → R. [sent-277, score-0.148]

69 Let i be a ﬁxed node in V , and consider function f (x) obtained from f (x) by a change of coordinates xi → xi and function g (u) obtained from g(u) by swapping variables ui and ui . [sent-278, score-0.554]

70 It is easy to check that g is a (bi-)submodular relaxation of f . [sent-279, score-0.184]

71 Furthermore, if f is a quadratic pseudoboolean function and g is its submodular relaxation constructed by the roof duality approach, then applying the roof duality approach to f yields function g . [sent-280, score-1.568]

72 Conversion to roof duality Let us now consider a non-quadratic pseudo-boolean function f : B → R. [sent-282, score-0.514]

73 Several papers [33, 1, 16] proposed the following scheme: (1) Convert f to a quadratic pseudo˜ ˜ boolean function f by introducing k auxiliary binary variables so that f (x) = minα∈{0,1}k f (x, α) ˜ by applying the roof for all labelings x ∈ B. [sent-283, score-0.568]

74 (2) Construct submodular relaxation g (x, α, y, β) of f ˜ ˜ duality relaxation to f ; then ˜ g (x, α, y, β) = g (y, β, x, α) , g (x, α, x, α) = f (x, α) ˜ ˜ ˜ (3) Obtain function g by minα,β ∈{0,1}k g (x, α, y, β). [sent-284, score-0.771]

75 ˜ minimizing out auxiliary ∀x, y ∈ B, α, β ∈ {0, 1}k variables: g(x, y) = One can check that g(x, y) = g(y, x), so g is a submodular relaxation4 . [sent-285, score-0.378]

76 Existence of submodular relaxations It is easy to check that if f : B → R is submodular 1 then function g(x, y) = 2 [f (x) + f (y)] is a submodular relaxation of f . [sent-289, score-1.293]

77 5 Thus, monomials of the form cΠi∈A xi where c ≤ 0 and A ⊆ V have submodular relaxations. [sent-290, score-0.444]

78 Using the “ﬂipping” operation xi → xi , we conclude that submodular relaxations also exist for monomials of the form 4 It is well-known that minimizing variables out preserves submodularity. [sent-291, score-0.758]

79 Indeed, suppose that h(x) = ˜ ˜ minα h(x, α) where h is a submodular function. [sent-292, score-0.324]

80 Then h is also submodular since ˜ ˜ ˜ ˜ h(x) + h(y) = h(x, α) + h(y, β) ≥ h(x ∧ y, α ∧ β) + h(x ∨ y, α ∨ β) ≥ h(x ∧ y) + h(x ∨ y) 5 In fact, it dominates all other bisubmodular relaxations g : X − → R of f . [sent-293, score-1.195]

81 ¯ g ¯ 7 cΠi∈A xi Πi∈B xi where c ≤ 0 and A, B are disjoint subsets of U . [sent-296, score-0.162]

82 This implies that any pseudo-boolean function f has a submodular relaxation. [sent-300, score-0.304]

83 Note that this argument is due to Lu and Williams [25] who converted function f to a sum of monomials of the form cΠi∈A xi and cxk Πi∈A xi , c ≤ 0, k ∈ A. [sent-301, score-0.221]

84 It is possible to show that the / relaxation proposed in [25] is equivalent to the submodular relaxation constructed by the scheme above (we omit the derivation). [sent-302, score-0.6]

85 bisubmodular relaxations An important question is whether bisubmodular relaxations are more “powerful” compared to submodular ones. [sent-304, score-2.046]

86 Let g be the submodular relaxation of a quadratic pseudo-boolean function f deﬁned by (12), and assume that the set E does not have parallel edges. [sent-307, score-0.501]

87 Then g dominates any other bisubmodular relaxation g of f , i. [sent-308, score-0.842]

88 we give an example of a function f of n = 4 variables which has a tight bisubmodular relaxation g (i. [sent-313, score-0.84]

89 g has a minimizer in X ◦ ), but all submodular relaxations are not tight. [sent-315, score-0.545]

90 Persistency Finally, we show that bisubmodular functions possess the autarky property, which implies persistency. [sent-316, score-0.775]

91 Let f : K1/2 → R be a bisubmodular function and x ∈ K1/2 be its minimizer. [sent-318, score-0.674]

92 Then z ∈ B and [Persistency] Function f : B → R has a minimizer x∗ ∈ B such that x∗ = xi for nodes i ∈ V i with integral xi . [sent-322, score-0.306]

93 It can be checked that zi = yi if xi = 2 and zi = xi if xi ∈ {0, 1}. [sent-324, score-0.283]

94 5 Conclusions and future work We showed that bisubmodular functions can be viewed as a natural generalization of the roof duality approach to higher-order cliques. [sent-329, score-1.218]

95 An important ˆ open question is how to construct bisubmodular relaxations fC for individual terms. [sent-331, score-0.871]

96 However, in our case we need to minimize a bisubmodular function which has a special structure: it is represented as a sum of low-order bisubmodular terms. [sent-337, score-1.348]

97 We recently showed [21] that a sum of low-order submodular terms can be optimized more efﬁciently using maxﬂow-like techniques. [sent-338, score-0.304]

98 We conjecture that similar techniques can be developed for bisubmodular functions as well. [sent-339, score-0.704]

99 Submodularity on a tree: Unifying L -convex and bisubmodular functions. [sent-452, score-0.674]

100 Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. [sent-471, score-0.694]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('bisubmodular', 0.674), ('roof', 0.343), ('submodular', 0.304), ('relaxations', 0.197), ('ui', 0.187), ('totally', 0.176), ('duality', 0.171), ('relaxation', 0.148), ('fij', 0.116), ('labelings', 0.115), ('hammer', 0.083), ('xi', 0.081), ('xn', 0.078), ('persistency', 0.077), ('fc', 0.07), ('signed', 0.063), ('sz', 0.063), ('lov', 0.061), ('rv', 0.06), ('fujishige', 0.059), ('satoru', 0.059), ('bisubmodularity', 0.059), ('monomials', 0.059), ('integral', 0.056), ('characterization', 0.052), ('xj', 0.051), ('quadratic', 0.049), ('boros', 0.047), ('autarky', 0.044), ('bouchet', 0.044), ('simeone', 0.044), ('nodes', 0.044), ('minimizer', 0.044), ('ordering', 0.043), ('checked', 0.04), ('hansen', 0.04), ('pseudoboolean', 0.039), ('generalizations', 0.038), ('labeling', 0.038), ('check', 0.036), ('uj', 0.035), ('inequalities', 0.033), ('iwata', 0.033), ('lempitsky', 0.031), ('functions', 0.03), ('epigraph', 0.029), ('kabadi', 0.029), ('mccormick', 0.029), ('rename', 0.029), ('rutcor', 0.029), ('woodford', 0.029), ('rother', 0.029), ('ipping', 0.028), ('qi', 0.027), ('ek', 0.027), ('polyhedral', 0.027), ('possess', 0.027), ('extreme', 0.026), ('induction', 0.026), ('rrr', 0.026), ('lu', 0.025), ('chandrasekaran', 0.024), ('carsten', 0.024), ('characterizations', 0.024), ('integrality', 0.024), ('santosh', 0.024), ('binary', 0.023), ('conversely', 0.023), ('inequality', 0.022), ('prove', 0.022), ('fi', 0.022), ('victor', 0.022), ('nemhauser', 0.022), ('ej', 0.022), ('vision', 0.022), ('restriction', 0.022), ('facets', 0.021), ('ando', 0.021), ('extension', 0.02), ('dominates', 0.02), ('combinatorial', 0.02), ('auxiliary', 0.02), ('programming', 0.02), ('suppose', 0.02), ('integer', 0.019), ('stefan', 0.019), ('submodularity', 0.019), ('cvpr', 0.019), ('convex', 0.019), ('kolmogorov', 0.019), ('minimization', 0.019), ('called', 0.018), ('fusion', 0.018), ('november', 0.018), ('claim', 0.018), ('variables', 0.018), ('discrete', 0.018), ('minimizing', 0.018), ('graph', 0.017), ('ali', 0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 102 nips-2010-Generalized roof duality and bisubmodular functions

Author: Vladimir Kolmogorov

2 0.24130778 258 nips-2010-Structured sparsity-inducing norms through submodular functions

Author: Francis R. Bach

Abstract: Sparse methods for supervised learning aim at ﬁnding good linear predictors from as few variables as possible, i.e., with small cardinality of their supports. This combinatorial selection problem is often turned into a convex optimization problem by replacing the cardinality function by its convex envelope (tightest convex lower bound), in this case the ℓ1 -norm. In this paper, we investigate more general set-functions than the cardinality, that may incorporate prior knowledge or structural constraints which are common in many applications: namely, we show that for nondecreasing submodular set-functions, the corresponding convex envelope can be obtained from its Lov´ sz extension, a common tool in submodua lar analysis. This deﬁnes a family of polyhedral norms, for which we provide generic algorithmic tools (subgradients and proximal operators) and theoretical results (conditions for support recovery or high-dimensional inference). By selecting speciﬁc submodular functions, we can give a new interpretation to known norms, such as those based on rank-statistics or grouped norms with potentially overlapping groups; we also deﬁne new norms, in particular ones that can be used as non-factorial priors for supervised learning.

3 0.22797899 69 nips-2010-Efficient Minimization of Decomposable Submodular Functions

Author: Peter Stobbe, Andreas Krause

Abstract: Many combinatorial problems arising in machine learning can be reduced to the problem of minimizing a submodular function. Submodular functions are a natural discrete analog of convex functions, and can be minimized in strongly polynomial time. Unfortunately, state-of-the-art algorithms for general submodular minimization are intractable for larger problems. In this paper, we introduce a novel subclass of submodular minimization problems that we call decomposable. Decomposable submodular functions are those that can be represented as sums of concave functions applied to modular functions. We develop an algorithm, SLG, that can efÄ?Ĺš ciently minimize decomposable submodular functions with tens of thousands of variables. Our algorithm exploits recent results in smoothed convex minimization. We apply SLG to synthetic benchmarks and a joint classiÄ?Ĺš cation-and-segmentation task, and show that it outperforms the state-of-the-art general purpose submodular minimization algorithms by several orders of magnitude. 1

4 0.17492117 166 nips-2010-Minimum Average Cost Clustering

Author: Kiyohito Nagano, Yoshinobu Kawahara, Satoru Iwata

Abstract: A number of objective functions in clustering problems can be described with submodular functions. In this paper, we introduce the minimum average cost criterion, and show that the theory of intersecting submodular functions can be used for clustering with submodular objective functions. The proposed algorithm does not require the number of clusters in advance, and it will be determined by the property of a given set of data points. The minimum average cost clustering problem is parameterized with a real variable, and surprisingly, we show that all information about optimal clusterings for all parameters can be computed in polynomial time in total. Additionally, we evaluate the performance of the proposed algorithm through computational experiments. 1

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

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

6 0.07572262 73 nips-2010-Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization

7 0.074116528 223 nips-2010-Rates of convergence for the cluster tree

8 0.066384509 170 nips-2010-Moreau-Yosida Regularization for Grouped Tree Structure Learning

9 0.048757717 63 nips-2010-Distributed Dual Averaging In Networks

10 0.048485719 181 nips-2010-Network Flow Algorithms for Structured Sparsity

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

12 0.045018021 70 nips-2010-Efficient Optimization for Discriminative Latent Class Models

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

14 0.041751109 148 nips-2010-Learning Networks of Stochastic Differential Equations

15 0.039986171 164 nips-2010-MAP Estimation for Graphical Models by Likelihood Maximization

16 0.039961372 225 nips-2010-Relaxed Clipping: A Global Training Method for Robust Regression and Classification

17 0.038854521 49 nips-2010-Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning

18 0.038123935 91 nips-2010-Fast detection of multiple change-points shared by many signals using group LARS

19 0.038029224 232 nips-2010-Sample Complexity of Testing the Manifold Hypothesis

20 0.03708268 236 nips-2010-Semi-Supervised Learning with Adversarially Missing Label Information

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.112), (1, 0.036), (2, 0.096), (3, 0.043), (4, -0.004), (5, -0.113), (6, -0.06), (7, 0.097), (8, 0.299), (9, 0.034), (10, 0.121), (11, 0.089), (12, 0.072), (13, -0.053), (14, -0.16), (15, 0.105), (16, -0.0), (17, -0.036), (18, 0.032), (19, -0.018), (20, -0.1), (21, -0.078), (22, 0.014), (23, -0.001), (24, 0.066), (25, 0.091), (26, 0.047), (27, -0.024), (28, -0.04), (29, 0.05), (30, -0.02), (31, 0.04), (32, 0.038), (33, 0.042), (34, 0.058), (35, -0.042), (36, 0.06), (37, 0.047), (38, 0.023), (39, 0.035), (40, -0.022), (41, -0.032), (42, -0.019), (43, 0.001), (44, -0.029), (45, 0.013), (46, -0.007), (47, -0.013), (48, -0.033), (49, 0.05)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.93138492 102 nips-2010-Generalized roof duality and bisubmodular functions

Author: Vladimir Kolmogorov

2 0.84969097 69 nips-2010-Efficient Minimization of Decomposable Submodular Functions

Author: Peter Stobbe, Andreas Krause

3 0.82898366 258 nips-2010-Structured sparsity-inducing norms through submodular functions

Author: Francis R. Bach

4 0.72852355 166 nips-2010-Minimum Average Cost Clustering

Author: Kiyohito Nagano, Yoshinobu Kawahara, Satoru Iwata

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

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

6 0.30290636 181 nips-2010-Network Flow Algorithms for Structured Sparsity

7 0.26914018 108 nips-2010-Graph-Valued Regression

8 0.25976884 288 nips-2010-Worst-case bounds on the quality of max-product fixed-points

9 0.2540563 278 nips-2010-Universal Consistency of Multi-Class Support Vector Classification

10 0.24702314 58 nips-2010-Decomposing Isotonic Regression for Efficiently Solving Large Problems

11 0.24331842 164 nips-2010-MAP Estimation for Graphical Models by Likelihood Maximization

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

13 0.23271173 267 nips-2010-The Multidimensional Wisdom of Crowds

14 0.23181151 274 nips-2010-Trading off Mistakes and Don't-Know Predictions

15 0.2238421 236 nips-2010-Semi-Supervised Learning with Adversarially Missing Label Information

16 0.22321846 73 nips-2010-Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization

17 0.22262251 63 nips-2010-Distributed Dual Averaging In Networks

18 0.21831281 180 nips-2010-Near-Optimal Bayesian Active Learning with Noisy Observations

19 0.21638578 177 nips-2010-Multitask Learning without Label Correspondences

20 0.21384554 151 nips-2010-Learning from Candidate Labeling Sets

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.033), (21, 0.01), (27, 0.026), (30, 0.068), (33, 0.359), (35, 0.028), (45, 0.135), (50, 0.053), (52, 0.036), (60, 0.062), (77, 0.036), (78, 0.024), (90, 0.032)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.70341671 102 nips-2010-Generalized roof duality and bisubmodular functions

Author: Vladimir Kolmogorov

2 0.58045208 139 nips-2010-Latent Variable Models for Predicting File Dependencies in Large-Scale Software Development

Author: Diane Hu, Laurens Maaten, Youngmin Cho, Sorin Lerner, Lawrence K. Saul

Abstract: When software developers modify one or more ﬁles in a large code base, they must also identify and update other related ﬁles. Many ﬁle dependencies can be detected by mining the development history of the code base: in essence, groups of related ﬁles are revealed by the logs of previous workﬂows. From data of this form, we show how to detect dependent ﬁles by solving a problem in binary matrix completion. We explore different latent variable models (LVMs) for this problem, including Bernoulli mixture models, exponential family PCA, restricted Boltzmann machines, and fully Bayesian approaches. We evaluate these models on the development histories of three large, open-source software systems: Mozilla Firefox, Eclipse Subversive, and Gimp. In all of these applications, we ﬁnd that LVMs improve the performance of related ﬁle prediction over current leading methods. 1

3 0.56079954 258 nips-2010-Structured sparsity-inducing norms through submodular functions

Author: Francis R. Bach

4 0.47431675 89 nips-2010-Factorized Latent Spaces with Structured Sparsity

Author: Yangqing Jia, Mathieu Salzmann, Trevor Darrell

Abstract: Recent approaches to multi-view learning have shown that factorizing the information into parts that are shared across all views and parts that are private to each view could effectively account for the dependencies and independencies between the different input modalities. Unfortunately, these approaches involve minimizing non-convex objective functions. In this paper, we propose an approach to learning such factorized representations inspired by sparse coding techniques. In particular, we show that structured sparsity allows us to address the multiview learning problem by alternately solving two convex optimization problems. Furthermore, the resulting factorized latent spaces generalize over existing approaches in that they allow having latent dimensions shared between any subset of the views instead of between all the views only. We show that our approach outperforms state-of-the-art methods on the task of human pose estimation. 1

5 0.4496702 222 nips-2010-Random Walk Approach to Regret Minimization

Author: Hariharan Narayanan, Alexander Rakhlin

Abstract: We propose a computationally efﬁcient random walk on a convex body which rapidly mixes to a time-varying Gibbs distribution. In the setting of online convex optimization and repeated games, the algorithm yields low regret and presents a novel efﬁcient method for implementing mixture forecasting strategies. 1

6 0.44669294 270 nips-2010-Tight Sample Complexity of Large-Margin Learning

7 0.44352362 260 nips-2010-Sufficient Conditions for Generating Group Level Sparsity in a Robust Minimax Framework

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

9 0.44045386 117 nips-2010-Identifying graph-structured activation patterns in networks

10 0.43910643 193 nips-2010-Online Learning: Random Averages, Combinatorial Parameters, and Learnability

11 0.43905205 265 nips-2010-The LASSO risk: asymptotic results and real world examples

12 0.43780485 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

13 0.43762708 63 nips-2010-Distributed Dual Averaging In Networks

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

15 0.43750519 243 nips-2010-Smoothness, Low Noise and Fast Rates

16 0.43652511 69 nips-2010-Efficient Minimization of Decomposable Submodular Functions

17 0.43459728 280 nips-2010-Unsupervised Kernel Dimension Reduction

18 0.43458223 49 nips-2010-Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning

19 0.43436381 199 nips-2010-Optimal learning rates for Kernel Conjugate Gradient regression

20 0.43420693 166 nips-2010-Minimum Average Cost Clustering