笔记写到第二次课了

第一节

[分词]

前缀词典是根据统计词典构建出来的.

构造有向无环图是为了求最大概率路径.

北京大=0, 用于我还可以匹配更长的,只是我自己不存在而已.

最大概率计算

看代码(学了Python后必须重看理解 + 动态规划)

get_DAG

动态规划

get_route

这个代码中n-gram的n是多少:就是1,直接拿词的概率来算。

【55：50】下半场

基于汉字成词能力HMM模型(另外一种分词模型)

前面是基于词典。如果没有前缀词典或者有些词不在前缀词典中,jieba分词使用这种方法识别未登录词。

利用HMM模型进行分词，主要是将分词问题视为一个序列标注（sequence labeling）问题，其中，句子为观测序列，分词结果为状态序列。首先通过语料训练出HMM相关的模型，然后利用Viterbi算法进行求解，最终得到最优的状态序列，然后再根据状态序列，输出分词结果。

序列标注，就是将输入句子和分词结果当作两个序列，句子为观测序列，分词结果为状态序列，当完成状态序列的标注，也就得到了分词结果。

隐含状态和可(可观察)见状态之间有一个概率叫发射概率或者输出概率：D6(6面体骰子掷出1的概率)

HMM模型有三个基本问题：

3.预测问题，也称为解码问题，已知模型 和观测序列 ，求对给定观测序列条件概率 最大的状态序列 ，即给定观测序列。求最有可能的对应的状态序列；

其中，jieba分词主要中主要涉及第三个问题，也即预测问题。

HMM模型中的五元组表示：

- 1.观测序列；

- 2.隐藏状态序列；

- 3.状态初始概率；

- 4.状态转移概率；

- 5.状态发射概率；

这里仍然以“去北京大学玩”为例，那么“去北京大学玩”就是观测序列。

而“去北京大学玩”对应的“SBMMES”则是隐藏状态序列

状态初始概率表示，每个词初始状态的概率

第二节

马尔科夫链太长，提出了一个有名的的算法，维特比算法(没搞懂，需要重看，要求搞懂)

Viterbi算法

Viterbi算法实际上是用动态规划求解HMM模型预测问题，即用动态规划求概率路径最大（最优路径）。这时候，一条路径对应着一个状态序列。

基于HMM模型的分词流程

jieba分词会首先调用函数cut(sentence)，cut函数会先将输入句子进行解码，然后调用_cut函数进行处理。cut函数就是jieba分词中实现HMM模型分词的主函数。cut函数会首先调用viterbi算法，求出输入句子的隐藏状态，然后基于隐藏状态进行分词。

jieba分词实现Viterbi算法是在viterbi(obs, states, start_p, trans_p, emit_p)函数中实现。viterbi函数会先计算各个初始状态的对数概率值，然后递推计算，每时刻某状态的对数概率值取决于上一时刻的对数概率值、上一时刻的状态到这一时刻的状态的转移概率、这一时刻状态转移到当前的字的发射概率三部分组成。

维特比算法比穷举的低:

• 每一步都是动态的，网状的。
• 算法复杂度，计算量：t * (n的平方)
• 也有动态规划的思想？

隐含状态数n

可观察序列长度T

如何通俗地理解维特比算法

马尔科夫模型：新的状态只能他前面的一个状态相关。

HMM要懂

viterbi代码要看懂.

【02：00：00】viterbid的时间复杂度

viterbid的时间复杂度: T * n^2^ 每一次计算 总共要算T步， 每一步 前面n个状态 转换到后面 n个状态 ，挑出来最大的。(n是什么)

【02：03：00】

HMM的应用：