机器学习及其应用从离散数学谈起Machine Learning and Its ApplicationsTo Begin with Discrete Mathematics李 军 应用数学系 2013.10.301我的离散数学考试题1、哪个悖论是罗素提出的？（） A、理发师悖论B、说谎者悖论C、芝诺悖论D、言尽悖5、相比之下，与计算机科学发展史最不相关的是（） A、图灵B、莱布尼兹C、哈密顿D、哥德尔6、许多计算机科学的先驱者既是数学家，也是计算机科学家，但下列哪个选项例外？（） A、冯.诺依曼B、图灵C、 罗素D、高德纳10、离散数学能够培养学生严密的抽象思维和严格的逻辑推理能力，离散数学研究离散量的结构和相互关系，充分描述了计算机科学离散性的特点。离散数学的英语表示是（） A、Fuzzy Mathematics B、Discrete Mathematics C、Computing Mathematics D、Continuous Mathematics 15、离散数学与下列哪个研究方向最无关（） A、人工智能B、机器学习C、模式识别D、函数论2我的离散数学考试题1、哪个悖论是罗素提出的？（） A、理发师悖论B、说谎者悖论C、芝诺悖论D、言尽悖5、相比之下，与计算机科学发展史最不相关的是（） A、图灵图灵B、莱布尼兹C、哈密顿D、哥德尔6、许多计算机科学的先驱者既是数学家，也是计算机科学家，但下列哪个选项例外？（） A、冯冯.诺依曼诺依曼B、图灵图灵C、 罗素D、高德纳10、离散数学能够培养学生严密的抽象思维和严格的逻辑推理能力，离散数学研究离散量的结构和相互关系，充分描述了计算机科学离散性的特点。离散数学的英语表示是（） A、Fuzzy Mathematics B、Discrete Mathematics C、Computing Mathematics D、Continuous Mathematics 15、离散数学与下列哪个研究方向最无关（） A、人工智能人工智能B、机器学习机器学习C、模式识别模式识别D、函数论3算盘 帕斯卡加法机4巴贝奇差分机 分析机5莱布尼兹二进制 乘法机 猜测人类的思想可以简化为机械计算 形式推理6数理逻辑离散数学第一部分20世纪，数理逻辑研究上的突破使得人工智能好像呼之欲出。 布尔 思维的定律 弗雷格 概念文字 罗素、怀特海 数学原理中对数学的基础给出了形式化描述。 希尔伯特“能否将所有数学推理形式化?” 哥德尔不完备定理图灵机 丘奇 演算7冯诺伊曼二进制 101页报告EDVAC报告书 冯诺伊曼结构8Can Machines Think? 图灵测试 图灵机9图灵在1950年发表的一篇催生现代智能机器研究的著名论文中称，“我们只能看到眼前的一小段距离但是，我们可以看到仍有许多工作要做”。 邱奇-图灵论题暗示，一台仅能处理0和1这样简单二元符号的机械设备能够模拟任意数学推理过程。这里最关键的灵感是图灵机：这一看似简单的理论构造抓住了抽象符号处理的本质。这一创造激发科学家们探讨让机器思考的可能。10WhatWhat：什么是机器学习？：什么是机器学习？WhyWhy：为什么需要机器学习？：为什么需要机器学习？HowHow：机器机器如何如何学习？学习？机器学习的未来机器学习的未来如果你学会机器学习如果你学会机器学习11WhatWhat：什么是机器学习？：什么是机器学习？机器学习机器学习是近20多年兴起的一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。机器学习算法是一类从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。因为学习算法中涉及了大量的统计学理论，机器学习与统计推断学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。 机器学习已经有了十分广泛的应用，例如：数据挖掘、计算机视觉、自然语言处理、生物特征识别、搜索引擎、医学诊断、检测信用卡欺诈、证券市场分析、DNA序列测序、语音和手写识别、战略游戏和机器人运用。12WhatWhat：什么是机器学习？：什么是机器学习？机器学习(Machine Learning)是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域，它主要使用归纳、综合而不是演绎。13机器学习的发展历史(1)1950s：神经科学的理论基础 James关于神经元是相互连接的发现 McCullon & Pitts的神经元模型 Hebb 学习律（相互连接强弱度的变换规则）1960s：感知器（Perceptron）时代 1957年Rosenblatt首次提出14机器学习的发展历史(2)1969年：Perceptron出版，提出著名的XOR问题 1970s：符号主义，逻辑推理 1980s：MLP+BP算法成功解决XOR问题，从此进入神经网络时代（连接主义） 1960s-1970s: 统计学习理论创立 VC维的基本概念 结构风险最小化原则 概率空间的大数定律15机器学习的发展历史(3)1990s：统计学习理论的发展及完善 典型代表：SVM （Vapnik，Bell实验室） 结构风险最小化 最小描述长度原则 小样本问题 核函数、核空间变化 PAC理论下的弱可学习理论的建立 支持向量机 16机器学习的发展历史(4)2000s：各种机器学习理论及算法得以充分发展 符号机器学习 计算机器学习（统计学习理论，典型例子：SVM） 集群机器学习（典型代表：Boosting） 强化机器学习 流形机器学习 监督学习，非监督学习 半监督学习、 .1718连接机器学习符号机器学习 遗传机器学习 分析机器学习流形机器学习 半监督机器学习 多实例机器学习 Ranking机器学 数据流机器学习流形机器学习 半监督机器学习 多实例机器学习 Ranking机器学 数据流机器学习应用驱动的机器学习研应用驱动的机器学习研统计机器学习 集成机器学习 符号机器学习 增强机器学习Carbonell(1989)展Carbonell(1989)展Dietterich(1997)展Dietterich(1997)展机器学习研究的变机器学习研究的变1819近年机器学习的发展趋势问题驱动的机器学习研究(基础类型)问题驱动的机器学习研究(基础类型)观测数据不能决定其类别标号，需要根据已知类别标号的样本与领域知识来推测。例如，医学影像，质谱蛋白质结构分析。例如，医学影像，质谱蛋白质结构分析。半监督学习 Semi-supervised learning很多问题的表示方法，使得信息十分稀疏，且具有强的非线性特性，将信息稠密化、可视化是重要任务。例如，图像、文本等处理。例如，图像、文本等处理。流形学习 Manifold Learning数据存储在关系数据库中，它们不能表示为属性-值表形式。只能使用一阶谓词来描述，例如，金融数据分析。例如，金融数据分析。关系学习 Relational learning1920近年机器学习的发展趋势问题驱动的机器学习研究(应用类型)问题驱动的机器学习研究(应用类型)一个对象同时有多个描述，不知道哪个描述是决定对象性质(例如类别)，“对象:描述:类别”之间呈现1:N:1关系。例如，基因功能分析。例如，基因功能分析。假设用户的需求不能简单地表示为“喜欢”或“不喜欢”，而需要将“喜欢”表示为一个顺序，如何学习获得这个“喜欢”顺序的模型。例如，信息检索。例如，信息检索。多示例学习 Multi-instance learningRanking学习 Learning for ranking从用户节点流过的数据巨大，但大多数无意义，例如，网络信息分析。，例如，网络信息分析。数据流学习 Data stream learning模型重要，不满足模型的个例更为重要，例外相对特定模型存在。例如，科学与情报数据分析。例如，科学与情报数据分析。规则+例外学习 Rule+Exception Learning 2 0WhyWhy：为什么需要机器学习？：为什么需要机器学习？2 122机器学习的重要性美国航空航天局JPL实验室的科学家在Science（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，该领域在今后的若干年内将取得稳定而快速的发展2 223入侵检测：是否是入侵？是何种入侵？如何检测？历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现对当前访问模式分类这是一个典型的机器学习问题常用技术：神经网络决策树支持向量机贝叶斯分类器k近邻序列分析聚类 例1:网络安全2 324常用技术：神经网络支持向量机隐马尔可夫模型贝叶斯分类器k近邻决策树序列分析聚类 例2:生物信息学2 425例3:计算语言学常用技术：神经网络隐马尔可夫模型贝叶斯分类器决策树序列分析聚类 2 526Google的成功，使得Internet 搜索引擎成为一个新兴的产业不仅有众多专营搜索引擎的公司出现（例如专门针对中文搜索的就有百度、慧聪等），而且Microsoft等巨头也开始投入巨资进行研发Google掘到的第一桶金，来源于其创始人Larry Page和Sergey Brin提出的PageRank算法机器学习技术正在支撑着各类搜索引擎例4:搜索引擎2 627例5:色彩空间转换常用技术：神经网络支持向量机隐马尔可夫模型贝叶斯分类器聚类 2 7HowHow：机器如何学习？：机器如何学习？2 8Andrew Ng What do we want computers to do with our data? Images/video Audio Text Label: “Motorcycle” Suggest tags Image search Speech recognition Speaker identification Music classification Web search Anti-spam Machine translation Machine learning performs well on many of these problems, but is a lot of work. What is it about machine learning that makes it so hard to use? 2 22 9Andrew Ng Why is this hard? You see this: But the camera sees this: 2 330Andrew Ng Machine learning and feature representations Input Raw image Motorbikes “Non”-Motorbikes Learning algorithm pixel 1 pixel 2 pixel 1 pixel 2 2 431Andrew Ng Machine learning and feature representations Input Motorbikes “Non”-Motorbikes Learning algorithm pixel 1 pixel 2 pixel 1 pixel 2 Raw image 2 532Andrew Ng Machine l