ニューラル情報処理第５回
特徴選択とスパースモデリング
竹内一郎
名古屋工業大学
高次元線形モデル
▶
基底関数を用いた非線形モデリング(n
が大きいとき)f (x) = w 0 + w 1 h 1 (x) + . . . + w n h n (x)
0 0.2 0.4 0.6 0.8 1
0 20 40 60 80 100
Basis function values hq(x)
Input x
▶
高次元データの線形モデル（例: DNA
マイクロアレイ）f (x) = w 0 + w 1 x 1 + . . . + w 10000 x 10000
Ichiro Takeuchi, Nagoya Institute of Technology 2/22
高次元モデルの２つの問題点
▶
新しいデータの予測に計算コストがかかる▶
基底関数アプローチの場合,
以下の計算が必要▶ n
個の基底関数: h k (x), k = 1, . . . , n,
▶ n + 1
項の線形和: w 0 + ∑ n
k=1 h k (x)
▶ DNA
マイクロアレイデータ解析の場合,
▶ d ≃ 10000
個の遺伝子の活動量 を調べないと診断ができない▶
モデルの解釈が難しい▶ DNA
マイクロアレイデータ解析の場合,
どの遺伝子が 重要であるのかわからない.
線形モデルの特徴選択とは
▶
線形モデルf(x 1 , . . . , x d ) = w 0 + w 1 x 1 + . . . + w d x d
のうち,w j ̸ = 0
となる特徴の部分集合J := { j ∈ { 1, . . . , d } | w j ̸ = d }
を選択したい
▶
最適な特徴選択は組み合わせ最適化問題: 可能な部分集 合J
の数は2 d
通り▶ d = 10
の場合, 1024
通り▶ d = 100
の場合,
約1.3 × 10 30
通りIchiro Takeuchi, Nagoya Institute of Technology 4/22
特徴選択問題の例
▶
遺伝子発現マイクロアレイの例▶
データとモデル▶ x ij :
患者i
の遺伝子j
の活動量▶ y i :
患者i
への薬剤効果y i = f (x i ) = w 0 + w 1 x i1 + . . . + w 10000 x i10000
正則化に基づく特徴選択
(LASSO)
LASSO (Least Absolute Shrinkage and Selection Operator)
▶
アイデア:
いくつかの係数w j
が0
となるよう正則化▶
学習データ{ (x i , y i ) } n i=1 , x i ∈ R d , y i ∈ R
▶ LASSO
（正則化形式）min w
∑ n i=1
( y i − w ⊤ x i ) 2
+ λ || w || 1 , || w || 1 :=
∑ d j=1
| w j |
▶ LASSO
（制約形式）min w
∑ n i=1
( y i − w ⊤ x i ) 2
subject to || w || 1 ≤ s
Ichiro Takeuchi, Nagoya Institute of Technology 6/22
ベクトルのノルム（参考）
▶ L q
ノルム:
∥ w ∥ q := (∑ d
j=1 | w j | q ) 1
q
▶ L 1
ノルム∥ w ∥ 1 := (∑ d
j=1 | w j | 1 ) 1 1
= ∑ d
j=1 | w j |
▶ L 2
ノルム∥ w ∥ 2 := (∑ d
j=1 | w j | 2 ) 1 2
= √∑ d j=1 w 2 j
▶ L ∞
ノルム∥ w ∥ ∞ := (∑ d
j=1 | w j | ∞ ) ∞ 1
= max j ∈{ 1,...,d } | w j |
▶ L 0
ノルム∥ w ∥ 0 := {
j ∈ { 1, . . . , d } | w j ̸ = 0 }
1
次正則化と2
次正則化(
その1)
min w
∑ n
i=1
( y i − w ⊤ x i ) 2
+ λ || w || 1 ,
-4 -2 0 2 4
-4 -2 0 2 4
w2
w1
min w
∑ n
i=1
( y i − w ⊤ x i ) 2
+ λ || w || 2 2 ,
-4 -2 0 2 4
-4 -2 0 2 4
w2
w1
Ichiro Takeuchi, Nagoya Institute of Technology 8/22
L 1制約とL 2制約
min w
∑ n
i=1
(y i − w ⊤ x i ) 2 s.t || w || 1 ≤ s
L 1
正則化min w
∑ n
i=1
(y i − w ⊤ x i ) 2 s.t || w || 2 2 ≤ s
L 2
正則化1
次正則化と2
次正則化(
その1)
▶
遺伝子発現マイクロアレイデータの例（n= 188
人,d = 7399
遺伝子)
▶ 1
次正則化のパラメータ-0.6 -0.4 -0.2 0 0.2 0.4 0.6
0 1000 2000 3000 4000 5000 6000 7000
Coefficients Values
Feature ID
▶ 2
次正則化のパラメータ-0.06 -0.04 -0.02 0 0.02 0.04 0.06
0 1000 2000 3000 4000 5000 6000 7000
Coefficients Values
Feature ID
Ichiro Takeuchi, Nagoya Institute of Technology 10/22
問題の単純化
:
定数項のみを持つモデル▶
定数のみを持つモデルf (x) = w
▶
最小二乗法w ∗ = arg min
w ∈R E :=
∑ n i=1
(y i − w) 2
▶
最小二乗解は算術平均∂E
∂w ∝
∑ n i=1
(y i − w ∗ ) = 0 ⇔ w ∗ = 1 n
∑ n i=1
y i
課題１
▶
以下の1
変数の問題を考える: min w
1 2n
∑ n
i=1
(y i − w) 2 + λ | w |
▶
第1
項を整理すると，上の最小化問題が以下のように 書けることを示せ．min w
1
2 (w − y) ¯ 2 + λ | w | , y ¯ := 1 n
∑ n
i=1
y i
▶
ヒント：最適化問題では，変数w
を含まない定数部分 は異なっていてもよい（最適解に影響を与えない）こ とに留意せよ．Ichiro Takeuchi, Nagoya Institute of Technology 12/22
課題１のさらなるヒント
▶
最適化問題としての等価性を示すには，g 1 (w) := 1 2n
∑ n
i=1
(y i − w) 2 ,
g 2 (w) := 1 2 (w − 1
n
∑ n
i=1
y i )
が定数項（wに依存しない項）を除いて一致することをしめせばよい．
▶
それぞれ，g 1 (w) = · · · = 1 2 w 2 − 1
n ( n
∑
i=1
y i
) w + C 1 ,
g 2 (w) = · · · = 1 2 w 2 − 1
n ( n
∑
i=1
y i
) w + C 2
と表せることが確認できればよい（ただし，C
1
とC 2
はw
に依存しない異なる 定数）LASSO
の数値解法（なぜ疎な解を持つのか）その１▶
最適解の条件0 = ∂E
∂w = w − y ¯ + λ ∂ | w |
∂w =
w − y ¯ + λ, if w > 0, w − y ¯ − λ, if w < 0, not well defined if w = 0
Ichiro Takeuchi, Nagoya Institute of Technology 14/22
LASSO
の数値解法（なぜ疎な解を持つのか）その２▶ w > 0
の場合w > 0 ⇒ ∂E
∂w = w ∗ − y ¯ + λ = 0 ⇔ w ∗ = ¯ y − λ
LASSO
の数値解法（なぜ疎な解を持つのか）その３▶ w < 0
の場合w < 0 ⇒ ∂E
∂w = w ∗ − y ¯ − λ = 0 ⇔ w ∗ = ¯ y + λ
Ichiro Takeuchi, Nagoya Institute of Technology 16/22
LASSO
の数値解法（なぜ疎な解を持つのか）その3
w ∗ = ¯ y − λ w ∗ = ¯ y + λ w ∗ = 0
λ < y ¯
のときy < ¯ − λ
のとき− λ < y < λ ¯
のときソフトスレッショルディング
▶
ソフトスレッショルディングw ∗ =
¯
y + λ if y < ¯ − λ 0 if − λ ≤ y ¯ ≤ λ
¯
y − λ if y > λ ¯
Ichiro Takeuchi, Nagoya Institute of Technology 18/22
正則化とスレッショルディング
Least Square Hard Thresholding Ridge
課題２
ソフトスレッショルディングを用いた
Shooting
アルゴリズ ムと呼ばれるLASSO
のアルゴリズムを考える. このアルゴ リズムでは, d
個のパラメータw 1 , . . . , w d
のうちd − 1
個を 固定し, 1
つのパラメータのみの更新を繰り返す:
1: w j ← 0 for j = 1, . . . , d 2: repeat
3: for k = 1, . . . , d do
4: update w k with the remaining parameters { w j } j ̸ =k fixed 5: end for
6: until stopping condition is satisfied
このアルゴリズムの
4
行目のステップ がソフトスレッショ ルディングによって実現できることを示せ.
Ichiro Takeuchi, Nagoya Institute of Technology 20/22
課題２のヒント
