机器学习之MSE的梯度下降

本文主要讲解使用梯度下降算法迭代熟悉的MSE损失函数。

$$J(\theta)=E[(y-\theta^{T}x)^{2}] \\ =\sigma_{y}^{2}-2\theta^{T}p + \theta^{T} \phi \theta$$

MSE可以看上面这个博文了解上面这个公式。
其中$\phi$是输入特征的协方差矩阵，p是输入和输出的互相关矩阵。

$$\triangledown J(\theta)=2 \phi \theta-2p \tag{1.1}$$

其迭代过程如下公式

$$\theta^{(i)}=\theta^{(i-1)} - \mu(\phi \theta^{(i-1)} -p) \\ =\theta^{(i-1)} + \mu(p-\phi\theta^{(i-1)} ) \tag{1.2}$$

其中$\mu$表示步长。

步长的收敛性

$$c^{(i)}=\theta^{(i)}-\theta_{\\*} \\ \theta_{\\*} \phi=p$$

上面的公式1.2两边同时减去$\theta_{\\*}$,得到如下公式

$$\theta^{(i)}-\theta_{\\*}=\theta^{(i-1)} + \mu(p-\phi\theta^{(i-1)})-\theta_{\\*} \\ c^{(i)}= c^{(i-1)}+\mu(p-\phi c^{(i-1)}-\phi \theta_{\\*}) \\ =c^{(i-1)}-\mu \phi c^{(i-1)}=(I-\mu \phi)c^{(i-1)} \tag{2.1}$$

因为$\phi$是正定的，所以有$\phi=Q \wedge Q^{T}$，其中$\wedge$表示特征值，Q表示特征向量。将上面的条件带入公式2.1.

$$c^{(i)}=Q(I-\mu \wedge) Q^{T} c^{(i-1)} \tag{2.2}$$

进一步简化，$v^{(i)}=(I-\mu \wedge) v^{(i-1)}$，得到下面的表达式

$$v^{(i)}=Q^{T}c^{(i)} \tag{2.3}$$

以上的转换是为了拆解公式1.2中的$\theta^{(i)}$的各个分量。$v^{(i)}(j)$表示$v^{(i)}$的第j个分量，且迭代路径和其他分量无关，满足以下表达式。

$$v^{(i)}(j)=(1-\mu \lambda_{j})v^{(i-1)}(j) \\ =(1-\mu \lambda_{j})^{2} v^{(i-2)}(j) = (1-\mu \lambda_{j})^{i} v^{(0)}(j) \tag{2.4}$$

其中$v^{(0)}(j)$是初始化的分量，如有以下的表达式成立。

$$|1-\mu \lambda_{j}|<1 \tag{2.5}$$

那么相应的次幂将趋近于0.，且

$$v^{(i)} \rightarrow 0 ,Q^{T}(\theta^{i}-\theta^{\\*}) \rightarrow 0,逼近最优参数$$

那么这个时候，步长收敛的条件就是(公式2.5)

$$0<\mu<\frac{2}{\lambda_{max}}$$

迭代速度

既然能保证保证迭代收敛，那么这个值的指定和迭代速度有什么关系呢？咱们继续来探索。
假设迭代的函数为$f(t)=exp(\frac{-t}{\tau_{j}})$,就是v， 将t=iT和t=(i-1)T带入到公式2.4中的$v^{(i)}， v^{(i-1)}$ ，求得是时间常数。

$$\tau_{j}=\frac{-1}{ln(1-\mu \lambda_{j})}$$

如果两个迭代步之间采样的时间T=1，那么对于很小的$\mu$,就有

$$\tau_{j}=\frac{-1}{\mu \lambda_{j}} \tag{3.1}$$

通过这个公式能够知道，最慢的收敛速度与对应的最小特征值有关，不过这只是适用于$\mu$比较小的情况。当然实际上是取决于$1-\mu \lambda_{j}$这一项决定，也称为第j个模态。

为了获取最佳的步长，必须以最小化得到最大模态绝对值的方式选择步长。

$$\mu_{0}=\arg\ min_{\mu} \max_{j}|1-\mu \lambda_{j}| \tag{3.2}$$

当然这个在下图中很容易被找到。求得的交叉点为。

$$1-\mu_{0} \lambda_{min}=-(1-\mu_{0}\lambda_{max}) \\ \mu_{0}=\frac{2}{\lambda_{min}+\lambda_{max}} \tag{3.3}$$

在最优处的$\mu_{0}$。有两个最慢的模态，一个对应于$\lambda_{min}$,另一个对应于$\lambda_{max}$就是$1-\mu_{0} \lambda_{max}$，且大小相同，符号相反，这里只要公式3.3带入到$1- \mu_{0} \lambda_{i}$即可，就有如下的表达。

$$\frac{p-1}{p+1} \\ p=\frac{\lambda_{max}}{\lambda_{min}}$$

也就是说，收敛速度取决于协方差矩阵的特征值的扩散度。