scikit-learn 隨機(jī)梯度下降

隨機(jī)梯度下降(SGD)是一種在凸損失函數(shù)(如(線性)支持向量機(jī)和Logistic回歸)下擬合線性分類器和回歸器的簡單而有效的方法。盡管SGD在機(jī)器學(xué)習(xí)社區(qū)中已經(jīng)存在了很長一段時(shí)間，但就在最近大規(guī)模學(xué)習(xí)的背景下，它得到了相當(dāng)多的關(guān)注。

SGD已成功地應(yīng)用于文本分類和自然語言處理中經(jīng)常遇到的大規(guī)模和稀疏的機(jī)器學(xué)習(xí)問題。由于數(shù)據(jù)稀疏，本模塊中的分類器很容易處理到具有個(gè)訓(xùn)練樣本和個(gè)特征以上的問題。

嚴(yán)格地說，SGD只是一種優(yōu)化技術(shù)，并不與特定的機(jī)器學(xué)習(xí)模型相對(duì)應(yīng)。它只是訓(xùn)練模型的一種方式。通常，scikit-learn API中SGDClassifier或SGDRegressor 具有等效的估計(jì)，只是可能使用了不同的優(yōu)化技巧。例如，使用SGDClassifier(loss='log')將導(dǎo)致Logistic回歸， 即一個(gè)等價(jià)于LogisticRegression的模型可以通過SGD擬合而不是LogisticRegression中其他的優(yōu)化方案。類似的。SGDRegressor(loss='squared_loss', penalty='l2')和 Ridge就是通過不同的方法解決了相同的優(yōu)化問題。

隨機(jī)梯度下降的優(yōu)點(diǎn)是：

• 高效
• 易于實(shí)現(xiàn) (有大量優(yōu)化代碼的機(jī)會(huì))

隨機(jī)梯度下降的缺點(diǎn)包括：

• SGD需要一些超參數(shù)，例如正則化參數(shù)和迭代次數(shù)
• SGD對(duì)特征縮放非常敏感

警告：

在擬合模型之前，一定要重新排序(打亂的)訓(xùn)練數(shù)據(jù)，或者在每次迭代后(默認(rèn)情況下使用)使用shuffle=True來打亂數(shù)據(jù)。此外，理想情況下，應(yīng)該使用make_pipeline(StandardScaler(), SGDClassifier())(參見 Pipelines)對(duì)特征進(jìn)行標(biāo)準(zhǔn)化。

1.5.1 分類

SGDClassifier 分類器實(shí)現(xiàn)了一個(gè)簡單的隨機(jī)梯度下降學(xué)習(xí)程序，支持不同的損失函數(shù)和懲罰項(xiàng)。下面是用合頁損失(hinge loss)訓(xùn)練的SGDClassifier分類器的決策邊界，相當(dāng)于線性支持向量機(jī)。

作為其他分類器，SGD必須fit兩個(gè)數(shù)組：一個(gè)包含訓(xùn)練樣本的形狀(n_samples, n_features) 的X和一個(gè)包含訓(xùn)練樣本目標(biāo)值(類標(biāo)簽)的形狀 (n_samples)的數(shù)組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)

經(jīng)擬合后，該模型可用于預(yù)測新的值：

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

SGD擬合訓(xùn)練數(shù)據(jù)的線性模型。coef_屬性保存了模型參數(shù)：

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

intercept_保存了截距項(xiàng)(又被稱為 偏移(offset)或者偏差(bias))

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

模型是否使用截距項(xiàng)，即有偏的超平面(a biased hyperplane)，是由參數(shù)fit_intercept控制的。

到超平面的符號(hào)距離(計(jì)算為系數(shù)和輸入樣本之間的點(diǎn)積，加上截距)可由 SGDClassifier.decision_function:

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

可以通過loss參數(shù)設(shè)置具體的損失函數(shù)。SGDClassifier 分類器支持以下?lián)p失函數(shù)：

• loss="hinge":(軟-間隔)線性支持向量機(jī)
• loss="modified_huber:平滑的合頁損耗(smoothed hinge loss)
• loss="log":邏輯回歸
• 以及以下所有的回歸損失。在這種情況下，目標(biāo)被編碼為-1或1，并且這個(gè)問題被看作是一個(gè)回歸問題。然后，預(yù)測的類對(duì)應(yīng)于預(yù)測目標(biāo)的符號(hào)。

請(qǐng)參閱下面的數(shù)學(xué)部分的公式。前兩個(gè)損失函數(shù)是懶惰的，它們只在一個(gè)樣本違反邊際約束的情況下更新模型參數(shù)，這使得訓(xùn)練非常有效，并且也可能導(dǎo)致稀疏模型(即更多的零系數(shù))， 即使使用的是L2懲罰。

使用loss="log" 或者 loss="modified_huber" 來激活 predict_proba 方法,這會(huì)給每個(gè)樣本一個(gè)概率估計(jì)的向量。

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

具體的懲罰項(xiàng)可以通過penalty參數(shù)來設(shè)定。SGD支持以下懲罰項(xiàng)：

• penalty="l2": L2 范數(shù)懲罰 在 coef_
• penalty="l1": L1 范數(shù)懲罰 在 coef_
• penalty="elasticnet": L1和L2的凸組合; (1 - l1_ratio) * L2 + l1_ratio * L1

默認(rèn)設(shè)置為 penalty="l2"。L1懲罰會(huì)導(dǎo)致稀疏解，使大部分系數(shù)變?yōu)榱?。彈性網(wǎng)[11]在具有高度相關(guān)屬性的情況下，解決了L1懲罰的一些不足。參數(shù)l1_ratio控制L1和L2懲罰的凸組合。

SGDClassifier分類器通過使用“one versus all” (OVA)方案組合多個(gè)二分類器來支持多分類。對(duì)于每個(gè)類，學(xué)習(xí)了一個(gè)二分類器，該分類器區(qū)分該類和所有其他類。在測試時(shí)，我們計(jì)算每個(gè)分類器的置信分?jǐn)?shù)(即到超平面的符號(hào)距離)，并選擇置信度分?jǐn)?shù)最高的類。下圖說明了在 iris數(shù)據(jù)集的OVA方法。虛線表示三個(gè)OVA分類器，背景顏色表示由三個(gè)分類器決定的的決策面。

在多分類的情況下，coef_是一個(gè)形狀是 (n_classes, n_features)的二維數(shù)組，而intercept_是一個(gè)形狀是(n_classes,)的一維數(shù)組。coef_的第i行是第i類的OVA分類器的權(quán)重向量；類按升序進(jìn)行索引(請(qǐng)參見class_)。請(qǐng)注意，原則上，由于它們?cè)试S創(chuàng)建概率模型，所以loss="log" 和 loss="modified_huber"更適合于 one-vs-all分類。

SGDClassifier 分類器可以通過fit方法的參數(shù)class_weight和sample_weight來支持對(duì)類加權(quán)和對(duì)實(shí)例加權(quán)。有關(guān)更多信息，請(qǐng)參見下面的示例和SGDClassifier.fit的說明文檔。

SGDClassifier支持平均最近梯度下降(averaged SGD (ASGD))[10]。通過設(shè)置 average=True來啟用。ASGD與常規(guī)的SGD表現(xiàn)出相同的更新(參見數(shù)學(xué)公式)，但不使用系數(shù)的最后一個(gè)值作為coef_(即上次更新的值)，相反，coef_被設(shè)置為所有更新中系數(shù)的平均值。

對(duì)于具有邏輯損失的分類，另一種采用平均策略的SGD方法是用隨機(jī)平均梯度(SAG)算法進(jìn)行的，它可以作為 LogisticRegression中的求解器。

1.5.2 回歸

SGDRegressor類實(shí)現(xiàn)了一個(gè)簡單的隨機(jī)梯度下降學(xué)習(xí)程序，它支持不同的損失函數(shù)和懲罰來擬合線性回歸模型。 SGDRegressor非常適合于具有大量訓(xùn)練樣本(>10.000)的回歸問題，對(duì)于其他問題，我們建議使用 Ridge, Lasso, 或者 ElasticNet。

具體的損失函數(shù)可以通過 loss 參數(shù)設(shè)置。 SGDRegressor 支持以下的損失函數(shù):

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

有關(guān)公式，請(qǐng)參閱下面的數(shù)學(xué)部分。Huber和epsilon—insensitive損失函數(shù)可用于魯棒回歸。不敏感區(qū)域的寬度必須通過參數(shù) epsilon 來設(shè)定。這個(gè)參數(shù)取決于目標(biāo)變量的規(guī)模。

penalty參數(shù)確定要使用的正則化(請(qǐng)參閱分類部分中的說明)。

SGDRegressor還支持平均SGD [10] (同樣，請(qǐng)參閱分類部分中的說明)。

對(duì)于具有平方損失和L2懲罰的回歸，另一種具有平均策略的SGD算法可用隨機(jī)平均梯度(SAG)算法作為嶺中的求解器, 就像 Ridge回歸的解法。

1.5.3 稀疏數(shù)據(jù)的隨機(jī)梯度下降

注意：稀疏實(shí)現(xiàn)會(huì)產(chǎn)生與密集實(shí)現(xiàn)略有不同的結(jié)果，這是因?yàn)閷W(xué)習(xí)速率縮小了。請(qǐng)參閱實(shí)施細(xì)節(jié)。

在 scipy.sparse 支持的格式中，任意矩陣都有對(duì)稀疏數(shù)據(jù)的內(nèi)置支持方法。但是，為了獲得最高的效率，請(qǐng)使用 scipy.sparse.csr_matrix 中定義的 CSR 矩陣格式。

1.5.4 復(fù)雜度

SGD的主要優(yōu)點(diǎn)是它的效率，這在訓(xùn)練數(shù)據(jù)上基本都是線性的。假如 X 是形狀為 的矩陣，則訓(xùn)練的成本為, 其中 是迭代次數(shù)， 是每個(gè)樣本非零特征的平均數(shù)。

然而，最近的理論結(jié)果表明，隨著訓(xùn)練集大小的增加，運(yùn)行時(shí)得到一些期望的優(yōu)化精度并沒有提高。

1.5.5 停止準(zhǔn)則

當(dāng)達(dá)到給定的收斂水平時(shí)， SGDClassifier和 SGDRegressor提供了兩個(gè)停止該算法的準(zhǔn)則：

• 使用早期early_stopping=True，輸入數(shù)據(jù)被分割成一個(gè)訓(xùn)練集和一個(gè)驗(yàn)證集。然后在訓(xùn)練集上對(duì)模型進(jìn)行擬合，并根據(jù)在驗(yàn)證集上計(jì)算的預(yù)測分?jǐn)?shù)(使用分?jǐn)?shù)法)確定停止準(zhǔn)則。驗(yàn)證集的大小可以隨參數(shù)validation_fraction而改變。
• 在early_stopping=False的情況下，模型對(duì)整個(gè)輸入數(shù)據(jù)進(jìn)行擬合，根據(jù)目標(biāo)函數(shù)在訓(xùn)練數(shù)據(jù)計(jì)算確定停止準(zhǔn)則。

在這兩種情況下，準(zhǔn)則都是按歷次計(jì)算一次的，當(dāng)該準(zhǔn)則不改進(jìn)n_iter_no_change時(shí)，該算法就停止了。用絕對(duì)公差法進(jìn)行了評(píng)價(jià)改進(jìn)或者算法在最大迭代次數(shù)(max_iter)后，這兩種任意一個(gè)情況下算法都會(huì)停止。

1.5.6 實(shí)用技巧

• 隨機(jī)梯度下降對(duì)特征縮放非常敏感，因此強(qiáng)烈建議對(duì)數(shù)據(jù)進(jìn)行縮放。例如，將輸入向量X上的每個(gè)特征縮放為[0，1]或[-1，+1]，或?qū)⑵錁?biāo)準(zhǔn)化為均值為0和方差為1。注意，相同的縮放必須應(yīng)用于測試向量以獲得有意義的結(jié)果。使用StandardScaler可以很容易地做到這一點(diǎn)：

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)

如果您的屬性具有固有的尺度(例如，單詞頻率或指示特征)，則不需要縮放。

• 找到一個(gè)合理的正則化項(xiàng)最好是使用自動(dòng)超參數(shù)搜索，比如 GridSearchCV或者RandomizedSearchCV， 通常的范圍是10.0**-np.arange(1,7)

• 根據(jù)經(jīng)驗(yàn)，我們發(fā)現(xiàn)SGD在觀察了大約10^6個(gè)訓(xùn)練樣本后收斂。因此，對(duì)迭代次數(shù)的合理猜測是max_iter = np.ceil(10**6 / n)，其中是訓(xùn)練集的大小。

• 如果將SGD應(yīng)用于PCA提取的特征，我們發(fā)現(xiàn)，通常明智的做法是將特征值通過某個(gè)常數(shù)c縮放，使訓(xùn)練數(shù)據(jù)的L2范數(shù)平均值等于1。

• 我們發(fā)現(xiàn)，當(dāng)特征很多或 eta0 很大時(shí)， ASGD（平均隨機(jī)梯度下降） 效果更好。

參考

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

1.5.7 數(shù)學(xué)公式

我們?cè)谶@里描述SGD的數(shù)學(xué)細(xì)節(jié)。一個(gè)很好的概述和收斂速度可以在[12]中找到。

給定一組訓(xùn)練集樣本, 其中, 分類問題， 我們的目的是得到線性的得分函數(shù), 其中參數(shù), 并且。為了進(jìn)行二分類預(yù)測，我們簡單看一下。為了找到模型參數(shù)，我們將正則化訓(xùn)練誤差降到最小:

其中是度量模型(mis)擬合的損失函數(shù)，是懲罰模型復(fù)雜度的正則化項(xiàng)，是控制正則化強(qiáng)度的非負(fù)超參數(shù)。

對(duì)于不同的 選擇不同的分類器和回歸器：

• Hinge (軟間隔)：等價(jià)于支持向量分類器

• Perceptron:

• Modified Huber:

• Log: 等價(jià)于邏輯回歸：

• Least-Squares:線性回歸((Ridge 還是 Lasso 取決于 ) 。

• Huber: 與最小二乘相比，對(duì)離群值不太敏感。當(dāng), 并且, 等價(jià)于最小二乘。

• Epsilon-Insensitive:(軟間隔)等價(jià)于支持向量回歸。

如下圖所示，上述所有損失函數(shù)都可視為錯(cuò)誤分類錯(cuò)誤(0一1 損失)的上限。

比較流行的正則化（penalty 參數(shù)）的選擇如下：

• L2 范數(shù):
• L1 范數(shù): 這會(huì)導(dǎo)致稀疏的解
• Elastic Net:, L2和L1的凸組合，其中是通過1 - l1_ratio指定的。

下圖顯示了當(dāng)=1時(shí)，不同正則化項(xiàng)在二維參數(shù)空間(=2)中的輪廓。

1.5.7.1 SGD

隨機(jī)梯度下降是求解無約束優(yōu)化問題的一種優(yōu)化方法。與(批量)梯度下降相比，SGD通過一次只考慮一個(gè)訓(xùn)練樣本來逼近的真實(shí)梯度。

SGDClassifier類實(shí)現(xiàn)了一階SGD學(xué)習(xí)程序。該算法對(duì)訓(xùn)練樣本進(jìn)行迭代，并對(duì)每個(gè)樣本根據(jù)給出的更新規(guī)則更新模型參數(shù)。

其中 是控制參數(shù)空間中學(xué)習(xí)速率的步長。截距b 類似地被更新，但沒有正則化(并且對(duì)稀疏矩陣有額外的衰減，詳見實(shí)現(xiàn)細(xì)節(jié))。

的學(xué)習(xí)速率可以是恒定的，也可以是逐漸衰減的。對(duì)于分類，默認(rèn)的學(xué)習(xí)率通過(learning_rate='optimal')由下式給出。

其中是時(shí)間步長(總共有n_samples * n_iter個(gè)時(shí)間步長)，是基于Léon Bottou提出的啟發(fā)式算法確定的，這樣期望的初始更新與權(quán)重的預(yù)期大小相當(dāng)(假設(shè)訓(xùn)練樣本的范數(shù)接近1)。確切的定義可以在BaseSGD中的的_init_t中找到。

對(duì)于回歸，默認(rèn)的學(xué)習(xí)率計(jì)劃是反向縮放(learning_rate='invscaling')，由下式給出:

其中和是用戶通過 eta0 和power_t指定的超參數(shù)。

對(duì)于固定的學(xué)習(xí)速率設(shè)置，可以使用learning_rate='constant'，并且通過指定學(xué)習(xí)率。

對(duì)于自適應(yīng)下降的學(xué)習(xí)速率，使用learning_rate='adaptive' , 并使用 eta0指定最起始學(xué)習(xí)速率。當(dāng)達(dá)到停止條件時(shí)，學(xué)習(xí)速率除以5，算法不停止。當(dāng)學(xué)習(xí)速率低于1e-6時(shí)，算法停止。

模型參數(shù)可以通過coef_和intercept_來訪問：coef__持有權(quán)重w和intercept__含有b。

當(dāng)使用平均梯度下降(含有參數(shù)average)時(shí), coef_被設(shè)置為所有更新的平均權(quán)重：coef_=, 其中 是所有更新的總數(shù)，可以在屬性t_中找到。

1.5.8 實(shí)現(xiàn)細(xì)節(jié)

SGD 的實(shí)現(xiàn)受到[7]的隨機(jī)梯度支持向量機(jī)的影響。與SvmSGD類似，權(quán)重向量表示為標(biāo)量和向量的乘積，在L2正則化的情況下允許有效的權(quán)重更新。在輸入X稀疏的情況下，以較小的學(xué)習(xí)速率(乘以0.01)更新截距，以說明它被更新得更頻繁。在每個(gè)觀察到的示例之后，依次提取訓(xùn)練示例，并降低學(xué)習(xí)率。我們采用了[8]中的學(xué)習(xí)計(jì)劃。對(duì)于多分類的來說， 采用的是“one versus all”。對(duì)于L1正則化(和彈性網(wǎng))，我們使用了[9]中提出的截?cái)嗵荻人惴ā４a是用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.