贝叶斯

一、相关公式

1、条件概率公式

设A,B是两个事件，且P(B)>0,则在事件B发生的条件下，事件A发生的条件概率（conditional probability)为：

                     P(A|B)=P(AB)/P(B)

复制

2、乘法公式

1）.由条件概率公式得：

                   P(AB)=P(A|B)P(B)=P(B|A)P(A)    

         上式即为乘法公式；

复制

2）.乘法公式的推广：对于任何正整数n≥2，当P(A1A2…An-1) > 0 时，有：

      P(A1A2...An-1An)=P(A1)P(A2|A1)P(A3|A1A2)...P(An|A1A2...An-1)

复制

3、全概率公式

如果事件组B1，B2，…. 满足

1.B1，B2….两两互斥，即 Bi ∩ Bj = ∅ ，i≠j ， i,j=1，2，….，且P(Bi)>0,i=1,2,….; 2.B1∪B2∪….=Ω ，则称事件组 B1,B2,…是样本空间Ω的一个划分

设 B1,B2,…是样本空间Ω的一个划分，A为任一事件，则：

全概率公式的意义在于，当直接计算P(A)较为困难,而P(Bi),P(A|Bi) (i=1,2,…)的计算较为简单时，可以利用全概率公式计算P(A)。 思想就是: 将事件A分解成几个小事件，通过求小事件的概率，然后相加从而求得事件A的概率，而将事件A进行分割的时候，不是直接对A进行分割，而是先找到样本空间Ω的一个个划分B1,B2,…Bn,这样事件A就被事件AB1,AB2,…ABn分解成了n部分，即A=AB1+AB2+…+ABn, 每一Bi发生都可能导致A发生相应的概率是P(A|Bi)，由加法公式得:

     P(A)=P(AB1)+P(AB2)+....+P(ABn)

           =P(A|B1)P(B1)+P(A|B2)P(B2)+...+P(A|Bn)P(PBn)

复制

4、贝叶斯公式

与全概率公式解决的问题相反，贝叶斯公式是建立在条件概率的基础上寻找事件发生的原因（即大事件A已经发生的条件下，分割中的小事件Bi的概率），设B1,B2,…是样本空间Ω的一个划分，则对任一事件A（P(A)>0),有

Bi 常被视为导致试验结果A发生的”原因“，P(Bi)(i=1,2,…)表示各种原因发生的可能性大小，故称先验概率；P(Bi|A)(i=1,2…)则反映当试验产生了结果A之后，再对各种原因概率的新认识，故称后验概率。

二、朴素贝叶斯

基本思想：朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。

其实并非上式如此简单。 P(yi)是先验概率，P(x | yi)是类条件概率，两者都是未知的。根据仅有的样本数据进行分类时，一种可行的办法是我们需要先对先验概率和类条件概率进行估计，然后再套用贝叶斯分类器。

先验概率的估计较简单，1、每个样本所属的自然状态都是已知的（有监督学习）；2、依靠经验；3、用训练样本中各类出现的频率估计。 类条件概率的估计（非常难），原因包括：概率密度函数包含了一个随机变量的全部信息；样本数据可能不多；特征向量x的维度可能很大等等。总之要直接估计类条件概率的密度函数很难.解决的办法就是，把估计完全未知的概率密度转化为估计参数。这里就将概率密度估计问题转化为参数估计问题，极大似然估计就是一种参数估计方法。当然了，概率密度函数的选取很重要，模型正确，在样本区域无穷时，我们会得到较准确的估计值，如果模型都错了，那估计半天的参数，肯定也没啥意义了。

极大似然估计

极大似然估计的原理，用一张图片来说明，如下图所示：

极大似然估计提供了一种给定观察数据来评估模型参数的方法，即：“模型已定，参数未知”。通过若干次试验，观察其结果，利用试验结果得到某个参数值能够使样本出现的概率为最大，则称为极大似然估计。

总结起来，最大似然估计的目的就是：利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值。

求最大似然估计量的一般步骤： （1）写出似然函数； （2）对似然函数取对数，并整理； （3）求导数； （4）解似然方程。

（1）写出似然函数；

(2) 求解极大似然函数

可以看到，整个朴素贝叶斯分类分为三个阶段：

第一阶段——准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况【确定特征属性】，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，【形成训练样本集合】。 这一阶段的【输入】是所有待分类数据，【输出】是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。

第二阶段——分类器训练阶段，这个阶段的任务就是生成分类器，主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其【输入】是特征属性和训练样本，【输出】是分类器。这一阶段是机械性阶段，根据前面讨论的公式可以由程序自动计算完成。

第三阶段——应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其【输入】是分类器和待分类项，【输出】是待分类项与类别的映射关系。这一阶段也是机械性阶段，由程序完成。

三、贝叶斯网络（概率图模型）

概率图的表达是一张。。。图。。。图当然会有节点，会有边。节点则为随机变量（一切都是随机变量），边则为依赖关系（现在只谈有向图）。一张典型的概率图——贝叶斯网络如下所示： 例：一个聪明人，在一场很难的考试里拿了高分，却得到了一封很烂的推荐信，同时他SAT考试却是高分的概率是多少？

考虑P(D,I,G,L,S)应该怎么计算？如果没有任何先验信息，那么应该是按照条件概率公式： P(D,I,G,L,S) = P(D)*P(I|D)*P(G|I,D)*P(L|I,D,G)*P(S|D,I,G,L);

上式的最后一项，光是对于P(S|D,I,G,L)就需要考虑DIGL所有的可能，并且每增加一个随机变量，计算的复杂程度就会上升一个档次。使用贝叶斯链式法则，那么上式就可以简化成以下形式：

四、隐马尔可夫模型

1）、马尔可夫过程

马尔可夫链是随机变量 S1, … , St 的一个数列（状态集），这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而 St 的值则是在时间 t 的状态。如果 St+1 对于过去状态的条件概率分布仅是 St 的一个函数，则：

这里小 x 为过程中的某个状态。上面这个等式称为马尔可夫假设，即一个状态的转移只依赖于之前的n个状态，当n取1时就是马尔可夫假设。

2）、马尔可夫模型

一个含有 N 个状态的马尔可夫链有 N^2 个状态转移。每一个转移的概率叫做状态转移概率 (state transition probability)，就是从一个状态转移到另一个状态的概率。这所有的 N^2 个概率可以用一个状态转移矩阵来表示( 矩阵的每一行的数据累加和为1)：

3）、隐马尔可夫模型

在很多时候，马尔可夫过程不足以描述我们发现的问题，例如我们并不能直接知晓宝宝的状态是饿了或者困了，但是可以通过宝宝的其他行为推测。如果宝宝哭闹，可能是饿了；如果无精打采，则可能是困了。由此我们将产生两个状态集，一个是可观测的状态集O和一个隐藏状态集S，我们的目的之一是借由可观测状态预测隐藏状态，为了简化描述，将“玩”这个状态去掉，让宝宝每天除了吃就是睡，这也是大多数家长共同的愿望，模型如下：

由此得到O={Ocry,Otired,Ofind}，S={Seat,Szzz}。宝宝在“吃（饥饿）”状态下表现出哭、没精神、找妈妈三种可观察行为的概率分别是(0.7,0.1,0.2)。

怎样表示P(Ot|S)呢（观测到的状态相当于对隐藏的真实状态的一种估计）？在HMM中我们使用另一个矩阵(混淆矩阵)：

混淆矩阵可视为马尔可夫模型的另一个假设——独立性假设：假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其它观测状态无关。

HMM模型的形式定义

　一个 HMM 可用一个5元组 { N, M, π，A，B } 表示，其中：

*N 表示隐藏状态的数量，我们要么知道确切的值，要么猜测该值； *M 表示可观测状态的数量，可以通过训练集获得； *π={πi} 为初始状态概率；代表的是刚开始的时候各个隐藏状态的发生概率； *A={aij}为隐藏状态的转移矩阵；N*N维矩阵，代表的是第一个状态到第二个状态发生的概率； *B={bij}为混淆矩阵，N*M矩阵，代表的是处于某个隐状态的条件下，某个观测发生的概率。 　　在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的，即当系统演化时，这些矩阵并不随时间改变。对于一个 N 和 M 固定的 HMM 来说，用 λ={π, A, B } 表示 HMM 参数。

问题求解

在该模型中，初始化概率π={Seat=0.3,Szzz=0.7}；隐藏状态N=2；可观测状态M=3；转移矩阵和混淆矩阵分别是：

现在我们要解决3个问题：

1.模型评估问题（概率计算问题）

　　已知整个模型，宝宝的行为依次是哭 -> 没精神 –>找妈妈，计算产生这些行为的概率。

　　即：

　　已知模型参数，计算某一给定可观察状态序列的概率。即在已知一个观察序列，和模型λ=（A,B,π}的条件下，观察序列O的概率，即P(O|λ}。

　　对应算法：遍历法、向前算法、向后算法

2．解码问题（预测问题）

　　已知整个模型，宝宝的行为依次是哭 -> 没精神 –>找妈妈，计算这三个行为下，宝宝的状态最可能是什么。

　　即：

　　已知模型参数和可观察状态序列，怎样选择一个状态序列S={S1,S2,…,ST}，能最好的解释观测序列O。

　　对应算法：维特比算法

3.参数评估问题（属于非监督学习算法）

　　通过宝宝的行为，哭、没精神、找妈妈，来确定宝宝的状态转换概率。

　　数据集仅有观测序列，如何调整模型参数 λ=(π, A, B), 使得P(O|λ)最大

　　对应算法：鲍姆-韦尔奇算法

遍历法——解决概率计算问题

遍历法也是典型的穷举法，实现较为简单，罗列可能情况后将其相加即可。观察状态的序列T(随时间增加)是3，每个可观察状态对应的隐藏状态数N为2，共有N^T=2^3 = 8中可能的情况。其中一种情况：

P(Seat1, Seat2, Seat3,Ocry1,Otired2,Ofind3) = P(Seat1)·P(Ocry1)·P(Seat2)·P(Otired2)·P(Seat3)·P(Ofind3) = (0.3×0.7)×(0.1×0.1)×(0.1×0.2) = 0.000042

#遍历法最为有效（因为简单），一旦节点数增加，计算量将急剧增大，

#时间复杂度：每种情况中有2*T个因子，所以遍历法的时间复杂度是O(T*N^T)。

前向算法——解决概率计算问题

时间复杂度：时间复杂度是O(T*N^2)？

　　向前算法是在时间 t=1的时候，一步一步往前计算。

　　其背后的马尔可夫概率公式：

P(W1,W2) = P(W1)P(W2|W1)

P(W1,W2,W3) = P(W1,W2)P(W3|W1,W2)

P(W1,W2,…,Wn) = P(W1,W2,…,Wn-1)P(Wn|W1,W2,…,Wn-1)

1.计算当t=1时，发生Cry这一行为的概率：

　　P(Ocry,Seat) = P(Seat)P(Ocry|Seat) =0.3×0.7=0.21

　　P(Ocry,Szzz) = P(Szzz)P(Ocry|Szzz) =0.7×0.3=0.21

2.计算当t=2时，发生Tired这一行为的概率：

　　根据马尔可夫假设，P(Ot=2)仅与St=1有关，下一天的行为概率是由前一天的状态计算而来，如果St=2=Seat2：

P(Ocry1,Otired2,Seat2)

= P(Ocry1,Seat1)P(Seat2|Seat1)P(Otired2|Seat2)+ P(Ocry1,Szzz1)P(Seat2|Szzz1)P(Otired2|Seat2)

=[P(Ocry1,Seat1)P(Seat2|Seat1)+P(Ocry1,Szzz1)P(Seat2|Szzz1)]·P(Otired2|Seat2)

= [0.21×0.1+0.21×0.8]×0.1

= 0.0189

　　如果St=2=Szzz2：

P(Ocry1,Otired2,Szzz2)

= P(Ocry1,Seat1)P(Szzz2|Seat1)P(Otired2|Szzz2)+P(Ocry1,Szzz1)P(Szzz2|Szzz1)P(Otired2|Szzz2)

= [P(Ocry1,Seat1)P(Szzz2|Seat1)+ P(Ocry1,Seat1)P(Szzz2|Seat1)]·P(Otired2|Szzz2)

= [0.21×0.9+0.21×0.2]×0.5

= 0.1155

3.计算当t=3时，发生Find这一行为的概率：

如果St=3=Seat3，

P(Ocry1,Otired2,Ofind3,Seat3)

= P(Ocry1,Otired2,Seat2)P(Seat3| Seat2)P(Ofind3|Seat3)+

P(Ocry1,Otired2,Szzz2)P(Seat3| Szzz2)P(Ofind3|Seat3)

= [P(Ocry1,Otired2,Seat2)P(Seat3| Seat2)+

P(Ocry1,Otired2,Szzz2)P(Seat3| Szzz2)]·P(Ofind3|Seat3)

= [0.0189×0.1+0.1155×0.8]×0.2

= 0.018858

如果St=3=Szzz3，

P(Ocry1,Otired2,Ofind3,Seat3)

= P(Ocry1,Otired2,Seat2)P(Szzz3| Seat2)P(Ofind3|Szzz3)+ P(Ocry1,Otired2,Szzz2)P(Szzz3| Szzz2)P(Ofind3|Szzz3)

= [P(Ocry1,Otired2,Seat2)P(Szzz3| Seat2)+

P(Ocry1,Otired2,Szzz2)P(Szzz3| Szzz2)]·P(Ofind3|Szzz3)

= [0.0189×0.9+0.1155×0.2]×0.2

= 0.008022

综上，

P(Ocry1,Otired2,Ofind3)

= P(Ocry1,Otired2,Ofind3,Seat3)+ P(Ocry1,Otired2,Ofind3,Szzz3)

= 0.018858+0.049602

= 0.06848

维特比算法（Viterbi Algorithm）——解决解码问题（预测问题）

参照百度百科：

维特比算法的基础可以概括成下面三点：

如果概率最大的路径p(或者说最短路径)经过某个点，比如途中的X22，那么这条路径上的起始点S到X22的这段子路径Q，一定是S到X22之间的最短路径。否则，用S到X22的最短路径R替代Q，便构成一条比P更短的路径，这显然是矛盾的。证明了满足最优性原理。 从S到E的路径必定经过第i个时刻的某个状态，假定第i个时刻有k个状态，那么如果记录了从S到第i个状态的所有k个节点的最短路径，最终的最短路径必经过其中一条，这样，在任意时刻，只要考虑非常有限的最短路即可。 结合以上两点，假定当我们从状态i进入状态i+1时，从S到状态i上各个节的最短路径已经找到，并且记录在这些节点上，那么在计算从起点S到第i+1状态的某个节点Xi+1的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这个节点到Xi+1，j的距离即可。 在本例中，维特比算法实际上是从t=1时刻开始，不断向后计算，寻找概率最大的路径。

1.计算t=1时刻Ocry发生的概率：

δ11 = P(Ocry,Seat) = P(Seat)P(Ocry|Seat)=0.3×0.7=0.21

　　δ12 = P(Ocry,Szzz) = P(Szzz)P(Ocry|Szzz)=0.7×0.3=0.21

2.计算t=2时刻Otired发生的概率：

δ21 =max(P(Ocry1,Seat1)P(Seat2|Seat1)P(Otired2|Seat2),P(Ocry1,Szzz1)P(Seat2|Szzz1)P(Otired2|Seat2))

= max(P(Ocry1,Seat1)P(Seat2|Seat1), P(Ocry1,Szzz1)P(Seat2|Szzz1))·P(Otired2|Seat2)

= max(δ11 P(Seat2|Seat1), δ12 P(Seat2|Szzz1)) ·P(Otired2|Seat2)

= max(0.21×0.1,0.21×0.8)×0.1

　　    = 0.0168

复制

S21 = eat

δ22 = max(P(Ocry1,Seat1)P(Seat2|Seat1)P(Otired2|Szzz2),P(Ocry1,Szzz1)P(Seat2|Szzz1)P(Otired2|Szzz2))

= max(δ11 P(Szzz2|Seat1), δ12 P(Szzz2|Szzz1)) ·P(Otired2|Szzz2)

= max(0.21×0.9,021×0.2)×0.1

= 0.0189

S22 = zzz

3.计算t=3时刻Ofind发生的概率：

δ31 = max(δ21P(Seat3|Seat2), δ22P(Seat3|Szzz2)) ·P(Ofind3|Seat3)

=max(0.0168×0.1, 0.0189×0.8)×0.2

=0.003024

S31 = eat

δ32 = max(δ21P(Szzz3|Seat2), δ22P(Szzz3|Szzz2)) ·P(Ofind3|Szzz3)

=max(0.0168×0.9, 0.0189×0.2)×0.2

=0.003024

S32 = zzz

4.回溯，每一步的最大概率：

max(δ11,δ12), max(δ21,δ22), max(δ31,δ32)

对应的状态：eat or zzz, zzz, eat or zzz