nips nips2012 nips2012-248 knowledge-graph by maker-knowledge-mining

248 nips-2012-Nonparanormal Belief Propagation (NPNBP)

Source: pdf

Author: Gal Elidan, Cobi Cario

Abstract: The empirical success of the belief propagation approximate inference algorithm has inspired numerous theoretical and algorithmic advances. Yet, for continuous non-Gaussian domains performing belief propagation remains a challenging task: recent innovations such as nonparametric or kernel belief propagation, while useful, come with a substantial computational cost and offer little theoretical guarantees, even for tree structured models. In this work we present Nonparanormal BP for performing efﬁcient inference on distributions parameterized by a Gaussian copulas network and any univariate marginals. For tree structured networks, our approach is guaranteed to be exact for this powerful class of non-Gaussian models. Importantly, the method is as efﬁcient as standard Gaussian BP, and its convergence properties do not depend on the complexity of the univariate marginals, even when a nonparametric representation is used. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 il Abstract The empirical success of the belief propagation approximate inference algorithm has inspired numerous theoretical and algorithmic advances. [sent-7, score-0.32]

2 In this work we present Nonparanormal BP for performing efﬁcient inference on distributions parameterized by a Gaussian copulas network and any univariate marginals. [sent-9, score-0.288]

3 For tree structured networks, our approach is guaranteed to be exact for this powerful class of non-Gaussian models. [sent-10, score-0.146]

4 Importantly, the method is as efﬁcient as standard Gaussian BP, and its convergence properties do not depend on the complexity of the univariate marginals, even when a nonparametric representation is used. [sent-11, score-0.172]

5 The usefulness of such models in complex domains, where exact computations are infeasible, relies on our ability to perform efﬁcient and reasonably accurate inference of marginal and conditional probabilities. [sent-13, score-0.182]

6 Perhaps the most popular approximate inference algoritm for graphical models is belief propagation (BP) [Pearl, 1988]. [sent-14, score-0.345]

7 This has inspired several innovative and practically useful methods speciﬁcally aimed at the continuous non-Gaussian case such as expectation propagation [Minka, 2001], particle BP [Ihler and McAllester, 2009], nonparametric BP [Sudderth et al. [sent-26, score-0.161]

8 In terms of generality, we focus on the ﬂexible class of Copula Bayesian Networks (CBNs) [Elidan, 2010] that are deﬁned via local Gaussian copula functions and any univariate densities (possible nonparametric). [sent-33, score-0.518]

9 Utilizing the power of the copula framework [Nelsen, 2007], these models can capture complex multi-modal and heavy-tailed phenomena. [sent-34, score-0.339]

10 1 Figure 1: Samples from the bivariate Gaussian copula with correlation θ = 0. [sent-35, score-0.421]

11 First, it is guaranteed to converge and return exact results on tree structured models, regardless of the form of the univariate densities. [sent-39, score-0.273]

12 Third, its convergence properties on general graphs are similar to that of GaBP and, quite remarkably, do not depend on the complexity of the univariate marginals. [sent-41, score-0.127]

13 2 Background In this section we provide a brief background on copulas in general, the Gaussian copula in particular, and the Copula Bayesian Network model of Elidan [2010]. [sent-42, score-0.413]

14 1 The Gaussian Copula A copula function [Sklar, 1959] links marginal distributions to form a multivariate one. [sent-44, score-0.417]

15 A copula function C : [0, 1]n → [0, 1] is a joint distribution Cθ (u1 , . [sent-50, score-0.339]

16 , Un ≤ un ), where θ are the parameters of the copula function. [sent-56, score-0.442]

17 Sklar’s seminal theorem states that for any joint distribution FX (x), there exists a copula function C such that FX (x) = C(FX1 (x1 ), . [sent-61, score-0.339]

18 When the univariate marginals are continuous, C is uniquely deﬁned. [sent-65, score-0.255]

19 Since Ui ≡ Fi is itself a random variable that is always uniformly distributed in [0, 1], any copula function taking any marginal distributions {Ui } as its arguments, deﬁnes a valid joint distribution with marginals {Ui }. [sent-67, score-0.572]

20 Thus, copulas are “distribution generating” functions that allow us to separate the choice of the univariate marginals and that of the dependence structure, encoded in the copula function C. [sent-68, score-0.668]

21 2: The Gaussian copula distribution is deﬁned by: −1 −1 CΣ (u1 , . [sent-71, score-0.339]

22 However, the Gaussian copula can give rise to complex varied distribution and offers great ﬂexibility. [sent-80, score-0.339]

23 As an example, Figure 1 shows two bivariate distributions that are constructed using the Gaussian copula and two different sets of univariate marginals. [sent-81, score-0.548]

24 Generally, any univariate marginal, both parametric and nonparametric can be used. [sent-82, score-0.172]

25 Let ϕΣ (x) denote the multivariate normal density with mean zero and covariance Σ, and let ϕ(x) denote the univariate standard normal density. [sent-83, score-0.205]

26 Using the derivative chain rule and the derivative 2 inverse function theorem, the Gaussian copula density c(u1 , . [sent-84, score-0.417]

27 = −1 ∂Ui i ϕ(Φ (ui )) For a distribution deﬁned by a Gaussian copula FX (x1 , . [sent-103, score-0.339]

28 , Fn (xn )), using ∂Ui /∂Xi = fi , we have fX (x1 , . [sent-109, score-0.184]

29 , ∂Xn i fi (xi ), (2) i −1 where xi ≡ Φ (ui ) ≡ Φ (Fi (xi )). [sent-121, score-0.269]

30 ΘC is a set of local copula functions Ci (ui , upai1 , . [sent-135, score-0.339]

31 In addition, Θf is the set of parameters representing the marginal densities fi (xi ) (and distributions ui ≡ Fi (xi )). [sent-139, score-0.42]

32 , upaiki )fi (xi ) (3) i=1 i When Xi has no parents in G, Rci (·) ≡ 1. [sent-152, score-0.115]

33 Note that Rci (·)fi (xi ) is always a valid conditional density f (xi | pai ), and can be easily computed. [sent-153, score-0.18]

34 In particular, when the copula density c(·) in the numerator has an explicit form, so does Rci (·). [sent-154, score-0.417]

35 , upaiki ) deﬁnes a valid copula so that the univariate marginals of the constructed density are fi (xi ). [sent-159, score-0.951]

36 In this case the CBN model can be viewed as striking a balance between the ﬁxed marginals and the unconstrained maximum likelihood objectives. [sent-162, score-0.128]

37 3 Nonparanormal Belief Propagation As exempliﬁed in Figure 1, the Gaussian copula can give rise to complex multi-modal joint distributions. [sent-164, score-0.339]

38 Yet, as we show in this section, tractable inference in this highly non-Gaussian model is possible, regardless of the form of the univariate marginals. [sent-166, score-0.188]

39 , xn ) be a density parameterized by a Gaussian copula. [sent-173, score-0.144]

40 dxn Rn−k k = fi (xi ) ϕ(˜i ) x i=1 n −1 −1 ϕΣ Φ (F1 (x1 )), . [sent-192, score-0.218]

41 , Φ (Fn (xn )) Changing the integral variables to Ui and using fi = k fX1 ,. [sent-195, score-0.212]

42 , xk ) = fi (xi ) ϕ(˜i ) x i=1 ∂Ui ∂Xi fi (xi ) dxk+1 . [sent-201, score-0.395]

43 ϕ(Φ (Fi (xi ))) i=k+1 −1 so that fi (xi )dxi = dui , we have ϕΣ Φ−1 (u1 ), . [sent-205, score-0.184]

44 −1 −1 ˜ Changing variables once again to xi = Φ (ui ), and using ∂ Xi /∂Ui = ϕ(˜i ) , we have ˜ x k fX1 ,. [sent-212, score-0.113]

45 x ˜ x x Rn−k The integral on the right hand side is now a standard marginalization of a multivariate Gaussian (over xi ’s) and can be carried out in closed form. [sent-225, score-0.128]

46 Letting W = X \ {Z ∪ Y} denote non query or evidence variables, and plugging in the above, we have: fY|Z (y | z) = f (x)dw = f (x)dwdy i∈Y fi (xi ) ϕ(˜i ) x ˜ ϕΣ (˜1 , . [sent-227, score-0.184]

47 , xn ) dwd˜ x ˜ The conditional density is now easy to compute since a ratio of normal distributions is also normal. [sent-234, score-0.144]

48 The ﬁnal answer, of course, does involve fi (xi ). [sent-235, score-0.184]

49 , xn ) = i fi (xi ) ϕ(˜i ) x ϕΣi (˜i , xpai1 , . [sent-243, score-0.25]

50 When the graph is tree structured, this density x is also a copula and its marginals are fi (xi ). [sent-251, score-0.811]

51 , xpaiki ) x ˜ i i Since a ratio of Gaussians is also a Gaussian, the entire density is Gaussian in xi space, and compu˜ tation of any marginal fY (˜ ) is easy. [sent-262, score-0.342]

52 The required marginal in xi space is then recovered using y ˜ fY (y) = fY (˜ ) ˜ y i∈Y fi (xi ) ϕ(˜i ) x (4) which essentially summarizes the detailed derivation of the previous section. [sent-263, score-0.347]

53 2, the marginals may not equal fi (xi ), and the above simpliﬁcation is not applicable. [sent-265, score-0.312]

54 However, for the Gaussian case, it is always possible to estimate the local copulas in a topological order so that the univariate marginals are equal to fi (xi ) (the model in this case is equivalent to the distribution-free continuous Bayesian belief net model [Kurowicka and Cooke, 2005]). [sent-266, score-0.656]

55 1: The complexity of inference in a Gaussian CBN model is the same as that of inference in a multivariate Gaussian model of the same structure. [sent-268, score-0.122]

56 CG ← a valid cluster graph over the following potentials for all nodes i in the graph • ϕΣi (˜i , xpai1 , . [sent-272, score-0.14]

57 , xpaiki ) x ˜ i foreach cluster S in CG bG (˜ S ) ← GaBP belief over cluster S. [sent-278, score-0.336]

58 x foreach cluster S in CG bS (xS ) = bG (˜ S ) x // use black-box GaBP in xi space ˜ // change to xi space fi (xi ) i∈S ϕ(˜i ) x While mathematically this conclusion is quite straightforward, the implications are signiﬁcant. [sent-279, score-0.413]

59 A GCBN model is the only general purpose non-Gaussian continuous graphical model for which exact inference is tractable. [sent-280, score-0.129]

60 (4) includes fi (xi ) terms for all variables that have not been marginalized out. [sent-284, score-0.212]

61 As noted, this is indeed desirable as we would like to preserve the complexity of the density in the marginal computation. [sent-285, score-0.156]

62 A possible alternative is to consider the popular belief propagation algorithm [Pearl, 1988]. [sent-294, score-0.259]

63 In the case of a GCBN model, performing belief propagation may seem difﬁcult since Ψi (xi ) ≡ fi (xi ) can have a complex form. [sent-296, score-0.469]

64 That is, one can perform inference in xi space using standard Gaussian BP ˜ (GaBP) [Weiss and Freeman, 2001], and then perform the needed change of variables. [sent-298, score-0.146]

65 In fact, this is true regardless of the structure of the graph so that loopy GaBP can also be used to perform approximate computations for a general GCBN model in xi space. [sent-299, score-0.159]

66 • Observation 2: Convergence of NPNBP depends only on the covariance matrices Σi that parameterize the local copula and does not depend on the univariate form. [sent-305, score-0.466]

67 Nonparametric BP marginals for the GCBN model learned from the wine quality dataset. [sent-309, score-0.21]

68 Shown are the marginal densities for the ﬁrst four variables. [sent-310, score-0.13]

69 We learned a tree structured GCBN using a standard Chow-Liu approach [Chow and Liu, 1968], and a model with up to two parents for each variable using standard greedy structure search. [sent-312, score-0.15]

70 For the univariate densities, we use a standard Gaussian kernel density estimator (see, for example, [Bowman and Azzalini, 1997]). [sent-314, score-0.205]

71 In this case, since our univariate densities are constructed using Gaussian kernels, there is no approximation in the NBP representation and all approximations are due to message computations. [sent-324, score-0.207]

72 1 Qualitative Assessment We start with a small domain where the qualitative nature of the inferred marginals is easily explored, and consider performance and running time in more substantial domains in the next section. [sent-328, score-0.259]

73 We ﬁrst examine a tree structured GCBN model where our NPNBP method allows us to perform exact marginal computations. [sent-331, score-0.224]

74 Figure 2 compares the ﬁrst four marginals to the ones computed by the NBP method. [sent-332, score-0.128]

75 As can be clearly seen, although the NBP marginals are not nonsensical, they are far from accurate (results for the other marginals in the domain are similar). [sent-333, score-0.281]

76 Figure 3 demonstrates the quality of the bivariate marginals inferred by our NPNBP method relative to the ones of a linear Gaussian BN model where inference can also be carried out efﬁciently. [sent-340, score-0.371]

77 In contrast, the bivariate marginals computed by our algorithm (right panel) demonstrate the power of working with a copula-based construction and an effective inference procedure: in both cases the inferred marginals capture the non-Gaussian distributions quite accurately. [sent-343, score-0.431]

78 Total Sulfur (a) true samples (b) optimal Gaussian (c) CBN marginal Figure 3: The bivariate density for two pairs of variables in a tree structured GCBN model learned from the wine quality dataset. [sent-347, score-0.451]

79 (a) empirical samples; (b) maximum likelihood Gaussian density; (c) exact GCBN marginal computed using our NPNBP algorithm. [sent-348, score-0.121]

80 In this setting, the bivariate marginal computed by our algorithm (d) is approximate and we also compare to the exact marginal (c). [sent-350, score-0.281]

81 NPNBP dampens some of this accuracy and results in marginal densities that have the correct overall structure but with a reduced variance. [sent-352, score-0.13]

82 Nevertheless, the approximate result of NPNBP is clearly better than the exact Gaussian model, which assigns very low probability to regions of high density (along the main vertical axis of the density). [sent-354, score-0.121]

83 For each domain we learn a tree structured GCBN, and justify the need for the expressive copula-based model by reporting its average generalization advantage in terms of log-loss/instance over a standard linear Gaussian model. [sent-362, score-0.128]

84 We justify the use of NPNBP for performing inference by comparing the running time of NPNBP to exact computations carried out using matrix inversion. [sent-363, score-0.173]

85 Density (a) true samples (b) optimal Gaussian (c) exact CBN marginal (d) inferred marginal Figure 4: The bivariate density for a pair of variables in a non-tree GCBN model learned from the wine quality dataset. [sent-379, score-0.501]

86 (a) empirical samples; (b) maximum likelihood Gaussian density; (c) exact CBN marginal; (d) marginal density computed by our NPNBP algorithm. [sent-380, score-0.199]

87 (right) speedup relative to matrix inversion for a tree structured GCBN model. [sent-383, score-0.166]

88 As discussed, a GCBN model is itself tractable in that inference can be carried out by ﬁrst constructing the inverse covariance matrix over all variables and then inverting it so as to facilitate marginalization. [sent-389, score-0.132]

89 Figure 5(right) shows the speedup of NPNBP relative to inference based on matrix inversion for the different domains. [sent-391, score-0.124]

90 Although NPNBP is somewhat slower for the small domains (in which inference is carried out in less than a second), the speedup of NPNBP reaches an order of magnitude for the larger gene expression domain. [sent-392, score-0.221]

91 5 Summary We presented Nonparanormal Belief Propagation (NPNBP), a propagation-based algorithm for performing highly efﬁcient inference in a powerful class of graphical models that are based on the Gaussian copula. [sent-395, score-0.112]

92 To our knowledge, ours is the ﬁrst inference method for an expressive continuous non-Gaussian representation that, like ordinary GaBP, is both highly efﬁcient and provably correct for tree structured models. [sent-396, score-0.164]

93 Appealingly, the efﬁciency and convergence properties of our method do not depend on the choice of univariate marginals, even when a nonparametric representation is used. [sent-397, score-0.172]

94 The Gaussian copula is a powerful model widely used to capture complex phenomenon in ﬁelds ranging from mainstream economics (e. [sent-398, score-0.339]

95 Recent probabilistic graphical models that build on the Gaussian copula open the door for new high-dimensional non-Gaussian applications [Kirshner, 2007, Liu et al. [sent-402, score-0.364]

96 On the uniqueness of loopy belief propagation ﬁxed points. [sent-456, score-0.305]

97 Turbo decoding as an instance of pearl’s belief propagation algorithm. [sent-504, score-0.259]

98 Loopy belief propagation for approximate inference: An empirical study. [sent-521, score-0.259]

99 An analysis of belief propagation on the turbo decoding graph with gaussian densities. [sent-541, score-0.418]

100 Correctness of belief propagation in gaussian graphical models of arbitrary topology. [sent-577, score-0.387]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('npnbp', 0.44), ('gcbn', 0.389), ('copula', 0.339), ('gabp', 0.254), ('cbn', 0.22), ('fi', 0.184), ('belief', 0.143), ('elidan', 0.134), ('fx', 0.131), ('bp', 0.129), ('marginals', 0.128), ('univariate', 0.127), ('nbp', 0.119), ('propagation', 0.116), ('ui', 0.106), ('un', 0.103), ('gaussian', 0.103), ('rci', 0.101), ('xpaiki', 0.101), ('freeman', 0.086), ('xi', 0.085), ('bivariate', 0.082), ('nonparanormal', 0.079), ('density', 0.078), ('marginal', 0.078), ('pai', 0.075), ('copulas', 0.074), ('weiss', 0.068), ('upaiki', 0.068), ('xn', 0.066), ('inference', 0.061), ('fy', 0.06), ('wine', 0.057), ('pearl', 0.055), ('tree', 0.054), ('densities', 0.052), ('cbns', 0.051), ('ihler', 0.049), ('structured', 0.049), ('parents', 0.047), ('loopy', 0.046), ('gene', 0.045), ('nonparametric', 0.045), ('domains', 0.045), ('carried', 0.043), ('exact', 0.043), ('sudderth', 0.042), ('appealingly', 0.041), ('crime', 0.039), ('bickson', 0.037), ('inversion', 0.036), ('bowman', 0.034), ('cario', 0.034), ('cortez', 0.034), ('dxk', 0.034), ('dxn', 0.034), ('embrechts', 0.034), ('marion', 0.034), ('nondescendantsi', 0.034), ('ood', 0.034), ('rusmevichientong', 0.034), ('bn', 0.033), ('hebrew', 0.033), ('cluster', 0.033), ('inferred', 0.032), ('cg', 0.031), ('globerson', 0.031), ('dxi', 0.03), ('malioutov', 0.03), ('wiegerinck', 0.03), ('isard', 0.03), ('koller', 0.029), ('substantial', 0.029), ('variables', 0.028), ('graph', 0.028), ('message', 0.028), ('turbo', 0.028), ('mceliece', 0.028), ('sklar', 0.028), ('kurowicka', 0.028), ('speedup', 0.027), ('valid', 0.027), ('xk', 0.027), ('performing', 0.026), ('heskes', 0.026), ('mooij', 0.026), ('foreach', 0.026), ('domain', 0.025), ('graphical', 0.025), ('quality', 0.025), ('fn', 0.025), ('nodes', 0.024), ('resulted', 0.024), ('bg', 0.024), ('yedidia', 0.024), ('qualitatively', 0.023), ('chow', 0.023), ('ows', 0.023), ('jerusalem', 0.023), ('kde', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999976 248 nips-2012-Nonparanormal Belief Propagation (NPNBP)

Author: Gal Elidan, Cobi Cario

2 0.25893128 211 nips-2012-Meta-Gaussian Information Bottleneck

Author: Melanie Rey, Volker Roth

Abstract: We present a reformulation of the information bottleneck (IB) problem in terms of copula, using the equivalence between mutual information and negative copula entropy. Focusing on the Gaussian copula we extend the analytical IB solution available for the multivariate Gaussian case to distributions with a Gaussian dependence structure but arbitrary marginal densities, also called meta-Gaussian distributions. This opens new possibles applications of IB to continuous data and provides a solution more robust to outliers. 1

3 0.11284836 145 nips-2012-Gradient Weights help Nonparametric Regressors

Author: Samory Kpotufe, Abdeslam Boularias

Abstract: In regression problems over Rd , the unknown function f often varies more in some coordinates than in others. We show that weighting each coordinate i with the estimated norm of the ith derivative of f is an efﬁcient way to signiﬁcantly improve the performance of distance-based regressors, e.g. kernel and k-NN regressors. We propose a simple estimator of these derivative norms and prove its consistency. Moreover, the proposed estimator is efﬁciently learned online. 1

4 0.1122321 335 nips-2012-The Bethe Partition Function of Log-supermodular Graphical Models

Author: Nicholas Ruozzi

Abstract: Sudderth, Wainwright, and Willsky conjectured that the Bethe approximation corresponding to any ﬁxed point of the belief propagation algorithm over an attractive, pairwise binary graphical model provides a lower bound on the true partition function. In this work, we resolve this conjecture in the afﬁrmative by demonstrating that, for any graphical model with binary variables whose potential functions (not necessarily pairwise) are all log-supermodular, the Bethe partition function always lower bounds the true partition function. The proof of this result follows from a new variant of the “four functions” theorem that may be of independent interest. 1

5 0.099334471 96 nips-2012-Density Propagation and Improved Bounds on the Partition Function

Author: Stefano Ermon, Ashish Sabharwal, Bart Selman, Carla P. Gomes

Abstract: Given a probabilistic graphical model, its density of states is a distribution that, for any likelihood value, gives the number of conﬁgurations with that probability. We introduce a novel message-passing algorithm called Density Propagation (DP) for estimating this distribution. We show that DP is exact for tree-structured graphical models and is, in general, a strict generalization of both sum-product and max-product algorithms. Further, we use density of states and tree decomposition to introduce a new family of upper and lower bounds on the partition function. For any tree decomposition, the new upper bound based on ﬁner-grained density of state information is provably at least as tight as previously known bounds based on convexity of the log-partition function, and strictly stronger if a general condition holds. We conclude with empirical evidence of improvement over convex relaxations and mean-ﬁeld based bounds. 1

6 0.090259075 317 nips-2012-Smooth-projected Neighborhood Pursuit for High-dimensional Nonparanormal Graph Estimation

7 0.083345443 204 nips-2012-MAP Inference in Chains using Column Generation

8 0.080334961 213 nips-2012-Minimization of Continuous Bethe Approximations: A Positive Variation

9 0.067003064 105 nips-2012-Dynamic Pruning of Factor Graphs for Maximum Marginal Prediction

10 0.066006824 326 nips-2012-Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses

11 0.065629594 37 nips-2012-Affine Independent Variational Inference

12 0.06185668 84 nips-2012-Convergence Rate Analysis of MAP Coordinate Minimization Algorithms

13 0.05827919 82 nips-2012-Continuous Relaxations for Discrete Hamiltonian Monte Carlo

14 0.056783356 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs

15 0.056323137 287 nips-2012-Random function priors for exchangeable arrays with applications to graphs and relational data

16 0.055734571 180 nips-2012-Learning Mixtures of Tree Graphical Models

17 0.055327721 147 nips-2012-Graphical Models via Generalized Linear Models

18 0.055287205 351 nips-2012-Transelliptical Component Analysis

19 0.054269779 186 nips-2012-Learning as MAP Inference in Discrete Graphical Models

20 0.053462453 359 nips-2012-Variational Inference for Crowdsourcing

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.151), (1, 0.039), (2, 0.043), (3, -0.046), (4, -0.083), (5, -0.015), (6, 0.02), (7, -0.065), (8, -0.077), (9, 0.009), (10, -0.096), (11, -0.023), (12, 0.038), (13, 0.01), (14, -0.073), (15, -0.063), (16, 0.058), (17, -0.085), (18, -0.026), (19, 0.096), (20, 0.05), (21, -0.109), (22, -0.036), (23, 0.021), (24, -0.03), (25, 0.032), (26, -0.026), (27, -0.042), (28, 0.066), (29, 0.071), (30, 0.004), (31, -0.04), (32, 0.017), (33, 0.053), (34, -0.05), (35, 0.074), (36, -0.076), (37, -0.02), (38, -0.099), (39, 0.04), (40, 0.016), (41, 0.012), (42, 0.023), (43, -0.027), (44, -0.065), (45, 0.146), (46, -0.098), (47, 0.124), (48, -0.074), (49, -0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.91285414 248 nips-2012-Nonparanormal Belief Propagation (NPNBP)

Author: Gal Elidan, Cobi Cario

2 0.72190058 211 nips-2012-Meta-Gaussian Information Bottleneck

Author: Melanie Rey, Volker Roth

3 0.5911094 96 nips-2012-Density Propagation and Improved Bounds on the Partition Function

Author: Stefano Ermon, Ashish Sabharwal, Bart Selman, Carla P. Gomes

4 0.5799399 82 nips-2012-Continuous Relaxations for Discrete Hamiltonian Monte Carlo

Author: Yichuan Zhang, Zoubin Ghahramani, Amos J. Storkey, Charles A. Sutton

Abstract: Continuous relaxations play an important role in discrete optimization, but have not seen much use in approximate probabilistic inference. Here we show that a general form of the Gaussian Integral Trick makes it possible to transform a wide class of discrete variable undirected models into fully continuous systems. The continuous representation allows the use of gradient-based Hamiltonian Monte Carlo for inference, results in new ways of estimating normalization constants (partition functions), and in general opens up a number of new avenues for inference in difﬁcult discrete systems. We demonstrate some of these continuous relaxation inference algorithms on a number of illustrative problems. 1

5 0.57109785 335 nips-2012-The Bethe Partition Function of Log-supermodular Graphical Models

Author: Nicholas Ruozzi

6 0.52148235 145 nips-2012-Gradient Weights help Nonparametric Regressors

7 0.5209381 352 nips-2012-Transelliptical Graphical Models

8 0.48946056 105 nips-2012-Dynamic Pruning of Factor Graphs for Maximum Marginal Prediction

9 0.47687033 317 nips-2012-Smooth-projected Neighborhood Pursuit for High-dimensional Nonparanormal Graph Estimation

10 0.45608675 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs

11 0.45323256 213 nips-2012-Minimization of Continuous Bethe Approximations: A Positive Variation

12 0.44771272 351 nips-2012-Transelliptical Component Analysis

13 0.44169119 204 nips-2012-MAP Inference in Chains using Column Generation

14 0.43306217 359 nips-2012-Variational Inference for Crowdsourcing

15 0.42250237 232 nips-2012-Multiplicative Forests for Continuous-Time Processes

16 0.41877738 180 nips-2012-Learning Mixtures of Tree Graphical Models

17 0.41835144 349 nips-2012-Training sparse natural image models with a fast Gibbs sampler of an extended state space

18 0.41452467 326 nips-2012-Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses

19 0.41223094 147 nips-2012-Graphical Models via Generalized Linear Models

20 0.40796933 206 nips-2012-Majorization for CRFs and Latent Likelihoods

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.032), (21, 0.014), (38, 0.092), (39, 0.418), (42, 0.017), (54, 0.038), (55, 0.036), (74, 0.036), (76, 0.107), (80, 0.096), (92, 0.033)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.75496918 248 nips-2012-Nonparanormal Belief Propagation (NPNBP)

Author: Gal Elidan, Cobi Cario

2 0.7518155 351 nips-2012-Transelliptical Component Analysis

Author: Fang Han, Han Liu

Abstract: We propose a high dimensional semiparametric scale-invariant principle component analysis, named TCA, by utilize the natural connection between the elliptical distribution family and the principal component analysis. Elliptical distribution family includes many well-known multivariate distributions like multivariate Gaussian, t and logistic and it is extended to the meta-elliptical by Fang et.al (2002) using the copula techniques. In this paper we extend the meta-elliptical distribution family to a even larger family, called transelliptical. We prove that TCA can obtain a near-optimal s log d/n estimation consistency rate in recovering the leading eigenvector of the latent generalized correlation matrix under the transelliptical distribution family, even if the distributions are very heavy-tailed, have inﬁnite second moments, do not have densities and possess arbitrarily continuous marginal distributions. A feature selection result with explicit rate is also provided. TCA is further implemented in both numerical simulations and largescale stock data to illustrate its empirical usefulness. Both theories and experiments conﬁrm that TCA can achieve model ﬂexibility, estimation accuracy and robustness at almost no cost. 1

3 0.72460604 106 nips-2012-Dynamical And-Or Graph Learning for Object Shape Modeling and Detection

Author: Xiaolong Wang, Liang Lin

Abstract: This paper studies a novel discriminative part-based model to represent and recognize object shapes with an “And-Or graph”. We deﬁne this model consisting of three layers: the leaf-nodes with collaborative edges for localizing local parts, the or-nodes specifying the switch of leaf-nodes, and the root-node encoding the global veriﬁcation. A discriminative learning algorithm, extended from the CCCP [23], is proposed to train the model in a dynamical manner: the model structure (e.g., the conﬁguration of the leaf-nodes associated with the or-nodes) is automatically determined with optimizing the multi-layer parameters during the iteration. The advantages of our method are two-fold. (i) The And-Or graph model enables us to handle well large intra-class variance and background clutters for object shape detection from images. (ii) The proposed learning algorithm is able to obtain the And-Or graph representation without requiring elaborate supervision and initialization. We validate the proposed method on several challenging databases (e.g., INRIA-Horse, ETHZ-Shape, and UIUC-People), and it outperforms the state-of-the-arts approaches. 1

4 0.71028149 166 nips-2012-Joint Modeling of a Matrix with Associated Text via Latent Binary Features

Author: Xianxing Zhang, Lawrence Carin

Abstract: A new methodology is developed for joint analysis of a matrix and accompanying documents, with the documents associated with the matrix rows/columns. The documents are modeled with a focused topic model, inferring interpretable latent binary features for each document. A new matrix decomposition is developed, with latent binary features associated with the rows/columns, and with imposition of a low-rank constraint. The matrix decomposition and topic model are coupled by sharing the latent binary feature vectors associated with each. The model is applied to roll-call data, with the associated documents deﬁned by the legislation. Advantages of the proposed model are demonstrated for prediction of votes on a new piece of legislation, based only on the observed text of legislation. The coupling of the text and legislation is also shown to yield insight into the properties of the matrix decomposition for roll-call data. 1

5 0.65813273 249 nips-2012-Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison

Author: Tianbao Yang, Yu-feng Li, Mehrdad Mahdavi, Rong Jin, Zhi-Hua Zhou

Abstract: Both random Fourier features and the Nystr¨ m method have been successfully o applied to efﬁcient kernel learning. In this work, we investigate the fundamental difference between these two approaches, and how the difference could affect their generalization performances. Unlike approaches based on random Fourier features where the basis functions (i.e., cosine and sine functions) are sampled from a distribution independent from the training data, basis functions used by the Nystr¨ m method are randomly sampled from the training examples and are o therefore data dependent. By exploring this difference, we show that when there is a large gap in the eigen-spectrum of the kernel matrix, approaches based on the Nystr¨ m method can yield impressively better generalization error bound than o random Fourier features based approach. We empirically verify our theoretical ﬁndings on a wide range of large data sets. 1

6 0.64370024 323 nips-2012-Statistical Consistency of Ranking Methods in A Rank-Differentiable Probability Space

7 0.61105418 352 nips-2012-Transelliptical Graphical Models

8 0.51152617 310 nips-2012-Semiparametric Principal Component Analysis

9 0.48910779 154 nips-2012-How They Vote: Issue-Adjusted Models of Legislative Behavior

10 0.47014606 47 nips-2012-Augment-and-Conquer Negative Binomial Processes

11 0.45932153 315 nips-2012-Slice sampling normalized kernel-weighted completely random measure mixture models

12 0.45792308 216 nips-2012-Mirror Descent Meets Fixed Share (and feels no regret)

13 0.44317839 163 nips-2012-Isotropic Hashing

14 0.4386546 354 nips-2012-Truly Nonparametric Online Variational Inference for Hierarchical Dirichlet Processes

15 0.43851718 363 nips-2012-Wavelet based multi-scale shape features on arbitrary surfaces for cortical thickness discrimination

16 0.43799299 234 nips-2012-Multiresolution analysis on the symmetric group

17 0.43683705 211 nips-2012-Meta-Gaussian Information Bottleneck

18 0.43391511 218 nips-2012-Mixing Properties of Conditional Markov Chains with Unbounded Feature Functions

19 0.43382648 309 nips-2012-Semi-supervised Eigenvectors for Locally-biased Learning

20 0.43299213 246 nips-2012-Nonparametric Max-Margin Matrix Factorization for Collaborative Prediction