求解L1正则化问题

求解L1正则化问题

Sub-Gradient

次梯度定义了一个新的梯度,使得不可微的点也有梯度。左导数 <= 次梯度 <= 右导数
为了避免负次梯度不是下降的方向,采用了保留当前最优点的更新方法。

参考资料 很详细

次梯度法 - 维基百科,自由的百科全书

SubGradient_百度文库

OWLQN

阅读 理解机器学习中常用优化方法 | Oath2yangmen’s Blog 中的OWL-QN部分

OWLQN说明

Proximal Gradient Descent

回顾 lipschitz 条件 及它的含义 lipschitz条件_百度百科

参考 ISTA算法求解L1正则化问题 - CSDN博客

参考 Proximal Gradient Descent

参考 Proximal Algorithm 入门 - CSDN博客

lipschitz条件限定了函数的导数存在一个上界。

PGD推导-1

PGD推导-2

所以其实Proximal Gradient Descent是将优化复杂的函数 f (x) 的问题等价转化为优化f (x)的上界问题。

Spark里L1正则问题的求解方法

以spark里线性回归求解方法为例

优化器选择支持3个选项:

a. normal : normal equation 得到解析解

b. l-bfgs

c. auto 按照后面的条件自行选择

1. 低维数据且L2正则化  -> WeightedLeastSquares via normal equation
 For low dimensional data, WeightedLeastSquares is more efficiently since the training algorithm only requires one pass through the data.(SPARK-10668)

2. 无正则项或L2正则化 -> l-bfgs

3. 其他 -> OWLQN

之前Spark还提供SGD梯度下降求解,使用L1正则时用Proximal Gradient Descent方法。

Spark PGD实现-1

Spark PGD实现-1

现在Spark 2.0.0之后建议 “ Use ml.regression.LinearRegression or LBFGS”,即前面说三个选项。

其他Spark优化器的细节可阅读 optimization-of-linear-methods-developer - Spark 2.2.1 Documentation

0 Comments