1.5. 随机梯度下降#

随机梯度下降 (SGD) 是一种简单而高效的方法，用于在凸损失函数下拟合线性分类器和回归器，例如（线性）支持向量机和逻辑回归。尽管 SGD 在机器学习社区中已经存在很长时间了，但最近在大型学习的背景下，它受到了相当多的关注。

SGD 已成功应用于文本分类和自然语言处理中经常遇到的海量和稀疏机器学习问题。鉴于数据是稀疏的，此模块中的分类器很容易扩展到具有超过 10^5 个训练样本和超过 10^5 个特征的问题。

严格来说，SGD 仅仅是一种优化技术，并不对应于特定的机器学习模型族。它只是一种训练模型的方式。SGDClassifier 或SGDRegressor 的实例通常在 scikit-learn API 中会有一个等效的估计器，可能会使用不同的优化技术。例如，使用 SGDClassifier(loss='log_loss') 会导致逻辑回归，即等效于 LogisticRegression 的模型，它是通过 SGD 拟合的，而不是通过 LogisticRegression 中的其他求解器之一拟合的。类似地，SGDRegressor(loss='squared_error', penalty='l2') 和 Ridge 通过不同的方法解决了相同的优化问题。

随机梯度下降的优点包括：

  • 效率。

  • 易于实现（许多代码调整机会）。

随机梯度下降的缺点包括：

  • SGD 需要许多超参数，例如正则化参数和迭代次数。

  • SGD 对特征缩放敏感。

警告

确保在拟合模型之前对训练数据进行置换（洗牌），或者使用 shuffle=True 在每次迭代后进行洗牌（默认使用）。此外，理想情况下，应该使用例如 make_pipeline(StandardScaler(), SGDClassifier()) 对特征进行标准化（参见管道）。

1.5.1. 分类#

类 SGDClassifier 实现了一个简单的随机梯度下降学习程序，它支持不同的损失函数和用于分类的惩罚项。以下是使用铰链损失（等效于线性 SVM）训练的 SGDClassifier 的决策边界。

../_images/sphx_glr_plot_sgd_separating_hyperplane_001.png

与其他分类器一样，SGD 必须用两个数组拟合：形状为 (n_samples, n_features) 的数组 X，其中包含训练样本；以及形状为 (n_samples,) 的数组 y，其中包含训练样本的目标值（类别标签）。

>>> from sklearn.linear_model import SGDClassifier
>>> X = [[0., 0.], [1., 1.]]
>>> y = [0, 1]
>>> clf = SGDClassifier(loss="hinge", penalty="l2", max_iter=5)
>>> clf.fit(X, y)
SGDClassifier(max_iter=5)

拟合后，模型即可用于预测新值。

>>> clf.predict([[2., 2.]])
array([1])

SGD 将线性模型拟合到训练数据。 coef_ 属性保存模型参数。

>>> clf.coef_
array([[9.9..., 9.9...]])

intercept_ 属性保存截距（又称偏移量或偏差）。

>>> clf.intercept_
array([-9.9...])

模型是否应该使用截距（即有偏超平面）由参数 fit_intercept 控制。

到超平面的带符号距离（计算为系数与输入样本的点积加上截距）由SGDClassifier.decision_function给出。

>>> clf.decision_function([[2., 2.]])
array([29.6...])

具体的损失函数可以通过loss参数设置。SGDClassifier支持以下损失函数：

  • loss="hinge"：（软间隔）线性支持向量机，

  • loss="modified_huber"：平滑铰链损失，

  • loss="log_loss"：逻辑回归，

  • 以及下面所有回归损失。在这种情况下，目标编码为-1或1，问题被视为回归问题。预测的类别然后对应于预测目标的符号。

请参考下面的数学部分了解公式。前两个损失函数是惰性的，只有当一个例子违反了边缘约束时，它们才会更新模型参数，这使得训练非常高效，并且可能导致更稀疏的模型（即具有更多零系数），即使使用了L2惩罚。

使用loss="log_loss"或loss="modified_huber"启用predict_proba方法，该方法为每个样本\(x\)提供概率估计\(P(y|x)\)的向量。

>>> clf = SGDClassifier(loss="log_loss", max_iter=5).fit(X, y)
>>> clf.predict_proba([[1., 1.]]) 
array([[0.00..., 0.99...]])

具体的惩罚项可以通过penalty参数设置。SGD支持以下惩罚项：

  • penalty="l2"：对coef_施加L2范数惩罚。

  • penalty="l1"：对coef_施加L1范数惩罚。

  • penalty="elasticnet"：L2和L1的凸组合；(1 - l1_ratio) * L2 + l1_ratio * L1。

默认设置是penalty="l2"。L1惩罚会导致稀疏解，将大多数系数驱动为零。弹性网络[11]解决了在存在高度相关属性时L1惩罚的一些缺陷。l1_ratio参数控制L1和L2惩罚的凸组合。

SGDClassifier通过在“一对多”（OVA）方案中组合多个二元分类器来支持多类分类。对于每个\(K\)类，学习一个二元分类器来区分它和所有其他\(K-1\)类。在测试时，我们计算每个分类器的置信度分数（即到超平面的带符号距离），并选择置信度最高的类。下图说明了在iris数据集上OVA方法。虚线代表三个OVA分类器；背景颜色显示由三个分类器引起的决策面。

../_images/sphx_glr_plot_sgd_iris_001.png

在多类分类的情况下，coef_是一个形状为(n_classes, n_features)的二维数组，而intercept_是一个形状为(n_classes,)的一维数组。coef_的第i行保存第i类的OVA分类器的权重向量；类按升序索引（参见属性classes_）。请注意，原则上，由于它们允许创建概率模型，loss="log_loss"和loss="modified_huber"更适合一对多分类。

SGDClassifier通过拟合参数class_weight和sample_weight支持加权类和加权实例。有关详细信息，请参见下面的示例以及SGDClassifier.fit的文档字符串。

SGDClassifier支持平均SGD (ASGD)[10]。可以通过设置average=True来启用平均。ASGD执行与常规SGD相同的更新（参见数学公式），但是，它不是使用系数的最后一个值作为coef_属性（即最后一次更新的值），而是将coef_设置为所有更新中系数的**平均**值。intercept_属性也是如此。当使用ASGD时，学习率可以更大，甚至可以保持不变，这在某些数据集上会导致训练时间的加快。

对于具有逻辑损失的分类，另一种具有平均策略的SGD变体可用于随机平均梯度 (SAG) 算法，该算法作为LogisticRegression中的求解器使用。

示例

1.5.2. 回归#

类SGDRegressor实现了简单的随机梯度下降学习程序，它支持不同的损失函数和惩罚项来拟合线性回归模型。SGDRegressor非常适合训练样本数量庞大的回归问题（> 10,000），对于其他问题，我们推荐使用Ridge、Lasso或ElasticNet。

可以通过loss参数设置具体的损失函数。SGDRegressor支持以下损失函数：

  • loss="squared_error"：普通最小二乘法，

  • loss="huber"：用于稳健回归的 Huber 损失函数，

  • loss="epsilon_insensitive"：线性支持向量回归。

请参阅下面的数学公式部分了解公式。Huber 和 epsilon-insensitive 损失函数可用于稳健回归。不敏感区域的宽度必须通过参数epsilon指定。此参数取决于目标变量的尺度。

penalty参数确定要使用的正则化方法（参见上面分类部分的描述）。

SGDRegressor也支持平均 SGD [10]（同样，参见上面分类部分的描述）。

对于具有平方损失和 l2 惩罚的回归问题，另一种具有平均策略的 SGD 变体可通过随机平均梯度 (SAG) 算法获得，该算法作为Ridge中的求解器提供。

1.5.3. 在线单类 SVM#

类sklearn.linear_model.SGDOneClassSVM使用随机梯度下降实现了单类 SVM 的在线线性版本。结合核近似技术，sklearn.linear_model.SGDOneClassSVM可以用来近似在sklearn.svm.OneClassSVM中实现的核化单类 SVM 的解，其复杂度与样本数量呈线性关系。请注意，核化单类 SVM 的复杂度至少与样本数量的平方成正比。sklearn.linear_model.SGDOneClassSVM因此非常适合具有大量训练样本（> 10,000）的数据集，对于这些数据集，SGD 变体可以快几个数量级。

数学细节#

它的实现基于随机梯度下降的实现。实际上，单类 SVM 的原始优化问题如下所示：

\[\begin{split}\begin{aligned} \min_{w, \rho, \xi} & \quad \frac{1}{2}\Vert w \Vert^2 - \rho + \frac{1}{\nu n} \sum_{i=1}^n \xi_i \\ \text{s.t.} & \quad \langle w, x_i \rangle \geq \rho - \xi_i \quad 1 \leq i \leq n \\ & \quad \xi_i \geq 0 \quad 1 \leq i \leq n \end{aligned}\end{split}\]

其中\(\nu \in (0, 1]\)是由用户指定的参数，用于控制异常值的比例和支持向量的比例。消除松弛变量\(\xi_i\)后，此问题等价于：

\[\min_{w, \rho} \frac{1}{2}\Vert w \Vert^2 - \rho + \frac{1}{\nu n} \sum_{i=1}^n \max(0, \rho - \langle w, x_i \rangle) \, .\]

乘以常数\(\nu\)并引入截距\(b = 1 - \rho\)，我们得到以下等效优化问题：

\[\min_{w, b} \frac{\nu}{2}\Vert w \Vert^2 + b\nu + \frac{1}{n} \sum_{i=1}^n \max(0, 1 - (\langle w, x_i \rangle + b)) \, .\]

这类似于数学公式部分中研究的优化问题，其中\(y_i = 1, 1 \leq i \leq n\)，\(\alpha = \nu/2\)，\(L\)是合页损失函数，\(R\)是 L2 范数。我们只需要在优化循环中添加项\(b\nu\)。

与SGDClassifier和SGDRegressor一样，SGDOneClassSVM支持平均 SGD。可以通过设置average=True启用平均。

示例

1.5.4. 稀疏数据的随机梯度下降#

注意

由于截距的学习率降低，稀疏实现的结果与密集实现的结果略有不同。参见实现细节。

内置支持以scipy.sparse支持的任何矩阵格式给出的稀疏数据。但是，为了获得最高的效率，请使用scipy.sparse.csr_matrix中定义的CSR矩阵格式。

示例

1.5.5. 复杂度#

SGD的主要优势在于其效率，它基本上与训练样本的数量呈线性关系。如果X是一个大小为(n, p)的矩阵，则训练的成本为\(O(k n \bar p)\)，其中k是迭代次数（轮数），\(\bar p\)是每个样本的非零属性的平均数量。

然而，最近的理论结果表明，获得所需优化精度的运行时间不会随着训练集大小的增加而增加。

1.5.6. 停止准则#

类SGDClassifier和SGDRegressor提供两个准则，当达到给定的收敛水平时停止算法。

  • 使用early_stopping=True，输入数据被分割成训练集和验证集。然后在训练集上拟合模型，停止准则基于在验证集上计算的预测分数（使用score方法）。可以使用参数validation_fraction更改验证集的大小。

  • 使用early_stopping=False，模型在整个输入数据上拟合，停止准则基于在训练数据上计算的目标函数。

在这两种情况下，准则都按轮次评估一次，当准则连续n_iter_no_change次没有改进时，算法停止。改进是用绝对容差tol评估的，算法在任何情况下最多迭代max_iter次后停止。

参见随机梯度下降的提前停止，了解提前停止效果的示例。

1.5.7. 实践技巧#

  • 随机梯度下降对特征缩放敏感，因此强烈建议缩放您的数据。例如，将输入向量X上的每个属性缩放至[0,1]或[-1,+1]，或将其标准化为均值为0且方差为1。请注意，必须对测试向量应用相同的缩放才能获得有意义的结果。这可以使用StandardScaler轻松完成。

    from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(X_train)  # Don't cheat - fit only on training data
X_train = scaler.transform(X_train)
X_test = scaler.transform(X_test)  # apply same transformation to test data

# Or better yet: use a pipeline!
from sklearn.pipeline import make_pipeline
est = make_pipeline(StandardScaler(), SGDClassifier())
est.fit(X_train)
est.predict(X_test)

    如果您的属性具有内在的尺度（例如，词频或指示符特征），则不需要缩放。

  • 找到合理的正则化项\(\alpha\) 最好使用自动超参数搜索来完成，例如GridSearchCV或RandomizedSearchCV，通常在10.0**-np.arange(1,7)范围内。

  • 根据经验，我们发现SGD在观察大约10^6个训练样本后收敛。因此，迭代次数的合理初步猜测是max_iter = np.ceil(10**6 / n)，其中n是训练集的大小。

  • 如果您将SGD应用于使用PCA提取的特征，我们发现通常明智的做法是用某个常数c缩放特征值，使得训练数据的平均L2范数等于1。

  • 我们发现平均SGD在特征数量较多且eta0较高的情況下效果最佳。

参考文献

1.5.8. 数学公式#

我们在此描述SGD过程的数学细节。可以在[12]中找到一个包含收敛速度的良好概述。

给定一组训练样本\((x_1, y_1), \ldots, (x_n, y_n)\)，其中\(x_i \in \mathbf{R}^m\)且\(y_i \in \mathcal{R}\)（分类时\(y_i \in {-1, 1}\)），我们的目标是学习一个线性评分函数\(f(x) = w^T x + b\)，其模型参数为\(w \in \mathbf{R}^m\)，截距为\(b \in \mathbf{R}\)。为了对二元分类进行预测，我们只需查看\(f(x)\)的符号。为了找到模型参数，我们最小化由下式给出的正则化训练误差：

\[E(w,b) = \frac{1}{n}\sum_{i=1}^{n} L(y_i, f(x_i)) + \alpha R(w)\]

其中\(L\)是衡量模型（误）拟合的损失函数，\(R\)是惩罚模型复杂度的正则化项（又称惩罚项）；\(\alpha > 0\)是控制正则化强度的非负超参数。

损失函数详情#

不同的\(L\)选择会导致不同的分类器或回归器。

  • 合页损失(软边缘): 等价于支持向量机分类。 \(L(y_i, f(x_i)) = \max(0, 1 - y_i f(x_i))\)。

  • 感知器损失: \(L(y_i, f(x_i)) = \max(0, - y_i f(x_i))\)。

  • 修正Huber损失: 当 \(y_i f(x_i) > -1\) 时，\(L(y_i, f(x_i)) = \max(0, 1 - y_i f(x_i))^2\)；否则，\(L(y_i, f(x_i)) = -4 y_i f(x_i)\)。

  • 对数损失: 等价于逻辑回归。 \(L(y_i, f(x_i)) = \log(1 + \exp (-y_i f(x_i)))\)。

  • 平方误差损失: 线性回归 (取决于\(R\)，可能是岭回归或Lasso回归)。 \(L(y_i, f(x_i)) = \frac{1}{2}(y_i - f(x_i))^2\)。

  • Huber损失: 比最小二乘法对异常值更不敏感。当 \(|y_i - f(x_i)| \leq \varepsilon\) 时，它等价于最小二乘法；否则，\(L(y_i, f(x_i)) = \varepsilon |y_i - f(x_i)| - \frac{1}{2} \varepsilon^2\)。

  • ε-不敏感损失 (软边缘): 等价于支持向量机回归。 \(L(y_i, f(x_i)) = \max(0, |y_i - f(x_i)| - \varepsilon)\)。

以上所有损失函数都可以看作是误分类误差（0-1损失）的上界，如下图所示。

../_images/sphx_glr_plot_sgd_loss_functions_001.png

正则化项\(R\)（penalty参数）的常用选择包括：

  • L2范数: \(R(w) := \frac{1}{2} \sum_{j=1}^{m} w_j^2 = ||w||_2^2\)，

  • L1范数: \(R(w) := \sum_{j=1}^{m} |w_j|\)，这会导致稀疏解。

  • 弹性网络: \(R(w) := \frac{\rho}{2} \sum_{j=1}^{n} w_j^2 + (1-\rho) \sum_{j=1}^{m} |w_j|\)，这是L2和L1的凸组合，其中\(\rho\)由1 - l1_ratio给出。

下图显示了在二维参数空间(\(m=2\))中，当\(R(w) = 1\)时，不同正则化项的等高线。

../_images/sphx_glr_plot_sgd_penalties_001.png

1.5.8.1. SGD#

随机梯度下降是一种用于无约束优化问题的优化方法。与（批量）梯度下降相比，SGD通过一次考虑单个训练样本，来近似\(E(w,b)\)的真实梯度。

类SGDClassifier实现了一阶SGD学习程序。该算法迭代训练样本，并针对每个样本根据以下更新规则更新模型参数：

\[w \leftarrow w - \eta \left[\alpha \frac{\partial R(w)}{\partial w} + \frac{\partial L(w^T x_i + b, y_i)}{\partial w}\right]\]

其中\(\eta\)是学习率，它控制参数空间中的步长。截距\(b\)的更新方式类似，但不包含正则化（对于稀疏矩阵，还有额外的衰减，详见实现细节）。

学习率\(\eta\)可以是常数，也可以逐渐衰减。对于分类，默认学习率调度(learning_rate='optimal')由下式给出：

\[\eta^{(t)} = \frac {1}{\alpha (t_0 + t)}\]

其中\(t\)是时间步（共有n_samples * n_iter个时间步），\(t_0\)基于Léon Bottou提出的启发式方法确定，使得预期的初始更新与权重的预期大小相当（假设训练样本的范数约为1）。精确定义可在BaseSGD中的_init_t中找到。

对于回归，默认学习率调度是反比例缩放(learning_rate='invscaling')，由下式给出：

\[\eta^{(t)} = \frac{eta_0}{t^{power\_t}}\]

其中\(eta_0\)和\(power\_t\)是由用户通过eta0和power_t分别选择的超参数。

对于恒定的学习率，使用learning_rate='constant'并使用eta0指定学习率。

对于自适应递减的学习率，使用learning_rate='adaptive'并使用eta0指定起始学习率。当达到停止标准时，学习率除以5，算法不会停止。当学习率低于1e-6时，算法停止。

模型参数可以通过coef_和intercept_属性访问：coef_保存权重\(w\)，intercept_保存\(b\)。

当使用平均SGD（使用average参数）时，coef_设置为所有更新的平均权重：coef_ \(= \frac{1}{T} \sum_{t=0}^{T-1} w^{(t)}\)，其中\(T\)是总更新次数，可在t_属性中找到。

1.5.9. 实现细节#

SGD 的实现受 Stochastic Gradient SVM 的影响，该方法参考文献[7]。与 SvmSGD 类似，权重向量表示为标量和向量的乘积，这允许在 L2 正则化的情况下进行高效的权重更新。对于稀疏输入 X，截距的更新使用较小的学习率（乘以 0.01），以考虑它被更频繁更新的事实。训练样本是按顺序选择的，并且在观察到每个样本后都会降低学习率。我们采用了参考文献[8]中的学习率调度方案。对于多类别分类，使用“一对多”方法。对于 L1 正则化（和弹性网络），我们使用了参考文献[9]中提出的截断梯度算法。代码是用 Cython 编写的。

参考文献