来源：原始 Jupyter Notebook。内容已转换为网页阅读格式；下载原文件。

对于一堆输入数据，我们可以用线性回归来拟合它，也可以用二次回归，三次回归，或者 N 次回归来拟合它。在函数逼近理论里，有一个定理叫做 Weierstrass定理，该定理阐述了在预先给定的精度下，可以用多项式逼近任意给定的闭区间上的连续函数。

Weierstrass第一逼近定理：假设 f(x)f(x) 是闭区间 [a,b] 上的连续函数，对于任意的 ϵ>0\epsilon>0，则存在多项式 P(x)P(x) 使得对于所有的 x∈[a,b]x\in [a,b]，有 ∣f(x)−P(x)∣<ϵ|f(x)-P(x)|<\epsilon。

也就是说使用多项式回归，随便什么样的输入数据，都可以逼近，因为回归问题的输入本身就是连续且在特定区间内的。多项式回归的表达式如下：

y=θ1ϕ1(x)+θ2ϕ2(x)+...+θkϕk(x) y = \theta_1\phi_1(x) + \theta_2\phi_2(x) + ... + \theta_k\phi_k(x)

其中，ϕ(x)=(1,x,x2,...,xk−1)T\phi(x) = (1, x, x_2, ..., x^{k-1})^T，在实际求解中，这里的 k 值不可能取无穷大，我们可以从 k=2 开始（也就是线性模型），得到一个模型，评估模型是否满足条件，不满足的话，取 k=3，依次迭代，直到模型满足条件为止。

我们再来看看之前的一元线性回归的数据：

import numpy as np
import matplotlib.pyplot as plt

plt.xlim(30, 60)
plt.ylim(100, 600)

X = np.array([39.93, 42.05, 43.18, 44.68, 49.87, 53.57])
Y = np.array([199,   290,   298,   310,   399,   420])
plt.scatter(X, Y)

plt.show()

运行结果

Notebook 运行结果

从图中很显然能看出这是一条直线，我们使用线性回归来求解（这里只是一个简单的示例，在实际问题的求解中，如果输入的维度非常大，很难通过图形直观的看出数据是不是线性的）：

import numpy as np

X = np.matrix([
    [1, 1, 1, 1, 1, 1], 
    [39.93, 42.05, 43.18, 44.68, 49.87, 53.57]]).T
Y = np.matrix([199,   290,   298,   310,   399,   420]).T

a = (X.T * X).I * X.T * Y
print("a = {0}".format(a))

运行结果

a = [[-360.87880256]
 [  14.93439994]]

得到回归模型：

y=14.93x−360.88 y = 14.93x - 360.88 
import numpy as np
import matplotlib.pyplot as plt

plt.xlim(30, 60)
plt.ylim(100, 600)

X = np.array([39.93, 42.05, 43.18, 44.68, 49.87, 53.57])
Y = np.array([199,   290,   298,   310,   399,   420])
plt.scatter(X, Y)

x = np.linspace(30, 60)
y = 14.93*x-360.88
plt.plot(x, y)

plt.show()

运行结果

Notebook 运行结果

那么这个模型是不是最好的呢？我们不妨再来求解二次回归和三次回归，甚至可以求出十次回归：

import numpy as np

# 不使用科学计数法
np.set_printoptions(suppress=True)

X2 = np.matrix([
    [1, 1, 1, 1, 1, 1], 
    [39.93, 42.05, 43.18, 44.68, 49.87, 53.57],
    [39.93**2, 42.05**2, 43.18**2, 44.68**2, 49.87**2, 53.57**2]]).T
X3 = np.matrix([
    [1, 1, 1, 1, 1, 1], 
    [39.93, 42.05, 43.18, 44.68, 49.87, 53.57],
    [39.93**2, 42.05**2, 43.18**2, 44.68**2, 49.87**2, 53.57**2],
    [39.93**3, 42.05**3, 43.18**3, 44.68**3, 49.87**3, 53.57**3]]).T
Y = np.matrix([199,   290,   298,   310,   399,   420]).T

a2 = (X2.T * X2).I * X2.T * Y
a3 = (X3.T * X3).I * X3.T * Y
print("a2 = {0}".format(a2))
print("a3 = {0}".format(a3))

运行结果

a2 = [[-2560.63241005]
 [  109.75507269]
 [   -1.01064275]]
a3 = [[-8453.71313725]
 [  494.12237385]
 [   -9.32082522]
 [    0.0595445 ]]

得到二次模型：

y=109.75507269x−1.01064275x2−2560.63241005 y = 109.75507269x - 1.01064275x^2 - 2560.63241005

和三次模型：

y=494.12237385x−−9.32082522x2+0.0595445x3−8453.71313725 y = 494.12237385x - -9.32082522x^2 + 0.0595445x^3 - 8453.71313725 
import numpy as np
import matplotlib.pyplot as plt

plt.xlim(30, 60)
plt.ylim(100, 600)

X = np.array([39.93, 42.05, 43.18, 44.68, 49.87, 53.57])
Y = np.array([199,   290,   298,   310,   399,   420])
plt.scatter(X, Y)

x = np.linspace(30, 60, 200)
y = 109.75507269*x-1.01064275*x**2-2560.63241005
plt.plot(x, y)

x = np.linspace(30, 60, 200)
y = 494.12237385*x-9.32082522*x**2+0.0595445*x**3-8453.71313725
plt.plot(x, y)

plt.show()

运行结果

Notebook 运行结果

蓝色曲线是二次回归的结果，橙色曲线是三次回归的结果，可以看出拟合程度也很高，而且随着多项式回归的维数的增加，回归线可以无限的接近输入的数据。那么，我们到底该使用哪个回归模型呢？

根据 奥卡姆剃刀原则（Occam’s razor）我们可能会认为最简单的往往是最有效的，既然一元线性回归能解决问题，为什么要使用多项式回归呢？虽然这个原则在大多数情况下很实用，但是在很多时候，“最简单”是一个模棱两可的指标，什么是“最简单”并不好判定。

其实，更多的时候，我们并不是要追求最简单的模型，而是希望我们的模型能适应更多训练集之外的情景，也就是模型要有举一反三的能力，即泛化能力。从直观上来看，在上面的场景中，线性回归和多项式回归比较起来，我们更希望线性回归更好一点。遗憾的是，虽然一元线性回归能在训练集上得到很好的拟合结果，但是在训练集之外的样本数据上，完全可能出现二次曲线或三次曲线的情况，而且谁也不能保证在训练集之外的数据是什么样子的。

而且可以证明的是（证明过程可以参见周志华《机器学习》1.4节 归纳偏好）：学习算法在样本上的总误差与学习算法本身无关，任意两个学习算法它们的期望性能是相同的，也就是说，你所见过的所有机器学习算法，简单的线性回归也好，高级的决策树、支持向量机也好，甚至神经网络、深度学习，他们的期望性能和随机瞎猜是一样的。这个定理被称为 NFL 定理（No Free Lunch Theorem，没有免费的午餐定理）。

那么既然如此，还要搞这么多的机器学习算法干什么呢？实际上，NFL 定理有一个很重要的前提：所有的问题出现的机会相同，或者说所有的问题同等重要。很显然，事实并非如此，我们一般只关注自己正在解决的问题，对其他问题并不关心。所以，NFL 定理的真实意图是告诉我们，判断模型的好坏要结合具体的问题，脱离具体问题的模型毫无意义，就譬如上面的几个散点数据，如果你不知道这是什么数据，不知道在解决什么问题，只是抽象的数字，得到的模型也无法得知孰好孰坏。

回到我们上面的问题，现在有三个模型对数据集的拟合都很好，能看出二次回归和三次回归对数据的误差要更小，根据上面介绍的 Weierstrass 定理，我们甚至可以计算出一个多项式回归模型，使得误差趋近于 0，这样的模型是不是最好的呢？

这里要引入几个概念，我们把模型预测结果和样本的真实结果之间的差异称为 误差（error），训练集上得到的误差称为 训练误差（training error）或 经验误差（empirical error），在新样本上的误差称为 泛化误差（generalization error），上面我们用复杂的模型把误差降的很低，其实降低的是训练误差，而我们显然是希望模型在新样本上表现的很好，也就是泛化误差要小，当我们把模型训练的太复杂时，模型的泛化能力反而会下降。这种现象被称为 过拟合（overfitting）。

过拟合是机器学习算法中一个非常重要，也非常棘手的问题，各种机器学习算法都避免不了，有多种因素可能会导致过拟合，其中最常见的情况是由于学习能力过于强大，以至于把训练样本所包含的不太一般的特性都学习到了。与之相反的一种场景是 欠拟合（underfitting），通常是由于学习能力低下造成的。

针对这个问题我们后面还会学习如何尽可能的避免过拟合。