竞价广告系统-逻辑回归优化方法-L-BFGS

时间:2024-01-18 14:21:44

逻辑回归优化方法-L-BFGS

逻辑回归的优化方法是一个经典的问题,如果我们把它视为一个最大熵模型,那么我们知道最早的优化方法是IIS,这个方法就不细讲了,因为它速度很慢。后来发现在最优化领域中非常常用的l-BFGS方法对于Logistic Regression的收敛速度优化是不错的。

l-BFGS方法是Quasi-Newton方法中的一种,我想从工程角度谈一下我的看法,上次我们谈到在分布式环境下进行模型的优化,无非有两种思路,一,如果数据是mixture of exponent family的分布,用mapper进行E步骤,reducer进行M步骤进行迭代优化,这种是比较简单的方法。如果不是mixture of exponent family的情况,就用基于导数,基于梯度的方法优化。但基于梯度的方法有一个问题,比如有两次函数中,函数等高线是一个非常扁的椭圆,那么基于梯度的收敛速度是很慢的。在实际的工程问题中,这种病态的函数是很常见的,因为在工程中有成千上万的特征,它们的物理意义有时候是不明确的,无法统一的对它们进行归一化处理,因此无法用一阶导数的方法很快的求解,那么我们可以用二阶的导数,根据前两次的路径,大概求得它两次的求值是什么,这样就可以校正它的方向,使得它快速收敛。所以Quasi-Newton在工程中是必要的方法,而不只是优化的方法。那么这种方法与Newton法有什么不同呢?在Newton法中要求Hession矩阵是正定的,但在实际问题中,很难保证是正定的。BFGS的思路是用函数值和特征的变化量来近似Hession矩阵,以保证正定性,并减少计算量。Hession阵是通过前几步的路径,估计出一个二阶导数,它有不同的估计方法,BFGS就是其中一种估计方法。

L(imited memory)-BFGS它是为了解决空间复杂度的问题,虽然Hession阵可以估计可以计算,但它的规模太大,对于刚才说的点击率预测问题,它可能有上亿个特征,而Hession是一个n*n 的矩阵。而在L-BFGS,它是对Hession进行近似,将它拆为一个单位阵加上三个小的矩阵之积,假设选择一个比较小的k值以近似前面的Hession阵。它将BFGS的O(n*n)空间复杂度降到了O(n*k),k一般是10以内的数。

竞价广告系统-逻辑回归优化方法-L-BFGS

l-BFGS在特征量大时比BFGS实用,可以非常容易用map/reduce实现分布式求解,mapper求部分数据上的梯度,reducer求和并更新参数。它与梯度法实现复杂一点的地方在,它需要保存前几次的模型,才能计算当前迭代的更新值。

l-BFGS是对Logistic Regression优化的最基本的一个方法,了解它之后对优化的框架和思路会有一个比较清晰的线索。