probabilistic inference recap

given a probabilistic model, Probabilistic Inference is answering a probabilistic query over that model. It is also used for the computation/estimation of: distributions, the distribution’s parameters (if it’s a parametric distribution), the distribution’s probabilities, and/or the distribution’s characteristics

syntax definition

Click here to expand...

A graphical model 𝒢 is a tuple 𝒢 = ⟨𝐗, 𝐃, 𝐒, 𝐅, 𝐂⟩ where:

• 𝐗 = {𝑋₁, …, 𝑋_𝑛} set of ordered variables
• 𝐃 = {𝐷₁, …, 𝐷_𝑛} set of corresponding domains of each variable 𝑋_𝑖 (e.g. if 𝑋₁is a boolean variable then 𝐷₁= {true, false}). The size of each 𝐷_𝑖corresponds to the cardinality of variable 𝑋_𝑖
• 𝐒 = {𝑆₁, …, 𝑆_𝑚} set of variable scopes, where each variable scope 𝑆_𝑖is a subset of 𝐗 (i.e. 𝑆_𝑖 ⊆ 𝐗)
• 𝐅 = {𝐹₁, …, 𝐹_𝑚} set of factors/functions, where each factor/function 𝐹_𝑖 is defined over its corresponding variable scope 𝑆_𝑖and maps any assignment over its scope to a real value
  • in context of Bayesian Networks, 𝐅 = set of conditional probability tables
  • in context of Markov Networks, 𝐅 = set of factors
  • global function - is a function whose scope includes all variables (i.e. 𝑆_𝑖 = 𝐗)
  • local functions - is a function whose scope is a proper subset of variables (i.e. 𝑆_𝑖⊂ 𝐗)
• 𝐂 is a set of combination operators which defines how functions are combined. common combination operators are:
  • summation operator (𝛴)
  • multiplication operator (𝛱)
  • AND operator (∧) - for Boolean functions
  • relational join operator (⨝) - when the functions are relation
  • marginalization operator - for reasoning queries
  • max operator - e.g. = argmax_𝑦[ 𝐹_𝑖(𝑥,𝑦) ] = 𝐹_𝑗(𝑥) where 𝐹_𝑗is a new function with scope over variable 𝑥

the set of local functions can be combined in a variety of ways (e.g. combination operators) to generate a new local function or even a global function

Link to original

and let:

• 𝐐 = 𝑄₁, …, 𝑄_𝑟be the set of query variables
• 𝐄 = 𝐸₁, …, 𝐸_𝑠be the set of evidence variables
• 𝐇 = 𝐻₁, …, 𝐻_𝑡be the remainder of the variables(called the hidden variables (non-evidence, non-query variables))
• 𝐪 = 𝑞₁, …, 𝑞_𝑟be a grounded instantiation of 𝐐
• 𝐞 = 𝑒₁, …, 𝑒_𝑠be a grounded instantiation of 𝐄
• 𝐡 = 𝘩₁, …, 𝘩_𝑡be a grounded instantiation of 𝐇

𝑋, 𝐸, and 𝑌 are disjoint exhaustive sets of all variables 𝐗

therefore:

• the complete set of variables is 𝐗 = 𝐐 ∪ 𝐄 ∪ 𝐇 = {𝑋₁, …, 𝑋_𝑛} = {𝑄₁, …, 𝑄_𝑟, 𝐸₁, …, 𝐸_𝑠, 𝐻₁, …, 𝐻_𝑡}
• the complete set of instantiations is 𝒙 = 𝐪 ∪ 𝐞 ∪ 𝐡 = {𝑥₁, …, 𝑥_𝑛} = {𝑞₁, …, 𝑞_𝑟, 𝑒₁, …, 𝑒_𝑠, ℎ₁, …, ℎ_𝑡}

Link to original

representations

Click here to expand...

• Parametric Probability Distribution Models - function/model based
• Non-Parametric Probability Distribution Models - instance-based

see also: ML - Parametric vs Non-Parametric

• Univariate Probability Distribution Models

  • Continuous Models (Probability Density Functions)
  • Discrete Models (Probability Mass Functions)

• Multivariate Probability Distribution Models

  • Probabilistic Graphical Models (PGM)

• Multi-Model Probability Distribution

• representations of global structures

  • Probabilistic Graphical Models (PGM)

• representations of local structures

  • representations of normalized distributions:
    • Conditional Probability Distributions (CPD)
      • see: CPD Representations
  • representations of un-normalized distributions:
    • Potential Functions

Link to original

probability query types

Click here to expand...

• product comes from a joint probability 𝐏(𝐐=𝐪, 𝐇=𝐡, 𝐄=𝐞) being factorized into a product of conditional probabilities
• when we take the log of products it becomes sum of factors

Query	Product Sum	Marginalization𝛴	Maximization𝑎𝑟𝑔𝑚𝑎𝑥	Description
Posterior Conditional Query𝐏(𝐐=𝐪|𝐄=𝐞) = 𝛴𝐡∊𝐇[ 𝐏(𝐐=𝐪, 𝐇=𝐡, 𝐄=𝐞) ] / 𝐏(𝐄=𝐞) Belief Updating Query (a type of posterior conditional query)𝐏(𝑄𝑖=𝑞𝑖|𝐄=𝐞) = 𝛴𝐡∊𝐇[ 𝐏(𝑄𝑖=𝑞𝑖, 𝐇=𝐡, 𝐄=𝐞) ] / 𝐏(𝐄=𝐞)	✔	✔	✘	sum-product problem sum-log-sums problem
Prior Marginal Query𝐏(𝐐=𝐪) = 𝛴𝐡∊𝐇[ 𝐏(𝐐=𝐪, 𝐇=𝐡) ] Probability of Evidence Query𝐏(𝐄=𝐞) = 𝛴𝐡∊𝐇[ 𝐏(𝐇=𝐡, 𝐄=𝐞) ]	✔	✔	✘	sum-product problem sum-log-sums problem both queries essentially the same where 𝐐 = 𝐄 #P-Hard Problem
Maximum a Posterior (𝑴𝑨𝑷) Query𝑀𝐴𝑃(𝐐=?|𝐄=𝐞) = 𝑎𝑟𝑔𝑚𝑎𝑥𝐪[ 𝛴𝐡∊𝐇[ 𝐏(𝐐=𝐪, 𝐇=𝐡, 𝐄=𝐞) ] ] where: 𝐐∪𝐄⊂𝐗 and 𝐐∪𝐇∪𝐄=𝐗	✔	✔	✔	max-sum-product problem max-sum-log-sums problem most probable assignment because they include maximization NPPP-Hard Problem
Most Probable Explanation (𝑴𝑷𝑬) Query𝑀𝑃𝐸(𝐐=?|𝐄=𝐞) = 𝑎𝑟𝑔𝑚𝑎𝑥𝐪[ 𝐏(𝐐=𝐪, 𝐄=𝐞) ] where: 𝐐∪𝐄=𝐗	✔	✘	✔	max-product problem max-log-sums problem most probable assignment because they include maximization NP-Hard Problem

more details: Probabilistic Inference - Query／Task Types (Posterior Conditional - Prior Marginal ／ Probability of Evidence - MPE - MAP)

Link to original

resources:

Click here to expand...

• Daphne Koller’s Video Lectures

Link to original

Approximate Inference is a type of inference method used for the computation/estimation of distributions, their parameters, their probabilities, and/or distribution characteristics

related to:

• point estimation (inferential statistics) - given a sample of a population, we use sample statistics as estimates of population parameters
• simulating distributions

Approximate Inference Algorithm - Types

• deterministic/analytical approximations:
  • Inverse Transform Method - Smirnov Transform - only works if:
    • distribution is normalized (e.g. probability distribution)
    • we know the distribution’s cumulative distribution function and is invertible
• non-deterministic/sampling approximations & stochastic simulations:
  • Independent Sampling (Standard Monte Carlo Methods) - is where the next value sampled from a distribution is INDEPENDENT on the previous sample
  • Dependent Sampling (Markov Chain Monte Carlo (MCMC) Methods) is where the next value sampled from a distribution is DEPENDENT on the previous sample
  • Estimate
    • Approximation - estimating hidden target function/distribution
    • Approximation - estimating parameters of parametric distribution/population function/model
      • Maximum Likelihood Estimation (MLE) - maximizes the likelihood function
      • Maximum a Posteriori (MAP) - maximizes the posterior distribution
• search-based:
  • Monte Carlo Tree Search (MCTS)
• elimination/propagation:
  • junction graph
  • variational inference
  • generalized belief propagation
• w-cutset - combines search and elimination
• variational algorithms

Comparisons

• Importance Sampling (IS) vs Monte Carlo Markov Chains (MCMC)