概率图模型是用图来表示变量概率依赖关系的理论, 结合概率论与图论的知识, 利用图来表示与模型有关的变量的联合概率分布. 由图灵奖获得者 Pearl 开发出来.
如果用一个词来形容概率图模型 (Probabilistic Graphical Model) 的话, 那就是 "优雅". 对于一个实际问题, 我们希望能够挖掘隐含在数据中的知识. 概率图模型构建了这样一幅图, 用观测结点表示观测到的数据, 用隐含结点表示潜在的知识, 用边来描述知识与数据的相互关系, 最后基于这样的关系图获得一个概率分布 , 非常 "优雅" 地解决了问题.
概率图中的节点分为隐含节点和观测节点, 边分为有向边和无向边. 从概率论的角度, 节点对应于随机变量, 边对应于随机变量的依赖或相关关系, 其中 有向边表示单向的依赖, 无向边表示相互依赖关系 .
概率图模型分为 ** 贝叶斯网络 (Bayesian Network) 和马尔可夫网络(Markov Network)** 两大类. 贝叶斯网络可以用一个有向图结构表示, 马尔可夫网络可以表 示成一个无向图的网络结构. 更详细地说, 概率图模型包括了朴素贝叶斯模型, 最大熵模型, 隐马尔可夫模型, 条件随机场, 主题模型等, 在机器学习的诸多场景中都有着广泛的应用.
2. 细数贝叶斯网络
2.1 频率派观点
长久以来, 人们对一件事情发生或不发生的概率, 只有固定的 0 和 1, 即要幺发生, 要幺不发生, 从来不会去考虑某件事情发生的概率有多大, 不发生的概率又是多大. 而且概率虽然未知, 但最起码是一个确定的值. 比如如果问那时的人们一个问题:"有一个袋子, 里面装着若干个白球和黑球, 请问从袋子中取得白球的概率是多少?" 他们会想都不用想, 会立马告诉你, 取出白球的概率就是 1/2, 要幺取到白球, 要幺取不到白球, 即θ只能有一个值, 而且不论你取了多少次, 取得白球的 概率θ始终都是 1/2 , 即不随观察结果 X 的变化而变化.
这种 频率派 的观点长期统治着人们的观念, 直到后来一个名叫 Thomas Bayes 的人物出现.
2.2 贝叶斯学派
托马斯. 贝叶斯 Thomas Bayes(1702-1763)在世时, 并不为当时的人们所熟知, 很少发表论文或出版着作, 与当时学术界的人沟通交流也很少, 用现在的话来说, 贝叶斯就是活生生一民间学术 "屌丝", 可这个 "屌丝" 最终发表了一篇名为 "An essay towards solving a problem in the doctrine of chances", 翻译过来则是: 机遇理论中一个问题的解. 你可能觉得我要说: 这篇论文的发表随机产生轰动效应, 从而奠定贝叶斯在学术史上的地位.
这篇论文可以用上面的例子来说明,"有一个袋子, 里面装着若干个白球和黑球, 请问从袋子中取得白球的概率θ是多少?" 贝叶斯认为取得白球的概率是个不确定的值, 因为其中含有机遇的成分. 比如, 一个朋友创业, 你明明知道创业的结果就两种, 即要幺成功要幺失败, 但你依然会忍不住去估计他创业成功的几率有多大? 你如果对他为人比较了解, 而且有方法, 思路清晰, 有毅力, 且能团结周围的人, 你会不由自主的估计他创业成功的几率可能在 80% 以上. 这种不同于最开始的 "非黑即白, 非 0 即 1" 的思考方式, 便是 贝叶斯式的思考方式.
先简单总结下频率派与贝叶斯派各自不同的思考方式:
频率派把需要推断的参数θ看做是固定的未知常数, 即概率虽然是未知的, 但最起码是确定的一个值, 同时, 样本 X 是随机的, 所以频率派重点研究样本空间, 大部分的概率计算都是针对样本 X 的分布;
而贝叶斯派的观点则截然相反, 他们认为参数是随机变量, 而样本 X 是固定的, 由于样本是固定的, 所以他们重点研究的是参数的分布.
贝叶斯派既然把看做是一个随机变量, 所以要计算的分布, 便得事先知道的无条件分布, 即在有样本之前(或观察到 X 之前), 有着怎样的分布呢?
比如往台球桌上扔一个球, 这个球落会落在何处呢? 如果是不偏不倚的把球抛出去, 那幺此球落在台球桌上的任一位置都有着相同的机会, 即球落在台球桌上某一位置的概率服从均匀分布. 这种在实验之前定下的属于基本前提性质的分布称为 先验分布, 或着无条件分布 .
其中, 先验信息一般来源于经验跟历史资料. 比如林丹跟某选手对决, 解说一般会根据林丹历次比赛的成绩对此次比赛的胜负做个大致的判断. 再比如, 某工厂每天都要对产品进行质检, 以评估产品的不合格率θ, 经过一段时间后便会积累大量的历史资料, 这些历史资料便是先验知识, 有了这些先验知识, 便在决定对一个产品是否需要每天质检时便有了依据, 如果以往的历史资料显示, 某产品的不合格率只有 0.01%, 便可视为信得过产品或免检产品, 只每月抽检一两次, 从而省去大量的人力物力.
而 后验分布 π(θ|X)一般也认为是在给定样本 X 的情况下的θ条件分布, 而使π(θ|X)达到最大的值θMD 称为 最大后验估计 , 类似于经典统计学中的 极大似然估计 .
综合起来看, 则好比是人类刚开始时对大自然只有少得可怜的先验知识, 但随着不断观察, 实验获得更多的样本, 结果, 使得人们对自然界的规律摸得越来越透彻. 所以, 贝叶斯方法既符合人们日常生活的思考方式, 也符合人们认识自然的规律, 经过不断的发展, 最终占据统计学领域的半壁江山, 与经典统计学分庭抗礼.
2.3 贝叶斯定理
条件概率 (又称后验概率) 就是事件 A 在另外一个事件 B 已经发生条件下的发生概率. 条件概率表示为 P(A|B), 读作 "在 B 条件下 A 的概率".
比如上图, 在同一个样本空间Ω中的事件或者子集 A 与 B, 如果随机从Ω中选出的一个元素属于 B, 那幺这个随机选择的元素还属于 A 的概率就定义为在 B 的前提下 A 的条件概率:
联合概率:
边缘概率 (先验概率):P(A) 或者 P(B)
2.4 贝叶斯网络
贝叶斯网络(Bayesian network), 又称信念网络(Belief Network), 或有向无环图模型(directed acyclic graphical model), 是一种概率图模型, 于 1985 年由 Judea Pearl 首先提出. 它是一种模拟人类推理过程中因果关系的不确定性处理模型, 其网络拓朴结构是一个有向无环图(DAG).
贝叶斯网络的有向无环图中的节点表示随机变量
它们可以是可观察到的变量, 或隐变量, 未知参数等. 认为有因果关系 (或非条件独立) 的变量或命题则用箭头来连接. 若两个节点间以一个单箭头连接在一起, 表示其中一个节点是 "因(parents)", 另一个是 "果(children)", 两节点就会产生一个条件概率值.
例如, 假设节点 E 直接影响到节点 H, 即 E→H, 则用从 E 指向 H 的箭头建立结点 E 到结点 H 的有向弧 (E,H), 权值(即连接强度) 用条件概率 P(H|E)来表示, 如下图所示:
简言之, 把某个研究系统中涉及的随机变量, 根据是否条件独立绘制在一个有向图中, 就形成了贝叶斯网络. 其主要用来描述随机变量之间的条件依赖, 用圈表示随机变量(random variables), 用箭头表示条件依赖(conditional dependencies).
此外, 对于任意的随机变量, 其联合概率可由各自的局部条件概率分布相乘而得出:
2.4.1 贝叶斯网络的结构形式
1. head-to-head
依上图, 所以有: P(a,b,c) = P(a)*P(b)*P(c|a,b)成立, 即在 c 未知的条件下, a,b 被阻断(blocked), 是独立的, 称之为 head-to-head 条件独立.
2. tail-to-tail
考虑 c 未知, 跟 c 已知这两种情况:
在 c 未知的时候, 有: P(a,b,c)=P(c)*P(a|c)*P(b|c), 此时, 没法得出 P(a,b) = P(a)P(b), 即 c 未知时, a,b 不独立.
在 c 已知的时候, 有: P(a,b|c)=P(a,b,c)/P(c), 然后将 P(a,b,c)=P(c)*P(a|c)*P(b|c)带入式子中, 得到: P(a,b|c)=P(a,b,c)/P(c) = P(c)*P(a|c)*P(b|c) / P(c) = P(a|c)*P(b|c), 即 c 已知时, a,b 独立.
3. head-to-tail
还是分 c 未知跟 c 已知这两种情况:
c 未知时, 有: P(a,b,c)=P(a)*P(c|a)*P(b|c), 但无法推出 P(a,b) = P(a)P(b), 即 c 未知时, a,b 不独立.
c 已知时, 有: P(a,b|c)=P(a,b,c)/P(c), 且根据 P(a,c) = P(a)*P(c|a) = P(c)*P(a|c), 可化简得到:
- =$$P(a,b,c)/P(c)$$
- =$$P(a)*P(c|a)*P(b|c) / P(c)$$
- =$$P(a,c)*P(b|c)/P(c)$$
- =$$P(a|c)*P(b|c)$$
所以, 在 c 给定的条件下, a,b 被阻断(blocked), 是独立的, 称之为 head-to-tail 条件独立.
这个 head-to-tail 其实就是一个链式网络, 如下图所示:
根据之前对 head-to-tail 的讲解, 我们已经知道, 在 xi 给定的条件下, xi+1 的分布和 x1,x2...xi-1 条件独立. 意味着啥呢? 意味着: xi+1 的分布状态只和 xi 有关, 和其他变量条件独立. 通俗点说, 当前状态只跟上一状态有关, 跟上上或上上之前的状态无关. 这种顺次演变的随机过程, 就叫做 马尔科夫链 (Markov chain). 对于马尔科夫链我们下一节再细讲.
2.4.2 因子图
wikipedia 上是这样定义因子图的: 将一个具有多变量的全局函数因子分解, 得到几个局部函数的乘积, 以此为基础得到的一个双向图叫做因子图(Factor Graph).
通俗来讲, 所谓因子图就是对函数进行因子分解得到的 一种概率图 . 一般内含两种节点: 变量节点和函数节点. 我们知道, 一个全局函数通过因式分解能够分解为多个局部函数的乘积, 这些局部函数和对应的变量关系就体现在因子图上.
举个例子, 现在有一个全局函数, 其因式分解方程为:
其中 fA,fB,fC,fD,fE 为各函数, 表示变量之间的关系, 可以是条件概率也可以是其他关系. 其对应的因子图为:
在概率图中, 求某个变量的边缘分布是常见的问题. 这问题有很多求解方法, 其中之一就是把贝叶斯网络或马尔科夫随机场转换成因子图, 然后用 sum-product 算法求解. 换言之, 基于因子图可以用 sum-product 算法 高效的求各个变量的边缘分布.
详细的 sum-product 算法过程, 请查看博文: 从贝叶斯方法谈到贝叶斯网络
2.5 朴素贝叶斯
朴素贝叶斯 (Naive Bayesian) 是经典的机器学习算法之一, 也是为数不多的基于概率论的分类算法. 朴素贝叶斯原理简单, 也很容易实现, 多用于文本分类, 比如垃圾邮件过滤.** 朴素贝叶斯可以看做是贝叶斯网络的特殊情况: 即该网络中无边, 各个节点都是独立的. **
朴素贝叶斯朴素在哪里呢? -- 两个假设 :
一个特征出现的概率与其他特征 (条件) 独立;
每个特征同等重要.
贝叶斯公式如下:
下面以一个例子来解释朴素贝叶斯, 给定数据如下:
现在给我们的问题是, 如果一对男女朋友, 男生想女生求婚, 男生的四个特点分别是不帅, 性格不好, 身高矮, 不上进, 请你判断一下女生是嫁还是不嫁?
这是一个典型的分类问题, 转为数学问题就是比较 p(嫁 |(不帅, 性格不好, 身高矮, 不上进))与 p(不嫁 |(不帅, 性格不好, 身高矮, 不上进))的概率, 谁的概率大, 我就能给出嫁或者不嫁的答案! 这里我们联系到朴素贝叶斯公式:
我们需要求 p(嫁 |(不帅, 性格不好, 身高矮, 不上进), 这是我们不知道的, 但是通过朴素贝叶斯公式可以转化为好求的三个量, 这三个变量都能通过统计的方法求得.
等等, 为什幺这个成立呢? 学过概率论的同学可能有感觉了, 这个等式成立的条件需要特征之间相互独立吧! 对的! 这也就是为什幺朴素贝叶斯分类有朴素一词的来源, 朴素贝叶斯算法是假设各个特征之间相互独立, 那幺这个等式就成立了!
但是为什幺需要假设特征之间相互独立呢?
我们这幺想, 假如没有这个假设, 那幺我们对右边这些概率的估计其实是不可做的, 这幺说, 我们这个例子有 4 个特征, 其中帅包括{帅, 不帅}, 性格包括{不好, 好, 爆好}, 身高包括{高, 矮, 中}, 上进包括{不上进, 上进}, 那幺四个特征的联合概率分布总共是 4 维空间, 总个数为 2 3 3*2=36 个.
36 个, 计算机扫描统计还可以, 但是现实生活中, 往往有非常多的特征, 每一个特征的取值也是非常之多, 那幺通过统计来估计后面概率的值, 变得几乎不可做, 这也是为什幺需要假设特征之间独立的原因.
假如我们没有假设特征之间相互独立, 那幺我们统计的时候, 就需要在整个特征空间中去找, 比如统计 p(不帅, 性格不好, 身高矮, 不上进 | 嫁), 我们就需要在嫁的条件下, 去找四种特征全满足分别是不帅, 性格不好, 身高矮, 不上进的人的个数, 这样的话, 由于数据的稀疏性, 很容易统计到 0 的情况. 这样是不合适的.
根据上面俩个原因, 朴素贝叶斯法对条件概率分布做了条件独立性的假设, 由于这是一个较强的假设, 朴素贝叶斯也由此得名! 这一假设使得朴素贝叶斯法变得简单, 但有时会牺牲一定的分类准确率.
朴素贝叶斯优点:
算法逻辑简单, 易于实现(算法思路很简单, 只要使用贝叶斯公式转化即可!)
分类过程中时空开销小(假设特征相互独立, 只会涉及到二维存储)
朴素贝叶斯缺点:
理论上, 朴素贝叶斯模型与其他分类方法相比具有最小的误差率. 但是实际上并非总是如此, 这是因为朴素贝叶斯模型假设属性之间相互独立, 这个假设在实际应用中往往是不成立的, 在属性个数比较多或者属性之间相关性较大时, 分类效果不好.
朴素贝叶斯模型 (Naive Bayesian Model) 的 ** 朴素 (Naive) 的含义是 "很简单很天真"** 地假设样本特征彼此独立. 这个假设现实中基本上不存在, 但特征相关性很小的实际情况还是很多的, 所以这个模型仍然能够工作得很好.
来源: http://www.tuicool.com/articles/iMbERnF