图解机器学习/第三章 最小二乘学习法

最小二乘学习法

 最小二乘学习法是对模型的输出$f_{\theta}(x_i)$和训练集输出$\lbrace y_i \rbrace_{i=1}^n$的平方误差

$$J_{LS}(\theta)=\frac{1}{2}\sum_{i=1}^n(f_{\theta}(x_i) - y_i)^2$$

为最小时的参数$\theta$进行学习

$$\hat{\theta}_{LS}=\mathop{argmin}_{\theta} J_{LS}(\theta)$$

平方误差$(f_{\theta}(x_i)-y_i)^2$是残差$f_{\theta}(x_i) - y_i$的$\mathcal{l}_2$范数，因此最小二乘学习法有时也称为$\mathcal{l}_2$损失最小化学习法。

 如果使用线性模型

$$f_{\theta}(x_i)=\sum_{j=1}^b \theta_i \phi_i (x)=\theta^{\intercal}\phi(x)$$

训练样本的平方差

$$J_{LS}(\theta)=\frac{1}{2}||\Phi \theta - y||^2$$

其中，$y=(y_1,\dots,y_n)^{\intercal}$是训练输出的$n$维向量，$\Phi$是下式中定义的$n\times b$阶矩阵，也称为设计矩阵

$$\Phi=\left[ \begin{matrix} \phi_1(x_1) & \cdots & \phi_b(x_1) \\ \vdots & \ddots & \vdots \\ \phi_1(x_n) & \cdots & \phi_b(x_n) \\ \end{matrix} \right]$$

训练样本的平方差$J_{LS}$的参数向量$\theta$的偏微分

$$\nabla_{\theta}J_{LS}=(\frac{\partial J_{LS}}{\partial \theta_1},\dots,\frac{\partial J_{LS}}{\partial \theta_b})^{\intercal} = \Phi^{\intercal}\Phi \theta - \Phi^{\intercal}y$$

将其微分设置为0，则

$$\hat{\theta}_{LS} = (\Phi^{\intercal}\Phi)^{-1}\Phi^{\intercal}y$$

对顺序为$i$的训练样本的平方差通过权重$\omega_i \ge 0$进行加权，然后采用最小二乘学习，这称为加权最小二乘学习法

$$\mathop{min}_{\theta} \frac{1}{2}\sum_{i=1}^n \omega_i (f_{\theta}(x_i)-y_i)^2$$

最小二乘解的性质

 设计矩阵$\Phi$的奇异值分解

$$\Phi = \sum_{k=1}^{min(n,b)} \kappa_k \psi_k \varphi_k^{\intercal}$$

$\kappa_k、\psi_k、\varphi_k$分别称为奇异值、左奇异向量、右奇异向量。奇异值全部是非负的，奇异向量满足正交性。

线性模型的最小二乘学习法中，训练输出向量$y$是由$\Phi$的值域$\mathcal{R}(\Phi)$的正投影得到的。

大规模数据的学习算法

 随机梯度算法是指，沿着训练平方误差$J_{LS}$梯度下降，对参数$\theta$依次进行学习的算法。

• 凸函数

对于任意的两点$\theta_1、\theta2$和任意的$t\in [0,1]$

$$J(t\theta_1 + (1-t)\theta_2) \le tJ(\theta_1) + (1-t)J(\theta_2)$$

凸函数是只有一个峰值的函数，所以通过梯度法就可以得到训练平方误差$J_{LS}$在值域范围内的最优解，即全局最优解。

• 使用随机梯度算法对线性模型进行最小二乘学习算法

1. 给$\theta$以适当的初值

2. 随机选择一个训练样本

3. 对于选定的训练样本，采用使其梯度下降的方式，对参数$\theta$进行更新

   $$\theta \leftarrow \theta- \epsilon \nabla J_{LS}^{(i)}(\theta)$$

   在这里，$\epsilon$是名为学习系数的正标量，表示梯度下降的步幅。$\nabla J_{LS}^{(i)}(\theta)$是顺序为$i$的训练样本相对应的训练平方误差的梯度，表示梯度下降的方向。

   $$\nabla J_{LS}^{(i)}(\theta)=\phi(x_i)(f_{\theta}(x_i)-y_i)$$

4. 直到解$\theta$达到收敛精度为止，重复上述2、3步的计算。