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

大数据存储与应用

大规模机器学习课程主页：httppage_id=397陈一帅介绍机器学习定义Perceptron（

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

（X,y）X：featurevectory:label目的：找到一个函数：y=f(X)发现规律，预测未来y类型实数：Regression布尔值：二元分类有限取值：多元分类无限取值：句子狗狗分类奇瓦瓦狗（体小，毛平滑）小猎兔狗腊肠犬X:高度，重量y:狗的种类文本分类根据email的内容，判断是否垃圾邮件根据新闻内容，判断新闻类型SportPoliticsFeaturevector单词向量（1，0）常用方法无监督学习聚类有监督学习决策树感知机：PerceptronsSVM支持向量机神经元网络无循环感知机网络基于事例的学习Instance-basedlearningKNN模型元素训练集测试集分类器问题：Overfit工作方式BatchlearningOnlinelearning象Stream来一个处理一个，更新分类器能够处理大训练集应用快递获单预测X：出价，起点，终点y：接受/拒绝Online算法持续收集新数据，不断更新模型感知机感知机神经元刺激是输入入的加权和和感知机输入：实数数向量输出：1/-1例：垃圾邮邮件检测Instance空间类型输入：X输出：y模型目标：找到合适的的使0几何描述W和X向量的点积积（余弦弦距离）wx>0wx<0求W初始化为全全0来一个x，算如果y=y’，W保持不变如果y!=y，往yx的方向旋转转一点旋转的效果果y(x1)=1却被判为了了-1W往x1方向转一点W+cyx1判断平面逆时针旋转转一点试图把x1包进来收敛性只要是线性性可分割的的，就会收收敛如果不是，，最后会震震荡，无限限循环震荡时的停停止算法震荡时，如如何停止算算法？逐渐减小调调整幅度观察训练集集上的误差差观察一个小小测试集上上的误差限制最大迭迭代次数非零判决平移多类感知超过两类分别训练三三个分类器器谁的wx值最大，算谁Winnow算法总会收敛x取值：0，1初始化w全1，为为x的长度预测预测对，w不动预测错：y真值是1，可，，说说明w太小，看x中哪些值为为1，把对应的的w加倍y真值是-1，可，，说明w太大，看x中哪些值为为1，把对应的的w减半的调整把它加到w里，一起变变允许对对应的x为-1，但调整方方法反过来来：预测错：y真值是1，，，说明太大，减半y真值是-1，，说说明太小，加倍扩展平衡Winnow（BalancedWinnow）ThickSeparator界限（Margin）放松非线性边界界变换到线性性上Map-Reduce的实现每个机器处处理部分xMap：如果出错，，生成键值值对（i,cyxi)表示要对wi进行调整c为调整速度度Reduce累积，实现现对w的调整重复，直到收敛敛，或到达达停止的条条件感知机总结结感知机加法更新w适合x少，互相有有相关性Winnonw乘法更新w适合x多，互相无无相关性感知机总结结是一种Online算法新(x,y)到达，更新新w局限线性分割线性不可分分的话，不不收敛Feature多时，效果果一般问题过拟合哪个最优？？问题一旦找到边边界，就停停止，不是是最优SVM问题寻找最佳的的线性分割割最大化MarginMargin到分割平面面的距离，越宽宽越好最优分割平平面SVM改进Perceptron的问题：最最大化MarginMargin的数学描述述A在B上的投影点积MarginAM在w上的投影M在L上最大化Margin即：SVM求最佳分割割平面最佳分割平平面由支持向量决定d维X，一般有d+1个支持向量量其他点可以以忽略归一化最佳佳分割平面面w，b加倍，margin也加倍，不不好找Max加约束||W||=1给b也加一个约约束，支持持向量xi在上面等于于1/-1归一化结果最小化||W||优化问题转转化优化最小化||W||SVMwith““hard”约束即：优化训练集最优解:不能线性分割引入惩罚：：离边界的的距离优化问题转转化为惩罚因子CC大：Care，惩罚大C=0:无所谓也叫惩罚函数Z离边界的距距离优化Matlab求解BigData时，求解困困难最小化Convex函数GradientDescent（梯度下降降）递归惩罚函数的的导数如果y=1如果y=-1总结小结：梯度度下降法目标：求w，最小化梯度下降，，调整w梯度SVM例C=0.1，b作为一个W，参与优化化，初始W=[0,1],b=-2b对应的样本本值为1训练集获得得惩惩罚罚函函数数导数数表代入入训练练集集计算算梯梯度度代入入初初始始w=[u,v,b]=[0,1,-2]，过过一一遍遍表表，，得得到到第二二行行不不满满足足获得得梯梯度度更新新w重复复扫描描惩惩罚罚函函数数表表，，计算算梯梯度度调整整权权重重MapReducMap管不不同同的的惩惩罚罚函函数数行行Reduce加起起来来，，获获得得梯梯度度问题题调整整一一次次W，对对所所有有样样本本都都过过一一遍遍StochasticGradientDescent翻过过来来:对每个样样本（共共n个），把把各维更更新一遍遍性能评估LeonBottou文本分类类ReutersRCV1文档Trainset：n=781,000（文档））Testset:23,000d=50,000features（单词））移走禁用用词stop-words移走低频频词结果速度大大大提高准确度合理的质质量情况况下，时时间大大大缩短扩展BatchConjugateGradient收敛更快快SGD更简单多次SGD，比一次次BCG好。实际需要选择择和和Leon建议选，，使使期望的的初始更更新和期期望的权权重可比比选：：挑少量样样本尝试10,1,0.1,0.01,……选效果最最好的实际当x稀疏时近似为两两步因为x稀疏，所所以，第第一步中中更新的的Wi少两种方案案：W=SV，S为标量，，V为向量第二步频频率低一一些，大大一些停止在测试集集上检验验在训练集集上检验验多类方法1：类似感感知机训练三个个分类器器选多类方法2：同时学学习三类类权重优化问题题类似地解解最近邻K-NearestNeighbor(KNN)Instancebasedlearning保存整个个训练集集{(x,y)}新查询q寻找最近近的样例例根据样例例，预测测q的y回归/分类例：Collaborativefiltering寻找K个最相似似的用户户根据他们们的评分分，预测测用户的的评分四要素距离Metric：最近EuclideanK的选择加权函数数预测平均K=1K=9Kernel回归K：所有已已知样本本加权函数数K=9最近邻寻寻找算法线性扫描描基于树的高维维Index结构Multidimensionalindexstructures主存Quadtreekd-tree第二存储储R-trees高维的挑挑战curseofdimensionality维数诅咒咒两种方法法VAFiles两级降维（SVD）到低维处处理非欧式距距离ManhattandistanceJaccarddistance用LSH近似相似似决策树DecisionTree决策树回归分类构造树1)FindBestSplit–分类最大化信信息增益益1）FindBestSplit–回归最大化对数值：：Sort，然后依依次检查查对类型：：按子集集2)StoppingCriteria很多启发发式方法法方差足够够小元素足够够少3)FindPrediction回归返回叶子中元元素均值值返回叶子中元素线性性回归分类返回叶子中元素类型型MapReduce实现ParallelLearnerforAssemblingNumerousEnsembleTrees[Pandaetal.,VLDB‘09]一级一个个Map-ReduceMapper考虑大量量可能的的SplitReduce综合，决决定最优优Split装袋Bagging采样训练练集学习多个个树组合其预预测结果果，得到到更好的的结果很实用的的方法SVMvs.DT比较ReferB.Panda,J.S.Herbach,S.Basu,andR.J.Bayardo.PLANET:Massivelyparallellearningoftree