好几个月没再继续, 挖坑不填是不对的, 还是继续写手记.
线性回归
线性回归一般用来学习一维自变量和一维因变量之间的线性关系. 如果存在一维自变量 x, 同时还有一维因变量 y = f(x), 如果有一堆对不同 x 下 y 的观测值, 即 <x, y> 的观测对, 且如果 x, y 之间存在较明显的线性关系, 可以用 f(x) = a*x + b 这样的方程表示, 则可以用线性回归的方法学习出 a 和 b 的值, 同时估计这个拟合方法的误差 r.
扩展一下, 线性回归也可以指 y = a1*x1 + a2*x2 + … + ak*xk + b 这样多维自变量和一维因变量之间的线性关系 (多项式里自变量的最高幂次都是 1), 同样也可以用回归的方式学出来里面不同的系数和常数项的值. 只有一维自变量的称之为一元线性回归, 否则是多元线性回归.
判断线性回归好坏, 一般就用平方误差和来描述, 其表达为 (f(x1)-y1)2 + (f(x2)-y2)2 + … + (f(xk)-yk)2), 此值如果为 0 则说明自变量和因变量存在完全的线性关系, 否则是近似线性, 越小近似的越好. 这个东西看着有没有一点面熟? 其实就是机器学习手记系列 2: 离线效果评估里最后提到的 MSE 的非平均版本.
解方程法
假如输入样本存在绝对的线性关系, 即最后的误差为 0, 则问题变为解二元一次方程 (一元线性回归里的系数加常数) 或 N+1 元一次方程 (多元线性回归里 N 个自变量的系数加常数). 这没什么好说的, 直接对原输入直接求解就行了, 类似计算方法这样的课本上有的是解法, 做梯度下降或牛顿法乃至矩阵分解都可以解.
梯度下降法
考虑到绝大部分情况下不存在绝对的线性关系, 则问题可以变成怎么求平方误差和的最小值点. 如果是一元线性回归, 目标函数变为 g(a, b) = (f(x1)-y1)2 + (f(x2)-y2)2 + … + (f(xk)-yk)2
我们的目标就是让这个目标函数值最小, 选定一组 <a, b> 的初始值, 然后求其梯度方向, 每次前进一个小步长, 再求梯度前进, 直到目标函数值不再下降, 说明我们已经走到了一个极值点附近, 终止迭代. 对一元线性回归, 梯度方向是对函数求偏导得到的向量方向.
另外需要注意的是, 梯度下降不一定能找到最优解, 可能会在某个局部最优解那陷进去就出不来了.
这部分更详细的推导请见参考资料里 “机器学习中的数学(1)” 一篇, 里面的公式和图做的很赞, 思路也比我清晰.
牛顿法
梯度下降一般遇到的问题迭代步长不好选, 选太小到极值点太慢, 搞太大又会在极值点附近时因为步长太大跳过去了.
牛顿法最大的贡献就是同时给出了梯度方向和迭代步长, 几乎是一步到位的求解. 方法同解方程一样, 对新的损失目标函数求解, 只是一次解可能还不够好, 需要多做几次迭代. 一般梯度下降可能需要上千轮的迭代, 而牛顿法几次迭代就能到极值点了.
最小二乘法
伟大的高斯同学提出并证明了最小二乘法是最好解答, 证明过程略… 直接看维基或百度百科上的原文吧 (数学不好伤不起).
应用
虽然这个方法看起来很简单粗暴, 但是很多时候变化确实就是线性的. 比如在很多论文和工业实践中, 大家认为同等质量的广告或搜索结果, 放在从上到下不同的位置上, 其点击率和位置的关系符合线性关系, 即 ctr(rank) = a*rank + b.
在六月的一次随笔杂记里, 提到了这样的问题:
如下式子里不同的阿拉伯数字只是一个符号, 实际表示的可能是其他数字 967621 = 3 797321 = 1 378581 = 4 422151 = 0 535951 = 1 335771 = 0根据上述式子, 判断下式等于?
565441 = ?
假设每个式子最后做的都是加法, 并把字符 0~9 映射到 x0~x9, 则统计不同字母出现的次数就可以列线性返程, 可以将第一个式子表示为
x0*0 + x1*1 + x2*1 + x3*0 + x4*0 + x5*0 + x6*2 + x7*1 + x8*0 + x9*1 = 3
其他类推. 对这堆式子求解就可以得到不同数字对应的真实数值, 可以得到 565441 = 1. // 具体代码和方法下次给出
参考资料
- Wiki Least squares: http://en.wikipedia.org/wiki/Least_squares
- Wiki Mean Squared Error: http://en.wikipedia.org/wiki/Mean_squared_error
- 中文维基 最小二乘法: http://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E4%BA%8C%E4%B9%98%E6%B3%95
- 百度百科 线性回归: http://baike.baidu.com/view/449540.htm
- 百度百科 最小二乘法: http://baike.baidu.com/view/139822.htm
- 人人上的日志 幼儿园的题目和机器学习的关系: http://blog.renren.com/share/30314/13432269197
- 机器学习中的数学(1): http://www.cnblogs.com/LeftNotEasy/archive/2010/12/05/mathmatic_in_machine_learning_1_regression_and_gradient_descent.html
// 本文开写于 9.24, 拖到 10.26 才马马虎虎完成, 最后那个题的解也没写, 各种错乱后续再修改或补充吧