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的凸函数, 因此求解对偶问题等价求解原始问题。

- 阅读剩余部分 -

二、最大熵模型

1. 条件最大熵的意义

条件熵函数是条件概率分布函数的度量，其概率分布越均匀，熵值越大。

$$ H(Y|X) = - \sum_{x, y} p(x, y) log \, p(y|x) $$

给定$ x $的情况下$ Y $的熵对于$ x $的期望越大，表示$ X $并未给$ Y $带来多少信息增益，也就是说$ X $对$ Y $决策帮助信息越少。这看似矛盾，因为我们需要的是根据$ X $对$ Y $分类。如果$ X $对$ Y $无帮助，那么分类毫无意义(此时$Y$均匀分布)。但在实际操作中$ X,Y $被特征函数强制约束(出现$ x $同时出现$ y $)。因此，最大熵其实只能把特征函数未约束的信息对$ Y $的影响均匀分布。

承认在已知信息（特征函数约束）以外可能有未知信息会对判断$y$造成影响。但无法确定未知信息会对识别每个$ y $的具体值造成何种影响，为了风险最小化，不对未知信息对$ Y $的决策影响做任何主观倾向假设,而是认为未知信息对所有$ y $的影响程度都是趋于相同的，于是风险被平摊。

例如，事件集合$ Y = \{y_1,y_2,y_3,y_4 \}; \sum^4_{i=1} p(y_i) = 1$, 已知$ P(Y=y_1) = 0.4 $, 那么在没有其他更多信息帮助下, 最大熵理论认为 $ P(Y=y_2) = P(Y=y_3) = P(Y=y_4) = ( 1.0 - P(Y=y_1) ) / 3 = 0.2 $。

- 阅读剩余部分 -

一、MEMM和HMM的比较

$ \require{AMScd} $

$$ \text{HMM} \\ \begin{CD} q_1 @>>> q_2 @. \cdots @. q_{t-1} @>>> q_t \\ @VVV @VVV @. @VVV @VVV \\ o_1 @. o_2 @. @. o_{t-1} @. o_t \end{CD} \\ p(Q,O)=\prod^T_{t=1}p(q_t|q_{t-1})p(o_t|q_t) \\ \quad \\ \quad \\ \text{MEMM} \\ \begin{CD} q_1 @>>> q_2 @. \cdots @. q_{t-1} @>>> q_t \\ @AAA @AAA @. @AAA @AAA \\ o_1 @. o_2 @. @. o_{t-1} @. o_t \end{CD} \\ p(Q|O) = \prod^T_{t=1} p(q_t | q_{t-1}, o_t) $$

- 阅读剩余部分 -

回顾一阶HMM

在一阶HMM中，下一个隐藏状态是当前隐藏状态的条件概率：
$$ P(q_{t+1} = S_j | q_t = S_i, q_{t-1} = S_k, \cdots ) \approx P(q_{t+1} = S_j | q_t = S_i) $$

即转移矩阵：
$$ A = [a_{ij}] \quad \text{where} \quad a_{ij} \equiv P(q_{t+1} = S_j | q_t = S_i) $$

且特定时刻观察状态只和当前隐藏状态有关。
$$ b_j(m) \equiv P(O_t = \nu_m | q_t = S_j) $$

即观测矩阵：
$$ B = [b_j(m)] \quad \text{where} \quad b_j(m) \equiv P(O_t = \nu_m | q_t = S_j) $$

二阶HMM

对于字序列标记分词，当前分词标记和上一个字的分词标记相关，这是二元组 Bigram，但分析样本发现切分位置并不一定只和上一个字相关，可能会有更长远的关系，比如假设当前字标记和之前两个字标记有关，那么就成为了三元组。即 $ Trigram $：

$$ P(q_{t+1} = S_j | q_t = S_i, q_{t-1} = S_k, \cdots ) \approx P(q_{t+1} = S_j | q_t = S_i, q_{t-1} = S_k) $$

同时还假设当前观测到的字符除和当前分词标记（隐藏状态）相关外，也与上一个隐藏状态相关：

$$ b_{ij}(m) \equiv P(O_t = \nu_m | q_t = S_j, q_{t-1} = S_i) $$

对应转移矩阵和观测矩阵也改动为：

$$ \begin{align} A &= [a_{ijk}] \quad \text{where} \quad a_{ijk} \equiv P(q_{t+1} = S_k | q_t = S_j , q_{t-1} = S_i ) \\ B &= [b_{ij}(m)] \quad \text{where} \quad b_{ij}(m) \equiv P(O_t = \nu_m | q_t = S_j , q_{t-1} = S_i) \end{align} $$

- 阅读剩余部分 -