search

7. 优化算法

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

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

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

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

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

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

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

    • Lcross entropy(f,y)=−log⁡2(1+fy2)L_{cross\ entropy}(f,y)=-\log_2(\frac{1+fy}{2})

  • Regression

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

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

    • LHuber(f,y)={(f−y)2,∣f−y∣≤δ2δ∣f−y∣−δ2,∣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}，可导性、异常点鲁棒性

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

  • 凸函数：L(λx+(1−λ)y)≤λL(x)+(1−λ)L(y)L(\lambda x+(1-\lambda)y)\le\lambda L(x)+(1-\lambda)L(y)

  • LR 是凸优化问题 Y={1,−1}Y=\{1,-1\}

    • 优化问题：min⁡θL(θ)=∑i=1nlog⁡(1+exp⁡(−yiθTxi))\min_\theta L(\theta)=\sum_{i=1}^n \log(1+\exp(-y_i\theta^Tx_i))

    • 计算二阶 Hessian 矩阵验证，∇2L(θ)=∑i=1n∇2Li(θ)⪰0 \nabla^2L(\theta)=\sum_{i=1}^n \nabla^2L_i(\theta)\succeq 0 半正定

    • 其他例子：SVM、线性回归 等线性模型

  • PCA 是非凸优化

    • 优化问题：min⁡VVT=IkL(V)=∣∣X−VTVX∣∣F2\min_{VV^T=I_k}L(V)=||X-V^TVX||_F^2

    • 如果 V∗V^* 为全局极小值，则 −V∗-V^* 也是全局极小值，且 L(12V∗+12(−V∗))>12L(V∗)+12L(−V∗)L(\frac12V^*+\frac12(-V^*))>\frac12L(V^*)+\frac12L(-V^*)

    • 其他例子：低秩模型（如矩阵分解）、深度NN 等

hashtag
7.3 经典优化算法 **

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

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

      • Ridge Regression L(θ)=∣∣Xθ−y∣∣22+λ∣∣θ∣∣22L(\theta)=||X\theta-y||_2^2+\lambda ||\theta||_2^2，最优解 θ∗=(XTX+λI)−1XTy\theta^*=(X^TX+\lambda I)^-1X^Ty

    • 迭代法 δt=arg⁡min⁡δL(θt+δ)\delta_t=\arg\min_\delta L(\theta_t+\delta)

      • 一阶法（梯度下降法）：θt+1=θt−α∇L(θt)\theta_{t+1}=\theta_t-\alpha \nabla L(\theta_t)

      • 二阶法（牛顿法）：θt+1=θt−∇2L(θt)−1∇L(θt)\theta_{t+1}=\theta_t-\nabla^2L(\theta_t)^{-1}\nabla L(\theta_t)

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

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

hashtag
7.4 梯度验证 ***

  • ∣L(θ+hei)−L(θ−hei)2h−∂L(θ)∂θi∣≈Mh2|\frac{L(\theta+he_i)-L(\theta-he_i)}{2h}-\frac{\partial L(\theta)}{\partial \theta_i}|\approx Mh^2

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

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

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

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

hashtag
7.5 随机梯度下降法 SGD *

  • 目标函数 L(θ)=E(x,y)∼PdataL(f(x,θ),y)L(\theta)=\mathbb{E}_{(x,y)\sim P_{data}}L(f(x,\theta),y)，求解 θ∗=arg⁡min⁡θL(θ)\theta^*=\arg\min_\theta L(\theta)

  • 批量梯度下降法 BGD ablaL(θ)=1M∑i=1M∇L(f(xi,θ),yi)abla L(\theta)=\frac1M \sum_{i=1}^M \nabla L(f(x_i,\theta),y_i)

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

  • 随机梯度下降法 SGD ablaL(θ;xi,yi)=∇L(f(xi,θ),yi)abla L(\theta;x_i,y_i)=\nabla L(f(x_i,\theta),y_i)

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

  • 小批量梯度下降法 mini-batch ablaL(θ)=1m∑j=1m∇L(f(xij,θ),yij)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？调参，衰减学习速率

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

  • SGD 失效原因

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

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

    • local minimum

  • 惯性保持 和 环境感知

    • Momentum：vt=γvt−1+ηgtv_t=\gamma v_{t-1}+\eta g_t，θt+1=θt−vt\theta_{t+1}=\theta_t-v_t，动量 累积 / 抵消（惯性保持）

    • AdaGrad：θt+1,i=θt,i−η∑k=0tgk,i2+ϵgt,i\theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{\sum_{k=0}^t g_{k,i}^2 + \epsilon}} g_{t,i}，历史梯度平方和 => 参数梯度稀疏性（环境感知）

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

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

    • Adam：θt+1=θt−η⋅m^tv^t+ϵ\theta_{t+1}=\theta_t-\frac{\eta\cdot\hat m_t}{\sqrt{\hat v_t +\epsilon}}，其中 m^t=mt1−β1t\hat m_t=\frac{m^t}{1-\beta_1^t}，v^t=vt1−β2t\hat v_t=\frac{v^t}{1-\beta_2^t}

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

        • 一阶矩：mt=β1mt−1+(1−β1)gtm_t=\beta_1 m_{t-1}+(1-\beta_1)g_t，过去梯度与当前梯度的平均，惯性保持

        • 二阶矩：vt=β2vt−1+(1−β2)gt2v_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

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

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

    • 正则项 == 约束条件，min⁡∑i=1N(yi−wTxi)2, s.t.∣∣w∣∣22≤m\min \sum_{i=1}^N(y_i-w^Tx_i)^2,\ s.t. ||w||_2^2 \le m

    • 拉格朗日函数 L(w,λ)=∑i=1N(yi−wTxi)2+λ(∣∣w∣∣22−m)L(w,\lambda)=\sum_{i=1}^N(y_i-w^Tx_i)^2+\lambda(||w||_2^2-m)

    • 若 w∗w^* 和 λ∗\lambda^* 分别是原问题和对偶问题的最优解， 根据 KKT 条件

      • {0=∇w(∑i=1N(yi−wTxi)2+λ(∣∣w∣∣22−m))0≤λ∗\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)+Cw2L(w)+Cw^2

    • L1：L(w)+C∣w∣L(w)+C|w|

    • 在线梯度下降算法中，采用 截断梯度法 产生稀疏性，原理类似

  • 角度3. 贝叶斯先验

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

    • L2：Gaussian 先验

Previous6. 概率图模型Next8. 采样

Last updated