(Downloads - 0)
For more info about our services contact : help@bestpfe.com
Table of contents
i inference on graphs
1 markov random fields
1.1 Motivation
1.2 General Markov random fields
1.2.1 Definition and Markov property
1.2.2 Factor graph representation
1.2.3 First examples
1.3 Pairwise Markov random fields
1.3.1 Definition and examples
1.3.2 Maximum entropy principle
1.3.3 From general to pairwise Markov random fields
1.4 Random graph ensembles
1.4.1 The Erd˝os-Rényi model
1.4.2 The stochastic block model
1.4.3 The labeled stochastic block model
1.5 Mean-field approximations
1.5.1 Intractability of exact inference
1.5.2 Variational mean-field
1.5.3 The Bethe approximation and belief propagation
1.6 The Ising model: some physics
1.6.1 A different approach to mean-field approximations
1.6.2 The ferromagnetic Ising model
1.6.3 The Curie-Weiss model
1.6.4 The Ising spin glass
1.6.5 The planted spin glass
1.6.6 The Hopfield model
1.7 General approach of this work
ii spectral inference
2 factorized and symmetric models
2.1 Phase transition in belief propagation
2.1.1 Factorized models
2.1.2 Trivial fixed point of belief propagation
2.1.3 Phase transition
2.2 Symmetric models
2.2.1 Tensor decomposition and the non-backtracking matrix
2.2.2 Reduction to an Ising model
2.2.3 An example
2.2.4 A linearized belief propagation algorithm
2.3 The free energy point of view
2.3.1 The Ihara-Bass formula
2.3.2 The Bethe Hessian
2.3.3 Free energy Hessians
2.4 Conclusion
3 spectral properties of the non-backtracking operator and the bethe hessian on random graphs
3.1 The non-backtracking operator
3.1.1 Non-backtracking operator of the symmetric labeled stochastic block model
3.1.2 Cavity approach to the stability of the paramagnetic fixed point
3.1.3 Non-backtracking spectrum of the labeled stochastic block model
3.1.4 Cavity approach to the spectral density of the non-backtracking operator
3.2 The Bethe Hessian
3.2.1 Cavity approach to the spectral density of the Bethe Hessian on the labeled stochastic block
model
3.2.2 Ihara-Bass type formulas
3.3 Conclusion
4 case study: the planted spin glass, or censored block model
4.1 The non-backtracking operator
4.2 The Bethe Hessian
4.3 Algorithms
4.4 Spectral properties of the non-backtracking operator
4.5 Conclusion
iii some applications
5 community detection and the ising ferromagnet
5.1 The non-backtracking operator
5.2 The Bethe Hessian
5.3 Algorithm and numerical simulations
5.4 Conclusion
6 randomized clustering from sparse measurements
6.1 Motivation and definition of the problem
6.2 Algorithms
6.2.1 Belief propagation
6.2.2 The non-backtracking operator
6.2.3 The Bethe Hessian
6.3 Numerical results
6.4 Spectral properties of the non-backtracking operator
6.5 Conclusion
7 randomized semi-supervised clustering
7.1 Algorithm and guarantee
7.1.1 Algorithm for 2 clusters
7.1.2 Model and guarantee
7.1.3 More than 2 clusters
7.2 Numerical simulations
7.3 Proof of theorem 7.1.1
7.4 Proof of theorem 7.1.2
7.5 Conclusion
8 matrix completion and the hopfield model
8.1 Problem definition and relation to other work
8.2 Algorithm and motivation
8.2.1 The MaCBetH algorithm
8.2.2 Motivation from a Hopfield model
8.3 Analysis of performance in detection
8.3.1 Analysis of the phase transition
8.3.2 Computation of the spectral density
8.4 Numerical tests
8.5 Conclusion
9 spectral bounds on the ising ferromagnet
9.1 Introduction
9.1.1 Significance and prior work
9.1.2 Assumptions and definitions
9.2 Main results
9.2.1 Bound on the partition function
9.2.2 Bound on the susceptibility
9.2.3 Relation to belief propagation and susceptibility propagation
9.3 Proofs
9.3.1 High temperature expansion
9.3.2 Proof of theorem 9.2.1
9.3.3 Proof of theorem 9.2.2
9.4 Conclusion
10 outlook: learning and the natural gradient
10.1 Learning in exponential models
10.2 Natural gradient
10.3 Mean-field approximation to the natural gradient
10.4 Conclusion
concluding remarks
appendix
bibliography
