第06章_贝叶斯网络课件.ppt

2023/1/91贝叶斯网络贝叶斯网络概概 率率 推推 理理2023/1/92内容提要内容提要1.1 1.1 概述概述 1.2 1.2 贝叶斯概率贝叶斯概率基础基础1.3 1.3 贝叶斯贝叶斯问题的求解问题的求解1.4 1.4 简单贝叶斯简单贝叶斯学习模型学习模型1.5 1.5 贝叶斯贝叶斯网络的建造网络的建造1.6 1.6 贝叶斯贝叶斯潜在语义模型潜在语义模型1.7 1.7 半监督半监督文本挖掘文本挖掘算法算法2023/1/931.1 概概 述述l贝叶斯网络是用来表示贝叶斯网络是用来表示变量间连接概率变量间连接概率的的图形图形模式模式，它提供了一种自然的表示，它提供了一种自然的表示因果信息因果信息的方的方法，用来发现数据间的潜在关系。在这个网络法，用来发现数据间的潜在关系。在这个网络中，用中，用节点节点表示表示变量变量，有向边有向边表示表示变量间变量间的依的依赖赖关系关系。l贝叶斯方法以其独特的贝叶斯方法以其独特的不确定性不确定性知识表达形式、知识表达形式、丰富的丰富的概率表达概率表达能力、综合先验知识的能力、综合先验知识的增量学增量学习习特性等成为当前数据挖掘众多方法中最为引特性等成为当前数据挖掘众多方法中最为引人注目的焦点之一。人注目的焦点之一。2023/1/941.1 概概 述述1.1.1 贝叶斯网络的发展历史贝叶斯网络的发展历史l贝叶斯贝叶斯（Reverend Thomas Bayes,1702-1761）学派奠学派奠基性的工作是贝叶斯的论文基性的工作是贝叶斯的论文“关于几率性问题求解的关于几率性问题求解的评论评论”。或许是他自己感觉到它的学说还有不完善的。或许是他自己感觉到它的学说还有不完善的地方，这一论文在他生前并没有发表，而是在他死后，地方，这一论文在他生前并没有发表，而是在他死后，由他的朋友发表的。著名的数学家拉普拉斯由他的朋友发表的。著名的数学家拉普拉斯（Laplace P.S.）用贝叶斯的方法导出了重要的用贝叶斯的方法导出了重要的“相继律相继律”，贝叶斯，贝叶斯的方法和理论逐渐被人理解和重视起来。但由于当时的方法和理论逐渐被人理解和重视起来。但由于当时贝叶斯方法在理论和实际应用中还存在很多不完善的贝叶斯方法在理论和实际应用中还存在很多不完善的地方，因而在十九世纪并未被普遍接受。地方，因而在十九世纪并未被普遍接受。2023/1/951.1 概概 述述1.1.1 贝叶斯网络的发展历史贝叶斯网络的发展历史l二十世纪初，意大利的菲纳特（二十世纪初，意大利的菲纳特（B.de Finetti）以及英以及英国的杰弗莱（国的杰弗莱（Jeffreys H.）都对贝叶斯学派的理论作出都对贝叶斯学派的理论作出重要的贡献。第二次世界大战后，瓦尔德（重要的贡献。第二次世界大战后，瓦尔德（Wald A.）提出了提出了统计的决策统计的决策理论，在这一理论中，贝叶斯解占有理论，在这一理论中，贝叶斯解占有重要的地位；信息论的发展也对贝叶斯学派做出了新的重要的地位；信息论的发展也对贝叶斯学派做出了新的贡献。贡献。1958年英国最悠久的统计杂志年英国最悠久的统计杂志Biometrika全文全文重新刊登了贝叶斯的论文，重新刊登了贝叶斯的论文，20世纪世纪50年代，以罗宾斯年代，以罗宾斯（Robbins H.）为代表，提出了经验贝叶斯方法和经为代表，提出了经验贝叶斯方法和经典方法相结合，引起统计界的广泛注意，这一方法很快典方法相结合，引起统计界的广泛注意，这一方法很快就显示出它的优点，成为很活跃的一个方向。就显示出它的优点，成为很活跃的一个方向。2023/1/961.1 概概 述述1.1.1 贝叶斯网络的发展历史贝叶斯网络的发展历史l随着人工智能的发展，尤其是机器学习、数据挖掘等随着人工智能的发展，尤其是机器学习、数据挖掘等兴起，为贝叶斯理论的发展和应用提供了更为广阔的兴起，为贝叶斯理论的发展和应用提供了更为广阔的空间。贝叶斯理论的内涵也比以前有了很大的变化。空间。贝叶斯理论的内涵也比以前有了很大的变化。8080年代年代贝叶斯网络贝叶斯网络用于专家系统的知识表示，用于专家系统的知识表示，9090年代年代进一步研究进一步研究可学习的贝叶斯网络可学习的贝叶斯网络，用于数据采掘和机，用于数据采掘和机器学习。近年来，贝叶斯学习理论方面的文章更是层器学习。近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涵盖了人工智能的大部分领域，包括因出不穷，内容涵盖了人工智能的大部分领域，包括因果推理、不确定性知识表达、模式识别和聚类分析等。果推理、不确定性知识表达、模式识别和聚类分析等。并且出现了专门研究贝叶斯理论的组织和学术刊物并且出现了专门研究贝叶斯理论的组织和学术刊物International Society Bayesian Analysis。2023/1/971.1 概概 述述1.1.2 贝叶斯方法的基本观点贝叶斯方法的基本观点l贝叶斯分析方法的贝叶斯分析方法的特点特点是是用概率去表示所有形式用概率去表示所有形式的不确定性，学习或其它形式的推理都用概率规的不确定性，学习或其它形式的推理都用概率规则来实现则来实现。l贝叶斯贝叶斯学习的结果学习的结果表示为随机变量的概率分布，表示为随机变量的概率分布，它可以解释为我们对不同可能性的信任程度。它可以解释为我们对不同可能性的信任程度。l贝叶斯学派的起点是贝叶斯的两项工作：贝叶斯学派的起点是贝叶斯的两项工作：贝叶斯贝叶斯定理定理和和贝叶斯假设贝叶斯假设。l贝叶斯定理将事件的贝叶斯定理将事件的先验概率先验概率与与后验概率后验概率联系起联系起来来。2023/1/981.1 概概 述述1.1.2 贝叶斯方法的基本观点贝叶斯方法的基本观点 假定假定随机向量随机向量x，的的联合分布密度联合分布密度是是p(x,)，它们它们的的边际密度边际密度分别为分别为p(x)、p()。一般情况下设一般情况下设x是是观测向观测向量量，是是未知参数向量未知参数向量，通过观测向量获得未知参数向，通过观测向量获得未知参数向量的估计，量的估计，贝贝叶斯定理叶斯定理记作：记作：()是是的先验分布的先验分布 (1.1)2023/1/991.1 概概 述述1.1.2 贝叶斯方法的基本观点贝叶斯方法的基本观点 贝贝叶斯方法叶斯方法对未知参数向量估计的一般过程对未知参数向量估计的一般过程为：为：将将未知参数看成未知参数看成随机向量，这是随机向量，这是贝贝叶斯方法与传统的参叶斯方法与传统的参数估计方法的最大区别。数估计方法的最大区别。根据以往对参数根据以往对参数的知识，确定先验分布的知识，确定先验分布()，它是它是贝贝叶叶斯方法容易引起争议的一步，因此而受到经典统计界的攻击。斯方法容易引起争议的一步，因此而受到经典统计界的攻击。计算后验分布密度，做出对计算后验分布密度，做出对未知参数的推断。未知参数的推断。在第在第步，步，如果没有任何以往的知识来帮助确定如果没有任何以往的知识来帮助确定()，贝贝叶斯提出可以采用均匀分布作为其分布，即参数在它的变叶斯提出可以采用均匀分布作为其分布，即参数在它的变化范围内，取到各个值的机会是相同的，化范围内，取到各个值的机会是相同的，称这个称这个假定假定为为贝贝叶叶斯假设斯假设。2023/1/9101.1 概概 述述1.1.3 贝叶斯网络的应用领域贝叶斯网络的应用领域l 辅助智能决策l 数据融合l 模式识别l 医疗诊断l 文本理解l 数据挖掘1.贝叶斯方法用于分类及回归分析贝叶斯方法用于分类及回归分析2.用于因果推理和不确定知识表达用于因果推理和不确定知识表达3.用于聚类模式发现用于聚类模式发现2023/1/9111.2 1.2 贝叶斯贝叶斯概率基础概率基础 1.2.1 概率论基础概率论基础 概率论概率论是研究是研究随机现象规律性随机现象规律性的数学的数学。随机现象随机现象是指在是指在相同的条件下，其出现的结果是不确定的现象。随机现象相同的条件下，其出现的结果是不确定的现象。随机现象又又可分为可分为个别随机现象个别随机现象和和大量的随机现象。对大量的随机现象大量的随机现象。对大量的随机现象进行观察所得到的规律性，被人们称为进行观察所得到的规律性，被人们称为统计规律性统计规律性。在统计上，我们习惯在统计上，我们习惯把一次对现象的观察、登记或实验把一次对现象的观察、登记或实验叫做叫做一次试验一次试验。随机性实验随机性实验是指对随机现象的观察。是指对随机现象的观察。随机试随机试验在完全验在完全相同的条件相同的条件下，可能出现下，可能出现不同的结果不同的结果，但所有可能，但所有可能结果的范围是结果的范围是可以估计可以估计的，即随机试验的结果具有的，即随机试验的结果具有不确定性不确定性和和可预计性可预计性。在统计上，一般把。在统计上，一般把随机实验的结果随机实验的结果，即，即随机现随机现象的具体表现象的具体表现称为称为随机事件随机事件，简称，简称事件事件。随机事件是指试验中随机事件是指试验中可能出现可能出现，也也可能不出现可能不出现的结果。的结果。2023/1/9121.2 1.2 贝叶斯贝叶斯概率基础概率基础 1.2.1 概率论基础概率论基础 定义定义1.1 统计概率统计概率 若在大量重复试验中，事若在大量重复试验中，事件件A发生的频率稳定地接近于一个固定的常数发生的频率稳定地接近于一个固定的常数p，它它表明事件表明事件A出现的可能性大小，则称此常数出现的可能性大小，则称此常数p为事件为事件A发生的概率，记为发生的概率，记为P(A),即即 pP(A)(1.2)可见概率就是频率的稳定中心。任何事件可见概率就是频率的稳定中心。任何事件A的概率的概率为不大于为不大于1的非负实数，即的非负实数，即0P(A)1 2023/1/9131.2 1.2 贝叶斯贝叶斯概率基础概率基础 定义定义1.2 古典概率古典概率 我们设一种次试验有且仅有我们设一种次试验有且仅有有限的有限的N个可能结果，即个可能结果，即N个基本事件，而个基本事件，而A事件包事件包含着含着K个可能结果，则称个可能结果，则称K/N为事件为事件A的概率，记为的概率，记为P(A)。即即P(A)K/N 定义定义1.3 几何概率几何概率 假设假设是几何型随机试验的是几何型随机试验的基本事件空间，基本事件空间，F是是中一切可测集的集合，则对于中一切可测集的集合，则对于F中的任意事件中的任意事件A的的概率概率P(A)为为A与与的体积之比，即的体积之比，即 P(A)V(A)/V()(1.3)2023/1/9141.2 1.2 贝叶斯贝叶斯概率基础概率基础 定义定义1.4 条件概率条件概率 我们把事件我们把事件B已经出已经出现的条件下，事件现的条件下，事件A发生的概率记做为发生的概率记做为P(A|B)。并称为在并称为在B出现的条件下出现的条件下A出现的出现的条件概率条件概率，而称而称P(A)为为无条件概率无条件概率。若事件若事件A与与B中的任一个出现，并不影响中的任一个出现，并不影响另一事件出现的概率，即当另一事件出现的概率，即当P(A)P(AB)或或P(B)P(BA)时，时，则称则称A与与B是相互独立的事件是相互独立的事件。2023/1/9151 1.2.2 贝叶斯贝叶斯概率基础概率基础 定理定理1.1 加法定理加法定理 两个不相容两个不相容(互斥互斥)事事件之和的概率，等于两个事件概率之和，即件之和的概率，等于两个事件概率之和，即P(A+B)P(A)P(B)两个互逆事件两个互逆事件A和和A-1的概率之和为的概率之和为1。即当。即当A+A-1，且且A与与A-1互斥，则互斥，则P(A)P(A-1)1，或常有或常有P(A)1P(A-1)。若若A、B为两任意事件，则为两任意事件，则P(A+B)P(A)P(B)P(AB)2023/1/9161 1.2.2 贝叶斯贝叶斯概率基础概率基础 定理定理1.2 乘法定理乘法定理 设设A、B为两个为两个不相不相容容(互斥互斥)非零事件，则其乘积的概率等于非零事件，则其乘积的概率等于A和和B概率的乘积，即概率的乘积，即P(AB)P(A)P(B)或或 P(AB)P(B)P(A)设设A、B为两个任意的非零事件，则其乘为两个任意的非零事件，则其乘积的概率等于积的概率等于A(或或B)的概率与在的概率与在A(或或B)出现出现的条件下的条件下B(或或A)出现的条件概率的乘积。出现的条件概率的乘积。P(AB)P(A)P(B|A)或或 P(AB)P(B)P(A|B)2023/1/9171 1.2.2 贝叶斯贝叶斯概率基础概率基础1.2.2 贝叶斯概率贝叶斯概率 (1)先验概率。先验概率。先验概率是指根据历史的先验概率是指根据历史的资料或主观判断所确定的各事件发生的概率，资料或主观判断所确定的各事件发生的概率，该类概率该类概率没能经过实验证实没能经过实验证实，属于检验前的概，属于检验前的概率，所以称之为率，所以称之为先验概率先验概率。先验概率一般分为。先验概率一般分为两类，一是两类，一是客观先验概率客观先验概率，是指利用过去的历，是指利用过去的历史资料计算得到的概率史资料计算得到的概率；二是；二是主观先验概率主观先验概率，是指在无历史资料或历史资料不全的时候，只是指在无历史资料或历史资料不全的时候，只能凭借人们的主观经验来判断取得的概率能凭借人们的主观经验来判断取得的概率。2023/1/9181 1.2.2 贝叶斯贝叶斯概率基础概率基础 (2)后验概率。后验概率。后验概率一般是指后验概率一般是指利用贝利用贝叶斯公式叶斯公式，结合调查等方式结合调查等方式获取了新的附加获取了新的附加信息，对先验概率进行修正后得到的更符合信息，对先验概率进行修正后得到的更符合实际的概率。实际的概率。(3)联合概率。联合概率。联合概率也叫联合概率也叫乘法公式乘法公式，是指两个任意事件的乘积的概率是指两个任意事件的乘积的概率，或称之为，或称之为交事件的概率交事件的概率。2023/1/9191 1.2.2 贝叶斯贝叶斯概率基础概率基础 (4)全概率公式全概率公式。设设B1,B2,Bn是两两互斥的事是两两互斥的事件，且件，且P(Bi)0，i=1,2,n，B1+B2+,+Bn=。另有一事件另有一事件A=AB1+AB2+,+ABn称满足上述条件的称满足上述条件的B1,B2,Bn为为完备事件组完备事件组。B1B2B3BnA1 1.2.2 贝叶斯贝叶斯概率基础概率基础 由由此此可可以以形形象象地地把把全全概概率率公公式式看看成成为为“由由原原因因推推结结果果”，每每个个原原因因对对结结果果的的发发生生有有一一定定的的“作作用用”，即即结结果果发发生生的的可可能能性性与与各各种种原原因因的的“作作用用”大大小小有有关关。全全概概率率公公式式表表达达了了它它们们之之间的关系。间的关系。诸诸Bi是是原因原因A是是结果结果B1B2B3B4B5B6B7B8A1 1.2.2 贝叶斯贝叶斯概率基础概率基础 该公式于该公式于1763年由贝叶斯年由贝叶斯(Bayes)给出。它给出。它是在观察到事件是在观察到事件A已发生的条件下，寻找导致已发生的条件下，寻找导致A发生的每个原因的概率。发生的每个原因的概率。(5)贝贝叶叶斯斯公公式式。贝贝叶叶斯斯公公式式也也叫叫后后验验概概率率公公式式，亦亦叫叫逆逆概概率率公公式式，其其用用途途很很广广。设设先先验验概概率率为为P(Bi)，调调 查查 所所 获获 的的 新新 附附 加加 信信 息息 为为 P(Aj|Bi)(i=1,2,n;j=1,2,m),则则贝贝叶叶斯斯公公式式计计算算的的后后验验概率为概率为(1.5)2023/1/922贝叶斯规则贝叶斯规则l基于条件概率的定义lp(Ai|E)是在给定证据下的后验概率lp(Ai)是先验概率lP(E|Ai)是在给定Ai下的证据似然lp(E)是证据的预定义后验概率=iiiiiiii)p(AA|p(E)p(AA|p(Ep(E)p(AA|p(EE)|p(A=p(B)A)p(A)|p(Bp(B)B)p(A,B)|p(AA1A2A3A4A5A6E2023/1/923贝叶斯网络的概率解释贝叶斯网络的概率解释l任何完整的概率模型必须具有表示（直接或间接）该领域变量联合分布的能力。完全的枚举需要指数级的规模（相对于领域变量个数）l贝叶斯网络提供了这种联合概率分布的紧凑表示：分解联合分布为几个局部分布的乘积：l从公式可以看出，需要的参数个数随网络中节点个数呈线性增长，而联合分布的计算呈指数增长。l网络中变量间独立性的指定是实现紧凑表示的关键。这种独立性关系在通过人类专家构造贝叶斯网中特别有效。2023/1/9241 1.4.4 简单贝叶斯学习模型简单贝叶斯学习模型 简单贝叶斯简单贝叶斯（nave Bayes或或simple Bayes）学习模型学习模型将训练实例将训练实例I分解成特征向量分解成特征向量X和决策类别变量和决策类别变量C。简单贝简单贝叶斯模型假定特征向量的各分量间相对于决策变量是相对叶斯模型假定特征向量的各分量间相对于决策变量是相对独立的，也就是说独立的，也就是说各分量独立地作用于决策变量各分量独立地作用于决策变量。尽管这。尽管这一假定一定程度上限制了简单贝叶斯模型的适用范围，然一假定一定程度上限制了简单贝叶斯模型的适用范围，然而在实际应用中，不仅以而在实际应用中，不仅以指数级指数级降低了贝叶斯网络构建的降低了贝叶斯网络构建的复杂性，复杂性，而且在许多领域，在违背这种假定的条件下而且在许多领域，在违背这种假定的条件下，简，简单贝叶斯也表现出相当的健壮性和高效性，它已经成功地单贝叶斯也表现出相当的健壮性和高效性，它已经成功地应用到分类、聚类及模型选择等数据挖掘的任务中。目前，应用到分类、聚类及模型选择等数据挖掘的任务中。目前，许多研究人员正致力于改善特征变量间独立性的限制，以许多研究人员正致力于改善特征变量间独立性的限制，以使它适用于更大的范围。使它适用于更大的范围。2023/1/9史忠植 高级人工智能25简单贝叶斯简单贝叶斯 Nave Bayesian结构简单只有两层结构推理复杂性与网络节点个数呈线性关系2023/1/926设样本A表示成属性向量，如果属性对于给定的类别独立，那么P(A|Ci)可以分解成几个分量的积：ai是样本A的第i个属性 1 1.4.4 简单贝叶斯学习模型简单贝叶斯学习模型2023/1/927简单贝叶斯分类模型这个过程称之为这个过程称之为简单贝叶斯分类简单贝叶斯分类(SBC:Simple Bayesian SBC:Simple Bayesian Classifier)Classifier)。一般认为，只有在独立性假定成立的时候，一般认为，只有在独立性假定成立的时候，SBCSBC才能获得精度最优的分类效率；或者在属性相关性较小才能获得精度最优的分类效率；或者在属性相关性较小的情况下，能获得近似最优的分类效果。的情况下，能获得近似最优的分类效果。1 1.4.4 简单贝叶斯学习模型简单贝叶斯学习模型1.4.1 简单贝叶斯学习模型的介绍简单贝叶斯学习模型的介绍2023/1/9281.4.2 简单贝叶斯模型的提升简单贝叶斯模型的提升 提升方法（提升方法（Boosting）总的思想是学习一总的思想是学习一系列分类器，在这个序列中每一个分类器对它系列分类器，在这个序列中每一个分类器对它前一个分类器导致的错误分类例子给与更大的前一个分类器导致的错误分类例子给与更大的重视。尤其是在学习完分类器重视。尤其是在学习完分类器Hk之后，增加了之后，增加了由由Hk导致分类错误的训练例子的权值，并且通导致分类错误的训练例子的权值，并且通过重新对训练例子计算权值，再学习下一个分过重新对训练例子计算权值，再学习下一个分类器类器Hk+1。这个过程重复这个过程重复T次。最终的分类器从次。最终的分类器从这一系列的分类器中综合得出。这一系列的分类器中综合得出。1 1.4.4 简单贝叶斯学习模型简单贝叶斯学习模型2023/1/9291 1.5.5 贝叶斯网络的建造贝叶斯网络的建造1.5.1 贝叶斯网络的建构及建立方法贝叶斯网络的建构及建立方法 贝叶斯网络是表示变量间概率依赖贝叶斯网络是表示变量间概率依赖关系的有向无环图，这里每个节点表示关系的有向无环图，这里每个节点表示领域变量，每条边表示变量间的概率依领域变量，每条边表示变量间的概率依赖关系，同时对每个节点都对应着一个赖关系，同时对每个节点都对应着一个条件概率分布表条件概率分布表(CPT)，指明了该变量指明了该变量与父节点之间概率依赖的数量关系。与父节点之间概率依赖的数量关系。2023/1/930贝叶斯网的表示方法贝叶斯网的表示方法=P(A)P(S)P(T|A)P(L|S)P(B|S)P(C|T,L)P(D|T,L,B)P(A,S,T,L,B,C,D)条件独立性假设有效的表示CPT:T L B D=0 D=10 0 0 0.1 0.90 0 1 0.7 0.30 1 0 0.8 0.20 1 1 0.9 0.1 .LungCancerSmokingChestX-rayBronchitisDyspnoeaTuberculosisVisittoAsiaP(D|T,L,B)P(B|S)P(S)P(C|T,L)P(L|S)P(A)P(T|A)贝叶斯网络是表示变量间概率依赖关系的有向无环图2023/1/931BoostingBoosting背景背景l来源于:PAC-Learning Model Valiant 1984-11l提出问题:l强学习算法:准确率很高的学习算法l弱学习算法:准确率不高,仅比随机猜测略好l是否可以将弱学习算法提升为强学习算法2023/1/932BoostingBoosting背景背景l最初的boosting算法 Schapire 1989lAdaBoost算法 Freund and Schapire 19952023/1/933Boostingconcepts(3)Boostingl弱学习机（weak learner):对一定分布的训练样本给出假设（仅仅强于随机猜测）根据有云猜测可能会下雨l强学习机（strong learner):根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almost perfect expert)根据CNN,ABC,CBS以往的预测表现及实际天气情况作出综合准确的天气预测l弱学习机 强学习机2023/1/934BoostingBoosting流程流程(loop1)(loop1)强学习机弱学习机原始训练集加权后的训练集加权后的假设X1?1:-1弱假设2023/1/935BoostingBoosting流程流程(loop2)(loop2)强学习机弱学习机原始训练集加权后的训练集加权后的假设Y3?1:-1弱假设2023/1/936BoostingBoosting流程流程(loop3)(loop3)强学习机弱学习机原始训练集加权后的训练集加权后的假设Z7?1:-1弱假设2023/1/937Boostingl过程:l在一定的权重条件下训练数据，得出分类法Ctl根据Ct的错误率调整权重Set of weightedinstances Classifier Ct train classifier adjust weights2023/1/938流程描述流程描述lStep1:原始训练集输入，带有原始分布lStep2:给出训练集中各样本的权重lStep3:将改变分布后的训练集输入已知的弱学习机，弱学习机对每个样本给出假设lStep4:对此次的弱学习机给出权重lStep5:转到Step2,直到循环到达一定次数或者某度量标准符合要求lStep6:将弱学习机按其相应的权重加权组合形成强学习机2023/1/939核心思想核心思想l样本的权重l没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/Nl每次循环一后提高错误样本的分布概率，分错样本在训练集中所占权重增大，使得下一次循环的弱学习机能够集中力量对这些错误样本进行判断。l弱学习机的权重l准确率越高的弱学习机权重越高l循环控制：损失函数达到最小l在强学习机的组合中增加一个加权的弱学习机，使准确率提高，损失函数值减小。2023/1/940简单问题演示（简单问题演示（BoostingBoosting训练过程）训练过程）2023/1/9史忠植 高级人工智能41算法算法问题描述问题描述l训练集 (x1,y1),(x2,y2),(xN,yN)lxi Rm,yi -1,+1lDt 为第t次循环时的训练样本分布（每个样本在训练集中所占的概率，Dt总和应该为1）lht:X-1,+1 为第t次循环时的Weak learner，对每个样本给出相应的假设，应该满足强于随机猜测：lwt为ht的权重l 为t次循环得到的Strong learner2023/1/942算法算法样本权重样本权重l思想：提高分错样本的权重l 反映了strong learner对样本的假设是否正确l采用什么样的函数形式？2023/1/943算法算法弱学习机权重弱学习机权重l思想：错误率越低，该学习机的权重应该越大l 为学习机的错误概率l采用什么样的函数形式？和指数函数遥相呼应：2023/1/944算法算法-Adaboost-Adaboost2023/1/945AdaBoost.M1l初始赋予每个样本相等的权重1/N；lFor t=1,2,T Do l学习得到分类法Ct；l计算该分类法的错误率Et Et=所有被错误分类的样本的权重和；lt=Et/（1-Et）l根据错误率更新样本的权重；正确分类的样本：Wnew=Wold*t 错误分类的样本：Wnew=Woldl调整使得权重和为1；l每个分类法Ct的投票价值为log 1/t 2023/1/946AdaBoost Training Errorl将t=1/2-Et;lFreund and Schapire 证明:最大错误率为:l即训练错误率随t的增大呈指数级的减小.2023/1/947AdaBoost Generalization Error(1)l最大总误差:lm:样本个数ld:VC维lT:训练轮数lPr:对训练集的经验概率l如果T值太大,Boosting会导致过适应（overfit）2023/1/9史忠植 高级人工智能48AdaBoost Generalization Error(2)l许多的试验表明:Boosting不会导致overfit2023/1/949AdaBoost Generalization Error(3)l解释以上试验现象;l样本(X,Y)的margin:margin(x,y)=lt=1/2 ln(1-t)/t)l较大的正边界表示可信度高的正确的预测l较大的负边界表示可信度高的错误的预测2023/1/950AdaBoost Generalization Error(4)l解释:当训练误差降低后,Boosting继续提高边界,从而增大了最小边界,使分类的可靠性增加,降低总误差.l总误差的上界:l该公式与T无关2023/1/951BoostingBoosting其它应用其它应用lBoosting易受到噪音的影响;lAdaBoost 可以用来鉴别异常;具有最高权重的样本即为异常.2023/1/952是表示变量间连结关系的有向无环图贝叶斯网络的学习结构学习参数学习基于评分函数的结构学习基于条件独立性检验的结构学习构建贝叶斯网络构建贝叶斯网络2023/1/953构建贝叶斯网络构建贝叶斯网络BayesianNetworkBayesianNetworkBayesianNetworkProblemDomainProblemDomainProblemDomainExpertKnowledgeExpertKnowledgeTrainingDataTrainingDataProbabilityElicitorLearningAlgorithmLearningAlgorithm2023/1/9541.3 贝叶斯问题的求解贝叶斯问题的求解 贝叶斯学习理论利用先验信息和样本数据来获贝叶斯学习理论利用先验信息和样本数据来获得对未知样本的估计，而概率（联合概率和条件概得对未知样本的估计，而概率（联合概率和条件概率）是先验信息和样本数据信息在贝叶斯学习理论率）是先验信息和样本数据信息在贝叶斯学习理论中的表现形式。如何获得这些概率（也称之为中的表现形式。如何获得这些概率（也称之为密度密度估计估计）是贝叶斯学习理论争议较多的地方。）是贝叶斯学习理论争议较多的地方。研究如何根据样本的数据信息和人类专家的先验研究如何根据样本的数据信息和人类专家的先验知识获得对未知变量（向量）的分布及其参数的估计。知识获得对未知变量（向量）的分布及其参数的估计。它有它有两个过程两个过程：一是一是确定未知变量的先验分布；确定未知变量的先验分布；二是二是获得相应分布的参数估计。获得相应分布的参数估计。如果以前对所有信息一无如果以前对所有信息一无所知，称这种分布为所知，称这种分布为无信息先验分布无信息先验分布；如果知道其分如果知道其分布求它的分布参数，布求它的分布参数，称之为称之为有信息先验分布有信息先验分布。2023/1/9551 1.3.3 贝叶斯问题的求解贝叶斯问题的求解 选取选取贝叶斯先验概率是用贝叶斯模型贝叶斯先验概率是用贝叶斯模型求解求解的的第第一步一步，也是比较关键的一步。常用的选取先验分布，也是比较关键的一步。常用的选取先验分布的方法有的方法有主观主观和和客观客观两种。两种。主观的方法主观的方法是是借助人的借助人的经验、专家的知识等来指定其先验概率经验、专家的知识等来指定其先验概率。而。而客观的客观的方法方法是是通过直接分析数据的特点，来观察数据变化通过直接分析数据的特点，来观察数据变化的统计特征的统计特征，它要求有足够多的数据才能真正体现，它要求有足够多的数据才能真正体现数据的真实分布。数据的真实分布。2023/1/9561 1.3.3 贝叶斯问题的求解贝叶斯问题的求解l共轭分布族l先验与后验属于同一分布族l预先给定一个似然分布形式l对于变量定义在0-1之间的概率分布，存在一个离散的样本空间lBeta 对应着 2 个似然状态l多变量 Dirichlet 分布对应 2个以上的状态从数据中学习从数据中学习1.3 贝叶斯问题的求解贝叶斯问题的求解1.3.1几种常用的先验分布选取方法 1.共轭分布族共轭分布族 Raiffa和和Schaifeer提出先验分布应选取共轭提出先验分布应选取共轭分布，即要求后验分布与先验分布属于同一分分布，即要求后验分布与先验分布属于同一分布类型。它的一般描述为布类型。它的一般描述为:定定义义6.7 设设样样本本X1,X2,Xn 对对参参数数的的条条件件分分布布为为p(x1,x2,xn|)，如如果果先先验验分分布布密密度度函函数数()决决定定的的后后验验密密度度(|x)与与()同同属属于于一一种种类类型型，则称则称()为为p(x|)的的共轭分布共轭分布。1.3 贝叶斯问题的求解贝叶斯问题的求解1.3.1几种常用的先验分布选取方法 2.最大熵原则最大熵原则 熵是信息论中描述事物不确定性的程度的熵是信息论中描述事物不确定性的程度的一个概念。如果一个随机变量只取与两个不同一个概念。如果一个随机变量只取与两个不同的值，比较下面两种情况：的值，比较下面两种情况：(1)p(x=a)=0.98，p(x=a)=0.02；(2)p(x=a)=0.45，p(x=a)=0.55。很很明明显显，(1)的的不不确确定定性性要要比比(2)的的不不确确定定性性小小得得多多，而而且且从从直直觉觉上上也也可可以以看看得得出出当当取取的的两两个个值得概率相等时，不确定性达到最大。值得概率相等时，不确定性达到最大。1.3 贝叶斯问题的求解贝叶斯问题的求解1.3.1几种常用的先验分布选取方法 定义定义1.9 设随机变量设随机变量x是离散的，它取是离散的，它取a1 1,a2,ak k,可列个值，且可列个值，且p(x=ai i)=pi i(i=1,2,)，则则H(x)=-pilnpi称为称为x的熵的熵。对连续型随机变量对连续型随机变量x，它的概率密度函数为它的概率密度函数为p(x)，若若积分积分H(x)=-p(x)lnp(x)dx有意义有意义，称它为，称它为连续型随机变量的熵连续型随机变量的熵。最大熵原则最大熵原则：无信息先验分布应取参数无信息先验分布应取参数的变化范围的变化范围内熵最大的分布内熵最大的分布。1.3 贝叶斯问题的求解贝叶斯问题的求解1.3.1几种常用的先验分布选取方法 3.杰弗莱原则杰弗莱原则 杰弗莱对于先验分布的选取做出了重大的贡献，杰弗莱对于先验分布的选取做出了重大的贡献，它提出一个不变原理，较好地解决了贝叶斯假设中它提出一个不变原理，较好地解决了贝叶斯假设中的一个矛盾，并且给出了一个寻求先验密度的方法。的一个矛盾，并且给出了一个寻求先验密度的方法。杰弗莱原则由杰弗莱原则由两个部分两个部分组成：组成：一是一是对先验分布有一对先验分布有一合理要求；合理要求；二是二是给出具体的方法求得适合于要求的给出具体的方法求得适合于要求的先验分布。先验分布。1.3 贝叶斯问题的求解贝叶斯问题的求解1.3.2 计算学习机制 任何系统经过运行能改善其行为，都是任何系统经过运行能改善其行为，都是学习学习。到底贝叶斯公式求得的后验是否比原来信息有所改到底贝叶斯公式求得的后验是否比原来信息有所改善呢？其学习机制是什么？善呢？其学习机制是什么？现以正态分布为例进行分析，从参数的变化看现以正态分布为例进行分析，从参数的变化看先验信息和样本数据在学习中所起的作用。先验信息和样本数据在学习中所起的作用。1.3 贝叶斯问题的求解贝叶斯问题的求解1.3.3 贝叶斯问题的求解步骤 贝叶斯问题求解的基本步骤可以概括为：贝叶斯问题求解的基本步骤可以概括为：(1)定义随机变量。将未知参数看成随机变量（或随机向定义随机变量。将未知参数看成随机变量（或随机向量），记为量），记为。将样本将样本x1 1,x2 2,xn n的联合分布密度的联合分布密度p(x1 1,x2 2,xn n;)看成看成x1 1,x2 2,xn n对对的条件分布密度，记为的条件分布密度，记为p(x1 1,x2 2,xn n|)或p(D|)。(2)确定先验分布密度确定先验分布密度p()。采用。采用共轭分布共轭分布先验分布。如先验分布。如果对先验分布没有任何信息，就采用无信息先验分布的贝叶果对先验分布没有任何信息，就采用无信息先验分布的贝叶斯假设。斯假设。(3)利用贝叶斯定理计算后验分布密度利用贝叶斯定理计算后验分布密度。(4)利用计算得到的后验分布密度对所求问题做出判断。利用计算得到的后验分布密度对所求问题做出判断。2023/1/9631)n(nm/n)m(1variance+-=nmmean=x)(1xm)(n(m)(n)n)m,|(xp1mn1mBeta-=-G GG GG G先验分布的选取先验分布的选取betabeta分布分布2023/1/964先验分布的选取多项先验分布的选取多项DirichletDirichlet分布分布1)m(m)m/m(1mstatei theofvariancemmstatei theofmean.xxx)(m).(m)(m)m()m,.,m,m|(xpN1iiN1iiN1iiiithN1iiith1m1-m1mN21N1iiN21DirichletN21+-=GGGG=-=2023/1/965不完全数据的密度估计不完全数据的密度估计期望最大化方法（ExpectationMaximizationEM）Gibbs抽样（GibbsSamplingGS）Bound and Collapse(BC)2023/1/966期望最大化方法期望最大化方法分为以下几个步骤：（1）含有不完全数据的样本的缺项用该项的最大似然估计代替；（2）把第一步中的缺项值作为先验信息，计算每一缺项的最大后验概率，并根据最大后验概率计算它的理想值。（3）用理想值替换（1）中的缺项。（4）重复（13），直到两次相继估计的差在某一固定阀值内。2023/1/967GibbsGibbs抽样抽样lGibbs抽样（Gibbs Sampling GS）GS是