Brute- Force贝叶斯概念学习 概念学习问题:有限假设空间H定义在实例空 间X上,任务是学习某个目标概念c Brute- Force map学习算法 对于H中每个假设h,计算后验概率 P(hID)=P(DIh)P(h) P(D) 输出有最高后验概率的假设b=mD 上面算法需要较大计算量,因为它要计算每个 假设的后验概率,对于大的假设空间显得不切 实际,但是它提供了一个标准以判断其他概念 学习算法的性能 2003.12.18 机器学习-贝叶斯学习作者: Mitchel译者:曾华军等讲者:陶晓鹏 16
2003.12.18 机器学习-贝叶斯学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 16 Brute-Force贝叶斯概念学习 • 概念学习问题：有限假设空间H定义在实例空 间X上，任务是学习某个目标概念c。 • Brute-Force MAP学习算法 – 对于H中每个假设h，计算后验概率 – 输出有最高后验概率的假设 • 上面算法需要较大计算量，因为它要计算每个 假设的后验概率，对于大的假设空间显得不切 实际，但是它提供了一个标准以判断其他概念 学习算法的性能 ( ) ( | ) ( ) ( | ) P D P D h P h P h D = h argmax P(h | D) h H MAP =
特定情况下的MAP假设 假定 训练数据D是无噪声的,即d=c(x) 目标概念c包含在假设空间H中 每个假设的概率相同 求得 由于所有假设的概率之和是1,因此mm 由于训练数据无噪声,那么给定假设h时,与h致 的D的概率为1,不一致的概率为0,因此 P(DIho ∫1vd,d=x) othenwise 2003.12.18 机器学习-贝叶斯学习作者: Mitchel译者:曾华军等讲者:陶晓鹏 17
2003.12.18 机器学习-贝叶斯学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 17 特定情况下的MAP假设 • 假定 – 训练数据D是无噪声的，即di=c(xi ) – 目标概念c包含在假设空间H中 – 每个假设的概率相同 • 求得 – 由于所有假设的概率之和是1，因此 – 由于训练数据无噪声，那么给定假设h时，与h一致 的D的概率为1，不一致的概率为0，因此 | | 1 ( ) H P h = = = otherwise d d h x P D h i i i , ( ) 0 1 ( | )
特定情况下的MAP假设(2) 考虑 Brute-Force mAP算法的第一步 h与D不一致 ,P(h|D)=h) P(D) h与D一致, P(hD)=~|H⊥ H P(D) SH,DI L H VSHD是关于D的变型空间(见第2章,即与 D一致的偎设集) 2003.12.18 机器学习-贝叶斯学习作者: Mitchel译者:曾华军等讲者:陶晓鹏 18
2003.12.18 机器学习-贝叶斯学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 18 特定情况下的MAP假设（2） • 考虑Brute-Force MAP算法的第一步 – h与D不一致， – h与D一致， ， VSH,D是关于D的变型空间（见第2章，即与 D一致的假设集） 0 ( ) 0 ( ) ( | ) = = P D P h P h D | | 1 | | | | | | 1 ( ) | | 1 1 ( | ) , H ,D VSH D H VS H P D H P h D = = =
特定情况下的MAP假设(3) PD)的推导 P(D)-∑DbPb) H 1 H H 假设的概率演化情况如图6-1所示,初始时所有 假设具有相同的概率,当训练数据逐步出现后, 不一致假设的概率变为0,而整个概率的和为1, 它们均匀分布到剩余的一致假设中 每个一致的假设都是MAP假设 2003.12.18 机器学习-贝叶斯学习作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-贝叶斯学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 19 特定情况下的MAP假设（3） • P(D)的推导 P(D) • 假设的概率演化情况如图6-1所示，初始时所有 假设具有相同的概率，当训练数据逐步出现后， 不一致假设的概率变为0，而整个概率的和为1， 它们均匀分布到剩余的一致假设中 • 每个一致的假设都是MAP假设 | | | | | | 1 1 | | 1 0 | | 1 1 ( | ) ( ) , , , , H VS H H H P D h P h H D h VS h VS h VS h H i i i H D i H D i H D i = = = + =
MAP假设和一致学习器 致学习器:如果某个学习器输出的假设在训练样例 上为0错误率,则称为一致学习器 ·如果H上有均匀的先验概率,且训练数据是确定性和无 噪声的,任意一致学习器将输出一个MAP假设 Find-S算法按照特殊到一般的顺序搜索架设空间H,并 输出一个极大特殊的一致假设,因此可知在上面定义 的P(h)和P(Dh概率分布下,它输出MAP假设 更一般地,对于先验概率偏袒于更特殊假设的任何概 率分布,Find-S输出的假设都是MAP假设 2003.12.18 机器学习-贝叶斯学习作者: Mitchel译者:曾华军等讲者:陶晓鹏 20
2003.12.18 机器学习-贝叶斯学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 20 MAP假设和一致学习器 • 一致学习器：如果某个学习器输出的假设在训练样例 上为0错误率，则称为一致学习器 • 如果H上有均匀的先验概率，且训练数据是确定性和无 噪声的，任意一致学习器将输出一个MAP假设 • Find-S算法按照特殊到一般的顺序搜索架设空间H，并 输出一个极大特殊的一致假设，因此可知在上面定义 的P(h)和P(D|h)概率分布下，它输出MAP假设 • 更一般地，对于先验概率偏袒于更特殊假设的任何概 率分布，Find-S输出的假设都是MAP假设