BiLSTM+CRF:
如果看了之后还看不懂，我自罚三杯！！！
参考的是国外一个很好的博客，原文链接：https://createmomo.github.io/2017/12/06/CRF-Layer-on-the-Top-of-BiLSTM-7/
现在抽空学习一下知识图谱方面的知识
1、Introduction：
1.1 开始之前：
假设我们有两个实体类别：person+location。在我们的数据集中，我们有五个标签，B-person、I-person、B-location、I- location以及标签O。在一个句子x(小明生活在北京)中，小明是一个person实体，北京是一个location实体。其他的元素如“生”“活”“在”都属于O。
1.2 BiLSTM-CRF模型：
BilSTM-CRF模型输入：wi是句子中每一个元素，转换成字向量之后作为输入。
BilSTM-CRF模型输出：每一个元素相对应的标签。
BiLSTM模型输出：每一个元素对每个标签的概率，下图中黄色部分。这些会作为CRF的输入。
1.3 如果没有CRF层
如果没有CRF层，我们貌似也可以BiLSTM层每个元素输出的最大概率标签当做最后结果，如下图所示，w0的最大概率输出标签是B-person，那么直接把这个元素最后结果当做B-person，相应的w1是I-person，等等。
上面说的貌似是正确的，但这种情况下元素之间的标签不存在约束关系，即B-person之后绝对不能跟B-person，I-person之前绝对不能是I-organization，所以就会出现下面的错误。
1.4 CRF层能够学习到上面所说的限制关系
CRF层能够对最后的结果加上一些限制来确保结果是正确的，这些限制可以在训练过程中通过训练集自动学习得到。这些限制可能有：
- 句子中的第一个字可能是B-或者O，不能是I-
- B-label I-label2 I-label3中，label1、label2、label3应该是相同的实体label。也就是B-person后面不能跟I-location
- O后面不能跟I-label，这是明显的。
2 、CRF层：
在CRF层，存在两种类型的scores，这个两种scores是crf层重要部分。
2.1 Emission score：
Emission scores主要来自于BiLSTM层，如下图所示，第一个元素对于B-person的得分是1.5。
为了方便观察，给每个label加 一个index。
我们使用xiyj来代表emission score，其中i表示第几个元素，yj表示label的index。例如上上个图中，xi=1，yj=2= xw1，B-organization=0.1,代表的是第二个元素是B-organization的得分。
2.2 Transition score
tyiyj表示transition score，例如，tB-person，I-person=0.9意味着B-person到下一个字是I-person的概率是0.9，因此，transition包含所有标签之间的转移概率。为了是transition矩阵更鲁棒，我们新加两个label，start和end，start表示一个句子的开始，并不是第一个字，end表示句子的结束。样例如下图所示：
显然上述矩阵是存在一些限制关系的，如：transition矩阵从start到I-person和I-organization的概率是很低的，因为第一个字应该以B-或者O-开始，而不是I-；B-person到I-organization的概率很低，因为不能从一个label的开始到另一个标签的中间；O-到I-的概率很低，因为不可能呀！！！！那么如何获得这个矩阵呢？
实际上，transition矩阵是整个模型的一个参数，训练之前，你可以随机初始化这个矩阵，在训练过程中，这个矩阵会不断的更新，换言之，CRF层能够学习到这个矩阵。
2.3 CRF lossfunction
这一层的损失包含真实路径和所有路径的得分和，真实路径应该是最高得分。（真实路径也就是每个元素的真是标签，举个例子，一个句子有5个元素，标签数量是7个，那么路径个数是7^5，如下图所示，每条路径都有一个得分，也可以说是一个概率，真实路径只有一个，使其最大就好了）
那么总得分就是Ptotal=P1+ P2+……+ Pn=eS1+ eS2+……+ eSn,e是自然对数，下一节会介绍如何计算Si。损失计算公式如下：
LossFunction=PRealPath/( P1+ P2+……+ Pn)
在训练期间，参数的更新使这个比重越来越大。
- 如何计算每个路径的得分
- 如何计算所有路径的总得分
- 计算总得分的时候，有必要列出来所有路径吗（显然是NO）
2.4 真实路径
在训练过程中，lossFunction只需要两个得分，真实路径score+全部路径的score。
真实路径score的计算：句子有5个元素，7个label，真实路径是START B-Person I-Person O B-Organization O END
Si=EmissionScore+TransitionScore
EmissionScore=(x0,START)+(x1,B−Person)+(x2,I−Person)+(x3,O)+(x4,B−Organization)+(x5,O)+(x6,END)
x1,B−Person是第一个字是B-person的概率，这就是BiLSTM这一层的输出呀
x0,START和x6,END我们赋值为0
TransitionScore=tSTART−>B−Person + tB−Person−>I−Person + tI−Person−>O + t0−>B−Organization + tB−Organization−>O + tO−>END
tB−Person−>I−Person是CRF层transition的参数，表示B-person到I-person的转移概率
2.5 全路径score
可以计算出所有路径的score然后相加得到全路径的得分，但这样的话计算量是相当大的，训练是很耗时的。
下面的例子会让你了解如何快速计算全路径的score，一步一步来，不着急，你会明白其中的奥妙。
Step1：LossFunction=PRealPath/( P1+ P2+……+ Pn)
LogLossFunction=log(PRealPath/( P1+ P2+……+ Pn))
最小化
Step2：为了更好的描述，我们假设我们的句子长度只有3。 X=[w0, w1, w2];两个label={ l1, l2}
假设emission score情况如下：xij表示wi是lj的概率，即BiLSTM层的输出
Transition矩阵如下：tij表示label从i到j的概率
Step3: 我们的目标是计算log(eS1+ eS1+ ...+eSN)
整个计算过程和动态规划想类似。所有可能路径的总得分w0是已经计算好的，然后我们计算w0->w1的总得分，再计算 w0->w1->w2。在下面的步骤中，你会看到两个变量，obs和previous。previous储存了前一步的结果，obs表示当前字的 信息。
w0：
obs=[x01, x02]
previous=None
如果我们句子只有一个字，我们就不需要从previous中获取结果了，因此previous是None。那么很显然，所有路径的得分 就是log(ex01+ ex02)。
w0->w1：
obs=[ x11, x12]
previous=[x01, x02]
1.把previous和obs扩展成矩阵：
为什么要扩展呢？因为扩展之后才能有效计算所有路径的总得分呀。
2.计算previous、obs和transition score的和：
举个简单的例子你就理解了，假设只有两个元素，两个label，那么路径是不是有4条，即上面scores里面的东西， scores 里面每个元素的得分就是一个路径的得分，包括emission score和transition score，这也是为什么要把previous 和obs扩展成矩阵了，因为这样元素之间的相加可以罗列出所有的矩阵呀。那么下一次迭代的previous是什么呢，就是我 们的scores呀，只不过样式需要变换一下：
为什么要这种样式呢?我们分步计算一下就知道了：
最后这个结果和直接求e求和再求log的效果是一样的。看着previous是两个元素，实际上还有四条路径。
w0->w1->w2：
接下来的迭代和上面的几乎是一样的了。
obs=[ x21, x22]
previous=[log(ex01+x11+t11+ ex02+x11+t21), log(ex01+x12+t12+ ex02+x12+t22)]
1.把previous和obs扩展成矩阵：
2.计算previous、obs和transition score的和：
下一次迭代的previous就是：看着复杂，实际很简单。
分步计算可以知道，三个元素时，一共有8条路径，
发现没？完整的8条路径，就是全路径的得分了！！！
2.6 如果预测一个句子的label
Step1：emission score和transition score
假设句子还是三个字：X=[w0, w1, w2]，且已经得到相应的emission score和transition score。
Step2：如果你了解Viterbi算法（之前了解过，貌似忘了，之前的博客有介绍HMM算法，和Viterbi差不多）。α0是历史最好 得分 。α1是相应标签的indexs。
w0：
obs=[x01, x02]
previous=None
现在我们只观察到第一个字w0，如果obs=[ x01=0.2, x02=0.8]，显然，w0最好的结果就是l2。
w0->w1：
obs=[ x11, x12]
previous=[x01, x02]
（1）老规矩，把previous和obs扩展成矩阵：、
（2）计算previous、obs和transition矩阵的和：
到这里你会不会觉得这和之前求总得分的步骤是一样呀，不要着急，慢慢看。
previous=[max(scores[00], scores[10]), max(scores[01], scores[11])]
例如，如果我的得分是
那么我们下一次迭代的previous就会变成
previous=[max(scores[00], scores[10]), max(scores[01], scores[11])] = [0.5, 0.4]
这里previous存储的是前一个字的每一个label的最大得分，和HMM很像啊啊啊啊啊！
Example Start：
上述例子中，我们只有两个label，这两个label的index是0和1,。previous[0]表示到达前一个字是label1的最大 值，同理，previous[1]表示到达前一个字是label2的最大值。每一次迭代中，变量previous存储到达每一个 label的最大得分值。换言之，每一次迭代中，我们都存储了到达每一个label的最优路径。
Example End：
我们上面提到过，我们还有两个变量去存储历史信息α0和α1。
迭代时，我们把最优得分信息放入α0：
α0 = [(scores[10], scores[11])] = [(0.5, 0.4)]
α1中存入相应的列坐标：
α1 = [(ColumnIndex(scores[10]), ColumnIndex(scores[11]))] = [(1, 1)]
如何解释呢，l1的下标是0，l2的下标是1，所以（1, 1）=（l2, l2）表示当前字wi和li。具体来说就是对于w1 时，到达l1（这个l1是（l2, l2）中第一个元素l2所以在位置是0）的最大值的上一个标签是l2，即到达0.5的路 径是l(i-1) = l2 –> l(i) = l1。
到达l2（这个l2是（l2, l2）中第二个元素l2所以在位置是1）的最大值的上一个标签是l2，即到达0.4的路径是
l(i-1) = l2 –> l(i) = l2。
l(i-1)指的是字w(i-1)的标签。相当于保存了路径。
w0->w1->w2：
接下来的迭代和上面的几乎是一样的了。
obs=[ x21, x22]
previous=[0.5, 0.4]
1.把previous、obs扩展成矩阵：
- 然后还是求和：
- 然后计算找到最大值，更新previous：
previous=[max(scores[00], scores[10]), max(scores[01], scores[11])]
假设这个得分是：
那么previous=[0.8, 0.9]，实际上previous[0]和previous[1]中最大的一个就是最优路径的得分
同时，我们需要更新α0和α1：
α0 = [(0,5, 0.4), (scores[10], scores[01])] = [(0,5, 0.4), (0,8 0.9)]
α1 = [(1, 1), (1, 0)]
我觉得我有必要再强调一下α1，现在到达w2的l1和l2的最优路径分别是l2 –>l1 ->l2和l2 –>l2 ->l1
Step3：找到最高得分的最优路径：
实际上面已经说过了，α1中保存的就是最优路径，只要复现出来就ok了。算了，还是再说一遍吧。
w1->w2：
α0 = [(0,5, 0.4), (0,8 0.9)]
α1 = [(1, 1), (1, 0)]
最大得分是0.9呀，相当于w2的 标签是l2；再看α1，到达l2的上一个字w1的标签是l1，所以最后一条连线就是 l1- l2
w0->w1：
上一个w1的标签是l1，那么到达l1的上一个字w0的标签是l2，所以整个路径就是l2 –>l1 ->l2。
3、Chainer Implementation
终于到代码实现了，但作者使用chainer实现的，所以不写了吧，毕竟没用过，改天贴上自己的代码，整个算法过程肯定理解了吧。