中文分词词性和序列标注之MEMM-4-最优化算法-IIS
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 $，直到模型似然最大化为止。计算参数改变对应的似然改变量：$$ \begin{align} L(w + \delta) - L(w) &= \sum_{x,y} \tilde{p}(x,y) \log p_{w + \delta}(y|x) - \sum_{x,y}\tilde{p}(x,y) \log p_{w}(y|x) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} (w + \delta)_i f_i(x,y) - \sum_{x} \tilde{p}(x) \log Z_{w + \delta}(x) \\ & \quad - \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) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) - \sum_{x} \tilde{p}(x) \log \frac{Z_{w+\delta}(x)}{Z_w(x)} \\ & \text{because:} \sum_y \tilde{p}(x) = 1 \qquad \text{and} \qquad - \log a \geq 1-a, a > 0 \\ & \geq \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \frac{Z_{w+\delta}(x)}{Z_w(x)} \\ & \geq \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \frac{ \sum_y \exp \sum_{i=1} ( w + \delta )_i f_i (x,y) }{ \sum_y \exp \sum_{i=1} w_i f_i (x,y) } \\ & \geq \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \frac{ \sum_y \exp \sum_{i=1} w_i f_i (x,y) \exp \sum_{i=1} \delta_i f_i(x,y) }{ \sum_y \exp \sum_{i=1} w_i f_i (x,y) } \\ & \geq \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \sum_y p_w(y|x) \exp \sum_{i=1} \delta_i f_i(x,y) \end{align} $$将右端记为：$$ A(\delta|w) = \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \sum_y p_w(y|x) \exp \sum_{i=1} \delta_i f_i(x,y) $$表示参数增量带来的似然增量变化, 于是有以下表示对数似然改变量的下界。$$ L(w + \delta) - L(w) \geq A(\delta|w) $$从上文可得知函数 $ A(\delta|w) $ 是凹函数。当$ \delta $导数为零时，对似然的增量最大(且不会超过似然增量的下界引起优化反作用), 但是$ \delta $是个向量，其参数会互相影响而不易优化。因此时偏导为： $$ \frac{\partial A}{\partial \delta_i } = \sum_{x,y} \tilde{p}(x,y) f_i(x,y) - \sum_{x,y} \tilde{p}(x) p_w(y|x) f_i(x,y) \left[ \exp \sum_{i=1} \delta_i f_i(x,y) \right] $$进一步改进函数以得到优化时变量之间互相干扰比较小的函数，为此规定：$$ f^\#(x,y) = \sum_{i=1} f_i(x,y) $$因 $ f_i $ 是二值函数，这里实际上是对特定 $ x,y $ 做特征计数将$ A(\delta|w) $改写为：$$ A(\delta|w) = \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{p}(x) \sum_{y} p_w(y|x) \exp \sum_{i=1} \frac{ \delta_i f^\#(x,y) f_i(x,y) }{ f^\#(x,y) } $$$ \exp $是凸函数，且$ \sum_{i=1} \frac{ f_i(x,y) } { f^\#(x,y) } = 1 $, 使用$ jensen $不等式改写为：$$ \begin{align} A(\delta|w) \geq B(\delta|w) = \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} \delta_i f_i(x,y) + 1 - \sum_x \tilde{p}(x) \sum_y p_w(y|x) \sum_{i=1} \frac{f_i(x,y)}{f^\#(x,y)} \exp(\delta_i f^\#(x,y)) \end{align} $$Jensen不等式, 若f在区间(a,b)凸函数$ x_1,x_2,\cdots,x_n \in (a,b) $,且$ a_1 + a_2 + \cdots a_n = 1 $ 则: $$ f(a_1 x_1 + a_2 x_2 + \cdots + a_n x_n) \leq a_1 f(x_1) + a_2 f(x_2) + \cdots a_n f(x_n) $$这是相对$ A(\delta|w) $不那么紧的新的一个似然增量函数，求导令其为0依次优化每个参数即可，因为在这里只存在一个参数变量。$$ \begin{align} \frac{\partial B}{\partial \delta_i} & = \sum_{x,y} \tilde{p}(x,y) f_i(x,y) - \sum_{x,y} \tilde{p}(x) p_w(y|x) f_i(x,y) \exp(\delta_i f^\#(x,y)) \\ & = E_{\tilde{p}}(f_i) - \sum_{x,y} \tilde{p}(x) p_w(y|x) f_i(x,y) \exp(\delta_i f^\#(x,y)) \end{align} $$如 $ f^\#(x,y) = M $ 为常量，即对任何x,y特征计数相同（在分词和词性标注任务中此假设并不成立）。则参数可直接计算如下：$$ \delta_i = \frac{1}{M} \log \frac{E_{\tilde{p}(f_i)}}{E_p(f_i)} $$可使用一维搜索法解此方程，设$ g(\delta_i) = \frac{\partial B}{\partial \delta_i} $。牛顿法迭代公式为：$$ \delta^{k+1}_i = \delta^{k}_i - \frac{g(\delta^k_i)}{g^{\prime}(\delta^k_i)} $$五、参考资料[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)[3] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models[4] Daphne Koller, Nir Friedman; Probabilistic Graphical Models – Principles and Techniques[5] 李航; 统计学习方法[6] peghoty; http://blog.csdn.net/itplus/article/details/26550369[7] 琴生不等式 https://baike.baidu.com/item/琴生不等式/397409?fr=aladdin
中文分词词性和序列标注之MEMM-3-最大熵模型求解
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的凸函数, 因此求解对偶问题等价求解原始问题。定义对偶函数：$$ \Psi(w) = \min_P L(P, w) = L(P_w, w) $$其解为：$$ P_w = \arg\min_P L(P, w) = P_w(Y|X) $$也就是说，在$ w $不变时求得最小值参数。计算$ P_w(Y|X) $的导数，并让其为0即可。$$ \begin{align} \frac{\partial L(P,w)}{\partial p(y|x)} &= \sum_{x,y} \tilde{p}(x) \left( \log p(y|x) + 1 \right) - \sum_y w_0 - \sum_{x,y} \left[ \tilde{p}(x) \sum_{i=1} w_i f_i(x, y) \right] \\ &= \sum_{x,y} \tilde{p}(x) \left( \log p(y|x) + 1 \right) - \sum_x \tilde{p}(x) \sum_y w_0 - \sum_{x,y} \left[ \tilde{p}(x) \sum_{i=1} w_i f_i(x, y) \right] \\ & \quad \text{use:} \sum_x \tilde{p}(x) = 1; \\ &= \sum_{x,y} \tilde{p}(x) \left[ \log p(y|x) + 1 - w_0 - \sum_{i=1} w_i f_i(x,y) \right] \end{align} $$令其为0,且已知$ \tilde{p}(x) > 0 $：$$ \begin{align} \log p(y|x) &= \sum_{i=1} w_i f_i(x,y) - (1 - w_0) \\ p(y|x) &= \exp{\left[ \sum_{i=1} w_i f_i(x,y) - (1 - w_0) \right]} \\ &= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ \exp( 1-w_0 ) } \\ \text{because:} & \quad \sum_y p(y|x) = 1 \\ 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} $$$ Z_w(x) $为规范化因子，求得$ P_w $后，得到最大熵模型，其中$ w_{i=1,2,\cdots,n} $可以被理解为每个特征的权重，注意在这里$ w_0 $被规范化因子给消除掉了. 而学习最大熵模型只需要调整权重的大小，极大化对偶函数$ \max_w \Psi(w) $即可.4. 极大似然估计上面已推导出最大熵模型，并已知极大化其对偶函数为模型学习结果。接下来证明对偶函数极大化估计等价于最大熵模型的极大似然估计。条件概率分布的对数似然函数为：$$ L_\tilde{P}(P_w) = \log \prod_{x,y}p(y|x)^{\tilde{p}(x,y)} = \sum_{x,y} \tilde{p}(x,y) \log p(y|x) $$在这里使用指数表示似然，解释如下：设分布$ p(x_1,x_2,\cdots,x_n) $的似然函数为，($ Count $是计数函数)。$$ P(x_1,x_2,\cdots,x_n) = \prod_x P(X=x)^{Count(X=x)} $$需要的是求相对大小，并不在意绝对值。左右同时用总样本数$ N $开方。$$ \sqrt[N]{p(x_1,x_2,\cdots,x_n)} = \prod_x P(X=x)^{\frac{Count(X=x)}{N}} = \prod_x p(x) ^{p(x)} $$$$ \begin{align} L_\tilde{P}(P_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,y} \tilde{p}(x,y) \log Z_w(x) \\ \text{because:} & \quad \sum_y p(x,y) = p(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} $$对耦函数$ \Psi(w) $的极大化估计为（在函数解模型$ P_w $推导中参数$ w_0 $已被规范化因子证明约掉，因此不再考虑。）。$$ \begin{align} \Psi(w) &= L(P_w, w) \\ &= \sum_{x, y} \tilde{p}(x) p_w(y|x) \log p_w(y|x) \\ & \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_w(y|x) f_i(x, y) \right] \\ &= \sum_{x,y} \tilde{p}(x) p_w(y|x) \log p_w(y|x) \\ & \quad + \left[ \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) - \sum_{x,y} \tilde{p}(x)p_w(y|x) \sum_{i=1} w_i f_i(x,y) \right] \\ &= \sum_{x,y} \tilde{p}(x) p_w(y|x) \left[ \sum_{i=1} w_i f_i(x,y) - \log Z_w(x) \right] \\ & \quad + \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) - \sum_{x,y} \tilde{p}(x) p_W(y|x) \sum_{i=1} w_i f_i(x,y) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i (x,y) - \sum_{x,y} \tilde{p}(x) p_w(y|x) \log Z_w(x) \\ & \text{because:} \sum_y p_w(y|x) = 1 \\ &= \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} $$以上证明求解对偶函数极大化和求解模型对数极大似然是相同的，因此最大熵模型的学习使用这两个方法都可行。五、参考资料[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)[3] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models[4] Daphne Koller, Nir Friedman; Probabilistic Graphical Models – Principles and Techniques[5] 李航; 统计学习方法[6] peghoty; http://blog.csdn.net/itplus/article/details/26550369
中文分词词性和序列标注之MEMM-2-最大熵模型
二、最大熵模型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 $。2 特征函数特征函数 $ f(x, y) $ 指示某事实是否成立，例如：$$ f(x, y) = \begin{cases} 1, & \text{if y='rn' and next(x) = 'is'} \\ 0, & \text{else} \end{cases} $$如果 s是人名并且下一个词是"is". 则返回1指示存在此事实。$ \text{对数线性模型}^{\text{[4]}} $并未限制特征函数的取值范围，但通常输出为 $ \{0,1\} $ 的特征函数更容易分析和直观理解。例如返回1就是存在此特征。3. 最大熵模型最大熵模型是一种对数线性模型，其目的是对样本做$ P(Y|X) $建模, 其需要在满足观测事实约束时才有意义，现描述使用特征函数约束的最大熵模型。设经验分布：$$ \begin{align} \tilde{P}(X=x) &= \frac{Count(X=x)}{N} \\ \tilde{P}(X=x, Y=y) &= \frac{Count(X=x, Y=y)}{N} \end{align} $$$ Count $是计数函数，$ N $是样本总数。使用前面介绍的特征函数对$ x,y $对约束（指示存在的事实）。那么，统计样本可得到特征函数指示事实的经验分布期望:$$ E_{\tilde{P}}(f) = \sum_{x,y} \tilde{p}(x, y) f(x, y) $$假设我们的最大熵模型对条件概率估计正确，那么很显然应可得到符合观测事实的$ P(Y|X) $分布，也就是说。使用模型估计的特征函数期望应该和在样本中统计到的特征函数期望相同。$$ \begin{align} E_{P}(f) & = E_{\tilde{P}}(f) \\ \sum_{x,y} \tilde{p}(x) p(y|x) f(x, y) & = \sum_{x,y} \tilde{p}(x,y) f(x,y) \end{align} $$同时，模型得到的条件概率分布应该合法，于是最大熵模型的完整描述如下：$$ \begin{align} \max_{P} H(P) & = – \sum_{x, y} \tilde{p}(x) p(y|x) \log \, p(y|x) \Leftrightarrow \min_{P} -H(P) \\ \text{subject to:} \\ E_{P}(f_i) & = E_{\tilde{P}}(f_i) \qquad i=1,2,\cdots,n \\ \sum_y p(y|x) & = 1 \end{align} $$$ P $是分布函数, $ p $是质量函数，因没有$ p(x, y) $, 因此使用 $ \tilde{p}(x) p(y|x) $近似。按照惯例，转换为最小化负熵。其实就是求解满足约束的最小负条件熵的条件概率分布函数。五、参考资料[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)[3] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models[4] Daphne Koller, Nir Friedman; Probabilistic Graphical Models – Principles and Techniques[5] 李航; 统计学习方法[6] peghoty; http://blog.csdn.net/itplus/article/details/26550369
一、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) $$1. MEMM是判别模型。在HMM中，观测序列由隐藏状态序列生成，在序列标注任务中寻找以最大概率生成指定观测序列的隐藏状态序列,$HMM-viterbi$计算观测序列和隐藏序列的最大联合概率。$ \lambda $ 是模型参数。$$ Q = \arg\max_{Q} P(Q,O | \lambda) $$而MEMM作为判别模型直接给出目标状态序列。$$ Q = \arg\max_{Q} P(Q | O, \lambda) $$2. 可定义更复杂的特征在 $ HMM-Viterbi $ 查找序列标注时当前隐藏状态和上个隐藏状态相关，假定各观测状态之间互相独立, 观测状态是生成目标，并不便于定义更多特征条件。$$ \delta_t(j) = \max_i \delta_{t-1}(i)a_{ij} \cdot b_j(o_t) $$在MEMM中并不要求各观测状态独立，可使用特征函数对条件$ o_t $定义更复杂的分类特征，e.g. 大小写、上下文字符)。$$ \delta_t(j) = \max_i \delta_{t-1}(i) P(q_t=S_j | q_{t-1} = S_i, o_t) $$3. MEMM的$ viterbi $算法与$ HMM-viterbi $ 类似，定义两个函数用于保存每个步骤的最大概率和最佳前驱状态。然后从前向后递归，最后回朔状态序列。但这里和HMM不同的是改联合概率定义为条件概率。$$ \begin{align} \delta_t(i) & = \max_{q_1 q_2 \cdots q_{t-1}} P(q_1 q_2 \cdots q_{t-1},q_t=S_i | O_1 O_2 \cdots O_t) \\ \psi_t(i) & = \arg\max_{q_1 q_2 \cdots q_{t-1}} P(q_1 q_2 \cdots q_{t-1},q_t=S_i | O_1 O_2 \cdots O_t) \end{align} $$第一步 此时 $ q_0 = {\emptyset} $，这里理解为，没有上一个隐藏状态本身就表示一种特殊状态（序列开始状态）$$ \begin{align} \delta_1(i) & = P(q_t=S_i | q_0={\emptyset}, O_1) \\ \psi_1(i) & = {\emptyset} \end{align} $$递归$$ \begin{align} \delta_t(j) & = \max_i \delta_{t-1}(i)P(q_t=S_j | q_{t-1}=S_i, O_t) \\ \psi_t(j) & = \arg\max_i \delta_{t-1}(i)P(q_t=S_j | q_{t-1}=S_i, O_t) \end{align} $$结束 后续计算和回朔和HMM相同，不再叙述。在 $ P(q_t=S_j | q_{t-1}=S_i, O_t) $ 中，工程实现时，实际传递的其实是 $ P(q_t=S_j | q_{t-1}=S_i, O, t) $ ，原因是特征函数可能需要判断 $ t $ 时刻的上下文作为特征。作为最大熵马尔可夫模型介绍，本文不考虑使用其他的概率计算方法。五、参考资料[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)[3] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models[4] Daphne Koller, Nir Friedman; Probabilistic Graphical Models – Principles and Techniques[5] 李航; 统计学习方法[6] peghoty; http://blog.csdn.net/itplus/article/details/26550369
回顾一阶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} $$二阶Viterbi在每次的计算在中，要考虑先后两个状态，因此viterbi对应更改：$$ \begin{align} \delta_t(i, j) & \equiv \max_{{q_1}{q_2}{\cdots}{q_{t-2}}} P( {q_1}{q_2}{\cdots}{q_{t-2},q_{t-1}=S_i, q_t = S_j, O_1 \cdots O_t | \lambda } ) \\ \psi_t(i, j) & \equiv \arg\max_{{q_1}{q_2}{\cdots}{q_{t-2}}} P( {q_1}{q_2}{\cdots}{q_{t-2},q_{t-1}=S_i, q_t = S_j, O_1 \cdots O_t | \lambda } ) \end{align} $$初始化 此时并不满足二阶条件。 继续使用一阶HMM的初始/转移矩阵，但要第一步时需忽略参数 $ i $，且不考虑改进后的观测矩阵。当然其实也可以认为$ i $事件发生概率在这里永远是1：$$ \begin{align} \text{when} \quad t=1 \text{:} \qquad & \\ \delta_1(i, j) & = \pi_j b_j(O_1) \\ \psi_1(i,j) & = 0 \\ \text{when} \quad t=2 \text{:} \qquad & \\ \delta_2(i, j) & = \delta_1( , i)a_{ij} \cdot b_{ij}(O_2) \\ \psi_2(i,j) & = 0 \\ \end{align} $$恩，似乎有点麻烦，直接从t=2作为初始化，合并到一起好了。从t=3开始计算$ \psi $。$$ \begin{align} \delta_2(i, j) & = \pi_i b_i(O_1) \cdot a_{ij} \cdot b_{ij}(O_2) \\ \psi_2(i,j) & = 0 \end{align} $$递归$$ \begin{align} \delta_t(j, k) & = \max_i \delta_{t-1}(i, j) \cdot a_{ijk} \cdot b_{jk}(O_t) \\ \psi_t(j, k) & = \arg\max_i \delta_{t-1}(i, j) \cdot a_{ijk} \end{align} $$终止$$ \begin{align} p^* & = \max_{i,j} \delta_T(i, j) \\ q^*_{T-1} & = \arg_i\max_{i,j} \delta_T(i, j) \\ q^*_{T} & = \arg_j\max_{i,j} \delta_T(i, j) \\ \end{align} $$回朔状态序列路径 $$ q^*_t = \psi_{t+2}(q^*_{t+1}, q^*_{t+2}), t = T-2, T-3, \cdots, 1 $$平滑在二阶HMM算法中，可能无法从样本中统计到所有的 $ a_{jk}, a_{ijk},b_{ij}(m),b_j{m} $ 参数。因此和HMM一样可能存在零概率状态序列，为解决这个问题需要对转移矩阵和观测矩阵做平滑，在计算时估计新样本的概率。平滑转移矩阵Brants, Thorsten. "TnT: a statistical part-of-speech tagger. 提出的平滑方法。$$ p(t_3 | t_2, t_1) = \lambda_1 \hat{p}(t_3) + \lambda_2 \hat{p}(t_3 | t_2) + \lambda_3 \hat{p}(t_3 | t_2, t_1) $$系数 $ \lambda_1 + \lambda_2 + \lambda_3 = 1 $ ，于是$ p $表达为它们各自概率的线性组合。以下是系数计算方法$$ \begin{align} & \text{set} \quad \lambda_1 + \lambda_2 + \lambda_3 = 0 \\ & \text{foreach trigram} \quad t_1, t_2, t_3 \quad \text{with} \quad f(t_1,t_2,t_3) > 0 \\ & \qquad \text{depending on the maximum of the following three values：} \\ & \qquad \qquad \text{case} \quad \frac{f(t_1,t_2,t_3)-1}{f(t_1,t_2)-1} \text{:} \qquad \text{increment} \quad \lambda_3 \quad \text{by} \quad f(t_1,t_2,t_3) \\ & \qquad \qquad \text{case} \quad \frac{f(t_2,t_3)-1}{f(t_2)-1} \text{:} \qquad \text{increment} \quad \lambda_2 \quad \text{by} \quad f(t_1,t_2,t_3) \\ & \qquad \qquad \text{case} \quad \frac{f(t_3)-1}{N-1} \text{:} \qquad \text{increment} \quad \lambda_1 \quad \text{by} \quad f(t_1,t_2,t_3) \\ & \qquad \text{end} \\ & \text{end} \\ & \text{normalize} \quad \lambda_1,\lambda_2,\lambda_3 \end{align} $$计算时如果其中某个式子分母为0,则让计算结果为0。其实算法就是在累计三元，二元，一元在每个三元组下的数量，最后用这个数量归一得到比例。这就将三元组概率表达为线性插值算法。分子分母减1是考虑到可能有些样本没有观察到。其实在这里用梯度下降训练系数可能效果会更好些,或改为总数累计比例, 实际项目中需要尝试多种系数计算方法对比平滑效果。考虑到字序列分词只有BMES三种标签，实际上样本稍微多点就不需要平滑。平滑观察概率矩阵零概率问题不只是在转移概率中存在，因为我们在观察概率中也考虑了连续两个隐藏状态，这里也可能存在两个隐藏序列标注观察到某字符是零概率（考虑到汉字可有8万个之多,难免有样本中未统计到的状况）。在这里的平滑方式模仿转移概率平滑，但是考虑到观测字符在样本中并未出现过的情况，此时退回到其他的平滑方式，例如最简单的+1平滑。代码实现和效果并未优化代码结构和性能，只验证算法。因转移矩阵并无采样缺失，所以未做转移矩阵平滑，只对观察矩阵做了$ TnT $平滑, $ +1 $平滑。# -*- coding: utf-8 -*- import sys, re, math import numpy as np sys.argv.append('./gold/pku_training_words.utf8') sys.argv.append('./training/pku_training.utf8') sys.argv.append('./testing/pku_test.utf8') assert len(sys.argv) == 4 training_words_filename = sys.argv[1] training_filename = sys.argv[2] test_filename = sys.argv[3] with open(training_words_filename, 'rt', encoding='utf8') as f: training_words = f.readlines() with open(training_filename, 'rt', encoding='utf8') as f: training = f.readlines() with open(test_filename, 'rt', encoding='utf8') as f: test = f.readlines() # training += training_words # word tag by char hidden_state = ['B','M','E','S'] A, B, P = {}, {}, {} _N = 0 _O = {} for line in training: #print( line ) prev_a = None for w, word in enumerate(re.split(r'\s{2}', line)): I = len(word) _N += I for i, c in enumerate(word): _O[c] = _O.get(c, 0) + 1 if I == 1: a = 'S' else: if i == 0: a = 'B' elif i == I-1: a = 'E' else: a = 'M' # print(w, i, c, a) if prev_a is None: # calculate Initial state Number if a not in P: P[a] = 0 P[a] += 1 else: # calculate State transition Number if prev_a not in A: A[prev_a] = {} if a not in A[prev_a]: A[prev_a][a] = 0 A[prev_a][a] += 1 prev_a = a # calculate Observation Number if a not in B: B[a] = {} if c not in B[a]: B[a][c] = 0 B[a][c] += 1 _B = B.copy() # calculate probability for k, v in A.items(): total = sum(v.values()) A[k] = dict([(x, math.log(y / total)) for x, y in v.items()]) for k, v in B.items(): # plus 1 smooth total = sum(v.values()) V = len(v.values()) B[k] = dict([(x, math.log((y+1.0) / (total+V))) for x, y in v.items()]) # plus 1 smooth B[k]['<UNK>'] = math.log(1.0 / (total+V)) minlog = math.log( sys.float_info.min ) total = sum(P.values()) for k, v in P.items(): P[k] = math.log( v / total ) A2,B2 = {}, {} for line in training: temptags = [] tempsent = [] for w, word in enumerate(re.split(r'\s{2}', line)): I = len(word) for i, c in enumerate(word): if I == 1: a = 'S' else: if i == 0: a = 'B' elif i == I-1: a = 'E' else: a = 'M' temptags.append(a) tempsent.append(c) if len(temptags) >= 3: if temptags[-3] not in A2: A2[temptags[-3]] = {} if temptags[-2] not in A2[temptags[-3]]: A2[temptags[-3]][temptags[-2]] = {} if temptags[-1] not in A2[temptags[-3]][temptags[-2]]: A2[temptags[-3]][temptags[-2]][temptags[-1]] = 0 A2[temptags[-3]][temptags[-2]][temptags[-1]] += 1 if len(temptags) >= 2: if temptags[-2] not in B2: B2[temptags[-2]] = {} if temptags[-1] not in B2[temptags[-2]]: B2[temptags[-2]][temptags[-1]] = {} if tempsent[-1] not in B2[temptags[-2]][temptags[-1]]: B2[temptags[-2]][temptags[-1]][tempsent[-1]] = 0 B2[temptags[-2]][temptags[-1]][tempsent[-1]] += 1 #print( temptags, tempsent ) #break # calculate A2 log probabilitis for i in A2: for j in A2[i]: total = sum([A2[i][j][k] for k in A2[i][j]]) for k in A2[i][j]: A2[i][j][k] = math.log( A2[i][j][k] / total ) _A = np.array( [0,0,0] ) for i in B2: for j in B2[i]: total = sum([B2[i][j][k] for k in B2[i][j]]) V = len( B2[i][j] ) for k in B2[i][j]: # TnT smooth # 计算 TnT 平滑系数 a3 = ((B2[i][j][k] - 1.) / (total - 1.)) if total > 1 else 0 a2 = (_B[j][k] - 1.) / ( sum([_B[j][n] for n in _B[j]]) - 1. ) a1 = (_O[k] - 1.) / (_N - 1.) _A[np.argmax([a1,a2,a3])] += B2[i][j][k] # 计算二阶观察矩阵概率（+1平滑） B2[i][j][k] = math.log( ( B2[i][j][k] + 1 ) / (total + V) ) B2[i][j]['<UNK>'] = math.log( 1.0 / (total + V) ) # 计算 TnT 平滑系数 _A = _A / _A.sum() # 计算+1平滑字频 for o in _O: _O[o] = math.log( (_O[o] + 1.0) / (_N + len(_O)) ) _O['<UNK>'] = math.log( 1.0 / (_N + len(_O)) ) def viterbi2(observation): def _A2(i,j,k): key = ''.join([i,j,k]) if key.find('BB') >=0 : return minlog if key.find('MB') >=0 : return minlog if key.find('SM') >=0 : return minlog if key.find('EM') >=0 : return minlog if key.find('EE') >=0 : return minlog if key.find('SE') >=0 : return minlog if key.find('BS') >=0 : return minlog if key.find('MS') >=0 : return minlog try: return A2[i][j][k] except Exception as e: print( i, j, k) raise e def _B2(i,j,o): #return B[j].get(o, B[j]['<UNK>']) key = ''.join([i,j]) if key == 'BB': return minlog if key == 'MB': return minlog if key == 'SM': return minlog if key == 'EM': return minlog if key == 'EE': return minlog if key == 'SE': return minlog if key == 'BS': return minlog if key == 'MS': return minlog #if o not in B2[i][j]: # return B[j].get(o, B[j]['<UNK>']) #return B2[i][j].get(o, B2[i][j]['<UNK>']) return _A[0] * _O.get(o, _O['<UNK>']) + _A[1] * B[j].get(o, B[j]['<UNK>']) + _A[2] * B2[i][j].get(o, B2[i][j]['<UNK>']) state = ['B','M','E','S'] T = len(observation) delta = [None] * (T + 1) psi = [None] * (T + 2) for i in state: if delta[1] is None: delta[1] = {} if i not in delta[1]: delta[1][i] = {} for j in state: delta[1][i][j] = P.get(i, minlog) + B[i].get(observation[0], B[i]['<UNK>']) + A[i].get(j, minlog) + _B2(i, j, observation[1]) for t in range(2, T): Ot = observation[t] if delta[t] is None: delta[t] = {} if psi[t] is None: psi[t] = {} for j in state: if j not in delta[t]: delta[t][j] = {} if j not in psi[t]: psi[t][j] = {} for k in state: delta[t][j][k], psi[t][j][k] = max( [ (delta[t-1][i][j] + _A2(i,j,k) + _B2(j,k,Ot), i) for i in state] ) delta[T], (psi[T], psi[T+1]) = max( [ (delta[T-1][i][j], (i, j)) for i in state for j in state] ) q = [None] * (T+2) q[T+1] = psi[T+1] q[T] = psi[T] for t in range(T-1, 1, -1): q[t] = psi[t][q[t+1]][q[t+2]] return q[2:] for sent in test: if len(sent) < 2: print(sent, sep='', end='') continue sequence = viterbi2( list(sent) ) segment = [] for char, tag in zip(sent, sequence): if tag == 'B': segment.append(char) elif tag == 'M': segment[-1] += char elif tag == 'E': segment[-1] += char elif tag == 'S': segment.append(char) else: raise Exception() print(' '.join(segment), sep='', end='') #break 训练和评估使用pku语料：=== SUMMARY: === TOTAL INSERTIONS: 3921 === TOTAL DELETIONS: 7163 === TOTAL SUBSTITUTIONS: 13864 === TOTAL NCHANGE: 24948 === TOTAL TRUE WORD COUNT: 104372 === TOTAL TEST WORD COUNT: 101130 === TOTAL TRUE WORDS RECALL: 0.799 === TOTAL TEST WORDS PRECISION: 0.824 === F MEASURE: 0.811 === OOV Rate: 0.058 === OOV Recall Rate: 0.360 === IV Recall Rate: 0.825pku测试算法分词性能对比algorithmPRFOOVOOV RecallIV Recallmaximum matching0.8360.9040.8690.0580.0590.956maximum probability0.8590.9190.8880.0580.0850.970HMM0.8040.7890.7960.0580.3640.815Full Second Order HMM0.8240.7990.8110.0580.3600.825参考资料[1] Brants, Thorsten. "TnT: a statistical part-of-speech tagger." Proceedings of the sixth conference on Applied natural language processing. Association for Computational Linguistics, 2000.[2] Scott M. Thede and Mary P. Harper, A Second-Order Hidden Markov Model for Part-of-Speech Tagging
最大概率法分词是在最大匹配分词算法上的改进。在某些语句切分时，按最大长度切分词语可能并不是最优切分。而不按最优长度切分词语，则同一语句会出现多种切分结果。计算每种切分结果的概率，选取概率最高的切分作为最优分词切分。一、计算切分概率$W$：所有可能的切分组合$S$：待切分语句最佳切分：$$ {\arg\max}_w{P(W|S=s)} $$切分概率:$$ p(w|s) = \frac{p(w)p(s|w)}{p(s)} $$因为始终是同一语句，$ p(s) $ 未曾改变, $ p(s|w) $ 始终为1. 仅需计算 $ p(w) $.在词表中需记录每个词语的词频，计算每个独立词语出现的联合概率. 使用一元语法（不考虑词语上下文关系）则.$$ \begin{align} p(w^n_1) &= p(w_1,w_2, \cdots, w_n) \\ &= p(w_1)p(w_2){\cdots}p(w_n) \\ &= {\prod}^{n}_{1}p(w_n) \\ \end{align} $$在实践中一般用对数求和替代求积，原因是词语概率一般会很小，多次连乘后可能造成溢出.$$ \log{p(w)} = {\sum}^{n}_{1}\log{p(w_n)} $$只需要比较大小，所以最后计算结果无需再做一次 $ \log $二、平滑词表中不可能记录所有可能存在的词语和其词频，对于词表中没有的词如果认为其概率为0，则会存在0概率切分，为了解决零切分问题，给新词指定一个比较低的概率. 例如指定为词表中出现频数最低的词概率,或将其看待为只出现过一次，在这里 $N$ 表示词表词条总数。$ p(w_i) $ 是词表中的词语概率。将新词指定为词表中的最低词频率。 $$ p(w_{new}) = \min_i{p(w_i)} $$加$1$平滑。 假设在建造词表时所有词语都被漏计1次。所以刚好在词表中查询不到在待切分样本中碰到的新词（因为在切分特定位置时，新词只出现了1次）。因此在计算词表中的词语词频和新词词频时，给所有的词语词频$+1$。新的词语概率计算如下：$$ p(w)=\frac{c(w)+1}{N+V} \qquad c(w)=\begin{cases} 0, & \text{} \\ count(w), & \text{ \( {w} \in {dict} \) } \end{cases} $$$ N $ 词表中所有词语总计词频.$ V $ 词语总数，新词也算一个词语。$ c (w)$ 词表中对应词语频数，新词词频为$0$。三、切分词语切分词语时从语句中每个字作为词语前缀字符查询词表，查询结果构造为DAG图，如此表中无此词汇，则单字成词。以下代码摘录自*结巴分词。def get_DAG(sentence): global pfdict, FREQ DAG = {} N = len(sentence) for k in range(N): tmplist = [] i = k frag = sentence[k] while i < N and frag in pfdict: if frag in FREQ: tmplist.append(i) i += 1 frag = sentence[k:i+1] if not tmplist: tmplist.append(k) DAG[k] = tmplist return DAG四、选择最优切分有两种方法计算对DAG图做DFS搜索，得到所有切分组合，分别计算各组合概率，取最大概率组合输出。 segment_sent = [] def dfs(words, x): for y in DAG[x]: if y < N: new = words.copy() new.append(sentence[x:y]) dfs(new, y) else: new = words.copy() new.append(sentence[x:y]) segment_sent.append( new ) dfs([], 0) bestseg = max([(sum(fdist.get(w, math.log(1.0/total)) for w in seg), seg) for seg in segment_sent])很显然，这个计算复杂度非常高 $ O(\overline{word-length}^{(N-1)}) $ 以语句长度呈指数增长。对DAG图做动态规划DP算法, 从深度搜索这里可以看到, 其实很多局部计算过程是重复的。因此这里从图后面向前面反向计算, 每次累计最大概率结果。计算每个字为前缀的不同切分词语概率和后续最大切分概率的乘积，取最大结果为最佳切分，依次向语句前方递推。最后得到语句第一个字开始的最佳切分词语位置，并由第一个字开始的最佳切分词语位置向后依次查询切分词语,最终得到最佳切分。以下代码摘录自结巴分词。def calc(sentence, DAG, idx, route): N = len(sentence) route[N] = (0.0, '') for idx in range(N-1, -1, -1): route[idx] = max((FREQ.gdef __cut_DAG_NO_HMM(sentence): re_eng = re.compile(r'[a-zA-Z0-9]',re.U) DAG = get_DAG(sentence) route = {} calc(sentence, DAG, 0, route) x = 0 N = len(sentence) buf = '' while x < N: y = route[x][1] + 1 l_word = sentence[x:y] if re_eng.match(l_word) and len(l_word) == 1: buf += l_word x = y else: if buf: yield buf buf = '' yield l_word x = y if buf: yield buf buf = ''五、评估效果使用icwb2-data，pku语料, 词频也来自pku语料统计，封闭测试。最大概率法分词效果如下：=== SUMMARY: === TOTAL INSERTIONS: 8644 === TOTAL DELETIONS: 1325 === TOTAL SUBSTITUTIONS: 7114 === TOTAL NCHANGE: 17083 === TOTAL TRUE WORD COUNT: 104372 === TOTAL TEST WORD COUNT: 111691 === TOTAL TRUE WORDS RECALL: 0.919 === TOTAL TEST WORDS PRECISION: 0.859 === F MEASURE: 0.888 === OOV Rate: 0.058 === OOV Recall Rate: 0.085 === IV Recall Rate: 0.970完整代码# -*- coding: utf-8 -*- import sys import os.path import math import nltk from nltk.corpus import PlaintextCorpusReader sys.argv.append('./gold/pku_training_words.utf8') sys.argv.append('./training/pku_training.utf8') sys.argv.append('./testing/pku_test.utf8') assert len(sys.argv) == 4 with open(sys.argv[1], 'rt', encoding='utf8') as f: training_words = [w.strip() for w in f.readlines()] training = PlaintextCorpusReader( *os.path.split(sys.argv[2]) ) training_words += list(training.words()) #training_words = list(training.words()) N = len(training_words) V = len( set(training_words) ) fdist = nltk.FreqDist(training_words) fdist = dict([(w, math.log((c+1.0)/(N+V))) for w, c in fdist.items()]) defprob = math.log(1.0/(N+V)) with open(sys.argv[3], 'rt', encoding='utf8') as f: test = f.readlines() def get_DAG(sentence): DAG = {} T = len(sentence) for x in range(T): ys = [] for y in range(x+1, T+1): if sentence[x:y] in fdist: ys.append(y) if not ys: ys.append(x+1) DAG[x] = ys return DAG def dfs(DAG, sentence): segments = [] T = len(sentence) def _dfs(words, x): for y in DAG[x]: if y < T: new = words.copy() new.append(sentence[x:y]) _dfs(new, y) else: new = words.copy() new.append(sentence[x:y]) segments.append( new ) _dfs([], 0) bestseg = max([(sum(fdist.get(w, defprob) for w in seg), seg) for seg in segments]) return bestseg[1] def dp(DAG, sentence): T = len(sentence) prob = {T:(0.0,)} for x in range(T-1, -1, -1): prob[x] = max([(fdist.get(sentence[x:y], defprob) + prob[y][0], y) for y in DAG[x]]) x = 0 bestseg = [] while x < T: y = prob[x][1] bestseg.append( sentence[x:y] ) x = y return bestseg for sent in test: DAG = get_DAG(sent) #seg1 = dfs(DAG, sent) seg2 = dp(DAG, sent) #print(' '.join(seg1), sep='', end='') print(' '.join(seg2), sep='', end='') #break
正向最大匹配分词和逆向最大匹配分词词表词表为所有可能出现的词语组成的集合。当然，实践中不可能准备包含全所有已知和未知词语词表。建立词表从人工标注语料中得到词表。 由多人讨论并且得到共识的分词标注语料建立词表。这是效果最好，但也是成本最高的方案。从未标注语料中建立词表。 可以认为经常重复出现连续字符串属于词语。统计大量未标注语料中的连续字串重复出现频率，将多次重复出现的连续字串作为词语，以此建立词典。使用输入法，辞典，翻译（例如中英词语互译）词表.这是比较容易实现的方法，且这些数据大多能免费下载，有些输入法词表还带词频。正向最大匹配分词算法将待分词语句以每个字为开始词语前缀按从左到右的切分顺序与词表匹配，查找到的最长词语为分词结果，并将当前切分位置作为下个词语切分开始位置，如切分片段在在词表中无对应词语，则顺移到下一个字继续切分，把跳过的片段切分为新词（未登陆词）。此方法分词效果很大程度取决词表，且词表就算包含所有待切分词语，也可能造成分词效果不理想，原因是很多时候按最大长度切分词语可能并不是最优切分。例如:待切分词语句: 产量三年中将增长两倍正向最大匹配: 产量 三年 中将 增长 两倍最优切分词语: 产量 三年 中 将 增长 两倍词表中没有 “三年中”，但是有 “中将”, 而事实上 “三年中” 除非作为一个熟词，否则难以作为一个独立词语切分，毕竟还有四年中，五年中，这组合可就多了.与正向最大匹配分词算法类似的反/逆向最大匹配分词算法, 其改变切分顺序为从右到左.参考代码摘自 icwb2-data/scripts/mwseg.plwhile (<>) { chop; s/\s*//g; my $text = $_; while ($text ne "") { $sub = substr($text, 0, $maxwlen); while ($sub ne "") { if ($dict{$sub}) { print "$sub "; for (my $i = 0; $i < length($sub); ++$i) { $text =~ s/^.//; } last; } $sub =~ s/.$//; } if ($sub eq "") { if ($text =~ /^([\x21-\x7e])/) { print "$1 "; $text =~ s/^.//; } elsif ($text =~ /^([^\x21-\x7e].)/) { print "$1 "; $text =~ s/^..//; } else { ## shouldn't happen print STDERR "Oops: shouldn't be here: $n\n"; print "$1 "; $text =~ s/^.//; } } } print "\n"; ++$n; }用于PKU封闭测试效果=== SUMMARY: === TOTAL INSERTIONS: 9829 === TOTAL DELETIONS: 1359 === TOTAL SUBSTITUTIONS: 8648 === TOTAL NCHANGE: 19836 === TOTAL TRUE WORD COUNT: 104372 === TOTAL TEST WORD COUNT: 112842 === TOTAL TRUE WORDS RECALL: 0.904 === TOTAL TEST WORDS PRECISION: 0.836 === F MEASURE: 0.869 === OOV Rate: 0.058 === OOV Recall Rate: 0.059 === IV Recall Rate: 0.956
将算法分词结果与人工标注的分词结果对比，以此评估分词效果优劣。人工标注分词文本通常被看作公认的“黄金”标准。主要使用处理速度、精确率、召回率和F值四个指标衡量分词算法的性能。一、评估指标$TP$：正确分词数量$FP$：错误分词数量$N$：黄金分词数量$W$：算法处理样本字数$T$：算法运行时间（秒）分词算法处理速度使用每秒处理文本字数（或字节数）作为评估单位。$$ Speed=\frac{W}{T} $$精确率：算法分词结果中正确切分的词数占总切分词数的比例。$$ Precision=\frac{TP}{TP+FP} $$召回率：算法分词结果中正确切分的词数占黄金样本中应该被切分出的词数比例。$$ Recall=\frac{TP}{N} $$F值：精确率和召回率的调和值，可以理解为综合考虑结果。$$ F1=\frac{{2}\times{Precision}\times{Recall}}{{Precision} + {Recall}} $$注意：判断正确/错误切分时要注意切分词语的顺序，如顺序颠倒那么即使切分出词语也是错误。也就是说，不能用"if 词语 in 黄金分词"这种方法判断对错, icwb2使用"diff"命令实现分词对比。二、封闭测试和开放测试分词算法可能需要使用词表、统计/训练语料等相关数据，如固定黄金标准数据且提供词表和训练集用于算法设计和训练或参考，则属于封闭测试，可以理解为训练集（参考）和测试集是指定的。反之则属于开放测试。很显然封闭测试效果通常比开放测试好，在实际应用中不同行业或场景的词语切分差异很大，因此开放测试并不便于工程使用。多还是使用封闭测试，测试样本和训练样本来自相同行业/场景。三、简体中文分词封闭测试实战访问 Second International Chinese Word Segmentation Bakeoff Data，下载 icwb2-data 评估数据集和脚本。解压icwb2-data.zip后可得到多个数据集用于评估分词效果, 其中 PKU(北大), MSR（微软研究院）数据集用于评估简体中文分词. 使用其自带的最大正向匹配分词算法作为分词算法性能比较基准。PKU分词封闭测试使用最大正向匹配分词算法切分pku_test.utf8待文件。使用gold文件夹下的pku词表(封闭测试)。执行score对比人工标注的黄金分词样本和之前算法切分结果差异。# cd icwb2-data # perl scripts/mwseg.pl gold/pku_training_words.utf8 testing/pku_test.utf8 > test_segmentation.utf8 # perl scripts/score gold/pku_training_words.utf8 gold/pku_test_gold.utf8 test_segmentation.utf8等待执行完成后可看到如下报告，这里其自带mwseg.pl切分的性能为精确率：0.836、召回率：0.904、新词识别率：0.058、新词识别召回率：0.059。词表中未存在的词语为新词（也称为未登陆词），在某些分词算法中词表并不是必须的，不用过多关注新词识别指标。=== SUMMARY: === TOTAL INSERTIONS: 9829 === TOTAL DELETIONS: 1359 === TOTAL SUBSTITUTIONS: 8648 === TOTAL NCHANGE: 19836 === TOTAL TRUE WORD COUNT: 104372 === TOTAL TEST WORD COUNT: 112842 === TOTAL TRUE WORDS RECALL: 0.904 召回率 === TOTAL TEST WORDS PRECISION: 0.836 精度 === F MEASURE: 0.869 F调和 === OOV Rate: 0.058 新词率(此值同语料不会改变,毕竟词表以外都是未登陆词) === OOV Recall Rate: 0.059 未登陆词招回率 === IV Recall Rate: 0.956 已登陆词召回率scripts/mwseg.pl 是其自带的 最大正向匹配 分词算法，此脚本分词效果作为分词评估基准。
和JS版功能相同,只是为了提高性能才用C#重写一次.Form1.csusing System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.Threading; using System.Net; using System.IO; using System.Text.RegularExpressions; using MySql.Data; using MySql.Data.MySqlClient; namespace 网页关键词处理 { public partial class keywords : Form { public keywords() { InitializeComponent(); } private Thread t; delegate void SetTextCallback(string text); private void start_Click(object sender, EventArgs e){ if (start.Text.Equals("stop")) { this.t.Abort(); start.Text = "start"; }else{ this.t = new Thread(new ThreadStart(this.threadsafe)); this.t.Start(); start.Text = "stop"; } } private void threadsafe() { //获取数据库连接 string _sha1 = ""; string _url = ""; if (url.Text.Trim().Equals("")) { MySqlConnection conn = new MySqlConnection("server=" + db_servers.Text.Trim() + ";user=" + db_uid.Text.Trim() + ";database=" + db_db.Text.Trim() + ";port=3306;password=" + db_pwd.Text.Trim() + ";charset=utf8"); try { conn.Open(); MySqlCommand cmd = new MySqlCommand("SELECT url_sha1,url_link FROM url ORDER BY url_update,url_error ASC LIMIT 1", conn); MySqlDataReader rdr = cmd.ExecuteReader(); while (rdr.Read()) { _sha1 = rdr.GetString(0).Trim(); _url = rdr.GetString(1).Trim(); } rdr.Close(); cmd.Dispose(); rdr.Dispose(); rdr = null; cmd = null; conn.Close(); } catch (Exception ex) { MessageBox.Show(ex.Message); } conn.Dispose(); conn = null; }else { _sha1 = ""; _url = url.Text.Trim(); } show("访问:"+_url); try { html h = new html(gethttp(_url)); string title = h.Title; string body = h.Body; MySqlConnection conn = new MySqlConnection("server=" + db_servers.Text.Trim() + ";user=" + db_uid.Text.Trim() + ";database=" + db_db.Text.Trim() + ";port=3306;password=" + db_pwd.Text.Trim() + ";charset=utf8"); conn.Open(); MySqlCommand cmd = new MySqlCommand("UPDATE url SET url_title='"+title+"',url_keywords = '"+body+"',url_update = now() WHERE url_sha1 = '" + _sha1 + "'", conn); cmd.ExecuteNonQuery(); cmd.Dispose(); cmd = null; conn.Close(); conn.Dispose(); conn = null; show(title); show(body); }catch( Exception e){ //记录错误 show("访问出错!" + e.Message); MySqlConnection conn = new MySqlConnection("server=" + db_servers.Text.Trim() + ";user=" + db_uid.Text.Trim() + ";database=" + db_db.Text.Trim() + ";port=3306;password=" + db_pwd.Text.Trim() + ";charset=utf8"); conn.Open(); MySqlCommand cmd = new MySqlCommand("UPDATE url SET url_update = now(),url_error= url_error + 1 WHERE url_sha1 = '" + _sha1 + "'", conn); cmd.ExecuteNonQuery(); cmd.Dispose(); cmd = null; conn.Close(); conn.Dispose(); conn = null; } this.threadsafe(); } private string gethttp(string url) { WebClient wc = new WebClient(); wc.Credentials = CredentialCache.DefaultCredentials; wc.Headers.Add("User-Agent", "Mozilla/5.0+(compatible;+cpcunionbot/1.0;++http://www.cpcunion.com/bot.html)"); Byte[] pageData = wc.DownloadData(url); string html; string reponseencoding = wc.ResponseHeaders.GetValues("Content-Type").GetValue(0).ToString(); reponseencoding = reponseencoding.Substring(reponseencoding.IndexOf("charset=")+8); try { return Encoding.GetEncoding(reponseencoding).GetString(pageData); }catch(Exception e){ html = Encoding.Default.GetString(pageData); try { Regex reg_charset = new Regex(@"charset\b\s*=\s*(?<charset>[^""]*)"); string enconding = null; if (reg_charset.IsMatch(html)) enconding = reg_charset.Match(html).Groups["charset"].Value; else enconding = Encoding.Default.EncodingName; if (!Encoding.Default.EncodingName.Equals(enconding)) html = Encoding.GetEncoding(enconding).GetString(pageData); }catch(Exception ex){ show(ex.Message); } return html; } } private void show(string msg) { if (info.InvokeRequired) { SetTextCallback d = new SetTextCallback(show); this.Invoke(d, new object[] { msg }); } else { info.Items.Add(msg); if (info.Items.Count > 30) { info.Items.Clear(); } } } private void keywords_Load(object sender, EventArgs e) { } private void button1_Click(object sender, EventArgs e) { html h = new html(gethttp(url.Text.Trim())); string title = h.Title; string body = h.Body; MessageBox.Show("网页标题:"+title); MessageBox.Show("参考关键词:"+body); h = null; } } }html.csusing System; using System.Collections.Generic; using System.Collections; using System.Text; using System.Web; using System.Text.RegularExpressions; namespace 网页关键词处理 { class html { private const int cn_max = 8; private const int cn_min = 2; private const int en_max = 84; private const int en_min = 2; private const string endchars = " ;:,：，．.。'“”?？_{}/\\·[]()（）、…ˉ-!！<>《》〉〈〕〔【】〗〖［］｛｝『』」「￥—"; private string title; public string Title { get { return title; } } private string body; public string Body { get { return body; } } private string keywords; public string Keywords { get { return keywords; } } private string description; public string Description { get { return description; } } public html(string code) { //获取标题 this.title = this.getTitle(code).Trim(); this.body = this.getBody(code).Trim(); } //获取body private string getBody(string code) { string strfrom = NoHTML(code); //return strfrom; int strlength = strfrom.Length; int chscount, endasc, cx, ca, oldcount=0; string tempstr, oldchar=""; char endchar; Dictionary<string,int> strdic = new Dictionary<string,int>(); //中英文分词 for (var i = 0; i < strlength; i++) { chscount = 0; for (var j = 1; j < en_max; j++) { if ((i + j) <= strlength){ tempstr = strfrom.Substring(i, j); endasc = (int)Encoding.Default.GetBytes(tempstr)[j-1]; endchar = tempstr[j-1]; if (endchars.IndexOf(endchar) != -1 || (endasc >= 0 && endasc <= 47) || (endasc >= 58 && endasc <= 64) || (endasc >= 91 && endasc <= 96)) { break; }else{ if(endasc <= 0 || endasc >= 254)chscount++; if (chscount > cn_max) break; if (tempstr.Length > 1){ //标题匹配加倍权重 ca = (strlength - strfrom.Replace(tempstr, String.Empty).Length) / tempstr.Length; cx = this.title.IndexOf(tempstr) != -1? ca*2 : ca; //丢弃只出现一次的词语 if(cx>0){ if (!strdic.ContainsKey(tempstr)){ strdic.Add(tempstr, cx); } if (oldcount > 0 && tempstr.IndexOf(oldchar) == 0){ strdic[oldchar] = oldcount - cx; //丢弃只出现一次的词语 if(strdic[oldchar]<2)strdic.Remove(oldchar); } oldchar = tempstr; oldcount= cx; }; } } } } } int c = strdic.Count; string[] a = new string[c]; int[] b = new int[c]; int ti = 0; string upa="",doa=""; int upb=0,dob=0; keys[] keys = new keys[c]; strdic.Keys.CopyTo(a,0); strdic.Values.CopyTo(b,0); for(int i=c-1;i>=0;i--){ if(i>0){ upa = a[i]; upb = b[i]; doa = a[i-1]; dob = b[i-1]; if(doa.IndexOf(upa)==doa.Length-upa.Length){ upb = upb - dob; } if(upb>1){//丢弃只出现一次的词语 keys[ti] = new keys(); keys[ti].Str = upa; keys[ti].Count=upb; ti++; } }else{ keys[ti] = new keys(); keys[ti].Str = doa; keys[ti].Count=dob; } } //按匹配次数排序 bool py = true; int pyd, pye, pyf; string pys; c = ti; while(py){ py = false; for(int i=0;i<c;i++){ if ((i + 1) >= c)break; pyd = keys[i].Count; pye = keys[i+1].Count; if(pyd<pye){ pyf = keys[i].Count; pys = keys[i].Str; keys[i].Count = keys[i+1].Count; keys[i].Str = keys[i+1].Str; keys[i+1].Count = pyf; keys[i+1].Str = pys; py = true; } } } string keystring=""; for (int i = 0; i < c; i++) { keystring += keys[i].Str; if (keystring.Length >= 255) break; else keystring += " "; } if (keystring.Length > 255) keystring = keystring.Substring(0, 255); return keystring; } public string NoHTML(string Htmlstring) { //删除脚本 Htmlstring = Regex.Replace(Htmlstring, @"(?is)<script.*? "," "); Htmlstring = Regex.Replace(Htmlstring, @"(?is)<style.*? ", " "); Htmlstring = Regex.Replace(Htmlstring, @"(?is) ", " "); Htmlstring = Regex.Replace(Htmlstring, @"(?is)<.*?>", " "); Htmlstring = HttpUtility.HtmlDecode(Htmlstring); //删除符号 //Htmlstring = Htmlstring.Replace("(", " "); //Htmlstring = Htmlstring.Replace(")", " "); //Htmlstring = Htmlstring.Replace("|", " "); //Htmlstring = Htmlstring.Replace(",", " "); //Htmlstring = Htmlstring.Replace("@", " "); //Htmlstring = Htmlstring.Replace(";", " "); //Htmlstring = Htmlstring.Replace(".", " "); //Htmlstring = Htmlstring.Replace("]", " "); //Htmlstring = Htmlstring.Replace("[", " "); //Htmlstring = Htmlstring.Replace(">", " "); //Htmlstring = Htmlstring.Replace("<", " "); //Htmlstring = Htmlstring.Replace("*", " "); Htmlstring = Regex.Replace(Htmlstring, @"(?is)(\s+|\n+)", " "); return Htmlstring; } //获取描述 private string getDescription(string code) { Regex r = new Regex("(?is)(?<=<Title>).*?(?= )"); Match m = r.Match(code); return m.Success ? m.Value : ""; } //获取关键词 private string getKeywords(string code) { Regex r = new Regex("(?is)(?<=<Title>).*?(?= )"); Match m = r.Match(code); return m.Success ? m.Value : ""; } //获取页面标题 private string getTitle(string code) { Regex r = new Regex("(?is)(?<=<Title>).*?(?= )"); Match m = r.Match(code); string tit = m.Success? m.Value:""; if (tit.Length > 50) tit = tit.Substring(0, 50); return tit; } } }keys.csusing System; using System.Collections.Generic; using System.Text; namespace 网页关键词处理 { class keys { private string str; private int count; public string Str { get { return str; } set { str = value; } } public int Count { get { return count; } set { count = value; } } } }