机器学习总结

精品文档 2016 全新精品资料 全程指导写作 独家原创 1 / 144 机器学习总结 篇一：机器学习总结 目录前言 . 2 . 2 . 3 . 5 . 8 .2016 全新精品资料 全程指导写作 独家原创 2 / 144 . 13 . 15 . 16 . 17 . 18 . 21 . 22 .2016 全新精品资料 全程指导写作 独家原创 3 / 144 . 23 . 24 . 24 . 24 . 24 . 26 . 27 .2016 全新精品资料 全程指导写作 独家原创 4 / 144 . 28 . 28 . 28 . 29 . 29 . 30 . 31 .2016 全新精品资料 全程指导写作 独家原创 5 / 144 . 33 CF as . 34 CF as . 351精品文档 2016 全新精品资料 全程指导写作 独家原创 6 / 144 前言花了将近四个月时间， 终于把机器学习最基本的东西大致过了一遍了， 这中间还包括一个多 月的时间用于复习数学了 （坑爹啊） 很久没有花这么大的精力学一样东西了， ， 很高兴的是， 在比较深入的去了解后，我还没有对机器学习失去兴趣 ?，这至少说明，这个东 西是真真正 正吸引我的。 这阵子杂七杂八的看了不少东西， 为了避免以后全还回去了， 我决定一边复习一边写个总结， 把这些七七八八的东西都塞一块儿吧。 这里涵盖了绝大多数我学过的机器学习相关的东西，有一些算法可能被我略过去了，比如 次聚类，冠冕堂皇的原因是这些算法比较简单，相信不那么容易忘 记，其实真正的原因是写到最后实在疲了，懒得继续了 我最初对机器学习产生兴趣是源于吴军博士的数学之美 ，不能不说这本书实在是真好， 反正我是结结实实 的上套了，另外一个比较幸运的事情是，在我刚决定学习机器学习时，正 好有一家叫“培乐园”的针对互联网高端技术的培训机构开张了，我也有幸成为了第一批学 员，不得不说培乐园在机器学习方面对我的影响和数学之美一样巨大，正是蒋龙老师的 课程让我了解了机器学习的框架， 从而在后面的学习中不至于像无头苍蝇似的到处乱撞， 另 精品文档 2016 全新精品资料 全程指导写作 独家原创 7 / 144 外， g 和龙星计划的机器学习课程对我帮助也都非常的大，感谢这些无私分享的老 师们！ 最后，作为机器学习的菜鸟，我只能说，路漫漫其修远兮，努力吧！ 基于贝叶斯定理和条件独立性假设的分类器，贝叶斯定理简单的说就是已知条件概率 p(x|y)和先验概率 p(y)的情况下求 p(y|x)的方法，因为有些时候计算 p(x|y)和 p(y)比较容易， 而计算 p(y|x)很困难，这时候就可以通过贝叶斯定理将困难的问题转化为简单问题解决，从 另一个角度看，贝叶斯定理也可以理解为通过生成模型 p(x, y)求解判别模型 p(y|x)的方法， 这里就必须提到条件独立性假设了，因为 生成模型，也就是对联合概率分布 p(x,y)= p(x|y) *p(y)建模，由于 x 的结构一般很复杂，直接建模会很困难，因此几乎所有的生成模型 都对 x 的结构做了一定的假设， 的假设是在给定 y 的前提下， x 的各个 条件 独立的（非常强的假设，也许这就是该分类器名字里 来历吧） ，这样就可以很容易 的将 p(x|y)分解为 x 的各个 件概率的乘积。 模型学习采用 里有一个 0 概率问题，就是如果训练数据中某个 (y)的组 合没有出现过的话，所有 包含该 x 属于类 y 概率会变为 0，这显然不合理，一种 2精品文档 2016 全新精品资料 全程指导写作 独家原创 8 / 144 最简单的平滑方式是 滑（即 +1 平滑，分子加 1，分母加上分子可能取值的个数） ， 这样平滑后的 p(y)仍然是一个概率分布，或者可以引入一些先验知识，比如，采用 如下的公式： (+ 这里 应的是先验知识，而 训练样本总数， 调整前的条件概率 p(y)。 对条件概率 p(y)的估计，当 值为离散值时，只需要简单的统计训练样本中 的频率即可，当 值为连续值时，有两种处理方案： 1、计算给定 y 时 均 值和方差，得到概率密度。 2、将连续值切分为多个区间，也就是将特征离散化，这样估计 方法就和离散值一样了。 很多优点，训练简单，模型易于解释，不容易 小数据集上也能工作的相 当不错，缺点就是条件独立性假 设似乎过强了一些，导致精度可能没有其它分 类 器 高 。 实就是用一条函数曲线去拟合一组数据， 文翻译叫 “回归” ， 关于这个名字，我觉得培乐园的蒋龙老师解释的非常好，数据的内在规律就像是一股力量， 拉动着我们拟合的函数曲线精品文档 2016 全新精品资料 全程指导写作 独家原创 9 / 144 “回归”到正确的位置。 基本形式是 y=wx+b，这里的 该是指对 w 的 于 x，我 们可以做变换，比如添加高次 可以拟合非线性的情况，因此，对于原始输入 x， 方程未必是线性的。 关于在 如何添加 拟合非线性情况，这就是一个很有技术含量 的活儿了（至少我不懂） ，听说过什么 的，以后再看吧，另外还有一种思 路就是做特征离散化，我的理解就是将连续值的 散成许多小区间（和前面 理连续 一种思路差不多） ，通过这种方式，可能 我们就不需要费劲的去发掘高次 ？ 关于 w 的二次函数，通过 者 方法可以得到全局最优解，当 量不是非常大时，也可以 用最小二乘法求解： ，这里解释下最小二乘法（不得不提下，要不最近线代就白复习了） ，其实，最初我们想解的 是这个方程： Ax=b（这里 x 是前面的 w） ，但由于这个方程一般 无解（一般 m 很大， n 很小，再加上有噪声，所以无解） ，无解的原因是因为 b 不在矩阵 A 的列空间中，如果我们 能把 b 映射到矩阵 A 的列空间中，显然这个方程就有解了，精品文档 2016 全新精品资料 全程指导写作 独家原创 10 / 144 那么，怎么映射呢？在满足最 小平方误差的情况下，答案显然是将 b 投影到 A 的列空间中，这样， b 和投影向量的差的长 度最小，自然就满足了最小平方误差（ A (b - = 0，也就是 b 减去它在 A 的列空间的投影 应该和 A 的每一个列向量垂直 ） 。 关于最小二乘法的另一个问题是， A A 可能不可逆，出现这 个问题有两种可能， 1、 A 的某些 3精品文档 2016 全新精品资料 全程指导写作 独家原创 11 / 144 列是完全线性相关的， 2、 m 小于 n。解决这个问题的方法是加入 L2 时求 解 式子就变成了 一举两得，我喜欢 ?。 在使用 者 解 w 时，有几个点我想提一下： 1、 训练前对每个 值做 () / s，这里 是均值， s 是标准 差， 通过这种方式可以使各个 值域类似， 这样 等高线会更 “圆” ， 收敛会更快。 2、 关于 ，对于 的取值，太大会导致震荡，无法收敛，太小会导致收敛过 慢， 因此我们需要通过多次实验来取一个合适的值， 另外对于 同的是， 不需要做动态调整，保持一个固定值即可。 3、 除了 ，还有一种 方法，这种方法 和 区别是，每次只使用 1 条或者若干条样本进行训练，该方法 不保证每次迭代 变小，但是最终一定能收敛到全局最优值附近，非常适 合大数据情况下的模型训练（属于 ，时候 会有 一个解决办法是动态调整 ， 比如设置 精品文档 2016 全新精品资料 全程指导写作 独家原创 12 / 144 =4/(1.0+ 外一个要注意的地方就是在每轮迭代时对训练样本做随机排序。 关于 的参数项 b， 它的一个作用是，调节误差项的均值， 因为对于 说，要求误差项是均值为 0 的高斯分布，这时候 b 就刚好可以做这个调节。 ，另外还顺带解决了 问题，真是另外， 估计误差项的方差时， 我们采用如下的公式：， 这里的 p 是 数，这也 说明 了，模型 总是 倾向 于 ，而且当 多时，越容易 想提下的还有 从 名 字 可 以 看 出 ， 它就是加上了权重的 那么权重怎么计算呢？简单的说就是， 离待预测的点越近权重越大， 否则越小， 而 且 权 重 的 衰 减 呈 高 斯 分 布 ， ： ，权重是：，采用最小二乘法的计算公式是： 里 W 是一个对角 矩阵） ，这应该算是一种无参数方法吧，有点像 点就是，每来一个待预测的数据， 都得重新 个 这里还想记下的一个问题是，训练一个模型需要多少数据究竟是由什么因素决定的？比如， 两个 品文档 2016 全新精品资料 全程指导写作 独家原创 13 / 144 型的参数个数一样，那它们训练需要的数据一定是一样多吗？是不 是还和数据的分布有关呢？这个问题我也没想清楚，可能得等了解 后再说 吧。 接下来说 实就是在 套了一个 是这两个模型的作用就完全不一样了， 要用于预测 连续值，用于回归问题，而 要用于预测 0，用于分类，且输出的是 概率值（属于概率模型，这点和 一样） 。4精品文档 2016 全新精品资料 全程指导写作 独家原创 14 / 144 一个有意思的事情是， p(y=1|x)/p(y=0|x)=个值叫做几率，解释了 含义。 学习采用 大似然估计， 的是， 对其求导后， 梯度函数 它们俩的 h(x)完全不同了哦） 。 ，有趣 外形和 分相似 （注意， 应该是初学机器学习最重要的两个问题了，放在一起说吧。 当我们做模型训练时，数据一般分为 练的目标有两个： 1、 模型能良好的拟合 2、 模型在 的表现应该和 近。 先上图：结合该图可以看出，当 大（模型比较简单）时，模型在 的 表现都很差， 但此时两者比较接近， 这就是 而当 大 （模型比较复杂） 时，模型在 表现很好，而在 表现很差，这就是 此， 我们需要在 做一个权衡，以期获得最好的模型，这就是 意义。 在这里模型复杂度不单单指模型本身， 而是 O(d/n)， 精品文档 2016 全新精品资料 全程指导写作 独家原创 15 / 144 是模型的参数空间， 是训练样本数， d n 所以，即使模型参数非常多，但如果训练样本也非常多，这个模型的 会很小，所 以， 大（ 问题总能通过增加训练样本解决。 最后，再附两张 经典图，第一张是 二 张是 5精品文档 2016 全新精品资料 全程指导写作 独家原创 16 / 144 那么，知道 ，怎么控制呢？除了在模型选择和训练样本收集上下功夫外， 一个最重要的方法就是 本质是限制参数空间， 从而倾向于选择比较简单的模型， 按照奥卡姆剃刀原 理，能够较好的解释现有数据并且比较简单才是最好的模型，其实，从直觉去理解，也应该 是这样，比如参数 w 的值巨大的话，即使 x 变动一小点，预测的结果也会发生剧烈变化 (可 以对 x 求导，这时 w 就是梯度 向量， w 可以描述函数值随着 x 变化的剧烈程度，所以， w 描 述模型的稳定性或者光滑程度 )，这显然与直觉不符，按照直觉，相近的 x 应该有相似的预 测值。 两种形式，相互等价：一般， g(w)的形式为：这里 P 可以取值 0（ ， 1（ L1， ， 2（ 。 当于是直接限制参数个数，这种方法最直接也最直观，可惜的是，既不 不 好求解。 下面重点比较下 先说 优点是可以限制 |w|的大小，从而是模型更简单，更稳定，稳定的意思就是说，即使加 入一些干扰样本， 也不会使模型发生大的变化， 另外 L2 非精品文档 2016 全新精品资料 全程指导写作 独家原创 17 / 144 常易于求解 ?， 还有一个好处就是能解决 X X 不可逆的问题。 缺点就是不能产生稀疏解，因此，起不到特征选择的作用，导致预测时计算量较大（海 量 时候） 。 再说 优点就是能产生稀疏解，因此，能起到特征选择的作用（海量 爽歪歪啊） ， 这样，我们能更好的理解模型，另外， L1 全局最优解） ，但是不 处可 导但导数不连续 （求解肯定比 劲， 见过一种近似求解方法叫 看过，但忘了 。 缺点就是不如 L2 过比裸奔要 知道 说干扰数据会使得 2016 全新精品资料 全程指导写作 独家原创 18 / 144 在多个 一会儿选择这个，一会儿选择那个） 。 这里有个有趣的问题， 为什么 产生稀疏解而 能呢？这个问题的数学解释超出了本 人那可怜的数学功底，这里给一个直观的解释，就是 边缘比较尖锐，这样与目标函数 的等高线相交时，交点经常会在那些比较尖锐的地方，所以很多参数就是 0，如下图：关于 到的作用，这里有一个基于 解释（本人也不是完全理解） 。 先说下表示定理：这里说的意思是，参数 w 的值一定在训练样本 x（或者经过基变换的 x）的线性子空间中， 比如，我们可以考察 者 对偶形式的 w，基本都是符合这一形 式的，那么，为什么 w 一定在 x 的线性子空间中呢？这里有一个很简单的证明，就是假如 w 不在 x 的线性子空间中，那么， w 一定可以分解成两个分量，第一个分量在 x 的线性子空间 中，第二个分量与 x 的线性子空间垂直，显然，第二个分量与 x 的内积为 0，由于我们有 这种情况下， |w| = |+ |显然 被优化为 0，因此，可以反 过来证明 w 一定在 x 的线性子空间中。引入 ，损失函数变为这个形式：，写成无参数形式以后是这样： 这里， K 函数可以做如下的特征分解，这里各个特征函数彼此正交，形成了 K 函数空间的一 组正交基，因此，最精品文档 2016 全新精品资料 全程指导写作 独家原创 19 / 144 后我们的 f(x)就可以表示为各个特征函数的线性组合。这样， 束可以表示为如下形式（推导过程得改天再看看 ?） ： 7精品文档 2016 全新精品资料 全程指导写作 独家原创 20 / 144 这里就可以看出 作用了，对于 K 函数特征分解中比较小的特征值 ，我 们倾向于选择较小的 c，这是不是很像 ？其实 作用就是选择了 K 函数中的 过滤掉了噪声，增加了稳定性。 那么这个跟最终函数的光滑性有何关联呢？应该说， 一个好的 数应该是光滑的（待证明） ，因此， 择 同时也 就使得最终函数变的光滑了。 最后，说下 的调节， 较小时，倾向于较小的 大的 较大时，倾向于 较大的 小的 过这种方式，我们可以调节模型的复杂度。的 惩罚因子 C 与 1/ 的效果相同。 前先提下 ， 最简单的二值分类模型，也是后来很多分 类器如 的基础， 式： 其实就是在 基础上加了个 数。 接下来说一下 学习策略，最直观的 是误分类点的个数，但这个 显然不好求解，因此，我们采用了另一种形式： ，这个 ， 我们可以发现， 精品文档 2016 全新精品资料 全程指导写作 独家原创 21 / 144 思就是所有误分类点的函数间隔之和， 在数据线性可分的情况下， 该函数最后的值应该为 0。 对该函数求导就可以得到迭代求解公式， 注意的是这个迭代公式有原始形式和对偶形式， 对 偶形式： ， 是不是和 对偶形式很像啊？这个形式可以用迭代公式反推得到，另外， 如果采用对偶形式求解， 我们可以事先计算所有 x 内积的 阵， 是不是很像 K 矩阵？ 求解的算法采用 次对一个样本进行训练，如果分类正确，则 什么都不做，如果分类错误，则采用 参数进行更新，数学上可以证明， 如果训练样本是线性可分的，该算法收敛（就是一定能得到一个解，但解可能有无穷多个， 而且最后得到的是哪个解和初始以及迭代顺序有关） ，但是，如果训练样本是线性不可分， 则无法收敛。 如果看过 肯定会有一个疑问，这里我们的目标是 小化，如果我们缩放 w， 没有变，但是 值会变小，这是否意味着 小化失去意义了呢？这里不需要有这个担心，因为最后 目标值是 0，而这 8精品文档 2016 全新精品资料 全程指导写作 独家原创 22 / 144 个跟 w 是否缩放无关。 接下来进正题了，说说 前面的 终有无穷多个解， 那么， 这些解的质量都是一样吗？有没有可能得到唯 一的最优解呢？是奔着这个目标来的。 称 单的说就是，现成可用（不用费大力气 工具 里最 ，真是让人心潮澎湃啊，所以我最初花了不少时间研究这个，后来慢慢发现，其 实工具无所谓好坏，只要用得好，都能得到很好地效果，当然，这是后话。 总体优化目标就是 隔最大化（这里的间隔是几何间隔，和 函数间隔不一样） ，这个有什么好处呢？简单的说就是推广性好，稳定，不至于因为 x 的 一点细微变动就跳到另一个类去 了。另外，和前面提到过的 比， 是概率模型，预测值的大小和概率无关。 我们先从最简单的情况说起，就是线性可分的情况，优化目标是：总的意思就是在满足线性可分的情况下最大的函数间隔，这里之所以要限制 |w|=1，是因为 如果不加这个限制， 那么， 我们只需要等比例缩放 w 和 b， 就可以在不改变超平面的情况下， 无限放大函数间隔，这显然没有意义，接下来我们做两步简单的变换： 1、， 2、第一步很明显， 精品文档 2016 全新精品资料 全程指导写作 独家原创 23 / 144 第二步是因为函数间隔对结果没有 实际影响， 因此我们可以将最小函数间隔 限定为 1。 这属于不等式约束下的凸优化问题（有软件可以直接求解） 构造拉格朗日乘子： ， ，转换为等价的 题： 。这里说下两个问题等价的原因，这里不等式约束为 g(x) =0，因此和 f(w)等价，而如果不满足约束，则 )为无穷大，因此等价。 求解原问题不大容易，因此我们将其转换为对偶问题求解，对偶问题为： ，由于这里 f(x)和 g(x)都是凸函数，且数据线性可分，所以对偶问题 的解就是原问题的解。 9精品文档 2016 全新精品资料 全程指导写作 独家原创 24 / 144 由 件： 另外可以得到约束： 。，可知：，那么 b 如何求解呢？观察 件，我们会发现，对于 不为 0 的样本， g(w) = 0，也就是 说，这些点位于间隔边界上，我们只需要随便找到这样一个样本，将 w 代入，即可得到 b。 这里就引入了支持向量的概念， 刚才提到过， 只有位于间隔边界上的点前面的系数 不为 0， 这些点叫做支持向量，而且，超平面仅仅由这些支持向量决定，所以叫支持向量机。 将上面得到的 w 代入，得到最终要优化的问题：前面我们是基于线 性可分的情况来讨论的， 那么如果不是完全线性可分呢？这里我们引入松 弛变量，于是，问题变为：经过和上面类似的变换，问题转化为：这里，惊喜的发现，松弛变量没了，哈哈，唯一的区别就是 多了一个上界约束 C （ 惩 罚 因 子 ， 效 果 和 1 / 相 同 ， 参 加 。 这里解释下 = C 这种情况，上面的约束 的完整版本是 C = 0( 是 约束松弛量 = 0 的拉格朗日乘子 )，且由 件有 = 0，所以当 = C 时，我们可知 不为 0，所以， = C 对应的是那些分类错误或者是分类正确但是位于间隔面之间的训练样 本。 精品文档 2016 全新精品资料 全程指导写作 独家原创 25 / 144 这里再重新讨论下软间隔（前面是硬间隔，即线性可分）情况下的支持向量，这里 = 0 的 情况还是和以前一样，对应的是那些分类正确且位于间隔面之外的点，另外，所有 不为 0 的点都是支持向量，但是，这里和前面不一样的是，支持向量未必位于间隔面上，如上段所 10精品文档 2016 全新精品资料 全程指导写作 独家原创 26 / 144 述，如果 0 再说下求 b 的方法，其实还是和前面一样，只不过这里找间隔面上的样本时条件变了，现在 的条件是：0 前面提到的都是线性分类情况，如果数据不 是线性可分的呢？其实前面 讨论过这种情况，就是做特征变换，将低纬空间中的样本映射到高纬空 间中，就可能在高纬空间中线性可分了，但是，要找到这样一个映射函数是很费劲的。 观察前面优化目标的对偶形式， 我们发现所有的目标函数和预测函数都只和样本间的内积相 关，因此，如果有一种方法，能够让我们直接计算两个样本断增加，这样预测的时间 复杂度会很高，在实时性要求很高的情况下这可能也会成为问题。 那么， 我们怎么证明一个函 数是核函数呢？简单的说， 充要条件是， 矩阵是半正定矩阵 K （证 明看不懂 。 最后说一下对偶形式的学习算法吧，就是著名的 法，简单说下算法思路，先把目标函数贴过来：。首先说下前提（我不是很懂 ，就是，如果所有变量的解都满足 件，那么，这个最 优化问题的解就得到了，这是充分必要条件，因此，我们学习算法的终止条件就是所有变量 的解都满足 件。 接下来说学习过程，这是一个带约束的凸优化问题，有全局最优解，有两个约束，一个不等 式约束，一个等式约精品文档 2016 全新精品资料 全程指导写作 独家原创 27 / 144 束，这里我们可以借鉴 思路，每次选取一个 做 优化，但是这里有等式约束 ，因此，每次我们需要选择两个 （选择的思路一会 11精品文档 2016 全新精品资料 全程指导写作 独家原创 28 / 144 儿介绍） ，这里我们姑且记为 1 和 2 吧，由等式约束（其他 是常量） 我们可以把 1 表示为 2 的方程： ，另外，由于， ，加上 1 和 2 的线性关系， 可知 2 有上界 H 和下界 L， 这个可以直接计算出来，这里，先不考虑 2 的取值范围，这时目标函数就变成了只有 2 一个变量的二次函数，可 以直接通过 解析方式求解（速度很快，这也是 法很快