二、最大熵模型

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} $$

- 阅读剩余部分 -

之前的分词算法都需要附带词表，最大概率法需要计算词频，对于词表中不存在的新词，算法效果并不是很好。HMM是基于字统计的分词算法。无需词表，无需统计词频。对新词识别友好。

HMM用于分词的原理。

基于字标注词语切分

共同创造美好的新世纪
共同 创造 美好 的 新世纪

用字母B表示词语开始，M表示词语中间，E表示词语结束，S表示独立成词。那么上面的切分以字为单位重新标注

$$ \begin{array}{cccccccccccccc} B & E & \quad & B & E & \quad & B & E & \quad & S & \quad & B & M & E \\ 共 & 同 & \quad & 创 & 造 & \quad & 美 & 好 & \quad & 的 & \quad & 新 & 世 & 纪 \end{array} $$

- 阅读剩余部分 -

最大概率法分词是在最大匹配分词算法上的改进。在某些语句切分时，按最大长度切分词语可能并不是最优切分。而不按最优长度切分词语，则同一语句会出现多种切分结果。计算每种切分结果的概率，选取概率最高的切分作为最优分词切分。

- 阅读剩余部分 -

正向最大匹配分词和逆向最大匹配分词

词表

词表为所有可能出现的词语组成的集合。当然，实践中不可能准备包含全所有已知和未知词语词表。

建立词表

1. 从人工标注语料中得到词表。
   由多人讨论并且得到共识的分词标注语料建立词表。这是效果最好，但也是成本最高的方案。
2. 从未标注语料中建立词表。
   可以认为经常重复出现连续字符串属于词语。统计大量未标注语料中的连续字串重复出现频率，将多次重复出现的连续字串作为词语，以此建立词典。
3. 使用输入法，辞典，翻译（例如中英词语互译）词表.
   这是比较容易实现的方法，且这些数据大多能免费下载，有些输入法词表还带词频。

- 阅读剩余部分 -