nips nips2004 nips2004-63 knowledge-graph by maker-knowledge-mining

63 nips-2004-Expectation Consistent Free Energies for Approximate Inference

Source: pdf

Author: Manfred Opper, Ole Winther

Abstract: We propose a novel a framework for deriving approximations for intractable probabilistic models. This framework is based on a free energy (negative log marginal likelihood) and can be seen as a generalization of adaptive TAP [1, 2, 3] and expectation propagation (EP) [4, 5]. The free energy is constructed from two approximating distributions which encode different aspects of the intractable model such a single node constraints and couplings and are by construction consistent on a chosen set of moments. We test the framework on a difﬁcult benchmark problem with binary variables on fully connected graphs and 2D grid graphs. We ﬁnd good performance using sets of moments which either specify factorized nodes or a spanning tree on the nodes (structured approximation). Surprisingly, the Bethe approximation gives very inferior results even on grids. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 dk Abstract We propose a novel a framework for deriving approximations for intractable probabilistic models. [sent-6, score-0.354]

2 This framework is based on a free energy (negative log marginal likelihood) and can be seen as a generalization of adaptive TAP [1, 2, 3] and expectation propagation (EP) [4, 5]. [sent-7, score-0.572]

3 The free energy is constructed from two approximating distributions which encode different aspects of the intractable model such a single node constraints and couplings and are by construction consistent on a chosen set of moments. [sent-8, score-0.582]

4 We test the framework on a difﬁcult benchmark problem with binary variables on fully connected graphs and 2D grid graphs. [sent-9, score-0.252]

5 We ﬁnd good performance using sets of moments which either specify factorized nodes or a spanning tree on the nodes (structured approximation). [sent-10, score-0.368]

6 Surprisingly, the Bethe approximation gives very inferior results even on grids. [sent-11, score-0.161]

7 1 Introduction The development of tractable approximations for the statistical inference with probabilistic data models is of central importance in order to develop their full potential. [sent-12, score-0.471]

8 The most prominent and widely developed [6] approximation technique is the so called Variational Approximation (VA) in which the true intractable probability distribution is approximated by the closest one in a tractable family. [sent-13, score-0.436]

9 The most important tractable families of distributions are multivariate Gaussians and distributions which factorize in all or in certain groups of variables [7]. [sent-14, score-0.498]

10 While factorizing distributions neglect correlations, multivariate Gaussians allow to retain a signiﬁcant amount of dependencies but are restricted to continuous random variables which have the entire real space as their natural domain (otherwise KL divergences becomes inﬁnite). [sent-16, score-0.505]

11 More recently a variety of non variational approximations have been developed which can be understood from the idea of global consistency between local approximations. [sent-17, score-0.464]

12 , in the Bethe–Kikuchi approach [8] the local neighborhood of each variable in a graphical model is implicitly approximated by a tree-like structure. [sent-20, score-0.064]

13 Consistency is achieved by the matching of marginal distributions at the connecting edges of the graph. [sent-21, score-0.054]

14 Thomas Minka’s Expectation Propagation (EP) framework seems to provide a general framework for developing and unifying such consistency approximations [4, 5]. [sent-22, score-0.36]

15 Although the new frameworks have led to a variety of promising applications, often outperforming VA schemes, the unsatisfactory division between the treatment of constrained and unconstrained, continuous random variables seems to persist. [sent-23, score-0.254]

16 In this paper we propose an alternative approach which we call the expectation consistent (EC) approximation which is not plagued by this problem. [sent-24, score-0.276]

17 We require consistency between two complimentary global approximations (say, a factorizing & a Gaussian one) to the same probabilistic model which may have different support. [sent-25, score-0.42]

18 2 Approximative inference We consider the problem of computing expectations, i. [sent-27, score-0.115]

19 certain sums or integrals involving a probability distribution with density p(x) = 1 f (x) , Z (1) for a vector of random variables x = (x1 , x2 , . [sent-29, score-0.279]

20 We assume that the necessary exact operations are intractable, where the intractability arises either because the necessary sums are over a too large number of variables or because multivariate integrals cannot be evaluated exactly. [sent-33, score-0.43]

21 In a typical scenario, f (x) is expressed as a product of two functions f (x) = f1 (x)f2 (x) (2) with f1,2 (x) ≥ 0, where f1 is “simple” enough to allow for tractable computations. [sent-34, score-0.196]

22 The idea of many approximate inference methods is to approximate the “complicated” part f2 (x) by replacing it with a “simpler” function, say of some exponential form K exp λT g(x) ≡ exp j=1 λj gj (x) . [sent-35, score-0.235]

23 The vector of functions g is chosen in such a way that the desired sums or integrals can be calculated in an efﬁcient way and the parameters λ are adjusted to optimize certain criteria. [sent-36, score-0.216]

24 Hence, the word tractability should always be understood as relative to some approximating set of functions g. [sent-37, score-0.147]

25 Our novel framework of approximation will be restricted to problems, where both parts f 1 and f2 can be considered as tractable relative to some suitable g, and the intractability of the density p arises from forming their product. [sent-38, score-0.507]

26 (22) where Gq (m, M, 0) depend upon the approximation we are using. [sent-44, score-0.096]

27 For the factorized model we use the free energy eq. [sent-45, score-0.342]

28 (12) and for the structured model we assume a single tractable potential ψ(x) in eq. [sent-46, score-0.286]

29 (3) which contains all couplings on a spanning tree. [sent-47, score-0.19]

30 The spanning tree is deﬁned by the following simple heuristic: choose as next pair of nodes to link, the (so far unlinked) pair with strongest absolute coupling |Jij | that will not cause a loop in the graph. [sent-50, score-0.272]

31 The Bethe approximation always give inferior results compared to EC (note that only loopy BP convergent problem instances were used to calculate the error [12]). [sent-52, score-0.32]

32 This might be a bit surprising for the sparsely connected grids. [sent-53, score-0.085]

33 This indicates that loopy BP and too a lesser degree extensions building upon BP [5] are only to be applied to really sparse graphs and/or weakly coupled nodes, where the error induced by not using a properly normalized distribution can be expected to be small. [sent-54, score-0.183]

34 We also speculate that a structured variational approximation, using the same heuristics as described above to construct the spanning tree, in many cases will be superior to the Bethe approximation as also observed by Ref. [sent-55, score-0.498]

35 LD is a robust method which seems to be limited in it’s achievable precision. [sent-57, score-0.039]

36 EC structured is uniformly superior to all other approaches. [sent-58, score-0.129]

37 Additional simulations (not included in the paper) also indicate that EC give much improved estimates of free energies and two-node marginals when compared to the Bethe- and Kikuchi-approximation. [sent-59, score-0.41]

38 8 Conclusion and outlook We have introduced a novel method for approximate inference which tries to overcome certain limitations of single approximating distributions by achieving consistency for two of these on the same problem. [sent-60, score-0.53]

39 While we have demonstrated its accuracy in this paper only for a model with binary elements, it can also be applied to models with continuous random variables or hybrid models with both discrete and continuous variables. [sent-61, score-0.161]

40 We expect that our method becomes most powerful when certain tractable substructures of variables with strong dependencies can be identiﬁed in a model. [sent-62, score-0.424]

41 Our approach would then allow to deal well with the weaker dependencies between the groups. [sent-63, score-0.066]

42 A generalization of our method to treat graphical models beyond pair-wise interaction is obtained by iterating the approximation. [sent-64, score-0.064]

43 This is useful in cases, where an initial three term approximation G EC = Table 1: The average one-norm error on marginals for the Wainwright-Jordan set-up. [sent-65, score-0.19]

44 0024 Gq + Gr − Gs still contains non-tractable component free energies G. [sent-126, score-0.316]

45 Winther, “Tractable approximations for probabilistic models: The adaptive Thouless-Anderson-Palmer mean ﬁeld approach,” Phys. [sent-134, score-0.25]

46 Winther, “Adaptive and self-averaging Thouless-Anderson-Palmer mean ﬁeld theory for probabilistic modeling,” Phys. [sent-142, score-0.087]

47 Minka, “Expectation propagation for approximate Bayesian inference,” in UAI 2001, 2001, pp. [sent-149, score-0.191]

48 Qi, “Tree-structured approximations by expectation propagation,” in NIPS 16, S. [sent-153, score-0.21]

49 Bishop, David Spiegelhalter, and John Winn, “Vibes: A variational inference engine for bayesian networks,” in Advances in Neural Information Processing Systems 15, S. [sent-159, score-0.23]

50 Attias, “A variational Bayesian framework for graphical models,” in Advances in Neural Information Processing Systems 12, T. [sent-167, score-0.229]

51 Weiss, “Generalized belief propagation,” in Advances in Neural Information Processing Systems 13, T. [sent-176, score-0.053]

52 Yuille, “CCCP algorithms to minimize the Bethe and Kikuchi free energies: convergent alternatives to belief propagation,” Neural Comput. [sent-186, score-0.27]

53 Kappen, “Approximate inference and constrained optimization,” in UAI-03, San Francisco, CA, 2003, pp. [sent-194, score-0.115]

54 Jordan, “Semideﬁnite methods for approximate inference on graphs with cycles,” Tech. [sent-203, score-0.228]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('ec', 0.39), ('bethe', 0.279), ('winther', 0.214), ('tractable', 0.196), ('repulsive', 0.186), ('energies', 0.17), ('opper', 0.158), ('free', 0.146), ('ld', 0.142), ('propagation', 0.131), ('approximations', 0.115), ('variational', 0.115), ('inference', 0.115), ('bp', 0.114), ('minka', 0.112), ('spanning', 0.111), ('factorizing', 0.107), ('kikuchi', 0.107), ('consistency', 0.106), ('intractable', 0.103), ('energy', 0.102), ('attractive', 0.1), ('sp', 0.098), ('approximation', 0.096), ('expectation', 0.095), ('factorized', 0.094), ('integrals', 0.094), ('marginals', 0.094), ('mixed', 0.094), ('structured', 0.09), ('loopy', 0.088), ('intractability', 0.085), ('tap', 0.085), ('gq', 0.085), ('couplings', 0.079), ('multivariate', 0.079), ('va', 0.075), ('ep', 0.075), ('convergent', 0.071), ('sums', 0.07), ('denmark', 0.068), ('dependencies', 0.066), ('inferior', 0.065), ('graphical', 0.064), ('variables', 0.063), ('leen', 0.063), ('division', 0.061), ('approximating', 0.06), ('approximate', 0.06), ('nodes', 0.057), ('coupling', 0.055), ('distributions', 0.054), ('graphs', 0.053), ('belief', 0.053), ('certain', 0.052), ('framework', 0.05), ('tree', 0.049), ('continuous', 0.049), ('adaptive', 0.048), ('eld', 0.047), ('vandenberghe', 0.047), ('substructures', 0.047), ('attias', 0.047), ('plagued', 0.047), ('complimentary', 0.047), ('gs', 0.047), ('kingdom', 0.047), ('neglect', 0.047), ('southampton', 0.047), ('speculate', 0.047), ('spiegelhalter', 0.047), ('vibes', 0.047), ('winn', 0.047), ('probabilistic', 0.045), ('understood', 0.045), ('connected', 0.043), ('grid', 0.043), ('mean', 0.042), ('lyngby', 0.042), ('aka', 0.042), ('manfred', 0.042), ('sparsely', 0.042), ('outlook', 0.042), ('heskes', 0.042), ('isis', 0.042), ('lesser', 0.042), ('tractability', 0.042), ('variety', 0.042), ('developed', 0.041), ('novel', 0.041), ('gaussians', 0.041), ('thrun', 0.04), ('wainwright', 0.04), ('kappen', 0.04), ('electronics', 0.04), ('divergences', 0.04), ('superior', 0.039), ('seems', 0.039), ('arises', 0.039), ('consistent', 0.038)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999976 63 nips-2004-Expectation Consistent Free Energies for Approximate Inference

Author: Manfred Opper, Ole Winther

2 0.22323927 203 nips-2004-Validity Estimates for Loopy Belief Propagation on Binary Real-world Networks

Author: Joris M. Mooij, Hilbert J. Kappen

Abstract: We introduce a computationally efﬁcient method to estimate the validity of the BP method as a function of graph topology, the connectivity strength, frustration and network size. We present numerical results that demonstrate the correctness of our estimates for the uniform random model and for a real-world network (“C. Elegans”). Although the method is restricted to pair-wise interactions, no local evidence (zero “biases”) and binary variables, we believe that its predictions correctly capture the limitations of BP for inference and MAP estimation on arbitrary graphical models. Using this approach, we ﬁnd that BP always performs better than MF. Especially for large networks with broad degree distributions (such as scale-free networks) BP turns out to signiﬁcantly outperform MF. 1

3 0.13451242 116 nips-2004-Message Errors in Belief Propagation

Author: Alexander T. Ihler, John W. Fisher, Alan S. Willsky

Abstract: Belief propagation (BP) is an increasingly popular method of performing approximate inference on arbitrary graphical models. At times, even further approximations are required, whether from quantization or other simpliﬁed message representations or from stochastic approximation methods. Introducing such errors into the BP message computations has the potential to adversely affect the solution obtained. We analyze this effect with respect to a particular measure of message error, and show bounds on the accumulation of errors in the system. This leads both to convergence conditions and error bounds in traditional and approximate BP message passing. 1

4 0.076949961 198 nips-2004-Unsupervised Variational Bayesian Learning of Nonlinear Models

Author: Antti Honkela, Harri Valpola

Abstract: In this paper we present a framework for using multi-layer perceptron (MLP) networks in nonlinear generative models trained by variational Bayesian learning. The nonlinearity is handled by linearizing it using a Gauss–Hermite quadrature at the hidden neurons. This yields an accurate approximation for cases of large posterior variance. The method can be used to derive nonlinear counterparts for linear algorithms such as factor analysis, independent component/factor analysis and state-space models. This is demonstrated with a nonlinear factor analysis experiment in which even 20 sources can be estimated from a real world speech data set. 1

5 0.073614024 44 nips-2004-Conditional Random Fields for Object Recognition

Author: Ariadna Quattoni, Michael Collins, Trevor Darrell

Abstract: We present a discriminative part-based approach for the recognition of object classes from unsegmented cluttered scenes. Objects are modeled as ﬂexible constellations of parts conditioned on local observations found by an interest operator. For each object class the probability of a given assignment of parts to local features is modeled by a Conditional Random Field (CRF). We propose an extension of the CRF framework that incorporates hidden variables and combines class conditional CRFs into a uniﬁed framework for part-based object recognition. The parameters of the CRF are estimated in a maximum likelihood framework and recognition proceeds by ﬁnding the most likely class under our model. The main advantage of the proposed CRF framework is that it allows us to relax the assumption of conditional independence of the observed data (i.e. local features) often used in generative approaches, an assumption that might be too restrictive for a considerable number of object classes.

6 0.073128261 67 nips-2004-Exponentiated Gradient Algorithms for Large-margin Structured Classification

7 0.071406111 41 nips-2004-Comparing Beliefs, Surveys, and Random Walks

8 0.068851694 55 nips-2004-Distributed Occlusion Reasoning for Tracking with Nonparametric Belief Propagation

9 0.065483198 76 nips-2004-Hierarchical Bayesian Inference in Networks of Spiking Neurons

10 0.059145052 204 nips-2004-Variational Minimax Estimation of Discrete Distributions under KL Loss

11 0.058381133 105 nips-2004-Log-concavity Results on Gaussian Process Methods for Supervised and Unsupervised Learning

12 0.057178788 122 nips-2004-Modelling Uncertainty in the Game of Go

13 0.054597393 98 nips-2004-Learning Gaussian Process Kernels via Hierarchical Bayes

14 0.05223757 54 nips-2004-Distributed Information Regularization on Graphs

15 0.051941738 191 nips-2004-The Variational Ising Classifier (VIC) Algorithm for Coherently Contaminated Data

16 0.051501609 163 nips-2004-Semi-parametric Exponential Family PCA

17 0.051497057 49 nips-2004-Density Level Detection is Classification

18 0.051467605 62 nips-2004-Euclidean Embedding of Co-Occurrence Data

19 0.050407067 133 nips-2004-Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

20 0.049866855 73 nips-2004-Generative Affine Localisation and Tracking

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.173), (1, 0.004), (2, -0.005), (3, -0.027), (4, 0.037), (5, 0.01), (6, -0.009), (7, 0.12), (8, -0.086), (9, -0.27), (10, 0.127), (11, -0.135), (12, 0.154), (13, 0.031), (14, 0.057), (15, -0.069), (16, 0.058), (17, 0.103), (18, 0.118), (19, 0.137), (20, 0.045), (21, -0.059), (22, 0.023), (23, 0.031), (24, 0.03), (25, -0.048), (26, -0.021), (27, 0.03), (28, -0.013), (29, -0.098), (30, -0.004), (31, -0.014), (32, -0.027), (33, 0.137), (34, 0.002), (35, -0.158), (36, 0.003), (37, 0.016), (38, 0.032), (39, 0.065), (40, 0.015), (41, -0.047), (42, 0.058), (43, 0.048), (44, 0.019), (45, -0.11), (46, 0.004), (47, -0.069), (48, -0.047), (49, -0.006)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96044624 63 nips-2004-Expectation Consistent Free Energies for Approximate Inference

Author: Manfred Opper, Ole Winther

2 0.87531984 203 nips-2004-Validity Estimates for Loopy Belief Propagation on Binary Real-world Networks

Author: Joris M. Mooij, Hilbert J. Kappen

3 0.75688076 116 nips-2004-Message Errors in Belief Propagation

Author: Alexander T. Ihler, John W. Fisher, Alan S. Willsky

4 0.62853289 41 nips-2004-Comparing Beliefs, Surveys, and Random Walks

Author: Erik Aurell, Uri Gordon, Scott Kirkpatrick

Abstract: Survey propagation is a powerful technique from statistical physics that has been applied to solve the 3-SAT problem both in principle and in practice. We give, using only probability arguments, a common derivation of survey propagation, belief propagation and several interesting hybrid methods. We then present numerical experiments which use WSAT (a widely used random-walk based SAT solver) to quantify the complexity of the 3-SAT formulae as a function of their parameters, both as randomly generated and after simpli£cation, guided by survey propagation. Some properties of WSAT which have not previously been reported make it an ideal tool for this purpose – its mean cost is proportional to the number of variables in the formula (at a £xed ratio of clauses to variables) in the easy-SAT regime and slightly beyond, and its behavior in the hardSAT regime appears to re¤ect the underlying structure of the solution space that has been predicted by replica symmetry-breaking arguments. An analysis of the tradeoffs between the various methods of search for satisfying assignments shows WSAT to be far more powerful than has been appreciated, and suggests some interesting new directions for practical algorithm development. 1

5 0.57204431 122 nips-2004-Modelling Uncertainty in the Game of Go

Author: David H. Stern, Thore Graepel, David MacKay

Abstract: Go is an ancient oriental game whose complexity has defeated attempts to automate it. We suggest using probability in a Bayesian sense to model the uncertainty arising from the vast complexity of the game tree. We present a simple conditional Markov random ﬁeld model for predicting the pointwise territory outcome of a game. The topology of the model reﬂects the spatial structure of the Go board. We describe a version of the Swendsen-Wang process for sampling from the model during learning and apply loopy belief propagation for rapid inference and prediction. The model is trained on several hundred records of professional games. Our experimental results indicate that the model successfully learns to predict territory despite its simplicity. 1

6 0.36908194 198 nips-2004-Unsupervised Variational Bayesian Learning of Nonlinear Models

7 0.36455625 29 nips-2004-Beat Tracking the Graphical Model Way

8 0.35217476 57 nips-2004-Economic Properties of Social Networks

9 0.34580407 55 nips-2004-Distributed Occlusion Reasoning for Tracking with Nonparametric Belief Propagation

10 0.33862662 43 nips-2004-Conditional Models of Identity Uncertainty with Application to Noun Coreference

11 0.33276883 191 nips-2004-The Variational Ising Classifier (VIC) Algorithm for Coherently Contaminated Data

12 0.29957461 105 nips-2004-Log-concavity Results on Gaussian Process Methods for Supervised and Unsupervised Learning

13 0.29616439 149 nips-2004-Probabilistic Inference of Alternative Splicing Events in Microarray Data

14 0.29415801 44 nips-2004-Conditional Random Fields for Object Recognition

15 0.27716282 96 nips-2004-Learning, Regularization and Ill-Posed Inverse Problems

16 0.27662805 76 nips-2004-Hierarchical Bayesian Inference in Networks of Spiking Neurons

17 0.27250785 204 nips-2004-Variational Minimax Estimation of Discrete Distributions under KL Loss

18 0.27066213 86 nips-2004-Instance-Specific Bayesian Model Averaging for Classification

19 0.27021265 54 nips-2004-Distributed Information Regularization on Graphs

20 0.264768 193 nips-2004-Theories of Access Consciousness

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.033), (15, 0.082), (26, 0.025), (33, 0.762)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99628544 63 nips-2004-Expectation Consistent Free Energies for Approximate Inference

Author: Manfred Opper, Ole Winther

2 0.99180865 139 nips-2004-Optimal Aggregation of Classifiers and Boosting Maps in Functional Magnetic Resonance Imaging

Author: Vladimir Koltchinskii, Manel Martínez-ramón, Stefan Posse

Abstract: We study a method of optimal data-driven aggregation of classiﬁers in a convex combination and establish tight upper bounds on its excess risk with respect to a convex loss function under the assumption that the solution of optimal aggregation problem is sparse. We use a boosting type algorithm of optimal aggregation to develop aggregate classiﬁers of activation patterns in fMRI based on locally trained SVM classiﬁers. The aggregation coefﬁcients are then used to design a ”boosting map” of the brain needed to identify the regions with most signiﬁcant impact on classiﬁcation. 1

3 0.99176753 39 nips-2004-Coarticulation in Markov Decision Processes

Author: Khashayar Rohanimanesh, Robert Platt, Sridhar Mahadevan, Roderic Grupen

Abstract: We investigate an approach for simultaneously committing to multiple activities, each modeled as a temporally extended action in a semi-Markov decision process (SMDP). For each activity we deﬁne a set of admissible solutions consisting of the redundant set of optimal policies, and those policies that ascend the optimal statevalue function associated with them. A plan is then generated by merging them in such a way that the solutions to the subordinate activities are realized in the set of admissible solutions satisfying the superior activities. We present our theoretical results and empirically evaluate our approach in a simulated domain. 1

4 0.98968023 120 nips-2004-Modeling Conversational Dynamics as a Mixed-Memory Markov Process

Author: Tanzeem Choudhury, Sumit Basu

Abstract: In this work, we quantitatively investigate the ways in which a given person influences the joint turn-taking behavior in a conversation. After collecting an auditory database of social interactions among a group of twenty-three people via wearable sensors (66 hours of data each over two weeks), we apply speech and conversation detection methods to the auditory streams. These methods automatically locate the conversations, determine their participants, and mark which participant was speaking when. We then model the joint turn-taking behavior as a Mixed-Memory Markov Model [1] that combines the statistics of the individual subjects' self-transitions and the partners ' cross-transitions. The mixture parameters in this model describe how much each person 's individual behavior contributes to the joint turn-taking behavior of the pair. By estimating these parameters, we thus estimate how much influence each participant has in determining the joint turntaking behavior. We show how this measure correlates significantly with betweenness centrality [2], an independent measure of an individual's importance in a social network. This result suggests that our estimate of conversational influence is predictive of social influence. 1

5 0.98685664 186 nips-2004-The Correlated Correspondence Algorithm for Unsupervised Registration of Nonrigid Surfaces

Author: Dragomir Anguelov, Praveen Srinivasan, Hoi-cheung Pang, Daphne Koller, Sebastian Thrun, James Davis

Abstract: We present an unsupervised algorithm for registering 3D surface scans of an object undergoing signiﬁcant deformations. Our algorithm does not need markers, nor does it assume prior knowledge about object shape, the dynamics of its deformation, or scan alignment. The algorithm registers two meshes by optimizing a joint probabilistic model over all point-topoint correspondences between them. This model enforces preservation of local mesh geometry, as well as more global constraints that capture the preservation of geodesic distance between corresponding point pairs. The algorithm applies even when one of the meshes is an incomplete range scan; thus, it can be used to automatically ﬁll in the remaining surfaces for this partial scan, even if those surfaces were previously only seen in a different conﬁguration. We evaluate the algorithm on several real-world datasets, where we demonstrate good results in the presence of signiﬁcant movement of articulated parts and non-rigid surface deformation. Finally, we show that the output of the algorithm can be used for compelling computer graphics tasks such as interpolation between two scans of a non-rigid object and automatic recovery of articulated object models. 1

6 0.98682839 126 nips-2004-Nearly Tight Bounds for the Continuum-Armed Bandit Problem

7 0.98557699 115 nips-2004-Maximum Margin Clustering

8 0.98510689 149 nips-2004-Probabilistic Inference of Alternative Splicing Events in Microarray Data

9 0.8935473 80 nips-2004-Identifying Protein-Protein Interaction Sites on a Genome-Wide Scale

10 0.89239252 56 nips-2004-Dynamic Bayesian Networks for Brain-Computer Interfaces

11 0.89194626 143 nips-2004-PAC-Bayes Learning of Conjunctions and Classification of Gene-Expression Data

12 0.88422763 32 nips-2004-Boosting on Manifolds: Adaptive Regularization of Base Classifiers

13 0.88201368 72 nips-2004-Generalization Error and Algorithmic Convergence of Median Boosting

14 0.88092381 44 nips-2004-Conditional Random Fields for Object Recognition

15 0.87984276 147 nips-2004-Planning for Markov Decision Processes with Sparse Stochasticity

16 0.87457263 3 nips-2004-A Feature Selection Algorithm Based on the Global Minimization of a Generalization Error Bound

17 0.86702067 166 nips-2004-Semi-supervised Learning via Gaussian Processes

18 0.86480421 179 nips-2004-Surface Reconstruction using Learned Shape Models

19 0.8647095 51 nips-2004-Detecting Significant Multidimensional Spatial Clusters

20 0.86353028 38 nips-2004-Co-Validation: Using Model Disagreement on Unlabeled Data to Validate Classification Algorithms