近年来，Machine Learning 在许多领域上已然取得了可喜的成就，非常火热。就我个人来讲，有意将业余 Sport Programming
的范围扩展一下，譬如 Topcoder Marathon。在解决实际问题中，方法太 Naive 往往效果不怎么样，依旧需要学习一下相关的基础知识。
本系列文章主要基于 Coursera 的 Machine
Learning，我社内部 Machine Learning 课里能说的一部分，wikipedia，以及一些其他的读物。
对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么我们称这个计算机程序从经验E中学习。
这是一个比较严谨的界定机器学习问题的
Guideline。如果有什么问题搞不清楚是不是这个范畴，可以尝试套用定义来检查：任务是什么，性能度量是什么，经验是什么，性能是否由于经验而提升。
个人理解，模型代表着你如何看待这个问题。譬如识别一个东西是不是汽车，如果你认为识别的依据是：金属壳 + 车灯 + 反光镜 + 车轮子 … = 汽车，这个思路就比较接近基于规则，决策树，贝叶斯；如果你考虑这个东西和见过的什么东西比较相似，就是 KNN 的思路。之后我们要不断学习的实际上都是模型。
常见的两个策略是经验风险最小化和结构风险最小化。经验风险最小化意味着我们倾向于对训练数据取得精准的预测。这个想法很直接，且有一定道理：模型在训练数据上表现不佳，更无法指望在测试数据上取得好结果。但是，在训练集上表现好的模型，未必在测试集上表现好。通常来讲，简单的模型会更有通用性，而复杂的模型，往往会有一些 hardcode 了训练数据的感觉，效果反而不一定好。结构风险最小化在经验风险最小化的情况下，加入一些因子来限制模型的复杂度。
根据策略，可以列出一个需要最优化的式子。算法就是求这个式子最优或者较优解的方法。最常见的方法是梯度下降，其他技能还没有 get，就暂不讨论了。
暂时忘记机器学习，现在需要优化一个形如 y = f(\theta)
的式子，求 x = argmax f(\theta)
或 x = argmin f(\theta)
，有什么好的办法么？
梯度下降法，基于这样的观察：如果实值函数 F(x)
在点 a 处可微且有定义，那么函数 F(x)
在 a 点沿着梯度相反的方向 -F\nabla(a)
下降最快。因此，如果 b = a - \gamma\nabla F(a)
对于 \gamma > 0
且为一个够小数时成立，那么 F(a) \geq F(b)
。换句话说，我们给出一个对极值的估计 a，不断迭代求 a = a - \gamma\nabla
F(a)
，就能取得一个极值。
用一个实际例子来演示一下：对二次函数 f(y) = x^{2} + 2x + 10 ，使用梯度下降法求 min f(x) 和 argmin f(x) ，函数图像如下：
结论无论是从图像还是初中数学的角度来看都很简单。我们看看梯度下降算法是如何进行的：
f <- function(x) {
x^2 + 2 * x + 10
}
df <- function(x) {
2 * x + 2
}
x <- 5
y <- f(x)
learning.rate <- 0.3
plot(f, -5, 5)
while (TRUE) {
nx = x - df(x) * learning.rate
ny = f(nx)
if (abs(x - nx) < 0.01)
break
arrows(x, y, nx, ny, col = "red")
x = nx
y = ny
print(c(x, ny))
}
## [1] 1.40 14.76
## [1] -0.040 9.922
## [1] -0.616 9.147
## [1] -0.8464 9.0236
## [1] -0.9386 9.0038
## [1] -0.9754 9.0006
## [1] -0.9902 9.0001
无论是简单问题还是复杂问题，参数 learning.rate，也就是前文中提到的 \gamma 的选择非常重要。Learning rate 过小则需要更多的迭代。Learning rate 过大则会出现之字下降，甚至之字上升。
看一个非凸，多元函数的例子：Rosenbrock函数： f(x, y) = (1-x)^2 + 100(y-x^2)^2 很显然 x = y = 1 的时候可以取得最优解，但是求解过程却是很坑的。咱们把 x = y = 1 附近的图像画出来：
再研究一下 x = 1 时的切面：
大概能看出来，这个函数在解附近有个很大的很平的底。。。贴一段代码，大家可以 play 一下：
f <- function(x, y) { (1 - x) ** 2 + 100 * (y - x ** 2) ** 2}
df.dx <- function(x, y) { x * 2 - 2 - 400 * y + 400 * x ** 3}
df.dy <- function(x, y) { 200 * y - 200 }
x <- runif(1, 0, 2)
y <- runif(1, 0, 2)
z = f(x, y)
learning.rate = 1E-6
eps <- 1E-10
while (TRUE) {
new.x = x - df.dx(x, y) * learning.rate
new.y = y - df.dy(x, y) * learning.rate
new.z = f(new.x, new.y)
if (abs(new.z - z) < eps) break
x = new.x
y = new.y
z = new.z
print(c(x, y, z))
}
可以调整一些参数，譬如 learning.rate，eps 去看看某些现象。我们可以看到他最后几步的收敛极为缓慢，如果 learning.rate 过大，还会之字上升等等。总的来讲，选择一个合适的 learning rate 是非常重要的，除去经验性的技巧，往往也只好枚举了，看看 cost function 的变化情况，如果下降过慢，则需要增大 learning rate，如果反而增长了，则需要减少 learning rate。这也就是为什么某些时候我们需要一个比较小的 validate set，我们可以定期的在训练中的模型上跑一下 validate set，看一下 cost function 的变化，从而决定 learning rate 的调整。
以 Stanford Machine Learning 为例：根据房子的面积预测房价。咱们来把一些概念对上号：
策略： minimize J(\theta_{0}, \theta_{1}) = \sum_{i=1}^{m}(\theta_{0}x_{i} + \theta_{1} - y_{i})^2
算法：注意此时我们要求解的是 \theta_{0},\theta_{1} ，而 x_{i},y_{i} 都是已知量，可以考虑求偏导，然后用梯度下降求解，这就是技能范围以内的东西了，因为每次迭代用了所有的 Training Data，所以这个做法叫 Batch Gradient Descent。
实际应用中，比较好用的算法是 Stochastic Gradient Descent，Batch Gradient Descent 每次迭代，对 \sum_{i=1}^{m}(\theta_{0}x_{i} + \theta_{1} - y_{i})^2 求导，相当于 \theta_{0} = \theta_{0} - 2\alpha\sum_{i=1}^{m}(\theta_{0}x_{i} + \theta_{1} - y_{i})x_{i} \theta_{1} = \theta_{1} - 2\alpha\sum_{i=1}^{m}(\theta_{0}x_{i} + \theta_{1} - y_{i}) 而 Stochastic Gradient Descent 相当与把 Batch Gradient Descent 的 1 次迭代拆成了 m 次，每次对 （\theta_{0}x_{i} + \theta_{1} - y_{i})^2 求导，然后 \theta_{0} = \theta_{0} - 2\alpha(\theta_{0}x_{i} + \theta_{1} - y_{i})x_{i} \theta_{1} = \theta_{1} - 2\alpha(\theta_{0}x_{i} + \theta_{1} - y_{i})
Batch Gradient Descent 可以求得更精确的解，但是如果模型复杂，或者数据量大，就很难直接 Batch Gradient Descent 了。
Sweetkang 的机器学习实验室 (1),布布扣,bubuko.com
原文：http://www.cnblogs.com/sweetsc/p/3617842.html