# Probabilistic Graphical Models ## Overview Probabilistic Graphical Models (PGMs) provide a unified framework for representing and reasoning about complex probability distributions using graph structures. They combine [[probability_theory|probability theory]] with [[graph_theory|graph theory]] to create powerful tools for modeling uncertainty, dependencies, and causality in complex systems. ## Mathematical Foundation ### 1. Graph Representation #### Directed Graphs (Bayesian Networks) ```math P(X_1,...,X_n) = \prod_{i=1}^n P(X_i|Pa(X_i)) ``` where: - X_i are random variables - Pa(X_i) are parents of X_i #### Undirected Graphs (Markov Random Fields) ```math P(X_1,...,X_n) = \frac{1}{Z}\prod_{C \in \mathcal{C}} \phi_C(X_C) ``` where: - C are maximal cliques - φ_C are potential functions - Z is partition function #### Factor Graphs ```math P(X_1,...,X_n) = \prod_{a \in F} f_a(X_{\partial a}) ``` where: - F is the set of factors - ∂a denotes variables connected to factor a ### 2. [[conditional_independence|Conditional Independence]] ```math X \perp Y | Z \iff P(X|Y,Z) = P(X|Z) ``` ### 3. [[markov_properties|Markov Properties]] #### Local Markov Property ```math X_i \perp X_V\backslash cl(i) | X_{ne(i)} ``` #### Global Markov Property ```math X_A \perp X_B | X_S ``` where S separates A and B in the graph ## Types of Models ### 1. [[bayesian_networks|Bayesian Networks]] ```julia struct BayesianNetwork <: ProbabilisticGraphicalModel nodes::Vector{Variable} edges::Vector{DirectedEdge} parameters::Dict{Variable, ConditionalProbability} end ``` Key features: - Directed acyclic graphs - Conditional probability tables - Causal interpretation ### 2. [[markov_random_fields|Markov Random Fields]] ```julia struct MarkovRandomField <: ProbabilisticGraphicalModel nodes::Vector{Variable} edges::Vector{UndirectedEdge} potentials::Dict{Clique, PotentialFunction} end ``` Key features: - Undirected graphs - Potential functions - Symmetric dependencies ### 3. [[factor_graphs|Factor Graphs]] ```julia struct FactorGraph <: ProbabilisticGraphicalModel variables::Vector{Variable} factors::Vector{Factor} edges::Vector{Edge} end ``` Key features: - Bipartite graphs - Explicit factor nodes - Message passing structure ## Inference Methods ### 1. [[exact_inference|Exact Inference]] ```julia function variable_elimination(model::ProbabilisticGraphicalModel, query::Variable, evidence::Dict{Variable, Any}) # Order variables order = elimination_order(model, query) # Initialize factors factors = collect_factors(model) # Eliminate variables for var in order if var != query && var ∉ keys(evidence) factors = eliminate_variable(factors, var) end end return normalize(multiply_factors(factors)) end ``` ### 2. [[approximate_inference|Approximate Inference]] #### Sampling Methods ```julia function importance_sampling(model::ProbabilisticGraphicalModel, query::Variable, evidence::Dict{Variable, Any}, n_samples::Int) samples = Vector{Float64}(undef, n_samples) weights = Vector{Float64}(undef, n_samples) for i in 1:n_samples sample = generate_sample(model, evidence) weights[i] = compute_weight(sample, evidence) samples[i] = sample[query] end return weighted_average(samples, weights) end ``` #### Variational Methods ```julia function variational_inference(model::ProbabilisticGraphicalModel, q_family::Distribution, max_iters::Int=100) # Initialize variational parameters θ = initialize_parameters(q_family) for iter in 1:max_iters # Compute expectations expectations = compute_expectations(model, q_family, θ) # Update parameters θ_new = update_parameters(expectations) # Check convergence if converged(θ, θ_new) break end θ = θ_new end return q_family(θ) end ``` ## Learning ### 1. [[parameter_learning|Parameter Learning]] #### Maximum Likelihood ```julia function learn_parameters!(model::ProbabilisticGraphicalModel, data::Matrix{Float64}) # For each parameter for param in model.parameters # Compute sufficient statistics stats = sufficient_statistics(data, param) # Update parameter update_parameter!(param, stats) end end ``` #### Bayesian Learning ```julia function bayesian_parameter_learning!(model::ProbabilisticGraphicalModel, data::Matrix{Float64}, prior::Distribution) # For each parameter for param in model.parameters # Compute posterior posterior = update_posterior(prior, data, param) # Update parameter distribution update_parameter_distribution!(param, posterior) end end ``` ### 2. [[structure_learning|Structure Learning]] #### Score-Based Learning ```julia function learn_structure!(model::ProbabilisticGraphicalModel, data::Matrix{Float64}, score_fn::Function) current_structure = empty_structure() current_score = score_fn(current_structure, data) while true # Generate candidate structures candidates = generate_candidates(current_structure) # Score candidates scores = [score_fn(c, data) for c in candidates] # Select best candidate best_idx = argmax(scores) if scores[best_idx] <= current_score break end current_structure = candidates[best_idx] current_score = scores[best_idx] end return current_structure end ``` ## Applications ### 1. [[probabilistic_reasoning|Probabilistic Reasoning]] - Medical diagnosis - Fault detection - Decision support systems ### 2. [[computer_vision|Computer Vision]] - Image segmentation - Object recognition - Scene understanding ### 3. [[natural_language_processing|Natural Language Processing]] - Part-of-speech tagging - Named entity recognition - Semantic parsing ## Best Practices ### 1. Model Selection - Choose appropriate model type - Consider computational requirements - Balance model complexity - Validate assumptions ### 2. Implementation - Use efficient data structures - Implement numerical safeguards - Cache intermediate results - Profile performance bottlenecks ### 3. Validation - Test with synthetic data - Cross-validate results - Monitor convergence - Analyze sensitivity ## References 1. Koller, D., & Friedman, N. (2009). Probabilistic Graphical Models 1. Bishop, C. M. (2006). Pattern Recognition and Machine Learning 1. Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective 1. Wainwright, M. J., & Jordan, M. I. (2008). Graphical Models, Exponential Families, and Variational Inference 1. Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems