Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
確率的勾配法のはなし
Search
Yamaguchi Takahiro
April 17, 2019
Science
18
8.2k
確率的勾配法のはなし
プレーンなSGDから最近のアルゴリズム(Adabound)までの流れをまとめています。
Yamaguchi Takahiro
April 17, 2019
Tweet
Share
More Decks by Yamaguchi Takahiro
See All by Yamaguchi Takahiro
コンペを気楽に開催しよーぜ!@関西Kaggler会
nyk510
0
1.2k
Django のセキュリティリリースを見る
nyk510
0
72
3分でMLアプリを作る 〜推論コードにちょっとのStreamlitを添えて〜
nyk510
1
1.1k
硬派で真面目なグラフを描く
nyk510
0
490
CORSをちゃんと理解する atmaバックエンド勉強会#4
nyk510
0
380
pythonで気軽にパッケージを作るのは良いという話。
nyk510
14
9.5k
RestAPIのページネーション atma バックエンド勉強会 #3
nyk510
1
910
AWS CPU Credit を完全に理解する
nyk510
0
440
atmaCup#8 Opening
nyk510
0
240
Other Decks in Science
See All in Science
ICRA2024 速報
rpc
3
6.2k
サイゼミ用因果推論
lw
1
5.3k
WCS-LA-2024
lcolladotor
0
200
04_石井クンツ昌子_お茶の水女子大学理事_副学長_D_I社会実現へ向けて.pdf
sip3ristex
0
260
All-in-One Bioinformatics Platform Realized with Snowflake ~ From In Silico Drug Discovery, Disease Variant Analysis, to Single-Cell RNA-seq
ktatsuya
0
330
非同期コミュニケーションの構造 -チャットツールを用いた組織における情報の流れの設計について-
koisono
0
230
論文紹介: PEFA: Parameter-Free Adapters for Large-scale Embedding-based Retrieval Models (WSDM 2024)
ynakano
0
230
事業会社における 機械学習・推薦システム技術の活用事例と必要な能力 / ml-recsys-in-layerx-wantedly-2024
yuya4
4
320
Factorized Diffusion: Perceptual Illusions by Noise Decomposition
tomoaki0705
0
360
Quelles valorisations des logiciels vers le monde socio-économique dans un contexte de Science Ouverte ?
bluehats
1
190
ガウス過程回帰とベイズ最適化
nearme_tech
PRO
1
250
化学におけるAI・シミュレーション活用のトレンドと 汎用原子レベルシミュレーター: Matlantisを使った素材開発
matlantis
0
530
Featured
See All Featured
GitHub's CSS Performance
jonrohan
1030
460k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
30
1.1k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
135
33k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
16
1.1k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
160
15k
Bash Introduction
62gerente
611
210k
Gamification - CAS2011
davidbonilla
81
5.2k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
47
5.3k
Facilitating Awesome Meetings
lara
53
6.3k
GraphQLの誤解/rethinking-graphql
sonatard
70
10k
Making Projects Easy
brettharned
116
6.1k
StorybookのUI Testing Handbookを読んだ
zakiyama
28
5.6k
Transcript
確率的勾配法のはなし 2019/04/17 Kaggle もくもくかい @nyker_goto
じこしょうかい @nyker_goto (twitter) 京都大学院, 最適化数理 (修論は確率的勾配法関連) 零細ベンチャー Atmaでデータサイエンティスト (新卒二年目) 人大募集中です!!!
今日は確率的勾配法の歴史と最近の論文 Adabound を ざっくり紹介します 2
はじめにおことわり このスライドの数式は若干適当です 3
なんで適当か • 数式追いかけてもあんまりおもしろくない ◦ 正直あまり本質的でもなかったり(変形すればいいだけなので ◦ なので収束性とかの込み入った話はしないです • SGD の「ノリ」をちょっとでも知ってほしいという気持です
◦ SGD は楽しいのです 以上のねらいのため, 出来る限り一般化を避けた表記に変えています。 そのため論文の数式よりも具体的になっていて表記が若干違います。 4
早速ですが Deep の optimizer って 何使ってますか !? 5
Optimizer なにつかってますか !? • SGD ◦ Nesterov の加速法 ◦ Momentum
• Adagrad • RMSProp • Adadelta • Adam • Adabound (NEW!) … 僕は SGD + Nesterov + Momentum (0.8) とかが好きです 6 図1. 勝手にとってきた Nesterov 先生
しんぷるなSGD t ステップ目で全体のうちひとつのデータの勾配 g を使って更新。たんじゅん。 Gradient Descent (最急降下法) だと全データ N
使うのがちがうとこ SGD (Stochastic Gradient Descent ちなみに: Gradient Descent 7
ちょっと一般化 今後の議論のため天下り的にちょっと一般化します。 SGD は毎回勾配(やそれに似た方向) m に対してあるステップサイズと補正ベクトル Vt をかけたような動きをすりゃいいので… と表せます。これを基本形と呼ぶことにします (V
と m はアダマール積) 8
SGD再掲 この基本形で SGD を書き直すと以下のような感じ。 基本形 SGD 9 • SGD は学習率をいじると収束が早いことが実験的に知られている
◦ 最初大きくあとで小さくとかがポピュラー • できれば人がいじらずに勝手に良い学習率で更新してほしい
適合的 (adaptive) なアルゴリズム • Adagrad (2010) • ADAM (2015) •
Adabound (2019) 10
Q. 適合的 (adaptive) って何? 11
A. いい感じに学習率(や勾配)を 変えてくれるような方法のこと 12
Adagrad (2010) Adaptive Subgradient Methods for Online Learning and Stochastic
Optimization (2010) 発想 • 学習率がすべての要素で同じなのは不自然なのでは? ◦ 毎回大きな勾配を持っているような要素ではあまり大きな学習率をとりたくない ◦ 反対にほとんど毎回ゼロの勾配を持つものはたまに勾配があるとき大きく更新し たい • 要素ごとにいい感じの学習率で更新させたい 13
Adagrad (2010) うごく方向 m は SGD と同じ SGD のときとの 差分は
Vt にあり 過去の勾配の二乗を足したもの平均値で割り算 • 過去に大きな勾配を持っている要素はステップ サイズが小さくなる。 • 要素ごとにいい感じの lr を選べる。 基本形 Adagrad 14 [note] 実は Vt は BFGS などの準ニュートン法的な発想で導入 されていたりします
Adagrad の問題点 • よーく V を見ると過去の値すべての平均をとっ ている • 一度とても大きい勾配に遭遇すると再度 V
が 小さくなる (= lr が大きくなる)ことはなかなか無 い ◦ Deep のような非凸関数だと局所解に捕 まったりする。そのときは step size を大 きくして抜けだしたい。けどできない。 基本形 Adagrad 15
みんなだいすき ADAM 先生 (2015) 16 発想 • V の計算を指数で重み付けするので最近の勾 配が小さいと大きい
lr を取れる • 勾配も過去の情報も使うようにしたらいいん じゃない? (Momentum的な発想) • 単に足して平均取るんじゃなくてついでに期待 値でも一致するよう 1- β を掛け算しとくといい のでは?
ADAM の問題点 • 実は どんな lr をとったとしても, 凸な問題で収束しないような場合があります(SGD だと収束します)。 ◦
ニューラルネットワークは非凸関数なので直接的には影響しませんが 解のごく近傍では凸に近似できるのでちょっと気持ちがわるい ◦ Adabound 論文中では学習が進んだ終盤で SGD にくらべ adam の性能が わるくなるのはこのためではないか? と指摘されています 要するに最初は adam 的な更新が良いけれど学習終盤(解近傍)の挙動は微妙 むしろ適合的でない SGD のほうが理論的にも良い (余計なことしないほうが良い) 17
じゃあ ADAM から SGD にかわるようなアルゴリズムに すればよくない? 18
Adabound (NEW! 2019) • V, m (補正項と方向) は adam と一緒
• 違うのは学習率を Clip しているとこ ◦ 最大最小を決めることで極端な学習率に ならなくなる ◦ 最大最小を特定の値に収束させるような 関数を使えば学習終盤でスムーズに SGD に置きかわる (左の例なら lr=0.1 の SGD ) 最大最小の一例@論文中 19
数値実験 • DenseNet121 で CIFAR-10 • 強いよね。序盤、中盤、終盤、隙がない。 (終盤で SGD Momentum
に追いつかれているものの序盤は圧倒的) 20
まとめ • 適合的な手法の発想はどれも似ている。割とシンプル。 • Adabound は SGD と Adam のいいとこ取り。これから流行りそう
21
参考文献 • Duchi, John and Hazan, Elad and Singer, Yoram
/ Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. https://dl.acm.org/citation.cfm?id=2021068 adagrad の論文。結構最適化よりなのでむずい。 • Sebastian Ruder. An overview of gradient descent optimization algorithms. https://arxiv.org/abs/1609.04747 勾配法とか確率的勾配法のサーベイ。わかりよい。 • Liangchen Luo, Yuanhao Xiong, Yan Liu, Xu Sun. Adaptive Gradient Methods with Dynamic Bound of Learning Rate. https://openreview.net/forum?id=Bkg3g2R9FX adabound 論文 22