机器学习的数学基础machinelearning

第一课课程导言1.1导言大纲涵盖由浅入深的一系列机器学习技术将会学到：oPCA,MDS,K-mean,基于频谱的聚类方法，贝叶斯分类，boosting,logistic回归，决策树，EM算法，隐马尔可夫模型，卡尔曼滤波……讲述算法、理论、应用背后的故事将会既有趣又辛苦时间安排03.04介绍03.11分类03.18聚类03.25隐马尔可夫与卡尔曼滤波原则简即美在理论性和应用性上达到平衡先修课程概率论o分布、密度、边界……统计基础o矩、经典分布、回归……算法o动态规划、基本数据结构、复杂度……编程oC/C++,Java,Matlab……将会提供一些背景知识，但课程步调还是会比较快处理抽象数学概念的能力参考书MachineLearningobyTomMitchellPatternClasssification(2supnd/supEdition)obyDuda,HartandStorkInformationTheory,Inference,andLearningAlgorithmobyDavidMacKayStatisticalInferenceobyGeorgeCasellaandRogerL.BergerPatternRecogniationandMachineLearningoChristopherM.BishopAndmore…以上均为可选参考书目，每人都会有自己的学习方法网络资源享受之！机器学习在科学、工作及其它领域正变得无所不在本课程将提供应用机器学习、开发新方法的基础1.2机器学习单元概况Callforediting1.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关键字：名词：数据、模型、模式、特征形容词：概率性的、统计的动词：拟合、推理、挖掘作业在你的研究方向上寻找机器学习的潜在应用参考文献Reinforcementlearning:AsurveyEditbyXinyuanLuo(骆歆远),[e-mail]1.4点估计最大似然,最大化后验估计,贝叶斯估计,回归方法与过拟合问题你将要学习点估计o最大似然估计(MLE,MaximalLikelihoodEstimation)o贝叶斯学习(BayesianLearning)o最大化后验(MAP,MaximizeAPosterior)高斯估计回归(Regression)o基础方程＝特性o方差和的最优化o回归与高斯估计的关系倾向与方差的折中你的第一个咨询工作一个北京的IT亿万富翁咨询你如下问题：o富：我有一些图钉，我将其抛出，那么它尾部朝上的概率是多少？o你：那么扔几次看看吧…o(图待上传)o你：概率是3/5o富：这是为什么呢？o你：这是因为…二值分布设头朝下的概率P(Heads)=θ，尾朝下的概率P(Tails)=1-θ，发生的事件D={T,H,H,T,T}抛图钉是一种独立重复分布(i.i.d.IndependentIdenticallydistributed)每一次实验彼此独立根据二值分布的分布概率相同如果一个事件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)=argmaxθαHlnθ+αTln(1−θ)导数为0时取极值，则有θˆ=αTαH+αT=32+3我需要抛多少次？θsup^/sup=αsubT/sub/αsubH/sub+αsubT/sub*富：我抛了两个头朝上和三个尾朝上*你：θ是3/5，我可以证明*富：如果我抛了20个头朝上和30个尾朝上呢*你：答案依然一样，我可以证明*富：能多解释一下吗*你：越多约好吗*富：所以我才会给你这么多报酬啊简单边界（基于Höffding不等式）对于N=αH+αT和θ^=αT/αH+αT,有令θ*为真实值，对任意ε0，有P(|θ^-θ*|≥ε)≤2e-2Nε^2第二课数据分类方法2.1概念学习2.1.1基本概念概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数的值，或者说，是给定某一类别的若干正例和反例，从中获得该类别的一般定义，它在预定的假设空间中搜索假设，使其与训练样例有最佳的拟合度。举例介绍（通过例子介绍概念学习中的相关术语）通过以下的训练数据集来学习使EnjoySport=yes的日子:ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes实例空间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)归纳学习假设：任一假设如果在足够大的训练样例集中很好的逼近目标函数，它也能在未见实例中很好的逼近目标函数。一般到特殊序：如果对于假设h1和h2,任何被h1划分为正例的实例都会被h2为分为正例，我们说h2比h1更一般（h2=h1）变型空间：是H中与训练样例D一致的所有假设构成的集合，为H的子集表示为VSH,D(个人以为引入变型空间的概念更容易理解假设空间H的结构和之后的列表后消除算法)2.1.2算法介绍FIND-S:寻找最大特殊假设o算法思想：从H中最特殊的假设开始，然后在该假设覆盖正实例失败时将其一般化。o算法步骤：将h初始化为H中最特殊的假设对每个正实例x，对h的每个属性约束ai,如果x满足ai,那么不做任何处理，否则将h中ai替换为x满足的下一个更一般约束输出假设ho算法举例：LIST_THEN_ELIMATION:列表后消除算法o算法思想：将变型空间初始化为包含H中所有的假设，然后从中去除与任一训练样例不一致的假设。o算法步骤：1.变型空间包含H中所有假设的列表2.对每个训练样例x,c(x),从变形空间中移出所有h(x)!=C(x)的假设h3.输出假设空间中的假设列表(输出的是一个集合)o算法举例：CANDIDATE-ELIMINATION:候选消除算法o算法思想：类似前两种算法的结合o算法步骤：1.将G初始化为最一般的假设，将S初始化为最特殊的假设2.对每个训练样例d，进行如下操作1.如果d是正例，对S使用FIND_S类似算法，但是我们要确保G必须比S更一般，否则就应该删除G中相应的项。2.如果d是反例，对G使用LIST_THEN_ELIMINATION类似算法o算法举例：2.1.3概念学习的方法小结概念学习可以看作室在预定义的假设空间中进行搜索的过程从一般到特殊的偏序假设，使我们可以使用更加有效地搜索方式，例如：候选消除算法实际的概念学习的方法必须是有归纳偏差的，否则他们只能被用来分类观察样本变形空间和候选消除算法为概念学习提供了很有用的框架，然而，他们的正确性必须要求正确的训练数据集和有能够表达未知目标概念的假设。RevisedbyDuanjinChen(陈端金),[e-mail]2.2决策树决策树学习是一种逼近离散值目标函数的方法，在这种方法中学习到的函数被表示为一棵决策树。这种学习算法是最流行的归纳推理算法之一，是一种从一般到特殊的算法。下面的数据是一个测试用例，根据各种条件决定是否打网球。决策树通过把实例从根结点排列（sort）到某个叶子结点来分类实例，叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性（attribute）的测试，并且