THE UNIVERSITY OF TOKYO

数理情報工学特論第一【機械学習とデータマイニング】
2章：回帰（３）

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

DEPARTMENT OF MATHEMATICAL INFORMATICS

1THE UNIVERSITY OF TOKYO

教師つき学習の王道である「回帰」について学びます

回帰問題の定義

線形回帰問題の定式化



線形回帰問題の初等的解法



リッジ回帰：L2正則化による過学習の回避

交差確認によるハイパーパラメータの決定–2

Leave-one-out交差確認

回帰問題の確率モデル的解釈

回帰の応用

カーネル回帰L1正則化

THE UNIVERSITY OF TOKYO回帰の重要な応用

3

THE UNIVERSITY OF TOKYO線形回帰の自明でない使い方を2つ紹介します 時系列予測 分類

4

THE UNIVERSITY OF TOKYO

時系列予測 線形回帰の1つの使い方として、時系列予測に用いることができる 時系列とは、時刻 t =1,2,… に関連づけられた、実数値の列 x1, x2, … ( xt 2 R ) 時系列予測の目的は、ある時刻tにおける時系列の値 xt 2 R をそれ以前の値 x1, x2, …, xt-1 から予測すること
 時系列予測のための代表的モデルの1つが、自己回帰モデルもしくはAR(Auto Regressive)モデルと呼ばれるモデル
 D次の自己回帰モデル：– ある時刻tにおける値は、過去D時点分の値から決まる– モデルのパラメータは (w1,w2,…,wD)
5

THE UNIVERSITY OF TOKYO自己回帰モデルの学習は、線形回帰としてみることができます D次の自己回帰モデルは、
 これは、特徴ベクトルを (xt-1, xt-2,…, xt-D) 、パラメータを(w1, w2,…,wD)と考えれば、まさに線形回帰のモデル
 時刻1から時刻T までの時系列の値 x1, x2, …, xT が不えられたときに時刻T+1の値を予測したいものとする

 時刻T までの時系列 x1, x2, …, xT から長さD+1の窓をずらしながらT-D 個の訓練データを作ることができる。
 これらから、線形回帰の方法を用いてパラメータ wを推定し、それをもとに xT を予測する。
 時系列予測については、より詳細なモデルや特化した解法がある
6

THE UNIVERSITY OF TOKYO回帰で分類問題を解く
 回帰を用いて分類問題（例えば、2値分類 y 2 {+1,-1} の場合）を解く
 便宜的に各訓練データの出力を y(i) 2 {+1,-1}として回帰を適用する– 予測時には、f (x; w) が0以上の値であるなら出力「 +1」、そうでないならば 「-1」として予測する 出力は+1か-1のどちらかなので、回帰の仮定（出力にガウス的ノイズが入る）は成立せず、このような適用は厳密には尐しおかしい 分類問題をより適切にモデル化する方法は複雑になるため、分類問題を手軽に扱えるという意味で、このやり方は妥協に値する。
 なお、実際は訓練データの出力を y(i) 2 {+1,-1}とするのではなく、y(i) 2{+1/|N+|}, -1/|N-|}としたほうがよい– 出力が+1の訓練データの数を|N+|、出力が-1の訓練データの数を|N-|– フィッシャー判別に対応
7THE UNIVERSITY OF TOKYO

カーネル回帰8THE UNIVERSITY OF TOKYO

データ数よりも次元数が大きい場合の回帰：
データ数に依存した計算量にすることができます リッジ回帰の解は、以下で不えられた これは次元数£次元数（D £ D）の行列の逆行列計算（もしくは連立方程式の解）が必要– O(D3)

 もしも（訓練データ数 N と比較して）次元数Dが大きい場合にはどうしたらよいだろうか？
 実は、計算量が訓練データ数に依存するように問題を変換することができる– O(N3)
9THE UNIVERSITY OF TOKYOここで便利なのが、ウッドベリーの公式です：
逆行列計算のサイズを小さくできることがあります ウッドベリー(Woodbury)の公式：– シャーマン・モリソンの公式の一般化になっている• C ≡ Iとして、UとVをベクトルとするとシャーマン-モリソンに一致する
 重要なポイントは：– LOOCVのときと同じくA-1 が出てくるところ– UとVが縦長の行列の場合、右辺のほうが逆行列のサイズが小さいところ
10THE UNIVERSITY OF TOKYO

ウッドベリーの公式を用いると、リッジ回帰の計算量をO(D3) → O(N3) （次元の3乗からデータ数の3乗）にできます ウッドベリーでA ≡ ¸ I、U ≡ V ≡ ©>、C ≡ Iとおいてみると、リッジ回帰の解における逆行列の部分を以下のように書き直せる– 左辺ではD £ Dの逆行列計算が、右辺ではN £ Nの逆行列計算• 両辺で逆行列の中の ©と©>の順序が逆になっていることに注意– つまり、D > N のときには、右辺のほうが計算量的に有利
 右辺に出てくる行列 ©©>はグラム行列と呼ばれ、その各要素は訓練データの特徴ベクトル間の内積になっている
 これはまさにカーネル法におけるカーネル関数であり、我々は「ウッドベリーの公式を用いてカーネルリッジ回帰を導いた」
11THE UNIVERSITY OF TOKYOL1正則化12THE UNIVERSITY OF TOKYOL1正則化は、疎な解を不えるため、L2正則化と並び重要な正則化のひとつです 1-ノルムを用いた正則化はL1正則化と呼ばれる– L2正則化と並び、よく利用される
 L1正則化を用いた時の線形回帰の目的関数：
 L1正則化は「疎な解」を不える– 目的関数を最小化する w* において、多くの次元が丁度0になる– 特徴ベクトルÁの次元が非常に高く、その一方で、実際に予測に有用な特徴が尐ない場合に特に有効– 学習済みのモデルを用いて予測を行う際、予測の計算量は w の 0 でない次元数に依存する
13

THE UNIVERSITY OF TOKYOL1正則化を用いた場合には（L1正則化の場合と違い）最適化問題の解が閉じた形では求まりません L1正則化を用いた回帰における最適化問題は、リッジ回帰のときと異なり、解が閉じた形で求まらないため、その解法は複雑になる– L2正則化を用いた回帰（リッジ回帰）の解 以降、2つの比較的簡単な方法を見ていくことにする– 方法1: 次元ごとの逐次解法– 方法2: L2正則化への帰着

14

THE UNIVERSITY OF TOKYO方法1: 次元ごとの逐次解法
1つのパラメータに注目した最適化を繰り返します L1正則化項は：– 原点で微分できない– 原点が最適解となる場合が多いという問題があり、扱いづらい パラメータ w =(w1, w2, …, wD)の、ある特定の次元 wd に注目すると目的関数の最小化は簡単に行える
 そこで、
1. 次元dを適当に選ぶ

2. パラメータwd についての最適化を行うを、収束するまで繰り返すアルゴリズムを考える
15THE UNIVERSITY OF TOKYOある次元のパラメータ（wd ）に注目した目的関数を考えます i番目のデータに対するモデルの予測は、パラメータの d 次元目 wd を特別扱いすれば：
 目的関数を wd についての関数であると思えば：– 残りのwj ( j ≠d )は定数であると思う 最後の項は wd に関係ないので無視すると、最小化問題は：

16

THE UNIVERSITY OF TOKYOひとまずは、正則化項を無視して解いてみます 以下の1変数最小化問題を解きたい– 厄介なのが最後の項 ¸ |wd|
– この項はwd = 0 において、微分が定義されないために、単純に目的関数の微分を取って 0 とおいて…という方法が使えない ひとまず、最後の項を無視して：を解いてみると、この解は簡単に求まり：

17

THE UNIVERSITY OF TOKYO

正則化ナシの解を使って、目的関数を書き換えてみます これを用いて損失関数の部分を書き換えてみると、– 定数項は最小化に関係ないので無視した

 ここで、今後の表記を簡単にするためにとおく γ を使って目的関数を書きなおすと：

18

THE UNIVERSITY OF TOKYO

目的関数の微分を考えてみます（場合分け）の微分を計算してみると– wd = 0 のとき：
• |wd|が微分できないため定義されない– wd > 0 のとき：
• 傾き1で切片が– wd < 0 のとき:の一次関数• 傾き1で切片がの一次関数

 これが 0 になる wdを探す
19

THE UNIVERSITY OF TOKYO求まった解を見てみると、確かに「疎」な傾向が見えてきます グラフが 0 と交わる wd を探す 場合1：

すなわちのときには解は 場合2：

すなわちのときには解は 場合3：のとき–とするととなり矛盾–とするととなり矛盾– 解は必ず存在するので、従ってでないと困る
 場合3を見ると、正則化ナシの解が0に近いところでは、L1正則化の解が 0 になる（→ 疎になる）
20

THE UNIVERSITY OF TOKYO

方法2: L2正則化（リッジ回帰）への帰着
簡単に解けるリッジ回帰の繰り返し解法に変換します L1正則化項を直接扱うのは若干煩雑

 一方、L2正則化を用いた回帰（リッジ回帰）は、逆行列の計算によって求まるのでシンプル

 そこで、L1正則化による回帰（ラッソ回帰）を、リッジ回帰の繰り返しによって解く方法を考える
 ポイントは、L1正則化項の上界を、L2正則化項を用いて作るところ– その代償として、パラメータが 2倍に増える

21

THE UNIVERSITY OF TOKYOL1正則化項の上界を、相加相乗平均によって作ります d 次元目についての正則化項 |wd| の上界を以下のように求める。

 新たなパラメータ ¯d ¸0 が導入されていることに注意 最後の丌等号は相加相乗平均、すなわち a, b ¸ 0について

22THE UNIVERSITY OF TOKYO

できた上界はL2ノルムで書かれていることが分かります（パラメータの数は増えてしまいます）
 L1正則化項 の上界は： 特筆すべきは、上界においては各パラメータの2乗が現れるため、微分丌可能な点が無くなっている点
 新たなパラメータ ¯ ≡ (¯1, ¯2, …, ¯D) を導入したことにより、wと併せて、モデルパラメータの数は D から 2D に増加
 従って、左辺の ||w||1を w について最小化するかわりに、右辺を wと ¯ の両方について最小化することになる

23THE UNIVERSITY OF TOKYO

増えたパラメータをまとめて最適化する必要があります L1正則化を用いた時の線形回帰の目的関数はの上界を作ると： 最適なパラメータ(w*, ¯*)は、によって求まることになる

24THE UNIVERSITY OF TOKYOアルゴリズム： w と ¯ の推定を交互に行います アルゴリズムとしては、以下の2ステップを繰り返すA) （¯を現在の値で固定しておいて）w についての最小化B) （wを現在の値で固定しておいて）¯ についての最小化

25

THE UNIVERSITY OF TOKYO

ステップ A：¯ についての最小化は簡単です wを固定したうえで、¯ についての最小化を行う
 相加相乗平均の等号が成り立つのは、a=bのときである したがって、¯d = wd2 /¯d のとき、すなわち ¯d = |wd| のときに上界は最小化される

26

THE UNIVERSITY OF TOKYO

ステップ B：wについての最小化はリッジ回帰によって行えます 目的関数はと置く• diag(・)は、引数のベクトルを対角成分に持つような行列•を新たなデザイン行列と見ることによって、てのリッジ回帰として捉えることができる

27についについて最適化を行い、w に戻せば、THE UNIVERSITY OF TOKYO