Logit模型巨蟒解决方案的定义

小开

最佳答案

希望我来得还不算太晚！在深入研究大量信息(警告 : 这不是一个简单的比较，TL; DR)之前，让我先尝试建立一些直觉

简介

假设 h(x)，取一个输入，然后给我们 估计产出值估计产出值。

这个假设可以像一个单变量线性方程一样简单。.达到一个非常复杂和长的多元方程相对于我们使用的算法类型(例如线性回归、 Logit模型等)。

我们的任务是找到  最佳参数 (又名 Theta 或 Weights) ，它给我们预测输出的 最小错误。我们称计算这个误差的函数为 成本或损失函数 ，显然，我们的目标是 最小化的误差，以获得最佳预测输出！

另一件需要回忆的事情是，参数值与其对成本函数的影响(即错误)之间的关系看起来像 钟形曲线(即 二次曲线; 回忆这一点是因为它很重要)。

因此，如果我们从曲线上的任何一点开始，并继续求每个点(假设这是一个单变量问题否则如果我们有多个特征我们就采用偏导数)的导数(即切线) ，我们最终会得到所谓的 Global Optima，如图所示:

如果我们以最小成本点(即全局最优值)取偏导数，我们会发现切线的斜坡 = 0(那么我们就知道我们达到了目标)。

这只有在我们有一个凸起成本函数的情况下才有效，但是如果我们没有，我们最终可能会停留在所谓的  Local Optima 上; 考虑一下这个非凸函数:

现在你应该对我们正在做的事情和术语 派生物，切线，成本函数，假设之间的关系有直觉了。.等等。

附注: 上述直觉也与梯度下降法算法有关(见后文)。

背景资料

线性近似

给定一个函数 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 矩阵是 n X n阶二阶偏导数的方阵)扭曲的故事。

此外，牛顿方法的几何解释是，在每次迭代时，一个人通过围绕 xn的二次函数来近似 f(x)，然后向该二次函数的最大/最小值迈进一步(在更高的维度中，这也可能是鞍点)。注意，如果 f(x)恰好是一个二次函数，那么精确的极值可以在一个步骤中找到。

缺点:

由于 Hessian 矩阵(即二阶偏导数计算) ，它在计算上是 昂贵的。
它吸引到鞍点 ，这是常见的多变量优化(即一个点，它的偏导数不同意这个输入应该是一个最大点还是一个最小点!).

2. 有限内存 Broyden-Fletcher-Goldfarb-Shanno 算法:

简而言之，它类似于牛顿方法，然而这里的黑森矩阵是近似，使用梯度评估(或近似梯度评估)指定的更新。换句话说，使用估计的逆 Hessian 矩阵。

有限内存这个术语仅仅意味着它只存储几个隐含地表示近似的向量。

如果我敢说，当数据集是小强，L-BFGS 相对于其他方法表现最好，特别是因为它节省了大量的内存，但是，有一些“ 认真的”的缺点，如果它是不安全的，它可能不会收敛到任何东西。

注意: 自从版本0.22以来，这个解决方案已经成为 sklearn Logistic 回归中的默认解决方案，取代了 LIBLINEAR。

3. 大型线性分类图书馆:

它是支持 Logit模型和线性支持向量机的线性分类。

求解器使用坐标下降法(CD)算法，通过沿坐标方向或坐标超平面连续执行近似最小化来解决优化问题。

LIBLINEAR是 ICML 2008大规模学习挑战的获胜者。它适用于 自动选择参数自动选择参数(又名 L1正则化) ，当您拥有高维数据集(推荐用于解决大型分类问题)时，建议使用它

缺点:

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

也不能并行运行。

它不能学习一个真正的多项式(多类)模型，相反，最佳化问题以“一对一”的方式分解，所以分离的二进制分类器被训练用于所有类。

旁注: 根据 Scikit 文档: 由于历史原因，在0.22版本之前默认使用的是“ lilinear”求解器。从那时起，默认使用的是有限内存 Broyden-Fletcher-Goldfarb-Shanno 算法。

4. 随机平均梯度:

SAG 方法优化了有限个光滑凸函数的和。与随机梯度(SG)方法一样，SAG 方法的迭代代价与和中的项数无关。但是，通过 结合先前梯度值的记忆，SAG 方法获得了更快的收敛速度比黑盒 SG 方法。

在样本数和特征数都很大的情况下，它比其他很大数据集的解决方案都要优于 再快点。

缺点:

它只支持 L2惩罚。

这并不是真正的缺点，而更像是一种比较: 尽管 SAG 适合于大型数据集，其内存成本为 O(N)，但是对于非常大的 N(因为每个函数的最新梯度计算需要保存在内存中) ，它可能不太实用。这通常不是一个问题，但是一个更好的选择是 SVRG 1，2，不幸的是它没有在 scikit-learn 中实现！

5. 萨加:

SAGA 求解器是 SAG 的变异，也支持非平滑 罚款 L1选项(即 L1正则化)。因此，这是解决稀疏多项式 Logit模型的首选方法。与 SAG 相比，该算法具有更好的理论收敛性。

缺点:

这实际上并不是一个缺点，而更像是一个比较: SAGA 在内存成本方面与 SAG 类似。这是它适合于大型数据集，但在边缘情况下，数据集非常大，SVRG 1，2将是一个更好的选择(遗憾的是没有实现在 scikit-learn) ！

附注: 根据 Scikit 文档: SAGA 求解器通常是最佳选择。

请注意 Scikit-Learning 中使用的属性“大”和“小”，在这个比较中它们是相对的。AFAIK，没有普遍一致和准确的定义的数据集边界被认为是“大”，“太大”，“小”，“太小”... 等！

摘要

下表取自 Scikit 文件

以上连结的更新表格(2021年2月11日) :

小开

我想在 Yahia给出的精彩答案中加上我的两点意见

我的目标是建立直觉，如何从全梯度下降法方法到 SG，然后到 SAG，然后到 SAGA。

随机梯度(SG)方法研究。

SG 利用了这样一个事实，即常用的损失函数可以写成每个样本损失函数的总和 $f(w) = \frac{1}{n} \sum{f_i(w)}$ ，其中 w 是正在优化的权重向量。然后将梯度向量写成每个样本的梯度向量之和: $\nabla f(w) = \frac{1}{n} \sum{\nabla f_i(w)}$ .

最小二乘误差有这种形式

$\frac{1}{n} \sum{({x_i^T*w - y_i})^2}$ ，其中 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = x _ i”alt = “ x _ i”/> 是第 i 个样本的特征，而 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = y _ i”alt = “ y _ i”/> 第 i 个基本真值(目标，因变量)。

Logit模型损失有这种形式(符号 abc 0)

$\frac{1}{n}\sum_{j}^{n}log(1+e^{-y_j(x_j^T*w)})$ .

随机梯度的主要思想是不计算整个损失函数的梯度，而是计算单个随机样本的损失函数 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = f _ i”alt = “ f _ i”/> 的梯度，然后向该样本的梯度方向下降而不是 f (x)的完全梯度。这样快多了。其原因是均匀随机选择的样本梯度代表了对整个损失函数梯度的无偏估计。

在实际应用中，SG 下降的收敛速度比完全下降的收敛速度更慢。 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = O (1% 2Fk)”alt = “ O (1/k)”/> 其中 k 是迭代次数。 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = O (1% 2Fk)”alt = “ O (1/k)”/> 其中 k 是迭代次数。 < img src = “ https://chart.googleapis.com/chart? chl = tx & amp; chl = O (1% 2Fk)”/> 其中 k 是迭代次数。但是由于每次迭代只需要计算一个梯度而不需要计算 n 个梯度，因此在失败次数(简单的算术运算)方面它有更快的收敛速度。它还存在很大的方差(事实上，在选择随机 i 时，我们不一定会下降，我们也可以上升)

演员工会

Src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = O (1% 2Fk)”alt = “ O (1/k)”/> 达到全梯度下降法的收敛速度，而不会使每次迭代的成本比 SG 更高(如果只是一个常数的话)。

最小化 f (w)的 SAG 算法很简单(对于特征的稠密矩阵)。

在第0步，选择一个点 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = w _ 0”alt = “ w _ 0”/> (不考虑你是如何选择的)。用0个内存单元初始化在后面的步骤中保存 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = tx & amp; chl = y _ i”alt = “ y _ i”/> 的梯度。

在步骤 k 更新权重与平均滞后梯度取自记忆单元(滞后，因为他们没有在每一步更新) :

$w_{k+1} = w_k - \frac{\alpha_k}{n}\sum_{i}^{n}y_i$

从1中选择均匀随机索引 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = i _ k”alt = “ i _ k”/> 。.N，只更新一个内存单元 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = y _% 7Bi _ k% 7D”alt = “ y _ { i _ k }”/>

$y_i = \begin{cases} \nabla f_i(w_k) & \text{if $i = i_k$}, \y_i & \text{otherwise} \end{cases}$

看起来我们每一步都在计算滞后梯度的总和但最棒的是我们可以把累积总和存储为一个变量并在每一步对其进行廉价的更新。

我们可以稍微重写一下更新步骤

$w_{k+1} = w_k - \alpha_k(\frac{\nabla f_{i_k}(w_k) - y_{i_k}^k}{n} + \frac{1}{n}\sum_{i}^{n}y^k_i)$

并看到总和 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl =% 5Cfrac% 7B1% 7D% 7Bn% 7D% 5Csum _% 7Bi% 7D% 5E% 7Bn% 7Dy% 5Ek _ i”alt = “ frac {1}{ n } sum _ { i } ^ { n } y ^ k _ i”/> 更新的数量 < img src = “Https://chart.googleapis.com/chart?cht=tx&chl=%5cfrac%7b%5cnabla%20f_%7bi_k%7d(w_k)%20-%20y_%7bi_k%7d%5ek%7d%7bn%7d“ alt =”frac { nabla f _ { i _ k }(w _ k)-y _ { i _ k } ^ k }{ n }“/>

然而，当我们做这个下降步骤时，我们不再是沿着步骤 k 的完整梯度的无偏估计方向，而是沿着方差估计减少的方向(部分原因是我们正在做一个小步骤) ，但是有偏差。我认为这是一个重要而美丽的东西，所以我要引用一段来自 SAGA 论文的摘录:

假设我们想使用蒙特卡罗样本来估计 EX 和我们可以有效地计算另一个随机变量一种方差减少的方法是使用以下估计量 θ 作为 EX 的近似值: θ: = α (X-Y) + 对于步长 α ∈[0,1] ，Eθ 是凸的 EX 和 EY 的组合: Eθ = αEX + (1-α) EY 方差减少法采用 α = 1，估计值为无偏 Eθ = EX.Θ 的方差是: Var (θ) = α ^ 2 * [ Var (X) + Var (Y)-2 Cov (X，Y)] ，因此如果 Cov (X，Y)足够大，θ 的方差就会减小通过把 α 从0变为1, 我们将 θ 的方差增加到它的最大值(即通常仍然小于 X) ，同时减少其偏差接近于零。

因此，我们应用了一个或多或少的标准方差减少方法来得到从 SG 到 SAG。在 SAG 算法中，方差减缩常数 α 等于1/n。如果 Y 是随机选择的 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = y% 5Ek _% 7Bi _ k% 7D”alt = “ y ^ k _ { i _ k }”/> ，X 是 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl =% 5Cnabla% 20f _% 7Bi _ k% 7D (w _ k)”alt = “ nabla f _ { i _ k }(w _ k)”/> ，更新

$w_{k+1} = w_k - \alpha_k(\frac{\nabla f_{i_k}(w_k) - y_{i_k}^k}{n} + \frac{1}{n}\sum_{i}^{n}y^k_i)$

使用形式为1/n * (X-Y) + EY 的全梯度估计

我们提到了 SG 具有高变异性。因此，我们可以说 SAG 是 SG，并应用了一种巧妙的方差减少方法。我不想贬低这些发现的重要性——选择合适的 Y 随机变量并不容易。现在我们可以使用方差减少常数。如果我们取方差减少常数为1，因此使用全梯度的无偏估计，会怎样？

萨加

这是 SAGA 的主要思想。采用 SAG 算法，应用方差减少常数 α = 1的全梯度无偏估计。

更新步骤变大并变成

$w_{k+1} = w_k - \alpha_k(\nabla f_{i_k}(w_k) - y_{i_k}^k + \frac{1}{n}\sum_{i}^{n}y^k_i)$

由于缺乏偏差，收敛性的证明变得简单，并具有比 SAG 情形更好的常数。它还允许额外的技巧，允许 l1正则化。我的意思是近端操作员。

在 SAGA 中最近的梯度下降法步骤

如果你不需要 l1正则化，你可以跳过这一部分，因为在近端操作符上有整个数学理论。

近似算子在某种意义上是梯度下降法的一种推广。(操作符只是一个函数，从一个向量变成一个向量。例如，梯度是一个运算符)

$prox_h(v) = argmin_u(h(u) + \frac{1}{2}|| u-v ||^2)$

其中 h (u)是连续凸函数。

换句话说，它和寻找 h (u)的最小值是一样的，但是如果离开初始点太远，它也会受到惩罚。近似运算符是一个函数，从 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = R% 5En”alt = “ R ^ n”/> 到 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = R% 5En”alt = “ R ^ n”/> (矢量到矢量，就像梯度一样)参数化为 h (x)。它是非扩张的(即 x 和 y 之间的距离在对 x 和 y 应用近似算子后并没有变大)。它的固定点(chl = prox _ h (x)% 20% 3D% 20x”alt = “ prox _ h (x) = x”/>)是最佳化问题的解决方案。迭代应用的近似运算符实际上会收敛到它的不动点(尽管对于非扩张运算符通常不是这样，即对于旋转运算符不是这样)。因此，最简单的算法，找到最小使用近似算子只是应用算子多次 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = x _% 7Bk% 2B1% 7D% 20% 3D% 20prox _% 7B% 5Calalpha% 20h% 7D (x _ k)”alt = “ x _ { k + 1} = prox _ { alpha h }(x _ k)”/> 。这在某种意义上类似于梯度下降法。原因如下:

假设一个可微凸函数 h 而不是梯度下降法更新一个类似的向后欧拉更新:。这个更新可以看作是近端运算符更新 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = x _% 7Bk% 2B1% 7D% 20% 3D% 20prox _% 7B% 5Calalpha% 20h% 7D (x _ k)”alt = “ x _ { k + 1} = prox _ { alpha h }(x _ k)”/> ,因为对于近似算子，我们需要找到 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = x _% 7Bk% 2B1% 7D”alt = “ x _ { k + 1}”/> 最小化 < img src = “Https://chart.googleapis.com/chart?cht=tx&chl=%5calpha%20h(x_%7bk%2b1%7d)%20%2b%20%5cfrac%7b1%7d%7b2%7d%7c%7cx_%7bk%2b1%7d%20-x_k%7c%7c%5e2Alt = “ alpha h (x _ { k + 1}) + frac {1}{2} | | x _ { k + 1}-x _ k | | ^ 2”/> 或者找到 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = x _% 7Bk% 2B1% 7D”alt = “ x _ { k + 1}”/> 使得 < img src = “ https://chart.googleapis.com/chart?cht=tx&chl=%5calpha%20%5cnabla%20h(x_%7bk%2b1%7d)%20%2b%20x_%7bk%2b1%7d%20-%20x_k%20%3d%200”Alt = “ alpha nabla h (x _ { k + 1}) + x _ { k + 1}-x _ k = 0”/> so $x_{k+1} = x_k - \alpha \nabla h(x_{k+1})$

好的，为什么要考虑用一个最小化问题来改变另一个最小化问题(计算近似算子是最小化问题中的一个最小化问题)。对于大多数常见的损失函数的近似算子，其解答要么是闭式的，要么是有效的近似方法。拿 L1调整器。它的近似算子称为软阈值算子，它有一个简单的形式(我试图在这里插入它，但失败了)。

现在回到 SAGA。假设我们最小化 g (x) + h (x) ，其中 g (x)是光滑凸函数，h (x)是非光滑凸函数(例如 l1正则化) ，但是我们能够有效地计算近似算子。因此，该算法首先对 g 进行一个梯度下降法步骤来减小 g，然后对结果应用 h 的近似算子来减小 h。这是 SAGA 中的附加技巧，称为 近端梯度下降法。

为什么 SAG 和 SAGA 非常适合非常大的数据集

在这里，我不确定什么是 sklearn 作者的意思。做一个猜测-非常大的数据集可能意味着特征矩阵是稀疏的(有许多0)。

现在让我们考虑一个线性参数化的损失函数 $f(w) = \frac{1}{n} \sum{f_i(w)} = \frac{1}{n} \sum{l_i(x_i^Tw)}$ 。每个和项有一个特殊的形式 $f_i(w) = l_i(x_i^Tw)$ .{ img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = l _ i”alt = “ l _ i”/> 是单个变量的函数。注意，交叉熵损失和最小二乘损失都有这种形式。链式法则

$\nabla f_i(w) = \begin{bmatrix} X _ i ^ 1l’_ i (x _ i ^ Tw) ... x _ i ^ nl’_ i (x _ i ^ Tw)结束{ b 矩阵}”/> 所以很明显梯度也是稀疏的。 SAG (和 SAGA)对稀疏矩阵应用了一个巧妙的技巧。其思想是权重向量不需要在每一步的每一个索引中更新。当前随机选择的样本 < img src = “ https://chart.googleapis.com/chart? cht = tx & amp; chl = x _ i”alt = “ x _ i”/> 中稀疏的权重向量的指数可以跳过更新。 在 SAG 和 SAGA 中还有其他聪明的技巧。但是如果你做到这一点，我邀请你看看原来的文件 <a href=$ 1和 2。他们写得很好。