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

1、大数据存储与应用大数据存储与应用大规模机器学习大规模机器学习课程主页：http:/ 机器学习定义 Perceptron （ 感知机） SVM（ support-vector machines）支持向量机 最近邻（ nearest neighbor） 决策树机器学习 训练集 （X, y） X：feature vector y: label 目的： 找到一个函数：y = f(X) 发现规律，预测未来 y类型 实数：Regression 布尔值：二元分类 有限取值：多元分类 无限取值：句子狗狗分类奇瓦瓦狗（体小，毛平滑）小猎兔狗腊肠犬X: 高度，重量y: 狗的种类文本分类 根据email的内容，判断

2、是否垃圾邮件 根据新闻内容，判断新闻类型 Sport Politics Feature vector 单词向量（1，0）常用方法 无监督学习 聚类 有监督学习 决策树 感知机：Perceptrons SVM 支持向量机 神经元网络 无循环感知机网络 基于事例的学习 Instance-based learning KNN模型 元素 训练集 测试集 分类器 问题：Overfit工作方式 Batch learning Online learning 象Stream 来一个处理一个，更新分类器 能够处理大训练集应用 快递获单预测 X：出价，起点，终点 y：接受/拒绝 Online算法 持续收集新数据，

3、不断更新模型感知机感知机 神经元 刺激是输入的加权和感知机 输入：实数向量 输出：1/-1 例：垃圾邮件检测Instance 空间类型输入：X输出：y模型 目标： 找到合适的 使0几何描述 W和X向量的点积 （余弦距离）wx 0wx 0求W 初始化为全0 来一个x，算 如果y=y，W保持不变 如果y!=y，往yx的方向旋转一点旋转的效果 y(x1) = 1 却被判为了-1 W往x1方向转一点 W + cyx1 判断平面逆时针旋转一点 试图把x1包进来收敛性 只要是线性可分割的，就会收敛 如果不是，最后会震荡，无限循环震荡时的停止算法 震荡时，如何停止算法？ 逐渐减小调整幅度 观察训练集上的误差

4、 观察一个小测试集上的误差 限制最大迭代次数非零判决平移多类感知 超过两类 分别训练三个分类器谁的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 （Balanced Winnow） Thick Separator 界限（Ma

5、rgin） 放松非线性边界 变换到线性上Map-Reduce的实现 每个机器处理部分x Map： 如果出错，生成键值对（i, cyxi) 表示要对wi进行调整 c为调整速度 Reduce 累积，实现对w的调整 重复，直到收敛，或到达停止的条件感知机总结感知机 加法更新w 适合x少，互相有相关性Winnonw 乘法更新w 适合x多，互相无相关性感知机总结是一种Online算法 新(x,y)到达，更新w局限 线性分割 线性不可分的话，不收敛 Feature多时，效果一般问题 过拟合 哪个最优？问题一旦找到边界，就停止，不是最优SVM问题 寻找最佳的线性分割最大化MarginMargin 到分割平面

6、的距离，越宽越好 最优分割平面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|SVM with “hard” 约束即：优化 训练集最优解:不能线性分割 引入惩罚：离边界的距离 优化问题转化为惩罚

7、因子C C大：Care，惩罚大 C = 0: 无所谓 也叫惩罚函数Z离边界的距离优化 Matlab求解 Big Data时，求解困难 最小化 Convex函数 Gradient Descent （梯度下降） 递归惩罚函数的导数 如果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 重复 扫描惩罚函数表，

8、 计算梯度 调整权重 MapReduc Map管不同的惩罚函数行 Reduce加起来，获得梯度问题调整一次W，对所有样本都过一遍Stochastic Gradient Descent 翻过来:对每个样本（共n个），把各维更新一遍性能评估 Leon Bottou 文本分类 Reuters RCV1文档 Train set： n = 781,000 （文档） Test set: 23,000 d = 50,000 features （单词） 移走禁用词 stop-words 移走低频词结果 速度大大提高准确度 合理的质量情况下，时间大大缩短扩展Batch Conjugate Gradient 收敛

9、更快SGD 更简单多次SGD，比一次BCG好。实际 需要选择 和 Leon建议 选 ，使期望的初始更新和期望的权重可比 选 ： 挑少量样本 尝试10, 1, 0.1, 0.01, 选效果最好的实际 当x稀疏时 近似为两步 因为x稀疏，所以，第一步中更新的Wi少 两种方案：1. W = SV，S为标量，V为向量2. 第二步频率低一些， 大一些停止 在测试集上检验 在训练集上检验多类 方法1：类似感知机 训练三个分类器 选多类 方法2：同时学习三类权重 优化问题 类似地解最近邻K-Nearest Neighbor (KNN) Instance based learning 保存整个训练集 (x,y

10、) 新查询q 寻找最近的样例 根据样例，预测q的y 回归/分类 例：Collaborative filtering 寻找K个最相似的用户 根据他们的评分，预测用户的评分四要素 距离Metric：最近 Euclidean K的选择 加权函数 预测 平均K=1K=9Kernel回归 K：所有已知样本 加权函数K=9最近邻寻找算法线性扫描基于树的高维Index结构 Multidimensional index structures主存 Quadtree kd-tree第二存储 R-trees高维的挑战curse of dimensionality 维数诅咒两种方法 VA Files 两级 降维（SV

11、D） 到低维处理非欧式距离Manhattan distanceJaccard distance 用LSH 近似相似决策树Decision Tree决策树回归分类构造树1) FindBestSplit 分类 最大化信息增益1）FindBestSplit 回归 最大化 对数值：Sort，然后依次检查 对类型：按子集2) StoppingCriteria 很多启发式方法 方差足够小 元素足够少3) FindPrediction 回归 返回叶子中元素均值 返回叶子中元素线性回归 分类 返回叶子中元素类型MapReduce实现 Parallel Learner for Assembling Numerous Ensemble Trees Panda et al., VLDB 09 一级一个Map-Reduce Mapper考虑大量可能的Split Reduce综合，决定最优Split装袋 Bagging 采样训练集 学习多个树 组合其预测结果，得到更好的结果 很实用的方法SVM vs. DT 比较Refer B. Panda, J. S. Herbach, S. Basu, and R. J. Bayardo. PLANET: Massively parallel learning of tree ensembles with MapReduce. VLDB 2009. J.