NLP-马尔科夫模型
马尔科夫模型
本讲我们讲解一下：
- N元语法模型
- 马尔科夫模型 ## 一. n元语法分词：
一）基础概念：
1. 句子概率：
我们令字符串\(S = w_1w_2...w_n\)为一个句子，那么，其概率计算公式为：
\[P(s) = p(w_1)p(w_2|w_1)...p(w_n|w_1...w_{n-1}) = p(w_1) \prod_{i = 2}^np(w_i|w_1w_2....w_{i-1})\] #### 2. 历史： 从上式中我们看得出：对于第i个词的概率，他是与前i-1个词紧密相关的，我们就称那i-1个词为这第i个词的历史。 ### 二）n元语法模型：
1.对于这个模型来说，我们需要规定他的n的值，要求的历史的长度就是这个n。
2.同时我们要注意，n的值不能取得太大，n值常取$$3
3.n = 1，我们称为1元文法，也可被记作为：unigram，表示每个词出现的概率相互独立。
4.n = 2， 我们称其为二元文法，它出现在第i位上的词仅与前一个词有关，二元文法模型又称作一阶马尔可夫链，或是马尔科夫模型，记作bigram。
举个例次，如果我们要计算P(u|v),也即，在历史v后u出现的概率，使用如下公式： \[ P(u|v)=\frac{p(uv)}{p(v)} \] P(uv)为短语uv出现的频数，p(v)为词v出现的词频。
5.n = 3， 我们称其为三元文法，它出现在第i位上的词仅与前三个词组成的历史有关，也被称作是二阶马尔可夫链，记作: trigram
三）基于N元语法模型的分词：
我们通过N元语法模型获得了词出现的概率大小后，可使用如下公式进行划分的概率计算： \[
P(s) = p(w_1)p(w_2|w_1)...p(w_n|w_{n-1}) = p(w_1) \prod_{i = 2}^np(w_i|w_{i-1})
\] 为了将第一项也统一到连乘符号中，我们假装s开头处多了一个字符叫做：
我们假设Tset是一个句子：
这里我们期望这样的的一个划分(W)：在当前文本下，W是可能性最大，表示成公式就是： \[ W = arg \max_{w}P(w|Test) = arg \max_{w}\frac {P(Text|w)P(w)}{P(Test)} \] 其中，P(Test)为归一化因子，是共有的分母，比较式可以忽略。
P(Text|w)表示在给定的划分情况下还原出原文本的概率，应为1.
所以我们最终只是再求一个可以让P(w)最大的w作为我们的期望划分。这个P(w)就可以用N元语法模型来求解。
二. 马尔科夫模型：
一）模型介绍：
在N元语法模型中，如果N > 1，就对应着马尔科夫模型，具体对应方法如下：
我们有一个大小为n的有限状态集：\(S = \lbrace s_1, s_2, ...., s_n\rbrace\)，而随着时间的推移，系统将从一个状态转移到另一个状态。而在一个任务中，我们还可以有一个状态序列：\(Q = q_1, q_2, ...., q_t\)，其中\(q_t\)表示的是系统在t时刻所处的状态，这些个状态都应是S中实际存在的。
在我们的汉语分词中，我们的状态就相当于以此划分得到的一个词\(w_i\)。我们需要这么认为，下一时刻的状态，也即\(q_{t+1}\)在时间的影响下，它是要与之前的历史有关的，也即，在下一时刻是否处于某一状态，多大概率处于该状态，应该受之前的历史情况影响，也即（可以类比上面的N原语法模型）： \[ P(q_{t+1} = s_j|q_1,q_2,...q_t), 其中{q_1,q_2,...q_t,s_j} \subseteq S。 \]
若只与他前一时刻的历史有关，就变成了一个离散的1阶马尔可夫链： \[ P(q_{t+1} = s_j|q_1,q_2,...q_t) = P（q_{t+1} = s_j|q_t = s_i) = a_{ij}, 其中q_1,q_2,...q_t,s_j全部取自S。 \]
\[a_{ij} \geq 0\]
\[\sum_{j = 1}^na_{ij} = 1\]
二）例子说明：
1.已知状态转移矩阵求某一划分地概率大小：
已知当前的状态集为：S = {\(s_1, s_2, s_3\)}
状态转移矩阵为：A = [\(a_{ij}\)] = \(\begin{bmatrix} \ &s_1&s_2 & s_3 \\ s_1&0.3&0.5&0.2\\s_2&0.5&0.3&0.2\\s_3&0.4&0.2&0.4 \\ \end{bmatrix}\)
其中P(\(a_{ij}\)表示的是\(P(w_i|w_j)\))
同时我们假设\(P(s_1)=1\)，也即只有\(s_1\)能够作为句子的开头（如果有多个词都能作为句子的开头的话，他们的概率和应等于1。）。
求使用1阶马尔科夫链计算序列 O = \(s_1,s_2,s_3,s_1\)出现的概率：
故： \[ P(O|M) = P(s_1,s_2,s_3,s_1|M) = p(s_1)*p(s_2|s_1)*p(s_3|s_2)*p(s_1|s_3) = 1 * 0.5 * 0.2 * 0.4 = 0.04 \] 2.已知状态转移矩阵求某一最大概率划分：
此处我们需要根据状态转移矩阵地状态转移关系作为边，状态转移对应的概率作为变得值，在原文本装上构建一个图，计算方法也是使用的动态规划方法，和最短路径分词方法中的类似。变化之处在于：在原文本串的开头加一个