“Online and Batch Learning using Forward Looking Subgradients” John Duchi, Yoram Singer 2008 高松慎吾 概要 • 正則化つき損失関数最小化の新しい枠組み を提案する • 1st step：正則化なしの勾配法を実行 • 2nd step：1st stepの結果をある程度保ちながら、 正則化項を最小化する • バッチとオンラインにおいて、単純で効果的な アルゴリズムを得ることができる。 • さらに、高次元スパースなデータに対して効果 的な実装を示す 表記 • ベクトル：ボールド体 • <u,v>：ベクトルuとvの内積 • ||x||p：ベクトルxのp-ノルム コンテンツ • Introduction • 背景 • Forward Looking Subgradient Method • 提案法 • Convergence Analysis • 提案法の収束性について • Regret Analysis • オンライン学習における、Regret boundsについて • Derived Algorithms • 各正則化項における具体的な更新アルゴリズム • Efficient Implementation in High Dimensions • 高次元スパースなデータへの効率的な実装 • Preliminary Experiments • 実験 • Conclusion Introduction（背景） • 目的：次の関数を最小化すること • f と r は下限を持つ凸関数（一般性を失うことなく、 値域はR+とできる） • fは次のような経験損失関数であることが多い • rは正則化項で、複雑なベクトルにペナルティを与 える。たとえば、 • このタスクは機械学習では一般的である Subgradient Method f(w) w • f(w)+r(w) を最小化する最も一般的な方法 のひとつはSubgradient Methodである • は次を満たすsubgradient setとする • subgradientを用いて次のようにwを更新する ことによってf(w)を最小化する。 • • は正の定数か減少する正数 はsubgradientのひとつ Subgradient Methodの問題点 • Subgradient Methodをf(w)+r(w)の最小化 に適用すると、更新式は次のようになる • 問題点： f や r が微分不可能な点にはまれにし かとどまらないが、微分不可能な点が最適点であ ることが多い。 • たとえば、L1正則化 微分不可能な点にもとどまるようにしたい The Forward-Looking Subgfadient Method（提案法） • FOrward LOoking Subgradient Method： FOLOS • 動機：微分不可能な点にもとどまるようにする。 • 方針：L1正則化項などの微分不可能な問題を解 析的に解ける最小化問題に和らげる。 • 次の２stepを繰り返す ・・・r(w)の微分不可能性を重視 FOLOS • 2step目について • wt+1/2 の近くにとどまる • r で表現される、複雑でないベクトルを得る • ηt+1/2はηtかηt+1と等しくする • wt+1は2step目の最適解なので次が成り立つ • 次の関係が導かれる。 1時刻先の正則化項ロス FOLOS • 利点 • アルゴリズムの観点から、FOLOSは追加的な計算 なしで、スパースな解を得ることができる • 現存のアルゴリズムを利用できる • 多くの現存の勾配オンライン凸関数アルゴリズムにお ける収束性を示すことができる Convergence Analysis of FOLOS Theorem 1 • 次を仮定する • と のnormの上界をGとする • 最適解w*のnormはD以下とする • r(0)=0 • 、 に次が成り立つ とすると、T回の繰り返し後 ηが[0,1]だと、tの増大につれて 分母が分子より速いスピードで大きくなる。 Theorem 1 について • 仮定について • 最適解w*がある閉集合に含まれるならば、∂ｆと∂r はバウンドされる（theorem2.7 of Rockafellar) • r(w)がnorm、f(w)≧0とすると、 となり、w*がhyper cube内（閉集合）にあることがわかる。 • 確率勾配降下法について • を 理が成り立つ。 と置き換えても同じ定 • とすると、 • とすると、 1 ηt ∝ t 1 ηt ∝ t 1 ) とすると、目的関数の誤差は O ( t とすると、目的関数の誤差は log t O( ) t Regret Analysis of FOLOS • オンライン学習の場合のFOLOSにおける Regret Bound を解析する • オンライン学習 • が与えられる • 目標はwtとw*の差（regret）が小さいwtを得ること • Regret • はt番目の入力の損失 • 理想的にはRegret=0としたい Theorem 2 • 次を仮定する • すべての繰り返しにおいて • と のnormの上界をGとする • cを任意の正数とする • とすると、次が成り立つ のとき Theorem 3 • 次を仮定する • すべての繰り返しにおいて • と のnormの上界をGとする • が • • 関数ｆが とすると、次が成り立つ とは、 Derived Algorithms • 様々な正則化項について、FOLOSの具体的な更新ア ルゴリズムを導いていく • 特に、微分不可能な正則化関数をみる。たとえば、L1正則 化は微分不可能であるが、スパースな解を得ることができ る。 • また、mix-norm正則化への拡張もみる。 • 導出に都合がいいように、表記法を変える。 • v ： • ： • よって、FOLOSの最適化の式は次のようになる • ： L1正則化 とし、成分の和に直すと 添え字を取り除くと、次の最小化を解けばよいことになる。 ※ である。 と仮定すると、 となるが、これはw*が最小解であることに矛盾する v≧0と仮定すると、次の制約つき最小化問題を解くことになる。 • 目的関数は唯一の最小解を持つので、KKT条 件を満たす解が最小解となる。 • KKT条件より • • • • β=0のとき、 のとき、 の偏微分=0 ⇔ となるので、 。よって v≦0のときはwの符号を変えればよいので、解は次のように書ける 参：KKT条件 L2^2正則化 この正則化項を考えると、FOLOSの最小化問題は次のようになる。 停留条件は よって、解は次のようになる。 ちなみに、 正則化項が微分可能なので、 通常のsubgradient methodの 更新式が計算できる。 ~ wt+1 = wt - ηt gt - λwt f これも原点方向に縮小する 解になっている。 これは、原点方向に縮小する解になっている。 ※L∞normやL2normについても更新式が導出できる。 mixed norm • Berhu正則化 -γ γ • L1正則化とL2正則化のハイブリッド • ０に近い部分ではL1正則化なのでスパースな解 が得られ、値が大きい部分ではL2正則化なので 極端に大きな値はなくなる • Berhu正則化に関するアルゴリズムは次のよ うになる。 より大きい領域ではL2正則化、小さい領域ではL1正則化をする更新式 Efficient implementation in high dimensions • テキスト分類などでは重みベクトルwは高次元スパース になる。 • こういった場合は =0の要素の更新はサボりたい L1 a b c d e L2^2 このままでは =0 となる要素でも wを更新する必要がある。 =0となる要素の更新はサボりたい data1 1 0 0 2 1 data2 2 0 0 0 1 data3 3 0 0 0 0 data4 1 0 0 0 2 data5 0 0 2 1 0 Lemma 6.1. • wT を次の繰り返し最適化問題P1の解とする。 • t=1,…,Tとすると、 • w* を最適化問題P2の解とする。 • このとき、 致する。 において、 と は一 • FOLOSのアルゴリズムで、 の要素が0となる 部分ではLemma 6.1のP.1と同じ問題となる。 • そこで、 = を記憶しておき、必要に応 じてP.2の問題を解けばよい。 • 具体的には、 と最後にupdateされた時刻t0の を記憶しておき、次の問題を解けばよい • これで、 がk個のnon-zero要素を持っていた ときの更新は、計算時間O(k)のupdateで済む。 Preliminary Experiments • L2^2正則化とL1正則化について実験を行う。 • 最先端のアルゴリズムであるPegasosと比較 • Pegasos：高速な射影勾配法に基づくアルゴリズム • 損失関数は次の2種類を適用 • 次のようにデータを作成 • • • • w：標準正規分布からサンプル＆50％の要素をランダムに選び0にする x：標準正規分布からサンプル y：y=sign(<w,x>)で作成し、10%を反転させる（ノイズ） 400次元のデータ1000個を訓練データとして用いた L2^2正則化 logistic, projectionあり hinge, projectionあり 正則化項= logistic, projectionなし 20trialの平均 L1正則化 • L1正則化のlogistic regression問題 • 考察 • Subgradよりよい • IPより立ち上がりはよ いが最終的に負ける • IPはlogistic regression に特化したアルゴリズ ムである。 正則化項= Subgrad = Subgradient method IP = inter point method L1正則化 • L1正則化のスパース具 合をみる • 各グラフは異なるλの結 果を表している • 考察 • FOLOSはすばやくス パースな解を見つけ、そ こに留まる。 正則化項= Conclusions and future work • まとめ • 様々な正則化項付の凸最適化問題に対する新しいアルゴ リズムを提案した。 • アルゴリズムの収束とオンラインのregret boundsについ ても解析した • スパースな解を導く正則化に適用できる • FOLOSの最適化問題(1st step)を解けるならば、どんな損 失関数にも適用できる • 今後の課題 • FOLOSの最適化問題の第一項をEuclidean距離ではなく、 Bergman距離に一般化したい • より大規模なデータで実験したい
© Copyright 2024 ExpyDoc
