python - 逻辑回归python求解器的定义

Question

我正在使用 sklearn 的逻辑回归函数，并且想知道每个求解器实际上在幕后做什么来解决优化问题。
有人可以简要描述一下“newton-cg”、“sag”、“lbfgs”和“liblinear”在做什么吗？

Answer 1

好吧，我希望我参加聚会还不算太晚!在挖掘大量信息之前，让我先尝试建立一些直觉( 警告 :这不是简短的比较)

简介
一个假设 h(x) , 接受一个输入并给我们估计的输出值。
这个假设可以是一个简单的单变量线性方程，也可以是一个非常复杂和长的多元方程，与我们使用的算法类型有关(即线性回归、逻辑回归等)。

我们的任务是找到 最佳参数 (a.k.a Thetas 或 Weights) 给我们 最小错误 在预测输出时。我们将此错误称为 成本或损失函数 显然我们的目标是 最小化 它以获得最佳预测输出!
还有一件事要记住，参数值与其对成本函数的影响(即误差)之间的关系看起来像 钟形曲线 (即 二次方 ；记住这一点，因为它非常重要)。
因此，如果我们从该曲线的任何一点开始，并且继续取我们停止的每个点的导数(即切线)，我们最终会得到所谓的 。环球优品如图所示:

如果我们在最小成本点(即全局最优)处取偏导数，我们会找到 坡度切线 = 0 (然后我们知道我们达到了目标)。
这仅在我们有凸成本函数时才有效，但如果我们没有，我们可能最终会陷入所谓的 本地最优 ;考虑这个非凸函数:

现在您应该对我们正在做的事情与术语之间的 hack 关系有了直觉:Deravative、Tangent Line、Cost Function、Hypothesis ..等。
旁注:上述直觉也与梯度下降算法有关(见下文)。

背景
线性近似:
给定一个函数，f(x) ，我们可以在 x=a 处找到它的切线.切线L(x)的方程为:L(x)=f(a)+f′(a)(x−a) .
看看下面的函数及其切线图:

从这张图中我们可以看到在x=a附近，切线和函数具有几乎相同的图形。有时我们会使用切线，L(x) ，作为函数的近似值，f(x) , 附近 x=a .在这些情况下，我们将切线称为 x=a 处函数的线性近似。 .
二次近似:
与线性近似相同，但这次我们处理的是曲线，但我们 不能 找到靠近 的点0 通过使用切线。
相反，我们使用 抛物线 (这是一条曲线，其中任何点与固定点或固定直线的距离相等)，如下所示:

为了拟合一个好的抛物线，抛物线和二次函数应该具有相同的值，相同的一阶导数和二阶导数，......公式将是(只是出于好奇):Qa(x) = f(a) + f'(a)(x-a) + f''(a)(x-a)2/2现在我们应该准备好进行详细的比较了。

方法之间的比较
1. 牛顿法
回想 x 处梯度下降步骤的动机:我们最小化二次函数(即成本函数)。
牛顿方法在某种意义上使用了 更好 二次函数最小化。
更好，因为它使用二次近似(即一阶和二阶偏导数)。
您可以将其想象为带有 Hessian 的扭曲梯度下降(Hessian 是 nxn 阶二阶偏导数的方阵)。
此外，牛顿方法的几何解释是，在每次迭代中，一个近似于 f(x)由 xn 附近的二次函数，然后朝着该二次函数的最大值/最小值迈出一步(在更高的维度中，这也可能是一个鞍点)。请注意，如果 f(x)恰好是一个二次函数，那么在一步中找到精确的极值。
缺点:

这是计算上的 贵 因为 Hessian 矩阵(即二阶偏导数计算)。

它吸引到鞍点 这在多变量优化中很常见(即它的偏导数不同意这个输入应该是最大值还是最小值!)。

2. 有限内存 Broyden–Fletcher–Goldfarb–Shanno 算法:
简而言之，它类似于牛顿法，但这里的 Hessian 矩阵是 近似 使用梯度评估(或近似梯度评估)指定的更新。换句话说，使用对 Hessian 逆矩阵的估计。
有限内存一词仅表示它仅存储一些隐式表示近似值的向量。
如果我敢说当数据集是 小 , L-BFGS 与其他方法相比相对表现最好，尤其是它节省了大量内存，但是也有一些“严重”的缺点，如果它不 protected ，它可能不会收敛到任何东西。
旁注:自 0.22 版以来，此求解器已成为 sklearn LogisticRegression 中的默认求解器，取代了 LIBLINEAR。
3. 大型线性分类库:
它是一种支持逻辑回归和线性支持向量机的线性分类(线性分类器通过基于特征的线性组合值即特征值做出分类决策来实现这一点)。
求解器使用坐标下降 (CD) 算法，通过沿坐标方向或坐标超平面连续执行近似最小化来解决优化问题。 LIBLINEAR是ICML 2008大规模学习挑战赛的获胜者。它应用自动参数选择(又名 L1 正则化)，当你有高维数据集时推荐使用(推荐用于解决大规模分类问题)
缺点:

如果函数的水平曲线不平滑，它可能会卡在非平稳点(即非最优)。

也不能并行运行。

它无法学习真正的多项式(多类)模型；相反，优化问题以“one-vs-rest”方式分解，因此针对所有类别训练单独的二元分类器。

旁注:根据 Scikit 文档:“liblinear”求解器是 0.22 版本之前的历史原因默认使用的求解器。从那时起，默认使用的是有限内存 Broyden–Fletcher–Goldfarb–Shanno 算法。
4. 随机平均梯度:
SAG 方法优化有限数量的平滑凸函数的总和。与随机梯度 (SG) 方法一样，SAG 方法的迭代成本与总和中的项数无关。但是，通过 结合先前梯度值的内存，SAG 方法实现了更快的收敛速度 比黑盒SG方法。
是 更快 当样本数量和特征数量都很大时，与其他大型数据集求解器相比。
缺点:

它只支持 L2 惩罚。

其内存成本为O(N) ，这可能使它对于大 N 不切实际(因为它会记住大约所有梯度的最近计算值)。

5. 传奇:
SAGA 求解器是 SAG 的一个变体，它也支持非平滑惩罚=l1 选项(即 L1 正则化)。因此，这是 的首选求解器稀疏 多项逻辑回归也适用 非常大数据集。
旁注:根据 Scikit 文档:SAGA 求解器通常是最佳选择。

总结
下表摘自 Scikit Documentation