LDA 假设文章中的单词是相互独立的，而在 HMM 中所有观察结果并不是相互独立的。

因此，对于机器学习文章，LDA 会将“机器”和“学习”拆分为两个词，而 HMM 会将其视为一个词。

Z12状态2

.. .

状态n

概率

P1

P2

...♼信号向量。

上面的n维向量就是初始概率分布，记为π。

状态转移矩阵

但是Z2不能“等于上面”，因为Z2和Z1不独立，所以Z2处于状态1的概率为：当Z1处于状态1时，Z2处于状态1，并且Z1处于状态1.状态2，Z2状态1，...，Z1状态n，Z2状态1，所以下表是

即：Z1->Z2对应一个n*n矩阵。

同理：Zi -> Zi+1对应一个n*n矩阵。

上面的n*n矩阵称为状态转移矩阵，用An*n表示。

当然，如果要说的话，状态转移矩阵 Zi -> Zi+1 -> Z i+1i +1i+1转移矩阵的判定相同，即只有一个状态转移矩阵。

图1的第一行已经完成，这是第二行。

观测矩阵

如果对于 zi 有：状态 1，状态 2，...，状态 n，则每个状态 zi 将产生以下 m 个观测值之一：观测值 1，观测值 2，...。 ..，观测值 m，因此有以下矩阵：

这可以用n的矩阵表示，也就是观测矩阵，称为Bn*m。

因为HMM可以用上面的π、A、B来描述，所以我们可以说：HMM是由初始概率分布π、状态转移概率分布A、观测概率分布B决定的。为了表达方便，取A、B , π 用 λ 表示，即：

λ = (A, B, π)

示例

比如我们相对下面这行进行分词： 如果分了怎么办像这样：找到“终止词”，然后根据单词终止符来划分单词。含义：对于这行词来说，“welcome、attend、me、de、guest”是最后一个词，所以最后一个词分隔就是：welcome/to/my/the/blog

让我们用上面的知识来创造此示例的 HMM 为 A、B、π：

初始概率分布确定：

1。对于每个样本，我们的目标是确定它是否是“终结词”，因此对于每个样本，状态只有 n= 2：状态 1 - 是，状态 2 - 否。

2，所以初始概率分布π为：

π = {p1, p2}

P1：整个句子中第一个单词作为非终结词的概率

第一个单词整个句子该词作为最后一个词的概率

确定状态转移矩阵：

我只知道有n=2个状态，所以直接得到状态转移矩阵，即状态转移矩阵是一个n*n矩阵，如下：

A=

p11：单词不结束的概率->单词不结束。

p12：可能的单词未结尾 -> 最后一个单词。

p21：结束词->非结束词的概率。

p22：停止词 -> 可能的停止词。

确定观察矩阵：

如果目标文本使用Unicode编码，那么上面的单词包含0到65535之间的数字，那么我们的观察将有m=65536，所以观察矩阵是...... n*m 矩阵，如下：

B=

p1,0：Unicode 编码中 0 对应的汉字作为非终结符的概率

p1,65535：Unicode 中非终结符为 65535编码 终止词概率

p2,0：Unicode 编码中 0 对应的一个汉字是停用词的概率

p2,65535：对应 6 个汉字的概率。 Unicode编码是一个停用词

PS：为什么x有65535个观察值？ “欢迎来到我的博客”显然只有8个字。因为HMM面临的真实情况，即：存在Z1=“非终结词”的情况，那么根据这种情况从65535个单词中选择单词x1=“欢”，然后根据状态转移矩阵，接下来转入Z2=“停止词”，然后根据Z2从65535个单词中选出单词x2=“问候语”，这样最终就生成了这句话。

HMM 的两个基本属性

同质性假设

当前状态的总和与先前状态相关。用公式表示为：

P(zt|z t-1t |z 3t-1,

，zt-2，xt-2，...，z1。 所有观察结果都是相互独立的。：

P(x z , xt-2 ,..., x呢 其实如果严格考察的话，x1 和 x2 确实不独立，因为 x1 是由 z1 生成的， x2是由z2生成的，但是z2的形成是受z1影响的，所以x1和x2一定是相关的，但是为了学习和简单应用，假设产生x1的z1和产生x2的z2不是独立的，但x1和x2是独立的。

三题HMM

现在有一些问题： 1、知道HMM参数λ=(A,B,π)和观察顺序O={o1,o2 , ..., oT 根据模型 λ 观测序列 O 出现的概率 P(O | λ)。

2.如何确定 HMM 参数？

例子：目前中文分词的一个小例子。

π的初始概率分布很容易确定：是否是终结词的概率。

观测矩阵B也很容易确定：1/65535

但是状态转移矩阵如何确定呢？我如何知道下一个单词是终结词的概率？

3，了解HMM的参数λ=(A,B,π)和观测序列O={o1,o2,...,o❀如何计算State以条件概率对给定的观察序列最大的 P(I|O, λ) 进行排序，即：

对于中文分词，我想知道如何分词。

上面三题：

第​​一题叫做：概率计算问题。

解法：前向-后向算法（动态规划算法）。

第​​二个问题叫做：学习问题。

解决方案：如果状态序列已知，则使用最大似然估计。然而，HMM状态的序列是未知的，即它包含隐藏变量，因此必须使用Baum-welch算法（实际上，它本质上是一种EM算法）。

第​​三个问题叫做：预测问题/解码问题。

解法：维特比算法（动态规划算法）。

概率计算问题

该问题有两种解决方案：

1，直接/暴力算法。

2，前向/后向算法。

上述两种算法中的“粗暴法”在实际应用中不会使用。

P：为什么这么说！ （踢）

A：了解直接/强力算法可以帮助您创建 Baum-welch 算法。 （反击！）

直接/蛮力计算方法

问题：HMM 的参数 λ 已知，观测序列 O = {o1, o, ... 3T }，找到P(O|λ)

这个想法的本质：奇迹可以通过强大的力量发生。

想法：

1，列出长度为T的所有可能状态序列 I = {i1, i2, ..., i♷;

2. 求每个状态序列 I 和观测序列的联合概率 P(O,I|λ)；

3。将所有可能的状态序列 Σ_IP(O,I|λ) 相加得到 P(O|λ )。

步骤：

1。主要目标是求 O 和 I 一起出现的组合概率，即：

P(O,I|λ)= P(O|I, λ)P(I|λ )

那么你需要找到 P(O |I, λ) 和 P(I|λ)。P I|λ) = P(i1,i2,..., iT |λ)♹♹ λ) P (i , i i 1, λ)P(i3, i4, ..., iT |) |)

=P （我？ (i T | iT-1, λ)

| iT-1 , λ)

概率 P(i)上面是 P(i) 状态 i1，P(i2 | i1, λ) 是从状态 i1 到 i2 的转移概率。分别得到结果：

PS：上面的i1i2代表' P(O|I, λ), i的第i1行第i'列‿。 e. ，对于稳态序列 I，观察到序列 O 的概率为：

4。切换到第一步求 P(O,I|λ)。

5，将所有可能的状态序列 I 求和，得到观测序列 O 的概率 P(O|λ)：

时间复杂度：

每个时刻有 n 个状态，其中有 t 个时刻全部的。 ，根据上面第5步，我们可以知道每个时刻都要乘以2T-1，所以时间复杂度为：O((2T-1)nT)

前向算法/后向算法 前向算法

前向概率 - 后向概率

如下图所示：

第一行是未观测到的状态序列，第二行是可观测到的观测值序列。

前向概率的定义为：当第t时刻的情况为i时，被观测前的y1，y2，...，yts。 。概率，即：

后向概率的定义为：当第t时刻的情况为i时，观察到yt+1，yt如下。分别时间。概率 , ..., yT，为：

前向算法

如果前向概率 t=T i (T) = p(y1,y2, ..., yT, q❀T, q❀ = i | λ)

则这意味着当最后一个时刻在我第-状态 ，观察到 y1, y2, ..., yT 的概率不是直接结果。方法" "在步骤 4 中找到 P(O,I|λ)。

因此，如果我们将 αi(T) 与 i 相加，即：

T) + α2(T) + ...+ α n(T) 公式1

是观测值的概率P(O|)。那么如何计算α1(T) +α2(T) + ...+ αn(T)呢？

嗯。 ..如果我们可以计算出 T-1 时刻的前向概率，即 α1(T-1) +α2(T-1) + ... + 如果 αn (T-1)，则可以计算出式1（HMM参数已知，可以根据参数确定）。那么就可以得到T-1时刻的概率，那么就可以得到T时刻的概率。

按照这个想法：啊！我只需要计算1时刻的前向概率就可以算出结果了！

我刚刚得到一个有趣的结果，那就是：当我找到前1时刻的前向概率αi（1）后，与找到最后一个结果相同，然后 i (1)是什么？刻 当第一时刻的第一个状态为No时，Y1的概率是多少。 i，即：

α❀♺i (1) = p (y1, q1=i | λ)

且第一时刻状态的概率为第 i 个国家为 π ，在第 i 个国家获得观测值 y1 的概率为 Biy1，因此：

αi

(t)

单身概率

这里的单一状态是什么？给定观测值 O 和 HMM 参数 λ，在时间 t 处于隐藏状态的概率可写为：

γt(i) = P(i t= q i | O, λ)

PS: O 是所有观测值的集合，即：O = {y = , y = o , …，yT = oT非常好，我们可以估计t时刻的隐藏状态，然后找到隐藏状态的序列！

PS：这确实是一种求隐藏状态序列的方法，但是这样做有一个问题——隐藏状态是独立获得的，也就是说，它没有考虑当时的隐藏状态。 t + 1 由 Condition 给出，其中状态在时间 t 转移时被隐藏。换句话说：这样的隐藏状态就是“每个隐藏状态只是当前时刻最优的，但每个隐藏状态没有考虑到全局情况”。

而且解法也很简单，如下：

两个状态的联合概率

通过“一个状态的概率”得到的t时刻的隐藏状态现在不取“上下文”，那么考虑下面的Context ，即：当时间 t 处于隐藏状态 i 时，时间 t + 1 处于隐藏状态 j，可写为：

editt( i, j) =P( i t O, λ)

解法及推导：

一些希望

学习问题有两类：

1。给出了观察序列和隐藏状态序列。找到隐马。

PS：这种学习就是监督学习。

2，给出了观察序列，但未给出隐藏状态序列。找到隐马。

PS：这种学习是无监督学习，使用Baum-Welch算法。

观察序列和隐藏状态序列都给出

这种方法非常简单：使用大数定理使用频率来估计三个可能的 HMM。

说明：

仍然是使用第一个单词的示例。

初始概率：

i = 0：第一个字母的两倍是最后一个单词/（第一个字符的两倍是最后一个单词 + 时间不是最后一个单词）

i = 1：第一个文本的数量不是最后一个单词 / （第一个文本是最后一个单词的次数 + 第二次不是最后一个单词）

转换概率：

i=0,j=0：第 t 个单词是最后一个单词，单词 t+1 是单词之和/(单词 t -th 是单词，单词 t+1-th。单词是单词数 + 单词 t 是单词，而单词 t+1 不是单词 Vanda +第 t 个单词不是最后一个单词且单词 t+1 为最后一个单词 + 单词数 t-ne 不是最后一个单词且 t+1 也不是最后一个单词）

i=0， j =1、i=1、j=0、i=1、j=1 相同。

观察概率：

i=0,k=0：一个单词在Unicode编码中被编码为0作为单词终止符的次数/（单词在Unicode编码中被编码为0作为单词终止符的次数+数字of times coded in Unicode 编码 一个单词被编码为 0 非终止符的次数)

i=1,k=0: 一个单词在 Unicode 编码中被编码为 0 非终止符的次数/(多少次一个单词在Unicode编码中被编码为0作为终止符的次数+在Unicode编码中被编码为0的单词有多少次不是终止符）

与其他k=j相同。

Baum-Welch算法

其实这个算法的核心是EM算法，因为要解决的问题是：当有一个观测值X，并且该观测值有一个隐变量Z时，求根据 HMM 参数 λ 概率 P( X, Z | λ) 进行组合。 ？即：

所有观测数据写为 O=(o1, o2 …o, o2 …o，o 2.、o、o

T 、i1、i2 … iT )，完整数据的对数似然函数为 lnP(O , I | 所以：) 下面是推导：

描述：

第​​一行：Q EM 函数。

第​​二行：条件概率公式。

第​​三行：

第​​一：直线的分母 第二个表示“最后得到的参数和观测集的联合概率”，对于本次估计没有用处，所以可以丢弃。

也就是说，P(O, I | λ) 在《HMM概率计算问题》的“直接计算法/暴力”中已经解决了。

对于上面的公式，除了HMM参数λ=(A,B,π)之外，一切都是已知的。

上图中，最后一个等号写在第3行，表示一个点：这三行每一行都只包含HMM的一个参数，而我们的目标是求函数Q的最大值，所以只需要需要最后三行。为了便于解释，我将最后三行的三个公式从上到下分别命名为：π公式、α公式、β公式。

使用公式

π 求 π。该公式有一个约束：所有 πi 的总和为 1。

所以对于有约束条件下求极值的问题，拉格朗日乘子法就是答案！

1，拉格朗日函数

2，利用上式求πi的偏导数 与 和 i 若和为1，则消去π，即可得到拉格朗日参数

4。将上式带入第二步公式，可得 π：

而由上式求得 γ 为《HMM 概率计算问题》中“单一状态的概率”中的 γ（PS：不是拉格朗日参数） ”，这样π就计算出来了！

求出α的公式

α 公式可以写成

仍然使用拉格朗日乘子法，我们得到♿上面的公式♿“单一状态的概率” 》《HMM概率计算问题》中的γ ，上式中的Ψ是《HMM概率计算问题》中的《两种状态的联合概率》中的Ψ。《HMM概率计算问题》中的《单状态概率》。对于预测问题：

1、   近似算法，其实就是“HMM概率计算问题”中“单状态概率”的解决方案。

2、维特比算法。下面解释一下。

VIterbi算法

在介绍维特比算法之前，我先用通俗语言描述一下。

让我们面对这个问题：

当你在大学时，你让你的室友给你送食物（如果你在大学，别告诉我你不这样做......），然后你室友问你想吃什么？你回答：“你想吃什么我就吃什么，不过回来后我帮你搬一瓶雪碧，谢谢。”于是有趣的事情发生了：你的室友高兴地给你送来了米饭和雪碧：“我走了，食堂的厨师换了，食堂的收银员换了个女孩！！”然后你问他：“你是哪个食堂、食堂的？”他想了想，回答道：“你猜。”

好吧，你猜一猜~

我觉得是你姐(​​ □′)​​︵┻⁄┻

别急着翻盘。你的室友还在给你送食物，所以我们就满足于一个小恶作剧，并将其视为努力工作的报酬。

PS：假设你们学校有2个食堂，2个食堂。

那么，任务开始了！

首先问：你先去食堂吗？答案是：是的。

好了，购物顺序就结束了，如下：

接下来我们想一想：

第​​一步：宿舍到食堂A和B的距离几乎一样，所以是差不多一样。判断，即从宿舍到食堂A的概率=从宿舍到食堂B的概率，如下；

步骤2：从食堂A、B到食堂1、2有4条路线（A1、A2、B1、B2），那么这4条路线中，到食堂1最短的是A1，到食堂最短的是A1 2是B2。那么这个人总是会选择最近的一个，所以如果他去1号食堂他选择A1，如果他去2号食堂他选择B2，如下：

第3步：看带来的食物，嗯..我记得食堂1有卖这顿饭，但是食堂2不知道，所以就假装没有，然后假设他离开的是食堂1，如下：

第四步：好了，终点确定了，然后退，即选择最近的食堂，所以选择离食堂1最近的食堂A，如下：

第五步：说话。说：“你先去A食堂，再去1食堂，对吗？”他说：“我是第二好，你怎么知道？”

OK，示例完成，我们看一下维特比算法。其实维特比算法就是上面的过程：​ 1、首先将从前到后的步路径的最大概率相加，最后就得到从起点到各个终点的链接。 。 m条路径（假设有m个端点）。

2。确定终点后，反向选择上一条路径。

3、确定最优路径。

我们来看看维特比算法的定义。

维特比算法定义

定义变量δt(i)：表示在时间t时状态为i的所有路径中的最大概率值。公式如下：

过程：

以上符号以前见过，这里就不解释了。为了更好地理解这些步骤，我们举一个例子。

示例

这仍然是一个足球模型。

盒子和球模型 λ= (A, B,π)，状态集 Q={1, 2, 3}，观测集 V={红，白}，

已知观测序列 O=(红，白色，红色），尝试找到最优状态序列，即最优路径 I*= (i1*, i2*, i

♽♽ 。

解决方法：

如下图所示（后续步骤中图中的数字会一一递减）

要在所有可能的路径中选择最优路径，请按照以下步骤操作。

1，当开始

t=1时，对于每个状态i，i=1,2,3，求状态i观察到o1为红色的概率，记录这个概率为i) ，则：

δ1(i) = πib♷

)=πib (i) 红色), i = 1, 2, 3

更改实际数据

δ1(1),(1) = 0, 1 (3) = 8 记住ψ1(i) = 0, i = 1, 2, 3.

2, 当 t=n ❀ 当 t i2 时，找到当 t=1 时观察到状态 j 为红色的路径，当t=2时状态i观察到白色最大概率计算：

同理，当t=3

3时，找到最优路径的终点

令P*表示最优路径的概率，则

最优路径的终点为 i3 *:

最优路径的终点为 i3 *:

* ,i1*：当t=2时，i ❀

(i3*) =ψ3(3 ) = 3

当 t= 2、i1* = ψ 2(i)(i)(i ψ2(3) = 3

然后选择最优路径，也就是说，最有状态的序列 I* = (i1*,i2* , i♷ = , 3, 3)。