机器学习斯坦福大学讲义

机器学习——斯坦福大学讲义第一课机器学习的动机与应用工具：需正版：Matlab，免费：Octave定义（ArthurSamuel1959）：在不直接针对问题进行编程的情况下，赋予计算机学习能力的研究领域。例：Arthur的下棋程序，计算走每一步获胜的概率，最终打败程序作者本人。（感觉使用决策树思想）定义2（TomMitchell1998）：一个合理的学习问题应该这样定义：对一个计算机程序来说，给它一个任务T和一个性能测量方法P，如果在经验E的影响下，P对T的测量结果得到了改进，那么就说改程序从E中学习了。如上例：E：程序不断和自己下棋的经历，T：下棋，P：和人类选手对弈的胜率课程的四大部分：1、有监督学习（1）回归问题例：收集某地房屋价格统计、房屋大小和价格对应情况：画出一条拟合曲线，就可以通过房屋大小估计价格。-有监督学习即给出一个数据集（正确的房屋价格及对应大小）-此例为回归问题。回归意味着需要预测的变量是连续的（2）分类问题分类问题中需要处理的变量是离散的例：判断肿瘤是恶性还是两性-收集肿瘤大小和恶性/良性数据，大小为横轴，是否是恶性为纵轴（只有0,1）画图-肿瘤可能由多个因素导致，引入年龄，大小为横轴，年龄为纵轴，恶性以叉表示，良性以圆圈表示画图，分析患肿瘤的区域-还可引入更多属性，画在多维空间中-无限维空间如何处理？将无限维映射到内存的算法？2、学习理论学习理论即解释学习型算法有效的原因（学习算法的理论基础）寻找什么样的算法能很好地近似不同的函数，训练集的规模是否合适3、无监督学习例：如上述肿瘤例子，图中的点不知道正确答案，而是由你从中找去一定的结构，即聚类。应用于生物基因工程，图像处理，计算机视觉等领域例：鸡尾酒会问题在嘈杂的鸡尾酒会中，将你感兴趣的声音提取出来运用两个不同位置的麦克分开来自不同位置的声音还能应用于文本处理等领域使用ICA算法，Matlab一行代码即可解决4、强化学习通过决策产生的结论或对或错，故产生一系列的决策。例：对一个模型飞机编写一个起飞程序，飞机在程序做了一连串错误决策是才会坠毁，只要做出连续的整体还不错的决策，即可保持飞机正常飞行强化学习的基本概念：回报函数（正反馈及负反馈），程序做出正确决策时给出正反馈，反之亦然。程序不断做出决策，在不断尝试获得尽量多的正反馈时，逐渐学习并做出正确决策关键在于要定义什么是正确决策，什么是错误决策，再设计算法获取尽量多的正反馈第二课监督学习应用与梯度下降本课内容：1、线性回归2、梯度下降3、正规方程组（复习）监督学习：告诉算法每个样本的正确答案，学习后的算法对新的输入也能输入正确的答案1、线性回归例：Alvin汽车，先让人开车，Alvin摄像头观看（训练），而后实现自动驾驶。本质是一个回归问题，汽车尝试预测行驶方向。例：上一节课的房屋大小与价格数据集引入通用符号：m=训练样本数x=输入变量（特征）y=输出变量（目标变量）(x,y)–一个样本–第i个训练样本=本例中：m：数据个数，x：房屋大小，y：价格监督学习过程：1)将训练样本提供给学习算法2)算法生成一个输出函数（一般用h表示，成为假设）3)这个函数接收输入，输出结果。（本例中为，接收房屋面积，输出房价）将x映射到y。如下图所示：对假设进行线性表示：通常来说，回归问题有多个输入特征。如上例中，我们还已知房屋的卧室数，即有个第二个特征。即表示大小，表示卧室数，则可将假设写成：。为了将公式写整洁，定义，则h可写成：n=特征数目，：参数。选择的目的，是使h(x)与y的平方差尽量小。又由于有m个训练样本，需要计算每个样本的平方差，最后为了简化结果乘以1/2，即：我们要做的就是求：min(J())求min(J())方法：梯度下降和正规方程组2、梯度下降梯度下降是一种搜索算法，基本思想：先给出参数向量一个初始值，比如0向量；不断改变，使得J()不断缩小。改变的方法：梯度下降如图所示，水平坐标轴表示，垂直坐标表示J()一开始选择0向量作为初始值，假设该三维图为一个三维地表，0向量的点位于一座“山”上。梯度下降的方法是，你环视一周，寻找下降最快的路径，即为梯度的方向，每次下降一小步，再环视四周，继续下降，以此类推。结果到达一个局部最小值，如下图：当然，若初始点不同，则结果可能为另一个完全不同的局部最小值，如下：表明梯度下降的结果依赖于参数初始值。梯度下降算法的数学表示：为赋值运算符，即表示程序中的的赋值语句。每一次将减去对求偏导的结果，即沿最陡峭的“山坡”下降将偏导数展开分析：代入上式：：学习速度，即决定你下山时每一步迈多大。设的过小，收敛时间长，设的过大，可能会超过最小值（1）批梯度下降算法：上述为处理一个训练样本的公式，将其派生成包含m个训练样本的算法，循环下式直至收敛：复杂度分析：对于每个的每次迭代，即上式所示，时间为O(m)每次迭代（走一步）需要计算n个特征的梯度值，复杂度为O(mn)一般来说，这种二次函数的的三维图形为一个碗状，有一个唯一的全局最小值。其等高线为一个套一个的椭圆形，运用梯度下降会快速收敛到圆心。梯度下降性质：接近收敛时，每次的步子会越来越小。其原因是每次减去乘以梯度，但是梯度会越来越小，所以步子会越来越小。下图为使用梯度下降拟合的上例房屋大小和价格的曲线检测是否收敛的方法：1)检测两次迭代的改变量，若不再变化，则判定收敛2)更常用的方法：检验，若不再变化，判定收敛批梯度下降算法的优点是能找到局部最优解，但是若训练样本m很大的话，其每次迭代都要计算所有样本的偏导数的和，时间过慢，于是采用下述另一种梯度下降方法。（2）随机梯度下降算法（增量梯度下降算法）：每次计算不需要再遍历所有数据，而是只需计算样本i即可。即批梯度下降中，走一步为考虑m个样本；随机梯度下降中，走一步只考虑1个样本。每次迭代复杂度为O(n)。当m个样本用完时，继续循环到第1个样本。上述使用了迭代的方法求最小值，实际上对于这类特定的最小二乘回归问题，或者普通最小二乘问题，存在其他方法给出最小值，接下来这种方法可以给出参数向量的解析表达式，如此一来就不需要迭代求解了。3、正规方程组给定一个函数J，J是一个关于参数数组的函数，定义J的梯度关于的导数，它自己也是一个向量。向量大小为n+1维（从0到n），如下：所以，梯度下降算法可写成：更普遍的讲，对于一个函数f，f的功能是将一个m*n的矩阵映射到实数空间上，即：假设输入为m*n大小的矩阵A，定义f关于矩阵A的导数为：导数本身也是个矩阵，包含了f关于A的每个元素的偏导数。如果A是一个方阵，即n*n的矩阵，则将A的迹定义为A的对角元素之和，即：trA即为tr(A)的简化。一些关于迹运算符和导数的定理：1)trAB=trBA2)trABC=trCAB=trBCA3)4)5)若，tra=a6)有了上述性质，可以开始推导了：定义矩阵X，称为设计矩阵，包含了训练集中所有输入的矩阵，第i行为第i组输入数据，即：则由于，所以可得：又因为对于向量z，有，则有：由上述最后一个性质可得：通过上述6个性质，推导：倒数第三行中，运用最后一个性质将置为0，则有：称为正规方程组可得：第三课欠拟合与过拟合概念本次课程大纲：1、局部加权回归：线性回归的变化版本2、概率解释：另一种可能的对于线性回归的解释3、Logistic回归：基于2的一个分类算法4、感知器算法：对于3的延伸，简要讲复习：–第i个训练样本令，以参数向量为条件，对于输入x，输出为：n为特征数量定义成本函数J，定义为：m为训练样本通过正规方程组推导的结论：1、过拟合与欠拟合通常，你选择交给学习算法处理的特征的方式对算法的工作过程有很大影响。例：上次课的例子中，用x1表示房间大小。通过线性回归，在横轴为房间大小，纵轴为价格的图中，画出拟合曲线。回归的曲线方程为：若定义特征集合为：x1表示房子大小，x2表示房子大小的平方，使用相同的算法，拟合得到一个二次函数，在图中即为一个抛物线，即：以此类推，若训练集有7个数据，则可拟合出最高6次的多项式，可以找到一条完美的曲线，该曲线经过每个数据点。但是这样的模型又过于复杂，拟合结果仅仅反映了所给的特定数据的特质，不具有通过房屋大小来估计房价的普遍性。而线性回归的结果可能无法捕获所有训练集的信息。所以，对于一个监督学习模型来说，过小的特征集合使得模型过于简单，过大的特征集合使得模型过于复杂。对于特征集过小的情况，称之为欠拟合（underfitting）；对于特征集过大的情况，称之为过拟合（overfitting）解决此类学习问题的方法：1)特征选择算法：一类自动化算法，在这类回归问题中选择用到的特征2)非参数学习算法：缓解对于选取特征的需求，引出局部加权回归参数学习算法（parametriclearningalgorithm）定义：参数学习算法是一类有固定数目参数，以用来进行数据拟合的算法。设该固定的参数集合为。线性回归即使参数学习算法的一个例子非参数学习算法（Non-parametriclearningalgorithm）定义：一个参数数量会随m（训练集大小）增长的算法。通常定义为参数数量虽m线性增长。换句话说，就是算法所需要的东西会随着训练集合线性增长，算法的维持是基于整个训练集合的，即使是在学习以后。2、局部加权回归（LocallyWeightedRegression）一种特定的非参数学习算法。也称作Loess。算法思想：假设对于一个确定的查询点x，在x处对你的假设h(x)求值。对于线性回归，步骤如下：1)拟合出，使最小2)返回对于局部加权回归，当要处理x时：1)检查数据集合，并且只考虑位于x周围的固定区域内的数据点2)对这个区域内的点做线性回归，拟合出一条直线3)根据这条拟合直线对x的输出，作为算法返回的结果用数学语言描述即：1)拟合出，使最小2)w为权值，有很多可能的选择，比如：-其意义在于，所选取的x(i)越接近x，相应的w(i)越接近1；x(i)越远离x，w(i)越接近0。直观的说，就是离得近的点权值大，离得远的点权值小。-这个衰减函数比较具有普遍意义，虽然它的曲线是钟形的，但不是高斯分布。-被称作波长函数，它控制了权值随距离下降的速率。它越小，钟形越窄，w衰减的很快；它越大，衰减的就越慢。3)返回总结：对于局部加权回归，每进行一次预测，都要重新拟合一条曲线。但如果沿着x轴对每个点都进行同样的操作，你会得到对于这个数据集的局部加权回归预测结果，追踪到一条非线性曲线。*局部加权回归的问题：由于每次进行预测都要根据训练集拟合曲线，若训练集太大，每次进行预测的用到的训练集就会变得很大，有方法可以让局部加权回归对于大型数据集更高效，详情参见AndrewMoore的关于KD-tree的工作。3、概率解释概率解释所解决的问题：在线性回归中，为什么选择最小二乘作为计算参数的指标，使得假设预测出的值和真正y值之间面积的平方最小化？我们提供一组假设，证明在这组假设下最小二乘是有意义的，但是这组假设不唯一，还有其他很多方法可以证明其有意义。（1）假设1：假设输入与输出为线性函数关系，表示为：其中，为误差项，这个参数可以理解为对未建模效应的捕获，如果还有其他特征，这个误差项表示了一种我们没有捕获的特征，或者看成一种随机的噪声。假设服从某个概率分布，如高斯分布（正态分布）：，表示一个均值是0，方差是的高斯分布。高斯分布的概率密度函数：根据上述两式可得：即，在给定了特征与参数之后，输出是一个服从高斯分布的随机变量,可描述为：*为什么选取高斯分布？1)便于数学处理2)对绝大多数问题，如果使用了线性回归模型，然后测量误差分布，通常会发现误差是高斯分布的。3)中心极限定律：若干独立的随机变量之和趋向于服从高斯分布。若误差有多个因素导致，这些因素造成的效应的总和接近服从高斯分布。注意：并不是一个随机变量，而是一个尝试估计的值，就是说它本身是一个常量，只不过我们不知道它的值，所以上式中用分号表示。分号应读作“以…作为参数”，上式读作“给定x(i)以为参数的y(i)的概率服从高斯分布”。假设每个为IID（independentlya