sklearn.linear_model.LogisticRegression是否总是收敛到最佳解决方案？

Question

使用此代码时,我注意到它收敛速度令人难以置信(一秒的小部分),即使模型和/或数据非常大.我怀疑在某些情况下,我没有得到任何接近最佳解决方案的东西,但这很难证明.对于某种类型的全局优化器(如流域跳跃算法),可以选择,即使这消耗了100到1000倍的CPU.有没有人对这个问题有任何想法？

Answer 1

这是一个非常复杂的问题,这个答案可能不完整,但应该给你一些提示(因为你的问题也表明了一些知识差距):

• (1)首先,我不同意这种愿望,some type of global optimizer such as the basin hopping algorithm, even if this consumed 100 to 1,000 times as much CPU因为这在大多数情况下(在ML世界中)没有帮助,因为差异是如此微妙,与其他错误相比,优化错误通常可以忽略不计(模型 - 权力;经验 -风险)

  • 阅读"Stochastic Gradient Descent Tricks" (Battou)一些概述(以及错误组件!)
  • 他甚至给出了使用快速近似算法的一个非常重要的理由(如果1000x训练时间不成问题,则不一定非常适合您的情况):近似优化可以实现更好的预期风险,因为在允许的时间内可以处理更多的训练样例

• (2)盆地跳跃是这些高度启发式的全局优化工具(寻找全局最小值而非局部最小值)的一部分,完全没有任何保证(触及NP-硬度和co.).这是你想在这里使用的最后一个算法(见第(3)点)!

• (3)逻辑回归问题是凸优化问题!

  • 局部最小值始终是全局最小值,它来自凸性(我忽略了像严格/唯一解决方案和co这样的东西)!
  • 因此,您将始终使用针对凸优化进行调整的内容!从来没有盆地跳跃!

• (4)存在不同的求解器,每个求解器支持不同的问题变体(不同的正则化和合作).我们并不确切知道您在优化什么,但当然这些求解器在收敛方面的工作方式不同:

  • 请带着以下评论:
  • liblinear:可能使用一些基于CG的算法(共轭梯度),这意味着收敛高度依赖于数据
    • 如果实现准确的收敛完全取决于具体的实现(liblinear是高质量的)
    • 因为它是一阶方法,我称之为一般精度介质
  • sag/saga:似乎有一个更好的收敛理论(没有检查太多),但又一次:它依赖于sklearn的文档中提到的数据,如果解决方案是准确的,则高度依赖于实现细节
    • 因为这些是一阶方法:一般准确性介质
  • newton-cg:一种不精确的牛顿法
    • 一般而言,在收敛方面更加强大,因为线搜索取代了启发式或不断的学习率(LS在一阶选择中成本很高)
    • 具有不精确核心的二阶方法:预期精度:中高
  • lbfgs:准牛顿法
    • 再一般来说,就像newton-cg这样的收敛而言更加强大
    • 二阶法:预期准确度:中高

当然,对于大规模数据(甚至是复杂性),二阶方法会受到更多伤害,并且如前所述,并非所有解算器都支持sklearn中支持的每个logreg-optimization问题.

我希望你能理解这个问题是多么复杂(因为高度复杂的求解器 - 内部).

最重要的事情:

• LogReg是凸的 - >使用求解器来调整无约束凸优化
• 如果你想要中高精度:使用那些可用的二阶方法并进行多次迭代(这是一个参数)
• 如果你想要高精度:使用更加保守/小心的二阶方法(不:hessian-approx;反hessian-approx;截断......):
  • 例如来自凸优化的任何现成求解器
  • 开源:cvxopt,ecos和co.
  • 商业:Mosek
  • (但你需要在他们的框架或一些包装器中自己制定模型;可能有一些经典逻辑回归的例子)
• 正如预期的那样:有些方法会因很多数据而变慢.