CRF 维特比算法

真的难，一个CRF算法折腾了好久，总结一下

首先学东西真的急不得，我是因为要做nlp的ner，github上找了代码，基本你上都BiLstm+crf或者bert+crf，然后调代码测试，但是bert+crf的效率太慢了想优化一下，就想用BiLstm+crf的方式对比一下性能和准确率，因为之前文本分类用的pytorch，所以一直找的pytorch的BiLstm+crf的代码，但是基本上没有找到pytorch的BiLstm+crf的比较好用的批量运行的代码，找了一个调试了半天训练不收敛，然后就是一边学pytorch，一边学crf，一边学深度学习以及看一些知识蒸馏的东西，因为想通过知识蒸馏优化模型的速度。
主要还是crf这块学习路线有些曲折，还是应该一步一步来，首先需要一个可运行的BiLstm+crf与之前的bert+crf做性能和准确率的对比，最好的其实就是pytorch官方提供的代码，虽然没有批量运行功能，性能上可能有差异，但是这应该是最好的上手教程了，用官方的教程代码调了一晚上接入数据，然后就可以开始训练，能够得到训练效率，推理效率，准确率这些重要的结果，这才算是一个有效的成果。相比之前在GitHub上找了半天代码手动调浪费了好多时间，还是官方的东西更靠谱。
然后是crf的学习，想把官方的BiLstm+crf代码改成批量计算版，所以研究了下crf，折腾了很长时间，看了各种代码和博客，总结下就是还是要一步一步来，条件随机场crf运用于序列标注问题，基本模型，隐式马尔科夫模型，观测值，隐状态，初始状态矩阵，观测矩阵，状态转移矩阵，隐式马尔科夫模型的两个假设，一阶马尔科夫假设和观测独立性假设，然后模型要解决的3个问题，1)求给定观测序列的概率，2)模型训练，3)求给定观测序列最可能的隐状态，1用的前向算法，2直接统计概率，3使用维特比算法。然后crf解决了隐式马尔科夫的什么问题，就是消除了那两个假设，通过不对模型做局部归一化，根据特征值即发射矩阵和状态转移矩阵计算得到整个序列的一个得分，包括求给定观测序列的所有隐状态序列的得分S,和实际隐状态序列的得分s，通过softmax函数，先对各个得分取e的幂然后归一化，之后取负对数为损失函数，进行训练，其中求S的过程即为隐马中的问题1，使用前向算法，最后预测的过程即为问题3，同样使用维特比算法。
总结：
1.选择很重要，尽量优先做能最快有成果的事情，这样可以增加自己的信心和动力。
2.看东西学东西尽量选择官方的或者使用者较多的，坑会比较少，有坑也应该有人踩过，多看看github上的issue

3. 确定要学一个算法或者技术的时候还是要一步一步来，不能直接就想着看篇文章就能看懂，动手写代码或者解析是很好的学习方式。

P=[[1,2,3],[3,6,3],[9,8,4],[2,4,9]]
A=[[1,7,3],[9,2,8],[2,8,4]]
last_step_score = [0,0,0]
cur_step_score = [0,0,0]
last_cur_step_score = [0,0,0]
last_step_path = [[0],[1],[2]]
cur_step_path = [[0],[0],[0]]

last_step_score=P[0]

# i为步数，j为当前步的状态 ， k为前一步的状态
for i in range(1,len(P)):
    for j in range(len(A)):
        for k in range(len(A)):
            last_cur_step_score[k] = last_step_score[k]+ A[k][j]+P[i][j] #由k转移到j时当前步的得分
        max_score = max(last_cur_step_score)
        last_step_tag = last_cur_step_score.index(max_score)
        cur_step_path[j] = last_step_path[last_step_tag]+ [j]           #更新路径
        cur_step_score[j] = max_score                                   #更新得分
    last_step_path = cur_step_path.copy()
    last_step_score = cur_step_score.copy()
print(cur_step_path[0])
print(cur_step_path[1])
print(cur_step_path[2])
print(last_step_score)

#暴力算法
import numpy as np

score = np.zeros([3,3,3,3])

for i in range(len(A)):
    for j in range(len(A)):
        for k in range(len(A)):
            for l in range(len(A)):
                score[i][j][k][l] = A[i][j] + A[j][k] + A[k][l] + P[0][i] + P[1][j] + P[2][k] + P[3][l]

print(score.max())
print(np.where(score==score.max()))

维特比算法代码，也是折腾了很长时间，之前看了知乎上一个答案理解了这个算法，写的时候还是遇到了一些阻碍，主要还是对数据结构和代码的基础不熟悉，写一个算法最重要的就是选择一个最适合的数据结构去存储数据，这里使用维特比算法，是一种动态规划算法，多阶段决策过程的最优化问题，含有递推的思想以及各种数学原理。每一步有n条路径，需要存储的是每一步每条路径的最大得分和路径，最简单的想法就是用nlength的数组去存路径，用n1的数组去存得分。这个时候由于自己对于python一些数据结构的不熟悉就出现了问题，每一步我们需要对每一个当前路径的所以前一个路径计算得分，然后取最大值，需要计算n*n次，在这个过程中上一步的得分和路径需要全程保留，在一步计算完了之后再整体替换，因为每次计算下一步的时候都要使用上一步的所有得分和路径，所以需要路径和得分都需要两个数组，一个是当前的数据，一个是上一次的数据。然后我再更新的时候也出现了问题，之前使用=进行替换，但是python中数组的替换需要使用copy函数进行替换，还是对python的基础数据结构理解有问题。还有就是初始值得问题，应该想把第一个发射矩阵得分算法来然后再开始循环。

代码可以优化的地方：
1.在存储当前路径时应该是需要存储所有的路径，只需要存储上一步的路径到这一步的路径。

for k in range(len(A)):
    last_cur_step_score[k] = last_step_score[k]+ A[k][j]+P[i][j] 
max_score = max(last_cur_step_score)
last_step_tag = last_cur_step_score.index(max_score)

可以直接简化为

score,index = max((last_step_score[k]+ A[k][j]+P[i][j],k) for k in range(len(A))