3 向前向后算法

和HMM第一大问题相似，计算给定x,y序列的条件概率。

定义 $ \alpha_i(x) $为在时刻$ i $止之前所有时刻的所有可能$ y $取值联合当前$y_i$取值的非规范化概率。$ m=|y| $。类似再定义和$ \alpha $相反，从 $n+1$时刻开始的反向计算的向量$ \beta_i(x) $。

- 阅读剩余部分 -

2. 条件随机场

给定变量$ X $时无向图$ Y $的随机场。

$$ P(Y_v|X, Y_w \neq Y_v) $$

$ Y_W $ 是所有与$ Y_v $有连接的节点(考虑局部独立性，这里使得条件随机场的$ P(Y|X) $可描述为$ Y_v $的联合概率)。

- 阅读剩余部分 -

1. 概率无向图模型

概率无向图是指随机变量节点连接边没有方向的概率图模型, 其节点$ v \in V$表示随机变量，节点之间的边$ e \in E $表示随机变量之间的依赖关系。

$$ G=(V, E) $$

- 阅读剩余部分 -

6. limited memory graio newton

牛顿方法需要计算$ hessian $矩阵和其逆，为方便计算和减少内存使用，使用L_BFGS算法优化.

最大墒模型:

$$ \begin{align} p(y|x) &= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ Z_w(x) } \\ &= \frac{ \exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ \sum_y \exp \left[ \sum_{i=1} w_i f_i(x,y) \right] } \end{align} $$

目标优化函数：

$$ \begin{align} \min_w f(w) &= -\sum_{x,y} \tilde{p}(x,y) \log p(y|x) \\ &= \sum_{x} \tilde{p}(x) \log Z_w(x) - \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) \end{align} $$

梯度:
$$ \nabla f(w) = \left[\frac{\partial f(w)}{\partial w_1},\frac{\partial f(w)}{\partial w_2},\frac{\partial f(w)}{\partial w_3},\cdots \right]^T $$

$$ \frac{\partial f(w)}{\partial w_i} = \sum_{x,y} \tilde{p}(x) p_w(y|x) f_i(x,y) - \sum_{x,y} \tilde{p}(x,y) f_i(x,y) $$

- 阅读剩余部分 -

5. 最优化算法

1. IIS

最大熵模型：

$$ \begin{align} p(y|x) &= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ Z_w(x) } \\ &= \frac{ \exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ \sum_y \exp \left[ \sum_{i=1} w_i f_i(x,y) \right] } \end{align} $$

极大对数似然估计：

$$ \begin{align} L(w) &= \sum_{x,y} \tilde{p}(x,y) \log p(y|x) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) – \sum_{x} \tilde{p}(x) \log Z_w(x) \end{align} $$

改进的迭代尺度优化算法的思路，假设把现有参数$ w=(w_1,w_2,\cdots,w_n)^T $加上一个新的参数向量$ w + \delta =(w_1 + \delta_1,w_2 + \delta_2,\cdots,w_n + \delta_n)^T $，可以使得模型的对数似然增大，如果存在这样一个参数向量，那么重复$ \imath: w \to w + \delta $，直到模型似然最大化为止。

- 阅读剩余部分 -

3. 模型求解

使用$ Lagrange $将模型转换为无约束优化问题, 设乘子$ w = \{w_0,w_1,\cdots,w_n \} $。定义$ Lagrange $函数：

$$ \begin{align} L(P, w) &= -H(P) + w_0 \left[ 1 - \sum_y p(y|x) \right] + \sum_{i=1} w_i \left[ E_{\tilde{P}}(f_i) - E_P(f_i) \right] \\ &= \sum_{x, y} \tilde{p}(x) p(y|x) \log p(y|x) + w_0 \left[ 1 – \sum_y p(y|x) \right] \\ & \quad + \sum_{i=1} w_i \left[ \sum_{x,y} \tilde{p}(x,y) f_i(x,y) - \sum_{x,y} \tilde{p}(x) p(y|x) f_i(x, y) \right] \end{align} $$

原始问题和对偶问题分别为：

$$ \min_P \max_w L(P, w) \quad ; \quad \max_w \min_P L(P, w) $$

因$ Lagrange $函数$ L(P, w) $是P的凸函数, 因此求解对偶问题等价求解原始问题。

- 阅读剩余部分 -