非线性回归和梯度下降 Nonlinear Regression and Gradient Descent

在处理多项式和指数函数等拟合曲线时，我们可以使用解析的手段直接对误差函数进行分析，但是曲线拟合方法可以使用任意定制化的曲线函数，这要求我们必须寻找一种更加通用和普适的方法来最小化误差函数

例如，也许我们希望用于拟合的曲线函数是 $f(x) = \beta_1\cos(\beta_2x + \beta_3) + \beta_4$，类似这种非线性函数最终将给我们非线性方程组，所以我们要定义用于非线性回归的通用非线性拟合函数

$$f(x) = f(x,\beta)$$

对于需要拟合的 $n$ 个数据来说，$\beta \in \mathbb{R}^m$ ($m < n$)，也就是说有 $m$ 个参数组成的参数向量 $\beta$ 用于最小化误差函数，此时的 均方根误差 root-mean-square error (最小二乘误差不取均值且平方)

$$E_2(\beta) = \sum_{k=1}^{n} (f(x_k,\beta) - y_k)^2$$

我们要求误差函数的梯度，也就是误差函数对参数向量 $\beta$ 的每一个分量 $\beta_j$ 求偏导，由于有 $m$ 个分量 ( $m$个参数 )，所以会得到 $m \times m$ 的方程组

$$\frac{\partial E_2}{\partial \beta_j} = 0 \quad j = 1,2,\cdots,m$$

最终得到的非线性方程组是

$$\sum_{k=1}^{n}(f(x_k,\beta) - y_k)\frac{\partial f}{\partial \beta_j} \quad j = 1,2,\cdots,m$$

目前没有通用的直接方法来求解这样的非线性系统，这是因为非线性系统可以是无解，多解，无穷多解，目前解决非线性系统的大多数尝试都是基于迭代方法的，这需要良好的初始猜测才能收敛到误差的全局最小值

所以在这种情况下，就依赖于输入的初始猜测要足够好，否则可能无法很快很好的收敛到误差的极小值，对于凸函数来说，梯度下降表现是出色的，而对于非凸函数来说，情况就不那么好了，因为非凸函数可能存在一些局部坑洼，也就是局部极值，我们很有可能陷入其中，并且非凸函数可能存在很多难以计算梯度的平坦区域，在这些区域上，梯度接近于零，所以优化这种非凸函数就需要良好的初始猜测，不过目前来说，梯度下降方法有很多研究进展，例如不陷入局部最小值以及在平坦区域进行重启

梯度下降 Gradient Descent

对于高维系统，我们讨论的最小值和最大值是多维函数 $f(x)$ 的 极值 extremum，在极值处，函数的梯度必定为零，也就是

$$\nabla f(x) = 0$$

由于高维空间中存在 鞍点 saddle，所以必须检测极值是极大值还是极小值，梯度下降 Gradient Descent 或 最速下降 steepest descent 的思路是使用导数信息作为迭代算法的基础来逐步逼近并最终收敛到 $f(x)$ 的局部极值点

我们可以用一个例子来说明这个过程，例如对于函数

$$f(x,y) = x^2 + 3y^2$$

该函数在原点处，也就是 $(x,y)=(0,0)$ 处取到最小值，该函数的梯度是

$$\nabla f(x) = \frac{\partial f}{\partial x}\mathbf{\hat{x}} + \frac{\partial f}{\partial y}\mathbf{\hat{y}} = 2x\mathbf{\hat{x}} + 6y\mathbf{\hat{y}}$$

• $\mathbf{\hat{x}}$ 和 $\mathbf{\hat{y}}$ 是 $x$ 和 $y$ 方向的单位向量

首先，我们在最初的猜测点位置计算函数的梯度向量 $\nabla f(\mathbf{x})$ ，要想走向函数的极小值，我们需要沿着梯度向量的反方向走，也就是 $-\nabla f(\mathbf{x})$，注意负梯度向量并不是直接指向极小值，而是给出了在当前位置 (局部) 最小化 $f(x)$ 最快的方向 (下坡最快、最陡峭的方向)，这种在当前局部位置往函数变小的最快方向前进的方法可以构造出我们想要的迭代优化算法，即每次选择负梯度方向前进，并且到达该位置以后再次计算梯度以选择下一次前进的位置，并且不停重复迭代直到最终到达极值位置

$$\mathbf{x}_{k+1}(\delta) = \mathbf{x}_k - \delta\nabla f(\mathbf{x}_k)$$

• 这里存在一个参数 $\delta$，它表示我们沿着负梯度方向走多远，它也常常被称为 学习率 Learning Rate

这个公式是 牛顿法 Newton method 的推广，其中导数用于计算迭代时每次的更新内容，在梯度下降中，决定每一次沿着计算出的梯度方向走多远是非常重要的，也就是说 $\delta$ 的值很关键，它决定了算法是否一直以最优方式走向极值

要计算 $\delta$，我们需要构造一个新的函数

$$F(\delta) = f(\mathbf{x}_{k+1}(\delta))$$

我们来仔细看一下这个新构造的函数，其中 $f$ 是原回归函数，也就是我们正在执行梯度下降的函数，而 $\mathbf{x}_{k+1}(\delta)$ 在之前定义过，它是我们下一步要走到的位置，也就是说我们的新函数 $F(\delta)$ 是下一个迭代点在给定步长为 $\delta$ 时的函数值
对于所有可能的步长 $\delta$ 都有一个对应的函数值 $f$，在这些函数值内我们找到最小的一个 (不是指我们找的极值，而是所有可能步长里得到的函数值中最小的)，这个函数值对应的步长就是我们找的最佳的 $\delta$ ，为此，我们需要让 $F(\delta)$ 对 $\delta$ 求导，并令其导数等于零来找到最优的 $\delta$

$$\begin{align*} \frac{\partial F}{\partial \delta} &= \nabla f(\mathbf{x}_{k+1}) \cdot \frac{\partial \mathbf{x}_{k+1}(\delta)}{\partial \delta} \\ &= -\nabla f(\mathbf{x}_{k+1})\nabla f(\mathbf{x}_k) \\ &= 0 \end{align*}$$

我们运用链式法则得到 $-\nabla f(\mathbf{x}_{k+1})\nabla f(\mathbf{x}_k)=0$ 这意味着，在最优步长 $\delta$ 下，下一步的梯度 $\nabla f(\mathbf{x}_{k+1})$ 和当前梯度 $\nabla f(\mathbf{x}_k)$ 是正交的，也就是说我们可以确保当前的梯度方向和下一步的梯度方向正交，从而保证每一步更新的方向尽可能地朝向最小值，避免无效的振荡和过大或过小的步长选择

对于我们的例子 $f(x,y)=x^2+3y^2$ 来说，我们首先计算

$$\begin{align*} \mathbf{x}_{k+1} = \mathbf{x}_k - \delta\nabla f(\mathbf{x}_k) &= (x\mathbf{\hat{x}} + y\mathbf{\hat{y}}) - (2x\mathbf{\hat{x}} + 6y\mathbf{\hat{y}}) \\ &= (1-2\delta)x\mathbf{\hat{x}} + (1-6\delta)y\mathbf{\hat{y}} \end{align*}$$

然后我们可以计算 $\delta$

$$\begin{align*} F(\delta) = f(\mathbf{x}_{k+1}(\delta)) &= f(\ (1-2\delta)x,(1-6\delta)y\ ) \\ &= (1-2\delta)^2x^2 + 3(1-6\delta)^2y^2 \end{align*}$$

接着计算 $F$ 对 $\delta$ 的导数

$$F'(\delta) = -4(1-2\delta)x^2 - 36(1-6\delta)y^2$$

令 $F'(\delta)=0$ 并化简可得

$$\delta = \frac{x^2 + 9y^2}{2x^2 + 54y^2}$$

这就是该函数的最佳下降步长公式，注意 $\delta$ 的值会随着迭代的进行而更新，以上推导已经给了我们关于使用梯度下降求 $f(x,y)=x^2+3y^2$ 极小值的所有信息

显而易见，这种基于导数信息的迭代下降搜索方法，无论是在什么维度中，都非常类似于 牛顿迭代求根 方法

在上面的例子中，梯度可以通过分析方法直接推导出解析式，但是对于大多数实际案例的数据而言，梯度是通过数值方法计算出来的，我们可以看到梯度下降方法的一些主要问题，即确定初始值、步长以及如何有效的计算梯度

交替下降 Alternating Descent

另一种常用于优化多元非线性函数的技巧是 交替下降 Alternating Descent method ADM ，这种方法通过每次迭代只沿着一个变量方向走来避免计算完整的梯度向量，当所有变量方向都走完之后，从头再开始循环，直到达到收敛值