《机器学习研究》PPT课件.ppt

《《机器学习研究》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《机器学习研究》PPT课件.ppt（93页珍藏版）》请在三一办公上搜索。

1、机器学习研究,反思,网络经济的泡沫破灭之后，哪些是值得我们在研究方向上反思的问题呢？我们的研究应注意哪些课题呢？,需求-NII计划,不分地域地、有效地获得与传输信息。不分地域地、有效地共享硬软资源。有效地利用信息，以提高生产率。保证信息安全。,在过去的十年中，做了什么？,以浏览器为核心技术的“有效获得信息”的研究取得了预期效果。人们已可以从不同地域有效地获得信息。但是，,硬软资源的使用,在网络上的硬软资源的利用率只有3-5%。大量计算资源没有由于网络设施的支持而被充分利用。硬软件的快速更新，导致对环境的污染。,信息的有效使用,由于技术发展的滞后，在网络上获得的信息和与提高生产率有关的信息的有效

2、使用率甚至低于1%。占用大量硬软资源的信息正在大量地被浪费。,信息安全,信息的安全还没有保证。,提高信息使用率,以机器学习为理论基础的各种方法，是提高信息使用率的有效途径之一。,机器学习复杂数据分析(符号机器学习),机器学习,机器学习的一般说明统计机器学习集成机器学习,机器学习的研究动力,领域应用驱动。算法驱动。,领域应用驱动,自然语言数据分析。DNA数据分析。网络与电信数据分析。图像数据分析。金融与经济数据分析。零售业数据分析。情报分析。没有一种算法可以解决复杂的实际问题。需要各种算法集成。,算法驱动,海量数据(108-10)。算法的泛化能力，或算法可解释。不同类型数据的学习方法。,机器学习

3、研究热点的变迁,1989年(Carbonell),1997年(Dietterich)符号机器学习。符号机器学习。连接机器学习。集成机器学习。遗传机器学习。统计机器学习。分析机器学习。增强机器学习。,机器学习计算的说明,令W是这个给定世界的有限或无限所有对象的集合，由于我们观察能力的限制，我们只能获得这个世界的一个有限的子集QW。机器学习的任务就是根据这个世界的对象子集Q，计算这个世界的统计分布。这样，在统计意义下，这个分布对这个世界的绝大多数对象是正确的。这就是这个世界的一个模型。,三个要求,一致性假设：机器学习任务的本质。对样本空间的划分：决定对样本的有效性。泛化能力：决定对世界的有效性。,

4、一致性假设,假设世界W与被观察的对象集合Q具有某种相同的性质。称为一致性假设。,基于统计的假设,原则上说，存在各种各样的一致性假设。在统计意义下，一般假设：W与Q具有同分布。或，给定世界W的所有对象独立同分布。,划分,将被观测的对象集合放到一个n维欧氏空间，寻找一个超平面，使得问题决定的不同对象分在不相交的区域。机器学习主要研究的是这部分内容，即，寻找划分对象集合的超平面(等价关系)。,超平面类型,光滑且连续的超平面。有限不光滑点，甚至有限不连续点的超平面。,光滑连续超平面作为研究基础,Perceptron，人工神经网络是典型例子。困难：对线性不可分的对象集合，如果限制算法是P的，则存在本质性

5、困难。,泛化,机器学习的首要任务是划分。只有找到一个等价关系(模型)，将不同类的样本划分为不同的类，才能考虑其他问题。泛化是一个确定的划分对世界的分类能力。由于可能存在不同的划分样本集合方法，其泛化能力不同，泛化能力最强的划分就是我们希望的分类器。,Duda的泛化能力描述,以样本个数趋近无穷大来描述模型的泛化能力。泛化能力需要使用世界W来刻画，是无法构造的判据。均方差可作为目标函数。,评述,由于人们没有找到基于样本集合Q的描述泛化能力的数学工具。另外，线性不可分问题是一个困难。在感知机时代，基于Duda泛化理论无法指导机器学习算法的设计，这样，评价机器学习算法只能以划分能力作为指标。Vapni

6、k对这个问题做出重要贡献。这样，注重从划分变为泛化。,以划分能力为目标的研究,这类研究的指导思想，一直延续到上个世纪的九十年代。直到今天，还有大量的学者以此作为机器学习的指导思想。以BP算法为核心的神经网络研究是典型例子。划分是机器学习的一个目标，但是，不是预测任务的主要研究目标。,神经网络-BP算法,使用了一种非线性的基函数。这项研究的意义是为研究者回归感知机做好了舆论的准备。其在科学上的意义，远不如提示人们再次注意感知机的作用更大。,统计机器学习理论与SVM,对机器学习的研究者来说，统计机器学习理论所派生的算法SVM似乎更有吸引力。但是，如果研究者忘记SVM所基于的统计基础，就与Vapni

7、k的本意相悖了。事实上，Vapnik的统计理论才是其精华，而基于这个理论的算法只是从这个统计理论派生的自然结果。,机器学习的统计假设,机器学习的统计基础是基于经验风险最小假设，以此，对机器学习算法所建模型的泛化能力估计(经验风险)。,Vapnik的统计观点,Vapnik希望改变Duda的统计观点。泛化描述“从样本数趋于无穷大”变为“在给定样本集”基础上判定。由此，建立基于样本集合结构的VC维来描述的理论。这样，机器学习的目标函数就可以建立在样本集合的结构之上。这是统计机器学习理论的精髓。,泛化能力,以下不等式依概率1-成立：R:包含所有样本的球半径M:边缘l:样本个数,泛化不等式的解释,M0，

8、边缘不能等于零。这意味着，样本集合必须是可划分的。边缘最大，泛化能力最强。泛化能力可以使用样本集合的边缘来刻画。泛化能力的描述无需使用世界W来刻画，而只需样本集合Q来刻画。,泛化能力的几何解释(示意图),线性可分问题,定理：如果一个样本集合是线性可分的，它们一定可以构成两个不相交的闭凸集。这样，线性可分问题变为计算两个闭凸集的最大边缘问题。,线性不可分问题,划分问题：怎样获得两个不相交的闭凸集。泛化问题：怎样使两个闭凸集之间的距离最大。,核技术,可以证明，一定存在一个映射，称为核函数，将在欧式空间定义的样本映射到特征空间(一个更高维的空间)，使得在特征空间上，样本构成两个不相交的闭凸集。研究核

9、函数选择的技术称为核技术。,SVM,给定核函数，如果它可以保证将样本集合在特征空间变换为两个不相交的闭凸集，则对这个样本集合的最大边缘可以通过二次规划、计算几何等方法获得。由此，可以获得支持向量。这就是SVM。,未解决的问题,在特征空间样本集合是否可以划分为不相交的闭凸集，决定于核函数的选择。最大边缘尽量大，也决定于核函数的选择。核函数的选择没有一般的方法。准确地说，加大特征空间维数是一个方法，确定最小维数没有P算法。,解决线性不可分问题的方法,核函数选择的困难可能是根本性的。技术措施：同时考虑不满足一致性假设的情况。软边缘。集成机器学习。,两类技术措施的统计解释,目的是解决样本集合不满足一致

10、性假设，采用不确定性来补充，以使得模型与实际世界的统计分布一致。措施：软边缘：将边缘改为软性(有个范围)，以适应需要。集成机器学习：多个分类器集成，以使用不同模型补充一个模型的不足。,集成机器学习动机,弱分类器设计简单。在理论上似乎与Madaline类似。,集成机器学习,1990年Shapire证明，如果将多个弱分类器集成在一起，它将具有强分类器的泛化能力。进而，又说明，这类集成后的强分类器具有统计学习理论的基础。,弱分类器,如果一个分类器的分类能力(泛化)稍大于50%，这个分类器称为弱分类器。这意味着，比掷硬币猜正面的概率稍好，就是弱分类器。,集成,在分类时，采用投票的方式决定新样本属于哪一

11、类。由于每个分类器的分类能力不同，在集成时，需要对所有分类器加权平均，以决定分哪类。,为什么吸引人,弱分类器比强分类器设计简单以统计学习理论为基础,Vapnik的贡献,给出了可以指导机器学习算法设计的泛化理论。成为一种机器学习的规范。建立了从数据到分布的基本方法。以后机器学习的研究必须考虑从数据到分布的归纳机理问题。R,复杂数据分析,复杂数据分析的一般性说明符号机器学习,复杂数据分析-一类需求,机器学习研究方兴未艾，还有大量的理论与技术问题未解决。由于获得数据的手段的改善，在各行各业人们可以方便地获得越来越多的数据。但是，这些数据的积累也带来副作用，一方面，消耗大量资源，另一方面，无法使用的数

12、据，就是垃圾。另一个任务悄悄兴起，这就是复杂数据分析。,基于统计的数据分析不能满足需求,在某些行业，仅仅依赖积累的数据所建立的模型不能准确地预测未来。原因是：对大多数情况，积累的数据与未来将发生的事件不满足一致性假设，而是可能相差甚远。个别事件可能比统计显现的事件更为重要。,例如,零售业：积累的数据只能部分指导未来的进货策略与销售策略，特别是变化快的行业，例如，音像制品。电信业：对长久大户的特殊服务，对电信业至关重要。从海量数据中发现这些用户仅仅使用统计方法是不够的。情报分析：寻找不同常规行为的事件。,人们不相信模型,由于大多数数据集合不能满足一致性假设，使得人们可能不一定相信来自观测数据所建

13、立的模型。医疗诊断、零售业的各种问题、经济分析等专家系统所面临的问题就于此有关。,阅读数据的需求,“一致性假设”不满足，导致人们阅读数据的需求。人类阅读数据能力是有限的，需要计算机帮助。例如，在电信业、数据服务业、零售业、股票证券业，每天的数据量在106-8。假设每页A4有1000字符，这大约103-5页。假设人一分钟可以阅读一页，大约需要103-5分钟，16-1600小时，0.7-70天。对一定的需求，在保持需求信息不丢失的条件下，减少数据长度是阅读数据的必要条件。,未来十年关键性的研究课题,对大多数情况，一致性假设完全不能满足，甚至不能假设其近似满足。随着获得数据越来越容易，这个问题将越来

14、越突出。目前计算机90%的处理量是符号性的，只有10%是数值性的，未来的情况将可能与这类似。,复杂数据分析的要求,需要考虑每个被观测(积累)数据在这个领域中所扮演的角色。需要考虑不同用户在共享同一个数据集合的不同需求(包括解与解的长度)。传统的统计分析方法不能满足这些要求，需要研究观测数据的内在结构。这类研究也可以称为数据描述。,用户需求,对同一个数据集合，可能有不同的用户共享，而不同用户需要不同的解答。这与机器学习具有不同的目标。一般地说，机器学习以一个统计函数为目标，而数据描述则必须根据不同需求的前提下建立不同的目标。,应用领域,DNA功能分析。电信数据客户分析。金融、经济数据分析。图像数

15、据分析。文本分析。情报分析。等等。,符号与数值,对实际世界中某个事务，人们往往采用两种方式来描述：数值与语言(符号或概念)。颜色：赤橙黄绿青蓝紫，或光的波长。前者是语言性的，后者是数值性的。体温：发烧，或37度以上。,人类思考的语言倾向,事实上，在大多数情况下，人类的思考借助于语言或图像，而不是数值。,技术方法之一-符号机器学习,根据不同数据类型与不同需求，数据描述需要多种方法。来源于机器学习的方法是符号机器学习，它只能解决其中一部分问题。,基于符号机器学习的数据描述,可以分为三个步骤的过程：根据领域知识，从被直接观测的数值归纳(聚类)为符号(概念)。将这些符号构成的数据集合，约简为人可阅读的

16、规则集合(其长度必须满足特定用户的要求)。构成特定语言或图形文本，或添加不确定性描述。,符号机器学习,在上述过程中第二步的约简算法称为符号机器学习。其原始动机与统计机器学习完全相同，即泛化能力应该是其优劣的评价准则。但是，我们认为，它与统计机器学习不具有竞争力。它的优势在于符号信息的变换。,符号机器学习的历史,1959年Solomonoff关于文法归纳的研究应该是最早的符号机器学习。1967年Gold证明，这是不可能的实现的。,Samuel的贡献,六十年代末，Samuel将这类机器学习演变为一类基于符号数据集合的约简过程。这是符号机器学习的基础。,两类最重要的符号机器学习算法,覆盖算法与分治算

17、法。七十年代末，Michalski基于带等号的逻辑演算，提出了AQ11算法，称为符号机器学习的覆盖算法。1986年，Quinlan提出了决策树算法，也称为分治算法。,注释,决策树算法的优点是计算效率高。将决策树算法推广到C4.5，使其可以处理连续量。本质是将聚类与约简两个步骤合二为一。现已证明，可以建立与Vapnik理论类似的泛化理论。,符号机器学习优点,由于这类机器学习是将数据直接约简，因此，它的变换过程是透明的。过程可解释，结果与实际世界相对应，即，“白箱”。尽管其归纳的结果不一定具有对世界W的普适性，但是，它是给定数据集合在特定需求下的真实且简洁的映像。,描述,需要建立具有表示信息系统结

18、构的理论。以便可以对在信息系统中每个样本所扮演的角色进行分析。不能忽视任何样本所带给我们的信息，是这类问题的要点。,要点,矛盾样本可能比无矛盾样本带给我们更激动人心的信息。新知识来源于对矛盾的分析。,符号机器学习的基础-划分,机器学习的本质是对样本空间的划分。这需要定义一个等价关系，将样本空间划分为等价类。,等价关系的确定,由于符号机器学习的数据集合已被符号化，因此，符号机器学习所使用的等价关系可以事先确定。如果将符号化过程与约简过程合并，符号化过程可以理解为一类计算等价关系的过程。符号机器学习的理论对任何等价关系成立。,符号机器学习的等价关系,定义在给定符号对象集合U上的等价关系a(x,y)

19、:a(x)=a(y),x,yU,Rough Set理论,Pawlak在1982年提出的一种数学理论。这个理论包含了两个方面的内容：基于roughness测量的不精确知识表示理论。(与预测任务一致)约简理论与边缘理论。,知识表示理论,从字面上，rough set理论是一类与Fuzzy set类似的知识不精确表示理论。不幸的是，1996年，姚一豫教授证明，这类知识表示理论中的推理系统与模态逻辑的S5公理体系等价。因此，rough set理论的不精确知识表示似乎存在了问题。,约简理论与符号机器学习,可以证明：覆盖算法与约简理论等价。分治算法是在树表示条件下约简理论的一个特例。,Rough Set理论

20、的贡献,尽管所有符号机器学习的理论都是基于上述等价关系。但是，Rough Set理论提出了边缘区域的概念。在约简上，第一次给出了在结构上“非最小”解的精确数学定义-Reduct。Core的概念。,边缘区域,在信息系统中，所有存在矛盾的样本集合。如果C(x)=C(y)，但是，D(x)D(y)，x与y是样本集合中的矛盾对。,边缘区域的研究意义,边缘区域是信息系统矛盾样本的集合。Rough set理论第一次提供了我们研究矛盾信息结构的机会。,Reduct,是一个属性集合，当从这个集合中删除一个属性，则至少出现一个新的矛盾样本对。因此，它是在的不增加新矛盾对的最小属性集合。rR,POSR(D)POSR

21、-r(D),Reduct的意义,因为reduct空间是唯一的，因此，其任一reduct可以作为一种需求的解答。这个概念为我们根据用户不同需求选择不同解答提供了条件。,Core,是一个属性集合。如果删除一个这样的属性，必然出现一个新的样本矛盾对。反映了信息系统的本质。,Reduct and Core,对同一个信息系统，不同用户可能需要不简洁程度的文本。Reduct是最小属性集合，可以作为文本的基础。Core将成为形成简洁文本的关键。,性质,根据reduct可以建立一个新的信息系统，这个信息系统的所有属性是core。这个性质对形成不同简洁程度文本有重要的应用。,Rough Set理论是一种约简理论

22、。Rough set理论作为知识表示理论没有竞争性。Rough Set术语是历史的误会。,例子-“鸟”信息系统(赵岷),信息系统的语句集合,语言描述-1,The bird is the animal that can fly but is non-gregarious,or can fly and lay eggs,or can lay eggs and has lung and is gregarious.”,The sentence set with Penguin and Ostrich as exceptions,语言描述-2,The bird is the animal that c

23、an fly and lay eggs.Penguin and Ostrich are exceptions.,The sentence set with Penguin,Ostrich and Fruit bat as exceptions,语言描述-3,The bird is the animal that can fly.Penguin,Ostrich 是鸟，但是不会飞。Fruit bat 会飞，但是不是鸟。它们是上述规则的例外。,小结,描述任务需要了解每个样本个体意义，而预测任务需要了解样本集合整体的意义。符号机器学习的方法提供研究样本集合中个体的能力，是解决一类描述问题的有力工具。Rough set理论的边缘区域、Reduct and Core为我们提供了在以前研究中，从未提供的功能。,总结,四类机器学习是目前研究的主流。一些其他机器学习方法，正在等待时机，以期待重新兴起。需要更多的数学知识。简单的写程序的工作，将逐渐变为软件工人的事情。计算机科学家面临来自数学家与物理学家的严重生存挑战。,当务之急,补充数学也许是计算机科学研究者的当务之急。尽管数学不是万能的，但是没有数学是万万不能的！,谢 谢,