THE UNIVERSITY OF TOKYO

数理情報工学特論第一【機械学習とデータマイニング】
3章：分類④

かしま ひさし鹿島 久嗣（数理 6 研）kashima@mist.i.～

DEPARTMENT OF MATHEMATICAL INFORMATICS

1THE UNIVERSITY OF TOKYO

分類におけるL1正則化と、データ間の関係の予測について学びます

分類におけるL1正則化



データ間の関係の予測– データの組に対する予測– 行列パラメータをもつモデル– トレースノルム正則化を用いた学習

2

THE UNIVERSITY OF TOKYO

分類におけるL1正則化

3

THE UNIVERSITY OF TOKYO

分類の場合でもL1正則化は有効です 回帰の場合と同じく、分類の場合にも、L1正則化によって、疎なパラメータを得たい場合が多々ある– パラメータwの1-ノルム：をペナルティ項として小さくすることで、多くのwdが0になる効果 特に、データ数と比較して、特徴ベクトルの次元が高いような場合– 文書分類：文書中に出現する単語を用いた特徴ベクトル（bag-ofwords）表現がしばしば用いられる– マイクロアレイ診断：各遺伝子の発現量を、患者の特徴ベクトルとして用いる
 これは数千～数十万次元にもなりうるため、大幅な次元削減が必要になることがある
4THE UNIVERSITY OF TOKYO

分類の場合は、パラメータの最適解を閉じた形で得るのは難しいのでパラメータ徐々に改善する方式をとります L1正則化を用いた場合の目的関数：

 分類問題の場合、この解を閉じた形で得るのは困難であるので、パラメータw(t) からw (t+1) への更新によって、解を徐々に改善していく 更新量¢(t) は目的関数 L をなるべく大きくするように決定する

5

THE UNIVERSITY OF TOKYO

目的関数を対数尤度の項と正則化の項にわけて考えます 目的関数：において、対数尤度の和の部分をとおき、目的関数を対数尤度の和と正則化に分けと書くことにする 目指すのは以下を満たす¢：
6

THE UNIVERSITY OF TOKYO対数尤度の項をテーラー展開します L(w(t)+¢) = J(w(t)+¢) - ¸||w(t)+¢||1 を評価したい 対数尤度の項 J(w)を、現在のパラメータw(t)の周りで2次までのテーラー展開により近似してみると：– r(w(t))： J(w) の勾配– H(w(t))： J(w) のヘッセ行列

7THE UNIVERSITY OF TOKYO

ヘッセ行列を単位行列で置き換えることで、最急勾配法
 ヘッセ行列 H(w(t)) の代わりにH(w(t)) ≡ - 1/η(t) Iと置き換えると、– η(t)：適当な正の定数（学習率）
 この近似は、J(w(t+1)) を一次近似するが、その近似精度は w(t+1) がw(t)から離れるにつれ悪くなる なるべく現在のw(t)から離れないようにしようと働く項：－1/2η(t) ・¢>¢ = －1/2η(t) ||¢||22（すなわち、更新量の2ノルム）を、ペナルティ項として入れていると解釈することもできる

8THE UNIVERSITY OF TOKYO

目的関数の最適化は次元ごとに行うことができます 目的関数は以下のように書くこともできる：

 L1回帰のときと同じように、各次元 d ごとに分けて最大化を考えることができる
 つまり、目的関数を¢ の各次元¢ d について最大化：を行うことで最適な更新量¢ d (t) を各次元独立に得ればよい

9THE UNIVERSITY OF TOKYO

整理すると、L1正則化回帰のときに出てきた形式が現れます 次元ごとの最適化問題：

 を整理し、定数部分を無視すると：

 さらにこれは更新式の定義から：– どこかで見たことある形がでてくる
10

THE UNIVERSITY OF TOKYOL1正則化回帰のときには場合分けで解が決まるのでした 目的関数：

は、ちょうどL1回帰の次元ごとの解法を導いたとき出てきた形式であり、このときと同じ方法を用いることができる。
 L1回帰における次元ごとの目的関数を思い出してみると：

 このときの解は：–ならば解は–ならば解は–11

ならばTHE UNIVERSITY OF TOKYO我々の場合（L1正則化分類）も場合わけで解が求まります 2つの目的関数の間の対応関係：––
 我々の問題の解は：12THE UNIVERSITY OF TOKYOL1正則化分類のアルゴリズムは、最急勾配法と（ある種の）丸め操作の繰り返しと見ることができます 前述の場合分けは、ある種の丸め操作であり、wd(t) + η(t)rd(wd(t)) が0に近いときには解は0に丸められ、そうでない場合にも一定量だけ0に向かって引き戻されるように働く この場合分けの条件に入っている wd(t) + η(t)rd(wd(t)) は、まさに最急勾配法の更新式と同じ形をしている
 従って、アルゴリズムとしては：– 最急勾配法によってパラメータを更新したあとに– そのパラメータの値に応じて丸め操作を行うという2段階のパラメータ更新を繰り返し行っていると解釈できる

13

THE UNIVERSITY OF TOKYOL1正則化分類のアルゴリズム
 以下の2ステップを繰りかえす
1. 最急勾配法を適用し、中間的な解を得る。

1. 以下の丸め操作によって新しいパラメータ14を得る

THE UNIVERSITY OF TOKYOデータの組に対する予測

15

THE UNIVERSITY OF TOKYO

分類問題の一般化として、2つ（複数）の入力をもつ分類問
題を考えます これまでは入力xに対して出力yを予測するという一対一の関係を扱っていた
 時によって2つの入力xとx0の組（より一般的にはm個の入力）に対して出力yを予測したい場合がある
 例：ネットワーク構造の予測問題– ネットワーク構造のリンク構造が部分的に不えられた（いくつかのノード対に関して、それらの間にリンクがあるかないかという情報が不えられた）ときに、残りの部分についてのリンク構造の予測を行う問題• タンパク質の相互作用予測：2つのタンパク質（データ）の間に物理的な相互作用（チームで働くなど）があるかを予測• 購買予測：顧客と商品の間の購買関係を予測
16

THE UNIVERSITY OF TOKYO2つの入力をもつ条件付き分布を推定する問題を考えます リンク予測の一番シンプルな捉え方：2つのノードの2クラス分類– 2つのノードx とx0 に対し、それらの間にリンクが存在する（+1）
かしないか（-1）をクラスラベルとする

 つまり、2つの入力データが不えられた時の、出力の条件付き分布
P(y| x, x0)を推定する
 x と x0 は同じ集合X に属していても良いし、別々のノード集合に属して（xは集合X に、x0は集合X 0に属する）もよい– X を顧客の集合、X 0を商品の集合とすると、ある顧客 x∈ X がある商品x0∈ X 0を購入するかどうかを予測するというマーケティン
グの文脈での予測問題を考えることができる
 より一般的に、複数種類の関係がある場合（多クラス分類）や、数値的な関係がある場合（回帰）なども考えられる
17

THE UNIVERSITY OF TOKYO

2入力のロジスティック回帰モデルを考えます 入力の組 (x, x0) についての分類問題を解くために、入力の組が不えられた時の出力の条件付き確率P(y|x, x0)をモデル化する ロジスティック回帰モデルを2入力に拡張したモデルを考える：– ¾(z) ≡ (1+exp ( - z ) )-1 ：シグモイド関数– Ã(x, x0) ： 2つの入力 xと x0 の組み合わせに対する特徴ベクトル– w：パラメータベクトル

 通常のロジスティック回帰との違いは、特徴ベクトルが2つの入力の組み合わせに対して定義されているところ
 2つの入力それぞれの特徴ベクトルÁ(x) およびÁ(x0) が予め不えられているものとして、これらを利用してÃ(x, x0)を設計することが重要
18

THE UNIVERSITY OF TOKYO

組み合わせ特徴ベクトルの定義として良く用いられるのは2つの入力それぞれの特徴の組み合わせを用いる表現です 2つの入力ペアに対する特徴ベクトル Ã(x, x0) をそれぞれの特徴ベクトルÁ(x) および Á(x0) の特徴の組み合わせで構成する
 つまり、Á(x) および Á(x0) の次元がそれぞれDおよびD 0 であるとする
ときに、これらの間の D D 0 個の組み合わせ特徴を定義する：– - はクロネッカー積と呼ばれる演算子– 要素ごとに書けば Ã(i-1)D’+ j (x, x0) ≡ Ái (x) Áj (x0)19

THE UNIVERSITY OF TOKYO一旦特徴ベクトルが定義できれば、あとはこれまでと同じように学習を行うことができます 訓練データ集合：– 各訓練データを2つの入力の組(x(i), x’(i))と対応する出力y(i)とする– これをN組集めたもの{ (x(i), x’(i), y(i))}i=1N
 例えば、2-ノルムに基づく正則化（もしくは正規分布を事前分布とする事後確率最大化）を用いたとすれば、最適化問題：を解けば、最適なパラメータw*が求まる

 このモデルでは必然的に特徴ベクトルの次元は D D 0 と高くなってしまうため、パラメータを疎にするためにL1正則化を用いるのもよい
20

THE UNIVERSITY OF TOKYO行列パラメータをもつモデル

21

THE UNIVERSITY OF TOKYO

2入力のロジスティック回帰は行列を用いて表現できます 2つの入力の組に対する特徴ベクトルは、個々の入力の特徴の組み合わせで作られることから、特徴ベクトルを行列で自然に表現することができる
 つまり、 D D 0 次元の特徴ベクトルの定義の代わりに、D £ D 0の特徴行列ª(x, x0)を次のように定義する：
 これに対応して、パラメータのほうもD £ D 0の行列Wとして書くことにすると、ロジスティック回帰モデルは：– Tr は行列のトレースを表す– 上式におけるTrの中身はちょうどW と ª(x, x0) の要素ごとの積の和22

THE UNIVERSITY OF TOKYO学習の目的関数も同様に行列を用いて書き直すことができます 学習の目的関数も同じように書き直すことができる
 例えば、2-ノルムに基づく正則化の場合には、行列表現を使うと：– k・kF2 はフロベニウスノルム（行列の全ての要素の2乗和）• これは行列をベクトルだと思って2-ノルムをとったときに等しい

23

THE UNIVERSITY OF TOKYO

入力とパラメータを行列だとみなすことによって、新たな方向性が見えきます 入力行列は必ずしもベクトルのクロネッカー積による定義のようにランク1の行列である必要はなく、一般のD £ D 0の行列ª(x, x0) であるとしても問題ない– 画像は各要素が色の濃淡等を表す行列で自然に表現できる– 脳波解析などにおいて、複数の時系列に対する分類を行いたい場合、特徴の定義として、時系列間の相関係数を（対称）行列として表現することがある
 しかし、モデルを行列で表現したところで、これはベクトル表現による以前のモデルと等価であり、これらに伴う最適化問題もまた等価であるため、表現の違いによる本質的な変化はない
 入力が行列という構造をもつことが意味をもつためには、モデルの学習において行列の構造を明示的に利用する必要がある
24

THE UNIVERSITY OF TOKYO

「行列であること」を明示的に扱うためには行列の複雑さを正則化項に考慮する必要があります 入力が行列という構造をもつことが意味をもつためには、モデルの学習において行列の構造を明示的に利用する必要がある
 その行列構造をどこに入れるか？ → 正則化項に入れる

 最適化問題における正則化項であるフロベニウスノルム（2-ノルム）の代わりに、行列の複雑さを表す別の指標を考えることで、学習において行列の構造を明示的に考慮する？
25

THE UNIVERSITY OF TOKYO

行列パラメータの複雑さを測るひとつの基準は、行列のランク（階数）です 行列の複雑さの1つの指標として行列のランク（階数）が考えられる
 Wのランク：W の固有値（min {D, D 0 }個ある）を¹ ≡ (¹1(W), ¹2(W), …, ¹min {D, D’}(W) としたときの、¹ の非零要素の数

 ランクが小さいこと、つまり、固有値の集合における非零要素が尐ないことが、行列の複雑さが低いことを表す– ¹の非零要素だけを取り出して並べたベクトルを¹+と書くことにす
ると、W は以下のように分解できることが知られている：– diag(¹+) は ¹+を対角成分としてもつような対角行列– ¹+の非零要素の数をRとすると、UとVはそれぞれ D £ RおよびD 0£ Rの行列であり、ランクRが小さいほど、Wを小さな行列（UとV）で表現できることがわかる
26
THE UNIVERSITY OF TOKYO

ランクを落とすための正則化項として、行列の固有値の1-ノルムを用います 行列のフロベニウスノルムに代わる正則化項として、行列のランクR(W)を用いるのがよいという気がしてくるが、残念ながらR(W)は凸関数ではなく、最適化の観点からは正則化項に丌向きである
 そこで、ランクの代わりに固有値ベクトル ¹ の1-ノルムを用いることを考える（これは凸関数であることが知られている）
 そこで、Wの固有値ベクトル¹(W)に対するL1 正則化項を入れる：

 L1 正則化は結果として得られるパラメータの多くを0にする効果があるため、これを固有値に対して用いることによって、多くの固有値を0にし、結果として行列のランクを低くする
27

THE UNIVERSITY OF TOKYO固有値の1-ノルムを用いた正則化は、近年、盛んに利用されつつあります 行列の固有値ベクトルに対する1-ノルムはトレースノルムや核(nuclear)ノルムと呼ばれ、これを用いた正則化は、トレースノルム正則化、スペクトル正則化などと呼ばれる
 協調フィルタリングやネットワーク予測、マルチタスク学習など行
列がパラメータとして現れるに様々な場面において、近年盛んに用いられている

28

THE UNIVERSITY OF TOKYO

トレースノルム正則化を用いた学習

29

THE UNIVERSITY OF TOKYO

トレースノルム正則化を用いた学習の最適化問題はL1正則化のときと同じように2段階更新で行います 目的関数の最適化：

 例によって、現在のパラメータW(t) からW(t+1) への更新によって、解を徐々に改善していくことにする
 L1正則化のときと同じように：
1. パラメータW=W(t)における最急勾配による更新によって中間的なパラメータ を一旦得る

2. 丸め操作によって最終的な更新パラメータW(t+1)を得るという2段階の更新を繰り返す
30

THE UNIVERSITY OF TOKYO

ステップ1: （対数尤度部分についての）最急勾配法
 まず、最急勾配法によって、中間的なパラメータを計算する– r(W(t))は、目的関数の対数尤度部分：のW=W(t)における勾配（行列）であり、その(k,l) 要素の定義は：

31

THE UNIVERSITY OF TOKYO

ステップ2: ステップ1で得られた の固有値の丸め操作によって更新パラメータを得ます L1正則化のときには、中間パラメータに丸め操作を行うことで最終的なパラメータを得たが、今回の正則化項 k ¹(W)k1は固有値に対するL1ノルムであるため、 の固有値に対して丸め操作を行う
 まずの特異値分解を行う

 ¹(W)の各要素 ¹j(W) (j=1,2,…,min{D, D 0})に対して、L1正則化のときの丸め操作と同様の操作によって を得る：
纏めてベクトルとして書く

 疎になった32を用いてW(t+1) を得る：

THE UNIVERSITY OF TOKYO