機械学習プロフェッショナルシリーズ 確率的最適化 読書メモ

サマリー

機械学習での確率的最適化とは、ランダムなサンプルを用いた最適化問題の解法のことを指すものとなる。通常の最適化問題では、目的関数を最小化するために、全ての訓練データを使用して最適化する必要があるが、データセットが大規模である場合、これは非常に計算量が大きくなるため、確率的最適化を用いることで、ランダムに選択されたサブセット（ミニバッチ）のデータを使用して最適化を行い、計算量を大幅に削減することができる。また、ランダムに選択されたデータを使用するため、最適化の収束が速くなる場合もある。ここでは機械学習プロフェッショナルシリーズ「確率的最適化」ベースに様々な確率的最適化について述べる。

今回は読書メモについて述べる。

機械学習プロフェッショナルシリーズ 確率的最適化 読書メモ

機械学習プロフェッショナルシリーズ「確率的最適化」の紹介文より。「教師あり学習や凸解析の復習から、大量データ解析に有用な並列分散確率最適化まで丁寧に解説する。基本技法も新しいトピックも、きちんと理解できる1冊。式の成り立ち、アルゴリズムの意味がわかる。証明を極力略さず示す大規模計算実行までの本当の早道。」

第1章　教師あり学習と正則化

1.1 教師あり学習

はじめに
特徴抽出と学習

1.1.1 回帰

回帰の損失関数
続き
損失関数2


1.1.2 判別

f(x)が正なら1と判別し、負なら-1となるように 実数値函数を用いてそれの正負で判別することが一般的
2値判別の損失関数
損失関数2
0-1損失関数を使うのが妥当だが、 連続函数でも凸関数でもなく最適化がしにくい
0-1函数を近侍した「代理損失(surrogate loss)」を用いるのが一般的
上記の0-1関数以外

1.1.3 過学習

過学習の様子

1.2 正則化学習法

過学習避ける方法
正則化(regularization)
誤差関数をそのまま最小化するのではなく、 その「複雑さ」に応じた「罰則」を加えて最小化する
「複雑さ」はどのような構造をデータに想定しているかで決まる
正則化関数 (regularization function)
一般的な正則化学習法
λ>0は正則化の強さを調整する「正則化パラメータ(regularization parameter)」
第一項はデータの当てはまりを表す式
第二項はモデルの複雑さへの罰則
正則化関数の例
続き
各種正規化関数
線形モデルは単純だが、次元が高いと自由度高くなり過学習になる
L1正則化について
L1正則化は学習結果βをスパース(sparse)にさせやすいという性質を持つ
学習結果βが「スパースである」とは
βの「多くの成分が0である」ことを意味する
予測に必要のない無駄な特徴量を無視する
どのような意味で「必要」なのか?
汎化誤差を最小にする特徴量の選択
赤池情報量基準(Akaike information criterion, AIC)
正則化を用いた線形回帰手法

1.3 さまざまなスパース正則化

1.3.1 グループ正則化

Group Regularization
同じループに属する特徴量をまとめて1つの変数のように扱うスパース正則化
グループ正則化の式
∥βgk∥2は∥βgk∥rのように、1より大きいrに対するLrノルムとしても良い
グループ正則化は
グループの間でL1正則化をかけ、グループないではL2ノルムをかける形となっている
同じグループに属する変数はまとめて0になりやすい
さらに階層化して、グループのグループg'が与えられた時
階層的グループ正則化

1.3.2 一般化連結正則化

Generalized fused regularization
あるグラフに対して隣接した変数間は同じ値になるようにさせる正則化
一般化連結正則化の式

1.3.3 トレースノルム正則化

Trace norm regulization
低ランク行列を学習したい場合に現れる
トレースノルム正則化の式
特異値を並べたベクトルへのL1正則化
スパースな特異値を持つ行列、かなわち低ランクな行列が学習される
核ノルム(nuclear norm)とも呼ばれる
応用例
協調フィルタリング(collaborative filtering)
マルチタスク学習(multi-task learning)

1.3.4 正則化関数の組合せ

様々な正則化の組み合わせを考えられる
例:スパースかつ低ランクな行列の学習
L1正則化とトレースノルム正則化を同時に用いる
R(β) = ∥β∥1 + ∥β∥tr
正則化関数の組み合わせ方
和型
例
スパースかつ低ランクな行列
畳み込み型
例
スパースな行列と低ランクな行列の和
応用例
低ランクな行列の各成分にスパースなノイズが載っている時にそれを除去する
画像処理によくある
双対性が成り立つ

第2章　凸解析の基本事項

2.1 凸関数と凸集合

集合の凸性
凸集合
イメージ
凸関数
イメージ
エピグラフ
実効定義域
真凸関数、閉凸関数
狭義凸関数、強凸関数
強凸関数は凸関数の曲がり具合を想定
平滑凸関数
例
f(x)=x2は強凸かつ平滑
f(x)=log(1+exp(-x))は平滑だが強凸ではない
f(x)=|x|+x2は強凸だが平滑ではない

2.2 劣微分と双対関数

共役関数、ルジャンドル変換
共役関数は函数を傾きの情報から眺めたもの
f(x)-<x,y>は、点xでf(x)なる値をとる傾きyの直線のx=0での値
ルジャンドル変換
凸な関数y=f(x)は、(x,y)の集合によって表現できるが、 それらの傾きと切片の値で指定される接戦の集合によっても 等しく十分に表現できる
解析力学におけるラグラジアンのハミルトニアンへの変換で元いる
ルジャンドル変換の一般化として、ルジャンドル=フェンシェル変換がある
関数g(x)=f(x)-pxの最小値が定まる時のみ、ルジャンドル変換により新しい函数を与えられる
最小値が定まる場合でも、元となる関数が凸関数でない場合、あたらに定義された函数f*(p)は逆変換しても元に戻らない
補題
言葉の定義
凸包(convex hull)
集合C⊆ℝpの凸包はCを含む最小の凸集合
conv(C)
ある関数fに対し、 fのエピグラフの凸包(conv(epi(f)))を エピグラフとする凸関数を fの凸包と定義してconv(f)と書く
閉包(closure)
集合Cの閉包とは、集合Cを含む最小の閉集合
凸関数fの閉包を、 fのエピグラフの閉包(cl(epi(f)))を エピグラフとする閉凸関数と定義して、 cl(f)と書く
アフィン集合(Affine set)
集合Aがアフィン集合であるとは
Aに含まれる任意の2点x,yに対して、 λx+(1-λ)yが全てのλにおいてAに含まれるような集合
集合ないの任意の2点を通る直線がその集合からはみ出ない集合
線形空間の原点をずらした集合
アフィン包(Affine hull)
集合Cを含む最小のアフィン集合を、そのアフィン包とよぶ
相対的内点(relative interior)
凸集合Cのアフィン包をAとする
あるε>0が存在して、 {x'|∥x'-x∥≤ε}∩A⊆Cとなるような、 x∈Cの集合をCの相対的な移転といい、 ri(C)と書く
定理2.2.2
ある関数に対して、 ルジャンドル変換を2回実施した関数f**は、 元の関数fをしたから抑える最大の凸関数となる
系2.2.3
共役関数は真閉凸函数を 傾きの情報から眺めた「もう一つの姿」と言える
「傾き」の定義
劣微分(subdifferential)
劣微分の元を劣勾配 (subgradient)と呼ぶ
劣勾配は必ずしも存在すとは限らない
ri(dom(f))上では常に劣勾配が存在する (劣微分可能である)
劣微分の性質
ヤング・フェンシェルの不等式(Young-Fenchel's inequality)で統合が成り立つ時
xとyは劣微分で結ばれ、 かつ互いが互いのルジャンドル返還を与える
劣勾配
微分不可能な点での勾配を表現するため
Fを凸関数に限定した上で、その関数の各点での傾きをただ一つに限定せずに「複数の値」として表現
「複数の値」=集合として表現されるものが劣微分
その要素の一つが劣勾配
共役関数の性質
各種凸関数の共役関数
続き

2.3 フェンシェルの双対定理

フェンシェルの双対定理
Info{f(x)+g(Ax)}なる最適問題をときたい時、 これを主問題(primal problem)と呼ぶ
フェンシェルの双対定理から導かれる 等価な問題supy{-f*(ATy)-g*(-y)}を双対問題 (dual problem)と呼ぶ
問題によっては共役関数のほうが扱いやすく、 双対問題を解くほうが簡単な場合がある
アルゴリズムの途中で、 主問題と双対問題の途中解、 双方が求められている時
主問題と双対問題の差を求めるこで、 それらがどれだけ最適解に近いかの保証が得られる
主問題と双対問題の差を 双対ギャップ(duality gap)と呼ぶ
フェンシェル双対定理を用いた、 和と畳み込みの共役性について

2.4 近接写像

機械学習における確率的最適化では、 近接勾配に代表されるように 「近接写像(proximal mapping)」が重要な役割を果たす
近接写像について
fを真閉凸関数とする
近接写像proxfの定義
集合への投射の拡張
近接写像は微分できない凸関数に対して"写像"として一位に定義できる
勾配降下操作に代わる役割を果たす
近接写像の例
標示関数(indicator function)
モーロー分解(Moreau decomposition)

2.5 強凸関数と平滑凸関数の性質

強凸関数と平滑凸関数の片方もしくは両方が満たされていれば、 より高速に収束する最適化手法を構築できる

第3章　確率的最適化とは

学習に必要な最適化に 汎用の最適化ソルバーをそのまま当てはめると、 多くの時間がかかる
データを適切に分割し、 ランダムにその小さな部分問題を解いてゆき、 結果的にデータ全体を用いた最適化を解いてしまう
オンライン型確率的最適化(online stochastic optimization)
サンプルが逐次的に観測される場合に有用な手法
一回の更新にかかる計算量が非常に軽い
バッチ型確率的最適化(batch stochastic optimization)
全てのデータが手元にある状況を想定
一度利用したサンプルを再度用いることで、より早い収束が得られる
特徴量を分割する手法もある
機械学習の目的
汎化誤差を小さくする
汎化誤差が小さければ、 手元にあるデータにおける訓練誤差それ自体を 厳密に最適化させる必要はない
確率的最適化の歴史
1951年、統計学者のロビンスとモンロー
統計学における最尤推定を最適化問題とみなす
サンプルを観測するごとにパラメータを更新する
各種手法の分類

第4章　オンライン型確率的最適化

4.1 オンライン型確率的最適化の枠組み

サンプルを一つもしくは少数観察するごとにパラメータを更新する
時刻tで観測されるサンプルをzi∈Zとする(Zはサンプルの空間)
確率的最適化では、 ziはある確率分布Pから独立同一に 発生していると仮定する
Ztに対するパラメータβ∈ℝpの損失関数の値を ℓt(β)もしくはℓ(zt,β)とする
例:ℓt(β)=∥zt-βt∥2
教師あり学習の場合
入力(特徴ベクトル)とラベルの組zt=(xt,yt)
ℓt(β)=ℓ(yt,<xt,β>)とかける
<>　入力xtとβの内積
T時刻までサンプルを観察した後の訓練誤差最小化
正規化項を入れたもの
オンライン型確率的最適化の基本手順
正則化学習における確率的最適化は 上式の期待値を最小化することに対応
実用上は正則化の強さ(正則化パラメータ)を いくつか設定して学習を進め
T回目の更新が終わったら、 バリデーションデータで適切な正則かパラメータを選ぶ

4.2 オンライン学習と確率的最適化の関係

オンライン型学習
リグレット(regret)を、 逐次的にパラメータを更新していくことで、 最小化する
リグレットは
全てのサンプルを訓練した後に達成可能な固定パラメータによる最小の訓練誤差と、 逐次的に学習して行った際に被った累積的な訓練誤差との差
サンプルが確率変数であるとは仮定しない
応用例
広告戦略
広告の出し方によるその後の消費者の行動の変化
最小化したいのは広告をうつたびに被る損失の「累積」
T時刻目に得られている学習結果の汎化誤差ではない
「オンライン型確率的最適化」 と「オンライン学習」との違い
オンライン学習では、ztが独立同一の確率分布にしたが確率変数とは仮定しない
オンライン学習では、ztの挙動がコラの振る舞いに応じて変化する、オンライン確率的最適化では分布は変化しない
オンライン確率的最適化で最小化したいのは期待誤差でありリグレットではない

4.3 確率的勾配降下法(SGD)

4.3.1 確率的勾配降下法の枠組みとアルゴリズム

正則化項なしの確率的勾配降下法のアルゴリズム
gtは損失関数ℓtの劣勾配
劣微分の定義より上式が成り立つ
両辺をztに関して期待値をとると
gtの期待値は損失関数の期待値L(β)=Ezt[ℓt(β)]のβt-1での劣勾配になる
目的関数である期待損失L(β)の(劣)勾配を近似的に計算して、 その方向に少し動くことでβtを更新する
目的関数の勾配方向へ進むということは、 目的関数が最も傾斜している方向へ進むのと同等
勾配降下法(gradient descent)
最急降下法(steepest descent)
定義域Bの外にはみ出さないように、射影を施してBに引き戻す
射影勾配法(projected gradient descent)
正則項を含んだ確率的勾配降下法のアルゴリズム
確率的要素をなくし、gt∈∂L(βt-1)とできるならば
L𝛹を最小化する「近接勾配法(proximal gradient descent)」になる
確率的勾配法(SGD)と近接勾配法の収束の様子

4.3.2 確率的勾配降下法の収束レート

仮定
定理

4.3.3 確率的勾配降下法の収束レート(強凸)

仮定
定理

4.3.4 確率的勾配降下法の収束レートの証明(一般形)

定理

4.3.5 確率的鏡像降下法

ブレイグマンダイバージェンス
ブレイグマンダイバージェンス
ブレイグダイバージェンスの例
KLダイバージェンス
確率的胸像降下法アルゴリズム
鏡像降下法の更新
例

4.3.6 ネステロフの加速法の適用

4.4 確率的双対平均化法(SDA)

4.4.1 確率的双対平均化法のアルゴリズムと収束レート

アルゴリズム

4.4.2 強凸な正則化項における確率的双対平均化法

アルゴリズム

4.4.3 確率的双対平均化法の収束レートの証明(一般形)
4.4.4 確率的双対平均化法の鏡像降下法への拡張

アルゴリズム

4.5 AdaGrad

適応的に各座標ま更新幅を調整する方法
スパース正則化のオンライン学習において 出現頻度の低い特徴量がある場合、 その特徴量に対応する係数が 毎回スパース正則化で0に潰されてしまう
AdaGradによる対応
確率的勾配降下法および確率双対平均化法を少し修正したもの
修正点
AdaGradの更新式のアルゴリズム
凸損失の学習だけではなく、 深層学習の最適化にも使われる
目的関数の降下方向が局所的にほぼ平らな箇所に対応する
勾配の小さい方向を強調する性質を利用してプラトーから脱出
AdaGrad以外の深層学習〜のアプローチ
AdaDelta
RMSProp
文献38
定理
特徴量の出現頻度に差がある場合にも、 適応的に変数のスケーリングをしてより良い精度を得る

4.6 ミニマックス最適性

関数値と勾配を用いたどのような確率的最適化手法に対しても負けることはない
言葉の定義
一次確率的オラクル
リプシッツ連続な関数の集合
最適化アルゴリズムの集合
ミニマックス誤差

4.7 オンライン型確率的最適化の汎化誤差について

第5章　バッチ型確率的最適化

5.1 バッチ型確率的最適化の問題設定

訓練誤差を小さくすることを優先した最適化手法の構築
全てのサンプルを一回の更新で用いるのを避けるため
少数のサンプルをランダムに選択し、それのみを用いて1回の更新をする
目的関数に強凸性があれば更新回数に対して指数的な収束を達成するという利点がある
バッチ型確率的最適手法の特徴

5.2 確率的双対座標降下法

5.2.1 確率的双対座標降下法のアルゴリズム

双対問題を利用する方法
ある(真閉)凸関数fiを用いてℓi(β)=fi(xiTβ)とかける場合を想定
フェンシェルの双対定理を用いて上式のような双対問題を解く
座標降下法(coordinate descent)の技法が適用しやすい形となる
ブロック座標降下法(block coordinate descent)
SDCA(確率的双対座標降下法)のアルゴリズム

5.2.2 確率的双対座標降下法の収束証明

5.3 確率的分散縮小勾配降下法

5.3.1 確率的分散縮小勾配降下法のアルゴリズム

主問題での効率的な計算
確率的分散縮小勾配降下法(SVRG)
SVRGのアルゴリズム

5.3.2 確率的分散縮小勾配法の収束証明

5.4 確率的平均勾配法

アルゴリズム

第6章　分散環境での確率的最適化


6.1 オンライン型確率的最適化の分散処理


6.1.1 単純平均
6.1.2 同期型・ミニバッチ法
6.1.3 非同期型分散 SGD:Hogwild!


6.2 バッチ型確率的最適化の分散処理:確率的座標降下法


6.2.1 主問題における並列座標降下法
6.2.2 双対問題における並列座標降下法: COCOA

付録A

A.1 有用な不等式
A.2 正則化学習法の1次最適化法(近接勾配法)
A.2.1 平滑でない凸関数の最小化
A.2.2 平滑な凸関数の最小化
A.2.3 平滑な凸関数の最小化: ネステロフの加速法
イメージ