1.2　多项式逼近函数

在基础的数学理论中，也可以找到非常明显的机器学习的影子，那就是函数逼近理论。本节将回顾这个理论并且从机器学习的角度来重新阐述一些重要的原则。

已知有若干有限个一维实数空间的点和在这些点上的函数值，根据这些信息来预测这个函数在其他点的取值。这个传统的数学领域和机器学习的目标非常相似。下面我们用数学语言来精确描述问题。

给出直线上的一个区间[0，1]，有一个实值函数使得

但是我们不知道这个函数是什么形式。与此同时，给出[0，1]区间上的一个离散点集

0＜x₁＜x₂＜···＜x_n＜1

以及一组对应的函数值

y₁=f（x₁），y₂=f（x₂），···，y_n=f（x_n）

我们试图通过这些有限数据推测出原来的函数关系。那么什么样的函数可以精确地给出这种对应关系呢？常见的可以选择多项式。根据多项式理论，任何一个n−1次的多项式

使得能够满足对于任何0＜i＜n有

g（x_i）=y_i

这个问题就相当于求解一系列的关于多项式系数的线性方程

但是因为等号左边的线性矩阵是范德蒙行列式，即

所以不为零，从而这个线性方程一定是可解的。如果使用Cramer法则计算出未知数，可以得到

也称为拉格朗日插值公式。

虽然拉格朗日插值公式在形式上圆满解决了问题，但是从图像上看仍然不尽人意，整条曲线上下振荡，波动很大。我们可以从下面的事实来理解振荡的原因。如果y_i≡0，则除了零多项式以外，任意一个n次多项式

g（x）=（x−x₁）（x−x₂）···（x−x_n）

都满足条件g（x_i）=0。这个多项式虽然在所有给出的点上都等于零，但也会在这些x_i之间不断地上下振荡。所以可以想象，使用高次多项式虽然可以完全解决函数的插值问题，但是得到的函数会不断振荡，如图1.1所示。

现在想象这样一个事实。数据之间的关系原本就是一个线性函数，仅仅因为给出的函数值具有一些误差，从而破坏了线性性质，但是为了精准拟合所有函数值，我们需要用高次多项式函数来插值，得到的结果也就振荡多次，从而当我们使用这个函数做预测时，就会跟原来的线性函数产生较大的误差。这种在给定数据上精确的拟合，但是在预测数据上产生很大误差的现象可以称为过分拟合。

为了去除过分拟合，必须放弃精确插值的想法，以函数逼近的思路取而代之。假定给出函数f（x），考虑限定多项式的次数同时逼近该函数。为此，需要讨论多项式g（x）在什么意义下逼近函数f（x）。为了阐述误差，还需要引进函数之间距离的概念。我们引入两个函数f，g之间的距离函数L（f，g），假定区间是[0，1]时，可以定义积分意义下的L²距离

最佳逼近问题就成为寻找

在这里，我们限定了一个n次多项式的集合H，在这个集合里面寻找逼近函数g（x）。现在来求解最佳逼近的多项式，令

然后求解极值问题

这里借用一下线性空间的概念，特别是希尔伯特空间的知识。如果把所有在区间[0，1]上平方可积的函数作为一个空间，n次多项式构成的空间就是一个子空间。上述问题就成为在这个子空间上寻找一个函数，使其和f（x）的距离最小。根据希尔伯特空间的性质可知，这个元素存在，而且和f（x）构成的差和子空间上的任何一个元素都垂直。从而得到这里的系数a_i具有以下性质

对于每个j都成立。那么对于0≤j≤n，就有

这个线性方程组的线性系数构成的矩阵称为Cauchy矩阵。Cauchy矩阵构成的行列式值也是正的，所以Cauchy矩阵也是可逆的，通过解这个线性方程组，我们可以得到所有的系数。此处值得一提的是，一般的Cauchy矩阵的定义为

其中

而Cauchy矩阵的行列式为

可令x_i=i+1，y_j=j，从而有

所以确实是非零，如图1.2所示。

至此，我们发现对于给定的数据

（x₁，y₁），（x₂，y₂），···，（x_n，y_n）

其中，，可以使用任何一个多项式次数k≤n−1来逼近这些数据。当k=n−1时，逼近的误差是零，k越小，误差越大。但是可以想象，k越小，过分拟合的现象也越不明显。