大数据存储跟处理-大规模机器学习.ppt

大数据存储与应用大规模机器学习 课程主页：/?page_id=397 陈一帅 chenyishuai@ 介绍 机器学习定义 Perceptron （ 感知机） SVM（ support-vector machines）支持向量机 最近邻（ nearest neighbor） 决策树 机器学习 训练集 （X, y） X：feature vector y: label 目的： 找到一个函数：y = f(X) 发现规律，预测未来 y类型 实数：Regression 布尔值：二元分类 有限取值：多元分类 无限取值：句子 狗狗分类 奇瓦瓦狗（体小，毛平滑） 小猎兔狗 腊肠犬 X: 高度，重量 y: 狗的种类 文本分类 根据email的内容，判断是否垃圾邮件 根据新闻内容，判断新闻类型 Sport Politics Feature vector 单词向量（1，0） 常用方法 无监督学习 聚类 有监督学习 决策树 感知机：Perceptrons SVM 支持向量机 神经元网络 无循环感知机网络 基于事例的学习 Instance-based learning KNN 模型 元素 训练集 测试集 分类器 问题：Overfit 工作方式 Batch learning Online learning 象Stream 来一个处理一个，更新分类器 能够处理大训练集 应用 快递获单预测 X：出价，起点，终点 y：接受/拒绝 Online算法 持续收集新数据，不断更新模型 感知机 感知机 神经元 刺激是输入的加权和 感知机 输入：实数向量 输出：1/-1 例：垃圾邮件检测 Instance 空间 类型 输入：X 输出：y 模型 目标： 找到合适的 使 0 几何描述 W和X向量的点积 （余弦距离） wx 0 wx 0 求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 （Balanced Winnow） Thick Separator 界限（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的问题：最大化Margin Margin的数学描述 A在B上的投影 点积 Margin AM在w上的投影 M在L上 最大化Margin 即： SVM求最佳分割平面 最佳分割平面由支持向量决定 d维X，一般有d+1个支持向量 其他点可以忽略 归一化最佳分割平面 w，b加倍，margin也加倍，不好找Max 加约束 ||W|| = 1 给b也加一个约束，支持向量xi在上面等于1/-1 归一化结果 最小化||W|| 优化问题转化 优化 最小化||W|| SVM with “hard” 约束 即： 优化 训练集 最优解: 不能线性分割 引入惩罚：离边界的距离 优化问题转化为 惩罚因子C C大：Care，惩罚大 C = 0: 无所