nips nips2001 nips2001-192 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Martin J. Wainwright, Tommi Jaakkola, Alan S. Willsky
Abstract: We develop a tree-based reparameterization framework that provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles. It includes belief propagation (BP), which can be reformulated as a very local form of reparameterization. More generally, we consider algorithms that perform exact computations over spanning trees of the full graph. On the practical side, we find that such tree reparameterization (TRP) algorithms have convergence properties superior to BP. The reparameterization perspective also provides a number of theoretical insights into approximate inference, including a new characterization of fixed points; and an invariance intrinsic to TRP /BP. These two properties enable us to analyze and bound the error between the TRP /BP approximations and the actual marginals. While our results arise naturally from the TRP perspective, most of them apply in an algorithm-independent manner to any local minimum of the Bethe free energy. Our results also have natural extensions to more structured approximations [e.g. , 1, 2]. 1
Reference: text
sentIndex sentText sentNum sentScore
1 Tree-based reparameterization for approximate inference on loopy graphs Martin J. [sent-1, score-0.725]
2 edu Abstract We develop a tree-based reparameterization framework that provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles. [sent-7, score-0.861]
3 It includes belief propagation (BP), which can be reformulated as a very local form of reparameterization. [sent-8, score-0.278]
4 More generally, we consider algorithms that perform exact computations over spanning trees of the full graph. [sent-9, score-0.264]
5 On the practical side, we find that such tree reparameterization (TRP) algorithms have convergence properties superior to BP. [sent-10, score-0.635]
6 The reparameterization perspective also provides a number of theoretical insights into approximate inference, including a new characterization of fixed points; and an invariance intrinsic to TRP /BP. [sent-11, score-0.836]
7 These two properties enable us to analyze and bound the error between the TRP /BP approximations and the actual marginals. [sent-12, score-0.098]
8 While our results arise naturally from the TRP perspective, most of them apply in an algorithm-independent manner to any local minimum of the Bethe free energy. [sent-13, score-0.133]
9 Our results also have natural extensions to more structured approximations [e. [sent-14, score-0.179]
10 1 Introduction Given a graphical model, one important problem is the computation of marginal distributions of variables at each node. [sent-17, score-0.126]
11 Although highly efficient algorithms exist for this task on trees, exact solutions are prohibitively complex for more general graphs of any substantial size. [sent-18, score-0.253]
12 This difficulty motivates the use of approximate inference algorithms, of which one of the best-known and most widely studied is belief propagation [3], also known as the sum-product algorithm in coding [e. [sent-19, score-0.302]
13 Recent work has yielded some insight into belief propagation (BP). [sent-22, score-0.214]
14 , 5, 6] have analyzed the single loop case, where BP can be reformulated as a matrix powering method. [sent-25, score-0.047]
15 For Gaussian processes on arbitrary graphs, two groups [7, 8] have shown that the means are exact when BP converges. [sent-26, score-0.124]
16 For graphs corresponding to turbo codes, Richardson [9] established the existence of fixed points, and gave conditions for their stability. [sent-27, score-0.19]
17 [1] showed that BP corresponds to constrained minimization of the Bethe free energy, and proposed extensions based on Kikuchi expansions [10]. [sent-29, score-0.146]
18 , 11, 12] to develop more sophisticated algorithms for minimizing the Bethe free energy. [sent-33, score-0.091]
19 The framework of this paper provides a new conceptual view of various algorithms for approximate inference, including BP. [sent-35, score-0.191]
20 The basic idea is to seek a reparameterization of the distribution that yields factors which correspond, either exactly or approximately, to the desired marginal distributions. [sent-36, score-0.571]
21 , a tree) , then there exists a unique reparameterization specified by exact marginal distributions over cliques. [sent-39, score-0.622]
22 For a graph with cycles, we consider the idea of iteratively reparameterizing different parts of the distribution, each corresponding to an acyclic subgraph. [sent-40, score-0.105]
23 As we will show, BP can be interpreted in exactly this manner , in which each reparameterization takes place over a pair of neighboring nodes. [sent-41, score-0.533]
24 More significantly, this interpretation leads to more general updates in which reparameterization is performed over arbitrary acyclic subgraphs, which we refer to as tree-based reparameterization (TRP) algorithms. [sent-43, score-1.12]
25 At a low level, the more global TRP updates can be viewed as a tree-based schedule for message-passing. [sent-44, score-0.071]
26 Indeed, a practical contribution of this paper is to demonstrate that TRP updates tend to have better convergence properties than local BP updates. [sent-45, score-0.191]
27 At a more abstract level, the reparameterization perspective provides valuable conceptual insight, including a simple tree-consistency characterization of fixed points, as well as an invariance intrinsic to TRP /BP. [sent-46, score-0.828]
28 These properties allow us to derive an exact expression for the error between the TRP /BP approximations and the actual marginals. [sent-47, score-0.184]
29 Based on this exact expression, we derive computable bounds on the error. [sent-48, score-0.204]
30 Most of these results, though they emerge very naturally in the TRP framework , apply in an algorithm-independent manner to any constrained local minimum of the Bethe free energy, whether obtained by TRP /BP or an alternative method [e. [sent-49, score-0.168]
31 1 Basic notation An undirected graph Q = (V, £) consists of a set of nodes or vertices V = {l , . [sent-54, score-0.066]
32 Lying at each node s E V is a discrete random variable Xs E {a, . [sent-58, score-0.063]
33 , 3] guarantees that the distribution factorizes as p(x) ex: [lc Ee 'l/Jc(xc) where 'l/Jc(xc) is a compatibility function depending only on the subvector Xc = {xs I SEC} of nodes in a particular clique C. [sent-65, score-0.109]
34 Note that each individual node forms a singleton clique, so that some of the factors 'l/Jc may involve functions of each individual variable. [sent-66, score-0.133]
35 As a consequence, if we have independent measurements Ys of Xs at some (or all) of the nodes, then Bayes' rule implies that the effect of including these measurements - i. [sent-67, score-0.119]
36 , the transformation from the prior distribution p(x) to the conditional distribution p(x I y) - is simply to modify the singleton factors. [sent-69, score-0.07]
37 As a result, throughout this paper, we suppress explicit mention of measurements, since the problem of computing marginals for either p(x) or p(x Iy) are of identical structure and complexity. [sent-70, score-0.129]
38 The analysis of this paper is restricted to graphs with singleton ('l/Js) and pairwise ('l/Jst} cliques. [sent-71, score-0.216]
39 However, it is straightforward to extend reparameterization to larger cliques, as in cluster variational methods [e. [sent-72, score-0.496]
40 2 Exact tree inference as reparameterization Algorithms for optimal inference on trees have appeared in the literature of various fields [e. [sent-76, score-0.779]
41 One important consequence of the junction tree representation [15] is that any exact algorithm for optimal inference on trees actually computes marginal distributions for pairs (s, t) of neighboring nodes. [sent-79, score-0.459]
42 In doing so, it produces an alternative factorization p(x) = TI sEV P s TI(s,t)E£ Pst/(PsPt ) where Ps and Pst are the single-node and pairwise marginals respectively. [sent-80, score-0.225]
43 This {Ps , Pst} representation can be deduced from a more general factorization result on junction trees [e. [sent-81, score-0.22]
44 Thus, exact inference on trees can be viewed as computing a reparameterized factorization of the distribution p(x) that explicitly exposes the local marginal distributions. [sent-84, score-0.433]
45 2 Tree-based reparameterization for graphs with cycles The basic idea of a TRP algorithm is to perform successive reparameterization updates on trees embedded within the original graph. [sent-85, score-1.293]
46 Although such updates are applicable to arbitrary acyclic substructures, here we focus on a set T 1 , . [sent-86, score-0.186]
47 To describe TRP updates, let T be a pseudomarginal probability vector consisting of single-node marginals Ts(x s ) for 8 E V; and pairwise joint distributions Tst (x s, Xt) for edges (s, t) E [. [sent-90, score-0.17]
48 Aside from positivity and normalization (Lx s Ts = 1; L xs , xt Tst = 1) constraints, a given vector T is arbitraryl , and gives rises to a parameterization of the distribution as p(x; T) ex: TI sEV Ts TI(S,t)E£ Tst/ {(L x. [sent-91, score-0.16]
49 Ultimately, we shall seek vectors T that are consistent - i. [sent-93, score-0.035]
50 , that belong to as well as upper and lower bounds on the actual marginals. [sent-95, score-0.173]
51 (a) For weak potentials, TRP /BP approximation is excellent; bounds on exact marginals are tight. [sent-96, score-0.371]
52 Bounds are looser, and for certain nodes, the TRP /BP approximation lies above the upper bounds on the actual marginal P 8 ;1 . [sent-98, score-0.28]
53 Much of the analysis of this paper -- including reparameterization, invariance, and error analysis -- can be extended [see 14] to more structured approximation algorithms [e. [sent-99, score-0.185]
54 Figure 3 illustrates the use of bounds in assessing when to use a more structured approximation. [sent-102, score-0.199]
55 For strong attractive potentials on the 3 x 3 grid, the TRP /BP approximation in panel (a) is very poor, as reflected by relatively loose bounds on the actual marginals. [sent-103, score-0.388]
56 In contrast, the Kikuchi approximation in (b) is excellent, as revealed by the tightness of the bounds. [sent-104, score-0.065]
57 4 Discussion The TRP framework of this paper provides a new view of approximate inference; and makes both practical and conceptual contributions. [sent-105, score-0.165]
58 On the practical side, we find that more global TRP updates tend to have better convergence properties than local BP updates. [sent-106, score-0.191]
59 The freedom in tree choice leads to open problems of a graphtheoretic nature: e. [sent-107, score-0.057]
60 , how to choose trees so as to guarantee convergence, or to optimize the rate of convergence? [sent-109, score-0.103]
61 Among the conceptual insights provided by the reparameterization perspective are a new characterization of fixed points; an intrinsic invariance; and analysis of the approximation error. [sent-110, score-0.83]
62 Importantly, most of these results apply to any constrained local minimum of the Bethe free energy, and have natural extensions [see 14] to more structured approximations [e. [sent-111, score-0.314]
63 Bounds on single node marginals - - - - -0 - - - -0- - Bounds on single node marginals - e- - - - M M 0. [sent-123, score-0.384]
64 (a) For strong attractive potentials on the 3 x 3 grid, BP approximation is poor, as reflected by loose bounds on the actual marginal. [sent-140, score-0.388]
65 (b) Kikuchi approximation [1] for same problem is excellent; corresponding bounds are tight. [sent-141, score-0.156]
66 Iterative decoding of compound codes by probability propagation in graphical models. [sent-154, score-0.209]
67 Correctness of local probability propagation in graphical models with loops. [sent-169, score-0.189]
68 Correctness of belief propagation in Gaussian graphical models of arbitrary topology. [sent-175, score-0.282]
69 Belief optimization: A stable alternative to loopy belief propagation. [sent-197, score-0.137]
70 A double-loop algorithm to minimize the Bethe and Kikuchi free energies. [sent-201, score-0.056]
71 Tree-based reparameterization for approximate estimation on graphs with cycles. [sent-209, score-0.611]
72 Stochastic processes on graphs with cycles: geometric and variational approaches. [sent-217, score-0.134]
73 On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. [sent-227, score-0.225]
wordName wordTfidf (topN-words)
[('trp', 0.601), ('reparameterization', 0.467), ('bp', 0.196), ('tst', 0.158), ('marginals', 0.129), ('bethe', 0.12), ('bounds', 0.118), ('graphs', 0.105), ('trees', 0.103), ('kikuchi', 0.1), ('belief', 0.099), ('propagation', 0.088), ('xs', 0.088), ('conceptual', 0.086), ('exact', 0.086), ('wainwright', 0.082), ('structured', 0.081), ('acyclic', 0.077), ('inference', 0.076), ('updates', 0.071), ('xc', 0.07), ('singleton', 0.07), ('marginal', 0.069), ('potentials', 0.063), ('ti', 0.063), ('sev', 0.063), ('node', 0.063), ('invariance', 0.06), ('tree', 0.057), ('graphical', 0.057), ('free', 0.056), ('perspective', 0.056), ('factorization', 0.055), ('insights', 0.055), ('pst', 0.055), ('extensions', 0.055), ('actual', 0.055), ('ts', 0.054), ('cycles', 0.052), ('characterization', 0.05), ('february', 0.05), ('turbo', 0.05), ('reformulated', 0.047), ('excellent', 0.046), ('xt', 0.045), ('measurements', 0.044), ('loose', 0.044), ('january', 0.044), ('clique', 0.044), ('local', 0.044), ('intrinsic', 0.043), ('approximations', 0.043), ('reflected', 0.042), ('correctness', 0.042), ('pairwise', 0.041), ('practical', 0.04), ('ps', 0.04), ('tommi', 0.04), ('spanning', 0.04), ('approximate', 0.039), ('loopy', 0.038), ('approximation', 0.038), ('nodes', 0.038), ('arbitrary', 0.038), ('yedidia', 0.037), ('energy', 0.036), ('convergence', 0.036), ('fixed', 0.035), ('constrained', 0.035), ('algorithms', 0.035), ('seek', 0.035), ('junction', 0.035), ('decoding', 0.035), ('manner', 0.033), ('neighboring', 0.033), ('nips', 0.032), ('oxford', 0.032), ('freeman', 0.032), ('including', 0.031), ('grid', 0.031), ('jaakkola', 0.031), ('variational', 0.029), ('researchers', 0.029), ('grant', 0.029), ('codes', 0.029), ('embedded', 0.028), ('attractive', 0.028), ('phd', 0.028), ('graph', 0.028), ('deduced', 0.027), ('rises', 0.027), ('prohibitively', 0.027), ('compatibility', 0.027), ('media', 0.027), ('subgraphs', 0.027), ('tightness', 0.027), ('notwithstanding', 0.027), ('looser', 0.027), ('substructures', 0.027), ('insight', 0.027)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000002 192 nips-2001-Tree-based reparameterization for approximate inference on loopy graphs
Author: Martin J. Wainwright, Tommi Jaakkola, Alan S. Willsky
Abstract: We develop a tree-based reparameterization framework that provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles. It includes belief propagation (BP), which can be reformulated as a very local form of reparameterization. More generally, we consider algorithms that perform exact computations over spanning trees of the full graph. On the practical side, we find that such tree reparameterization (TRP) algorithms have convergence properties superior to BP. The reparameterization perspective also provides a number of theoretical insights into approximate inference, including a new characterization of fixed points; and an invariance intrinsic to TRP /BP. These two properties enable us to analyze and bound the error between the TRP /BP approximations and the actual marginals. While our results arise naturally from the TRP perspective, most of them apply in an algorithm-independent manner to any local minimum of the Bethe free energy. Our results also have natural extensions to more structured approximations [e.g. , 1, 2]. 1
2 0.23733485 188 nips-2001-The Unified Propagation and Scaling Algorithm
Author: Yee W. Teh, Max Welling
Abstract: In this paper we will show that a restricted class of constrained minimum divergence problems, named generalized inference problems, can be solved by approximating the KL divergence with a Bethe free energy. The algorithm we derive is closely related to both loopy belief propagation and iterative scaling. This unified propagation and scaling algorithm reduces to a convergent alternative to loopy belief propagation when no constraints are present. Experiments show the viability of our algorithm.
3 0.1623909 132 nips-2001-Novel iteration schemes for the Cluster Variation Method
Author: Hilbert J. Kappen, Wim Wiegerinck
Abstract: The Cluster Variation method is a class of approximation methods containing the Bethe and Kikuchi approximations as special cases. We derive two novel iteration schemes for the Cluster Variation Method. One is a fixed point iteration scheme which gives a significant improvement over loopy BP, mean field and TAP methods on directed graphical models. The other is a gradient based method, that is guaranteed to converge and is shown to give useful results on random graphs with mild frustration. We conclude that the methods are of significant practical value for large inference problems. 1
4 0.12382632 98 nips-2001-Information Geometrical Framework for Analyzing Belief Propagation Decoder
Author: Shiro Ikeda, Toshiyuki Tanaka, Shun-ichi Amari
Abstract: The mystery of belief propagation (BP) decoder, especially of the turbo decoding, is studied from information geometrical viewpoint. The loopy belief network (BN) of turbo codes makes it difficult to obtain the true “belief” by BP, and the characteristics of the algorithm and its equilibrium are not clearly understood. Our study gives an intuitive understanding of the mechanism, and a new framework for the analysis. Based on the framework, we reveal basic properties of the turbo decoding.
5 0.099835411 178 nips-2001-TAP Gibbs Free Energy, Belief Propagation and Sparsity
Author: Lehel Csató, Manfred Opper, Ole Winther
Abstract: The adaptive TAP Gibbs free energy for a general densely connected probabilistic model with quadratic interactions and arbritary single site constraints is derived. We show how a specific sequential minimization of the free energy leads to a generalization of Minka’s expectation propagation. Lastly, we derive a sparse representation version of the sequential algorithm. The usefulness of the approach is demonstrated on classification and density estimation with Gaussian processes and on an independent component analysis problem.
6 0.094641156 97 nips-2001-Information-Geometrical Significance of Sparsity in Gallager Codes
7 0.092428781 196 nips-2001-Very loopy belief propagation for unwrapping phase images
8 0.089634508 190 nips-2001-Thin Junction Trees
9 0.085637242 118 nips-2001-Matching Free Trees with Replicator Equations
10 0.072486334 105 nips-2001-Kernel Machines and Boolean Functions
11 0.068474531 119 nips-2001-Means, Correlations and Bounds
12 0.061236851 189 nips-2001-The g Factor: Relating Distributions on Features to Distributions on Images
13 0.05834429 56 nips-2001-Convolution Kernels for Natural Language
14 0.055273283 21 nips-2001-A Variational Approach to Learning Curves
15 0.054106861 117 nips-2001-MIME: Mutual Information Minimization and Entropy Maximization for Bayesian Belief Propagation
16 0.053765502 115 nips-2001-Linear-time inference in Hierarchical HMMs
17 0.046335492 3 nips-2001-ACh, Uncertainty, and Cortical Inference
18 0.04517898 8 nips-2001-A General Greedy Approximation Algorithm with Applications
19 0.044535618 52 nips-2001-Computing Time Lower Bounds for Recurrent Sigmoidal Neural Networks
20 0.043453179 84 nips-2001-Global Coordination of Local Linear Models
topicId topicWeight
[(0, -0.146), (1, -0.005), (2, 0.026), (3, -0.064), (4, -0.009), (5, -0.298), (6, 0.004), (7, -0.209), (8, 0.08), (9, 0.143), (10, -0.094), (11, -0.035), (12, 0.074), (13, 0.051), (14, 0.006), (15, 0.036), (16, -0.117), (17, 0.112), (18, -0.035), (19, -0.084), (20, 0.018), (21, -0.117), (22, -0.125), (23, -0.047), (24, -0.07), (25, -0.025), (26, -0.064), (27, 0.029), (28, 0.01), (29, -0.05), (30, 0.032), (31, -0.006), (32, -0.0), (33, 0.013), (34, -0.003), (35, -0.09), (36, -0.005), (37, 0.033), (38, -0.103), (39, -0.035), (40, 0.049), (41, -0.096), (42, 0.007), (43, 0.044), (44, 0.001), (45, 0.099), (46, -0.029), (47, -0.029), (48, -0.033), (49, 0.065)]
simIndex simValue paperId paperTitle
same-paper 1 0.96453881 192 nips-2001-Tree-based reparameterization for approximate inference on loopy graphs
Author: Martin J. Wainwright, Tommi Jaakkola, Alan S. Willsky
Abstract: We develop a tree-based reparameterization framework that provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles. It includes belief propagation (BP), which can be reformulated as a very local form of reparameterization. More generally, we consider algorithms that perform exact computations over spanning trees of the full graph. On the practical side, we find that such tree reparameterization (TRP) algorithms have convergence properties superior to BP. The reparameterization perspective also provides a number of theoretical insights into approximate inference, including a new characterization of fixed points; and an invariance intrinsic to TRP /BP. These two properties enable us to analyze and bound the error between the TRP /BP approximations and the actual marginals. While our results arise naturally from the TRP perspective, most of them apply in an algorithm-independent manner to any local minimum of the Bethe free energy. Our results also have natural extensions to more structured approximations [e.g. , 1, 2]. 1
2 0.93274122 188 nips-2001-The Unified Propagation and Scaling Algorithm
Author: Yee W. Teh, Max Welling
Abstract: In this paper we will show that a restricted class of constrained minimum divergence problems, named generalized inference problems, can be solved by approximating the KL divergence with a Bethe free energy. The algorithm we derive is closely related to both loopy belief propagation and iterative scaling. This unified propagation and scaling algorithm reduces to a convergent alternative to loopy belief propagation when no constraints are present. Experiments show the viability of our algorithm.
3 0.78337413 196 nips-2001-Very loopy belief propagation for unwrapping phase images
Author: Brendan J. Frey, Ralf Koetter, Nemanja Petrovic
Abstract: Since the discovery that the best error-correcting decoding algorithm can be viewed as belief propagation in a cycle-bound graph, researchers have been trying to determine under what circumstances
4 0.66116571 132 nips-2001-Novel iteration schemes for the Cluster Variation Method
Author: Hilbert J. Kappen, Wim Wiegerinck
Abstract: The Cluster Variation method is a class of approximation methods containing the Bethe and Kikuchi approximations as special cases. We derive two novel iteration schemes for the Cluster Variation Method. One is a fixed point iteration scheme which gives a significant improvement over loopy BP, mean field and TAP methods on directed graphical models. The other is a gradient based method, that is guaranteed to converge and is shown to give useful results on random graphs with mild frustration. We conclude that the methods are of significant practical value for large inference problems. 1
5 0.47376114 178 nips-2001-TAP Gibbs Free Energy, Belief Propagation and Sparsity
Author: Lehel Csató, Manfred Opper, Ole Winther
Abstract: The adaptive TAP Gibbs free energy for a general densely connected probabilistic model with quadratic interactions and arbritary single site constraints is derived. We show how a specific sequential minimization of the free energy leads to a generalization of Minka’s expectation propagation. Lastly, we derive a sparse representation version of the sequential algorithm. The usefulness of the approach is demonstrated on classification and density estimation with Gaussian processes and on an independent component analysis problem.
6 0.40885398 118 nips-2001-Matching Free Trees with Replicator Equations
7 0.39900753 98 nips-2001-Information Geometrical Framework for Analyzing Belief Propagation Decoder
8 0.38632849 97 nips-2001-Information-Geometrical Significance of Sparsity in Gallager Codes
9 0.38610548 180 nips-2001-The Concave-Convex Procedure (CCCP)
10 0.3642813 190 nips-2001-Thin Junction Trees
11 0.31710052 3 nips-2001-ACh, Uncertainty, and Cortical Inference
12 0.27750254 119 nips-2001-Means, Correlations and Bounds
13 0.26330352 189 nips-2001-The g Factor: Relating Distributions on Features to Distributions on Images
14 0.25951129 115 nips-2001-Linear-time inference in Hierarchical HMMs
15 0.22811869 169 nips-2001-Small-World Phenomena and the Dynamics of Information
16 0.22723743 84 nips-2001-Global Coordination of Local Linear Models
17 0.22107114 149 nips-2001-Probabilistic Abstraction Hierarchies
18 0.21964616 129 nips-2001-Multiplicative Updates for Classification by Mixture Models
19 0.2087478 114 nips-2001-Learning from Infinite Data in Finite Time
20 0.2066057 21 nips-2001-A Variational Approach to Learning Curves
topicId topicWeight
[(11, 0.245), (14, 0.016), (17, 0.019), (19, 0.055), (27, 0.151), (30, 0.062), (38, 0.032), (59, 0.026), (72, 0.064), (79, 0.064), (83, 0.03), (88, 0.013), (91, 0.131)]
simIndex simValue paperId paperTitle
1 0.89913094 120 nips-2001-Minimax Probability Machine
Author: Gert Lanckriet, Laurent E. Ghaoui, Chiranjib Bhattacharyya, Michael I. Jordan
Abstract: When constructing a classifier, the probability of correct classification of future data points should be maximized. In the current paper this desideratum is translated in a very direct way into an optimization problem, which is solved using methods from convex optimization. We also show how to exploit Mercer kernels in this setting to obtain nonlinear decision boundaries. A worst-case bound on the probability of misclassification of future data is obtained explicitly. 1
same-paper 2 0.85222673 192 nips-2001-Tree-based reparameterization for approximate inference on loopy graphs
Author: Martin J. Wainwright, Tommi Jaakkola, Alan S. Willsky
Abstract: We develop a tree-based reparameterization framework that provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles. It includes belief propagation (BP), which can be reformulated as a very local form of reparameterization. More generally, we consider algorithms that perform exact computations over spanning trees of the full graph. On the practical side, we find that such tree reparameterization (TRP) algorithms have convergence properties superior to BP. The reparameterization perspective also provides a number of theoretical insights into approximate inference, including a new characterization of fixed points; and an invariance intrinsic to TRP /BP. These two properties enable us to analyze and bound the error between the TRP /BP approximations and the actual marginals. While our results arise naturally from the TRP perspective, most of them apply in an algorithm-independent manner to any local minimum of the Bethe free energy. Our results also have natural extensions to more structured approximations [e.g. , 1, 2]. 1
3 0.67736852 13 nips-2001-A Natural Policy Gradient
Author: Sham M. Kakade
Abstract: We provide a natural gradient method that represents the steepest descent direction based on the underlying structure of the parameter space. Although gradient methods cannot make large changes in the values of the parameters, we show that the natural gradient is moving toward choosing a greedy optimal action rather than just a better action. These greedy optimal actions are those that would be chosen under one improvement step of policy iteration with approximate, compatible value functions, as defined by Sutton et al. [9]. We then show drastic performance improvements in simple MDPs and in the more challenging MDP of Tetris. 1
4 0.67345154 190 nips-2001-Thin Junction Trees
Author: Francis R. Bach, Michael I. Jordan
Abstract: We present an algorithm that induces a class of models with thin junction trees—models that are characterized by an upper bound on the size of the maximal cliques of their triangulated graph. By ensuring that the junction tree is thin, inference in our models remains tractable throughout the learning process. This allows both an efficient implementation of an iterative scaling parameter estimation algorithm and also ensures that inference can be performed efficiently with the final model. We illustrate the approach with applications in handwritten digit recognition and DNA splice site detection.
Author: Gregory Z. Grudic, Lyle H. Ungar
Abstract: We address two open theoretical questions in Policy Gradient Reinforcement Learning. The first concerns the efficacy of using function approximation to represent the state action value function, . Theory is presented showing that linear function approximation representations of can degrade the rate of convergence of performance gradient estimates by a factor of relative to when no function approximation of is used, where is the number of possible actions and is the number of basis functions in the function approximation representation. The second concerns the use of a bias term in estimating the state action value function. Theory is presented showing that a non-zero bias term can improve the rate of convergence of performance gradient estimates by , where is the number of possible actions. Experimental evidence is presented showing that these theoretical results lead to significant improvement in the convergence properties of Policy Gradient Reinforcement Learning algorithms. ¤ ¨ ¦ ¢ ©§¥¤£¡ ¦ ¤ ¨ £¡ ¨ ¤¢ ¢
6 0.6644389 89 nips-2001-Grouping with Bias
7 0.66176474 127 nips-2001-Multi Dimensional ICA to Separate Correlated Sources
8 0.66149729 8 nips-2001-A General Greedy Approximation Algorithm with Applications
9 0.66043401 88 nips-2001-Grouping and dimensionality reduction by locally linear embedding
10 0.66004813 84 nips-2001-Global Coordination of Local Linear Models
11 0.65997714 135 nips-2001-On Spectral Clustering: Analysis and an algorithm
12 0.65939391 131 nips-2001-Neural Implementation of Bayesian Inference in Population Codes
13 0.65933526 162 nips-2001-Relative Density Nets: A New Way to Combine Backpropagation with HMM's
14 0.65920043 29 nips-2001-Adaptive Sparseness Using Jeffreys Prior
15 0.65886426 132 nips-2001-Novel iteration schemes for the Cluster Variation Method
16 0.65821731 57 nips-2001-Correlation Codes in Neuronal Populations
17 0.65808684 95 nips-2001-Infinite Mixtures of Gaussian Process Experts
18 0.65807086 150 nips-2001-Probabilistic Inference of Hand Motion from Neural Activity in Motor Cortex
19 0.65775013 9 nips-2001-A Generalization of Principal Components Analysis to the Exponential Family
20 0.65675712 27 nips-2001-Activity Driven Adaptive Stochastic Resonance