注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

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

2013-04-29 09:57:27|  分类: 计算广告学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

逻辑回归优化方法-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阵。它将BFGSO(n*n)空间复杂度降到了O(n*k)k一般是10以内的数。

计算广告学-竞价广告系统-逻辑回归优化方法-L-BFGS - quweiprotoss - Koala++s blog

 

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

       l-BFGS是对Logistic Regression优化的最基本的一个方法,了解它之后对优化的框架和思路会有一个比较清晰的线索。
  评论这张
 
阅读(4331)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017