7. 优化算法

机器学习 = 模型表征 + 模型评估 + 优化算法

优化算法：在模型表征空间中，找到模型评估指标最好的模型

7.1 有监督学习的损失函数 *

• Binary Classification：$Y=\{1,-1\}$

  • $L_{0-1}(f,y)=1_{fy\le0}$，分类错误率，非凸非光滑

  • $L_{hinge}(f,y)=\max\{0,1-fy\}$，在 $fy=1$ 处不可导，次梯度下降

  • $L_{logistic}(f,y)=\log_2(1+\exp(-fy))$，光滑，梯度下降，但所有样本点惩罚，异常值敏感

  • $L_{cross\ entropy}(f,y)=-\log_2(\frac{1+fy}{2})$

• Regression

  • $L_{MSE}(f,y)=(f-y)^2$，光滑，梯度下降，但异常点敏感

  • $L_{MAE}(f,y)=|f-y|$，中值回归，但在 $f=y$ 处不可导

  • $L_{Huber}(f,y)=\begin{cases}(f-y)^2,&|f-y|\le\delta\\2\delta|f-y|-\delta^2,&|f-y|>\delta\end{cases}$，可导性、异常点鲁棒性

7.2 机器学习中的优化问题 **

• 凸函数：$L(\lambda x+(1-\lambda)y)\le\lambda L(x)+(1-\lambda)L(y)$
• LR 是凸优化问题 $Y=\{1,-1\}$

  • 优化问题：$\min_\theta L(\theta)=\sum_{i=1}^n \log(1+\exp(-y_i\theta^Tx_i))$
  • 计算二阶 Hessian 矩阵验证，$\nabla^2L(\theta)=\sum_{i=1}^n \nabla^2L_i(\theta)\succeq 0$ 半正定
  • 其他例子：SVM、线性回归 等线性模型

• PCA 是非凸优化

  • 优化问题：$\min_{VV^T=I_k}L(V)=||X-V^TVX||_F^2$
  • 如果 $V^*$ 为全局极小值，则 $-V^*$ 也是全局极小值，且 $L(\frac12V^*+\frac12(-V^*))>\frac12L(V^*)+\frac12L(-V^*)$
  • 其他例子：低秩模型（如矩阵分解）、深度NN 等

7.3 经典优化算法 **

• 无约束问题 $\min_\theta L(\theta)$，目标函数光滑

  • 直接法：凸函数，$\nabla L(\theta^*)=0$ 有闭式解

    • Ridge Regression $L(\theta)=||X\theta-y||_2^2+\lambda ||\theta||_2^2$，最优解 $\theta^*=(X^TX+\lambda I)^-1X^Ty$
  • 迭代法 $\delta_t=\arg\min_\delta L(\theta_t+\delta)$

    • 一阶法（梯度下降法）：$\theta_{t+1}=\theta_t-\alpha \nabla L(\theta_t)$
    • 二阶法（牛顿法）：$\theta_{t+1}=\theta_t-\nabla^2L(\theta_t)^{-1}\nabla L(\theta_t)$

      • 收敛快，但高维 Hessian 矩阵求逆复杂度高，非凸可能收敛到鞍点（Saddle Point）

    • 其他：一阶法的加速算法，BFGS，L-BFGS

7.4 梯度验证 ***

• $|\frac{L(\theta+he_i)-L(\theta-he_i)}{2h}-\frac{\partial L(\theta)}{\partial \theta_i}|\approx Mh^2$

  • 取 h 为较小的数（如 $10^{-7}$），验证左式是否 $\le h$

    • 如不成立，固定 $\theta$，减小 h 为原来的 $10^{-1}$，验证近似误差约减小为原来的 $10^{-2}$

      • 如成立，该下标对应的 M 过大，采用更小的 h 重新验证

      • 如不成立，梯度分量计算不正确，检查错误

7.5 随机梯度下降法 SGD *

• 目标函数 $L(\theta)=\mathbb{E}_{(x,y)\sim P_{data}}L(f(x,\theta),y)$，求解 $\theta^*=\arg\min_\theta L(\theta)$
• 批量梯度下降法 BGD $abla L(\theta)=\frac1M \sum_{i=1}^M \nabla L(f(x_i,\theta),y_i)$

  • 采用 所有训练数据 的平均损失，近似目标函数，数据量大时，计算量大

• 随机梯度下降法 SGD $abla L(\theta;x_i,y_i)=\nabla L(f(x_i,\theta),y_i)$

  • 用 单个训练样本 的损失，近似平均损失，加快收敛，适用于 在线更新 场景

• 小批量梯度下降法 mini-batch $abla L(\theta)=\frac1m \sum_{j=1}^m \nabla L(f(x_{i_j},\theta),y_{i_j})$

  • 如何选择 m？调参，2 的幂次，充分利用矩阵运算，e.g. 32, 64, 128, 256

  • 如何挑选 m 个训练数据？shuffle，然后按顺序遍历

  • 如何选取 $\alpha$？调参，衰减学习速率

7.6 随机梯度下降法的加速 ***

• SGD 失效原因

  • 山谷震荡：山壁间来回反弹震荡

  • 鞍点停滞（Saddle Point）：平地 plateau

  • local minimum

• 惯性保持 和 环境感知

  • Momentum：$v_t=\gamma v_{t-1}+\eta g_t$，$\theta_{t+1}=\theta_t-v_t$，动量 累积 / 抵消（惯性保持）
  • AdaGrad：$\theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{\sum_{k=0}^t g_{k,i}^2 + \epsilon}} g_{t,i}$，历史梯度平方和 => 参数梯度稀疏性（环境感知）

    • 更新频率低的参数 - 较大步幅；更新频率高的参数 - 减小步幅

    • 另外，实现了退火过程，学习率越来越小，从而保证收敛

  • Adam：$\theta_{t+1}=\theta_t-\frac{\eta\cdot\hat m_t}{\sqrt{\hat v_t +\epsilon}}$，其中 $\hat m_t=\frac{m^t}{1-\beta_1^t}$，$\hat v_t=\frac{v^t}{1-\beta_2^t}$

    • 惯性保持 & 环境感知（指数衰减平均）

      • 一阶矩：$m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t$，过去梯度与当前梯度的平均，惯性保持
      • 二阶矩：$v_t=\beta_2 v_{t-1}+(1-\beta_2)g_t^2$，梯度平方的平均，类似 AdaGrad
    • 物理意义

      • ||m|| 大且 v 大：梯度大且稳定，明显的大坡

      • ||m|| 小且 v 大：梯度不稳定，可能峡谷，反弹震荡

      • ||m|| 小且 v 小：local minimum，或平地 plateau

  • 其他变种

    • Nesterov Accelerated Gradient：惯性方向，计算未来位置梯度

    • AdaDelta, RMSProp：对 AdaGrad 的改进，采用指数衰减平均，过往梯度均值，代替求和

    • AdaMax：对 Adam 的变种，梯度平方的处理，指数衰减平均 改为 指数衰退最大值

    • Nadam：Nesterov Accelerated Gradient 版的 Adam

7.7 L1 正则化与稀疏化 ***

• 角度1. 解空间形状（KKT条件）

  • 正则项 == 约束条件，$\min \sum_{i=1}^N(y_i-w^Tx_i)^2,\ s.t. ||w||_2^2 \le m$
  • 拉格朗日函数 $L(w,\lambda)=\sum_{i=1}^N(y_i-w^Tx_i)^2+\lambda(||w||_2^2-m)$
  • 若 $w^*$ 和 $\lambda^*$ 分别是原问题和对偶问题的最优解， 根据 KKT 条件

    • $\begin{cases}0=\nabla_w(\sum_{i=1}^N(y_i-w^Tx_i)^2+\lambda(||w||_2^2-m)) \\0\le \lambda^*\end{cases}$
• 角度2. 函数叠加（考虑一维情况）

  • L2：$L(w)+Cw^2$
  • L1：$L(w)+C|w|$
  • 在线梯度下降算法中，采用 截断梯度法 产生稀疏性，原理类似

• 角度3. 贝叶斯先验

  • L1：Laplacian 先验，0 点处是尖峰

  • L2：Gaussian 先验