• local markov prop: any 2 nodes conditionally indep given parents' values
• edges usu repr causality but not required (either dir)
• plates: for repeating sub vars
• eg naive bayes, neural nets
• markov blanket: neighbors; parents, children, children's parents
  • every node is conditionally indep of all other nodes in network given blanket
• dynamic bayesian network: for sequences of vars, eg time series
  • eg HMMs, kalman filter, SMC

• reprs some things bayes nets can't (cyclic deps) & vice versa (induced deps)
• eg log-linear models, gaussian markov random field TODO
• must satisfy pairwise, local, global markov props TODO
• conditional random fields TODO

• bipartite hypergraph representing factorization of a function TODO

Inverse transform sampling

• Intuition: given ability to generate random numbers in [0,1] i.e. sample uniform $U(0,1)$, if you know the target distribution’s CDF $F$, go backward by mapping an output point on the range (which, since it’s a probability CDF, is always in [0,1]) to the input domain.

  • The “steep” parts are where there’s greatest density in the PDF.

• Derivation

  • Say $X$ is target distribution random variable, $U$ is uniform random variable, $F_A$ is CDF of any RV $A$, and $T$ is the transformation we want on $U$ to turn it into $X$. Note $P[U<a]=a$ for any $a\in[0,1]$. Then:

  $$ F_X(x)=P[X<x]=P[T(U)<x]=P[U<T^{-1}(x)]=T^{-1}(x) $$

  • So $F_x(x)=T^{-1}(x)$ i.e. $T(x)=F_X^{-1}(x)$! Thus, transform of uniform into $X$ is the inverse of the CDF.

• But you need the CDF. Many real world problems don’t have this. And then you need to invert it too.

Accept-reject sampling aka rejection sampling: simple, sample the same domain with an easy-to-sample distribution, and accept the sample with probability p_target(x) / p_surrogate(x).

• Don’t know target $p(s)$ but know it’s $f(s)/N_C$ and don’t know $N_C$ the normalizing constant (requires integrating everywhere).
• First choose easy to sample $g(s)$. Doesn’t need to be similar to $f(s)$ but helps. Scale it up by $M$ so that it’s actually strictly bigger than $f(s)$ everywhere.
• Repeatedly sample from $g(s)$, accepting with prob $\frac{f(s)}{M g(s)}$.
• But inefficient. Often $M$ must be huge, lots of wasted space.

Importance sampling

markov chain monte carlo (MCMC): general family of algorithms

• Intuition: accept-reject sampling treats samples independently, but inefficient. If we successfully sampled recently, then we next sample should be close by, because maybe we’re in a good place.
• Idea: stationary distribution should be the target distribution. We’ll get there and settle there eventually. Throw away the initial samples (”burn in” samples). Keep only the later ones, since those are what actually represent $p(x)$.
• How the chain evolves up to more specific algorithms.
• TODO taxonomy: http://brenocon.com/blog/2013/04/monte-carlo-algorithm-inputs/
• http://www.ams.org/journals/bull/2009-46-02/S0273-0979-08-01238-X/S0273-0979-08-01238-X.pdf
• variational bayes TODO
  • deterministic
• TODO BUGS, JAGS, Metropolis-Hastings

Gibbs sampling: MCMC; sample from multidimensional distribution by sampling from conditionals along each dimension

• Special cast of Metropolis-Hastings

• E.g. 2D normal: pick some initial $x,y$, then sample $p(x\mid y)$ then vice versa. Assumes sampling $p(x \mid y)$ easier than $p(x,y)$.

• Doesn’t work when can’t move along any single dimension to arrive at other density islands

  

• Inefficient when mostly low density, hard to arrive at high density bubbles, and then won’t leave

  

Metropolis Hastings Monte Carlo (MHMC): most popular MCMC algorithm

• Intuition: like accept-reject but with MCMC statefulness. Target dist is $f$. Sample from some distribution $g(X_{t+1} \mid X_t)$, say, the normal centered at last point $\mathcal{N}(X_t, \sigma^2)$. (Move nearby.) Then accept with some prob $A = \max(1, \frac{f(b)}{f(a)} \frac{g(a\mid b)}{g(b\mid a)})$.
• Intuition: always accept next state if it’s higher prob. Reject next state proportionally to how much of a drop it is: $p(b)/p(a)$.
• Metropolis: more specifically for when $g$ is symmetric
• aka random walk

Hamiltonian Monte Carlo (HMC): MCMC; intuition is, flip the pdf, simulate a frictionless object falling down the slopes, occasionally randomly kick it out of minima (source)

No U-Turn Sampler (NUTS): a HMC method; used in STAN, Pyro

• rejection sampling: fwd sampling, discard where $E\ne e$
  • $P(E=e)$ usu prohibitively small; too many samples required
• fwd sampling generally infeasible for markov networks; no "roots"

• num words ~ Poisson
• topic mix ~ Dirichlet (over fixed set of topics)
• to generate a word:
  • topic ~ doc's multinomial of topics
  • word ~ topic's multinomial of words