オンライン学習 定式化 評価法:Regretなど パーセプトロン Passive Aggressive Algorithm (アルゴリズムと損失の限界の評価) Confidence Weighted Algorithm Pegasos Coordinate Descent バッチ、オンライン、ストリームの比較 ビッグデータへの対応 オンライン(あるいは逐次)学習とは データを1つづつ読み込んで、それまでの学習結果 を更新する。 2つの利用局面 1. データ全体は保持しているが、学習を1データ毎に行う 2. データが1こずつ時系列としてやってくる この場合はストリームという。 データ全体をメモリの乗せなくてよいのでマシンに必 要なメモリ少、あるいはメモリに乗りきらないほど大 きなデータから学習可能 1個のデータからの学習(これを1roundという)だけ なら高速 オンライン学習の概観 以下1,2,3を時刻 t=1,2,…,Tで繰り返す 1. 時刻tにおいて、仮説ht、入力データxt 、正しい結果データ yt∈Yが与えられる。 2. 仮説ht による結果h (t) (xt)を計算し、その後でytとの比較を 損失関数lによって行う。 つまりl(h (t) ,(xt , yt ))を計算 lとしては2乗損失やヒンジ損失など 3. 損失関数lの値に応じてh (t) を更新し、新しい仮説 h (t+1)を 求める T 最終的な目的の累積損失 l h(t ) , xt , yt などを最小化す t 1 ること 簡単(線形)な仮説として重みベクトルwとxの内積 𝐰, 𝑥 を 使う場合はhを𝐰と書き、 ft w l w, xt , yt と定義 オンライン学習のイメージ 予測 データ xt 識別関数h(t) 正解(実測 あるいは人 手による) (t) h (xt) yt If 予測≠正解 then 更新:h(t)→h(t+1) オンライン学習の評価法 仮説hのなす空間をH, tラウンドの予測値をh T 累積損失 t 1 l h(t ) xt , xt , yt (最小化したい): (t) (xt) x , x , y l h , x , y : h H Regret H max Regret h l h x , x , y min l h , x , y Regret T h t 1 l h * T T (t ) t t t * t 1 * t t * T T h*H T t 1 T (t ) t t t h*H t 1 * t t Mistake(失敗回数)のupper bound 以後は識別に失敗しなくなるまでの学習回数=学習 データ数 オンライン学習をオンライン凸最適化の観点から定式化 By Shai Shalev-Shwartz 以下では L(w ,(xi , yi )) をfi (w)と略記することに留意。 最も簡単なオンライン学習は、過去の全roundの損失を最小 化するようなwを選ぶ方法:Follow-The-Leader(FTL) Follow The Leader (FTL) t 1 t w t arg min f i w wS Sは wの取り得る範囲で凸 i 1 Lemma 10 w1 , w 2 を FTLで生成された重みベク トル u S T T t 1 t 1 RegretT u f t w t f t u f t w t f t w t 1 Proof f w を Lemma 10の不等式の両辺から引 き移項すると t t t T T f w f u そこのこの不等式 t t 1 t 1 t t 1 を帰納法で導く。 base case : T 1の場合は w t 1の定義 w 2 arg min f1 w より、式の成立する w induction step : t T 1で不等式が成立すると 仮定する。つまり u S T 1 T 1 f w f u t 1 t 1 t t 1 t 両辺に fT w T 1 を加えると T 1 T f w f w f u t 1 t t 1 T 1 T t 1 t この式は u Sで成立し、 u w T 1でも成り立つ T T t 1 t 1 T f t w t 1 f t w T 1 min f t u uS t 1 T 最後の等式は w T 1の定義 w T 1 arg min f t w より。 □ wS t 1 uを選べる。 Follow-The-Regularized-Leader (FoReL) FTLではwに制約がないので、過学習が危ぶまれる 。そこで、正則化項(Regularizer)を加えたものを最 適化(FoReL) FoReL t 1 t w t arg min f w i Rw wS Sは wの取り得る範囲で凸 i 1 Lemma 20 w1 , w 2 を FoReLで生成された重みベク トル u S T T f w f u Ru Rw f w f w t 1 t t t 1 Proof Lemma10で t 0..Tとし、 f 0 R とおけばよい □ t 1 t t t t 1 Example of FoReL: 1 Rw w 2 1 ft w w, z t かつ S R で正則化項 Rw w 2 d t この場合は FoReLは w t 1 arg min i 1 2 2 2 2 where 0 1 w, z i w 2 2 2 t t 1 w 2 より、 0 w, z i w 2 z i を使えば w i 1 2 i 1 t w t 1 z i w t z t i 1 つまり w t 1 w t ft w t Online Gradient Descent: OGD 30 FoReLのRegretのUpper Bound Theorem 30 ft w w, z t , S R d , Rw T 1 2 u RegretT u u 2 zt 2 t 1 1 T if U u : u B and z t T t 1 B then とおくと L 2T Proof Lemma 20と式 (30)より 2 2 1 2 w 2 とする 2 2 2 L2 RegretT U inf RegretT u BL 2T uU T RegretT u Ru Rw1 ft w t ft w t 1 t 1 T 1 2 u 2 w t w t 1 , z t 2 t 1 T 1 2 u 2 zt 2 t 1 2 2 Regretの上限が 𝑇に比例してい ることに注目! 損失fが連続でない場合 Sub-gradient(劣勾配)のFoReL fの凸性が重要 Lemma 50 Sが凸集合、 fが S上の凸関数 iff w S , zu S , f u f w u w, z (50) (50)を満たす zの集合を fの sub - gradient と呼び f w と書く。 連続なら f w と同じ。 これを使った Online Gradient Descent が以下。 0, w1 0 , w t 1 w t z t where z t ft w t Sub-gradient の場合のFoReLのRegret Bound 再掲: Lemma 20 and Theorem30 : w1 , w 2 を FoReLで生成された重みベク トル u S T T f w f u Regret u Ru Rw f w f w t 1 t t t T 1 T 1 2 u 2 w t w t 1 , z t 2 t 1 t t 1 t t t 1 T 1 2 2 u 2 z t 2 (60) 2 t 1 Lemma 50 を少し変形して再掲: Sが凸集合、 fが S上の凸関数 iff w t S , z t w t 1 S , f w t 1 f w t w t 1 w t , z t (50) 凸だと各 round tに対して ft w t 1 ft w t w t 1 w t , z t だから ft w t ft w t 1 w t w t 1 , z t ft w t ft w t 1 w t , z t w t 1 , z t T T t 1 t 1 これを Lemma 20 and Theorem30に plug inすると sub - gradient OGDでも T RegretT u Ru Rw1 ft w t ft w t 1 問題はこの部分 t 1 T 1 2 u 2 w t w t 1 , z t 2 t 1 T 1 2 u 2 zt 2 t 1 2 2 T 1 2 Regret T u u 2 zt 2 t 1 2 2 1 2 u 2 TL2 にしたいが 2 そのためには z t が上から押さえられる ことを示す必要がある sub - gradientの定義から f w t f w t 1 z t , w t w t 1 where z t f w t fが L Lipfshitzだとすると 上の2式を合わせると L w t w t 1 f w t f w t 1 where L L w t w t 1 z t , w t w t 1 z t w t w t 1だったので L z t z t 2 L z t 2 1 2 Regret T u u 2 TL2 BL 2T same as Theorem 30 2 このboundは 1 2 にできる。 付録参照 FoReLの上界を厳しくする • まず、FoReLの別形式を導入する t w t 1 arg min Rw w, z i i 1 w t arg max w, z i Rw w ここで i 1 g θ arg max w, θ Rw とおくと FoReLは次式で書ける w initialize θ1 0 for t 1,.., T w t g θt ; θt 1 θt z t ; (z t ft w t ) Online Mirror Descent (OMD)という 数学的ツールの準備 • Fenchel-Young 不等式 f θ max u, θ f u とすると u u, f θ u, θ f u u f θ あるいは θで微分可能なら u f θ f θ u, θ f u w Rw 2 2 2 2 w θ * R θ max w, θ w 2 2 数学的ツールの準備 • Bregman Divergence: DR DR w u Rw Ru Ru , w u R z * z 2 DR* z1 z 2 2 z1 z 2 2 だと R* z z 2 2 z1 2 2 ( DR1) z 2 z 2 , z1 z 2 2 DR w u Online Mirror Descent で g Rであるなら 補題 OML1 : t 1 t w u , z R u R w D z || z t t 1 i i R t 1 t 1 i 1 i 1 Proof T T Fenchel - Young 不等式から T T Ru u, z t Ru u, z t t 1 t 1 T R zt t 1 (1) t 1 w t g θt R z i (2) i 1 Bregman Divergenceの定義より T t 1 t T R z t R 0 R z i R z i t 1 t 1 i 1 i 1 t 1 t R 0 w t , z t DR z i || z i (3) t 1 i 1 i 1 なお、 R 0 max w 0, w Rw min w Rw Rw1 T t 1 T (4) これらを合わせると T t 1 T t u, z t Ru R z t Ru R 0 w t , z t DR z i || z i t 1 i 1 t 1 i 1 t 1 t Ru Rw1 w t , z t DR z i || z i t 1 i 1 i 1 T 定理 OMD2 Online Mirror Descent において 2 w θ * Rw , つまり Rθ である 2 2 2 T t 1 2 u T w t u, z t zt 2 2 t 1 2 とする。 OMD10 Proof 補題OMD1 と DR1より明らか ■ T 1 2 L2 z t かつ T t 1 T t 1 w t u, z t BL T B ただし u B とすると L T OMD20 パーセプトロン(Perceptron) FoReLから導出されたOnline Gradient Descent の例としてパーセプトロンを紹介する。 パーセプトロンはF. Rosenblattが1956年に提案し た線形識別の繰り返しアルゴリズム 効率がよく、現在でもその価値が高い 入力xtが目的のクラスに 属する場合にyt=1, 属さない場合にyt= −1 f t w yt w, x t 右図 f t 0 0 これより失敗側では 正 yt w, xt 𝑓𝑡 𝑤 のsub-gradientを計算すると z t ft w t if yt w t , xt 0 then ft w t z t 0 otherwise ft w t z t yt xt ft w t Online Gradient Descentの形式: w t 1 w t z t に当てはめると wt w t 1 w t yt xt if yt w t , xt 0 otherwise ηは正 次にPerceptronのアルゴリズムが得られる。 FoReLの別形式として導入したOnline Mirror Descentとみれば、(OMD20)の上界が使え る Perceptron アルゴリズム 初期化: w1 0 for t 1,2 ,...,T 入力 xt if yt w t , xt 0 then w t 1 w t yt xt else w t 1 w t 分類に失敗し たときだけ そのデータを分類器Wに足し 込むという至って単純な更新 線形分離可能性 線形分離可能:クラスを識別するする超平面 が存在する場合 そうでない場合を線形分離不可能という。 下図参照 線形分離可能 線形分離不可能 γ:マージン Perceptronアルゴリズムの分析 FoReLの別形式として導入したOnline Mirror Descentとみれば、(OMD20)の上界が使える T T RegretT u ft w t t 1 t 1 1 T 2 ft u u 2 zt 2 2 t 1 2 2 (60) ここで解析の容易さの ため ft [1 yt w t , xt ] で近似する。 (もとの ftより必ず大きいので上 界は甘くなる。) sub - gradientは z t 1 yt y xt w t ,xt 0 t Wt,Xtをスケール変換し て、最も0に近い正例で 𝑤𝑡 , 𝑥𝑡 =1となったと見 なしたと考えてもよい Perceptronアルゴリズムの分析 判定の失敗 : mistakeを起こした xtの集合を M、 mistake回数 M ftの形より明らかに T f w M t t 1 u (60)の右辺の最小値は = T M ft u MRu t 1 t MR R max xt とおくと t のときなので 1 2 u M R2 2 2 (70) T if u yt u, xt 1 then ft u 0 : データが線形分離可能 t 1 M MRu M R u 2 2 R2 2 1 線形分離できる場合 は境界面に最も近いデ ータと境界面の距離 u Passive Aggressive Algorithm K.Crammer et.al. Online Passive-Aggressive Algorithms Journal of Machine Learning Research 7 (2006) 551–585 識別(あるいは分類)の問題設定 n round t でn次元データ xt R が到着 x t の正負は yt 1 : 正, 1 : 負のように与えられる n w R sign w, x : 正負を表すので 重みベクトル: 正しい(誤った)判定: yt wt , xt 0 、 0 wtはデータが到着するたびに更新されている 損失関数による定式化 境界面そのもので判定はきわどいのでマー ジンを持たせる。マージンを1とした場合の損 失関数(hinge-loss function)は以下の通り 0 y w, x 1 w; x, y 1 y w, x otherwise 以下では t w t ; xt , yt と書く 1 y w, x y w, x 0 1 この設定で、round tの更新は次の条件付き 最適化問題となる。 1 w t 1 arg min || w w t ||2 2 wR n s.t. w; xt , yt 0 PA 1 FoReLとして見ると FoReL t 1 t w t arg min f w i Rw wS Sは wの取り得る範囲で凸 i 1 t 1 arg min w i ; xi , yi 1 2 w wt 2 2 wS i 1 次ページのように FoReLの定式化では に相当する は 個別の yt , xt , w tに依存するため (60)のような簡単な解析が できない。 最適化問題(PA-1)を解く If lt=0 then wt minimizes 1 || w w t ||2 2 Passive wt+1 =wt If lt≠0 then Lagrange 未定乗数法で解く。 1 2 Lw, w w t 1 yt w, xt 2 Lw, w w t yt xt 0 w w w t yt xt 1 2 2 L xt 1 yt w t , xt 2 L 2 xt 1 yt w t , xt 0 1 yt w t , xt t w t 1 w t t yt xt 2 xt Aggressive Passive Aggressive xt xt w t 1 w t w t 1 w t t yt xt Passive Aggressive t t xt 2 soft marginの学習法 PA-I, PA-II w t 1 arg min wR n 1 2 w w t C 2 1 2 w t 1 arg min w w t C 2 2 wR n s.t. w; xt , yt , 0 s.t. w; xt , yt PA II w t 1 w t t yt xt t t min C , 2 PA I xt t t xt 2 1 2C PA I PA II Passive Aggressive Algorithm INPUT: aggressiveness parameter C > 0 INITIALIZE: w1 = (0, . . . ,0) For t = 1,2, . . . • receive instance: xt ∈ Rn • predict: ˆ yt = sign wt ,xt • receive correct label: yt ∈ {−1,+1} • suffer loss: lt = max{0 , 1−yt wt ,xt } • update: t 1. set: t x 2 (PA) t t t min C , 2 xt t t 1 2 xt 2C (PA-I) (PA-II) 2. update: wt+1 = wt +τt wt ,xt 付録:PA-Iの導出 PA Iの Lagrangianは以下の通り 1 2 w wt C 1 y w xt 2 1 2 w wt C 1 y w xt 0, 2 L( w, , , ) 0 ( pa1 1) L 0 w wt yt xt w C の最小値は 0で C 0 ( pa1 2)のとき。 C 0である。そうでないと すると、 C はいくらでも小さくな れる ので、 Lの最小化ができない。 KKT条件より 0なので、( pa1 2)より C 0 C ( pa1 3) 以下では C t xt (case 1)と C t xt (case 2)に分けて考える。 2 2 case 1 ( pa1 - 2)を ( pa1 1)に代入し L( w, , , ) 1 2 w wt 1 y w xt となるので、これを 2 元々の PAと同じく t t xt ( pa1 4) 2 wについて最適化すると case 2 t / xt 2 C C xt 元々の optimazation 1 2 wt 1 arg min w wt C 2 w 2 1 yt wt , xt ( pa1 6) s.t 1 yt w , xt ( pa1 7) and 0 と w wt yt xt により 1 yt wt , xt xt ( pa1 8)と ( pa1 6)を組み合わせると 2 ( pa1 8) C xt xt 2 2 ( pa1 3)で C だったから、 0 KKT条件から 0なので、 0 ( pa1 2)より C t (case 1) (case 2)を合せると t min C , 2 xt 付録:PA-IIの導出 t 0 t 0 t 0の場合について考えれ ばよい 1 2 L( w, , ) w wt C 2 1 y w xt 0 ( pa 2 1) 2 L 0 w wt yt xt w L 2C 0 2C この と wを Lに代入すると 2 1 Lw, xt 1 yt wt xt 2 2C L 1 yt wt xt t 0 ■ 1 1 2 2 xt xt 2C 2C 2 損失の限界の評価 任意の固定された重み ベクトル uに対する損失を lt*とする。 lt l wt ; xt , yt lt* l u; xt , yt Lemma 1 x1, y1 , . . . ,xT , yT はデータ列。ただし xt R n , yt +1, 1 τ tは PA, PA - I, PA - IIの Algorithm における更新式 の parameter 上記の u R nに対して τ 2 T t 1 t t τ t xt 2 2*t u 2 Proof def t wt u wt 1 u 2 w u T t 1 T t t t 1 w1 0 T t u 2 2 wt 1 u 2 w u 1 wT 1 u 0 2 2 wT 1 u 2 なので 2 t 1 minimum marginを violateしない場合は、 t 0, t 0 よって、 t 0の場合にだけ注目: wt 1 wt yt t xt t wt u wt 1 u wt u wt u yt t xt 2 2 2 wt u wt u 2 t yt wt u , xt t2 xt 2 2 2 t yt wt u , xt xt t2 xt 2 2 2 t 0 t 0の場合 t 1 yt wt , xt yt wt , xt 1 t 同じく yt u , xt 1 *t t 2 t yt wt u , xt t2 xt 2 t 1 1 t xt * t t 2 t t xt 2*t 2 2 t 2 2 ■ 2 Theorem T , max xt R u s.t. t *t 0 Lemma 1 と同じ設定。 t 2 2 R u t 2 t 1 Proof t *t 0 and Lemma 1 PAでは τt t xt t xt 2 R 2 2 T τt 2 t τt xt t 1 T 2t xt 2 u 2 u 2 2 t 1 T R u t 1 2 t 2 2 T 2 2 u R t t 1 2 ■ Theorem 2では次の制約が厳しい。 u この制約は、uで完全な識別ができること。 この制約を外す定理を考える Theorem 3 Lemma 1 と同じ設定。 t xt 2 *t u; xt , yt であるような 1 このとき u 2 t 1 T 2 t T t 1 * 2 t 2 Proofは次ページ s.t. t lt* 0 u R nに対して Proof 2 xt T 1 t lt τt 2lt τt xt t 1 2l u 2 * t l l t 1 T l t 1 2 t 2 T l 2 t t 1 l T t 1 l T LT 2 LT 2 t 1 * 2 t * 2 t * t t T l 2 t t 1 T l 2 ltlt* u t 1 T Cauchy - Schwartzより T 2 2 t 2 t 1 l T * 2 t t 1 だから T l u ここで 2 t 1 2 t LTとおくと u 0 2 LTの最大値 max LTは上式で を とした2次式の大きな max LT T t 1 * 2 t T t 1 * 2 t u 2 a b a bを使うと max LT max T 2 t 1 2 max t 2 t 1 T T t 1 * 2 t ほうの解。 u 2 t T t 1 * 2 t u 2 ■ PA-Iにおける入力データ識別の失敗回数の上限 t xt R t min 2 , C xt T 2 2 * # mistakes max R ,1 C u 2C t t 1 2 2 Proofは次のページ t回目の繰り返しで mistakeが起きたとすると xt 2 R と t min t xt , C より 2 2 t 1 min 1 R 2 , C t t M を繰り返し全体におけ る mistake回数とする。 T 0 t t なので min 1 R , C M t t pa1 - 10 2 t 1 *t u; xt , yt t t C t かつ t xt * T * 2 t これを Lemma 1 τt 2 t τt xt 2*t u に代入すると t 1 T 2 2 T * u 2 C tt t pa1 - 20 2 t 1 t 1 pa1 - 10pa1 - 20 より pa1 - 30の両辺に maxR 2 ,1 Cを掛けると T 2 * M max R ,1 C u 2C t ■ t 1 2 T min 1 R , C M u 2C t 2 2 t 1 * pa1 - 30 PA-IIにおける累積損失の上限 xt 2 R 2 t t xt 2 1 2C T 1 2 2 2 * R u 2 C t t 2C t 1 t 1 T Proofは次のページ T Lemma 1 : u τt 2 t τt xt 2*t で右辺の 内で τt *t を差し引く 2 t 1 1 2C ただし u τ 2 τ 2 τ τ x 2 τ τ x T 2 t t 1 t T t 1 t T t t 1 t 2 t 2 t t xt 2 2 2 t t 2 t 2 * t τ t * t 2 2 τt *t 2 τt2 2 τt *t *t 2 2 2 *t 2 2 1 2C を代入すると 1 2 2 *2 u 2 τt t τt xt 2C t 2C t 1 T 2 τt t xt 2 2 t 2 2 *2 xt 1 2C を代入すると u 2C t 1 2 t 1 x t 2C T T 2 1 2 * R を使えば、 R u 2 C t ■ 2C t 1 t 1 T 2 2 t 2 Confidence Weighted Algorithm Crammer et al. 2008 学習する重みベクトルWを点ではなく分布(正規分布)にする Wの期待値と分散を更新する Pegasos: Primal Estimated sub-GrAdientSOlver for SVM L2正則化+L1損失のSVM 1 2 min f w; B w 2 max 0,1 yi w T x w 2 k Aは学習に使うデータ、 k A iB Pegasosの更新は次式による w t 1 / 2 w t f w t ; A where f w; A w t f w t ; Aは fの劣微分 f w t ; Aの要素 1 A yi xi iA 1 , lはベクトル w, xiの次元、 tは繰り返し回数 t 更新の後、wを半径 min 1, 1 / の球にproject A i | i A,1 yi wT xi 0 , w min 1, 1 / w 2 w 以上を収束するまで繰り返す。データ集合Aごとな ので、onlineというよりはmini-batch Pegasos:Primal Estimated sub-GrAdient SOlver for SVM のアルゴリズム 初期化 : w1 0 For t 1,2,......, T 全データ Dから Atを選ぶ。 At k At i At | 1 yi w t , xi 0 t 1 t w t 1 / 2 1 t w t 1 w t 1 min 1, w t 1 / 2 Output : wT 1 t At yx iAt w t 1 / 2 i i f(w)の評価 まず w* arg min f w とする。 f w また、関数 fは、 f w 2 w が凸のとき、 strongly convex という。 2 Lemma1. f1 ,..., fTを - strongly convexとし、 Bを閉凸集合とする。 w1 ,..., wT 1を以下のようなベクト ルの列とする: tは ftの劣微分の要素 w1 B, t 1 w t 1 arg min w t t t w t w ただし t 1 t wB t w t Gのとき、 u Bに対して次式が成り立 つ 1 T 1 T G 2 1 ln T ft w t ft u T t 1 T t 1 2T Proof : ft は strongly - convexで、 tは劣微分の要素なので 内積w t u t ft w t ft u wt u 2 (10) 2 w t 1は wtの Bへの projectionであり wt w t t t とおき、 u B なので wt u w t 1 u である。よって 2 2 w t u w t 1 u w t u wt u 2t w t u t t2 t 2 2 2 2 2 (15) t Gかつ t 1 t なので (15)により w t u w t 1 u w t u, t t G2 2t 2 2 (10)と 20 を組み合わせると 30を t 1, Tまで総和をとると 2 20 w u w t 1 u ft w t ft u t t G 2 wt u 2t 2 2 2 2 w t u 2 w t 1 u 2 T 2 2 ft w t ft u wt u t G t 1 2 2t 2 t 1 t 1 T w t u 2 w t 1 u 2 w u t 1 t を代入すると 40 t 2 t 2 t 1 T T T t 1 w t u t w t 1 u t 1 2 2 2 40 G2 T 1 2 t 1 t G2 T 1 T G2 T 1 G2 2 1 lnT w t 1 u 2 t 1 t 2 2 t 1 t 2 2 30 Lemma1を拡張するとさらに強力な次の定理が得られる。 詳細は:Mathematical Programming 127(1), 2011, pp.3-30 Pegasos:primal estimated sub-gradient solver for SVM. Shai Shalev-Schwarts, et.al. Theorem 1 : x(入力データ ) : x R, w* arg min f w f w かつ projectionしたときは c projectionしないときは R c 4 R 2 とすると T 3に対して 1 T 1 T c1 ln T * f w ; A f w ; A t t T t T t 1 2 T t 1 2 Atは全データ Dから選ばれた部分集合 。 Proof : if projectionが起こらない then Bは半径 1 の球で、 w t 1 arg min w t t f w t ; At w wB Theorem1を証明するには Lemma1の前提条件が成立する ことを証明する。 1 f w, At は、 - strongly convex : - strongly convex 2 2 w と Atのヒンジ損失の平均値 の和なので Proof : cont' d 2 次に t の上界を求める。 if projection stepが実行された then w t 1 かつ x R f w t ; At w t 1 yi x i R A iA if projection stepが実行されなかった then w t 1 1 t w t t 1 1 y x 1 w i i t t t A At iAt t where At i At | 1 yi w t x i 0 ここで w1 0 w 2 1 A1 1 y x i i A 2 iA1 1 t 1 wt t j 1 Aj i w t 1 R iA j i iAt 1 1 y x w i i 3 2 A1 iA1 2 1 1 w 4 3 2 A1 yx yx 1 y x i i 3 A 3 iA2 i i yi x i iA1 yx iA3 i 1 2 A2 i ここの導出は初等的が だちょっとした計算 yx iA2 i i Proof : cont' d 3最後に w* Bを示す。 projectionしない場合は、 w t 1 arg min w t t t w t w により wB w* Bと言える。 projectionした場合は、 w* 1 ここで対象にしている を示す。 SVMの主問題は以下の形式 m 1 2 min w C i s.t. i 1, m : i 0, i 1 yi w xi 2 i 1 ここで双対問題を思い C 1 m とおき、以下の双対問 題を導く。 つくところがいかにも m min i i 1 1 2 m y x i 1 i i i 2 s.t. i 1, m : 0 i C 主問題の解を w* , * 、双対問題の解を *とすると SVM的 (50) Proof : cont' d 主問題の解を w* , * 、双対問題の解を *とすると m 1 * w y x であり 50 は次のように書き直せ る。 w 1 2 i 1 * * i i i * SVMの問題では強双対定理 が成り立つので 1 *2 1 * * * w C w 1 1 2 2 * 2 max i C 1 m * 2 強双対定理の実に 賢い使い方だ m * 1 i Cm 1 i 1 1 *2 1 *2 1 *2 1 1 * * * w w C w w 1 1 2 2 2 2 w* 1 2 以上の結果 12 3を Lemma1に適用すれば定理が得 られる。 □ Coordinate Descent C.-J. Hsieh, et.al. ICML2008 Target: L1損失- L2正則化のSVM 双対化し て解く。下に定義 1 T min f α α Q α eT α α 2 subject to 0 i C i 1,..., l D where Qij yi y j xi , x j Coordinate Descent Coordinate Descentは順番に1変数づつ選 び、他の変数は固定して最適化。 1 min f D α dei f D α Qii d 2 i f D α d d 2 f Dは fの双対 subject to 0 i d C where ei 0 ,..0,1,0,...0 i 1 dを計算することによる iの更新式は下式 D f α i i min max i ,0 , C Qii CD10 T Coordinate Descent つづき (CD10)のQiiはαiの最適化の中で1回計算すれ ばよいが f α Qα 1 y y x , x 1 は x , x t 1,.., l l D i i t 1 i t i t t の計算コストが Onl でうれしくない。そこ u i t で l y x t 1 t t t を保持しておけば i f D α Qα i 1 yi u, xi 1 (CD20) となり計算コストは u u+ yi i i xi 以下の計算のための On でうれしい。 CD30 i (CD10)の更新前、 i (CD10)の更新後 L1損失-L2正則化のSVMの Coordinate Descent アルゴリズム l αの初期化、および u yi i xi i 1 Qii i 1,..., lの計算 while α is not optimal For i 1,..l (CD20)により G yi u, xi 1の計算 i i G i min max i ,0 , C Qii u u yi i i xi オンライン学習とストリーム学習 オンライン学習 1データづつ 学習 モデル 正解との比較 ストリーム学習 データ 発生 1データづつ 到着データのモデ ル学習 と分類などの結果 学習結果 モデル バッチ、オンライン、ストリームの比較 バッチ学習 オンライン学習 ストリーム学習 メモリに乗せるデータ 同時に全部 同時には1データ 同時には1データ メモリ量 大 小でも可能 小 データの到来 全データが揃ってか ら処理 全データが揃って 1データ到着ごとに処 から処理 理 データの消去 消去せず 消去せず 同一データの処理 回数 収束するまで繰り返 し 収束するまで繰り 1回 返し メモリに保持するモ ノ 全データと途中に内 部状態 内部状態のみで も可能 内部状態のみ 性能 精度高 バッチより劣る。 ただし、最近は バッチに肉迫 劣る 可能な処理 何でもあり やや制限あり 限定的 データは処理後に消去 捕捉:世の中、ビッグデータがホットだと言うけれど ? ? ? ? ? ? ? 異なる分類のデータ ? ? ? 分類されていない生のデータ パーセプトロンの別のアルゴリズム データ xiは N個ある。 w0 0; k 0; R max1i N xi ; repeat この部分が線形識別 for i 1 to N {if yi w(k ), xi 0 then {w(k 1) w(k ) yi xi ; k k 1 ;} } forループ内で失敗しない until ように w(k )を最適化の結果とする 。 (すなわち yi w(k ), xi 0 の場合なし) yi w(k ), xi 0 という識別に失敗したデータに、その値を 重み(学習率と呼ぶ)ηでwに足しこんで是正を図るアルゴリズム パーセプトロンは有限回で収束 mistakeのupper bound Novikoffの定理(バイアスのない場合) R max1i N xi 0 yi wopt , xi : マージン (1) である woptが存在するなら、パー セプトロン アルゴリズムが失敗す る回数はたかだか 2 2 R wopt 回である 証明 t回目の失敗 に先立つ 重みを wt 1 更新は、 yi wt 1 , xi 0 のとき起こる。 wt , wopt wt 1 , wopt yi xi , wopt wt 1 , wopt (1)より w0 0とすれば 3を繰り返し用いて 2より このとき wt wt 1 yi xi (2) wt , wopt t 4 || wt ||2 || wt 1 ||2 2yi wt 1 , xi 2 || xi ||2 xiは負例なので第 2項は負 || wt 1 ||2 2 || xi ||2 || wˆ t 1 ||2 2 R 2 || wt ||2 t 2 R 2 45より || wt || tR 5 || wopt || tR || wopt |||| wt || wt , wopt t 2 R t || wopt ||2 ■ 3 メモリ容量より大きなデータのSVM Hsiang-Fu Yu et.al KDD2010 主問題の場合はPegasos, 双対問題の場合は Coordinate Descent(CD)をブロックごとに適用 1. 全データインデクス{1,..,l}をmブロック B1,…Bmに分割 2. 主問題ならw, 双対問題ならαを初期化 3. For k=1,2,… (外側の繰り返し) 4. For j=1,…,m (内側の繰り返し) ここが重要 5. read xr ∀r∈Bj from Disk 6. {xr| r∈Bj}に関して最適化(PegasosかCD)を行う 7. wあるいはαを更新 主問題をPegasosで解く場合の6.の部分 Pegasosでは次の最適化をする 1 1 l 2 min w max1 yi w, xi ,0 w 2lC l i 1 B jを B1j ,...., B rjに分割 For r 1,..., r w w t t lC where t t 1 1 w lC B t lC w min1, w w t t 1 end For l yx , iB i i B i B | 1 yi w, xi 0 双対問題でCoordinate Descent(CD)を使う場合 min f α d f は主問題 fの双対問題 CD10 D D Bj dBj subject to d Bj 0 and 0 i di C i B j where Qij yi y j xi , x j B j {1,..., l} \ Bj ここで、 Qのうちメモリにいるブ ロック Bjに関する部分だけを 使い、下の最適化を行 う( i 1,.., lに注意) 1 T T min f D α d Bj d Bj QBjBjd Bj αT QBj,id Bj eBj d Bj f D α CD20 d Bj 2 6.の α更新部分: α Bj α Bj arg min f D α d Bj d Bj l さて、 w i yi xi をメモリ中に保持し ておけば i 1 αT Qr ,id r yr w, x r , r Bj 最適化に必要なのはブ ロック Bjだけ。 なお、 w w rBj d r yr x r CD30 という更新で 6.の更新部分で wは更新すればよい。 双対化の御利益: 教師データアクセスの観点から 主問題と双対問題は最適化するパラメタ-数 が違う。 主問題パラメタ-数 >>双対問題パラメタ-数 な ら双対問題を解くほうが楽 教科書的 SVMの場合: 主問題のパラメタ-は重みベクトル:w 双対問題にパラメタ-は個別データ:xi 必ずしも教科書的なお得感ではない。 双対化の御利益 SVMの場合: 主問題のパラメタ-は重みベクトル:w 下の定式化なので、全教師データ{tn,xn}が同時 に必要 1 arg min || w ||2 2 w ,b subject to tn ( w T ( x n ) b) 1 n 1,, N ( SVM 30) データ量が大きくメモリにロード仕切れない場 合に困ったことになる。 データ量は最近、増加傾向 双対化の御利益 必ずしも教科書的なお得感ではない。 一方、双対問題では入力データxitiのと最適化するaiが対応 する形で最適化式に現れるので、どのデータを学習で使うか 制御しやすい。(下の式参照) 例えば、 ai(i≠j)を固定して、ajを最適化する操作をjを動かして繰り返 すなど。そのときには k x i , x j j 1,..., N だけしか使わない。 N 1 N N ~ max L (a) max an an amtntm k (x n , x m ) 2 n1 m1 n1 subject to an 0 n 1,.., N ( SVM 80) N antn 0 n 1 ( SVM 70) ( SVM 90) where k (x n , x m ) (x n )T (x m ) 双対化の御利益 入力データ、あるいはカーネル行列 全体がメモリに乗り切らないビッグデ ータを扱うために、入力(すなわちカ ーネルk(xn, xm)の一部を取捨選択し てメモリにロードして使う方法が、こ N の双対化で可能になっている。 ビッグデータ時代における御利益 cf. 台湾大学のLIBSVM (SVMの実装) 全データからどのようにメモリにロードする部 分を切り出すかについてはここで紹介した通 り。 M k(xn, xm) この部分だけ 使って最適化: 次に使う部分 ロードし直して最 適化:繰り返す 内外のバランス など 内側の繰り返しで最適化でCDにおいてαの 更新を1回にし、looseな解を求めると、外側 の繰り返しが多数回必要 内側の繰り返しで精密な最適化を行えば、外 側の繰り返しは少なくてよい。 Bj{j=1,..,m}内の要素の最適化処理における 順番は外側の繰り返し毎にランダムに変更し た方が収束が早い 小さなブロックに分けてデータマイニング、機械学習 ? ? ? ? ? ? ブロックをメモリに順次ロードして学習し、その結果を活 用して次のブロックへ と繰り返す: 例えば Stream SVM 転移学習 ? ? ? この分類での学習の ? 結果を別のグループ に転移して有効利用 ? ? ? ? 異なる分類のデータ ? ? 分類されていない生のデータ 人間に正解をつけてもらうデータを絞り込む:Active学習 ? 分類しにくい部 分のデータ ? ? ? ? ? ? 異なる分類のデータ ? ? ? 分類されていない生のデータ 付録: DualityによるFoReLの定式化 Fenchel 双対 : f * θ max u, θ f u u 明らかに次式が成立 : Fenchel - Young Equality : u, f * θ u, θ f u w t arg max u, z t f u だとすると u w t , z t f w t u, z t f u f u f w t u w t , z t z tは fの w tにおける sub - gradient fが微分可能なら、等式 が成立するときは f *の定義より z t f w t Online Mirror Descent:OMD FoReLで ft w w, z t Rw なお、 Rw は正則化関数とする w Sだと Rw とする z1:t i 1 z iと略記すると FoReLは t w t 1 arg min Rw i 1 w, z t arg min Rw w, z1:t t w arg max w,z1:t Rw w w g θ arg max w, θ Rw とおくと FoReLは w 1. θt 1 θt z t 2. w t 1 g θt 1 Online Mirror Descent (OMD) g:R d S θ1 0 for t 1,2,... w t g θt ( arg max w, θ Rw ) w θt 1 θt z t where z t ft w t ここで以下が言える T T RegretT u ft w t ft u Ru min Rv z t vS t 1 1 1 2 2 * Rw w R θ 2 2 t 1 2 * (OMD100) パーセプトロンの別のアルゴリズム データ xiはN個ある。 w0 0; b0 0; k 0; R max1i N xi ; repeat for i 1 to N この部分が線形識別 {if yi w(k )T xi bk 0 then {w(k 1) w(k ) yi xi ; bk 1 bk yi R 2 ; k k 1 ;} } forループ内で失敗しない until (すなわち yi w(k )T xi bk 0 の場合なし) ように w(k ), bk を最適化の結果とする 。 yi w(k )T xi bk 0 という識別に失敗したデータに、その値を 重み(学習率と呼ぶ)ηでwに足しこんで是正を図るアルゴリズム 更新後の判定式を見て みる x bk y y x y R x bk y x R x bk y x max x yi w(k 1) xi bk 1 T y w(k ) y w(k ) yi w(k ) T T i T i 2 i i 2 i i 2 i i i 2 i 2 第2項は必ず正 よって、 i i 2 i i 2 yi w(k 1) xi bk 1 yi w(k ) xi bk したがって、失敗しな T T い方向に wは改善していく。 w(k+1) w(k) パーセプトロンは有限回で収束 mistakeのupper bound Novikoffの定理(バイアスのある場合) R max1i N xi wopt 1 かつ 0 yi wopt xi bopt : マージン T である woptが存在するなら、パー セプトロン アルゴリズムが失敗す る回数はたかだか 2 2R 回である (1) 証明 入力ベクトルに値 Rとなる 1次元加え、 xˆi xiT , R とする。 T T T bi wˆ i wi , とする。 R t回目の失敗 に先立つ 重みを wˆ t 1 更新は、 yi wˆ t 1 xˆi yi wt 1 xi bt 1 0 のとき起こ T る。 x yは内積 T T b b このとき wˆ t wtT , t wtT1 , t 1 yi xiT , R wˆ t 1 yi xˆi R R bt bt 1 2 なぜなら 、 bt bt 1 yi R yi R R R ( 2) 証明 つづき T T T T bt T bt 1 T wˆ t wt , wt 1 , ( 2) yi xi , R wˆ t 1 yi xˆi R R 3 (1)より wˆ t wˆ opt wˆ t 1 wˆ opt yi xˆi wˆ opt wˆ t 1 wˆ opt wˆ 0 0とすれば 3を繰り返し用いて wˆ t wˆ opt t 2より 4 || wˆ t ||2 || wˆ t 1 ||2 2yi wˆ t 1 xˆi 2 || xˆi ||2 xˆiは負例なので第 2項は負 || wˆ t 1 ||2 2 || xˆi ||2 || wˆ t 1 ||2 2 || xi ||2 R 2 || wˆ t 1 ||2 2 2 R 2 || wˆ t ||2 2t 2 R 2 45より || wˆ t || 2tR 5 || wˆ opt || 2tR || wˆ opt |||| wˆ t || wˆ t wˆ opt t 2 2 R R 2R 2 2 ˆ ˆ t 2 || wopt || 2 || wopt || 1 2 ■
© Copyright 2025 ExpyDoc