逻辑回归 python 求解器的定义
Logistic regression python solvers' definitions
我正在使用 sklearn 中的逻辑回归函数，想知道每个求解器在幕后实际做了什么来解决优化问题。
谁能简单介绍一下“newton-cg”、“sag”、“lbfgs”和“liblinear”在做什么？
好吧，我希望我参加聚会还不算太晚！在挖掘大量信息之前，让我先尝试建立一些直觉（警告：这不是简短的比较，TL；DR）
简介
一个假设h(x)，接受一个输入并给我们估计输出值。
这个假设可以像单变量线性方程一样简单，..根据我们正在使用的算法类型，可以是非常复杂和长的多元方程（例如线性回归、逻辑回归等).
我们的任务是找到 最佳参数（a.k.a Thetas 或权重）给我们 最小错误 预测输出。我们称计算这个误差的函数为成本或损失函数；显然我们的目标是 最小化 错误以获得最佳预测输出！
还有一件事要记住，参数值与其对成本函数的影响（即误差）之间的关系看起来像 钟形曲线 （即 Quadratic；记住这一点，因为它很重要）。
因此，如果我们从该曲线上的任何一点开始并继续对我们停止的每个点求导数（即切线）（假设这是一个单变量问题，否则，如果我们有多个特征，我们采用偏导数)，我们将最终达到所谓的全局最优，如图所示：
如果我们在最小成本点（即全局最优）处取偏导数，我们会发现切线的 斜率 = 0（然后我们知道我们达到了目标）。
只有当我们有一个 Convex 成本函数时才有效，但如果我们不这样做，我们可能最终会陷入所谓的 局部最优；考虑这个非凸函数：
现在你应该对我们正在做的事情和术语之间的关系有了直觉：Deravative, Tangent Line, 成本函数、假设 ..等
旁注：上述直觉也与梯度下降算法有关（见下文）。
背景
线性近似：
给定一个函数 f(x)，我们可以找到它在 x=a 处的切线。切线L(x)的方程为：L(x)=f(a)+f′(a)(x−a).
看看下面的函数图及其切线：
从这张图中我们可以看出，在x=a附近，切线和函数有几乎相同的图形。有时，我们会在 x=a 附近使用切线 L(x) 作为函数 f(x) 的近似值。在这些情况下，我们将切线称为 x=a.
处函数的“线性逼近”
二次近似：
与线性近似相同，但这次我们处理的是一条曲线，我们无法通过使用找到靠近0的点只有 切线.
相反，我们使用 抛物线，如下图所示：
为了拟合好的抛物线，抛物线和二次函数应该有相同的值，相同的一阶导数，并且相同二阶导数。公式将是（只是出于好奇）：Qa(x) = f(a) + f'(a)(x-a) + f''(a)(x-a)2/2
现在我们应该准备好进行详细比较了。
方法比较
1.牛顿法
回想一下 x 梯度下降步骤的动机：我们最小化二次函数（即成本函数）。
牛顿法在某种意义上使用了更好的二次函数最小化。
更好，因为它使用二次近似（即第一个和第二个偏导数）。
你可以把它想象成一个带有 Hessian 矩阵的扭曲梯度下降（Hessian 矩阵是 n X n 阶的二阶偏导数的方阵）。
此外，牛顿法的几何解释是，在每次迭代中，通过围绕 xn 的二次函数逼近 f(x)，然后向 maximum/minimum 迈出一步二次函数（在更高的维度中，这也可能是一个 鞍点 ）。请注意，如果 f(x) 恰好是二次函数，则一步找到精确的极值。
缺点：
计算量昂贵因为Hessian矩阵（即二阶偏导数计算）
它吸引到多变量优化中常见的鞍点（即其偏导数不一致的点关于这个输入应该是最大点还是最小点！）。
2。有限内存 Broyden–Fletcher–Goldfarb–Shanno 算法：
简而言之，它类似于牛顿法，但这里的 Hessian 矩阵是 近似值 使用梯度评估指定的更新（或近似梯度评估）。换句话说，使用对逆海森矩阵的估计。
术语有限内存仅表示它仅存储几个隐式表示近似值的向量。
如果我敢说当数据集small时，L-BFGS相对于其他方法表现最好，尤其是它节省了很多内存，但是有一些“严重”的缺点，如果不加以保护，它可能不会收敛到任何东西。
旁注：自 0.22 版以来，此求解器已成为 sklearn LogisticRegression 中的默认求解器，取代了 LIBLINEAR。
3。大型线性分类库：
这是一个支持逻辑回归和线性支持向量机的线性分类。
求解器使用坐标下降 (CD) 算法，通过沿坐标方向或坐标超平面连续执行近似最小化来求解优化问题。
LIBLINEAR是ICML 2008大规模学习挑战赛的获胜者。它应用自动参数选择（a.k.a 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 的 变体 ，它还支持非平滑 penalty L1 选项（即 L1 正则化）。因此，这是 sparse 多项逻辑回归的首选求解器，也是 very Large 数据集的 suitable。
旁注：根据 Scikit 文档：SAGA 求解器通常是最佳选择。
总结
以下table摘自Scikit Documentation
从上面的 link 更新 Table（访问时间为 02/11/2021）：
我正在使用 sklearn 中的逻辑回归函数，想知道每个求解器在幕后实际做了什么来解决优化问题。
谁能简单介绍一下“newton-cg”、“sag”、“lbfgs”和“liblinear”在做什么？
好吧，我希望我参加聚会还不算太晚！在挖掘大量信息之前，让我先尝试建立一些直觉（警告：这不是简短的比较，TL；DR）
简介
一个假设h(x)，接受一个输入并给我们估计输出值。
这个假设可以像单变量线性方程一样简单，..根据我们正在使用的算法类型，可以是非常复杂和长的多元方程（例如线性回归、逻辑回归等).
我们的任务是找到 最佳参数（a.k.a Thetas 或权重）给我们 最小错误 预测输出。我们称计算这个误差的函数为成本或损失函数；显然我们的目标是 最小化 错误以获得最佳预测输出！
还有一件事要记住，参数值与其对成本函数的影响（即误差）之间的关系看起来像 钟形曲线 （即 Quadratic；记住这一点，因为它很重要）。
因此，如果我们从该曲线上的任何一点开始并继续对我们停止的每个点求导数（即切线）（假设这是一个单变量问题，否则，如果我们有多个特征，我们采用偏导数)，我们将最终达到所谓的全局最优，如图所示：
如果我们在最小成本点（即全局最优）处取偏导数，我们会发现切线的 斜率 = 0（然后我们知道我们达到了目标）。
只有当我们有一个 Convex 成本函数时才有效，但如果我们不这样做，我们可能最终会陷入所谓的 局部最优；考虑这个非凸函数：
现在你应该对我们正在做的事情和术语之间的关系有了直觉：Deravative, Tangent Line, 成本函数、假设 ..等
旁注：上述直觉也与梯度下降算法有关（见下文）。
背景
线性近似：
给定一个函数 f(x)，我们可以找到它在 x=a 处的切线。切线L(x)的方程为：L(x)=f(a)+f′(a)(x−a).
看看下面的函数图及其切线：
从这张图中我们可以看出，在x=a附近，切线和函数有几乎相同的图形。有时，我们会在 x=a 附近使用切线 L(x) 作为函数 f(x) 的近似值。在这些情况下，我们将切线称为 x=a.
二次近似：
与线性近似相同，但这次我们处理的是一条曲线，我们无法通过使用找到靠近0的点只有 切线.
相反，我们使用 抛物线，如下图所示：
为了拟合好的抛物线，抛物线和二次函数应该有相同的值，相同的一阶导数，并且相同二阶导数。公式将是（只是出于好奇）：Qa(x) = f(a) + f'(a)(x-a) + f''(a)(x-a)2/2
现在我们应该准备好进行详细比较了。
方法比较
1.牛顿法
回想一下 x 梯度下降步骤的动机：我们最小化二次函数（即成本函数）。
牛顿法在某种意义上使用了更好的二次函数最小化。 更好，因为它使用二次近似（即第一个和第二个偏导数）。
你可以把它想象成一个带有 Hessian 矩阵的扭曲梯度下降（Hessian 矩阵是 n X n 阶的二阶偏导数的方阵）。
此外，牛顿法的几何解释是，在每次迭代中，通过围绕 xn 的二次函数逼近 f(x)，然后向 maximum/minimum 迈出一步二次函数（在更高的维度中，这也可能是一个 鞍点 ）。请注意，如果 f(x) 恰好是二次函数，则一步找到精确的极值。
缺点：
计算量昂贵因为Hessian矩阵（即二阶偏导数计算）
它吸引到多变量优化中常见的鞍点（即其偏导数不一致的点关于这个输入应该是最大点还是最小点！）。
2。有限内存 Broyden–Fletcher–Goldfarb–Shanno 算法：
简而言之，它类似于牛顿法，但这里的 Hessian 矩阵是 近似值 使用梯度评估指定的更新（或近似梯度评估）。换句话说，使用对逆海森矩阵的估计。
术语有限内存仅表示它仅存储几个隐式表示近似值的向量。
如果我敢说当数据集small时，L-BFGS相对于其他方法表现最好，尤其是它节省了很多内存，但是有一些“严重”的缺点，如果不加以保护，它可能不会收敛到任何东西。
旁注：自 0.22 版以来，此求解器已成为 sklearn LogisticRegression 中的默认求解器，取代了 LIBLINEAR。
3。大型线性分类库：
这是一个支持逻辑回归和线性支持向量机的线性分类。
求解器使用坐标下降 (CD) 算法，通过沿坐标方向或坐标超平面连续执行近似最小化来求解优化问题。
LIBLINEAR是ICML 2008大规模学习挑战赛的获胜者。它应用自动参数选择（a.k.a 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 的 变体 ，它还支持非平滑 penalty L1 选项（即 L1 正则化）。因此，这是 sparse 多项逻辑回归的首选求解器，也是 very Large 数据集的 suitable。
旁注：根据 Scikit 文档：SAGA 求解器通常是最佳选择。
总结
以下table摘自Scikit Documentation
从上面的 link 更新 Table（访问时间为 02/11/2021）：