Download presentation
Presentation is loading. Please wait.
1
オンライン学習 定式化 評価法： Regret など パーセプトロン Passive Aggressive Algorithm ( アルゴリズムと損失の限界の評価） Confidence Weighted Algorithm Pegasos Coordinate Descent バッチ、オンライン、ストリームの 比較 ビッグデータへの対応
2
オンライン（あるいは逐次）学習と は データを１つづつ読み込んで、それまでの学習 結果を更新する。 2 つの利用局面 1. データ全体は保持しているが、学習を 1 データ毎に 行う 2. データが１こずつ時系列としてやってくる この場合はストリームという。 データ全体をメモリの乗せなくてよいのでマシ ンに必要なメモリ少、あるいはメモリに乗りき らないほど大きなデータから学習可能 1 個のデータからの学習（これを 1round という） だけなら高速
3
オンライン学習の概観
4
識別関数 h (t) データ xtxt 正解（実測 あるいは人 手による） ytyt 予測 h (t) (x t ) If 予測 ≠ 正解 then 更新： h (t) →h (t+1) オンライン学習のイメージ
5
オンライン学習の評価法 仮説 h のなす空間を H, t ラウンドの予測値を h (t) (x t ) 累積損失 （最小化し たい）： Mistake( 失敗回数）の upper bound 以後は識別に失敗しなくなるまでの学習回数＝ 学習データ数
6
オンライン学習をオンライン凸最適化の観点から定 式化 By Shai Shalev-Shwartz 以下では L (w,(x i, y i )) を fi (w) と略記することに留意。 最も簡単なオンライン学習は、過去の全 round の損失を 最小化するような w を選ぶ方法： Follow-The-Leader(FTL)
8
Follow-The-Regularized-Leader (FoReL) FTL ではｗに制約がないので、過学習が危ぶま れる。そこで、正則化項 (Regularizer) を加えた ものを最適化（ FoReL)
9
Example of FoReL: Online Gradient Descent: OGD
10
FoReL の Regret の Upper Bound Theorem 30
11
損失 f が連続でない場合 Sub-gradient( 劣勾配）の FoReL f の凸性が重要
12
Sub-gradient の場合の FoReL の Regret Bound 問題はこの部分
14
FoReL の上界を厳しくする まず、 FoReL の別形式を導入する Online Mirror Descent (OMD) という
15
数学的ツールの準備 Fenchel-Young 不等式
16
数学的ツールの準備 Bregman Divergence: D R
18
定理 OMD2
19
パーセプトロン (Perceptron) FoReL から導出された Online Gradient Descent の例としてパーセプトロンを紹介する。 パーセプトロンは F. Rosenblatt が 1956 年に提案 した線形識別の繰り返しアルゴリズム 効率がよく、現在でもその価値が高い 入力 x t が目的のクラスに 属する場合に y t =1, 属さない場合に y t = −1 右図
21
Perceptron アルゴリズム 分類に失敗し たときだけ そのデータを分類器 W に足 し込むという至って単純な 更新
22
線形分離可能性 線形分離可能：クラスを識別するする超 平面が存在する場合 そうでない場合を線形分離不可能という。 下図参照 線形分離可能 線形分離不可能 γ ：マージ ン
23
Perceptron アルゴリズムの分析 FoReL の別形式として導入した Online Mirror Descent とみれば、 (OMD20) の上界が使える
24
Perceptron アルゴリズムの分析
25
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 はデータが到着するたびに更新されている
26
損失関数による定式化 境界面そのもので判定はきわどいのでマ ージンを持たせる。マージンを 1 とした場 合の損失関数 (hinge-loss function) は以下 の通り この設定で、 round t の更新は次の条件付き 最適化問題となる。 0 1
27
FoRe Ｌとして見ると
28
最適化問題（ PA-1) を解く If l t =0 then w t minimizes w t+1 =w t If l t ≠0 then Lagrange 未定乗数法で解く。 Passive Aggressive
29
Passive Aggressive xtxt Passive xtxt Aggressive
30
soft margin の学習法 PA-I, PA-II
31
Passive Aggressive Algorithm
32
付録： PA-I の導出
34
付録： PA-II の導出
35
損失の限界の評価
36
Proof
39
Theorem 2 では次の制約が厳しい。 この制約は、 u で完全な識別ができること。 この制約を外す定理を考える Proof は次ページ
40
Proof
41
Proof は次のページ PA-I における入力データ識別の失敗回数の上限
43
PA-II における累積損失の上限 Proof は次のページ
45
Confidence Weighted Algorithm Crammer et al. 2008
46
学習する重みベクトル W を点ではなく分布（正規分布）にす る W の期待値と分散を更新する
47
Pegasos ： Primal Estimated sub-GrAdientSOlver for SVM L2 正則化＋ L1 損失の SVM Pegasos の更新は次式による 更新の後、 w を半径 の球に project 以上を収束するまで繰り返す。データ集合 A ご となので、 online というよりは mini-batc ｈ
48
Pegasos ： Primal Estimated sub-GrAdient SOlver for SVM のアルゴリズム
49
f (w) の評価
51
Lemma1 を拡張するとさらに強力な次の定理が得られる。 詳細は： Mathematical Programming 127(1), 2011, pp.3-30 Pegasos:primal estimated sub-gradient solver for SVM. Shai Shalev-Schwarts, et.al.
53
ここの導出は初等的が だちょっとした計算
54
ここで双対問題を思 いつくところがいか にも SVM 的
55
強双対定理の実に 賢い使い方だ
56
Coordinate Descent C.-J. Hsieh, et.al. ICML2008 Target: L1 損失 - L2 正則化の SVM 双対化 して解く。下に定義
57
Coordinate Descent Coordinate Descent は順番に 1 変数づつ選 び、他の変数は固定して最適化。
58
Coordinate Descent つづき (CD10) の Q ii は α i の最適化の中で 1 回計算すれ ばよいが
59
L1 損失 -L2 正則化の SVM の Coordinate Descent アルゴリズ ム
60
オンライン学習とストリーム学習 学習正解との比較 モデル１データづつ 到着データのモ デル学習 と分類などの結 果 学習結果 １データづ つ モデル データ 発生 オンライン学習 ストリーム学 習
61
バッチ、オンライン、ストリームの比 較 バッチ学習オンライン学習ストリーム学習 メモリに乗せるデー タ 同時に全部同時には 1 デー タ メモリ量大小でも可能小 データの到来全データが揃って から処理 1 データ到着ごとに処 理 データの消去消去せず データは処理後に消 去 同一データの処理 回数 収束するまで繰り 返し 1回1回 メモリに保持する モノ 全データと途中に 内部状態 内部状態のみで も可能 内部状態のみ 性能精度高バッチより劣る。 ただし、最近は バッチに肉迫 劣る 可能な処理何でもありやや制限あり限定的
62
捕捉：世の中、ビッグデータがホットだと言う けれど ？ ？ ？ ？ ？ ？ 異なる分類のデータ ？ ？ ？ ？ 分類されていない生のデータ
63
パーセプトロンの別のアルゴリズ ム という識別に失敗したデー タに、その値を重み（学習率と呼ぶ） η で w に足しこんで是正 を図るアルゴリズム この部分が線形識別
64
パーセプトロンは有限回で収束 mistake の upper bound Novikoff の定理 ( バイアスのない場合 ）
65
証明
66
メモリ容量より大きなデータの SVM Hsiang-Fu Yu et.al KDD2010 主問題の場合は Pegasos, 双対問題の場合は Coordinate Descent （ＣＤ）をブロックごとに適 用 ここが重要
67
主問題を Pegasos で解く場合の 6. の部 分
68
双対問題で Coordinate Descent （ＣＤ）を使う 場合
69
双対化の御利益： 教師データアクセスの観点か ら 主問題と双対問題は最適化するパラメタ －数が違う。 主問題パラメタ－数 >> 双対問題パラメタ－数 なら双対問題を解くほうが楽 教科書的 SVM の場合： 主問題のパラメタ－は重みベクトル :w 双対問題にパラメタ－は個別データ :x i 必ずしも教科書的なお得感ではない。
70
双対化の御利益 SVM の場合： 主問題のパラメタ－は重みベクトル :w 下の定式化なので、全教師データ {t n,x n } が同 時に必要 データ量が大きくメモリにロード仕切れ ない場合に困ったことになる。 データ量は最近、増加傾向
71
双対化の御利益 必ずしも教科書的なお得感ではない。 一方、双対問題では入力データ x i t i のと最適化する a i が対 応する形で最適化式に現れるので、どのデータを学習で 使うか制御しやすい。（下の式参照） 例えば、 a i (i≠j) を固定して、 a ｊ を最適化する操作を j を動かして 繰り返すなど。そのときには だけしか使わな い。
72
双対化の御利益 入力データ、あるいはカーネル行 列全体がメモリに乗り切らないビ ッグデータを扱うために、入力（ すなわちカーネル k ( x n, x m ) の一部 を取捨選択してメモリにロードし て使う方法が、この双対化で可能 になっている。 ビッグデータ時代における御利 益 cf. 台湾大学の LIBSVM （ SVM の実装） 全データからどのようにメモリにロードす る部分を切り出すかについてはここで紹介 した通り。 k ( x n, x m ) M N この部分だけ 使って最適化： 次に使う部分 ロードし直して 最適化：繰り返 す
73
内外のバランス など 内側の繰り返しで最適化でＣＤにおいて α の更新を 1 回にし、 loose な解を求めると、 外側の繰り返しが多数回必要 内側の繰り返しで精密な最適化を行えば 、外側の繰り返しは少なくてよい。 Bj{j=1,..,m} 内の要素の最適化処理におけ る順番は外側の繰り返し毎にランダムに 変更した方が収束が早い
74
小さなブロックに分けてデータマイニング、機 械学習 ？ ？ ？ ？ ？ ？ ブロックをメモリに順次ロードして学習し、その結 果を活用して次のブロックへ と繰り返す： 例えば Stream SVM
75
転移学習 ？ ？ ？ ？ ？ ？ 異なる分類のデータ ？ ？ ？ ？ 分類されていない生のデータ この分類での学習 の結果を別のグ ループに転移して 有効利用
76
人間に正解をつけてもらうデータを絞り込む： Active 学習 ？ ？ ？ ？ ？ ？ 異なる分類のデータ ？ ？ ？ ？ 分類されていない生のデータ 分類しにくい 部分のデータ
77
付録： Duality による FoReL の定式 化
78
Online Mirror Descent:OMD
80
パーセプトロンの別のアルゴリズ ム という識別に失敗したデー タに、その値を重み（学習率と呼ぶ） η で w に足しこんで是正 を図るアルゴリズム この部分が線形識別
82
w(k) w(k+1)
83
パーセプトロンは有限回で収束 mistake の upper bound Novikoff の定理（バイアスのある場 合）
84
証明
85
証明 つづき
Similar presentations
