LASSO回归中的凸优化问题

作者

吉鸿

发表时间

2019年03月03日

本文主要是关于最优化的学习笔记,参考的来源有各个博客,教材。

梯度类方法(gradient)

梯度类方法是无约束优化中非常常用的方法。其基本依据是梯度的负方向是函数值下降最快的方向。

Gradient Descent

梯度下降法的迭代公式为:

x(k)=x(k1)tkf(x(k1)) x^{(k)} = x^{(k-1)} - t_k \nabla f(x^{(k-1)}) 上标(k)表示第k次迭代,而tkt_k则表示步长,f(x(k1))\nabla f(x^{(k-1)})表示在点x(k1)x^{(k-1)}的梯度。

不同的步长tkt_k会影响收敛的速度。最简单的方法是选一个恒定的步长,当然也可以选择可变的(adaptive)的步长,即根据每次迭代依照一定的规则来改变步长。下面介绍两种:(1)backtracking line search (2) exact line search

Subgradient Descent

subgradient descent相比于gradient descent可用于求导某些连续不可导的函数梯度不存在的问题。对于可微的凸函数,一阶特性可以表达为:

f(y)f(x)+Tf(x)(yx) f(y) \ge f(x) + \nabla^T f(x)(y-x)

对于函数f(x)=xf(x) = |x|, subgradient

\begin{eqnarray} g = \{_{[-1, 1] \space \space x = 0}^{sign(x) \space \space x \neq 0}\\ \end{eqnarray}

Lasso的凸优化

LASSO对应如下的一个优化问题 minwi=1N(wTxiyi)2+λj=1nwj \color{red}{\min_w \sum_{i=1}^N {(w^Tx_i - y_i)}^2} + \color{skyblue}{\lambda\sum_{j=1}^n |w^j|} 整体上来看,红色的部分是Likelihood function,而蓝色的部分则叫做regularizer。其中xix_i是数据或特征量,yiy_i是对应的值,wjw^j便是向量ww的第j该 component,该优化问题使用线性回归模型去拟合给定的数据,而向量wRnw \in \mathbb{R^n}。当regularizer系数λ\lambda控制得当的话,最优解w则会有很多的component会是零。

要得到最优解,则一个重要部分是需要对regularizer中的l1norm\mathbb{l}_1-norm求导。首先,得要知道对于一个可测函数,存在以下性质: f(x)=f+(x)f(x),f(x)=f+(x)+f(x) f(x) = f^+(x) -f^-(x), |f(x)| = f^+(x) + f^-(x)

f+(x)f^+(x)f(x)f^-(x)分别称为f(x)f(x)的正部和负部。回到LASSO优化问题,任意实数wjw^j也可以表示成正部和负部之差wj=w+jwjw^j = w_+^j - {w^j}_-。因此,LASSO优化可以等价于 minw+,wi=1N((w+w)Txiyi)2+λj=1N(wj++wj)s.t. w+0,w0 \min_{w^+, w^-}\sum_{i =1}^{N}((w^+ - w^-)^Tx_i - y_i)^2 + \color{skyblue}{\lambda\sum_{j=1}^{N}{(w_j^+ + w_j^-)}} \\ s.t. \space{ } w^+ \ge 0,w^- \ge0

Reference

  1. 凸优化总结
  2. freemind的博客-Projected Gradient Method and LASSO
Back to top