机器学习及其应用

1、1机器学习研究进展及其应用2012年10月25日2内容机器学习的意义机器学习的基本概念机器学习的基本认知与发展趋势统计机器学习的基本方法总结典型机器学习开发包3机器学习是人工智能的核心研究领域之一经典定义：利用经验改善系统自身的性能随着该领域的发展，主要做智能数据分析典型任务：根据现有数据建立预测模型机器学习4生物信息学计算金融学分子生物学行星地质学工业过程控制机器人遥感信息处理信息安全机 器 学 习机器学习的重要性5机器学习的重要性美国航空航天局JPL实验室的科学家在Science（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，该领域在今后的若干年内将取得

2、稳定而快速的发展6入侵检测：是否是入侵？是何种入侵？如何检测？历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现对当前访问模式分类这是一个典型的机器学习问题常用技术：神经网络 决策树支持向量机 贝叶斯分类器k近邻 序列分析 聚类 例1:网络安全7常用技术：神经网络 支持向量机隐马尔可夫模型贝叶斯分类器 k近邻决策树 序列分析 聚类 例2:生物信息学8例3:计算语言学常用技术：神经网络 隐马尔可夫模型贝叶斯分类器 决策树序列分析 聚类 9Google的成功，使得Internet 搜索引擎成为一个新兴的产业不仅有众多专营搜索引擎的公司出现（例如专门针对中文搜索的就有百度、慧聪等），而且M

3、icrosoft等巨头也开始投入巨资进行研发Google掘到的第一桶金，来源于其创始人Larry Page和Sergey Brin提出的PageRank算法机器学习技术正在支撑着各类搜索引擎例4:搜索引擎10例5:色彩空间转换常用技术：神经网络 支持向量机隐马尔可夫模型贝叶斯分类器 聚类 11DARPA 2003年开始启动PAL（Perceptive Assistant that Learns）计划5年期，首期（1-1.5年）投资2千9百万美元以机器学习为核心的计划（涉及到AI的其他分支，如知识表示和推理、自然语言处理等）；包含2个子计划总目标：“is expected to yield ne

4、w technology of significant value to the military, business, and academic sectors” “develop software that will help decision-makers manage their complex worlds of multiple simultaneous tasks and unexpected events”美国的PAL计划12RADAR (Reflective Agents with Distributed Adaptive Reasoning)，承担单位为CMU， 首期7百万

5、美元目标：“the system will help busy managers to cope with time-consuming tasks” “RADAR must learn by interacting with its human master and by accepting explicit advice and instruction”美国的PAL计划: RADAR子计划13CALO (Cognitive Agent that Learns and Observes)， 承担单位为SRI，首期2200万美元除SRI外，这个子计划的参加单位有20家：Boeing, CMU,

6、 Dejima Inc., Fetch Tech Inc., GATech, MIT, Oregon HSU, Stanford, SUNY-Stony Brook, UC Berkeley, UMass, UMich, UPenn, Rochester, USC, UT Austin, UW, Yale, CALO无疑是PAL中更核心的部分美国的PAL计划: CALO子计划(1)14目标： “the name CALO was inspired by the Latin word calonis, which means soldiers assistant” “the CALO softw

7、are, which will learn by working with and being advised by its users, will handle a broad range of interrelated decision-making tasks It will have the capability to engage in and carry out routine tasks, and to assist when the unexpected happens”从CALO的目标来看，DARPA已经开始把机器学习技术的重要性放到了国家安全的角度来考虑美国的PAL计划:

8、CALO子计划(2)15美国的PAL计划: CALO子计划(3)重要性计算机科学在过去十年中发展极为迅速，今后会快速稳定地发展、对科学做出更大贡献的领域E.Mjolsness & D. DesCoste, Science 01人工智能中最活跃、应用潜力最明显的领域（之一）T.G. Dietterich, AIMag 97美国、欧洲各国都投入了大量人力物力大型公司如波音、微软、通用电器等都有研究课题已有一些研究成果进入产品17内容机器学习的意义机器学习的基本概念机器学习的基本认知与发展趋势统计机器学习的基本方法总结典型机器学习开发包机器学习智能系统：需要具有学习能力。例如，遇到错误时能自我校正；

9、会通过经验改善自身的性能；会自动获取和发现所需要的知识。基本特征：自适应：根据数据自动调整参数自组织：根据数据自动确定组织规则自推理：根据已有数据和规则能发现新的定理、定律和规则应用：如专家系统、自动推理、自然语言理解、模式识别、计算机视觉、智能机器人等领域。其中尤其典型的是专家系统中的知识获取瓶颈问题，人们一直在努力试图采用机器学习的方法加以克服。 2.1机器学习的定义和发展历史机器学习的基本概念： 按照人工智能大师西蒙的观点，学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。机器学习的定义 机器学习是研究如何使用机

10、器来模拟人类学习活动的 一门学科。稍为严格的提法是：机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。机器学习根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。机器学习问题的表示根据n个独立同分布观测样本确定预测函数f(x,w)。在一组函数f(x,w)中求一个最优的函数f(x,w0)对依赖关系进行估计，使预测的期望风险最小。环境学习环节知识库执行环节Simon的学习模型2.1机器学习的定义和发展历史学习问题的一般表示学习目标Given an i.i.d. l-sample z1,zl drawn from a fixed distri

11、bution F(z)For a function class loss functions Q(z,), with in We wish to minimize the risk, finding a function *In the case of equal risk, it becomes to minimize the error ratio.相关概念损失函数 loss function (L, Q)：the error of a given function on a given example风险函数risk functional (R)：the expected loss of

12、 a given function on an example drawn from F(x,y) 2.1机器学习的定义和发展历史学习问题的一般表示学习的目的在于使期望风险最小化。由于可利用的信息只有样本，期望风险往往无法计算。经验风险最小化归纳原则 (The Empirical Risk Minimization (ERM) Inductive Principle)核心思想：用样本定义经验风险。Define the empirical risk (sample/training error):Define the empirical risk minimizer:Least-squares

13、and Maximum-likelihood are realisations of ERM2.1机器学习的定义和发展历史Learning as a Search Problem2.1机器学习的定义和发展历史机器学习是人工智能应用研究较为重要的分支，它的发展过程大体上可分为4个时期：1.第一阶段是在50年代中叶到60年代中叶，属于热烈时期。2.第二阶段在60年代中叶至70年代中叶，被称为机器学习的冷静时期。3.第三阶段从70年代中叶至80年代中叶，称为复兴时期。4.机器学习的最新阶段始于1986年。一方面，由于神经网络研究的重新兴起，另一方面，对实验研究和应用研究得到前所未有的重视。我国的机器

14、学习研究开始进入稳步发展和逐渐繁荣的新时期。2.1机器学习的定义和发展历史机器学习进入新阶段的表现机器学习已经成为新的边缘学科并在高校形成课程综合各种学习方法机器学习与人工智能的统一性观点正在形成各种学习方法的应用范围不断扩大数据挖掘和知识发现的研究已经形成热潮与机器学习有关的学术活动空前活跃2.1机器学习的定义和发展历史2.2机器学习的基本结构基本结构 环境向系统的学习部分提供某些信息，学习部分利用这些信息修改知识库，以增进系统执行部分完成任务的效能，执行部分根据知识库完成任务，同时把获得的信息反馈给学习部分。 在具体的应用中，环境，知识库和执行部分决定了具体的工作内容，学习部分所需要解决的

15、问题完全由上述3部分确定。影响学习系统设计的重要因素影响学习系统设计的最重要的因素是环境向系统提供的信息。或者更具体地说是信息的质量。样本的质量知识库里存放的是指导执行部分动作的一般原则，但环境向学习系统提供的信息却是各种各样的。如果信息的质量比较高，则学习部分比较容易处理。如果向学习系统提供的是杂乱无章的指导执行具体动作的具体信息，则学习系统需要在获得足够数据之后，删除不必要的细节，进行总结推广，形成指导动作的一般原则，放入知识库，这样学习部分的任务就比较繁重，设计起来也较为困难。2.2机器学习的基本结构2.3机器学习分类基于学习策略的分类学习策略是指学习过程中系统所采用的推理策略。学习系统

16、的主体总是由学习和环境两部分组成。由环境（如书本或教师）提供信息，学习部分则实现信息转换，用能够理解的形式记忆下来，并从中获取有用的信息。在学习过程中，学习主体使用的推理越少，其对环境的依赖就越大，环境的负担也就越重。学习策略的分类标准就是根据学习主体实现信息转换所需的推理多少和难易程度来分类的，依从简单到复杂，从少到多的次序分为以下六种基本类型：机械学习(Rote learning) 学习者无需任何推理或其它的知识转换，直接吸取环境所提供的信息。如塞缪尔的跳棋程序，这类学习系统主要考虑的是如何索引存贮的知识并加以利用。系统的学习方法是直接通过事先编好、构造好的程序来学习，学习者不作任何工作，

17、或者是通过直接接收既定的事实和数据进行学习，对输入信息不作任何的推理。2.3机器学习分类 学生从环境（教师或其它信息源如教科书等）获取信息，把知识转换成内部可使用的表示形式，并将新的知识和原有知识有机地结合为一体。所以要求学生有一定程度的推理能力，但环境仍要做大量的工作。教师以某种形式提出和组织知识，以使学生拥有的知识可以不断地增加。这种学习方法和人类社会的学校教学方式相似，学习的任务就是建立一个系统，使它能接受教导和建议，并有效地存贮和应用学到的知识。目前，不少专家系统在建立知识库时使用这种方法去实现知识获取。2.3机器学习分类示教学习(Learning from instruction)

18、学生所用的推理形式为演译推理。推理从公理出发，经过逻辑变换推导出结论。这种推理是“保真”变换和特化(specialization)的过程，使学生在推理过程中可以获取有用的知识。 演绎推理的逆过程是归纳推理。演绎学习(Learning by deduction)2.3机器学习分类 利用二个不同领域（源域、目标域）中的知识相似性，可以通过类比，从源域的知识（包括相似的特征和其它性质）推导出目标域的相应知识，从而实现学习。类比学习系统可以使一个已有的计算机应用系统转变为适应于新的领域，来完成原先没有设计的相类似的功能。类比学习需要比上述三种学习方式更多的推理。 一般要求先从知识源（源域）中检索出可用

19、的知识，再将其转换成新的形式，用到新的状况（目标域）中去。类比学习在人类科学技术发展史上起着重要作用，许多科学发现就是通过类比得到的。例如著名的卢瑟福类比就是通过将原子结构（目标域）同太阳系（源域）作类比，揭示了原子结构的奥秘。2.3机器学习分类类比学习(Learning by analogy) 学生根据教师提供的目标概念、该概念的一个例子、领域理论及可操作准则，首先构造一个解释来说明为什该例子满足目标概念，然后将解释推广为目标概念的一个满足可操作准则的充分条件。EBL已被广泛应用于知识库求精和改善系统的性能。2.3机器学习分类基于解释的学习(Explanation-based learnin

20、g) 归纳学习是由教师或环境提供某概念的一些实例或反例，让学生通过归纳推理得出该概念的一般描述。这种学习的推理工作量远多于示教学习和演绎学习，因为环境并不提供一般性概念描述（如公理）。从某种程度上说，归纳学习的推理量也比类比学习大，因为没有一个类似的概念可以作为源概念加以取用。归纳学习是最基本的，发展也较为成熟的学习方法，在人工智能领域中已经得到广泛的研究和应用。归纳学习(Learning from induction)2.3机器学习分类依学习策略从简单到复杂的次序分为六种基本类型：1）机械学习(Rote learning)2）示教学习(Learning from instruction)3）

21、演绎学习(Learning by deduction)4）类比学习(Learning by analogy)5）基于解释的学习(Explanation-based learning)6）归纳学习(Learning from induction)2.3机器学习分类智能信息处理的瓶颈知识获取机器学习能够通过对数据及其关系的分析，提取出隐含在海量数据中的知识2.4知识发现知识发现的发展和定义 1.知识发现的产生和发展知识发现最早是于1989年8月在第11届国际人工智能联合会议的专题讨论会上提出。随着互联网的发展，网上已设立了不少研究KDD的网站、论坛和新闻报导。在研究的基础上，也出现一些KDD产品和

22、应用系统，引起企业界的关注。2.定义数据库中的知识发现是从大量数据中辨识出有效的、新颖的、潜在有用的、并可被理解的模式的高级处理过程。2.4知识发现数据集：是指一个有关事实F的集合，它是用来描述事物有关方面的信息，是进一步发现知识的原材料。新颖：经过知识发现提取出的模式必须是新颖的。潜在有用：提取出的模式应该是有意义的，这可以通过某些函数的值来衡量。可被人理解：知识发现的一个目标就是将数据库中隐含的模式以容易被人理解的形式表现出来，从而帮助人们更好地了解数据库中所包含的信息。模式高级过程2.4知识发现知识发现的处理过程数据选择：根据用户的需求从数据库中提取与KDD相关的数据。数据预处理：主要是

23、对上述数据进行再加工，检查数据的完整性及数据的一致性，对丢失的数据利用统计方法进行填补，形成发掘数据库。数据变换：即从发掘数据库里选择数据。数据挖掘：根据用户要求，确定KDD的目标是发现何种类型的知识。知识评价：这一过程主要用于对所获得的规则进行价值评定，以决定所得的规则是否存入基础知识库。 可归纳为三个步骤，即数据挖掘预处理、数据挖掘、数据挖掘后处理。 2.4知识发现知识发现的方法统计方法统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。机器学习方法(1) 规则归纳。规则反映数据项中某些属性或数据集中某些数据项之间的统计相关性。(2) 决策树。决策树的每一个非终叶节点表示所考虑的数

24、据项的测试或决策。(3) 范例推理。范例推理是直接使用过去的经验或解法来求解给定的问题。(4) 贝叶斯信念网络。贝叶斯信念网络是概率分布的图表示。(5) 科学发现。科学发现是在实验环境下发现科学定律。(6) 遗传算法。在求解过程中，通过最好解的选择和彼此组合，使期望解的集合愈来愈好。神经计算方法可视化方法可视化（visualization）就是把数据、信息和知识转化为可视的表示形式的过程。2.4知识发现知识发现的应用知识发现已在许多领域得到应用，且应用领域越来越广。现在，知识发现已在银行业、保险业、零售业、医疗保健、工程和制造业、科学研究、卫星观察和娱乐业等行业和部门得到成功应用，为人们的科学

25、决策提供很大帮助。 2.4知识发现42内容机器学习的意义机器学习的基本概念机器学习的基本认知与发展趋势统计机器学习的基本方法总结典型机器学习开发包433 机器学习的基本认知与发展趋势机器学习的一般说明机器学习发展中的重要结果近期机器学习的发展趋势机器学习研究中的难题注：本节部分内容引自中国科学院研究生院王珏机器学习研究第一讲443.1机器学习的一般说明基本假设：假设y=F(x)是问题世界的模型，z=N(x)是观测环境噪音，样本集是在噪音环境下，经过有限次观察，从问题世界获得的一组观测数据，记为，S(z, xk, yk)。它是问题世界所有可能观测数据的一个子集。几乎所有经典机器学习算法需要满足这

26、个基本假设经典机器学习的基本假设453.1机器学习的一般说明机器学习：从样本集S(z, xk, yk)学习(估计)一个假设f(x)，使得f(x)是问题世界模型F(x)的一个近似。机器学习的任务：从S计算一个f(x)，使得在输入输出意义下逼近F(x)。过滤观测环境附加在数据上的噪音。经典机器学习的基本任务463.1机器学习的一般说明样本集仅仅是定义在确定问题世界上的特例，除了独立于问题世界的观测噪音，不包含其他信息（精心设计实验）。数据单纯解答是问题世界的近似，即，对特定目标过滤噪音后的最优解（建模与过滤）。样本集是从确定问题世界获得，是在统计意义下可以覆盖问题世界的特例集合（数量与分布）。样本

27、稠密解答最优样本集格式标准，可使用命题形式表述。格式标准对经典机器学习假设的解释47机器学习方法3.1机器学习的一般说明涉及下述三个要素： (1)观测对象；(2)观测对象构成的样本集合。(3)获得模型。483.1机器学习的一般说明对 象对问题世界的一次观察的记录，称为这个问题世界中的一个对象。样本集合令W是问题世界的有限或无限所有对象的集合，由于我们观察能力的限制，我们只能获得这个世界的一个有限的子集QW，称为样本集(训练集)。493.1机器学习的一般说明机器学习的说明机器学习就是根据样本集，推算这个世界的模型，使其对这个世界W在一定概率下为真。503.1机器学习的一般说明“模型”的注释数学模

28、型：黑箱方法(机器学习)。物理模型：白箱方法。其区别：(1)更为简洁且模型的每个部分与物理世界相对应。(2)对世界确定为真。513.1机器学习的一般说明“说明”暗示的三个问题一致性假设：机器学习的条件。建立模型：决定模型对样本集合的有效性。泛化能力：决定模型对世界的有效性。523.1机器学习的一般说明三个问题一致性假设建立模型泛化能力假设世界W与样本集Q有相同的性质。例如，iid条件。原则上，存在各种一致性假设。假设一个基函数，计算其参数，获得对样本集合的模型，使得模型对给定目标函数误差最小。从有限样本集合，计算一个模型，泛化能力是这个模型对世界为真程度的指标。533.1机器学习的一般说明建立

29、模型的问题分类问题算法基础：样本集放到n维空间，找一个决策分界面，使得问题决定的不同对象分在不相交的区域。假设从样本集合估计的模型为Y=f(X)。Y定义的空间不同将导致完全不同的学习类型。回归问题算法基础：样本集放到一个n维空间，计算一个曲面，使得所有对象与这个曲面的距离之和最小。Y定义为空集： 无监督学习。Y定义为有限整数集：分类学习。Y定义为实数域： 回归学习。Y定义为有缺损： 半监督学习。Y定义为序集合： Learning for Ranking。543.1机器学习的一般说明不同时期，关注不同早期研究主要集中在建立模型上近期的研究，在考虑高效建立模型(多项式算法)的基础上，要求模型必须满

30、足泛化能力的条件未来的研究，必须考虑一致性假设553.2机器学习发展中的重要结果机器学习的神经科学基础19世纪末，James的神经系统结构。20世纪中期，McCulloch和Pitts的神经元工作方式。20世纪中期，Hebb的学习律。563.2机器学习发展中的重要结果James对计算的意义神经系统的结构：神经元是互相连接。这个事实使得我们可以建立基于神经系统机器学习的的数学模型。Y=WX其中，X是多个神经元的输入矢量，Y是神经元输出，W是输入与输出神经元之间联结强度的矢量(矩阵)。573.2机器学习发展中的重要结果MP对计算的意义神经元的工作方式是“兴奋”和“抑制”。这个发现不仅对神经科学有重

31、要的科学意义，而且是近代技术的科学基础，特别是计算机科学，0与1表示就受启于此。由此，机器学习模型变为：Y=sign(WX)583.2机器学习发展中的重要结果Hebb对计算的意义如果两个神经元之间的连接对正确识别有利，增强其连接强度(w0)，反之，减弱其连接强度(w0，边缘不能等于零。这意味着，样本集合必须是可划分的。边缘最大，误差界最小，泛化能力最强。泛化能力可以使用样本集合的边缘刻画这个不等式依赖于边缘M。贡献：给出了有几何直观的界描述，从而为算法设计奠定基础3.3近年机器学习的发展趋势在算法设计上，我们的进步是什么？Duda条件样本、属性独立同分布数据模型形式确定Vapnik条件样本、属

32、性独立同分布数据模型形式不确定(有限样本)这就是我们的进步？！我们有效利用了这个进步吗？我们利用库函数计算高斯类核映射时，“进步”化为乌有！边缘计算使得算法设计不必局限在代数方法上，直观的几何方法可以成为其基础。另外，核映射方法可以部分纠正领域知识使用的随意性。这些就是最重要的进步。3.3近年机器学习的发展趋势定理：如果一个概念是弱可学习的，充要条件是它是强可学习的这个定理证明是构造性的，派生了弱分类器的概念，即，比随机猜想稍好的分类器这个定理说明： 多个弱分类器可以集群为一个强分类器1990年，Schapire证明了一个定理，由此，奠定了集群机器学习的理论基础弱分类器理论3.3近年机器学习的

33、发展趋势 设D是原始样本集合（1）从D中选取子集D1,根据D1训练第一个分类器C1,只需其是一个弱分类器。（2)抛硬币决定第二个样本集D2.如果是正面，选取D 中剩余的样本用C1分类，一个被错分的样本加入D2；如果是反面，则选取一个被C1正确分类样本。这样，D2中一定在概率上有一半的样本可以被C1正确分类，而另一半被C1错误分类。然后，利用D2训练一个新的分类器C2.(3)构造第三个样本D3.在D剩余的样本中选取样本，用C1和C2进行分类，如果C1和C2的分类结果不同，则把这个样本加入D3,否则忽略此样本。使用D3训练新的分类器C3.递归地使用上述三个步骤.弱分类器的构造过程 3.3近年机器学

34、习的发展趋势理论问题驱动3.3近年机器学习的发展趋势表示问题：某个问题世界已被我们认识，即找到了一个空间，这个问题世界可以在这个空间上线性表示。泛化问题：某个算法保证从有限数据集合建立的模型，在一定概率意义下，对问题世界为真。先验知识问题：没有免费的午餐！不能指望存在对所有问题世界普适的一般方法。快速计算问题：数学工具的选择。“拓扑(划分)”保证对数据内在结构的刻画，“距离”保证局部的计算。先验知识必要性：维数灾难。方法：拍脑袋方法(经验)对给定问题，寻找领域专家，请求这些专家提供他们的经验，以获得知识。数据分析方法(数学)根据统计理论，对给定数据集合分析，给出合理的对特定数据集合有益的知识。

35、尽管这是令计算机科学家相当厌恶的方法，但是，有时，我们不得不承认其有效性。3.3近年机器学习的发展趋势统计建模的两种文化2001年，UC Berkeley的Leo Breiman在Statistical Science上发表了一篇文章，“Statistical Modeling: The Two Cultures”数据建模文化：经典统计分析，98%赞同。算法建模文化：机器学习，2%赞同。 3.3近年机器学习的发展趋势说 明文章的本意是向统计学家呼吁，鉴于各个领域对问题世界模型的关注，请他们关注统计建模的算法文化。我们的思考是：两种文化的融合可能更为重要，其关键原因是，统计建模的算法文化受到维数

36、灾难的约束，它不得不求助于统计建模的数据文化，以获得先验知识。3.3近年机器学习的发展趋势理论问题驱动3.3近年机器学习的发展趋势表示问题：某个问题世界已被我们认识，即找到了一个空间，这个问题世界可以在这个空间上线性表示。泛化问题：某个算法保证从有限数据集合建立的模型，在一定概率意义下，对问题世界为真。先验知识问题：没有免费的午餐！不能指望存在对所有问题世界普适的一般方法。快速计算问题：数学工具的选择。“拓扑(划分)”保证对数据内在结构的刻画，“距离”保证局部的计算。拓扑结构与对象距离刻画数据集合中样本之间的拓扑结构与对象之间的距离是机器学习算法设计的基础。基于拓扑结构的算法基于距离的算法统计

37、机器学习符号机器学习SMO经典支持向量机树结构算法差别矩阵序贯最小优化(sequential minimal optimization,简称SMO)算法 3.3近年机器学习的发展趋势结 合对算法设计，在数据集合的拓扑结构(树或图)上，将距离嵌入上述拓扑结构的某些局部。加入向低维空间的同胚映射，就是流形。优点：对nm的情况，可以获得快速算法。理由是考虑拓扑结构就意味着，有些样本之间的距离无需计算，例如，SVM，“远离”支持向量的样本无需与其它样本比较(计算距离)，“远离”就是拓扑结构。3.3近年机器学习的发展趋势困难问题信息稀疏问题。关系数据问题。需求问题。例外问题。等等维数灾难：满足一定统计指

38、标(期望与方差)的模型(精度)，需要的样本数量将随着维数的增加，指数增长(或模型复杂程度，或模型表示长度指数增长)。维数灾难问题！(Curse of dimensionality, Bellman, 1961)生物、金融与网络等领域如此。3.4机器学习研究中的难题信息稀疏问题属性巨大，样本稀少。表现形式任务根据特定问题降维，使得信息稠密。是从数据集合中剥离一个稠密的问题世界。信息颗粒太细，解释太多，维数灾难！3.4机器学习研究中的难题关系数据问题任务对一阶谓词约束，以表示特定问题关系。为了表示简洁，数据不能表示为属性-值表的形式，需要关系数据形式。表现形式数据不能表示为命题形式，只能表示为一阶

39、谓词形式。如果将其变换为命题表示，信息稀疏！3.4机器学习研究中的难题需求问题任务(1)无法精确描述需求，非精确到精确描述(2)对解空间有效搜索，以获得需要的解答数据集合中包含多个有意义的解答。表现形式不同需求，目标函数不同，表示形式也不同(半监督、Ranking、数据流、多示例等)。多个需求叠加的“平均”，无人需要！无人喝彩！3.4机器学习研究中的难题例外问题任务在特定需求下，建立不同信息长度的模型，并同时派生例外。模型与例外构成伴生形式。例外相对特定模型存在经典方法是将不满足模型的个例考虑为噪音，因此，过滤噪音是其主要任务之一。表现形式在很多问题中(科学数据分析，ISI)，模型重要，不满足

40、模型的个例更为重要。3.4机器学习研究中的难题训练数据问题PU 学习问题:只有正例和未标记数据的学习问题，从仅部分标记的正例和其它的未标记数据上学习最优分类器数据推广性1173.4机器学习研究中的难题结构输出问题1183.4机器学习研究中的难题119内容机器学习的意义机器学习的基本概念机器学习的基本认知与发展趋势统计机器学习的基本方法总结典型机器学习开发包模式分类问题：输出y是类别标号，两类情况下y=1,-1，预测函数称作指示函数(Indicator Function)，损失函数定义见下式，使期望风险最小就是Bayes决策中使错误率最小。4.1三类基本的机器学习问题回归问题：输出y是连续变量，

41、它是x的函数，损失函数定义见下式:4.1三类基本的机器学习问题概率密度估计问题：根据训练样本确定x的概率分布p(x,w)，则损失函数可定义为:4.1三类基本的机器学习问题有监督/无监督学习有监督(Supervised)：分类、回归无监督(Unsupervised)：概率密度估计、聚类、降维半监督(Semi-supervised)：EM、Co-training其他学习方法增强学习(Reinforcement Learning)多任务学习(Multi-task learning)4.2统计学习的基本方法124有监督学习标定的训练数据训练过程：根据目标输出与实际输出的误差信号来调节参数典型方法全局：

42、BN, NN,SVM, Decision Tree局部：KNN、CBR(Case-base reasoning)S(x)=0 Class AS(x)1?Boosting：结合低性能学习模型来产生一个强大的分类器组Bagging：结合多个不稳定学习模型来产生稳定预测主动学习(Active learning)：主动选择训练样本学习模型(2)4.2统计学习的基本方法BoostingBoosting 是个非常强大的学习方法, 它组合许多“弱”分类器来产生一个强大的分类器组。弱分类器：性能只比随机选择好一点，设计简单且计算花费低。最常用的弱分类器是决策树。 常见的Boosting算法离散AdaBoost

43、, 实数AdaBoost, LogitBoost和Gentle AdaBoost它们有非常类似的总体结构。4.2统计学习的基本方法Boosting两类问题的算法：训练(step 13)和估计(step 4) 为每一个样本初始化使它们具有相同的权值(step 2),然后一个弱分类器f(x)在具有权值的训练数据上进行训练,计算错误率和换算系数cm(step 3b),被错分的样本的权重会增加,所有的权重进行归一化,并继续寻找若其他分类器M-1次,最后得到的分类器F(x)是这些独立的弱分类器组合的符号函数(step 4)。4.2统计学习的基本方法Bagging基本假设: Combining many

44、unstable predictors to produce a ensemble (stable) predictor.Unstable Predictor: 训练数据的微小变化可能使得预测模型产生大的改变不稳定模型：Neural Nets, trees稳定模型：SVM, KNN.Each predictor in ensemble is created by taking a bootstrap sample of the data.引导样本：obtained by drawing N example at random, with replacement.Encourages predi

45、ctors to have uncorrelated errors.4.2统计学习的基本方法Unlabeled Data Set主动学习Intermediate SetClustering (K clusters)(Diversity Criterion)BatchSelect centroid of each cluster(Representativeness Criterion)Select M most informative examples(Informativeness Criterion)(1)(2)(3)产生式模型 vs 判别式模型Generative models: 建模(

46、联合)概率分布：利用Bayes theorem典型方法：BN、HMM、CMF问题的可解释性好Discriminative models: 直接用函数（而非概率）来建模典型方法：SVM、LDA一般来说，性能更好Bayes决策理论有什么用？用不同方法可能得到多个不同的估计，哪个估计更好一些？统计决策理论：比较统计过程的形式化理论决策是从样本空间S，到决策空间的一个映射，表示为D: S 评价决策有多种标准，对于同一个问题，采用不同的标准会得到不同意义下“最优”的决策。Bayes决策常用的准则最小错误率准则最小风险准则最小条件错误率准则：在限定一类错误率条件下使另一类错误率为最小最小最大决策准则：Mi

47、nimizing the maximum possible loss (or Maximizing the minimum gain)4.3贝叶斯决策理论Linear Decision Boundaryx1x2x3hyperplanex1x24.3贝叶斯决策理论Non-linear Decision Boundaryx1x2x1x2x34.3贝叶斯决策理论问题描述：Classification Problem给定：m个类，训练样本和未知数据目标：给每个输入数据标记一个类属性两个阶段：建模/学习：基于训练样本学习分类规则.分类/测试：对输入数据应用分类规则P(f1)f1鹅卵石救命稻草杆Pebbl

48、es StrawspebblesStrawsf1f2决策边界139最大后验(Maximum A Posterior, MAP)分类什么是最优分类器?已有:类条件概率密度函数This is called the class-conditional probability describing the probability of occurrence of the features on category.欲求:后验概率make a decision that maximize the conditional probability of the object, given certain fe

49、ature measurements. Also called posterior probability function. p(x|1)p(x|2)类条件概率密度函数p(1|x)后验概率p(2|x)140Bayes最小错误率(MAP)决策MAP决策:以后验概率为判决函数:Choose category/class that has the maximumThis produces the optimal performance: minimum probability of error:A classifier that achieves this optimal performance

50、is called Bayesian classifier.MAP决策的错误率Bayes决策是一致最优决策。使得每个观测值下的条件错误率最小因而保证了（平均）错误率最小。MAP决策的扩展：最小Bayesian风险决策的风险：做决策要考虑决策可能引起的损失。以医生根据白细胞浓度判断一个人是否患血液病为例：没病(1)被判为有病(2) ，还可以做进一步检查，损失不大；有病(2)被判为无病(1) ，损失严重。Decision Risk tableThe risk to make a decision : classify x (belong to class i) to class j, so:Dec

51、ision Rule:Bayes决策：讨论基于Bayes决策的最优分类器Bayes决策的三个前提：类别数确定各类的先验概率P(Ci)已知各类的条件概率密度函数p(x|Ci)已知问题的转换：基于样本估计P(Ci)和p(x|Ci)基于样本直接确定判别函数学习问题决策树统计推理用数据的似然度(likelihood)和假设(Hypothesis)的概率去预测新实例的值朴素Bayes方法(Nave Bayes, NB)基于实例的学习最近邻方法(Nearest Neighbor)神经网络(Neural Networks)支持向量机(Support Vector Machine)典型聚类方法：K-Means

52、4.4统计学习方法Decision TreesAt each step, choose the feature that “reduces entropy” most. Work towards “node purity”.All the dataf1f2Choose f2Choose f14.4统计学习方法Decision TreesCART (Breiman, 1984) C4.5 (Quinlan, 1993) J48 4.4统计学习方法 Bayesian学习基本思想给定训练数据 ,计算每个假设 的概率利用此概率来进行预测（注：预测时利用所有的假设，而不仅仅利用最好的一个）参数估计问题若

53、训练数据独立同分布(i.e., i.i.d)，则对分类问题，需要估计两个参数：类的先验概率P(Ci)和类条件概率密度p(x|Ci)对分类问题，假设hi可直接视为类属性Ci4.4统计学习方法Bayesian学习:参数估计的方法类的先验概率P(Ci)的估计：用训练数据中各类出现的频率估计依靠经验类条件概率密度p(x|Ci)估计的两种主要方法：参数估计：概率密度函数的形式已知，而表征函数的参数未知，通过训练数据来估计最大似然估计Bayes估计（最大后验估计）非参数估计：密度函数的形式未知，也不作假设，利用训练数据直接对概率密度进行估计KN-近邻法Parzen窗法简化模型：简单贝叶斯Nave Baye

54、s简单贝叶斯学习模型（NB ）将训练实例表示成属性(特征)向量A和决策类别变量C。假定特征向量的各分量间相对于决策变量是相对独立的，也就是说各分量独立地作用于决策变量。降低了学习的复杂性在许多领域，表现出相当的健壮性和高效性NB的特点结构简单只有两层结构推理复杂性与网络节点个数呈线性关系Ca1a2an-1an150NB用于分类NB假设：设样本A表示成属性向量，如果属性ak对于给定的类别独立，那么P(A|Ci)可以分解成几个分量的积：简单贝叶斯分类 (SBC: Simple Bayesian Classifier)一般认为，只有在独立性假定成立的时候，SBC才能获得精度最优的分类效率；或者在属性

55、相关性较小的情况下，能获得近似最优的分类效果。151扩展：贝叶斯网(Bayes Network)= 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 .Lung CancerSmokingChest X-rayBronchitisDyspnoeaTuberculosisVisit to AsiaP(D|T,L,B)P(B|S)P(S)P

56、(C|T,L)P(L|S)P(A)P(T|A)贝叶斯网络是表示变量间概率依赖关系的有向无环图基于实例的学习Instance-basedBayeis方法的缺陷参数估计误差不描述概率分布，而直接描述决策规则，如最近邻规则：直接从训练数据构造假设K近邻方法K-NN最近邻方法NN: K=14.4统计学习方法K-NN方法对输入样本 x, 从训练样本中找到与x距离最近的K个最近样本，以它们最可能的类标签来分类xxk=1k=64.4统计学习方法K-NN的性能亚优：在训练样本足够的情况下，错误概率小于最优错误率的两倍. Where: is the probability of error for Bayesi

57、an inference (Optimal) and NN rule;不能在有限的样本下获得同样的断言.K-NN的关键问题距离度量最常用方法: euclidean更好的距离度量: normalize each variable by standard deviation离散数据：Hamming distanceK的选择Increasing k reduces variance, increases bias高维空间的可区分性差For high-dimensional space, problem that the nearest neighbor may not be very close a

58、t all!大数据量时计算开销大Must make a pass through the data for each classification. This can be prohibitive for large data sets.Indexing the data can help; for example KD treesEuclidean DistanceEuclidean Distance between x and pk is: The decision rule based on this metric is called theminimum Euclidean Dista

59、nce (MED) classifier.Mahalanobis Distance用方差的倒数来进行加权，相当于使决策界从方差较大的一方朝方差较小一方移动:Let the distribution be approximated by a multivariate normal density. The Mahalanobis distance from x to m is given by :Where is the covariance matrix and is the sample mean of the prototype. 胞体(Soma)枝蔓（Dendrite）胞体(Soma)

60、轴突（Axon）突触（Synapse） 人工神经元模拟生物神经元的一阶特性。输入：X=(x1, x2, , xn)联接权：W=(w1, w2, ,wn)T网络输入：net=xiwi向量形式：net=XW激活函数：f网络输出：o=f(net)InputsignalSynapticweightsSummingfunctionActivationfunctionLocalFieldvOutputox1x2xnw2wnw1w0 x0 = +1神经网络(NN)：模拟人脑的学习4.4统计学习方法x1x2xno1o2onwnmw11w1mw2mwn1输出层输入层典型网络结构:简单单级网4.4统计学习方法输出