Uncertainty Modelling in AI

All materials are from Module CS5340 (NUS Computing)

PGM (Probabilistic Graphical Modeling)

• gain global insight based on local observations

Key Ideas:

• Represent the world as a collection of random variables $X_1,\cdots ,X_N$ with joint distribution $p(X_1,\cdots ,X_N)$

• Learn the distribution from data.

• Perform “inference” (compute conditional distributions ($p(X_i|X_1=x_1,\cdots ,X_N=x_N)$).

Introduction

Probability space

Three parts:

• Outcome space $\mathrm{\Omega }$: space of possible outcomes
• Event space $E$: $E\subseteq 2^{\mathrm{\Omega }}$, subset of power set of $\mathrm{\Omega }$
  • contains empty $\mathrm{\varnothing }$ and trivial event $\mathrm{\Omega }$
  • closed under union. if $\alpha ,\beta \in E$, so is $\alpha \cup \beta$
  • closed under complement. if $\alpha \in E$, So is $\mathrm{\Omega }-\alpha$
• Probability distribution $P$: mapping from events in $E$ into real values
  • Non negativity
  • sum to 1
  • Mutually disjoint events: if $\alpha ,\beta \in E$, and $\alpha \cap \beta =\mathrm{\varnothing }$, then $P(\alpha \cup \beta )=P(\alpha )\cup P(\beta )$.

Probability distribution:

• $X$: random variables. $x$: generic values [$x\in Val(X)$].

• Indicator Random Variables: map every outcome to 0 or 1.: Just indication

• Discrete vs.. continuous

  • Discrete:
    • PMF (Probability mass function): $p(x)$
  • Continuous:
    • PDF (Probability Density function) : $p(x):R\to R_{\ge 0}$
    • $P(X)$ is a cumulative function

Probability:

• Joint probability:

Basic operations

Marginalization

Recover probability distribution of any variable in a joint distribution by integrating (or summing) over all other variables.

$$p(x)=\int p(x,y)dy;p(y)=\int (x,y)dx$$

$p(x)=\sum _{y}p(x,y);p(y)=\sum _x(x,y)$

Conditional probability

$p(x|Y=y^{\ast })$

can be extracted from joint probability.

$P(x|Y=y^{\ast })=\frac{p(x,Y=y^{\ast })}{\underset{x}{\int }p(x,Y=y^{\ast })dx}=\frac{p(x,Y=y^{\ast })}{p(Y=y^{\ast })}$

i.e. $p(x|y)=\frac{p(x,y)}{p(y)}$

So, $p(x,y)=p(x|y)p(y)=p(y|x)p(x)$ : chain rule of product rule

Bayes rule

$$p(x|y)p(y)=p(y|x)p(x)⟹p(y|x)=\frac{p(x|y)p(y)}{p(x)}=\frac{p(x|y)p(y)}{\int p(x,y)dy}=\frac{p(x|y)p(y)}{\int p(x|y)p(y)dy}$$

Independence

independence of X and Y means that every conditional distribution is the same.

when variables are independent, $p(x,y)=p(x|y)p(y)=p(x)p(y)$

Expectation

$E[f(x)]=\sum _{x}f(x)p(x)\text{or}\int f(x)p(x)dx$

$E[f(x)+g(x)]=E[f(x)]+E[g(x)]$

$E[f(x)g(x)]=E[f(x)]E[g(x)]$(if X, Y independent)

Probability Distribution

Data Type	Domain	Distributions	PDF(PMF)	Parameter
Univariate, discrete, binary	$x\in 0,1$	Bernoulli	$p(x)={\lambda }^x(1-\lambda {)}^{1-x}$	$\lambda$
Univariate, discrete, multi-valued	$x\in 1,2,\cdots ,K$	Categorical	$p(\mathbb{x})=\prod _{k=1}^K{\lambda }_k^{x_k}={\lambda }_k$	$\lambda =[{\lambda }_1,\cdots ,{\lambda }_K{]}^T$, where $\lambda \ge 0$, $\sum _k{\lambda }_k=1$
Univariate, continuous, unbounded	$x\in R$	Univariate normal (Gaussian)	$p(x	\mu,\sigma^2)=\frac{1}{\sqrt{2\pi\sigma^2}} \exp -\frac{(x-\mu)^2}{2\sigma^2}$
Univariate, continuous, bounded	$x\in [0,1]$	Beta	$p(x)=\frac{\mathrm{\Gamma }[\alpha +\beta ]}{\mathrm{\Gamma }[\alpha ]\mathrm{\Gamma }[\beta ]}{x}^{\alpha -1}(1-x{)}^{\beta -1}$	$\alpha$, $\beta$
Multivariate, continuous, unbounded	$\mathbf{x}\in {\mathbb{R}}^D$	Multivariate normal	$\frac{1}{(2\pi)^{D/2}	\boldsymbol{\Sigma}
Multivariate, continuous, bounded, sum to 1	$\mathbf{x}=[x_1,x_2,\cdots ,x_K{]}^T$, $x_k\in [0,1]$, $\sum _{k=1}^K{x}_k=1$	Dirichlet	$p\left(\mathbb{x}\right)=\frac{\mathrm{\Gamma }\left[\sum _{k=1}^K{\alpha }_k\right]}{\prod _{k=1}^K\mathrm{\Gamma }\left[{\alpha }_k\right]}\prod _{k=1}^K{x}_k^{{\alpha }_k-1}$	${\alpha }_k$ (k个)
Bivariate, continuous, $x_1$ unbounded, $x_2$ bounded below	$\mathbf{x}=[x_1,x_2]$, $x_1\in \mathbb{R}$, $x_2\in {\mathbb{R}}^{+}$	Normal-scaled inverse gamma
Multivariate vector $\mathbf{x}$ and matrix $\mathbf{X}$. $\mathbf{x}$ Unbounded, $\mathbf{X}$ square, positive definite	$\mathbf{x}\in {\mathbb{R}}^K$, $\mathbf{X}\in {\mathbb{R}}^{K\times K}$, ${\mathbf{z}}^T\mathbf{X}\mathbf{z}>0\mathrm{\forall }\mathbf{z}\in {\mathbb{R}}^K$	Normal inverse Wishart

• Conjugate Distributions

  • Parameters of conjugate distributions are known as hyperparameters because they control the parameter distribution

  • Aim: Learning the parameters $\theta$ of a probability distribution:

    ​ $$p(\theta |x)=\frac{p(x|\theta )p(\theta )}{\int p(x|\theta )p(\theta )d\theta }$$

    • $p(\theta )$: prior. $p(x|\theta )$: likelihood. $p(\theta |x)$: posterior
    • Use prior and likelihood to compute posterior. Posterior has the same form as prior $⟶$ conjugate

  • 使用共轭先验的原因是，可以使得先验分布和后验分布的形式相同，这样符合人的直观感受，另一方面，是可以形成一个先验链，即现在的后验分布可以作为下一次计算的先验分布，也就是带来了计算的简单性。

  • 使得Bayes inference更加方便， 比如在 sequential Bayesian inference中，得到一个observation之后，可以算出一个posterior。由于选取的是conjugate prior，因此posterior和prior的形式一样，可以把该posterior当作新的prior，用于下一次的observation，继续下一次迭代。

  Distribution	Domain	Prior	Prior Distribution	hyper parameters
  Bernouli	$x\in 0,1$	Beta	$p(\lambda )=\frac{\mathrm{\Gamma }[\alpha +\beta ]}{\mathrm{\Gamma }[\alpha ]\mathrm{\Gamma }[\beta ]}{\lambda }^{\alpha -1}(1-\lambda {)}^{\beta -1}$, $\lambda \in [0,1]$	$\alpha$, $\beta$
  Binomial	$x\in 0,1,\cdots ,n$	Beta	$p(\lambda )=\frac{\mathrm{\Gamma }[\alpha +\beta ]}{\mathrm{\Gamma }[\alpha ]\mathrm{\Gamma }[\beta ]}{\lambda }^{\alpha -1}(1-\lambda {)}^{\beta -1}$, $\lambda \in [0,1]$	$\alpha$, $\beta$
  Categorical	$x\in 1,2,\cdots ,K$	Dirichlet	$p({\lambda }_1,\dots ,{\lambda }_K)=\frac{\mathrm{\Gamma }\left[\sum _{k=1}^K{\alpha }_k\right]}{\prod _{k=1}^K\mathrm{\Gamma }\left[{\alpha }_k\right]}\prod _{k=1}^K{\lambda }_k^{{\alpha }_k-1}$	k 个 ${\alpha }_k>0$
  Univariate normal (Given Variance, mean unknot)		Univariate normal
  Univariate normal (Given Mean, Variance unknown)		Gamma
  Univariate normal (Both Variance and Mean unknown)	$x\in \mathbb{R}$	normal inverse gamma	$p(\mu ,{\sigma }^2)=\frac{\sqrt{\gamma }}{\sigma \sqrt{2\pi }}\frac{{\beta }^{\alpha }}{\mathrm{\Gamma }[\alpha ]}{\left(\frac{1}{{\sigma }^2}\right)}^{\alpha +1}\exp [-\frac{2\beta +\gamma (\delta -\mu {)}^2}{2{\sigma }^2}]$	$\alpha ,\beta ,\gamma >0,\text{and}\delta \in \mathbb{R}$
  Multivariate normal	$\mathbf{x}\in {\mathbb{R}}^k$	normal inverse Wishart	$p(\boldsymbol{\mu}, \boldsymbol{\Sigma})=\frac{\gamma^{D / 2}	\mathbf{\Psi}

  Gamma Function:

  $\mathrm{\Gamma }(z)={\int }_0^{\mathrm{\infty }}{t}^{z-1}{e}^{-t}dt,z\in \mathbb{C}$;

  $\mathrm{\Gamma }(n)=(n-1)!,n\in {\mathbb{Z}}_{>0}$

  Binomial distribution: $p(x)=\left(\begin{array}{l}nx\end{array}\right){\lambda }^x(1-\lambda {)}^{n-x}$

  Categorical distribution: $p(\mathbb{x})=\prod _{k=1}^K{\lambda }_k^{x_k}={\lambda }_k$

  https://zhuanlan.zhihu.com/p/26638720

Fitting Probability Models

we already know some common parametric probability distributions $p(x|\theta )$.

Now, we need to know how to learn unknown parameters $\theta$ from given data $\mathcal{D}=x[1],\cdots ,x_{[}N]$. Then, use these parameters to make prediction.

Learning

Methods to learning the unknown parameters $\theta$ from data

Maximum Likelihood Estimation (MLE)

• Given data $\mathcal{D}=x[1],\cdots ,x_{[}N]$

• Assume:

  • distribution $p_{\theta }:\theta \in \mathrm{\Theta }$ where $p(\theta )=p(x|\theta )$
  • $\mathcal{D}$ is sampled from $X_{1}, X_{2}, \ldots, X_{N} \sim p_{\theta^{}}$forsome$\theta^ \in \Theta$
  • Random variables $X_1,X_2,\dots ,X_N$ are i.i.d

• Goal: estimate ${\theta }^{\ast }$

• Method: estimate ${\theta }_{MLE}$ is a maximum likelihood estimate (MLE) for ${\theta }^{\ast }$ if

  ​ $$\begin{array}{rlrl}{\theta }_{MLE}& =\underset{\theta \in \mathrm{\Theta }}{\mathrm{argmax}}[p(\mathcal{D}|\theta )]& =\underset{\theta \in \mathrm{\Theta }}{\mathrm{argmax}}[p(x|\theta )]& =\underset{\theta }{\mathrm{argmax}}[\prod _{i=1}^{N}p(x[i]|\theta )](\text{ i.i.d })⟶\text{decompose into products of likelihoods}\end{array}$$

• Solution: maximize the logarithm ${\theta }_{MLE}=\underset{\theta }{\mathrm{argmax}}[\log (\prod _{i=1}^{N}p(x[i]|\theta ))]$. Then, solve by taking derivative w.r.t. $\theta$ equal to 0.

• Advantages:

  • Easy and fast to compute
  • Nice Asymptotic properties**:**
    • Consistent: if data generated from $f({\theta }^{\ast })$, MLE converges to its true value, ${\hat{\theta }}_{MLE}\to {\theta }^{\ast }$ as $n\to \mathrm{\infty }$
    • Efficient: there is no consistent estimator that has lower mean squared error than the MLE estimate
  • Functional Invariance: if $\hat{\theta }$ is the MLE of ${\theta }^{\ast }$, and $g({\theta }^{\ast })$is a transformation of ${\theta }^{\ast }$ then the MLE for $\alpha =g({\theta }^{\ast })$ is $\hat{\alpha }=g(\hat{\theta })$

• Disadvantages:

  • MLE is a point estimate i.e., does not represent uncertainty over the estimate
  • MLE may overfit.
  • MLE does not incorporate prior information.
  • Asymptotic results are for the limit and assumes model is correct.
  • MLE may not exist or may not be unique
  • not know uncertainty of the parameter estimation

Bayesian Approach

To model uncertainty of the parameter estimation

Fitting: Instead of a point estimate $\hat{\theta }$, compute the posterior distribution over all possible parameter values using Bayes’ rule:

​ $$p(\theta |D)=\frac{\prod _{i=1}^{N}p(x[i]|\theta )p(\theta )}{p(D)}$$

Principle: why pick one set of parameters? There are many values that could have explained the data. Try to capture all of the possibilities.

Model:

• Goal: Model Uncertainty over $\theta$ using prior distribution

• Method: find posterior

  ​ $p(\theta |D)=\frac{\prod _{i=1}^{N}p(x[i]|\theta )p(\theta )}{p(D)}$

  ​ $p(\theta |x)=\frac{\prod _{i=1}^{N}p(x[i]|\theta )p(\theta )}{p(x)}=\frac{\prod _{i=1}^{N}p(x[i]|\theta )p(\theta )}{\int \prod _{i=1}^{N}p(x[i]|\theta )p(\theta )d\theta }$

  ​ where

  ​ $\prod_{i=1}^{N} p(x[i] | \theta) p(\theta)=\prod_{i=1}^{N} \operatorname{Norm}{x[i]}\left[\mu, \sigma^{2}\right] \underbrace{\operatorname{NormlnvGam}{\mu, \sigma^{2}}[\alpha, \beta, \gamma, \delta]}_{\text{conjugate prior}}$ifweuseGuassianasourobservationmodel,i.e.$p(x|\theta)$

Properties:

• models uncertainty over parameters.
• incorporating prior information
• can derive quantities of interest, $p(x<10|D)$
• can perform model selection.

Drawbacks:

• Need Prior
• Computationally intractable
• If initial belief not conjugate to normal likelihood.. bad

Maximum a Posterior Estimation (MAP)

Given: data $D=x[1],\cdots ,x[N]$

Assume:

• joint distribution $p(D,\theta )$
• $\theta$ is a random variable

Goal: Choose “good” $\theta$

Method:

• estimate ${\theta }_{MAP}$ is a maximum a posterior (MAP) estimation if

  $$\begin{array}{rlrl}{\theta }_{MAP}& =\underset{\theta }{\mathrm{argmax}}[p(\theta |D)]& =\underset{\theta }{\mathrm{argmax}}\left[\frac{p(D|\theta )p(\theta )}{p(D)}\right]\text{Bayes’ rule}\mathrm{\&}=\underset{\theta }{\mathrm{argmax}}\left[\frac{\prod _{i=1}^{N}p(x[i]|\theta )p(\theta )}{p(D)}\right]\text{i.i.d}& =\underset{\theta }{\mathrm{argmax}}[\prod _{i=1}^{N}p(x[i]|\theta )p(\theta )]p(D)\text{ is removed since it is independent of}\theta \end{array}$$

• $ \theta_{MAP} = \underset{\theta}{\operatorname{argmax}}\left[ \prod_{i=1}^N \underbrace{ p(x[i]|\theta)}{\text{likelihood}} \underbrace{p(\theta)}{\text{prior}} \right] $

• maximize the logarithm. Then taking derivatieves and setting to zero $⟶$ parameters estimation

Results:

• more data points $\to$ MAP is closer to MLE
• Less data points $\to$ MAP is closer to Prior

key steps:

1. Prior distribution

2. Derive
   $$\mathcal{L}=\log p(D|\theta )p(\theta )=\log p(D|\theta )+\log p(\theta )$$

3. Then set $\frac{\text{part}L}{\text{part}{\theta }_i}=0$ for each parameter ${\theta }_i$

Properties:

• Fast and easy
• incorporate prior information
• Avoid overfitting (“regularization”) ?
• As $n\to \mathrm{\infty }$, MAP tends to look like MLE, but not have same nice asympototic properties.

Drawbacks:

• Point estimation (like MLE)
  • not capture uncertainty over estimates
• NEED to choose Prior.
• Not functionally invariant:
  • if $\hat{\theta }$ is the MLE of ${\theta }^{\ast }$, and $g({\theta }^{\ast })$ is a transformation of ${\theta }^{\ast }$, then the MAP for $\alpha =g({\theta }^{\ast })$ is not necessarily $\hat{\alpha }=g(\hat{\theta })$

Prediction

• MLE / MAP: evaluate new data point under parameter learnt by MLE /MAP.

• Bayesian: calculate weighted sum of predictions from all possible values of parameters:
  $$
  \begin{aligned} p\left(x^{} | \mathcal{D}\right) &=\frac{p\left(x^{}, D\right)}{p(D)} \quad \text{(conditional probability)} \ &=\frac{\int p\left(x^{}, D, \theta\right) d \theta}{p(D)} \quad \text{(marginal probability)} \ &=\frac{\int p\left(x^{}, \theta | D\right) p(D) d \theta}{p(D)} \quad \text{(conditional probability)} \ &=\int p\left(x^{} | D, \theta\right) p(\theta | D) d \theta \quad \text{(conditional probability)} \ &=\int p\left(x^{} | D\right) p(\theta | D) d \theta \quad \text{(conditional independence)} \end{aligned}
  $$

• Predictive Density

  • $$
    p\left(x^{} | D\right)=\int \underbrace{p\left(x^{} | \theta\right)}{\text{weights}} \underbrace{p(\theta | D) d \theta}{\text{prediction for each possible}\ \theta}
    $$

    Make a prediction that is an infinite weighted sum (integral) of the predictions for each parameter value, where weights are probabilitys.

    consider MLE and MAP estimates as probability distributions with zero probability everywhere except at estimate

Training data decrease, Bayesian become less certain, but MAP is wrongly overconfident.

Exponential Family

exponential family:

• a set of probability distributions $p_{\theta }:\theta \in \mathrm{\Theta }$ with the form
  $$p_{\theta }(x)=\frac{h(x)\exp [-\eta (\theta {)}^{\mathrm{\top }}s(x)]}{Z(\theta )}$$
  Where

  • $\theta \in {\mathbb{R}}^k,x\in {\mathbb{R}}^d$
  • natural parameters $\eta (\theta ):\mathrm{\Theta }\to {\mathbb{R}}^m$
  • sufficient statistics: $s(x):{\mathbb{R}}^d\to {\mathbb{R}}^m$
  • base measure (supporting and scaling) : $h(x):{\mathbb{R}}^d\to [0,\mathrm{\infty })$
  • partition function: $Z(\theta ):\mathrm{\Theta }\to [0,\mathrm{\infty })$

an exponential family is in its natural (canonical 标准的) form if it is parameterized by its natural parameters $\eta$ :
$$p_{\eta }(x)=p(x|\eta )=\frac{h(x)\exp [-{\eta }^{\mathrm{\top }}s(x)]}{Z(\eta )}$$
Normaliser: $Z(\eta )$
$$Z(\eta )=\int h(x)\exp [-{\eta }^{\mathrm{\top }}s(x)]dx$$
Properties:

• has conjugate prior.
• fixed number of sufficient statistics that summarize iid data. 指数函数的充分统计量的可以从大量的i.i.d.数据中归结为估计的几个值（即 $s(x)$ )
• Posterior predictive distribution always has closed form solution
• 共轭先验性质给出了后验概率分布的闭式解，否则我们需要求解复杂的积分。而且，共轭先验使得我们能够清楚的看到似然函数对概率分布的影响。

For any ExpFam:
$$\mathbb{E}[s(x)]=\mathrm{\nabla }\log \mathrm{Z}(\eta )$$

• 通过对$Z(\eta )$求导，容易得到充分统计量$s(x)$的均值，方差和其他性质。

Important Properties:

Many distributions are Exponential Family:

PMF	PDF
• Bernoulli • Binomial
• Categorical/Multinoulli
• Poisson
• Multinomial
• Negative Binomial • Negative Binomial	• Normal • Gamma & Inverse Gamma
• Wishart & Inverse Wishart
• Beta
• Dirichlet
• lognormal
• Exponential
•…

Bayesian Networks

Conditional Independence

Fitting probability models (learning) and predictive density (inference)

• BUT just at the case of One random variables, i.e. $p(x|\theta )$
• How about joint probability with $N$ random variables?

Problem:

• Assume $N$ discrete random variables $x_1,\cdots ,x_N$, where $x_i\in 1,\cdots ,K$. $⟶$ need $O(K^N)$ parameters to represent the joint distribution $p(x_1,\cdots ,x_N)$ $⟶$ hard to infer, need huge amount of data to learn all parameters

• If all random variables are independent $⟶$ $O(NK)$ with $p(x_1,\cdots ,x_N|\theta )=\prod _{i=1}^{N}p(x_i|{\theta }_i)$ $⟶$ can infer, smaller data

###Definition:

Two random variables $X_A$ and $X_C$ are conditionally independent given $X_B$, $X_A\perp X_C|X_B$ iff $p(x_A,x_C|x_B)=p\left(x_A|x_B\right)p\left(x_C|x_B\right)$ OR $p(x_A|x_B,x_C)=p\left(x_A|x_B\right),\mathrm{\forall }{X}_B:p\left(x_B\right)>0$, which means learning $X_C$ does not change prediction of $X_A$ once we know the value of $X_B$.

###Meanings:

• parameter reduction
  • let $m_i$ denotes the number of parents of node $X_i$, and each node takes on $K$ values.
  • conditional probability of $X_i$ use $K^{m_i+1}$ parameters
  • Sum for all nodes, parameter reduction from $O(K^N)$ to $O(K^{m+1})$, and $m\ll N$

Learning with conditional independence: MLE

1. represent the joint probability distribution

2. Taking the logarithm of $p(x|\theta )$ converts the product into sums

3. find the maximum log-likelihood of each parameter ${\theta }_i$ . this can be executed seperatively.

   $\underset{{\theta }_1}{\mathrm{argmax}\log p(x|\theta )}$, $\underset{{\theta }_2}{\mathrm{argmax}\log p(x|\theta )}$, $\cdots$, [other random varibles which independent of $\theta -1$ can be removed.]

Learning with conditional independence: MAP

Similar as MLE:
$$\text{Missing or unrecognized delimiter for left}$$
where $\theta =({\theta }_1,\dots ,{\theta }_M)$

Bayesian Networks

• Bayesian Network is a DAG $\mathcal{G}$ (no cycle)

  • node is variables $X_i$, set of parent nodes $X_{{\pi }_i}$: all variables that are parents of $X_i$
  • Topological ordering: if $X_i\to X_j$, then $i<j$ [not unique]

• Path: {path follow the arrows cosidering direction}. V.S. Trail: {path follow the edges without considering the direction}

• Ancestors: parents, grand-parents , etc. V.S. Descendants: children, grand-children, etc.

• Local Markov assumption :

  • Each random variable $X_i$ is independent of its non-descendants $X_{nonDesc(X_i)}$ given its parents $X_{{\pi }_i}$

  • $$\text{Missing or unrecognized delimiter for left}$$

  • Given parents, $X_i$ 与 非后代 $X_{nonDesc(X_i)}$ 独立。

  • Then, conditional probability $p\left(x_i|x_{{\pi }_i}\right),i=1,\cdots ,N$ [according to local parent-children relationship]

Joint probability: Product of all local conditional independence
$$p(x_1,\dots ,x_N)=\prod _{i=1}^{N}p\left(x_i|x_{{\pi }_i}\right)$$
​ because $p(x_1,\dots ,x_N)=p\left(x_1\right)\prod _{i=2}^{N}p\left(x_i|x_{x_1,\dots ,x_{i-1}}\right)\text{ (chain rule) }$

a fully connected DAG can represent any distribution over its random variables.

Interprete arrows as “possible dependence”

Interpreting/Analyzing Bayesian Networks

• already know the conditional independence based on local parent-children relationship.
• hope to know other extra independece

Methods：

1. prove $p(x_A,x_C|x_B)=p\left(x_A|x_B\right)p\left(x_C|x_B\right)$ OR $p(x_A|x_B,x_C)=p\left(x_A|x_B\right),\mathrm{\forall }{X}_B:p\left(x_B\right)>0$ for $X_A\perp X_C|X_B$
2. Graph seperation

Graph seperation

Precise definition of “blocking” has to be done through the “three canonical 3-node graphs”, and “d-separation”.

Three canonical 3-node graphs:

• Head-Tail

  • if none variables are observed, A and B are not independent $A\text{notperp}B|\mathrm{\varnothing }$
    $$p(a,b)=p(a)\sum _{c}p(c|a)p(b|c)=p(a)p(b|a)$$

  • if C observed, using Bayes’ rule, obtain $A\perp B|C$
    $$\begin{array}{rlrl}p(a,b|c)& =\frac{p(a,b,c)}{p(c)}& =\frac{p(a)p(c|a)p(b|c)}{p(c)}& =p(a|c)p(b|c)\end{array}\text{ (Bayes rule) }$$

    

  • Intuition: past A is independent of future B given present C, $\to$ simple Markov Chain

• Tail-Tail

  • If none variables are observed, NOT independent, $A\text{notperp}B|\mathrm{\varnothing }$

  • If C observed, obtain $A\perp B|C$ , because

  • $$\begin{array}{rlr}p(a,b|c)& =\frac{p(a,b,c)}{p(c)}& =p(a|c)p(b|c)\end{array}$$

  • Then,

    

• Head-Head

  • if none variables observed, we obtain $A\perp B|\mathrm{\varnothing }$ because
    $$p(a,b)=p(a)p(b)$$

  • if C observed, we obtain $A\text{notperp}B|C$ , because
    $$\begin{array}{rlr}p(a,b|c)& =\frac{p(a,b,c)}{p(c)}& =\frac{p(a)p(b)p(c|a,b)}{p(c)}\end{array}$$
    ​ can not obtain $p(a)p(b)$

    

  • “V-structure”.

  • if C unobserved, “blocks”. If C observed, “unblocks”.

  • 

  • Observation of any descendent node of C “unblocks” the path from A to B.

  $A\perp B|C$ if all trails from nodes in A are “Blocked” from nodes in B when all C are observed.

  A is d-separated form B by C

• Key: Independence:

  1. The arrows on the trail meet either head-to-tail or tail-to-tail at the node, and the node is in the set C, or
  2. The arrows meet head-to-head at the node, and neither the node, nor any of its descendants, is in the set C.

Bayes Ball

• it’s a “reachability” algorithm”:

  1. shade the nodes in set $C$ (given nodes)
  2. Place a ball at each of the nodes in set $A$
  3. Let the balls “bounce around” the graph according to the d-separation rules:
     • if none of the balls reach B, then $A\perp B|C$
     • Else $A\text{norperp}B|C$

• can be implement as a breadth-first search

• procedure of algorithm:

  • given Graph $G$ and sets of nodes $X,Y$, and $Z$
  • Output True if $X\perp Y|Z$, False otherwise.
  • 2 Phases:
    • Phase 1: “Find all the unblocked v-structures”
      • traverse the graph from the leaves to the roots, marking all nodes that are in $Z$ or have descendants in $Z$.
    • Phase 2: “Traverse all the trails starting from $X$”
      • apply breadth-first-search, stopping a specific traversal when we hit a blocked node.
      • If $Y$ is reached during. this traversal, return False. Else, return True.

Bayes Network Examples:

Linear Regression

• Model:

  • $$Y[i]={\mathbf{w}}^{\mathrm{\top }}\mathbf{x}[i]+ϵ[i]$$

  • where input vector: $\mathbf{x}[i]=\left[\mathrm{x}[i]{1}, \mathrm{x}[i]{2}, \ldots, \mathrm{x}[i]{\mathrm{D}}\right]^{\top}$;coeffiecientvector:$\mathbf{w}=\left[w{1}, w_{2}, \ldots, w_{D}\right]^{\top}$;noise:$\epsilon[i] \sim N\left(0, \sigma_{n}^{2}\right)$

  • $⟹$

  • if $ϵ\sim N(0,{\sigma }_n^2)$ , then $Y\sim N({\mathbf{w}}^{\mathrm{\top }}\mathbf{x},{\sigma }_n^2)$

  • Affine property of Gaussian:

    • $f(x)=ax+b$ of Gaussian, $\to$ , new PDF $\mathcal{N}(a\mu +b,a^2{\sigma }^2)$

  • Independence assertion:
    $$Y[i]\perp Y[i+1]|\mathbb{x}[i],\mathbb{w},{\sigma }_n^2$$
    write the factorization:
    $$p(y[1],\cdots ,y[N])=\prod _i^{N}p(y[i]|{\mathbb{w}}^{\mathrm{\top }}\mathbb{x}[i],{\sigma }_n^2)$$

  • Problem: Assume we know ${\sigma }_n^2$, how to learn unknown parameter $\mathbb{w}$?

    • Approach 1: MLE

    $${\theta }_{MLE}=\underset{\theta }{\mathrm{argmax}}[\prod _{i=1}^{N}p(x[i]|\theta )]\text{iid}$$

    ​ with $p(x|\mu ,{\sigma }^2)={\mathrm{Norm}}_x[\mu ,{\sigma }^2]=\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp -\frac{(x-\mu {)}^2}{2{\sigma }^2}$

    ​ logarithm, and compute derivate for $\mathbb{w}$
    $$\log \prod _{i=1}^{N}p(y[i]|{\mathbb{w}}^{\mathrm{\top }}\mathbb{x}[i],{\sigma }_n^2)=\sum _{i=1}^N\log \mathcal{N}([i]|{\mathbb{w}}^{\mathrm{\top }}\mathbb{x}[i],{\sigma }_n^2)\propto -\sum _{i=1}^N\frac{(y[i]-{\mathbb{w}}^{\mathrm{\top }}x[i]{)}^2}{2{\sigma }_n^2}$$
    ​ So,
    $$\underset{\theta }{\mathrm{argmin}}\sum _{i=1}^N\frac{(y[i]-{\mathbb{w}}^{\mathrm{\top }}x[i]{)}^2}{2{\sigma }_n^2}=\frac{1}{2{\sigma }_n^2}\underset{\theta }{\mathrm{argmin}}(\mathbf{Y}-{\mathbf{X}}^{\mathrm{\top }}\mathbb{w}{)}^{\mathrm{\top }}(\mathbf{Y}-{\mathbf{X}}^{\mathrm{\top }}\mathbb{w})$$
    ​ Set $\mathcal{L}(\mathbb{w})=\mathbf{Y}-{\mathbf{X}}^{\mathrm{\top }}\mathbb{w}{)}^{\mathrm{\top }}(\mathbf{Y}-{\mathbf{X}}^{\mathrm{\top }}\mathbb{w})$
    $$\mathrm{\nabla }\mathcal{L}(\mathbb{w})=({\mathbb{w}}^{\mathrm{\top }}({\mathbf{X}}^{\mathrm{\top }}\mathbf{X})-{\mathbf{Y}}^{\mathrm{\top }}\mathbf{X})=0\text{so,}\mathbb{w}=(\mathbf{X}\mathrm{\top }\mathbf{X}{)}^{-1}{\mathbf{X}}^{\mathrm{\top }}\mathbf{Y}$$
    对ppt有疑问，手写的那一页， p41 

• **Model Uncertainty of $\mathbb{w}$ **

  • Model:

    

    • $p(\mathbf{w}|v)=N(\mathbf{0},v\mathbf{I})$

    • Conditional independence assertation:
      $$p(y[1],\dots ,y[N],\mathbf{w})=p(\mathbf{w}|v)\prod _i^{N}p(y[i]|{\mathbf{w}}^{\mathrm{\top }}\mathbf{x}[i],{\sigma }_n^2)$$

  • Problem: assume know ${\sigma }_n^2$, MAP solution of $\mathbb{w}$

    • Same as MLE, derivative, equal to 0.

    • $$\mathbb{w}=({\mathbf{Y}}^{\mathrm{\top }}\mathbf{X}+2\lambda {)}^{-1}{\mathbf{X}}^{\mathrm{\top }}\mathbf{Y},\text{where}\lambda =\frac{{\sigma }_n^2}{v}$$

    • if prior is laplacian distribution: $p(\mathbb{w}|0,b)=\frac{1}{2b}\exp (-\frac{|w|}{b})$

      • $\log p(\mathbb{w}|0,b)\propto -\frac{|w|}{b}$ , then, have $\lambda =-\frac{2{\sigma }_n^2}{b}$ , form $l_1$-norm.

    • derivative of $l_0$-norm: This is zero (as you pointed out), but only in places where it isn’t interesting. Where it is interesting it’s not differentiable (it has jump discontinuities).

    • derivative of $l_1$-norm: This norm is not differentiable with respect to a coordinate where that coordinate is zero. Elsewhere, the partial derivatives are just constants, $\pm 1$ depending on the quadrant.

    • derivative of $l_2$-norm: Usually people use the $l_2$-norm squared so that it’s differentiable even at zero. The gradient of $||x|{|}^2$ is $2x$, but without the square it’s $\frac{x}{||x||}$ (i.e. it just points away from zero). The problem is that it’s not differentiable at zero.

• Predictive DGM Model

  

Naiive Bayes

• Model:

  • Class $c\in 1,\dots ,K$, and input $\mathbf{x}={[x_1,x_2,\dots ,x_D]}^{\mathrm{\top }}$

  • naiive bayes assume that $p(\mathbf{x}|c)=\prod _{j}p\left(x_j|c\right)$. Naive assumption: all features are independent

    

  • Filled dots are deterministic parameters. If we have priors, we can make parameters random variables (open circles)

    $⟹$

  • Even the assumption for naiive bayes is so strong, it still works well?

    • Key idea: it works well when the local feature dependencies between the two classes “cancel out”.

##Properties of Bayesian network

• Independence-Maps (I-maps)

  • Theorem:

    Let $P$ be a joint distribution over $\mathcal{X}$ and $G$ be a Bayesian Network structure over $\mathcal{X}$. If $P$ factories according to $G$, then the local independence assertation ${\mathcal{J}}_l(G)\subseteq \mathcal{J}\mathcal{(}\mathcal{P}\mathcal{)}$.

    • The local Markov independence $\mathcal{J}l(G)$isthesetofallbasicconditionalindependenceassertionsoftheform$\left{X{i} \perp\left(X_{\text { nondesc }\left(x_{i}\right)} \backslash X_{\pi_{i}}\right) | X_{\pi_{i}}\right}$

  • Proof:

    • $\mathcal{J}l(G)\subseteq \mathcal{J(P)}$means$p(X_i|X\setminus X_i)=p(X_i|X{\pi_i})$$$\text{Missing or unrecognized delimiter for left}$$

    • So, $\text{Missing or unrecognized delimiter for left}$

• Global Markov independence:

  • Definition: the set of all independencies that correspond to d-seperation in graph $G$ is the set of global Markov independencies:
    $$\text{Missing or unrecognized delimiter for left}$$

  • Soundness:

    • Definition: if a distribution $P$ factorizes according to $G$, then ${\mathcal{J}}_l(G)\subseteq \mathcal{J}\mathcal{(}\mathcal{P}\mathcal{)}$.
    • i.e. two nodes are d-separated given $Z$, they are conditionally independent given $Z$.

  • Completeness:

    • Definition: $P$ is faithful to $G$ if for any conditional independence $(X\perp Y|Z)\in \mathcal{J}(P)$, then ${\mathrm{dsep}}_G(X;Y|Z)$.
    • i.e. any independence can be reflect as a d-separation.
    • Definition: weak completeness
    • Definition: almost completeness

  • How Powerful:

    Can find a Bayes network to $G$ represent all conditional independencies for a given $P$?

    • Minimal I-map: “no redundant edges”
    • perfect map:

    No

  

Undirected Graphical Models (Markov Random Fields)

##Undirected Graphical Models:

UGM (MRF) or (Markov Network) is graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, set of nodes and set of undirected edges

• Parameterization: via factors.

  • Factor $\phi (\mathcal{C})$ function map from set of variables to non-negative numbers.

• Factorization:

  • $$p(x_1,\dots ,x_N)=\frac{1}{Z}\prod _{j=1}^M{\phi }_j\left({\mathcal{C}}_j\right)$$

    DGM is $p(x_1,\dots ,x_N)=\prod _{i=1}^{N}p\left(x_i|x_i\right)$

  
  • just like DGM, UGM encode a set of conditional independence assertions.

• Conditional Independence:

  • 3 Markov properties of UGMs:

    1. Global Markov Property

       • $X_A\perp X_B|X_C$ iff $C$ separates $A$ from $B$.
       • NO trails connect $A$ and $B$ when remove all nodes in $C$.

    2. Local Markov Property

       • Markov Blanket $\mathrm{mb}(X_s)$: set of nodes that renders a node $X_s$ conditionally independent of all the other nodes:
         $$\text{Missing or unrecognized delimiter for left}$$

       • Markov blanket in UGM is the set of immediate neighbors

         • node 和除了本身以及neighbors 的其他node 都 conditionally independent. {due to global Markov property}

         Markov Blankets for a node $X_s$ in a DGM is the set of node’s parents, children, and co-parents (other parents of children).

         对ppt有疑问， p35 

    3. Pairwise Markov Property

       • two nodes $X_s$ and $X_t$ are conditionally independent given the rest if there is no direct edge between them
         $$\text{Missing or unrecognized delimiter for left}$$
         移除其他nodes后无直接连线

  • relationship among three properties.

    • Interrelated.

    • Global Markov $⟹$ local Markov $⟹$ Pairwise Markov $⟹$ Global Markov

      
      • for positive distribution $p(\mathbb{x})>0$, the three Markov properties are equavalent.

Parameterization of MRFs

Aim: obtain a local parameterization of UGMs.

For DGM:

• Local conditional probabilities: $p(x_i|x_{{\pi }_i})$

• Joint probability is product of local conditional probabilities: $p(x_1,\dots ,x_N)=\prod _{i=1}^{N}p\left(x_i|x_{{\pi }_i}\right)$

But for UGM, difficult to obtain conditional probabilities since no topological ordering. So, discard conditional probabilities.

Represent the joint as a product of local functions.

• Normalize
• Factors NOT represent marginal/conditional distributions

Gibbs distribution

• Definition: A distribution $P$ is a Gibbs distribution parameterized by a set of factors ${\varphi_1(\mathcal{C}1), \varphi_2(\mathcal{C}2),\cdots, \varphi_m(\mathcal{C}m)}$,where$$
  p\left(x{1}, x{2}, \ldots, x{N}\right)=\frac{1}{Z} \prod_{j=1}^{M} \varphi_{j}\left(\mathcal{C}_{j}\right)
  $$

• Factor:

  Two nodes $X_i$ and $X_j$ that are not directly linked in UGM are conditionally independent given all other nodes. [不直接相连的nodes是条件独立的]

  $\to$ Factorization of joint probability that places $X_i$ and $X_j$ in different factors.

  All nodes $X_C$ in a maximal clique $C$ in UGM form factor (local function) $\phi (X_C)$

  • Clique: a fully connected subset of nodes.
  • Maximal Clique $C$: cliques that cannot be extended to include additional nodes

  Hammersley-Clifford: a positive distribution $p(y)>0$ satisfies the CI properties of undirected graph $\mathcal{H}$ iff $p$ can be represented as a product of factors, one per maimal clique:

  • $$
    p(\mathbf{y} | \boldsymbol{\theta})=\frac{1}{Z(\boldsymbol{\theta})} \prod_{c \in \mathcal{C}} \psi_{c}\left(\mathbf{y}{c} | \boldsymbol{\theta}{c}\right)
    $$

    where $\mathcal{C}$ is the set of all the maimal liques; ${\phi }_C(\cdot )$ is the factor or potential function of clique $c$; $\theta$ is the parameter of factors ${\phi }_C(\cdot )$ for $c\in \mathcal{C}$; $Z(\mathit{\theta })$ is the partition function $Z(\boldsymbol{\theta}) \triangleq \sum \prod\limits_{c \in \mathcal{C}} \psi_{c}\left(\mathbf{y}{c} | \boldsymbol{\theta}{c}\right)$.

    UGM NOT specify a unique factorization.

    Hammersley-Clifford is just one type of factorization.

  Pairwise MRF:

  • parameretization to the edges of the graph, rather than maximal cliques. [每条边作为factor，不考虑maximal clique]
  • SIMPLE but not general.

• Properties:

  • Independent set; Independence map (I-map);

  • Soundness

    • if $P$ is a Gibbs distribution over $H$, then $H$ is an I-map for $P$.
      • Hammersley-Clifford states that if $H$ is an I-map for $P$, then $P$ is a Gibbs distribution over $H$ (for positive distribution)

  • Weak completeness

    • if $X$ and $Y$ are not separated in $H$, then there is some distribution $P$ that factories over $H$ where $X$ and $Y$ are dependent.

  • How Powerful: ? represent all conditional independencies ?

    • Perfect map: $\mathcal{J}(G)=\mathcal{J}(P)$

      

    • UGM are NOT “richer” or “more powerful” than DGM.

  

• representing Potential (local) function

  • Log potentials is a linear function of parameters:

  • $$
    \log \psi_{c}\left(\mathbf{y}{c}\right) \triangleq \phi{c}\left(\mathbf{y}{c}\right)^{T} \boldsymbol{\theta}{c}
    $$

    ${\varphi }_C(y_C)$ is a feature vector derived from the values of the variables $y_C.$

    Then, log probability is
    $$
    \log p(\mathbf{y} | \boldsymbol{\theta})=\sum_{c} \phi_{c}\left(\mathbf{y}{c}\right)^{T} \boldsymbol{\theta}{c}-\log Z(\theta)
    $$
    also called “maximum entropy” or “log-linear” model.

• every MRF is an [exponential family](#Exponential Family).

Example of MRF

Model:

• Ising and Potts (Depth Map from Stereo Images (Multi) or Binary Image Denosing)

$$\begin{array}{r}p(y,x|J,\theta )=p(\mathbf{y}|J)\prod _{t}p(x_t|y_t,\mathit{\theta })=\left[\frac{1}{Z(J)}\underset{\text{Pairwise Potential}}{\underbrace{\prod _{s\sim t}\psi (y_s,y_t;J)}}\right]\underset{\text{Unary potential}}{\underbrace{\prod _{t}p(x_t|y_t,\theta )}}\end{array}$$ 其实不太懂why 

Parameter Learning

UGM (MRF) in log-linear form, where $c$ indexes the cliques:
$$
p(\mathbf{y} | \boldsymbol{\theta})=\frac{1}{Z(\boldsymbol{\theta})} \exp \left(\sum_{c} \boldsymbol{\theta}{c}^{T} \boldsymbol{\phi}{c}(\mathbf{y})\right)
$$
The scaled log-likelihood is given by
$$
\ell(\boldsymbol{\theta}) \triangleq \frac{1}{N} \sum_{i}^{N} \log p\left(\mathbf{y}{i} | \boldsymbol{\theta}\right)=\frac{1}{N} \sum{i}^{N}\left[\sum_{c} \boldsymbol{\theta}{c}^{T} \boldsymbol{\phi}{c}\left(\mathbf{y}_{i}\right)-\log Z(\boldsymbol{\theta})\right]
$$

• belongs to exponential family,

• convex function in $\theta$, so can find unique global maximum by gradient-based optimizers.

• $$
  \frac{\partial \ell}{\partial \boldsymbol{\theta}{c}}=\frac{1}{N} \sum{i}^{N}\left[\boldsymbol{\phi}{c}\left(\mathbf{y}{i}\right)-\frac{\partial}{\partial \boldsymbol{\theta}_{c}} \log Z(\boldsymbol{\theta})\right]
  $$

  对ppt有疑问， p96， 怎么求的导？ 

• for exponential family distribution:

  • $$\mathbb{E}[s(x)]=\mathrm{\nabla }\log Z(\eta )$$

  • if $s(x)=x$ (natural exponential family), we can find moments of $x$ simply by differentiation.

  • the derivative of the log partition function w.r.t. ${\theta }_c$ is the expectation of the $c^{th}$ feature under the model:

  • $$\frac{\partial \log Z(\mathit{\theta })}{\partial {\theta }_c}=\mathbb{E}[{\varphi }_c(\mathbf{y})|\mathit{\theta }]=\sum _{\mathbf{y}}{\varphi }_c(\mathbf{y})p(\mathbf{y}|\mathit{\theta })$$

  • Proof:

  • $$
    \begin{align}
    \frac{\partial \log Z(\theta)}{\partial \theta_{c}} &= \frac{1}{Z(\theta)} \frac{\partial Z(\theta)}{\partial \theta_{c}}, \quad \text { where } \quad Z(\theta) = \sum_{y} \exp \left(\sum_{c} \theta_{c}^{T} \phi_{c}(y)\right)\
    \Rightarrow \frac{\partial Z(\theta)}{\partial \theta_{c}} &= \sum_{y} \exp \left(\sum_{c} \theta_{c}^{T} \phi_{c}(y)\right) \phi_{c}(y)\
    \Rightarrow \frac{\partial \log Z(\theta)}{\partial \theta_{c}} &= \frac{1}{Z(\theta)} \sum_{y} \phi_{c}(y) \exp \left(\sum_{c} \theta_{c}^{T} \phi_{c}(y)\right) =\sum_{y} \phi_{c}(y) \underbrace{\frac{1}{Z(\theta)} \exp \left(\sum_{c} \theta_{c}^{T} \phi_{c}(y)\right)}{p(y|\theta)} = \sum{y} \phi_{c}(y) p(y | \theta)
    \end{align}
    $$

  • So, the gradient of the log-likelihood is

  • $$
    \frac{\partial \ell}{\partial \boldsymbol{\theta}{c}}=\left[\underbrace{\frac{1}{N} \sum{i}^{N} \boldsymbol{\phi}{c}\left(\mathbf{y}{i}\right)}{\text{Clamped term}}\right] - \underbrace{\mathbb{E}\left[\boldsymbol{\phi}{c}(\mathbf{y})\right]}_{\text{Unclamped/contrastive term}}
    $$

    Clamped term: $y$ is fixed to its observed values; Unclamped/contrastive term: $y$ is a free variable.

    Unclamped term requires inference in the model, once per gradient step, and this makes UGM learning much slower than DGM.

  • Gradient of log-likelihood rewrite:

  • $$\frac{\partial l}{\partial {\theta }_c}=E_{p_{emp}}[{\varphi }_c(y)]-E_{p(y|\theta )}[{\varphi }_c(y)]$$

    • $E_{p_{emp}}[{\varphi }_c(y)]=\frac{1}{N}\sum _{n=1}^N{\varphi }_c\left(y_i\right)$ : Expected feature vector according to empirical distribution.
    • $E_{p(y|\theta )}[{\varphi }_c(y)]$ : Expected feature vector according to model’s distribution.

    At optimum, gradient =0, i.e. $E_{p(y|\theta )}[{\varphi }_c(y)]=\sum _y{\varphi }_c(y)p(y|\theta )$. But this equation cannot solve for unknown $\theta$.

  • Solution: Gradient-based optimizers.

  • $$\frac{\partial l}{\partial {\theta }_c}=E_{p_{emp}}[{\varphi }_c(y)]-E_{p(y|\theta )}[{\varphi }_c(y)]$$

    But, when computing $E_{p(y|\theta )}[{\varphi }_c(y)]$ requires sum over all states of $y$ , which is intractable.

  • Solution: combine approximate inference with gradient-based learning. i.e. Stochastic Maximum Likelihood

• Stochastic Maximum Likelihood:

  iteratively updates the parameter ${\theta }_{k+1}$ at the $k$ step using the parameter and gradient from previous step:
  $${\theta }_{k+1}\leftarrow {\theta }_k-\eta g_k$$
  where $\eta$ is step size or learning rate, $g_k\approx \frac{\text{part}l}{\text{part}{\theta }_C}$ is the gradient that can be approximated with Markov Chain Monte Carlo (MCMC), sampling.

  

• Maximum A posterior (MAP):

  • add prior:

  • $$\text{Missing or unrecognized delimiter for left}$$

    Choose prior with hyper-parameters.

Conditional Random Fields (CRF)

CRF or discriminative random field

• a version of MRF where all the clique potentials are conditioned on input feature $X$:

• $$p(\mathbf{y}|\mathbf{x},\mathbf{w})=\frac{1}{Z(\mathbf{x},\mathbf{w})}\prod _c{\psi }_c({\mathbf{y}}_c|\mathbf{x},\mathbf{w})$$

  • Log-linear representation of potentials:

  • $$
    \psi_{c}\left(\mathbf{y}{c} | \mathbf{x}, \mathbf{w}\right)=\exp \left(\mathbf{w}{c}^{T} \boldsymbol{\phi}\left(\mathbf{x}, \mathbf{y}_{c}\right)\right)
    $$

    where $\varphi (\mathbb{x},y_C)$ is a feature vector derived from the global inputs $X$ and the local set of labels $Y_C$.

  

• Advantages: (compare to generative models)

  • No need to waste resources, i.e. modelling things that we can always observe.
    • Focus our attention on modeling what we care about, i.e. the distribution of labels given the data.
  • We can make the potentials (or factors) of the model be data-dependent.
    • e.g., in natural language processing problems, we can make the latent labels depend on global properties of the sentence, such as which language it is written in.

• Disadvantages:

  • require labeled training data
  • learning is slower.

• Parameter learning:

  Consider CRF in log-linear form:
  $$
  p(\mathbf{y} | \mathbf{x}, \mathbf{w})=\frac{1}{Z(\mathbf{x}, \mathbf{w})} \prod_{c} \exp \left(\mathbf{w}{c}^{T} \phi{c}\left(\mathbf{x}, \mathbf{y}{c}\right)\right)
  $$
  where $\phi{c}\left(\mathrm{x}, y_{c}\right)$isafeaturevectorderivedfromtheglobalinputs$\mathbb{x}$andthelocalsetoflabels$y_c$.

  Scaled log-likelihood:
  $$
  \begin{aligned} \ell(\mathbf{w}) & \triangleq \frac{1}{N} \sum_{i}^{N} \log p\left(\mathbf{y}{i} | \mathbf{x}{i}, \mathbf{w}\right) =\frac{1}{N} \sum_{i}^{N}\left[\sum_{c} \mathbf{w}{c}^{T} \boldsymbol{\phi}{c}\left(\mathbf{y}{i}, \mathbf{x}{i}\right)-\log Z\left(\mathbf{w}, \mathbf{x}{i}\right)\right] \end{aligned}
  $$Gradient:$$
  \frac{\partial \ell}{\partial \mathbf{w}{c}} =\frac{1}{N} \sum_{i}^{N}\left[\boldsymbol{\phi}{c}\left(\mathbf{y}{i}, \mathbf{x}{i}\right)-\frac{\partial}{\partial \mathbf{w}{c}} \log Z\left(\mathbf{w}, \mathbf{x}{i}\right)\right] =\frac{1}{N} \sum{i}^{N}\left[\boldsymbol{\phi}{c}\left(\mathbf{y}{i}, \mathbf{x}{i}\right)-\mathbb{E}\left[\boldsymbol{\phi}{c}\left(\mathbf{y}, \mathbf{x}{i}\right)\right]\right]
  $$
  ​ Need labeled pairs of data $(y_i,x_i){i=1}^N$forlearning.And$\mathbb{E}\left[\boldsymbol{\phi}{c}\left(\mathbf{y}, \mathbf{x}{i}\right)\right] =\sum_{\mathbb{y}, \mathbb{x}{i}} p\left(\mathbb{y} | \mathbb{x}{i}, \mathbb{w}\right) \boldsymbol{\phi}{c}\left(\mathbb{y}, \mathbb{x}{i}\right)$

  • depend on inputs ${\mathbb{x}}_i$
  • Need inference for every single training case inside each gradient step, which is $O(N)$ times slower than MRF.
  • Also use MAP to estimate unknown parameter $\text{Missing or unrecognized delimiter for left}$ by choosing a prior.

Probabilistic inference

calculate $p(X_F|X_E)$ for arbitrary subset $E$ and $F$

---

黑体