大数据存储与处理-大规模机器学习课件

大数据存储与应用

大规模机器学习课程主页：http:///?page_id=397陈一帅chenyishuai@大数据存储与应用

大规模机器学习1介绍机器学习定义Perceptron（

感知机）SVM（support-vectormachines）支持向量机最近邻（nearestneighbor）决策树介绍机器学习定义2机器学习训练集

（X,y）X：featurevectory:label目的：找到一个函数：y=f(X)发现规律，预测未来y类型实数：Regression布尔值：二元分类有限取值：多元分类无限取值：句子机器学习训练集（X,y）3狗狗分类奇瓦瓦狗（体小，毛平滑）小猎兔狗腊肠犬X:高度，重量y:狗的种类狗狗分类奇瓦瓦狗（体小，毛平滑）小猎兔狗腊肠犬X:高度，4文本分类根据email的内容，判断是否垃圾邮件根据新闻内容，判断新闻类型SportPoliticsFeaturevector单词向量（1，0）文本分类根据email的内容，判断是否垃圾邮件5常用方法无监督学习聚类有监督学习决策树感知机：PerceptronsSVM支持向量机神经元网络无循环感知机网络基于事例的学习Instance-basedlearningKNN常用方法无监督学习6模型元素训练集测试集分类器问题：Overfit模型元素7工作方式BatchlearningOnlinelearning象Stream来一个处理一个，更新分类器能够处理大训练集工作方式Batchlearning8应用快递获单预测X：出价，起点，终点y：接受/拒绝Online算法持续收集新数据，不断更新模型应用快递获单预测9感知机感知机10感知机神经元刺激是输入的加权和感知机神经元11感知机输入：实数向量输出：1/-1例：垃圾邮件检测Instance空间类型输入：X输出：y感知机输入：实数向量Instance空间类型输入：X输出：12模型目标：找到合适的使0模型目标：013几何描述W和X向量的点积（余弦距离）wx>0wx<0几何描述W和X向量的点积（余弦距离）wx>0wx<14求W初始化为全0来一个x，算如果y=y’，W保持不变如果y!=y，往yx的方向旋转一点求W初始化为全015旋转的效果y(x1)=1却被判为了-1W往x1方向转一点W+cyx1判断平面逆时针旋转一点试图把x1包进来旋转的效果y(x1)=116收敛性只要是线性可分割的，就会收敛如果不是，最后会震荡，无限循环收敛性只要是线性可分割的，就会收敛17震荡时的停止算法震荡时，如何停止算法？逐渐减小调整幅度观察训练集上的误差观察一个小测试集上的误差限制最大迭代次数震荡时的停止算法震荡时，如何停止算法？18非零判决平移非零判决平移19多类感知超过两类分别训练三个分类器谁的wx值最大，算谁多类感知超过两类谁的wx值最大，算谁20Winnow算法总会收敛x取值：0，1初始化w

全1，为x的长度预测预测对，w不动预测错：y真值是1，可，说明w太小，看x中哪些值为1，把对应的w加倍y真值是-1，可，说明w太大，看x中哪些值为1，把对应的w减半Winnow算法总会收敛21的调整把它加到w里，一起变允许对应的x为-1，但调整方法反过来：预测错：y真值是1，，说明

太大，减半y真值是-1，，说明

太小，加倍的调整把它加到w里，一起变允许对应的x为22扩展平衡Winnow（BalancedWinnow）ThickSeparator界限（Margin）放松扩展平衡Winnow（BalancedWinnow）23非线性边界变换到线性上非线性边界变换到线性上24Map-Reduce的实现每个机器处理部分xMap：如果出错，生成键值对（i,cyxi)表示要对wi进行调整c为调整速度Reduce累积，实现对w的调整重复，直到收敛，或到达停止的条件Map-Reduce的实现每个机器处理部分x25感知机总结感知机加法更新w适合x少，互相有相关性Winnonw乘法更新w适合x多，互相无相关性感知机总结感知机26感知机总结是一种Online算法新(x,y)到达，更新w局限线性分割线性不可分的话，不收敛Feature多时，效果一般感知机总结是一种Online算法27问题过拟合哪个最优？问题过拟合28问题一旦找到边界，就停止，不是最优问题一旦找到边界，就停止，不是最优29SVMSVM30问题寻找最佳的线性分割问题寻找最佳的线性分割31最大化MarginMargin到分割平面的距离，越宽越好最优分割平面最大化MarginMargin32SVM改进Perceptron的问题：最大化MarginSVM改进Perceptron的问题：最大化Margin33Margin的数学描述A在B上的投影点积Margin的数学描述A在B上的投影点积34MarginAM在w上的投影M在L上MarginAM在w上的投影M在L上35最大化Margin即：最大化Margin即：36SVM求最佳分割平面最佳分割平面由支持向量决定d维X，一般有d+1个支持向量其他点可以忽略SVM求最佳分割平面最佳分割平面由支持向量决定37归一化最佳分割平面w，b加倍，margin也加倍，不好找Max加约束

||W||=1给b也加一个约束，支持向量xi在上面等于1/-1归一化最佳分割平面w，b加倍，margin也加倍，不好找Ma38归一化结果归一化结果39最小化||W||优化问题转化最小化||W||优化问题转化40优化最小化||W||SVMwith“hard”约束即：优化最小化||W||41优化训练集最优解:优化训练集最优解:42不能线性分割引入惩罚：离边界的距离优化问题转化为不能线性分割引入惩罚：离边界的距离43惩罚因子CC大：Care，惩罚大C=0:无所谓也叫惩罚因子CC大：Care，惩罚大44惩罚函数Z离边界的距离惩罚函数Z离边界的距离45优化Matlab求解BigData时，求解困难最小化Convex函数GradientDescent（梯度下降）递归优化Matlab求解46惩罚函数的导数如果y=1如果y=-1总结惩罚函数的导数如果y=147小结：梯度下降法目标：求w，最小化梯度下降，调整w梯度小结：梯度下降法目标：求w，最小化48SVMSVM49例C=0.1，b作为一个W，参与优化，初始W=[0,1],b=-2b对应的样本值为1训练集例C=0.1，50获得惩罚函数导数表代入训练集获得惩罚函数导数表代入训练集51计算梯度代入初始w=[u,v,b]=[0,1,-2]，过一遍表，得到第二行不满足获得梯度计算梯度代入初始w=[u,v,b]=[0,1,-2]，过52更新w重复扫描惩罚函数表，计算梯度调整权重MapReducMap管不同的惩罚函数行Reduce加起来，获得梯度更新w53问题调整一次W，对所有样本都过一遍StochasticGradientDescent翻过来:对每个样本（共n个），把各维更新一遍问题调整一次W，对所有样本都过一遍54性能评估LeonBottou文本分类ReutersRCV1文档Trainset：n=781,000（文档）Testset:23,000d=50,000features（单词）移走禁用词stop-words移走低频词性能评估LeonBottou55结果速度大大提高结果速度大大提高56准确度合理的质量情况下，时间大大缩短准确度合理的质量情况下，时间大大缩短57扩展BatchConjugateGradient收敛更快SGD更简单多次SGD，比一次BCG好。扩展BatchConjugateGradient58实际需要选择和Leon建议选，使期望的初始更新和期望的权重可比选：挑少量样本尝试10,1,0.1,0.01,…选效果最好的实际需要选择和59实际当x稀疏时近似为两步因为x稀疏，所以，第一步中更新的Wi少两种方案：W=SV，S为标量，V为向量第二步频率低一些，大一些实际当x稀疏时60停止在测试集上检验在训练集上检验停止在测试集上检验61多类方法1：类似感知机训练三个分类器选多类方法1：类似感知机62多类方法2：同时学习三类权重优化问题类似地解多类方法2：同时学习三类权重63最近邻最近邻64K-NearestNeighbor(KNN)Instancebasedlearning保存整个训练集{(x,y)}新查询q寻找最近的样例根据样例，预测q的y回归/分类例：Collaborativefiltering寻找K个最相似的用户根据他们的评分，预测用户的评分K-NearestNeighbor(KNN)Instan65四要素距离Metric：最近EuclideanK的选择加权函数预测平均四要素距离Metric：最近66K=1K=9K=1K=967Kernel回归K：所有已知样本加权函数K=9Kernel回归K：所有已知样本K=968最近邻寻找算法线性扫描基于树的高维Index结构Multidimensionalindexstructures主存Quadtreekd-tree第二存储R-trees最近邻寻找算法线性扫描69高维的挑战curseofdimensionality维数诅咒两种方法VAFiles两级降维（SVD）到低维处理高维的挑战curseofdimensionality70非欧式距离ManhattandistanceJaccarddistance用LSH近似相似非欧式距离Manhattandistance71决策树DecisionTree决策树DecisionTree72决策树回归分类决策树回归73构造树构造树741)FindBestSplit–分类最大化信息增益1)FindBestSplit–分类最大化信息增益751）FindBestSplit–回归最大化对数值：Sort，然后依次检查对类型：按子集1）FindBestSplit–回归最大化762)StoppingCriteria很多启发式方法方差足够小元素足够少2)StoppingCriteria很多启发式方法773)FindPrediction回归返回叶子中元素均值返回叶子中元素线性回归分类返回叶子中元素类型3)FindPrediction回归78MapReduce实现ParallelLearnerforAssemblingNumerousEnsembleTrees[Pandaetal.,VLDB‘09]一级一个Map-ReduceMapper考虑大量可能的SplitReduce综合，决定最优SplitMapReduce实现ParallelLearnerfo79装袋Bagging采样训练集学习多个树组合其预测结果，得到更好的结果很实用的方法装袋Bagging80SVMvs.DT比较SVMvs.DT比较81ReferB.Panda,J.S.Herbach,S.Basu,andR.J.Bayardo.PLANET:MassivelyparallellearningoftreeensembleswithMapReduce.VLDB2009.J.Ye,J.-H.Chow,J.Chen,Z.Zheng.StochasticGradientBoostedDistributedDecisionTrees.CIKM2009.ReferB.Panda,J.S.Herbach,82总结机器学习Perceptron（

感知机）SVM（support-vectormachines）支持向量机最近邻（nearestneighbor）决策树总结机器学习83大数据存储与应用

大规模机器学习课程主页：http:///?page_id=397陈一帅chenyishuai@大数据存储与应用

大规模机器学习84介绍机器学习定义Perceptron（

感知机）SVM（support-vectormachines）支持向量机最近邻（nearestneighbor）决策树介绍机器学习定义85机器学习训练集

（X,y）X：featurevectory:label目的：找到一个函数：y=f(X)发现规律，预测未来y类型实数：Regression布尔值：二元分类有限取值：多元分类无限取值：句子机器学习训练集（X,y）86狗狗分类奇瓦瓦狗（体小，毛平滑）小猎兔狗腊肠犬X:高度，重量y:狗的种类狗狗分类奇瓦瓦狗（体小，毛平滑）小猎兔狗腊肠犬X:高度，87文本分类根据email的内容，判断是否垃圾邮件根据新闻内容，判断新闻类型SportPoliticsFeaturevector单词向量（1，0）文本分类根据email的内容，判断是否垃圾邮件88常用方法无监督学习聚类有监督学习决策树感知机：PerceptronsSVM支持向量机神经元网络无循环感知机网络基于事例的学习Instance-basedlearningKNN常用方法无监督学习89模型元素训练集测试集分类器问题：Overfit模型元素90工作方式BatchlearningOnlinelearning象Stream来一个处理一个，更新分类器能够处理大训练集工作方式Batchlearning91应用快递获单预测X：出价，起点，终点y：接受/拒绝Online算法持续收集新数据，不断更新模型应用快递获单预测92感知机感知机93感知机神经元刺激是输入的加权和感知机神经元94感知机输入：实数向量输出：1/-1例：垃圾邮件检测Instance空间类型输入：X输出：y感知机输入：实数向量Instance空间类型输入：X输出：95模型目标：找到合适的使0模型目标：096几何描述W和X向量的点积（余弦距离）wx>0wx<0几何描述W和X向量的点积（余弦距离）wx>0wx<97求W初始化为全0来一个x，算如果y=y’，W保持不变如果y!=y，往yx的方向旋转一点求W初始化为全098旋转的效果y(x1)=1却被判为了-1W往x1方向转一点W+cyx1判断平面逆时针旋转一点试图把x1包进来旋转的效果y(x1)=199收敛性只要是线性可分割的，就会收敛如果不是，最后会震荡，无限循环收敛性只要是线性可分割的，就会收敛100震荡时的停止算法震荡时，如何停止算法？逐渐减小调整幅度观察训练集上的误差观察一个小测试集上的误差限制最大迭代次数震荡时的停止算法震荡时，如何停止算法？101非零判决平移非零判决平移102多类感知超过两类分别训练三个分类器谁的wx值最大，算谁多类感知超过两类谁的wx值最大，算谁103Winnow算法总会收敛x取值：0，1初始化w

全1，为x的长度预测预测对，w不动预测错：y真值是1，可，说明w太小，看x中哪些值为1，把对应的w加倍y真值是-1，可，说明w太大，看x中哪些值为1，把对应的w减半Winnow算法总会收敛104的调整把它加到w里，一起变允许对应的x为-1，但调整方法反过来：预测错：y真值是1，，说明

太大，减半y真值是-1，，说明

太小，加倍的调整把它加到w里，一起变允许对应的x为105扩展平衡Winnow（BalancedWinnow）ThickSeparator界限（Margin）放松扩展平衡Winnow（BalancedWinnow）106非线性边界变换到线性上非线性边界变换到线性上107Map-Reduce的实现每个机器处理部分xMap：如果出错，生成键值对（i,cyxi)表示要对wi进行调整c为调整速度Reduce累积，实现对w的调整重复，直到收敛，或到达停止的条件Map-Reduce的实现每个机器处理部分x108感知机总结感知机加法更新w适合x少，互相有相关性Winnonw乘法更新w适合x多，互相无相关性感知机总结感知机109感知机总结是一种Online算法新(x,y)到达，更新w局限线性分割线性不可分的话，不收敛Feature多时，效果一般感知机总结是一种Online算法110问题过拟合哪个最优？问题过拟合111问题一旦找到边界，就停止，不是最优问题一旦找到边界，就停止，不是最优112SVMSVM113问题寻找最佳的线性分割问题寻找最佳的线性分割114最大化MarginMargin到分割平面的距离，越宽越好最优分割平面最大化MarginMargin115SVM改进Perceptron的问题：最大化MarginSVM改进Perceptron的问题：最大化Margin116Margin的数学描述A在B上的投影点积Margin的数学描述A在B上的投影点积117MarginAM在w上的投影M在L上MarginAM在w上的投影M在L上118最大化Margin即：最大化Margin即：119SVM求最佳分割平面最佳分割平面由支持向量决定d维X，一般有d+1个支持向量其他点可以忽略SVM求最佳分割平面最佳分割平面由支持向量决定120归一化最佳分割平面w，b加倍，margin也加倍，不好找Max加约束

||W||=1给b也加一个约束，支持向量xi在上面等于1/-1归一化最佳分割平面w，b加倍，margin也加倍，不好找Ma121归一化结果归一化结果122最小化||W||优化问题转化最小化||W||优化问题转化123优化最小化||W||SVMwith“hard”约束即：优化最小化||W||124优化训练集最优解:优化训练集最优解:125不能线性分割引入惩罚：离边界的距离优化问题转化为不能线性分割引入惩罚：离边界的距离126惩罚因子CC大：Care，惩罚大C=0:无所谓也叫惩罚因子CC大：Care，惩罚大127惩罚函数Z离边界的距离惩罚函数Z离边界的距离128优化Matlab求解BigData时，求解困难最小化Convex函数GradientDescent（梯度下降）递归优化Matlab求解129惩罚函数的导数如果y=1如果y=-1总结惩罚函数的导数如果y=1130小结：梯度下降法目标：求w，最小化梯度下降，调整w梯度小结：梯度下降法目标：求w，最小化131SVMSVM132例C=0.1，b作为一个W，参与优化，初始W=[0,1],b=-2b对应的样本值为1训练集例C=0.1，133获得惩罚函数导数表代入训练集获得惩罚函数导数表代入训练集134计算梯度代入初始w=[u,v,b]=[0,1,-2]，过一遍表，得到第二行不满足获得梯度计算梯度代入初始w=[u,v,b]=[0,1,-2]，过135更新w重复扫描惩罚函数表，计算梯度调整权重MapReducMap管不同的惩罚函数行Reduce加起来，获得梯度更新w136问题调整一次W，对所有样本都过一遍StochasticGradientDescent翻过来:对每个样本（共n个），把各维更新一遍问题调整一次W，对所有样本都过一遍137性能评估LeonBottou文本分类ReutersRCV1文档Trainset：n=781,000（文档）Testset:23,000d=50,000features（单词）移走禁用词stop-words移走低频词性能评估LeonBottou138结果速度大大提高结果速度大大提高139准确度合理的质量情况下，时间大大缩短准确度合理的质量情况下，时间大大缩短140扩展BatchConjugateGradient收敛更快SGD更简单多次SGD，比一次BCG好。扩展BatchConjugateGradient141实际需要选择和Leon建议选，使期望的初始更新和期望的权重可比选：挑少量样本尝试10,1,0.1,0.01,…选效果最好的实际需要选择和142实际当x稀疏时近似为两步因为x稀疏，所以，第一步中更新的Wi少两种方案：W=SV，S为标量，V为向量第二步频率低一些，大一些实际当x稀疏时143停止在测试集上检验在训练集上检验停止在测试集上检验144多类方法1：类似感知机训练三个分类器选多类方法1：类似感知机145多类方法2：同时学习三类权重优化问题类似地解多类方法2：同时学习三类权重146最近邻最近邻147K-NearestNeighbor(KNN)Instancebasedlearning保存整个训练集{(x,y)}新查询q寻找最近的样例根据样例，预测q的y回归/分类例：Collaborativefiltering寻找K个最相似的用户根据他们的评分，预测用户的评分K-NearestNeighbor(KNN)Instan148四要素距离Metric：最近EuclideanK的选择加权函数预测平均四要素距离Metric：最近149K=1K=9K=1K=9150Kernel回归K：所有已知样本加权函数K=9Kernel回归K：所有已知样本K=9151最近邻寻找算法线性扫描基于树的高维Index结构Multidimensionalindexstructures主存Quadtreekd-tree第二存储R-trees最近邻寻找算法线性扫描152高维的挑战curseofdimensionality维数诅