1.5 随机梯度下降

随机梯度下降(SGD)是一种在凸损失函数(如(线性)支持向量机Logistic回归)下拟合线性分类器和回归器的简单而有效的方法。尽管SGD在机器学习社区中已经存在了很长一段时间,但就在最近大规模学习的背景下,它得到了相当多的关注。

SGD已成功地应用于文本分类和自然语言处理中经常遇到的大规模和稀疏的机器学习问题。由于数据稀疏,本模块中的分类器很容易处理到具有个训练样本和个特征以上的问题。

严格地说,SGD只是一种优化技术,并不与特定的机器学习模型相对应。它只是训练模型的一种方式。通常,scikit-learn API中SGDClassifierSGDRegressor 具有等效的估计,只是可能使用了不同的优化技巧。例如,使用SGDClassifier(loss='log')将导致Logistic回归, 即一个等价于LogisticRegression的模型可以通过SGD拟合而不是LogisticRegression中其他的优化方案。类似的。SGDRegressor(loss='squared_loss', penalty='l2')Ridge就是通过不同的方法解决了相同的优化问题。

随机梯度下降的优点是:

  • 高效
  • 易于实现 (有大量优化代码的机会)

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

  • SGD需要一些超参数,例如正则化参数和迭代次数
  • SGD对特征缩放非常敏感

警告:

在拟合模型之前,一定要重新排序(打乱的)训练数据,或者在每次迭代后(默认情况下使用)使用shuffle=True来打乱数据。此外,理想情况下,应该使用make_pipeline(StandardScaler(), SGDClassifier())(参见 Pipelines)对特征进行标准化。

1.5.1 分类

SGDClassifier 分类器实现了一个简单的随机梯度下降学习程序,支持不同的损失函数和惩罚项。下面是用合页损失(hinge loss)训练的SGDClassifier分类器的决策边界,相当于线性支持向量机。

作为其他分类器,SGD必须fit两个数组:一个包含训练样本的形状(n_samples, n_features) 的X和一个包含训练样本目标值(类标签)的形状 (n_samples)的数组y。

>>> from sklearn.linear_model import SGDClassifier
>>> X = [[0.0.], [1.1.]]
>>> y = [01]
>>> 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_保存了截距项(又被称为 偏移(offset)或者偏差(bias))

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

模型是否使用截距项,即有偏的超平面(a biased hyperplane),是由参数fit_intercept控制的。

到超平面的符号距离(计算为系数和输入样本之间的点积,加上截距)可由 SGDClassifier.decision_function:

>>> clf.decision_function([[2.2.]])
array([29.6...])

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

  • loss="hinge":(软-间隔)线性支持向量机
  • loss="modified_huber:平滑的合页损耗(smoothed hinge loss)
  • loss="log":逻辑回归
  • 以及以下所有的回归损失。在这种情况下,目标被编码为-1或1,并且这个问题被看作是一个回归问题。然后,预测的类对应于预测目标的符号。

请参阅下面的数学部分的公式。前两个损失函数是懒惰的,它们只在一个样本违反边际约束的情况下更新模型参数,这使得训练非常有效,并且也可能导致稀疏模型(即更多的零系数), 即使使用的是L2惩罚。

使用loss="log" 或者 loss="modified_huber" 来激活 predict_proba 方法,这会给每个样本一个概率估计的向量

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

具体的惩罚项可以通过penalty参数来设定。SGD支持以下惩罚项:

  • penalty="l2": L2 范数惩罚 在 coef_
  • penalty="l1": L1 范数惩罚 在 coef_
  • penalty="elasticnet": L1和L2的凸组合; (1 - l1_ratio) * L2 + l1_ratio * L1

默认设置为 penalty="l2"。L1惩罚会导致稀疏解,使大部分系数变为零。弹性网[11]在具有高度相关属性的情况下,解决了L1惩罚的一些不足。参数l1_ratio控制L1和L2惩罚的凸组合。

SGDClassifier分类器通过使用“one versus all” (OVA)方案组合多个二分类器来支持多分类。对于每个类,学习了一个二分类器,该分类器区分该类和所有其他类。在测试时,我们计算每个分类器的置信分数(即到超平面的符号距离),并选择置信度分数最高的类。下图说明了在 iris数据集的OVA方法。虚线表示三个OVA分类器,背景颜色表示由三个分类器决定的的决策面。

在多分类的情况下,coef_是一个形状是 (n_classes, n_features)的二维数组,而intercept_是一个形状是(n_classes,)的一维数组。coef_的第i行是第i类的OVA分类器的权重向量;类按升序进行索引(请参见class_)。请注意,原则上,由于它们允许创建概率模型,所以loss="log"loss="modified_huber"更适合于 one-vs-all分类。

SGDClassifier 分类器可以通过fit方法的参数class_weightsample_weight来支持对类加权和对实例加权。有关更多信息,请参见下面的示例和SGDClassifier.fit的说明文档。

SGDClassifier支持平均最近梯度下降(averaged SGD (ASGD))[10]。通过设置 average=True来启用。ASGD与常规的SGD表现出相同的更新(参见数学公式),但不使用系数的最后一个值作为coef_(即上次更新的值),相反,coef_被设置为所有更新中系数的平均值。

对于具有逻辑损失的分类,另一种采用平均策略的SGD方法是用随机平均梯度(SAG)算法进行的,它可以作为 LogisticRegression中的求解器。

示例
SGD:最大间距分离超平面
在iris数据集上绘制多类SGD
SGD:样本加权
比较各种在线求解器
SVM: 不平衡数据集的分离超平面

1.5.2 回归

SGDRegressor类实现了一个简单的随机梯度下降学习程序,它支持不同的损失函数和惩罚来拟合线性回归模型。 SGDRegressor非常适合于具有大量训练样本(>10.000)的回归问题,对于其他问题,我们建议使用 Ridge, Lasso, 或者 ElasticNet

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

  • loss="squared_loss": Ordinary least squares(普通最小二乘)
  • loss="huber": Huber loss for robust regression(鲁棒回归的Huber损失)
  • loss="epsilon_insensitive": linear Support Vector Regression(线性支持向量回归)

有关公式,请参阅下面的数学部分。Huber和epsilon—insensitive损失函数可用于鲁棒回归。不敏感区域的宽度必须通过参数 epsilon 来设定。这个参数取决于目标变量的规模。

penalty参数确定要使用的正则化(请参阅分类部分中的说明)。

SGDRegressor还支持平均SGD [10] (同样,请参阅分类部分中的说明)。

对于具有平方损失和L2惩罚的回归,另一种具有平均策略的SGD算法可用随机平均梯度(SAG)算法作为岭中的求解器, 就像 Ridge回归的解法。

1.5.3 稀疏数据的随机梯度下降

注意:稀疏实现会产生与密集实现略有不同的结果,这是因为学习速率缩小了。请参阅实施细节

scipy.sparse 支持的格式中,任意矩阵都有对稀疏数据的内置支持方法。但是,为了获得最高的效率,请使用 scipy.sparse.csr_matrix 中定义的 CSR 矩阵格式。

示例
基于稀疏特征的文本分类

1.5.4 复杂度

SGD的主要优点是它的效率,这在训练数据上基本都是线性的。假如 X 是形状为 的矩阵,则训练的成本为, 其中 是迭代次数, 是每个样本非零特征的平均数。

然而,最近的理论结果表明,随着训练集大小的增加,运行时得到一些期望的优化精度并没有提高。

1.5.5 停止准则

当达到给定的收敛水平时, SGDClassifierSGDRegressor提供了两个停止该算法的准则:

  • 使用早期early_stopping=True,输入数据被分割成一个训练集和一个验证集。然后在训练集上对模型进行拟合,并根据在验证集上计算的预测分数(使用分数法)确定停止准则。验证集的大小可以随参数validation_fraction而改变。
  • early_stopping=False的情况下,模型对整个输入数据进行拟合,根据目标函数在训练数据计算确定停止准则。

在这两种情况下,准则都是按历次计算一次的,当该准则不改进n_iter_no_change时,该算法就停止了。用绝对公差法进行了评价改进或者算法在最大迭代次数(max_iter)后,这两种任意一个情况下算法都会停止。

1.5.6 实用技巧

  • 随机梯度下降对特征缩放非常敏感,因此强烈建议对数据进行缩放。例如,将输入向量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)

如果您的属性具有固有的尺度(例如,单词频率或指示特征),则不需要缩放。

  • 找到一个合理的正则化项最好是使用自动超参数搜索,比如 GridSearchCV或者RandomizedSearchCV, 通常的范围是10.0**-np.arange(1,7)

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

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

  • 我们发现,当特征很多或 eta0 很大时, ASGD(平均随机梯度下降) 效果更好。

参考

“Efficient BackProp” Y. LeCun, L. Bottou, G. Orr, K. Müller - In Neural Networks: Tricks of the Trade 1998.

1.5.7 数学公式

我们在这里描述SGD的数学细节。一个很好的概述和收敛速度可以在[12]中找到。

给定一组训练集样本, 其中, 分类问题, 我们的目的是得到线性的得分函数, 其中参数, 并且。为了进行二分类预测,我们简单看一下。为了找到模型参数,我们将正则化训练误差降到最小:

其中是度量模型(mis)拟合的损失函数,是惩罚模型复杂度的正则化项,是控制正则化强度的非负超参数。

对于不同的 选择不同的分类器和回归器:

  • Hinge (软间隔):等价于支持向量分类器

  • Perceptron:

  • Modified Huber:

  • Log: 等价于逻辑回归:

  • Least-Squares:线性回归((Ridge 还是 Lasso 取决于 ) 。

  • Huber: 与最小二乘相比,对离群值不太敏感。当, 并且, 等价于最小二乘。

  • Epsilon-Insensitive:(软间隔)等价于支持向量回归。

如下图所示,上述所有损失函数都可视为错误分类错误(0一1 损失)的上限。

比较流行的正则化penalty 参数)的选择如下:

  • L2 范数:
  • L1 范数: 这会导致稀疏的解
  • Elastic Net:, L2和L1的凸组合,其中是通过1 - l1_ratio指定的。

下图显示了当=1时,不同正则化项在二维参数空间(=2)中的轮廓。

1.5.7.1 SGD

随机梯度下降是求解无约束优化问题的一种优化方法。与(批量)梯度下降相比,SGD通过一次只考虑一个训练样本来逼近的真实梯度。

SGDClassifier类实现了一阶SGD学习程序。该算法对训练样本进行迭代,并对每个样本根据给出的更新规则更新模型参数。

其中 是控制参数空间中学习速率的步长。截距b 类似地被更新,但没有正则化(并且对稀疏矩阵有额外的衰减,详见实现细节)。

的学习速率可以是恒定的,也可以是逐渐衰减的。对于分类,默认的学习率通过(learning_rate='optimal')由下式给出。

其中是时间步长(总共有n_samples * n_iter个时间步长),是基于Léon Bottou提出的启发式算法确定的,这样期望的初始更新与权重的预期大小相当(假设训练样本的范数接近1)。确切的定义可以在BaseSGD中的的_init_t中找到。

对于回归,默认的学习率计划是反向缩放(learning_rate='invscaling'),由下式给出:

其中是用户通过 eta0power_t指定的超参数。

对于固定的学习速率设置,可以使用learning_rate='constant',并且通过指定学习率。

对于自适应下降的学习速率,使用learning_rate='adaptive' , 并使用 eta0指定最起始学习速率。当达到停止条件时,学习速率除以5,算法不停止。当学习速率低于1e-6时,算法停止。

模型参数可以通过coef_intercept_来访问:coef__持有权重w和intercept__含有b。

当使用平均梯度下降(含有参数average)时, coef_被设置为所有更新的平均权重:coef_=, 其中 是所有更新的总数,可以在属性t_中找到。

1.5.8 实现细节

SGD 的实现受到[7]的随机梯度支持向量机的影响。与SvmSGD类似,权重向量表示为标量和向量的乘积,在L2正则化的情况下允许有效的权重更新。在输入X稀疏的情况下,以较小的学习速率(乘以0.01)更新截距,以说明它被更新得更频繁。在每个观察到的示例之后,依次提取训练示例,并降低学习率。我们采用了[8]中的学习计划。对于多分类的来说, 采用的是“one versus all”。对于L1正则化(和弹性网),我们使用了[9]中提出的截断梯度算法。代码是用Cython编写的。

参考资料:

[7] “Stochastic Gradient Descent” L. Bottou - Website, 2010.

[8] “Pegasos: Primal estimated sub-gradient solver for svm” S. Shalev-Shwartz, Y. Singer, N. Srebro - In Proceedings of ICML ‘07.

[9] “Stochastic gradient descent training for l1-regularized log-linear models with cumulative penalty” Y. Tsuruoka, J. Tsujii, S. Ananiadou - In Proceedings of the AFNLP/ACL ‘09.

10(1,2) “Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent” Xu, Wei

[11] “Regularization and variable selection via the elastic net” H. Zou, T. Hastie - Journal of the Royal Statistical Society Series B, 67 (2), 301-320.

[12] “Solving large scale linear prediction problems using stochastic gradient descent algorithms” T. Zhang - In Proceedings of ICML ‘04.