L1-regularized logistic regression

先挖个坑吧,以后慢慢填。

刚读到台大几个学生写的一篇关于L1-regularized logistic regression(L1LR)综述性的论文:“A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification”。使我很受益,他们把各种思路和方法都罗列了出来,使得我可以按图索骥,一一尝试。不至于自己独自瞎忙活。所以我先挖个坑,逐渐的慢慢更新。

关于问题的背景请参考我的Logistic Regression笔记。我认为L1-regularized logistic regression的核心是如何对一个非平滑(non-smooth)的非线性凸函数求最小值的问题。这在数学上是一个很广的topic,够写厚厚一本书了。我在此试图以L1LR为例探一探路。

关于subgradient与BFGS的关系,在这篇A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning 论文中讲的比较好。

Boyd的插值法

http://stanford.edu/~boyd/l1_logreg/

论文: An Interior-Point Method for Large-Scale `1-Regularized Logistic Regression

Glmnet

论文: Regularization paths for generalized linear models via coordinate descent . Jerome H. Friedman, Trevor Hastie, and Robert Tibshirani. Journal of Statistical Software, 33(1):1–22, 2010.

L-BFGS-B

这是一个比较经典的算法了,也可以用在这个问题上。

OWLQN

论文: OrthantWise Limited-memory Quasi-Newton "Scalable Training of L1-Regularized Log-Linear Models(2007)"

视频:

Scalable Training of L1-regularized Log-linear Models

OWL-QN主要的改动有这么几点:

1、 梯度在传递给BFGS用之前,要转换成pseudo gradient。

2、 在计算方向的时候,算出的\(H_k∇f_k\)要用\(∇f_k\)修正,sign不同就要取0。
下面的代码中dir是\(-H_k∇f_k\), g是\(∇f_k\)。\(∇f_k\)是pseudo gradient

    private static void constrainSearchDir(double[] dir, double[] g) {
          for (int i = 0; i != g.length; ++i) {
                if (dir[i] * g[i] >= 0.0) {
                       dir[i] = 0.0;
                }
          }
    }

3、 计算出的newX也需要做投影。根据旧的x求newX的规则是

newX[i]=x[i] + step * dir[i];  
newX[i]=newX[i]*((x[i] == 0.0) ? -grad[i] : x[i])>0?newX[i]:0;  

4、 LBFGS中用来计算逆Hessian矩阵的y(i)(即\(\Delta g\)),用的是未修正的梯度。不是那个pseudo gradient,而是OWLQN修正之前的那个梯度!

关于OWL-QN的一些思考

OWL-QN所选择的pseudo gradient其实是f(x)的所有subgradient中最靠近0的一个(范数最小的一个)。

计算逆Hessian矩阵的y(i)之所以用未修正的梯度是因为|x|的二阶导数等于0(当x不等于0)。

另外,论文中未提及,但是实践中发现,OWLQN会break wolfe condition。所以line search的算法只能用backtracking,又因为初始步长是1,所以每次算出来的step必然是<=1的。

OWLQN的 实现

下面罗列一下我所看见的OWLQN的实现(共计4个),并做一下比较

C/C++:

  1. 论文的原始作者提供了demo代码,发布在research.microsoft.com上。它没有检查curvature condition,它使用αp来计算充分下降条件。

  2. libLBFGS 作者是一个日本人Naoaki Okazaki,任教于日本东北大学。 可以说是他首先把OWLQN的坑都踩了一遍。他是首个指出OWLQN不能和MoreThuente一维搜索算法一起用。他没有检查curvature condition,他使用 Δx 来判断充分下降条件.

Java:
stanfordnlp 中也有 OWLQN 的实现。 stanfordnlp顾名思义,是由Stanford NLP group开发并维护的一个机器学习库。它没有检查curvature condition,它使用 Δx 来判断充分下降条件。它每次循环会检查\(y \cdot s > 0 \) 来维护H正定。

Scala:
breeze 我感觉这个库基本上是从stanfordnlp衍生过来的。 It enforces Wolfe and strong Wolfe conditions,所以我很怀疑它实际中是否真的可用,但是实际上spark mllib就是用的它的实现。它使用 αp 来判断充分下降条件。

但是作者又在注释中写到 “Technically speaking, this is not quite right. dir should be (newX - state.x) according to the paper and the author. However, in practice, this seems fine. And interestingly the MSR reference implementation does the same thing (but they don't do wolfe condition checks.).”

参考

Optimization Methods for l1-Regularization Mark Schmidt,2009
A comparison of numerical optimizers for logistic regression Thomas P. Minka October 22, 2003
我的BFGS的笔记
我的Logistic Regression笔记

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥