机器学习研究(王珏).ppt

机器学习研究,王 珏 中国科学院自动化研究所 2003年3月，北京，自动化所,反思,网络经济的泡沫破灭之后，哪些是值得我们在研究方向上反思的问题呢？ 我们的研究应注意哪些课题呢？,需求-NII计划,不分地域地、有效地获得与传输信息。 不分地域地、有效地共享硬软资源。 有效地利用信息，以提高生产率。 保证信息安全。,在过去的十年中，做了什么？,以浏览器为核心技术的“有效获得信息”的研究取得了预期效果。 人们已可以从不同地域有效地获得信息。 但是，,硬软资源的使用,在网络上的硬软资源的利用率只有3-5%。 大量计算资源没有由于网络设施的支持而被充分利用。 硬软件的快速更新，导致对环境的污染。,信息的有效使用,由于技术发展的滞后，在网络上获得的信息和与提高生产率有关的信息的有效使用率甚至低于1%。 占用大量硬软资源的信息正在大量地被浪费。,信息安全,信息的安全还没有保证。,提高信息使用率,以机器学习为理论基础的各种方法，是提高信息使用率的有效途径之一。,机器学习 复杂数据分析(符号机器学习),机器学习,机器学习的一般说明 统计机器学习 集成机器学习,机器学习的研究动力,领域应用驱动。 算法驱动。,领域应用驱动,自然语言数据分析。 DNA数据分析。 网络与电信数据分析。 图像数据分析。 金融与经济数据分析。 零售业数据分析。 情报分析。 没有一种算法可以解决复杂的实际问题。需要各种算法集成。,算法驱动,海量数据(108-10)。 算法的泛化能力，或算法可解释。 不同类型数据的学习方法。,机器学习研究热点的变迁,1989年(Carbonell), 1997年(Dietterich) 符号机器学习。 符号机器学习。 连接机器学习。 集成机器学习。 遗传机器学习。 统计机器学习。 分析机器学习。 增强机器学习。,机器学习计算的说明,令W是这个给定世界的有限或无限所有对象的集合，由于我们观察能力的限制，我们只能获得这个世界的一个有限的子集QW。 机器学习的任务就是根据这个世界的对象子集Q，计算这个世界的统计分布。这样，在统计意义下，这个分布对这个世界的绝大多数对象是正确的。这就是这个世界的一个模型。,三个要求,一致性假设：机器学习任务的本质。 对样本空间的划分：决定对样本的有效性。 泛化能力：决定对世界的有效性。,一致性假设,假设世界W与被观察的对象集合Q具有某种相同的性质。 称为一致性假设。,基于统计的假设,原则上说，存在各种各样的一致性假设。 在统计意义下，一般假设： W与Q具有同分布。或， 给定世界W的所有对象独立同分布。,划分,将被观测的对象集合放到一个n维欧氏空间，寻找一个超平面，使得问题决定的不同对象分在不相交的区域。 机器学习主要研究的是这部分内容，即，寻找划分对象集合的超平面(等价关系)。,超平面类型,光滑且连续的超平面。 有限不光滑点，甚至有限不连续点的超平面。,光滑连续超平面作为研究基础,Perceptron，人工神经网络是典型例子。 困难： 对线性不可分的对象集合，如果限制算法是P的，则存在本质性困难。,泛化,机器学习的首要任务是划分。只有找到一个等价关系(模型)，将不同类的样本划分为不同的类，才能考虑其他问题。 泛化是一个确定的划分对世界的分类能力。 由于可能存在不同的划分样本集合方法，其泛化能力不同，泛化能力最强的划分就是我们希望的分类器。,Duda的泛化能力描述,以样本个数趋近无穷大来描述模型的泛化能力。 泛化能力需要使用世界W来刻画，是无法构造的判据。 均方差可作为目标函数。,评述,由于人们没有找到基于样本集合Q的描述泛化能力的数学工具。另外，线性不可分问题是一个困难。 在感知机时代，基于Duda泛化理论无法指导机器学习算法的设计，这样，评价机器学习算法只能以划分能力作为指标。 Vapnik对这个问题做出重要贡献。 这样，注重从划分变为泛化。,以划分能力为目标的研究,这类研究的指导思想，一直延续到上个世纪的九十年代。 直到今天，还有大量的学者以此作为机器学习的指导思想。以BP算法为核心的神经网络研究是典型例子。 划分是机器学习的一个目标，但是，不是预测任务的主要研究目标。,神经网络-BP算法,使用了一种非线性的基函数。 这项研究的意义是为研究者回归感知机做好了舆论的准备。 其在科学上的意义，远不如提示人们再次注意感知机的作用更大。,统计机器学习理论与SVM,对机器学习的研究者来说，统计机器学习理论所派生的算法SVM似乎更有吸引力。 但是，如果研究者忘记SVM所基于的统计基础，就与Vapnik的本意相悖了。 事实上，Vapnik的统计理论才是其精华，而基于这个理论的算法只是从这个统计理论派生的自然结果。,机器学习的统计假设,机器学习的统计基础是基于经验风险最小假设，以此，对机器学习算法所建模型的泛化能力估计(经验风险)。,Vapnik的统计观点,Vapnik希望改变Duda的统计观点。 泛化描述“从样本数趋于无穷大”变为“在给定样本集”基础上判定。 由此，建立基于样本集合结构的VC维来描述的理论。 这样，机器学习的目标函数就可以建立在样本集合的结构之上。 这是统计机器学习理论的精髓。,泛化能力,以下不等式依概率1-成立： R: 包含所有样本的球半径 M: 边缘 l: 样本个数,泛化不等式的解释,M0，边缘不能等于零。这意味着，样本集合必须是可划分的。 边缘最大，泛化能力最强。泛化能力可以使用样本集合的边缘来刻画。 泛化能力的描述无需使用世界W来刻画，而只需样本集合Q来刻画。,泛化能力的几何解释(示意图),线性可分问题,定理： 如果一个样本集合是线性可分的，它们一定可以构成两个不相交的闭凸集。 这样，线性可分问题变为计算两个闭凸集的最大边缘问题。,线性不可分问题,划分问题：怎样获得两个不相交的闭凸集。 泛化问题：怎样使两个闭凸集之间的距离最大。,核技术,可以证明，一定存在一个映射，称为核函数，将在欧式空间定义的样本映射到特征空间(一个更高维的空间)，使得在特征空间上，样本构成两个不相交的闭凸集。 研究核函数选择的技术称为核技术。,SVM,给定核函数，如果它可以保证将样本集合在特征空间变换为两个不相交的闭凸集，则对这个样本集合的最大边缘可以通过二次规划、计算几何等方法获得。由此，可以获得支持向量。 这就是SVM。,未解决的问题,在特征空间样本集合是否可以划分为不相交的闭凸集，决定于核函数的选择。 最大边缘尽量大，也决定于核函数的选择。 核函数的选择没有一般的方法。 准确地说，加大特征空间维数是一个方法，确定最小维数没有P算法。,解决线性不可分问题的方法,核函数选择的困难可能是根本性的。 技术措施：同时考虑不满足一致性假设的情况。 软边缘。 集成机器学习。,两类技术措施的统计解释,目的是解决样本集合不满足一致性假设，采用不确定性来补充，以使得模型与实际世界的统计分布一致。 措施： 软边缘：将边缘改为软性(有个范围)，以适应需要。 集成机器学习：多个分类器集成，以使用不同模型补充一个模型的不足。,集成机器学习动机,弱分类器设计简单。 在理论上似乎与Madaline类似。,集成机器学习,1990年Shapire证明，如果将多个弱分类器集成在一起，它将具有强分类器的泛化能力。 进而，又说明，这类集成后的强分类器具有统计学习理论的基础。,弱分类器,如果一个分类器的分类能力(泛化)稍大于50%，这个分类器称为弱分类器。 这意味着，比掷硬币猜正面的概率稍好，就是弱分类器。,集成,在分类时，采用投票的方式决定新样本属于哪一类。 由于每个分类器的分类能力不同，在集成时，需要对所有分类器加权平均，以决定分哪类。,为什么吸引人,弱分类器比强分类器设计简单 以统计学习理论为基础,Vapnik的贡献,给出了可以指导机器学习算法设计的泛化理论。 成为一种机器学习的规范。 建立了从数据到分布的基本方法。 以后机器学习的研究必须考虑从数据到分布的归纳机理问题。 R,复杂数据分析,复杂数据分析的一般性说明 符号机器学习,复杂数据分析-一类需求,机器学习研究方兴未艾，还有大量的理论与技术问题未解决。 由于获得数据的手段的改善，在各行各业人们可以方便地获得越来越多的数据。但是，这些数据的积累也带来副作用，一方面，消耗大量资源，另一方面，无法使用的数据，就是垃圾。 另一个任务悄悄兴起，这就是复杂数据分析。,基于统计的数据分析不能满足需求,在某些行业，仅仅依赖积累的数据所建立的模型不能准确地预测未来。 原因是：对大多数情况， 积累的数据与未来将发生的事件不满足一致性假设，而是可能相差甚远。 个别事件可能比统计显现的事件更为重要。,例如,零售业：积累的数据只能部分指导未来的进货策略与销售策略，特别是变化快的行业，例如，音像制品。 电信业：对长久大户的特殊服务，对电信业至关重要。从海量数据中发现这些用户仅仅使用统计方法是不够的。 情报分析：寻找不同常规行为的事件。,人们不相信模型,由于大多数数据集合不能满足一致性假设，使得人们可能不一定相信来自观测数据所建立的模型。 医疗诊断、零售业的各种问题、经济分析等专家系统所面临的问题就于此有关。,阅读数据的需求,“一致性假设”不满足，导致人们阅读数据的需求。 人类阅读数据能力是有限的，需要计算机帮助。 例如，在电信业、数据服务业、零售业、股票证券业，每天的数据量在106-8。 假设每页A4有1000字符，这大约103-5页。 假设人一分钟可以阅读一页，大约需要103-5分钟，16-1600小时，0.7-70天。 对一定的需求，在保持需求信息不丢失的条件下，减少数据长度是阅读数据的必要条件。,未来十年关键性的研究课题,对大多数情况，一致性假设完全不能满足，甚至不能假设其近似满足。 随着获得数据越来越容易，这个问题将越来越突出。 目前计算机90%的处理量是符号性的，只有10%是数值性的，未来的情况将可能与这类似。,复杂数据分析的要求,需要考虑每个被观测(积累)数据在这个领域中所扮演的角色。 需要考虑不同用户在共享同一个数据集合的不同需求(包括解与解的长度)。 传统的统计分析方法不能满足这些要求，需要研究观测数据的内在结构。 这类研究也可以称为数据描述。,用户需求,对同一个数据集合，可能有不同的用户共享，而不同用户需要不同的解答。 这与机器学习具有不同的目标。 一般地说，机器学习以一个统计函数为目标，而数据描述则必须根据不同需求的前提下建立不同的目标。,应用领域,DNA功能分析。 电信数据客户分析。 金融、经济数据分析。 图像数据分析。 文本分析。 情报分析。等等。,符号与数值,对实际世界中某个事务，人们往往采用两种方式来描述：数值与语言(符号或概念)。 颜色：赤橙黄绿青蓝紫，或光的波长。前者是语言性的，后者是数值性的。 体温：发烧，或37度以上。,人类思考的语言倾向,事实上，在大多数情况下，人类的思考借助于语言或图像，而不是数值。,技术方法之一-符号机器学习,根据不同数据类型与不同需求，数据描述需要多种方法。 来源于机器学习的方法是符号机器学习，它只能解决其中一部分问题。,基于符号机器学习的数据描述,可以分为三个步骤的过程： 根据领域知识，从被直接观测的数值归纳(聚类)为符号(概念)。 将这些符号构成的数据集合，约简为人可阅读的规则集合(其长度必须满足特定用户的要求)。 构成特定语言或图形文本，或添加不确定性描述。,符号机器学习,在上述过程中第二步的约简算法称为符号机器学习。 其原始动机与统计机器学习完全相同，即泛化能力应该是其优劣的评价准则。 但是，我们认为，它与统计机器学习不具有竞争力。 它的优势在于符号信息的变换。,符号机器学习的历史,1959年Solomonoff关于文法归纳的研究应该是最早的符号机器学习。 1967年Gold证明，这是不可能的实现的。,Samuel的贡献,六十年代末，Samuel将这类机器学习演变为一类基于符号数据集合的约简过程。这是符号机器学习的基础。,两类最重要的符号机器学习算法,覆盖算法与分治算法。 七十年代末，Michalski基于带等号的逻辑演算，提出了AQ11算法，称为符号机器学习的覆盖算法。 1986年，Quinlan提出了决策树算法，也称为分治算法。,注释,决策树算法的优点是计算效率高。 将决策树算法推广到C4.5，使其可以处理连续量。本质是将聚类与约简两个步骤合二为一。 现已证明，可以建立与Vapnik理论类似的泛化理论。,符号机器学习优点,由于这类机器学习是将数据直接约简，因此，它的变换过程是透明的。 过程可解释，结果与实际世界相对应，即，“白箱”。 尽管其归纳的结果不一定具有对世界W的普适性，但是，它是给定数据集合在特定需求下的真实且简洁的映像。,描述,需要建立具有表示信息系统结构的理论。 以便可以对在信息系统中每个样本所扮演的角色进行分析。 不能忽视任何样本所带给我们的信息，是这类问题的要点。,要点,矛盾样本可能比无矛盾样本带给我们更激动人心的信息。 新知识来源于对矛盾的分析。,符号机器学习的基础-划分,机器学习的本质是对样本空间的划分。 这需要定义一个等价关系，将样本空间划分为等价类。,等价关系的确定,由于符号机器学习的数据集合已被符号化，因此，符号机器学习所使用的等价关系可以事先确定。 如果将符号化过程与约简过程合并，符号化过程可以理解为一类计算等价关系的过程。 符号机器学习的理论对任何等价关系成立。,符号机器学习的等价关系,定义在给定符号对象集合U上的等价关系a (x, y) : a(x)=a(y), x, yU,Rough Set理论,Pawlak在1982年提出的一种数学理论。 这个理论包含了两个方面的内容： 基于roughness测量的不精确知识表示理论。(与预测任务一致) 约简理论与边缘理论。,知识表示理论,从字面上，rough set理论是一类与Fuzzy set类似的知识不精确表示理论。 不幸的是，1996年，姚一豫教授证明，这类知识表示理论中的推理系统与模态逻辑的S5公理体系等价。 因此，rough set理论的不精确知识表示似乎存在了问题。,约简理论与符号机器学习,可以证明： 覆盖算法与约简理论等价。 分治算法是在树表示条件下约简理论的一个特例。,Rough Set理论的贡献,尽管所有符号机器学习的理论都是基于上述等价关系。但是， Rough Set理论提出了边缘区域的概念。 在约简上，第一次给出了在结构上“非最小”解的精确数学定义-Reduct。 Core的概念。,边缘区域,在信息系统中，所有存在矛盾的样本集合。 如果C(x)=C(y)，但是，D(x)D(y)，x与y是样本集合中的矛盾对。,边缘区域的研究意义,边缘区域是信息系统矛盾样本的集合。 Rough set理论第一次提供了我们研究矛盾信息结构的机会。,Reduct,是一个属性集合，当从这个集合中删除一个属性，则至少出现一个新的矛盾样本对。 因此，它是在的不增加新矛盾对的最小属性集合。 rR, POSR(D)POSR-r(D),Reduct的意义,因为reduct空间是唯一的，因此，其任一reduct可以作为一种需求的解答。 这个概念为我们根据用户不同需求选择不同解答提供了条件。,Core,是一个属性集合。 如果删除一个这样的属性，必然出现一个新的样本矛盾对。 反映了信息系统的本质。,Reduct and Core,对同一个信息系统，不同用户可能需要不简洁程度的文本。 Reduct是最小属性集合，可以作为文本的基础。 Core将成为形成简洁文本的关键。,性质,根据reduct可以建立一个新的信息系统，这个信息系统的所有属性是core。 这个性质对形成不同简洁程度文本有重要的应用。,Rough Set理论是一种约简理论。 Rough set理论作为知识表示理论没有竞争性。 Rough Set术语是历史的误会。,例子-“鸟”信息系统(赵岷),信息系统的语句集合,语言描述-1,The bird is the