Re: [問題] 請教關於Stochastic gradient descent
幾個想法提供參考
(1) "好"的比較
training error小？ generalization ability強？
收斂速度快？ 運算時間少？
(2) GD 和 SGD之間的關係
在 machine learning 中
gradient descent 或者說 Batch gradient descent
通常針對 full training set 的 Empirical Risk 進行
也就是 objective function : L(w,x) = 1/N \sum^{N}_{i=1} loss(w;x_i)
Stochstic gradient descent 則是隨機針對前式的 loss 進行
理論上能達到對 Expected Risk 進行最佳化的結果
介於之間的 mini-batch 則是對 L'(w,x) = 1/n \sum^{n}_{i=1} loss(w;x_i)
n 即是代表 mini-batch size的大小
相對於single data 的 gradient
mini-batch 的 gradient方向，與 Batch gradient 的方向會更近
因此，最佳化的過程中，相對會更穩定
(3) 比較
GD SGD
收斂性 ： linear~suplinear sublienar ~linear
per-iter. ： dependent N independent N
cost
Convex ： 收斂到opt. 會因learning rate
problems 有gap
Non-convex： 收斂到 實作有機會收斂到
problems stationary point global minimum
(4) 回答(1)
a.Training error的表現:
基本上GD直接針對Empirical risk最佳化
只要是convex problems通常會比較好
b.Generalization ability:
不一定，當N夠大或者說足夠代表母體時，GD仍可能比較好
反之，SGD理論上針對Expected risk最佳化
所以在N不夠代表母體時，比較能夠避免bias
c.收斂速度:
GD 勝
d.計算時間:(收斂速度 * per-iter.cost)
small data -> GD
large-scale dat -> SGD
至於怎麼定義大小，通常取決於硬體設備而非絕對
(5) 結尾
Stochastic approximation方法在1951年就被提出
而近年來為了解決資料量成長速度遠快於硬體的運算速度
因此，除了分散式處理方法外，使用stochastic方案最為熱門
然而SGD的收斂上的不穩定性是問題之一
針對Batch size 大小的取捨上並沒有太絕對的結論
https://arxiv.org/abs/1711.00489
這篇提出隨著update調整batch size大小
https://arxiv.org/abs/1609.04836
這篇提出過大的batch size大小導致 generalization ability 差
當然兩者並不互相矛盾也可以同時成立
仍是大家正在研究的議題之一
最後，影響著SGD training 幾個可能的因素
(1) sampling (2) mini-batch size (3) learning rate
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.25.44
※ 文章網址: https://www.ptt.cc/bbs/DataScience/M.1522794628.A.083.html
※ 編輯: championship (140.113.25.44), 04/04/2018 06:59:36
推
04/04 13:19,
6年前
, 1F
04/04 13:19, 1F
→
04/05 07:08,
6年前
, 2F
04/05 07:08, 2F
→
04/05 07:09,
6年前
, 3F
04/05 07:09, 3F
推
04/05 07:20,
6年前
, 4F
04/05 07:20, 4F
(1) 前兩個問題就是關於accuracy，training error 和 generalization ability
後者通常用 testing error 去代表好壞。
(2) 至於時間和收斂速度的兩個問題，則是與SGD的發展原因和其問題有關，所以想說順便
提出來討論。
(3) 打散資料的行為其實就是 sampling 的部份，簡單的方法大致上有兩種：
a. 每個epoch把整筆資料 random shuffle b. 取後放回的方式
更高階一點的方法，就是在training 過程中同時學習資料的distribution，並且以此
做sample的策略，一般這種方法比較常在online learning中使用，關鍵字可以搜尋
muti-armed bandit
※ 編輯: championship (36.232.55.11), 04/05/2018 09:05:59
推
04/05 09:53,
6年前
, 5F
04/05 09:53, 5F
→
04/05 09:53,
6年前
, 6F
04/05 09:53, 6F
→
04/05 09:53,
6年前
, 7F
04/05 09:53, 7F
SGD 狹義來說是指 mini-batch = 1 時的情況，不過 stochastic update 不僅限於此
且性質上與mini-batch gradient descent 大致類似，故共同討論之。
而 mini-batch size 調整上，會影響幾件事情：
(1) 每個 epoch 中 update 的次數
(2) 單次 update 的計算時間
(3) stochastic gradient 方向 與當下的 batch gradient 方向的差異
推
04/05 10:02,
6年前
, 8F
04/05 10:02, 8F
推
04/05 10:10,
6年前
, 9F
04/05 10:10, 9F
※ 編輯: championship (36.232.55.11), 04/05/2018 11:02:12
推
04/05 13:35,
6年前
, 10F
04/05 13:35, 10F
推
04/05 22:00,
6年前
, 11F
04/05 22:00, 11F
→
04/06 16:47,
6年前
, 12F
04/06 16:47, 12F
→
04/06 16:48,
6年前
, 13F
04/06 16:48, 13F
推
04/07 16:36,
6年前
, 14F
04/07 16:36, 14F
討論串 (同標題文章)