Paper: Classical Probabilistic Models and Conditional Random Fields

先放出这篇论文的核心图：

熵

自信息量

一个事件本身所包含的消息量，由事件不确定性决定
随机事件 $x_i$ 发生概率为 $p(x_i)$ , 自信息量定义为

$$I(x_i) = -log\;p(x_i)$$

log以2为底,单位bit

信息熵

自信息量的期望，最短编码长度

$$H(X) = E[I(X)] = -\sum p(x_i) log\;p(x_i)$$

条件熵

给定X的条件下，Y 的信息熵还有多少

$$H(Y \mid X) = \sum_{x \in X}p(x)H(Y \mid X = x) \\ = -\sum_{x \in X}p(x)\sum_{y \in Y}p(y \mid x)log\;p(y \mid x) \\ = -\sum_{x \in X}\sum_{y \in Y}p(x, y)log\;p(y \mid x) \\ = -\sum_{x \in X}\sum_{y \in Y}p(x, y)log\;\frac{p(x, y)}{p(x)}$$

联合熵

X,Y同时发生的不确定性度量

$$H(X,Y) = -\sum_{x \in X}\sum_{y \in Y}p(x,y)log\;p(x,y)$$ $$H(X,Y) = H(X \mid Y) + H(Y)$$

互信息

信息增益, 给定Y,X不确定性减少的度量

$$I(X;Y) = H(X) - H(X \mid Y) = \sum_{x \in X}\sum_{y \in Y}p(x,y)log\frac{p(x,y)}{p(x)p(y)} = D(p(x,y) \parallel p(x)p(y))$$ $$I(X;Y) = I(Y;X)$$

交叉熵

用估计得q概率分布去编码,真实概率是p,得到的平均编码长度

$$H(p, q) = -\sum_{x}p(x)log\; q(x)$$

相对熵

KL散度，一定程度上看成两个随机变量距离的度量，编码长度不完美时平均编码长度得增大值

$$D(p \parallel q) = \sum_{x}p(x)log \frac{p(x)}{q(x)} = H(p,q) - Entropy(p)$$

我们希望最小化相对熵,因为真实概率 是固定得，等价于最小化交叉熵，等价于MLE(这个要回去看一下deep learning5.5)

最大熵原理

Principle of maximum entropy: :the probability distribution which best represents the current state of knowledge is the one with largest entropy, in the context of precisely stated prior data
By Wiki

条件最大熵模型

(这里论文里叫最大熵模型,但我查了一下最大熵似乎是model p(x)的原理都一样，这个是条件最大熵模型)
也叫softmax回归模型(另一角度),是一种条件概率模型(判别式模型),根据最大熵原理我们选择

$$p^* (y \mid x) = \underset{p(y \mid x) \in P}{argmax}\;H(y \mid x)$$

P是所有和训练集“一致”的概率分布，如何定义”一致”如下：

给定训练集 $\Gamma = \{(x_1,y_1),\ldots,(x_N,y_N)\}$ 和 m个特征函数 $f_i(x,y) \in \{0, 1\}$
那么特征函数估计得期望是

$$\tilde{E}[f_i] = \sum_{(x,y) \in X \times Y}\tilde{p}(x,y)f_i(x,y) = \frac{1}{N}\sum_{(x,y) \in \Gamma}f_i(x,y)$$

其中 $\tilde{p}(x,y)$ 简单得用训练集中出现得次数来估计
真实的 特征函数期望值是

$$E[f_i] = \sum_{(x,y) \in X \times Y}p(x,y)f_i(x,y) = \sum_{(x,y) \in X \times Y}p(x)p(y \mid x)f_i(x,y)$$

往往x的可能取值很多,而集合Y比较小, 为了有效得计算期望，我们重写成上面的形式之后，用训练集中x的分布逼近真实的x分布得到

$$E[f_i] \approx \sum_{(x,y) \in X \times Y}\tilde{p}(x)p(y \mid x)f_i(x,y) = \frac{1}{N}\sum_{x \in \Gamma}\sum_{y \in Y}p(y \mid x)f_i(x,y)$$

“一致” 的概率分布需要满足：

$$\tilde{E}[f_i] = E[f_i]$$ $$p(y \mid x) \ge 0 \; \forall x,y$$ $$\sum_{y \in Y}p(y \mid x) = 1$$

拉格朗日乘子法得

$$L(p, \vec{\lambda}) = H(y \mid x) + \sum_{i = 1}^m \lambda_i(E[f_i] - \tilde{E}[f_i]) + \lambda_{m+1}(\sum_{y \in Y}p(y \mid x) - 1)\tag{1}$$

和前面同样的，条件熵如下近似

$$H(y \mid x) \approx - \sum_{(x,y) \in X \times Y}\tilde{p}(x)p(y \mid x)log\;p(y \mid x) = - \frac{1}{N}\sum_{x \in \Gamma}\sum_{y \in Y}p(y \mid x)log\;p(y \mid x)$$ $$\nabla_{p(y \mid x)}L = -\tilde{p}(x)(1 + log\;p(y \mid x)) + \sum_{i=1}^m \lambda_i \tilde{p}(x)f_i(x,y) + \lambda_{m + 1} = 0$$

推出

$$p(y \mid x) = \mathrm{exp}(\sum_{i=1}^m \lambda_i f_i(x,y))\; \mathrm{exp}(\frac{\lambda_{m + 1}}{\tilde{p}(x) } - 1)$$

应用（1）式子得到

$$p(y \mid x) = \mathrm{exp}(\sum_{i=1}^m \lambda_i f_i(x,y))\; \frac{1}{\sum_{y \in Y}\mathrm{exp}(\sum_{i=1}^m \lambda_i f_i(x,y))}$$

是一个log-linear的模型，概率图模型就是Naive Bayes图模型(有向)的无向图版本…其中exp可以看作因子图中的势能函数，能量函数是特征函数的线性加权

条件随机场

也是一种直接建模条件概率的无向图模型，可以看作条件最大熵的sequence版本,并且不限制于HMM的线性结构
观察变量 $\vec{x} = \{x_1,\ldots,x_n\}$ ,预测变量/隐变量 $\vec{y} = \{y_1, \ldots, y_n\}$

根据无向图的因子图中联合概率的形式

$$p(\vec{v}) = \frac{1}{Z}\prod_{C}\Phi_C(\vec{v}_C)$$

我们推导出条件概率的形式为

$$p(\vec{y} \mid \vec{x}) = \frac{p(\vec{x},\vec{y})}{p(\vec{x})} \\ = \frac{p(\vec{x},\vec{y})}{\sum_{\vec{y}'}p(\vec{x},\vec{y}')} \\ = \frac{\prod_{C}\Phi_C(\vec{x}_C,\vec{y}_C)}{\sum_{\vec{y}'}\prod_{C}\Phi_C(\vec{x}_C,\vec{y}'_C)} \\ = \frac{1}{Z(\vec{x})}\prod_{C}\Phi_C(\vec{x}_C,\vec{y}_C)$$

(??这就叫条件随机场了)

Linear-chain CRFs

隐变量是链式结构 ,假设链长 n + 1

那么

$$p(\vec{y}\mid \vec{x}) = \frac{1}{Z(\vec{x})}\prod_{j = 1}^n \Phi_j(\vec{x},\vec{y})$$

定义势函数的形式是

$$\Phi_j(\vec{x},\vec{y}) = \mathrm{exp}(\sum_{i=1}^m \lambda_i f_i(y_{j-1},y_j,\vec{x},j))$$

所以

$$p_{\vec{\lambda}}(\vec{y}\mid \vec{x}) = \frac{1}{Z_{\lambda}(\vec{x})}\prod_{i=1}^m \mathrm{exp}(\sum_{i=1}^m \lambda_i f_i(y_{j-1},y_j,\vec{x},j))$$

因为最大团模板只有一个 $C = \{\Phi_j(y_j,y_{j-1},\vec{x})\mid \forall j \in \{1,\ldots,n\}\}$ 所以可以用一个全连接的SFSA(stochastic finite state automaton) 来表示（这里不是特别明白）

对于高阶的linear-CRF 特征需要涉及前k个隐变量序列

##### maximum-likelihood
防止过拟合，加入惩罚项

$$L(\vec{\lambda}) = \sum_{(\vec{x},\vec{y}) \in \Gamma}log\;p(\vec{y}\mid \vec{x}) - \sum_{i=1}^m \frac{\lambda_i^2}{2\sigma^2}\\ = \sum_{(\vec{x},\vec{y}) \in \Gamma}\left[ log(\frac{exp(\sum_{j=1}^n\sum_{i=1}^m \lambda_if_i(y_{j-1},y_j,\vec{x},j))}{\sum_{\vec{y}' \in Y}exp(\sum_{j=1}^n\sum_{i=1}^m\lambda_i f_i(y'_{j-1},y'_j,\vec{x},j))}) \right] - \sum_{i=1}^m \frac{\lambda_i^2}{2\sigma^2}$$ $$\frac{\partial{L}}{\partial{\lambda_k}} = \sum_{(\vec{x},\vec{y}) \in \Gamma}\sum_{j=1}^nf_k(y_{j-1},y_j,\vec{x},j) + \sum_{(\vec{x},\vec{y}) \in \Gamma}\sum_{\vec{y}' \in Y}p_{\lambda}(\vec{y}' \mid \vec{x})\sum_{j=1}^nf_k(y'_{j-1},y'_j,\vec{x},j) - \frac{\lambda_k}{\sigma^2}$$

可以从偏导项看出是一个凹函数(????中间的那一项怎么理解)

$$\tilde{E}(f_i) = \sum_{(\vec{x},\vec{y}) \in \Gamma}\sum_{j=1}^n f_i(y_{j-1},y_{j},\vec{x},j)$$ $$E(f_i) = \sum_{(\vec{x},\vec{y}) \in \Gamma}\sum_{\vec{y'} \in Y}p(\vec{y}'\mid \vec{x})\sum_{j=1}^n f_i(y'_{j-1},y'_{j},\vec{x},j)$$

这里省去了前面的常数 $\frac{1}{N}$ , 不影响结果

$$\frac{\partial{L}}{\partial{\lambda_k}} = \tilde{E}[f_k] - E[f_k] - \frac{\lambda_k}{\sigma^2}$$

但是因为 $\vec{y} \in Y$ 可能的所有取值太多了，所以用forward-backward来方便的计算 $E[f_i]$
##### inference
算法就是Viterbi算法

---

• Previous
  HMM
• Next
  Linux简单命令