アカリの部屋

概率图模型

问题提出

首先看几个经典的问题:

1.当你去做体检,医生说,我们的设备认为你有99%的概率得了这个病,而这个病的真实发病率是1/10000,那么,你认为你得这个病的概率是多少?
2.著名的Monty Hall问题,在一场游戏中,有三道门,有且只有一道门后有大奖,你要随机选一个门,主持人会从另外两道门中任意选一个没中奖的门打开给你看,之后你有一次机会选择另一扇门,那么从数学上讲,你换不换门?(当然,可以用蒙特卡罗模拟,用程序随机玩一百万次看结果,也可以排列组合列出所有情况,但是要求用算的)

贝叶斯公式

为了解决这个问题需要条件概率公式:

$ P(A|B) = \frac{P(AB)}{P(B)} $

经过简单推导得到乘法形式:

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

对右边两项变形,有:

$ P(A|B) = \frac{P(B|A)P(A)}{P(B)} $

再看左边两项,因为 $ P(AB) = P(B|A)P(A) $ ,那么如果想求 $ P(B) $ ,实质上就是把联合分布中 $ P(A) $ 消掉,那么就需要把A的所有情况枚举求和,这等同于二元函数对其中一元做积分来消掉,也就是全概率公式:

$ P(B) = \sum{_A} P(A)P(B|A) $

那么我们就可以把全概率公式套到上面的分母里,就有了贝叶斯公式

$ P(A|B) = \frac{P(B|A)P(A)}{\sum{_A} P(A)P(B|A)} $

于是,当我们知道了联合分布之后,就能拿到任意的概率分布和条件概率了!这就是概率图模型的终极目标。

解题

问题1,假设D表示得了这个病,T表示验出来了,那么

$ P(T=1|D=1) = 0.99 $

且没得病也没被检验出来的概率也是99%,

$ P(T=0|D=0) = 0.99 $

而又知道一个先验概率

$ P(D=1) = 0.0001 $

现在要求的是被检验出来且得了这个病的概率 $ $ P(D=1|T=1) $,套用贝叶斯公式:

$ P(D=1|T=1) = \frac{P(T=1|D=1)P(D=1)}{P(T=1|D=0)P(D-0)+P(T=1|D=1)P(D=1)} = 0.0098 $

也就是说,医生告诉你有病,你只有0.98%的概率真得病。

至于需不需要担心或者治疗,则要通过损失回报模型和这个概率求期望,来做行为决策。

问题2,假设每扇门的先验中奖概率都是均等的:

$ P(H=1)=P(H=2)=P(H=3)=1/3 $

假设我们选了1号门,那么主持人会在2和3之间挑一个,假设有奖的门是H,被开的门是D,有主持人开们山门的所有概率:

$ P(D=2|H=1)=1/2, P(D=3|H=1)=1/2 $
$ P(D=2|H=2)=0, P(D=3|H=2)=1 $
$ P(D=2|H=3)=1, P(D=3|H=3)=0 $

做完了这两部翻译,就要解决要不要换的问题了,根据贝叶斯公式,能算出假设主持人开了3号门D后,大奖在每扇门H后的概率:

$ P(H=1|D=3) = 1/3 $ ,$ P(H=2|D=3) = 2/3 $ ,$ P(H=3|D=3) = 0 $

也就是说,如果不换,赢的概率是33%,换的话是66%,所以答案就是换。

直观上解释,主持人开的门的判断是基于参与者判断的,也就是为参与者增加了后验的知识,是有助于参与者下一步判断。

概率图模型

假设我们有三个独立事件ABC,当我们想知道三个事件的联合分布 $ P(ABC) $ 的时候,根据贝叶斯公式我们就能回答很多条件概率问题。

然而,果我们根本不知道这三个事件之间的关系的话(没有任何先验知识的话),那么,假设每个事件都是零一型的,那么每个事件光零一组合就有8种,三个事件各自0和1的概率就要存三个表,才能得到联合分布。

为了得到几个数来表示联合分布,需要的数据量是呈指数级增加的,这个计算量和存储量就根本没法玩了。这就是图模型要解决的根本问题——维度灾难,退一步说,如果有一点建模者的先验知识,能不能把指数级别的复杂度压到多项式级别来得到全概率呢?

假设有一个地震模型:当地震(E)时和遭贼(B)时,警报都会响(A),当地震时,收音机也会响(R),而警报响时,我要电话报警(C)。

这时就可以定义出一个有向无环关系图:

logo

概率图模型的意图是,当我们可以用一个图的关系表示出变量之间的依赖结构时,联合分布就可以写成一系列小的概率分布的乘积,每一个小的概率分布都是 $ P(节点|父节点) $。比如:B和E都没有父节点,则两个概率分别是 $ P(B) $ 和 $ P(E) $,A有父节点,则是 $ P(A|BE) $,同理还有 $ P(R|E) $ 和 $ P(C|A) $。

所以这张图的公式是:

$ P(B,E,A,R,C) = P(B)P(E)P(A|BE)P(R|E)P(C|A) $

假设每个事件都是零一型的,这样一来,就根本不需要2的5次方个概率来学得这个公式了,因为这里只有5个变量做乘积,所以只需要5个概率分布就能达到期望的效果了。

在这个视角下,如果需要回答 $ P(C) $ 的概率究竟是多少?最笨的方法要用全概率公式“积掉”所有其他变量,这又是一个很蛋疼的N层for循环查表,这又回到了指数级别的复杂度,这里可以用消元法(variable elimination)来消除无关变量。

朴素贝叶斯(Naive Bayes)

朴素贝叶斯分类器是一个在70年代就有的模型,实际就是一种简化的概率图模型,输入是向量 $ X(x{_1} ,x{_2}…) $,而这些属性 $ x{_i} $ 是相互独立的,输出是结果 $ Y $,显然机器学习想知道的就是 $ P(Y|X) $。

那么根据概率图模型就有:

$ P(XY) = P(X)P(X{_1}|Y)P(X{_2}|Y)…P(X{_n}|Y) $

这样,当看到一个新样本时,就有

$ P(Y|X) = \frac{p(XY)}{P(x)} $

这里的分母 $ P(x) $ 训练集会有,而 $ P(XY) $ 可以每项查表得到,从而完成分类。

垃圾邮件分类器

假设有一个Email,表示为 $ X $,它是不是垃圾邮件表示为 $ Y $。

Email是个文本,将其表示为One Hot的形式,即把每个词作为一个index编号,假设“滚”是100号,那么如果这篇文章里出现了这个词,则这个向量的第100号位置为1,否则为0,这样就得到了一个长度很长的一维向量。

那么,当看到“滚”这个 $ x $ 的时候,机器学习要干的事情是求 $ P(Y=1|X) $,也就是当看到“滚”的时候,是垃圾邮件的概率。

朴素贝叶斯有个关键假设,就是认为这些词是彼此独立的,两个词之间没有关系,所以它Naive,那么就有

$ P(Y=1|X) = \frac{P(X|Y=1)P(Y)}{P(X)} $

左上角的 $ P(X|Y=1) $ 的求法是,因为我知道 $ P(XY) = P(Y)P(x{_1}|Y)P(x{_2}|Y)… $ 是连乘出来的,那么只要看训练集的垃圾邮件当中每个词的出现概率是多少算一遍,有了联合分布就能算出这个条件分布了。右上角的 $ P(Y) $ 直接看训练集当中垃圾邮件的比率,是个先验知识。分母 $ P(X) $ 不用管,因为最终在判定是不是垃圾邮件的时候我们要比的是 $ P(Y=1|x{_0}) $ 和 $ P(Y=0|x{_0}) $ 哪个大,两边分母一样直接消了。

但是任何一个单词的 $ P(x{_i}|Y) $ 都是要统计出来的,如果整个向量里存在一个没有学习过的词的话,那么会导致结果为0,分母也为0,这样一来上面连乘公式就会永远为0,解决方法是将所有单词出现的次数都+1,当数据量很大时,这个+1并不影响整个结果,这个方法叫拉普拉斯平滑

隐马尔可夫模型(HMM)

在朴素贝叶斯当中有个每个变量都是独立同分布的假设,然而在时间序列这样的数据当中,某个时刻的数据是和之前的时刻是有关系的,那么用SVM之类的无记忆性的方法来强行计算从根上就是有问题的。

对于一个X->Y简单概率图,有 $ P(XY) = P(X)P(Y|X) $ ,这里管 $ X $ 叫隐变量,是不知道的潜在因素,而 $ Y $ 是观测值。如 $ X $ 是心情 $ Y $ 是表情,那么通过外在表现就可以推断出隐变量是什么的概率,如 $ P(X=伤心|Y=哭) $ 的概率值就比较大,同理,可以从股票价格来推断是牛市还是熊市,这就是隐马尔可夫模型或者推断系统想干的事情。

在这个概率图中,$ P(X) $ 是通过训练集历史数据总结的,可以查表得到,而 $ P(Y|X) $ 则是个二维表,当 $ X $ 取某个值的时候,能对应每种 $ Y $ 的概率,和为1,比如,伤心的时候哭、伤心的时候笑、开心的时候哭、开心的时候笑,四个概率的和为1。然而机器学习要得到的是 $ P(X|Y) $,这时候就要祭出贝叶斯公式了:$ P(X|Y) = \frac{P(Y|X)P(X)}{P(Y)} $。

问题在于,隐变量会随着时间从 $ x1 $ 转化为 $ x2 $、$ x3 $,这样假设隐变量有3个状态,那么概率图就有6个变量了。

logo

那么又能得到一个联合分布:
$ P(X1X2X3Y1Y2Y3) = P(X1)P(Y1|X1) P(X2|X1)P(Y2|X2) P(X3|X2)P(Y3|X3)) $

其中,有些项只和 $ X $ 有关,如 $ P(X1) P(X2|X1) P(X3|X2) $,这些项叫做状态转移,即隐变量一个状态转化为另一个状态的概率,另一类是 $ P(Y1|X1) P(Y2|X2) P(Y3|X3) $,两个下标都相等,叫输出概率,即在某个时刻下从隐变量转化为具体表现的概率。而隐马尔可夫模型的一个关键假设就是每一次状态转移的概率都是相等的,即可以用一个固定的转移矩阵(又是一个查表)来表示概率,比如,A转A、A转B、B转A、B转B各自的概率。

隐马尔可夫模型的另一个假设就是,隐变量之间只会从状态1转化为状态2,而不会从2到3且从1到3,这种情况可以通过对隐变量加隐变量,即深层的隐马尔可夫,但是这计算很复杂。

隐马尔可夫模型最常见的用法是,当观测到 $ Y1,Y2, Y3 $ 的具体表现时,想求得隐变量的概率 $ P(X3=?|Y1,Y2,Y3) $ 是多少,这又回到了前面的求解概率图的问题,这里就不赘述了。

要注意的是,HMM是平方级复杂度的算法,而RNN(循环神经网络)的效果更好。

语音识别问题

语音识别实际上是想知道当听到一个声音它对应是某个单词的概率 $ P(words|sound) $,而想知道词对应的声音的概率 $ P(sound|words) $ 是容易的,大不了都读一遍暴力查表,而知道这个单词本身的概率 $ P(words) $ 则是更简单的词频统计问题,所以:

$ P(words|sound) = P(sound|words)P(words) $

而字是存在于句子当中的,即听到了“你好吗”三个字的频率的时候,需要用隐马尔可夫推测出第三个字是“吗”的概率是多少。

循环神经网络(RNN)

RNN的做法是,每个时刻都有一个输入比如“你”向量,都会乘以一个大矩阵,得到新的向量,即隐层,也就是上面的隐变量X,而输出的“You”是要往前看几个时间点的X才能共同决定的,要学的就是这些大矩阵。而HMM只往前看一个时间点。