概率图模型

        概率图模型（Probabilistic Graphical Model）是用图结构来表示多元随机变量之间条件依赖关系的模型。在图模型中，节点表示随机变量，边表示变量之间的依赖关系。概率图模型可以分为有向图模型（如贝叶斯网络）和无向图模型（如马尔可夫网络或马尔可夫随机场）。

1.隐马尔可夫模型

（1）马尔科夫模型

        马尔科夫模型是一种统计模型，它描述了状态之间的转换关系。以天气为例，如果昨天是晴天，那么根据马尔科夫模型，我们可以根据一定的概率推断出今天可能是晴天、阴天或雨天。如下图：

        通过今天的状态，我们可以预测明天的情况；同理，借助明天的状态，我们也能推知后天的情况。这种连续的状态转换，就如同一个链条，一环扣一环。为了实现这一系列的预测，我们首先需要定义一个初始状态，它将成为我们预测的起点。

        在一阶马尔科夫模型中，虽然后面的天气跟前面很多天的天气都有关，但是为了简化问题，我们定义后一天的状态只和前一天的状态有关系。在上面这个例子中：

状态：晴天，多云，雷雨

状态转换概率：三种天气状态间的转换概率

初始概率：

根据以上条件，可以计算今天(t=1)的天气状况：

        今天为晴天的概率=初始晴天概率X晴天转晴天概率+初始多云概率X多云转晴天概率+初始雷雨概率X雷雨转晴天概率。

 （2）隐马尔可夫模型

        隐马尔可夫模型（HMM）的核心思想是对一个被假设为具有不可观测（隐藏）状态的马尔可夫过程系统进行建模。HMM允许你基于一系列观察事件预测一系列隐藏状态。

         现在假设我们无法直接观察到天气状况，我们只能观察到海藻的状况，海藻状态和天气有着密切的关联。海藻是能看到的，那它就是观察状态，天气信息看不到就是隐藏状态。我们的目标是通过观察状态预测隐藏状态。

          

  首先，引入隐马尔科夫模型假设，它的目的是简化条件概率的求解：

• 齐次马尔可夫假设：当前的状态只和前一状态有关

• 观测独立假设：某个观测只和生成它的状态有关

 隐马尔可夫模型关注的3个问题：

         给定初始概率(π)，隐藏状态转移概率矩阵(A)，生成观测状态概率矩阵(B)。

模型为：

 即模型与观测序列之间的匹配程度。

 

即训练模型得到参数，以更好的描述观测序列。 

即根据观测序列推断模型的隐状态。

（3）暴力求解方式

         我们要求的是在给定模型下观测序列出现的概率，那如果我能把所有的隐藏序列都给列出来，也就可以知道联合概率分布 

          其中，隐藏状态和观测状态的联合概率分布为隐藏序列的条件概率乘以生成观测状态概率矩阵

          在给定模型下，一个隐藏序列出现的概率，那就由初始状态求得，T时刻的状态等于T-1时刻的状态乘以状态转移矩阵，依此类推。因此，隐藏状态的条件概率可求为：

        因此，对于固定的隐藏序列，得到观察序列

 的概率为：（观测状态由隐藏状态决定，它们之间假设是独立的）

        联合概率：

         观测序列概率（上面得到的是一个隐藏序列的联合概率，而我们需要得到所有的隐藏序列的联合概率，然后求和）：

         复杂度：如果隐藏状态数有N个，时间复杂度为

         解释：当有N个隐藏状态的时候，T时刻的隐藏序列将有N^T个，每个隐藏序列的计算的时间复杂度为2T。

（4） 前向算法

利用动态规划求解，即以空间换取时间，避免重复的计算

        给定t时刻的隐藏状态为i，观测序列为o1,o2...ot的概率叫做前向概率：这是很容易求的

        如果我们求出所有可能状态，不就能够求解了吗

         

         第一个时刻：

        表示第一时刻的隐藏状态为i，观测序列为y1，

 现在到了第t时刻，状态为j，那t+1时刻状态为i表示为：

 现在到了第t时刻，状态为j，那t+1时刻状态为i表示为

 其中t时状态为j的前向概率为：转移到t+1时刻状态为i的概率为

 但是这里要考虑t时刻所有的可能：还要得到t+1的观测

 最终结果依然是需要对各种隐藏状态下的观测状态的条件概率求和。

在前项算法中，t时刻的隐藏状态有N种，t+1时刻的条件概率为N种，前向算法的时间从t=1~T进行遍历；因此时间复杂度为O（TN^2

（5）后向算法

        与前向算法类似，与前向算法相似，但它从后向前递归地计算后向变量。也就是递归求解。

（6）参数估计

        当模型的初始概率(π)，隐藏状态转移概率矩阵(A)，生成观测状态概率矩阵(B)未知时，此时涉及到参数估计问题，使用EM算法求解。

1. 初始化：选定模型参数的初始值。通常，这些初始值可以是随机的，或者基于某种启发式选择的。HMM的参数通常包括初始状态概率π，状态转移概率A和观测概率B。
2. E步（期望步）：在这一步中，我们使用当前的模型参数来计算隐变量的期望。对于HMM，这涉及到计算给定观测序列和当前模型参数下，每个时刻t处于状态qi以及从状态qi转移到qj的期望值。这些期望值是通过前向-后向算法（Forward-Backward Algorithm）来计算的。
3. M步（最大化步）：在这一步中，我们使用E步计算出的隐变量的期望值来更新模型参数。对于HMM，这意味着我们要更新初始状态概率π，状态转移概率A和观测概率B。更新这些参数的方法是基于这些参数的最大似然估计，利用在E步中计算出的期望值。
4. 迭代：重复E步和M步，直到模型参数收敛或者达到预设的迭代次数。每次迭代，我们都会使用更新后的模型参数来重新计算隐变量的期望值，然后再用这些新的期望值来更新模型参数。

2.马尔可夫随机场

        马尔可夫随机场是一种无向图模型，用于描述一组随机变量之间的空间依赖关系。在MRF中，随机变量对应于图中的节点，而变量之间的依赖关系则通过边来表示。MRF的关键特性是它具有马尔可夫性，即每个随机变量的条件概率分布仅依赖于它的邻接变量。

        在马尔可夫随机场中，联合概率使用极大团的势函数的乘积表示。 

         

         

3.条件随机场（CRF）

        条件随机场是一种判别式概率模型，它属于无向图模型的一种。在CRF中，我们给定一组输入随机变量（观测序列），目标是预测另一组输出随机变量（标记序列）的条件概率分布。CRF假设输出随机变量构成马尔可夫随机场。

CRF的概率图表示

        在CRF的概率图表示中，通常有两种类型的节点：观测节点和标记节点。观测节点对应输入序列中的每个元素，而标记节点对应输出序列中的每个标记。边则连接相邻的标记节点，表示它们之间的依赖关系。

        CRF中的条件概率分布可以通过定义在团（clique）上的势函数（potential function）来描述。团是无向图中的完全连接子图。在CRF中，我们通常关注两种类型的团：节点团和边团。节点团包含单个标记节点，而边团包含相邻的标记节点对。

        势函数定义了团中变量的兼容性或相关性。对于节点团，势函数通常与观测节点和对应的标记节点有关，它衡量了给定观测下某个标记的可能性。对于边团，势函数衡量了相邻标记之间的兼容性或转移概率。

CRF的计算与推断

        CRF的条件概率分布可以通过将所有团的势函数相乘并归一化来计算。然而，由于归一化常数的计算涉及到对所有可能的标记序列进行求和，这通常是一个难以处理的问题。因此，在实际应用中，我们通常使用近似推断方法，如动态规划（如维特比算法）或采样方法（如吉布斯采样）来找到最可能的标记序列或计算条件概率。

4.学习与推断

        推断（Inference）则是基于概率图模型所定义的联合概率分布，对目标变量的边际分布或以某些可观测变量为条件的条件分布进行推断。具体来说，推断问题可以分为两类：精确推断和近似推断。

1. 精确推断：希望能计算出目标变量的边际分布或条件分布的精确值。然而，一般情形下，此类算法的计算复杂度随着极大团规模的增长呈指数增长，因此适用范围有限。变量消去法是最直观的精确推断算法，也是构建其他精确推断算法的基础。但它有一个明显的缺陷：若需计算多个边际分布，重复使用变量消去法将造成大量的冗余计算。
2. 近似推断：希望在较低时间复杂度下获得原问题的近似解。此类方法在现实任务中更常用。近似推断方法大致可以分为两类：确定性近似（如变分推断）和随机近似（如马尔可夫链蒙特卡罗方法，简称MCMC）。这些方法的目标都是在可接受的计算成本下，尽可能地接近真实分布。

精确推断

（1）变量消去

        核心思想: 变量消除（VE）是一种在概率图模型中进行推理的算法，它通过系统地从方程中消除变量，简化了边缘概率的概率的计算。

         在VE中，目标是计算某些变量的边缘概率，而不必对模型中其他变量的所有可能配置进行求和。这是通过一次消除一个不相关的变量来完成的，利用模型的因子分解属性来降低计算复杂性。过程涉及以一种不再需要被消除变量的方式操纵和结合因子（概率分布），逐步简化模型，直到只剩下感兴趣的变量。

        想象你在图书馆中寻找一本特定的书。你不需要检查每一本书，而是首先排除你知道不包含它的部分（例如，如果你正在寻找一本科幻小说，你就跳过历史部分）。然后，在正确的部分内，你逐个排除书架，等等，直到找到这本书。变量消除也是类似地通过在每一步丢弃不相关的信息来简化查找你感兴趣的概率的过程。

（2）信念传播

核心思想: 信念传播（BP）是一种在图形模型中使用的推理算法，包括贝叶斯网络和马尔可夫随机场，用于计算边缘分布和每个变量的信念。它通过在图的节点（变量和因子）之间传递消息来操作，根据从其邻居收到的消息迭代更新每个节点的信念。

        这个过程从叶子（只有一个邻居的节点）开始发送它们的初始消息。然后每个节点计算一个要发送给每个邻居的消息，通过对发送节点的所有可能值进行整合，考虑来自其他邻居的传入消息和节点自己的证据（如果有的话）。这个程序重复进行，消息来回传递直到收敛，在这一点上，边缘概率可以计算为每个节点传入消息的乘积。

        想象一群人试图一起解决一个谜题，但每个人只掌握了总信息的一部分。他们开始与他们的直接邻居分享他们所知道的。基于他们学到的，他们然后更新他们对谜题的理解，并再次分享这个更新的信息。这个过程重复进行，直到每个人对整个谜题都有一个一致的理解。信念传播的工作方式类似，每个节点根据来自其邻居的信息更新其对世界状态的“信念”。

近似推断 

（1） MCMC抽样

        核心思想: MCMC抽样是一系列算法的统称，用于从概率分布中抽样，这通过构建一个具有所需分布作为其平衡分布的马尔可夫链来实现。它特别适用于直接抽样不切实际的高维空间。

        MCMC方法通过从一个随机位置开始并进行一系列步骤来生成样本，其中每一步只依赖于当前位置（马尔可夫性质）。这些步骤的方式确保了随着时间的推移，样本位置的分布将近似目标概率分布。两种众所周知的MCMC方法是Metropolis-Hastings算法和Gibbs抽样。

1. Metropolis-Hastings算法：这种方法基于当前位置和一个提议分布提出一个新位置。新位置是基于接受比率接受或拒绝的，接受比率通过比较目标分布下新位置和当前位置的概率来确定。

2. Gibbs抽样：这是Metropolis-Hastings算法的一个特例，用于当从每个变量的条件分布中抽样更容易时。它循环遍历每个变量，从其条件分布中抽样，同时保持所有其他变量固定。

        想象你在一个巨大的派对上，你想弄清楚哪里是最受欢迎的区域，但人太多了，一次看不到整个场景。所以，你随机穿过人群，根据你认为可能接下来会有趣的地方进行步骤（这是你的提议分布）。你使用一些规则来决定是否移动（接受比率），比如如果区域看起来更拥挤（概率更高）。随着时间的推移，你花费最多时间的区域会让你知道派对的热点在哪里。

（2）变分推断

        核心思想: 变分推断（VI）是贝叶斯统计中用于近似复杂概率分布的技术。它将推理问题转化为一个优化问题，目标是找到一个最接近真实后验分布的简化分布。

        在VI中，我们选择一个带有一组参数的分布家族（例如，高斯分布）。然后，我们调整这些参数，使我们选择的分布尽可能接近目标后验分布，通过库尔巴克-莱布勒（KL）散度来衡量。优化过程旨在最小化这种散度，有效地在选定的分布家族内找到最佳近似。

        VI的美妙之处在于，它可以比精确推理方法（如MCMC）更有效地处理大型数据集和复杂模型，尽管它提供的是近似而非精确解。

         想象你试图用很多细节勾勒一个非常复杂的风景，里面有山脉、河流和森林。变分推断就像选择绘制这个风景的简化卡通或抽象版本。你决定代表某些关键特征（分布家族），然后调整你的绘画（参数）以最好地捕捉风景的本质（目标分布）。虽然你的画不会捕捉到每一个细节，但这是一种传达总体场景的更快方式。

5.LDA主题模型

        LDA是一种用于发现文档集合中隐藏主题结构的统计模型。你可以将LDA想象成一个能够自动对文档进行主题分类的机器。这些主题是隐藏的，即它们并没有直接给出，而是由模型通过分析文档中的单词来推断出来的。

        LDA话题模型的核心思想可以概括为利用文档中的词项共现信息来发现隐藏的主题结构。它假设每个文档是由多个主题混合而成的，而每个主题则是一组相关的单词的集合。LDA通过分析文档中的单词出现情况来推断文档的主题分布以及每个主题下单词的分布。

        在LDA模型中，有两个关键的狄利克雷分布：一个是文档-主题分布，表示每篇文档在各个主题上的权重；另一个是主题-单词分布，表示每个主题下各个单词的出现概率。LDA通过训练和学习这两个分布来揭示文档集合中的主题结构。

LDA的工作过程可以大致分为两个步骤：

1. 训练阶段：在这个阶段，LDA模型会分析整个文档集合，并尝试找出隐藏的主题。它会根据文档中的单词出现情况来推断每个文档的主题分布，以及每个主题下单词的分布。这个过程是通过贝叶斯推断和狄利克雷分布（一种多项分布的先验分布）来实现的。
2. 推断阶段：一旦模型训练完成，它就可以用来对新的文档进行主题推断。给定一个新的文档，LDA模型会根据已经学到的主题和单词分布来预测该文档的主题构成。这可以帮助我们理解文档的主题内容，或者对文档进行主题分类。

需要注意的是，LDA模型并不直接告诉我们文档的确切主题，而是给出了文档属于各个主题的概率分布。这意味着一个文档可以同时包含多个主题，只是每个主题所占的比例不同而已。