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

大数据存储与应用大规模机器学习课程主页：@gmail.com介绍•机器学习定义•Perceptron（感知机）•SVM（support-vectormachines）支持向量机•最近邻（nearestneighbor）•决策树机器学习•训练集（X,y）•X：featurevector•y:label•目的：•找到一个函数：y=f(X)•发现规律，预测未来•y类型•实数：Regression•布尔值：二元分类•有限取值：多元分类•无限取值：句子狗狗分类奇瓦瓦狗（体小，毛平滑）小猎兔狗腊肠犬X:高度，重量y:狗的种类文本分类•根据email的内容，判断是否垃圾邮件•根据新闻内容，判断新闻类型•Sport•Politics•Featurevector•单词向量（1，0）常用方法•无监督学习•聚类•有监督学习•决策树•感知机：Perceptrons•SVM支持向量机•神经元网络•无循环感知机网络•基于事例的学习Instance-basedlearning•KNN模型•元素•训练集•测试集•分类器•问题：Overfit工作方式•Batchlearning•Onlinelearning•象Stream•来一个处理一个，更新分类器•能够处理大训练集应用•快递获单预测•X：出价，起点，终点•y：接受/拒绝•Online算法•持续收集新数据，不断更新模型感知机感知机•神经元•刺激是输入的加权和感知机•输入：实数向量•输出：1/-1•例：垃圾邮件检测Instance空间类型输入：X输出：y模型•目标：•找到合适的•使0几何描述•W和X向量的点积（余弦距离）wx0wx0求W•初始化为全0•来一个x，算•如果y=y’，W保持不变•如果y!=y，往yx的方向旋转一点旋转的效果•y(x1)=1•却被判为了-1•W往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的实现•每个机器处理部分x•Map：•如果出错，生成键值对（i,cyxi)表示要对wi进行调整•c为调整速度•Reduce•累积，实现对w的调整•重复，直到收敛，或到达停止的条件感知机总结•感知机•加法更新w•适合x少，互相有相关性•Winnonw•乘法更新w•适合x多，互相无相关性感知机总结•是一种Online算法•新(x,y)到达，更新w•局限•线性分割•线性不可分的话，不收敛•Feature多时，效果一般问题•过拟合•哪个最优？问题一旦找到边界，就停止，不是最优SVM问题•寻找最佳的线性分割最大化Margin•Margin•到分割平面的距离，越宽越好•最优分割平面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”约束即：优化•训练集最优解:不能线性分割•引入惩罚：离边界的距离•优化问题转化为惩罚因子C•C大：Care，惩罚大•C=0:无所谓•也叫惩罚函数Z离边界的距离优化•Matlab求解•BigData时，求解困难•最小化•Convex函数•GradientDescent（梯度下降）•递归惩罚函数的导数•如果y=1•如果y=-1•总结小结：梯度下降法•目标：求w，最小化•梯度下降，调整w•梯度SVM例•C=0.1，•b作为一个W，参与优化，•初始W=[0,1],b=-2•b对应的样本值为1训练集获得惩罚函数导数表代入训练集计算梯度•代入初始w=[u,v,b]=[0,1,-2]，过一遍表，得到•第二行不满足•获得梯度更新w•重复•扫描惩罚函数表，•计算梯度•调整权重•MapReduc•Map管不同的惩罚函数行•Reduce加起来，获得梯度问题•调整一次W，对所有样本都过一遍•StochasticGradientDescent•翻过来:对每个样本（共n个），把各维更新一遍性能评估•LeonBottou•文本分类•ReutersRCV1文档•Trainset：n=781,000（文档）•Testset:23,000•d=50,000features（单词）•移走禁用词stop-words•移走低频词结果•速度大大提高准确度•合理的质量情况下，时间大大缩短扩展•BatchConjugateGradient•收敛更快•SGD•更简单•多次SGD，比一次BCG好。实际•需要选择和•Leon建议•选，使期望的初始更新和期望的权重可比•选：•挑少量样本•尝试10,1,0.1,0.01,…•选效果最好的实际•当x稀疏时•近似为两步•因为x稀疏，所以，第一步中更新的Wi少•两种方案：1.W=SV，S为标量，V为向量2.第二步频率低一些，大一些停止•在测试集上检验•在训练集上检验多类•方法1：类似感知机•训练三个分类器•选多类•方法2：同时学习三类权重•优化问题•类似地解最近邻K-NearestNeighbor(KNN)•Instancebasedlearning•保存整个训练集{(x,y)}•新查询q•寻找最近的样例•根据样例，预测q的y•回归/分类•例：Collaborativefiltering•寻找K个最相似的用户•根据他们的评分，预测用户的评分四要素•距离Metric：最近•Euclidean•K的选择•加权函数•预测•平均K=1K=9Kernel回归•K：所有已知样本•加权函数K=9最近邻寻找算法•线性扫描•基于树的高维Index结构•Multidimensionalindexstructures•主存•Quadtree•kd-tree•第二存储•R-trees高维的挑战•curseofdimensionality•维数诅咒•两种方法•VAFiles•两级•降维（SVD）•到低维处理非欧式距离•Manhattandistance•Jaccarddistance•用LSH•近似相似决策树DecisionTree决策树•回归•分类构造树1)FindBestSplit–分类•最大化信息增益1）FindBestSplit–回归•最大化•对数值：Sort，然后依次检查•对类型：按子集2)StoppingCriteria•很多启发式方法•方差足够小•元素足够少3)FindPrediction•回归•返回叶子中元素均值•返回叶子中元素线性回归•分类•返回叶子中元素类型MapReduce实现•ParallelLearnerforAssemblingNumerousEnsembleTrees[Pandaetal.,VLDB‘09]•一级一个Map-Reduce•Mapper考虑大量可能的Split•Reduce综合，决定最优Split装袋•Bagging•采样训练集•学习多个树•组合其预测结果，得到更好的结果•很实用的方法SVMvs.DT比较Refer•B.Panda,J.S.Herbach,S.Basu,andR.J.Bayardo.PLANET:MassivelyparallellearningoftreeensembleswithMapReduce.VLDB2009.•J.Ye,J.-H.Chow,J.Chen,Z.Zheng.StochasticGradientBoostedDistributedDecisionTrees.CIKM2009.总结•机器学习•Perceptron（感知机）•SVM（support-vectormachines）支持向量机•最近邻（nearestneighbor）•决策树