sklearn中的梯度下降法(SGD)

Reading time ~1 minute

介绍

梯度下降法(SGD)是一个简单有效的方法,用于判断使用凸loss函数(convex loss function)的分类器(SVM或logistic回归)。即使SGD在机器学习社区已经存在了很久,到它被广泛接受也是最近几年。

SGD被成功地应用在大规模稀疏机器学习问题上(large-scale and sparse machine learning),经常用在文本分类及自然语言处理上。假如数据是稀疏的,该模块的分类器可以轻松地解决这样的问题:超过10^5的训练样本、超过10^5的features。

SGD的优点是:

  • 高效
  • 容易实现(有许多机会进行代码调优)

SGD的缺点是:

  • SGD需要许多超参数:比如正则项参数、迭代数。
  • SGD对于特征归一化(feature scaling)是敏感的。

2.分类

注意:在对模型进行拟合前,必须重排(permute/shuffle)你的训练数据集; 或者在每次迭代后使用shuffle=True 进行shuffle。

SGDClassifier类实现了一个为分类设计的普通随机梯度下降学习,它支持不同的loss函数和罚项。

和其它分类器一样,SGD必须使用两个array数姐:一个数组X(其size为[n_samples, n_features]):保存着训练样本;一个数组Y:保存着训练样本的target值(class label):

>>> from sklearn.linear_model import SGDClassifier
>>> X = [[0., 0.], [1., 1.]]
>>> y = [0, 1]
>>> clf = SGDClassifier(loss="hinge", penalty="l2")
>>> clf.fit(X, y)
SGDClassifier(alpha=0.0001, average=False, class_weight=None, epsilon=0.1,
       eta0=0.0, fit_intercept=True, l1_ratio=0.15,
       learning_rate='optimal', loss='hinge', n_iter=5, n_jobs=1,
       penalty='l2', power_t=0.5, random_state=None, shuffle=True,
       verbose=0, warm_start=False)

在fit后,模型就可以用来进行预测:

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

SGD可以为训练数据拟合线性模型。属性coef_保存着模型参数:

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

属性intercept_保存着intercept(aka offset or bias):

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

通过设置参数fit_intercept来控制模型是否使用intercept(一个偏差超平面 biased hyperplane)

为了得到与该超平面的有符号距离,可以使用SGDClassifier.decision_function:

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

loss function可以通过loss参数进行设置。SGDClassifier支持下面的loss函数:

  • loss=”hinge”: (soft-margin)线性SVM.
  • loss=”modified_huber”: 带平滑的hinge loss.
  • loss=”log”: logistic回归
  • 以及下面所提到的所有回归的loss

前两个loss函数都是lazy的,如果相应的一个示例违反了这个margin约束,它们只更新模型参数,这使得训练非常有效,并可能导致稀疏的模型,即使使用了L2罚项。

使用loss=”log” 或 loss=”modified_huber”可以启用predict_proba方法,它给出了一个概率估计向量,每个样本x都有对应一个P(y x):
>>> clf = SGDClassifier(loss="log").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的convex组合; (1 - l1_ratio) * L2 + l1_ratio * L1

缺省设置为:penalty=”l2”。L1罚项会导致稀疏解决方案,产生许多零系数。Elastic Net可以解决L1罚项在高度相关属性上的一些不足。参数l1_ratio控制着L1和L2罚项的convex组合。

SGDClassifier支持多分类,它以”one-vs-all(OVA)”的方式通过结合多个二分类来完成。对于K个类中的每个类来说,一个二分类器可以通过它和其它K-1个类来进行学习得到。在测试时,我们会为每个分类器要计算置信度(例如:到超平面的有符号距离),并选择最高置信度的类。下图展示了对iris数据集进行OVA方式分类。虚线表示三个OVA分类器,背影色展示了三个分类器产生的决策边界。

在多分类问题上,coef_是一个二维数组:shape=[n_classes, n_features],intercept_是一个一维数组:shape=[n_classes]. coef_的第i行保存着OVA分类器对第i类的权重向量;这些类通过升序方式索引(详见属性classes_)。注意,原则上,因为他们允许创建一个概率模型,loss=”log” 和 loss=”modified_huber”更合适one-vs-all分类。

SGDClassifier 支持带权重的分类和带权重的实例,通过fit参数:class_weight 和 sample_weight。详见:SGDClassifier.fit。

示例:

SGDClassifier 支持平均随机梯度下降法(ASGD)。可以通过设置

1
average=True
来开启平均功能。ASGD通过对一个样本每次进行SGD迭代的系数做平均。当使用ASGD时,learning_rate可以变得更大,从而在训练时对一些数据集进行加速。

对于使用logistic loss的分类,另一个使用平均策略的SGD变种是:随机平均梯度(SAG)算法。由LogisticRegression提供。

3.回归

SGDRegressor类实现了一个普通的随机梯度下降学习,它支持不同的loss函数和罚项来拟合线性回归模型。SGDRegressor对于大数据量训练集(》10000)的回归问题很合适。对于其它问题:我们推荐你使用Ridge, Lasso, or ElasticNet。

loss函数可以通过loss参数进行设置。SGDRegressor支持以下的loss函数:

  • loss=”squared_loss”: 普通最小二乘法
  • loss=”huber”: 对于稳健回归(robust regression)的Huber loss
  • loss=”epsilon_insensitive”: 线性SVM

Huber 和 epsilon-insensitive loss函数可以用于稳健回归(robust regression)。敏感区的宽度可以通过参数epsilon来指定。该参数依赖于target变量的规模。

SGDRegressor和SGDClassifier一样支持ASGD。通过设置

1
average=True
来开启。

对于使用最小二乘loss和l2罚项的回归来说,可以使用SGD的另一个变种SAG算法,由Ridge的solver提供。

4.稀疏数据的SGD

注意:稀疏实现与dense实现相比会产生不同结果,由于在intercept的learning rate上有shrink。

稀疏矩阵由scipy.sparse支持。出于最大化的效率,使用CSR矩阵格式可以由scipy.sparse.csr_matrix定义。

示例:

5.复杂度

SGD的主要优点在于它的高效,它与训练样本数成线性关系。如果X是一个size(n,p)的训练矩阵,具有一个cost为,其中k为迭代数(epochs),而是每个样本的非零属性平均数。

最近的理论结果表明,优化正确率问题的runtime并不会随着训练样本大小的增加而增加。

6.实用tips

  • SGD对于特征归一化(feature scaling)很敏感,因此强烈推荐你对数据进行归一化。例如,将输入向量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

如果你的属性项本身就做了归一化(例如:词频、或者指示器feature),那就不需要再做归一化了。

  • 可以通过GridSearchCV找到一个合适的正则项,通常范围在:10.0**-np.arange(1,7)。
  • 经验上,我们发现SGD在接近10^6的训练样本时进行收敛。因此,第一步合理的猜想是,将迭代数设置成:n_iter = np.ceil(10**6 / n),其中n是训练集的size。
  • 如果你在使用PCA提取的feature上使用SGD,我们发现,对于feature值进行归一化是明智的,通过一些常数c,以便训练数据的平均L2范式等于1。
  • 我们发现ASGD在当feature很大和eta0很大时运转很好。

参考:

7.数学公式

给定训练集:

且满足

我们的目标是学到一个线性scoring函数:

它的模型参数为:

intercept为:

为了进行预测,我们还需要看一个f(x)的符号。一个通用的选择是,通过最小化正则化的训练误差来得到最优模型参数:

其中L是loss函数,计算模型是否拟合,R是正则项(aka penalty),用于惩罚模型复杂度;是一个非负的超参数。

对于不同分类器,L有不同选择,比如:

  • Hinge: (soft-margin)SVM
  • Log: Logistic回归
  • Least-Squares: Ridge回归
  • Epsilon-Insensitive: (soft-margin)SVM

上面所有的loss函数可以被认为是误分类的上边界(0-1 loss),如图如下:

正则项R有如下的选择:

  • L2范数:
  • L1范数:,会导致稀疏。
  • Elastic Net: ,它是L2和L1的convex组合,其中通过1 - l1_ratio给出。

下图展示了当在参数空间内不同的正则项的轮廓。

7.1 SGD

随机梯度下降(Stochastic gradient descent)是一个优化方法,用于非限制性优化问题。与它对应的是批梯度下降(batch gradient descent),SGD逼近E(w,b)的真实梯度,它在一次迭代时只考虑一个训练样本。

SGDClassifier实现了一阶的SGD学习。该算法在训练集上进行迭代,对于每个样本,根据下面的更新规则更新模型参数:

其中,是学习率,它控制着参数空间的步长。截距(intercept)b的更新相类似,但没有正则项。

学习率即可以是常数,也可以逐渐衰减。对于分类,缺省的学习率(learning_rate=’optimal’),通过下式给定:

其中,t是时间步长(总共有:n_samples * n_iter的时间步长),则基于Léon Bottou提出的启发式学习,以便期望的初始更新与期望的权值size是可以相比较的。可以在BaseSGD的_init_t中找到精确定义。

对于回归,缺省的学习率schedule是inverse scaling(learning_rate=’invscaling’),通过:

其中,这两个超参数由用户通过参数eta0 和 power_t来控制。

对于一个常数值的学习率来说,可以使用learning_rate=’constant’ ,并使用eta0来指定学习率。

该模型的参数可以通过属性coef_和intercept_来访问:

  • coef_: 权重w
  • intercept_: 参数b

8.实现细节

SGD的实现受Léon Bottou提出的Stochastic Gradient SVM的影响。与SvmSGD相类型,weight向量被表示成一个标量(scalar)和一个向量(vector)的乘积,它允许L2正则化进行更新。对于稀疏特征向量的情况,截距(intercept)的更新使用一个更小的学习率(乘以0.01)来说明事实上更新更频繁。训练样本按顺序被选择,在每一个被观察到的示例后学习率会变慢。

我们采用的学习率schedule是:Shalev-Shwartz et al. 2007提出的。对于多分类,使用”one-versus-all“方法。我们使用由Tsuruoka et al. 2009提出的截断梯度(truncated gradient)算法进行L1正则化(和Elastic Net)。代码使用cython编写。

参考:

参考:

1.http://scikit-learn.org/stable/modules/sgd.html