Machine LearningLesson 4:Bayesian LearningDr. JinxiuChen（陈锦秀）Department of Cognitive ScienceXiamen UniversityEmail: cjx@: 138060027692009-3-101
概述在机器学习过程中，如何通过一种自然和有效的方式来捕捉、表示和推理不确定性知识显得十分重要。贝叶斯方法就是一种非常有代表性的不确定性知识表示和推理方法，在机器学习领域具有十分重要的地位和作用。22009-3-10
概述贝叶斯推理提供了一种概率手段，基于如下的假定：待考察的量遵循某概率分布，且可根据这些概率及已观察到的数据进行推理，以作出最优的决策。贝叶斯推理为衡量多个假设的置信度提供了定量的方法贝叶斯推理为直接操作概率的学习算法提供了基础，也为其他算法的分析提供了理论框架32009-3-10
贝叶斯方法的主要特点使用概率表示所有形式的不确定性知识，学习和推理过程都用概率规则来实现，学习或推理结果表示为随机变量的概率分布；观察到的每个训练样本可以增量地降低或升高某假设的估计概率；先验知识可以与观察数据一起决定假设的最终概率；贝叶斯方法可允许对假设做出不确定性的预测；新的实例分类可由多个假设一起做出预测，用它们的概率来加权；可作为最优决策标准衡量其它方法的优劣。42009-3-10
贝叶斯学习在实际应用中，若能正确估计概率密度函数假设，就可使用少量样本数据，进行少量计算得到较满意的结果。这在样本难得的情形下特别有用，这也是贝叶斯方法优于其它方法之处。在贝叶斯方法中，由于全联合概率公式假设所有变量之间都具有条件依赖性，其计算复杂性十分巨大，而且为每个原子事件指定概率既不自然也相当困难，所以，在实际应用中一般都采用其简化形式。52009-3-10
朴素贝叶斯朴素贝叶斯（Naïve Bayes）分类器就是经常使用的一种简化方法。然而，由于朴素贝叶斯分类器假设所有变量之间都是条件独立的，该假设太过简单和武断，与实际情况并不相符。因此，如何在全联合概率计算公式和朴素贝叶斯分类器之间取得均衡，就成为贝叶斯方法的重要研究课题。62009-3-10
贝叶斯网络贝叶斯网络（Bayesian Network）就是一种很好的折衷方法。它充分利用了变量之间的独立性和条件独立性关系，从而大大减少了为定义全联合概率分布所需指定的概率数目。同时，它又避免了朴素贝叶斯分类器要求所有变量都是条件独立的不足。72009-3-10
OutlineTask1: 贝叶斯理论Task2:贝叶斯法则和概念学习的关系Task3: 朴素贝叶斯(Naïve Bayeslearner)和文本分类Task4:贝叶斯信念网，这是存在未知变量时被广泛使用的学习算法82009-3-10
贝叶斯理论机器学习的任务：在给定训练数据D时，确定假设空间H中的最佳假设。最佳假设：一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知识下的最可能假设贝叶斯理论提供了一种计算假设概率的方法，基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身92009-3-10
贝叶斯理论贝叶斯公式提供了从先验概率P(h)、P(D)和P(D|h)计算后验概率P(h|D)的方法P(D|h)P(h)P(h|D)=P(D)P(h|D)随着P(h)和P(D|h)的增长而增长，随着P(D)的增长而减少，即如果D独立于h时被观察到的可能性越大，那么D对h的支持度越小102009-3-10
贝叶斯理论用P(h)表示在没有训练数据前假设h拥有的初始概率。P(h)被称为h的先验概率。先验概率反映了关于h是一正确假设的机会的背景知识如果没有这一先验知识，可以简单地将每一候选假设赋予相同的先验概率类似地，P(D)表示训练数据D的先验概率，P(D|h)表示假设h成立时D的概率机器学习中，我们关心的是P(h|D)，即给定D时h的成立的概率，称为h的后验概率112009-3-10
假设选择1：极大后验假设（MAP）学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下P(D|h)P(h)h=argmaxP(h|D)=argmax=argmaxP(D|h)P(h)MAPh∈Hh∈HP(D)h∈H最后一步，去掉了P(D)，因为它是不依赖于h的常量122009-3-10
假设选择2：极大似然假设(ML)在某些情况下，可假定H中每个假设有相同的先验概率，即P(h)=P(h)，在这种情况ij下，可进一步简化成极大似然假设：h=argmaxP(D|h)MLh∈H132009-3-10
举例：一个医疗诊断问题有两个可选的假设：病人有癌症、病人无癌症可用数据来自化验结果：正+和负-有先验知识：在所有人口中，患病率是对确实有病的患者的化验准确率为98%，对确实无病的患者的化验准确率为97%总结如下P(cancer)=, P(¬cancer)=(+|cancer)=, P(-|cancer)=(+|¬cancer)=, P(-|¬cancer)=-3-10
举例：一个医疗诊断问题（2）问题：假定有一个新病人，化验结果为正，是否应将病人断定为有癌症？求后验概率P(cancer|+)和P(¬cancer|+)找到极大后验假设
P(+|cancer)P(cancer)=
P(+|¬cancer)P(¬cancer)=
h=¬cancerMAP确切的后验概率可将上面的结果归一化以使它们的和为1
P(canner|+)=
基本概率公式表乘法规则：P(A∧B)=P(A|B)P(B)=P(B|A)P(A)加法规则：P(A∨B)=P(A)+P(B)-P(A∧B)贝叶斯法则：P(h|D)=P(D|h)P(h)/P(D)全概率法则：如果事件A...A互斥，且满1nnnP(B)=P(B|A)P(A)P(A)=1足，∑ii∑ii=1i=1162009-3-10
贝叶斯法则和概念学习贝叶斯法则为计算给定训练数据下任一假设的后验概率提供了原则性方法，因此可以直接将其作为一个基本的学习方法：计算每个假设的概率，再输出其中概率最大的。将上面方法与第2讲介绍的概念学习算法比较，可以看到：在特定条件下，它们学习得到相同的假设，不同的是第2讲的方法不明确计算概率，而且效率更高。172009-3-10
Brute-Force贝叶斯概念学习概念学习问题：有限假设空间H定义在实例空间X上，任务是学习某个目标概念c。Brute-Force MAP学习算法P(D|h)P(h)P(h|D)=
对于H中每个假设h，计算后验概率P(D)h=argmaxP(h|D)MAP
输出有最高后验概率的假设h∈H上面算法需要较大计算量，因为它要计算每个假设的后验概率，对于大的假设空间显得不切实际，但是它提供了一个标准以判断其他概念学习算法的性能182009-3-10
朴素贝叶斯分类器实用性很高，在某些领域内其性能可与神经网络和决策树学习相当。When to use?
有足够的训练数据
根据给定的分类任务，描述实例的属性彼此条件独立Successful applications:
诊断
文本分类192009-3-10
朴素贝叶斯分类器（1）应用的学习任务：每个实例x可由属性值的合取描述，而目标函数f(x)从某有限集合V中取值贝叶斯方法的新实例分类目标是在给定描述实例的属性值<a,...,a>下，得到最可能的目标值v1nMAPv=argmaxP(v|a,...,a)MAPj1nvj使用贝叶斯公式变化上式P(a,...,a|v)P(v)1njjv=argmaxMAP∈P(a,...,avV)j1n=argmaxP(a,...,a|v)P(v)1njjv∈Vj202009-3-10
朴素贝叶斯分类器（2）基于训练数据估计两个数据项的值：
估计P(v)很容易：计算每个目标值v出现在训练数jj据中的频率
估计P(a,...a|v)遇到数据稀疏问题，除非有一个1nj非常大的训练数据集，否则无法获得可靠的估计朴素贝叶斯分类器引入一个简单的假定避免数据稀疏问题：在给定目标值时，属性值之间相互条件独立，即P(a,...,a|v)=P(a|v)1nj∏iji212009-3-10
朴素贝叶斯分类器（3）朴素贝叶斯分类器的定义：v=argmaxP(v)P(a|v)NBj∏ijv∈Vji从训练数据中估计不同P(a|v)项的数量比要估计ijP(a,...,a|v)项所需的量小得多1nj只要条件独立性得到满足，朴素贝叶斯分类v等于NBMAP分类，否则是近似朴素贝叶斯分类器与其他学习方法的一个区别：没有明确地搜索可能假设空间的过程（假设的形成不需要搜索，只是简单地计算训练样例中不同数据组合的出现频率）222009-3-10
朴素贝叶斯分类器举例：学习分类文本利用贝叶斯方法学习目标概念，然后用于文本自动过滤，比如
我感兴趣的电子新闻稿
讨论机器学习的万维网页文本分类的通用算法，它是目前所知的文本分类的最有效方法之一问题框架：实例空间X包含了所有的文本文档，给定某未知目标函数f(x)的一组训练样例，f(x)的值来自某有限集合V（作为示例，此处令V={like,dislike}）232009-3-10
举例：学习分类文本（2）应用朴素贝叶斯分类器的两个主要设计问题：
怎样将任意文档表示为属性值的形式
如何估计朴素贝叶斯分类器所需的概率表示文档的方法
给定一个文本文档，对每个单词的位置定义一个属性，该属性的值为在此位置上找到的英文单词假定我们共有1000个训练文档，其中700个分类为dislike，300个分类为like，现在要对下面的新文档进行分类：
This is an example document for the naive Bayesclassifier. This document contains only one paragraph, or two -3-10
举例：学习分类文本（3）计算式19v=argmaxP(v)P(a|v)NBj∏ijv∈{like,dislike}ji=1=argmaxP(v)P(a="this"|v)...P(a="sentences"|v)j1j19jv∈{like,dislike}j注意此处贝叶斯分类器隐含的独立性假设并不成立。通常，某个位置上出现某个单词的概率与前后位置上出现的单词是相关的虽然此处独立性假设不精确，但别无选择，否则要计算的概率项极为庞大。另外实践中，朴素贝叶斯学习器在许多文本分类问题中性能非常好252009-3-10
举例：学习分类文本（4）需要估计概率项P(v)和P(a=w|v)。前一项可基于每一类在iiki训练数据中的比例很容易得到，后一项含三个参数，出现数据稀疏问题再引入一个假定以减少需要估计的概率项的数量：假定单词w出现的概率独立于单词所在的位置，即kP(a=w|v)=P(w|v)ikikj作此假定的一个主要优点在于：使可用于估计每个所需概率的样例数增加了，因此增加了估计的可靠程度采纳m-估计方法，即有统一的先验概率并且m等于词汇表的大小，因此n+mpn+1kkP(w|v)==kjn+mn+|Vocabulary|262009-3-10
用于学习和分类文本的朴素贝叶斯算法Learn_Naive_Bayes_Text( Examples, V )Examples为一组文本文档以及它们的目标值。V为所有可能目标值的集合。此函数作用是学习概率项P(w|v)和P(v)。kjj
收集Examples中所有的单词、标点符号以及其他记号Vocabulary←在Examples中任意文本文档中出现的所有单词及记号的集合
计算所需要的概率项P(v)和P(w|v)jkj对V中每个目标值vj
docs←Examples中目标值为v的文档子集jj
P(v)←|docs| / |Examples|jj
Text←将docs中所有成员连接起来建立的单个文档jj
n←在Text中不同单词位置的总数j
对Vocabulary中每个单词wkn←单词w出现在Text中的次数kkjP(w|v)←(n+1) / (n+|Vocabulary|)kjk272009-3-10
用于学习和分类文本的朴素贝叶斯算法Classify_Naive_Bayes_Text( Doc )对文档Doc返回其估计的目标值，a代表在iDoc中的第i个位置上出现的单词
positions←在Doc中的所有单词位置，它包含能在Vocabulary中找到的记号
返回v，NBv=argmaxP(v)P(a|v)NBj∏ijv∈Vji∈positions282009-3-10
实验结果Joachims将此算法用于新闻组文章的分类
每一篇文章的分类是该文章所属的新闻组名称
20个新闻组，每个新闻组有1000篇文章，共2万个文档
2/3作为训练样例，1/3进行性能测量
词汇表不包含最常用词（比如the、of）和罕见词（数据集中出现次数少于3）Lang用此算法学习目标概念“我感兴趣的新闻组文章”
NewsWeeder系统，让用户阅读新闻组文章并为其评分，然后使用这些评分的文章作为训练样例，来预测后续文章哪些是用户感兴趣的
每天向用户展示前10%的自动评分文章，它建立的文章序列中包含的用户感兴趣的文章比通常高3~4倍292009-3-10
贝叶斯网络的由来全联合概率计算复杂性十分巨大朴素贝叶斯太过简单现实需要一种自然、有效的方式来捕捉和推理——不确定性知识变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目302009-3-10
贝叶斯网络的定义是一个有向无环图(DAG)随机变量集组成网络节点，变量可离散或连续一个连接节点对的有向边或箭头集合每节点X都有一个条件概率分布表(CPT)：iP(X|Parents(X))，量化其父节点对该节ii点的影响312009-3-10
独立和条件独立说明CavityWeatherCatchToothacheWeather和其它3个变量相互独立给定Cavity后，Toothache和Catch条件独立322009-3-10
贝叶斯网络示例一个表示防盗报警器（Alarm）与盗贼闯入（Burglary）、地震（Earthquake）、John来电告知（JohnCalls）、Mary来电告知（MaryCalls）之间的条件依赖关系的贝叶斯网络，如下图所示。332009-3-10
贝叶斯网络示例(2)P(E) P(B) EP(A) t (J) AP(M) JohnCallsMaryCallst 0 .90t 0 .-3-10
贝叶斯网络示例(3)该贝叶斯网络的拓扑结构表明：盗贼闯入和地震直接影响到警报的概率，但是，John或者Mary是否打电话只取决于报警。该网络隐式地假设：John和Mary不直接感知盗贼闯入，也不会注意到轻微地震，并且他们在打电话前并不会交换意见，也就是说，在给定警报Alarm后，JohnCalls和MaryCalls是条件独立的。352009-3-10
贝叶斯网络示例(4)图中每个节点都有一个条件概率表CPT（Conditional probability table）。CPT中的每一行包含了每个节点对于一个条件事件（Conditioning case，即所有父节点的取值的一个可能组合）的条件概率，且每一行的概率总和必须为1。对于布尔变量，一旦知道了它为真的概率为p，那么它为假的概率就是1-p，因此，在图中经常省略第二个概率值。特别地，对于没有父节点的节点而言，其概率分布表只有一行，表示该变量可能取值的先验概率。362009-3-10
贝叶斯网络的语义贝叶斯网络的两种理解(含义)对联合概率分布的表示对条件依赖性语句集合的编码贝叶斯网络的语义P(x,..., x) = P(x|parent(x)) ... P(x|parent(x))1n11nn其中P(x,..., x)表示对每个变量赋予一个1n特定值的情况下的联合概率，它是的简化表示形式。372009-3-10
贝叶斯网络的语义公式计算示例试计算：报警器响了，但既没有盗贼闯入，也没有发生地震，同时John和Mary都给你打电话的概率。解：P(j,m,a,~b,~e) = P(j|a)P(m|a)P(a|~b,~e) P(~b) P(~e)= = = %382009-3-10
贝叶斯网络的特性作为对域的一种完备而无冗余的表示，贝叶斯网络比全联合概率分布紧凑得多BN的紧凑性是局部结构化(Locally structured, 也称稀疏, Sparse)系统一个非常普遍特性的实例BN中每个节点只与数量有限的其它节点发生直接的相互作用假设节点数n=30, 每节点有5个父节点，则5BN需30x2=960个数据，而全联合概率分布30需要2= 10亿个！392009-3-10
贝叶斯网络的构造原则首先，添加“根本原因”节点(无父节点的节点)然后，加入受它们直接影响的变量节点依次类推，直到叶节点，即对其它变量没有直接因果影响的节点两节点间的有向边的取舍原则：更高精度概率的重要性与指定额外信息的代价的折衷“因果模型”比“诊断模型”需要更少的数据，且这些数据也更容易得到402009-3-10
贝叶斯网络中的条件独立关系给定父节点，一个节点与它的非后代节点是条件独立的给定一个节点的父节点、子节点以及子节点的父节点——马尔可夫覆盖(Markov blanket)，这个节点和网络中的所有其它节点是条件独立的412009-3-10
UU1【说明】：m给定节点X的父节点U... 1XU，节点X与Z1jZmnj它的非后代节点（即Z）是ij条件独立的。YY1n422009-3-10
UU1【说明】：m给定马尔可夫覆盖（两圆圈XZ之间的区1jZnj域），节点X和网络中所有其它节点是条YY1n件独立的。432009-3-10
条件概率表CPT的有效表达(无连续变量)已知：P(~fever | cold, ~flu, ~malaria) = (~fever | ~cold, flu, ~malaria) = (~fever | ~cold, ~flu, malaria) = ，可利用“噪声或”（Noisy-OR）关系得到下表：Cold Flu MalariaP(Fever)P(~Fever)F F F T T = X F F = X T = X T = X X -3-10
含连续变量的贝叶斯网络－Hybrid BNP(S) P(H) SubsidyxHarvest高斯分布S HP(C) Costt h高斯分布f h高斯分布CP(B) c S 型函数Buys离散随机变量：Subsidy, Buys; 连续随机变量：Harvest, -3-10
含连续变量的贝叶斯网络－Hybrid BN上图所示的是一个同时包含离散随机变量（Subsidy，Buys）和连续随机变量（Harvest，Cost）的混合贝叶斯网络。图中4个节点的CPT表达方法分别如下
Subsidy是离散变量，且无父节点，故其概率可根据实际情况指定为x
Harvest是连续变量，具有无限个可能的取值，故不可能显式地为每个取值指定条件概率。462009-3-10
含连续变量的贝叶斯网络－Hybrid BN
HarvestCPT的表示有如下两种方式通过离散化，将所有可能的取值划分到固定的区间集合中。但该方法有时会导致很大的精度损失和巨大的CPT；定义标准的概率密度函数族，通过有限个参数进行指定。例如，高斯（即正态）22分布N(µ, σ)以均值µ和方差σ为参数。472009-3-10
含连续变量的贝叶斯网络－Hybrid BNCost是连续变量，其父节点既有离散变量（Subsidy）也有连续变量（Harvest）。
对于离散父节点Subsidy可通过直接枚举方式来处理，即分别指定P(Cost| Harvest, Subsidy)和P(Cost| Harvest, ┐Subsidy)。
对于Harvest，可将Cost的连续取值c指定为Harvest的连续取值h的线性高斯分布，即子节点Cost服从均值µ随父节点Harvest的值线性变化，而标准差σ保持不变的高斯分布。对于Subsidy和¬Subsidy，需要分别定义2个参数不同的线性高斯分布：2P(c| h, subsidy) = N(ah+ b, σ)(c)ttt1/2–1/2{[c-(ah + b)]/σt]}= 1/ (σ2π) e ttt2P(c| h, ~subsidy) = N(ah+ b, σ)(c)fff1/2–1/2{[c-(ah + b)]/σf]}= 1/ (σ2π) e fff482009-3-10
含连续变量的贝叶斯网络－Hybrid BNBuys是离散变量，而其父节点Cost则是连续变量。比较合理的分布情况是：价格Cost较低时顾客会购买(Buys=True)，而Cost较高时就很少买(甚至不购买，即Buys=False)，并且Buys的概率在某个中间区域平滑变化。对于这个例子，可采用S形函数(Sigmoidfunction，即“软”的阈值函数)来生成Buys随Cost的值变化的条件概率分布，即P(buys| Cost = c) = 1 / {1 + exp[-2(-u+μ)/ σ]}492009-3-10
小结概率学习方法利用关于不同假设的先验概率，以及在给定假设时观察到不同数据的概率的知识贝叶斯方法提供了概率学习方法的基础，基于这些先验和数据观察假定，赋予每个假设一个后验概率贝叶斯方法确定的极大后验概率假设是最可能成为最优假设的假设贝叶斯最优分类器将所有假设的预测结合起来，并用后验概率加权，以计算对新实例的最可能分类朴素贝叶斯分类器增加了简化假定：属性值在给定实例的分类时条件独立贝叶斯信念网能够表示属性的子集上的一组条件独立性假定502009-3-10
Any Questions?cs_xmu@：ml2009512009-3-10
