Probabilistic Graphical Models

  1. Inference: Answering Queries
    1. The Inference Problem
      1. Types of Inference Queries
        1. Marginal Inference
          1. Computing Marginals for Single Variables
            1. Computing Marginals for Subsets of Variables
              1. Conditional Marginals
              2. Maximum a Posteriori (MAP) Inference
                1. Definition and Applications
                  1. Most Probable Assignment
                    1. Partial MAP Queries
                    2. Marginal MAP Inference
                      1. Definition and Complexity
                    3. Computational Challenges
                      1. Complexity of Exact Inference
                        1. NP-hardness Results
                          1. Exponential Blowup
                          2. Computing the Partition Function
                            1. Importance in Normalization
                              1. Computational Difficulty
                          3. Exact Inference Algorithms
                            1. Inference on Simple Structures
                              1. Inference on Chain Graphs
                                1. Forward-Backward Algorithm
                                  1. Forward Pass
                                    1. Backward Pass
                                      1. Applications to HMMs
                                      2. Inference on Tree Structures
                                        1. Message Passing on Trees
                                          1. Leaf-to-Root and Root-to-Leaf Passes
                                        2. Variable Elimination
                                          1. Basic Algorithm
                                            1. Elimination Process
                                              1. Factor Operations
                                                1. Sum-Product Elimination
                                                2. Elimination Orderings
                                                  1. Impact on Efficiency
                                                    1. Finding Good Orderings
                                                      1. Heuristics for Ordering
                                                      2. Induced Graph and Treewidth
                                                        1. Definition of Induced Graph
                                                          1. Treewidth and Elimination
                                                            1. Computational Complexity Analysis
                                                            2. Max-Product Variable Elimination
                                                              1. Adaptation for MAP Inference
                                                                1. Differences from Sum-Product
                                                              2. Belief Propagation
                                                                1. Sum-Product Algorithm
                                                                  1. Message Passing on Trees
                                                                    1. Message Definitions
                                                                      1. Initialization and Update Rules
                                                                        1. Convergence Properties
                                                                        2. Max-Product Algorithm
                                                                          1. Adaptation for MAP Inference
                                                                            1. Message Modifications
                                                                              1. Backtracking for Solutions
                                                                            2. The Junction Tree Algorithm
                                                                              1. Graph Triangulation
                                                                                1. Chordal Graphs
                                                                                  1. Triangulation Process
                                                                                    1. Elimination and Fill-in
                                                                                    2. Clique Tree Construction
                                                                                      1. Maximal Cliques
                                                                                        1. Running Intersection Property
                                                                                          1. Clique Tree Properties
                                                                                          2. Message Passing on Clique Trees
                                                                                            1. Belief Update Procedures
                                                                                              1. Calibration Process
                                                                                                1. Global Consistency
                                                                                            2. Approximate Inference Algorithms
                                                                                              1. Variational Inference
                                                                                                1. Variational Principle
                                                                                                  1. The Evidence Lower Bound (ELBO)
                                                                                                    1. Variational Objective
                                                                                                      1. KL Divergence Minimization
                                                                                                      2. Mean-Field Approximation
                                                                                                        1. Factorized Approximations
                                                                                                          1. Independence Assumptions
                                                                                                            1. Coordinate Ascent Updates
                                                                                                            2. Kullback-Leibler (KL) Divergence
                                                                                                              1. Definition and Properties
                                                                                                                1. Role in Variational Methods
                                                                                                                  1. Forward and Reverse KL
                                                                                                                  2. Coordinate Ascent Variational Inference (CAVI)
                                                                                                                    1. Update Equations
                                                                                                                      1. Convergence Properties
                                                                                                                        1. Implementation Details
                                                                                                                        2. Structured Variational Inference
                                                                                                                          1. Beyond Mean-Field
                                                                                                                            1. Structured Approximations
                                                                                                                          2. Sampling-Based Methods
                                                                                                                            1. Basic Sampling Techniques
                                                                                                                              1. Forward Sampling
                                                                                                                                1. Ancestral Sampling
                                                                                                                                  1. Procedure and Limitations
                                                                                                                                  2. Rejection Sampling
                                                                                                                                    1. Acceptance Criteria
                                                                                                                                      1. Efficiency Considerations
                                                                                                                                      2. Importance Sampling
                                                                                                                                        1. Proposal Distributions
                                                                                                                                          1. Weighting and Normalization
                                                                                                                                            1. Effective Sample Size
                                                                                                                                          2. Markov Chain Monte Carlo (MCMC)
                                                                                                                                            1. Basic Principles
                                                                                                                                              1. Markov Chain Theory
                                                                                                                                                1. Stationary Distributions
                                                                                                                                                  1. Convergence Criteria
                                                                                                                                                  2. Gibbs Sampling
                                                                                                                                                    1. Conditional Distributions
                                                                                                                                                      1. Implementation Details
                                                                                                                                                        1. Convergence Analysis
                                                                                                                                                        2. Metropolis-Hastings Algorithm
                                                                                                                                                          1. Proposal Distributions
                                                                                                                                                            1. Acceptance Probability
                                                                                                                                                              1. Detailed Balance
                                                                                                                                                                1. Variants and Extensions
                                                                                                                                                              2. Advanced Sampling Methods
                                                                                                                                                                1. Hamiltonian Monte Carlo
                                                                                                                                                                  1. Gradient-Based Sampling
                                                                                                                                                                    1. Leapfrog Integration
                                                                                                                                                                    2. Slice Sampling
                                                                                                                                                                      1. Uniform Sampling Approach
                                                                                                                                                                        1. Implementation
                                                                                                                                                                    3. Loopy Belief Propagation
                                                                                                                                                                      1. Extension to Graphs with Cycles
                                                                                                                                                                        1. Message Passing on Loopy Graphs
                                                                                                                                                                          1. Differences from Tree-Structured Graphs
                                                                                                                                                                            1. Fixed Point Equations
                                                                                                                                                                            2. Convergence and Accuracy
                                                                                                                                                                              1. Convergence Issues
                                                                                                                                                                                1. When and Why It Fails
                                                                                                                                                                                  1. Empirical Performance
                                                                                                                                                                                  2. Variants and Improvements
                                                                                                                                                                                    1. Damped Updates
                                                                                                                                                                                      1. Generalized Belief Propagation

                                                                                                                                                                                Previous

                                                                                                                                                                                2. Representation: Types of Graphical Models

                                                                                                                                                                                Go to top

                                                                                                                                                                                Next

                                                                                                                                                                                4. Learning: From Data to Models