過学習と正則化

Lec10

過学習と正則化

高次元モデル

▶

（例）マイクロアレイによる遺伝子活動計測

x ij :

i

j

/ y i :

▶

y = w 0 + w 1 x 1 + . . . + w 10000 x 10000

非線形モデル

▶

▶

y = w 1 x + w 2 x ² + +w 3 x ³ + · · · + w 50 x ⁵⁰

過学習（重要）

▶

パラメータ数=1 パラメータ数=2

過学習（重要）

▶

パラメータ数=10 パラメータ数=20

パラメータ数=40 パラメータ数=50

最小二乗法（復習）

▶

X

n × d

=



 

 

x 11 x 12 · · · x 1d

x 21 x 22 · · · x 2d

.. . .. . . . . .. . x n1 x n2 · · · x nd



 

  ∈ R ^{n × d} , y

n × 1

=



 

  y 1

y 2

.. . y n



 

  ∈ R ⁿ .

▶

X ^⊤ X w ˆ = X ^⊤ y ⇒ w ˆ = (X ^⊤ X ) ^{− 1} X ^⊤ y

▶

X ^⊤ X

事例数

n

d

▶ n > d

（一般に）解ける

▶ n = d

誤差が

0（完全に過学習）

▶ n < d

（一般に）解けない

n = d

事例数

n

d

▶

X

y

= 0

X

2 × 2

= [ 1 2

3 3 ]

, y

2 × 1

= [ 4

9 ]

▶

= (y − Xw) ^⊤ (y − Xw)

w = X ^{− 1} y

y − Xw = 0

E = 0

n < d

事例数

n

d

▶

X

y

1 X × 2

= [

1 2 ] , y

1 × 1

= [ 5 ]

▶

(X ^⊤ X ) ^{− 1} =

([ 1 2

] [ 1 2 ]) ^{− 1}

=

([ 1 2 2 4

]) ₋ 1

▶ n < d

^⊤ X

ここまでのまとめ

▶

▶

▶

⇔ X ^⊤ X

▶

n < d

演習問題１

▶

n = 3

X =



 1 2 4



 , y =



 2 4 3





▶

（定数項あり），２次多項式モデル（定数項あり）を学習せよ

y i = w 0 + ε i ,

y _i = w ₀ + w ₁ x _i + ε _i , y i = w 0 + w 1 x i + w 2 x ² _i ε i

▶

x，縦軸を y

▶

0

演習問題１のヒント

▶

X

X

=



 1 1 1



 ⇒ w ˆ

= (X

X

)

X

y

▶

X

X

=



 1 1 1 2 1 4



 ⇒ [ w ˆ

ˆ w

]

= (X

X

)

X

y

▶

X

X

=



 1 1 1

1 2 2

1 4 4



 ⇒



 w ˆ

ˆ w

ˆ w



 = (X

X

)

X

y

演習問題１の解答

過学習を防ぐには

▶

Feature Selection

ˆ

w = arg min

w (y − Xw) ^⊤ (y − X w) s.t. ∥ w ∥ 0 = k

ただし，

∥ w ∥ 0

w

▶

ˆ

w = arg min

w (y − Xw) ^⊤ (y − X w) s.t. w ∈ Ω ⊂ R ^d

ただし，

Ω ⊂ R ^d

d

R ^d

特徴選択

▶

d

d = 10000

y i = w 1 x i1 + . . . + w 10000 x i10000 + ε i

▶ k < d

= 4）

y i = w 6 x i6 + w 58 x i58 + w 3192 x i3192 + w 7325 x i7325 + ε i

▶

特徴選択の組み合わせ数=

( d k )

=

( 10000 4

)

= 4.16 × 10 ¹⁴

逐次特徴選択

Step 1 Step 2 Step 3

逐次特徴選択アルゴリズム（実装１）

Input:

(X, y),

k 1: t ← 1, J ← ∅

2: for t = 1, . . . , k do

3:

j t ← arg min

j ∈{ 1,...,d }\J (y − X t+1,j w ˆ t+1,j ) ^⊤ (y − X t+1,j w ˆ t+1,j )

X t+1,j := [

X t x j

] , ˆ

w t+1,j := (

X _t+1,j ^⊤ X t+1,j

) ₋ 1

X _t+1,j ^⊤ y 4:

J

J ← J ∪ { j _t } 5: t ← t + 1

6: end for

Output:

J

逐次特徴選択アルゴリズム（実装２）

Input:

(X, y),

k 1: t ← 1, P ₁ ← y, J ← ∅

2: for t = 1, . . . , k do

3:

j _t ← arg max

j ∈{ 1,...,d }\J

(y ^⊤ P _t x _j ) ² x ^⊤ _j P t x j

4:

J

J ← J ∪ { j _t } 5:

P t+1 ← P t − P _t x ^⊤ _j x _j P _t x ^⊤ _j P t x j

6: t ← t + 1

7: end for

計算量

▶

u ^⊤ v (u, v ∈ R ⁿ )

FLOP

− 1，

O (n)

▶

M v (M ∈ R ^{m × n} , v ∈ R ⁿ )

FLOP

− m,

O (mn)

▶

M N (M ∈ R ^{m × k} , N ∈ R ^{k × n} )

FLOP

2mnk − mn,

O (mnk)

逐次特徴選択の計算コスト

逐次特徴選択は計算コストが大きい

▶

O (n ³ + dn ² + d ² n)

▶

O (2n ² + dn + d ² )

大規模データに対する機械学習アルゴリズムでは実装の工夫が不可欠

演習問題２

▶

A ∈ R ^{m × k} , B ∈ R ^{k × n} ,

v ∈ R ⁿ

ABx

2

1. (AB)v 2. A(Bv)

がある．それぞれの計算方法の

FLOP

どちらが効率的であるかを議論せよ．

演習問題２の解答

過学習を防ぐには（再掲）

▶

Feature Selection

ˆ

w = arg min

w (y − Xw) ^⊤ (y − X w) s.t. ∥ w ∥ 0 = k

ただし，

∥ w ∥ 0

w

▶

ˆ

w = arg min

w (y − Xw) ^⊤ (y − X w) s.t. w ∈ Ω ⊂ R ^d

ただし，

Ω ⊂ R ^d

d

R ^d

過学習されたモデルの係数

▶ 10

最小二乗推定値

w

+8.110 w

− 0.850 w

− 52.16 w

−4.110 w

+87.75 w

+41.13 w

− 49.97 w

− 79.87 w

+6.340 w

+43.99

−1.0 −0.5 0.0 0.5 1.0

−1.0−0.50.00.51.0

x

y

−1.0 −0.5 0.0 0.5 1.0

−1.0−0.50.00.51.0

−1.0 −0.5 0.0 0.5 1.0

−1.0−0.50.00.51.0 True

Data Estimated

リッジ回帰分析（制約表現）

ˆ

w Ridge = arg min

w ∈R

∑ n

i=1

(y i − w ^⊤ x i ) ² subject to

∑ d

j=1

w _j ² ≤ s

リッジ回帰分析（罰則表現）

hatw Ridge = arg min

w ∈R

∑ n

i=1

(y i − w ^⊤ x i ) ² + λ

∑ d

j=1

w _j ²

λ > 0

対応関係

w∈R

min

∑

(y

− w

x

)

+ λ

∑

w

min

w∈R^d

∑

(y

− w

x

)

subject to

∑

w

≤ s

リッジ回帰分析（復習）

▶

w λ = arg min

w ∈R

∑ n i=1

(y i − w ^⊤ x i ) ² + λ

∑ d j=1

w _j ²

ただし，λ >

0

リッジ回帰分析の行列・ベクトル表現（復習）

▶

X

n × d

=



 

 

x ₁₁ x ₁₂ · · · x _1d x ₂₁ x ₂₂ · · · x _2d .. . .. . . . . .. . x n1 x n2 · · · x nd



 

  ∈ R ^{n × d} , y

n × 1

=



 

  y ₁ y ₂ .. . y n



 

  ∈ R ⁿ .

▶

E= (y − X w) ^⊤ (y − Xw) + λw ^⊤ w

= w ^⊤ (X ^⊤ X )w − 2(X ^⊤ y) ^⊤ w + y ^⊤ y + λw ^⊤ w

= w ^⊤ (X ^⊤ X + λI)w − 2(X ^⊤ y) ^⊤ w + y ^⊤ y

▶

w ^∗ _λ = (X ^⊤ X ^{− 1} + λI) ^{− 1} X ^⊤ y

平均二乗誤差のバイアス・分散分解

▶

E [ ˆ w] = w

▶

E [ ˆ w] ̸ = w

▶

E [(w − w) ˆ ² ] = (w − E [ ˆ w]) ²

| {z }

バイアス²

+ E [( ˆ w − E [ ˆ w]) ² ]

| {z }

分散

E [(w − w) ˆ

]= E [((w − E [ ˆ w]) − ( ˆ w − E [ ˆ w]))

]

= (w − E [ ˆ w])

+ 2(w − E [ ˆ w]) E [ ˆ w − E [ ˆ w]] + E [( ˆ w − E [ ˆ w])

]

最小二乗法とリッジ回帰分析のバイアス・分散

▶

MSE[ ˆ w] = σ ²

∑ d j=1

1 ρ _j

| {z }

分散

ただし，

ρ j , j = 1, . . . , d

X ^⊤ X

( ≥ 0)

▶

MSE[ ˆ w ^R ] = σ ²

∑ d j=1

ρ _j (ρ j + λ) ²

| {z }

分散

+ λ ² w ^⊤ (X ^⊤ X + λI) ^{− 2} w

| {z }

バイアスの

2

一般化二次正則化

▶

∈ R ^{d × d}

G

⇔ z ^⊤ Gz ≥ 0 ∀ z ∈ R ^d

▶

E:= (y − X w) ^⊤ (y − X w) + λw ^⊤ Gw

= w ^⊤ (X ^⊤ X + λG)w − 2(X ^⊤ y)w + y ^⊤ y

▶

∂E

∂w = 0 ⇔ (X ^⊤ X + λG)w = X ^⊤ y

⇔ w _λ ^∗ = (X ^⊤ X + λG) ^{− 1} y

演習問題３（その１）

▶

4

y = w 1 x 1 + w 2 x 2 + w 3 x 3 + w 4 x 4

を使ってモデル化しよう．ここで，

4

x 1 30

x 2 40

x ₃ 50

x 4 60

演習問題３（その２）

▶

以下の正則化項を導入する：

R(w) := λ 1

∑ 4 j=1

w ² _j + λ 2

∑ 3 j=1

(w j − w j+1 ) ² .

ただし，第

1

2

▶

R(w)

R(w) = w ^⊤ Gw

と表すためには，Gをどのような行列とすればよいか答えよ．た だし，Gは正定値行列として，対称行列であることに留意せよ．

演習問題３の解答

発展問題

▶

t

X t

w ˆ t = (X _t ^⊤ X t ) ^{− 1} X _t ^⊤ y

S _t := (y − X _t w ˆ _t ) ^⊤ (y − X _t w ˆ _t )

P _t := I − X _t (X _t ^⊤ X _t ) ^{− 1} X _t ^⊤

と定義する．新たに加える特徴を

x j ∈ R ⁿ

t + 1

S _t+1 = S _t − (y ^⊤ P _t x _j ) ² x ^⊤ _j P t x j

と表されることを示せ．

発展問題のヒント（その１）

▶

P _t := I − X _t (X _t ^⊤ X _t ) ^{− 1} X _t

▶

P _t

P _t ² = P _t

▶

P _t

S t := (y − X t w ˆ t ) ^⊤ (y − X t w ˆ t ) = y ^⊤ P t y

発展問題のヒント（その２）

▶

A ∈ R ^{d × d}

a ∈ R ^d

a ∈ R

[ A a a

a

]

=

[ A

0 0

0

]

+ 1

a − a

A

a

[ A

a

− 1

] [ A

a

− 1 ]

▶

(X _t+1 ^⊤ X _t+1 ) ^{− 1}

(X

X

)

= ([ X

x

] [ X

x

])

=

[ (X

X

)

0

0

0

]

+ 1

x

x

− x

X

(X

X

)

X

x

[ (X

X

)

X

x

− 1

] [ (X

X

)

X

x

− 1

]

発展問題の解答