オンライン学習 定式化 評価法： Regret など パーセプトロン Passive Aggressive Algorithm ( アルゴリズムと損失の限界の評価） Confidence Weighted Algorithm Pegasos Coordinate Descent バッチ、オンライン、ストリームの 比較 ビッグデータへの対応

オンライン（あるいは逐次）学習と は  データを１つづつ読み込んで、それまでの学習 結果を更新する。  2 つの利用局面 1. データ全体は保持しているが、学習を 1 データ毎に 行う 2. データが１こずつ時系列としてやってくる  この場合はストリームという。  データ全体をメモリの乗せなくてよいのでマシ ンに必要なメモリ少、あるいはメモリに乗りき らないほど大きなデータから学習可能  1 個のデータからの学習（これを 1round という） だけなら高速

オンライン学習の概観

識別関数 h (t) データ xtxt 正解（実測 あるいは人 手による） ytyt 予測 h (t) (x t ) If 予測 ≠ 正解 then 更新： h (t) →h (t+1) オンライン学習のイメージ

オンライン学習の評価法  仮説 h のなす空間を H, t ラウンドの予測値を h (t) (x t )  累積損失 （最小化し たい）：  Mistake( 失敗回数）の upper bound  以後は識別に失敗しなくなるまでの学習回数＝ 学習データ数

オンライン学習をオンライン凸最適化の観点から定 式化 By Shai Shalev-Shwartz  以下では L (w,(x i, y i )) を fi (w) と略記することに留意。  最も簡単なオンライン学習は、過去の全 round の損失を 最小化するような w を選ぶ方法： Follow-The-Leader(FTL)

Follow-The-Regularized-Leader (FoReL)  FTL ではｗに制約がないので、過学習が危ぶま れる。そこで、正則化項 (Regularizer) を加えた ものを最適化（ FoReL)

Example of FoReL: Online Gradient Descent: OGD

FoReL の Regret の Upper Bound  Theorem 30

損失 f が連続でない場合 Sub-gradient( 劣勾配）の FoReL  f の凸性が重要

Sub-gradient の場合の FoReL の Regret Bound 問題はこの部分

FoReL の上界を厳しくする まず、 FoReL の別形式を導入する Online Mirror Descent (OMD) という

数学的ツールの準備 Fenchel-Young 不等式

数学的ツールの準備 Bregman Divergence: D R

定理 OMD2

パーセプトロン (Perceptron)  FoReL から導出された Online Gradient Descent の例としてパーセプトロンを紹介する。  パーセプトロンは F. Rosenblatt が 1956 年に提案 した線形識別の繰り返しアルゴリズム  効率がよく、現在でもその価値が高い  入力 x t が目的のクラスに  属する場合に y t =1, 属さない場合に y t = −1  右図 

Perceptron アルゴリズム 分類に失敗し たときだけ そのデータを分類器 W に足 し込むという至って単純な 更新

線形分離可能性  線形分離可能：クラスを識別するする超 平面が存在する場合  そうでない場合を線形分離不可能という。  下図参照 線形分離可能 線形分離不可能 γ ：マージ ン

Perceptron アルゴリズムの分析 FoReL の別形式として導入した Online Mirror Descent とみれば、 (OMD20) の上界が使える

Perceptron アルゴリズムの分析

Passive Aggressive Algorithm  K.Crammer et.al. Online Passive-Aggressive Algorithms Journal of Machine Learning Research 7 (2006) 551–585  識別（あるいは分類）の問題設定  round t で n 次元データ が到着  の正負は のように 与えられる  重みベクトル :  正しい（誤った）判定：  w t はデータが到着するたびに更新されている

損失関数による定式化  境界面そのもので判定はきわどいのでマ ージンを持たせる。マージンを 1 とした場 合の損失関数 (hinge-loss function) は以下 の通り  この設定で、 round t の更新は次の条件付き 最適化問題となる。 0 1

FoRe Ｌとして見ると

最適化問題（ PA-1) を解く  If l t =0 then w t minimizes w t+1 =w t  If l t ≠0 then Lagrange 未定乗数法で解く。 Passive Aggressive

Passive Aggressive xtxt Passive xtxt Aggressive

soft margin の学習法 PA-I, PA-II

Passive Aggressive Algorithm

付録： PA-I の導出

付録： PA-II の導出

損失の限界の評価

Proof

 Theorem 2 では次の制約が厳しい。  この制約は、 u で完全な識別ができること。  この制約を外す定理を考える Proof は次ページ

Proof

Proof は次のページ PA-I における入力データ識別の失敗回数の上限

PA-II における累積損失の上限 Proof は次のページ

Confidence Weighted Algorithm Crammer et al. 2008

学習する重みベクトル W を点ではなく分布（正規分布）にす る  W の期待値と分散を更新する

Pegasos ： Primal Estimated sub-GrAdientSOlver for SVM  L2 正則化＋ L1 損失の SVM  Pegasos の更新は次式による  更新の後、 w を半径 の球に project  以上を収束するまで繰り返す。データ集合 A ご となので、 online というよりは mini-batc ｈ

Pegasos ： Primal Estimated sub-GrAdient SOlver for SVM のアルゴリズム

f (w) の評価

Lemma1 を拡張するとさらに強力な次の定理が得られる。 詳細は： Mathematical Programming 127(1), 2011, pp.3-30 Pegasos:primal estimated sub-gradient solver for SVM. Shai Shalev-Schwarts, et.al.

ここの導出は初等的が だちょっとした計算

ここで双対問題を思 いつくところがいか にも SVM 的

強双対定理の実に 賢い使い方だ

Coordinate Descent C.-J. Hsieh, et.al. ICML2008  Target: L1 損失 - L2 正則化の SVM 双対化 して解く。下に定義

Coordinate Descent  Coordinate Descent は順番に 1 変数づつ選 び、他の変数は固定して最適化。

Coordinate Descent つづき  (CD10) の Q ii は α i の最適化の中で 1 回計算すれ ばよいが 

L1 損失 -L2 正則化の SVM の Coordinate Descent アルゴリズ ム

オンライン学習とストリーム学習 学習正解との比較 モデル１データづつ 到着データのモ デル学習 と分類などの結 果 学習結果 １データづ つ モデル データ 発生 オンライン学習 ストリーム学 習

バッチ、オンライン、ストリームの比 較 バッチ学習オンライン学習ストリーム学習 メモリに乗せるデー タ 同時に全部同時には 1 デー タ メモリ量大小でも可能小 データの到来全データが揃って から処理 1 データ到着ごとに処 理 データの消去消去せず データは処理後に消 去 同一データの処理 回数 収束するまで繰り 返し 1回1回 メモリに保持する モノ 全データと途中に 内部状態 内部状態のみで も可能 内部状態のみ 性能精度高バッチより劣る。 ただし、最近は バッチに肉迫 劣る 可能な処理何でもありやや制限あり限定的

捕捉：世の中、ビッグデータがホットだと言う けれど ？ ？ ？ ？ ？ ？ 異なる分類のデータ ？ ？ ？ ？ 分類されていない生のデータ

パーセプトロンの別のアルゴリズ ム という識別に失敗したデー タに、その値を重み（学習率と呼ぶ） η で w に足しこんで是正 を図るアルゴリズム この部分が線形識別

パーセプトロンは有限回で収束  mistake の upper bound Novikoff の定理 ( バイアスのない場合 ）

証明

メモリ容量より大きなデータの SVM Hsiang-Fu Yu et.al KDD2010 主問題の場合は Pegasos, 双対問題の場合は Coordinate Descent （ＣＤ）をブロックごとに適 用 ここが重要

主問題を Pegasos で解く場合の 6. の部 分

双対問題で Coordinate Descent （ＣＤ）を使う 場合

双対化の御利益： 教師データアクセスの観点か ら  主問題と双対問題は最適化するパラメタ －数が違う。  主問題パラメタ－数 >> 双対問題パラメタ－数 なら双対問題を解くほうが楽  教科書的  SVM の場合：  主問題のパラメタ－は重みベクトル :w  双対問題にパラメタ－は個別データ :x i  必ずしも教科書的なお得感ではない。

双対化の御利益  SVM の場合：  主問題のパラメタ－は重みベクトル :w  下の定式化なので、全教師データ {t n,x n } が同 時に必要  データ量が大きくメモリにロード仕切れ ない場合に困ったことになる。  データ量は最近、増加傾向

双対化の御利益  必ずしも教科書的なお得感ではない。  一方、双対問題では入力データ x i t i のと最適化する a i が対 応する形で最適化式に現れるので、どのデータを学習で 使うか制御しやすい。（下の式参照）  例えば、 a i (i≠j) を固定して、 a ｊ を最適化する操作を j を動かして 繰り返すなど。そのときには だけしか使わな い。

双対化の御利益  入力データ、あるいはカーネル行 列全体がメモリに乗り切らないビ ッグデータを扱うために、入力（ すなわちカーネル k ( x n, x m ) の一部 を取捨選択してメモリにロードし て使う方法が、この双対化で可能 になっている。  ビッグデータ時代における御利 益  cf. 台湾大学の LIBSVM （ SVM の実装）  全データからどのようにメモリにロードす る部分を切り出すかについてはここで紹介 した通り。 k ( x n, x m ) M N この部分だけ 使って最適化： 次に使う部分 ロードし直して 最適化：繰り返 す

内外のバランス など  内側の繰り返しで最適化でＣＤにおいて α の更新を 1 回にし、 loose な解を求めると、 外側の繰り返しが多数回必要  内側の繰り返しで精密な最適化を行えば 、外側の繰り返しは少なくてよい。  Bj{j=1,..,m} 内の要素の最適化処理におけ る順番は外側の繰り返し毎にランダムに 変更した方が収束が早い

小さなブロックに分けてデータマイニング、機 械学習 ？ ？ ？ ？ ？ ？ ブロックをメモリに順次ロードして学習し、その結 果を活用して次のブロックへ と繰り返す： 例えば Stream SVM

転移学習 ？ ？ ？ ？ ？ ？ 異なる分類のデータ ？ ？ ？ ？ 分類されていない生のデータ この分類での学習 の結果を別のグ ループに転移して 有効利用

人間に正解をつけてもらうデータを絞り込む： Active 学習 ？ ？ ？ ？ ？ ？ 異なる分類のデータ ？ ？ ？ ？ 分類されていない生のデータ 分類しにくい 部分のデータ

付録： Duality による FoReL の定式 化

Online Mirror Descent:OMD

パーセプトロンの別のアルゴリズ ム という識別に失敗したデー タに、その値を重み（学習率と呼ぶ） η で w に足しこんで是正 を図るアルゴリズム この部分が線形識別

w(k) w(k+1)

パーセプトロンは有限回で収束  mistake の upper bound Novikoff の定理（バイアスのある場 合）

証明

証明 つづき