机器学习的数学基础.doc

第一课 课程导言 1.1 导言 大纲  涵盖由浅入深的一系列机器学习技术  将会学到： o PCA, MDS, K-mean, 基于频谱的聚类方法，贝叶斯分类，boosting, logistic回归，决策树，EM 算法，隐马尔可夫模型，卡尔曼滤波……  讲述算法、理论、应用背后的故事  将会既有趣又辛苦 时间安排  03.04 介绍  03.11 分类  03.18 聚类  03.25 隐马尔可夫与卡尔曼滤波 原则  简即美  在理论性和应用性上达到平衡 先修课程  概率论 o 分布、密度、边界……  统计基础 o 矩、经典分布、回归……  算法 o 动态规划、基本数据结构、复杂度……  编程 o C/C++, Java, Matlab……  将会提供一些背景知识，但课程步调还是会比较快  处理抽象数学概念的能力 参考书  Machine Learning o by Tom Mitchell  Pattern Classsification (2nd Edition) o by Duda, Hart and Stork  Information Theory, Inference, and Learning Algorithm o by David MacKay  Statistical Inferenceo by George Casella and Roger L. Berger  Pattern Recogniation and Machine Learning o Christopher M.Bishop  And more …  以上均为可选参考书目，每人都会有自己的学习方法 网络资源  享受之！  机器学习在科学、工作及其它领域正变得无所不在  本课程将提供应用机器学习、开发新方法的基础 1.2 机器学习单元概况 Call for editing 1.3 什么是机器学习？ 大纲  背景  什么是机器学习  机器学习对于计算机科学和技术有何帮助 当今计算机科学的最大挑战  数据，数据，数据…… o 需要大量乏味的重复的工作才能创建数字化的世界  需要寻找新的交互方式，创造新类型的媒体  花费高的代价才能请专家（科学家、工程师、电影制作人员、图形 设计师、优秀艺术家和游戏设计人员）来完成工作  需要高效地处理已经存在的数据，并通过它们获得新的数据 计算机是高效运行的机器  各种图像、场景，只要人能够创造，就可以利用计算机来得到它  但是如何来创造这些图像、场景 完全过程化合成VS完全数据化  为电影中的一个角色创造动作 o 完全过程化合成  动作比较连贯，但是很容易让人觉得是伪造的，很少在实际中这样 用 o 完全手工制作或者完全数据化  效果质量很高，但是连贯性不好 o 把两者结合起来的混合方法或许是最好的！？ 贝叶斯推理 关于不确定性的一个规则模型  非结构化数据的通用模型  数据拟合和不确定分析的有效算法 但是，当前它通常被当做一个黑盒来使用 确定性 VS 几率性 数据驱动模型什么是机器学习机器学习 != 人工智能  Mitchell 在1997 年定义的：机器学习乃于某类任务兼性能度量的经验中学习之程 序；若其作用于任务，可由度量知其于已知经验中获益。

 Hertzmann在2003 年的评论：对于计算机图形学上的一些应用，机器学习应该被 看作处理数据的一系列技术给定一些数据，可以得到一个方法模型用于生产新的数据  编制学习系统不只是用来解决一个问题，而是基于一些特征来使系统本身更加优化 ： o 关于系统应该如何做出响应的一些例子o 关于系统在解决问题的过程中反复试验学习到的经验  不同于通常的计算机科学，去实现一个未知的功能；仅仅是处理已知的输入输出数 据对（学习过程中的训练例子） 学习问题的主要分类  学习情景根据训练例子中提供的有效信息的改变而改变 o 监督的：需要正确的输出  分类：输入N个目标，输出结果为选择其中一个（语音识别、目标 辨认、医学诊断）  回归：输出准确值（预测未来的市场价格、温度） o 部分监督的：只输出一部分有效结果 o 无监督的：没有反馈，需要对输出进行自我评估  聚类：聚类是指将数据分割成连贯的群集的技术  结构异常识别：检测超出正常范围的数据点 o 加强的:标量反馈,可能暂时推迟 更多信息  时间序列分析  降维  模型选择  泛型方法  图形建模 为什么要学习机器学习？  开发强化的计算机系统 o 能够自动适应用户，更加符合用户要求 o 旧的系统往往很难获得必要的知识 o 发掘大型数据库中离线的新数据挖掘模式  提高对人的认识，生物学习 o 提供具体的理论计算分析，预测 o 分析大脑的学习过程中的爆发式活动  研究时机很好 o 数据量的快速增长 o 计算机不再昂贵而且功能强大 o 理论得到了很好的发展，有一系列的算法组件 机器学习对计算机科学和技术有用吗？  赞成方：所有事物都是机器学习，所有事物都是人的调整 o 在有些时候，这个说法是正确的  反对方：虽然是对“ 学习” 的一种深化，但还有其它更强大和有效的算法。

o 问题分类 o 通用模型 o 通过概率进行推算 相信数学的魔力 怎样才是一个成功的机器学习算法？  计算效率  鲁棒性  统计稳定性 一些实际应用  Google!  目标识别和辨认——机器学习的力量  文档处理——贝叶斯分类器  网格处理——数据聚类和分割  纹理合成和分析——隐式马尔科夫模型  反射纹理合成——降维  人体建模——降维  图像处理和合成——图形建模  人体运动合成——时间序列分析  视频纹理——强化学习 总结  机器学习就是这样简单明了的东西 o 关键字：  名词：数据、模型、模式、特征  形容词：概率性的、统计的  动词：拟合、推理、挖掘 作业  在你的研究方向上寻找机器学习的潜在应用 参考文献  Reinforcement learning: A survey Edit by Xinyuan Luo(骆歆远), wisp@ 1.4 点估计 最大似然, 最大化后验估计, 贝叶斯估计, 回归方法与过拟合问题 你将要学习  点估计 o 最大似然估计(MLE, Maximal Likelihood Estimation) o 贝叶斯学习(Bayesian Learning) o 最大化后验(MAP, Maximize A Posterior)  高斯估计  回归(Regression)o 基础方程 ＝ 特性 o 方差和的最优化 o 回归与高斯估计的关系  倾向与方差的折中 你的第一个咨询工作  一个北京的IT 亿万富翁咨询你如下问题： o 富：我有一些图钉，我将其抛出，那么它尾部朝上的概率是多少？ o 你：那么扔几次看看吧… o ( 图待上传) o 你：概率是3/5 o 富：这是为什么呢？ o 你：这是因为… 二值分布  设头朝下的概率 P(Heads)= θ，尾朝下的概率 P(Tails)=1- θ，发生的事件D={T,H,H,T,T}  抛图钉是一种独立重复分布(i.i.d. Independent Identically distributed)  每一次实验彼此独立  根据二值分布的分布概率相同  如果一个事件D 包含α H 个头朝下的概率和α T 个尾朝下的概率，这样事件的概率是： \\P(D|θ)=θ α H (1-θ) α T 最大似然估计  数据：观察事件集合D 包含α H 个头朝下的事件和α T 个尾朝下的事件  前提：二值分布  在优化问题中对θ进行学习：  目标函数是什么？ D = {T, H, H, T, T}  MLE: 找出使观察到的现象的概率最大化的 θ θˆ =argmaxθP(D ∣θ) =argmaxθlnP(D ∣θ) =argmaxθln(θαH(1−θ)αT) =argma xθαHlnθ+αTln(1 −θ)  导数为0时取极值，则有θˆ=αTαH+αT=32+3 我需要抛多少次？ θ^ = αT / αH + αT * 富：我抛了两个头朝上和三个尾朝上 * 你：θ是3/5，我可以证明 * 富：如果我抛了20个头朝上和30个尾朝上呢 * 你：答案依然一样，我可以证明 * 富：能多解释一下吗 * 你：越多约好吗 * 富：所以我才会给你这么多报酬啊 简单边界（基于Höffding不等式）  对于N = α H + α T 和 θ ^ = α T / α H + α T , 有  令θ * 为真实值，对任意ε>0，有 P(|θ ^ - θ * |≥ε)≤2e -2Nε^2第二课 数据分类方法 2.1 概念学习 2.1.1 基本概念 概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函 数的值，或者说，是给定某一类别的若干正例和反例，从中获得该类别的一般 定义，它在预定的假设空间中搜索假设，使其与训练样例有最佳的拟合度。

举例介绍（通过例子介绍概念学习中的相关术语） 通过以下的训练数据集来学习使EnjoySport=yes的日子: Exampl e Sky AirTem p Humidi ty Wind Wat er Foreca st EnjoySpo rt 1 Sunn y Warm Normal Stron g War m Same Yes 2 Sunn y Warm High Stron g War m Same Yes 3 Rainy Cold High Stron g War m Change No 4 Sunn y Warm High Stron g Cool Change Yes 实例空间X：概念是定义在一个实例集合上的，本例中X是所有可能的日子 ，而Sky,AirTemp之类是日子的属性; 目标函数C：代学习的函数，可以是定义在实例集X 上的任意布尔函数,形式化 为C:X→{0,1}; 训练样本D ：是为学习概念而提供的训练实例，训练样本中的每一个条目为X中 的一个实例加上此实例对应的目标函数的值C(x); 假设空间H：所有可能假设的集合，它中的每一个假设h表示X上定义的布尔函 数，即h ：X →{0,1};注：机器学习要做的就是拟合出h，使h(x)=c(x) 归纳学习假设：任一假设如果在足够大的训练样例集中很好的逼近目标函 数，它也能在未见实例中很好的逼近目标函数。

一般到特殊序：如果对于假设h 1 和h 2 , 任何被h 1 划分为正例的实例都会被h 2 为分 为正例，我们说h 2 比h 1 更一般（h 2 >= h 1 ） 变型空间：是H中与训练样例D一致的所有假设构成的集合，为H的子集表示为 VS H,D ( 个人以为引入变型空间 的概念更容易理解假设空间H 的结构和之后的列 表后消除算法)2.1.2 算法介绍  FIND-S:寻找最大特殊假设 o 算法思想：从H中最特殊的假设开始，然后在该假设覆盖正实例失败时将 其一般化 o 算法步骤：  将h初始化为H中最特殊的假设  对每个正实例x，对h的每个属性约束a i , 如果x 满足a i , 那么不做任何 处理，否则将h 中a i 替换为x满足的下一个更一般约束  输出假设h o 算法举例：  LIST_THEN_ELIMATION:列表后消除算法 o 算法思想：将变型空间初始化为包含H中所有的假设，然后从中去除与任 一训练样例不一致的假设 o 算法步骤： 1. 变型空间包含H中所有假设的列表 2. 对每个训练样例,从变形空间中移出所有h(x)!=C(x)的 假设h 3. 输出假设空间中的假设列表(输出的是一个集合)。