データ解析
第六回「L1 正則化法：高次元データ解析」
鈴木 大慈
理学部情報科学科
西八号館 W707 号室
s-taiji@is.titech.ac.jp

1 / 12

休講情報

7/7 は休講

2 / 12

今日の講義内容
L1 正則化
バイオデータとスパムメール判別によるデモ
レポート課題3 / 12

モデル選択の難しさ
高次元データ：パラメータの次元 p が大きい．

AIC でモデル選択→ 2p 通り ! (NP 困難)→ 計算に時間がかかりすぎる→ L1 正則化：凸最適化で変数選択(R の step() では変数を一つ加えたり削ったりして最適なモデルを探索．初期値に大きく依存する．)

4 / 12

スパース推定 [Lasso]
デザイン行列 X = (Xij ) ∈ Rn×p .
p (次元) ≫ n (サンプル数).
真のベクトル β ∗ ∈ Rp : 非ゼロ要素の個数がたかだか d 個 (スパース).
モデル : Y = X β ∗ + ξ.

∑1β̂ ← arg min ∥X β − Y ∥22 + λn|βj |.
β∈Rp npj=15 / 12

スパース推定 [Lasso]
デザイン行列 X = (Xij ) ∈ Rn×p .
p (次元) ≫ n (サンプル数).
真のベクトル β ∗ ∈ Rp : 非ゼロ要素の個数がたかだか d 個 (スパース).
モデル : Y = X β ∗ + ξ.

∑1β̂ ← arg min ∥X β − Y ∥22 + λn|βj |.
β∈Rp npj=1Theorem (Lasso の収束レート (Bickel et al., 2009, Zhang, 2009))
デザイン行列が Restricted eigenvalue condition Bickel et al. (2009) かつ
2 2maxi,j |Xij | ≤ 1 を満たし，ノイズが E[e τ ξi ] ≤ e σ τ /2 (∀τ > 0) を満たすなら, 確率1−δでd log(p/δ).
∥β̂ − β ∗ ∥22 ≤ Cn
※次元が高くても，たかだか log(p) でしか効いてこない．実質的な次元 d が支配的．
5 / 12

一般化加法モデルへの L1 正則化の適用

L1 正則化：β̂ ← arg min
β∈Rp

∑
1∑
|βj |.
ℓ(yi , xi⊤ β) + λnnn

pi=1j=1

L2 正則化（前回の授業参照．Ridge regression はこれに含まれる）：β̂ ← arg min
β∈Rp

∑
1∑
ℓ(yi , xi⊤ β) + λnβj2 .
nnpi=1j=1

6 / 12

glmnet で L1 正則化

glmnet(x, y,..., alpha = 1)alpha (デフォルト 1) で正則化項を L1 と L2 の間で調整：
β̂ ← arg minβ∈Rp∑
1∑1(α|βj | + (1 − α)βj2 ).
ℓ(yi , xi⊤ β) + λnn2np

i=1j=1

この α の値を alpha で指定．
（これを Elasticnet 正則化と呼ぶ）

α = 1 → L1 正則化
α = 0 → L2 正則化

7 / 12

LiblineR で L1 正則化

LiblineaR(x,y, type=6)
type で正則化の種類とロス関数を指定．デフォルトは type=0.
0 - L2-regularized logistic regression
1 - L2-regularized L2-loss support vector classification (dual)
2 - L2-regularized L2-loss support vector classification (primal)
3 - L2-regularized L1-loss support vector classification (dual)
4 - multi-class support vector classification by Crammer and Singer
5 - L1-regularized L2-loss support vector classification
6 - L1-regularized logistic regression
7 - L2-regularized logistic regression (dual)※ LiblineaR は判別問題しか扱えない．

8 / 12

library(glmnet)
library(lars)data(diabetes) #糖尿病データ．線形回帰問題．lars パケージに入っている．
lasso <- glmnet(diabetes$x, diabetes$y)plot(lasso)
24681010400600

00−600−400−200

Coefficients

200

左図の意味：λ を動かしていった時に，推定された係数がどうふるまうか．
λ が大きい時，つまり L1 ノルムが小さい時は推定量がスパースになっていることがわかる．

0500

1000

1500

2000

2500

3000

L1 Norm

正則化パス．横軸は推定量の L1 ノルム．
9 / 12

スパムメール判別
メールをスパムかそうでないかを判別したい．
判別分析の枠組みに乗せるため，各メールを一つのベクトル x として表したい．

Bag of words: 出現した単語の頻度を並べたベクトル．
各要素が各単語の頻度に対応．
単語数分だけの次元になるため高次元になりやすい．自然言語処理では 100 万次
元はザラ．
“please” の出現頻度
 “credit” の出現頻度 



..

.
“money” の出現頻度
今回は UCI Machine Learning Repository の Spam e-mail database を利用．
これは 57 次元と次元は低い方．

10 / 12

レポート課題三回目
Ridge 回帰で k-fold CV を実行する関数を書け．入力は Y ∈ Rn (従属変数),
X ∈ Rn×d (説明変数), λ (正則化定数), k (k-fold CV) で，出力は二乗誤差((y − x ⊤ β̂)2 ) の CV スコア．ただし，ライブラリを用いるのではなく，推定量の計算から CV スコアの計算まで自分でコーディングすること．
2
講義第五回に用いた手書き文字認識データで，正則化パラメータと判別精度の関係をグラフにせよ．その際，サンプル数をいくつか変えてみて，それらのグラフを重ね書きせよ．最良な判別精度を達成する正則化パラメータはサンプル数に依存してどう変化しているか？
3
上のデータにさらに CV スコアを重ね書きせよ．LiblineR では cross=k とおくことで k-fold CV スコアが得られる．
cvscore <- LiblineaR(..., cross = 10)
4
自分が興味のあるデータにおいて，最小二乗法以外のこれまで講義で紹介した手法を用いて解析せよ．線形判別，正則化付き線形判別，一般化線形モデ
ル，正則化付き線形回帰など，最小二乗法以外の説明変数から従属変数を予測する問題ならなんでも良い．なお，講義で使わなかった関数を用いても構わない．また，最小二乗法以外の手法を用いても，結局最小二乗法が一番（何らかの意味で）良かった場合はその旨論じてもよい．自分で工夫していればその分評価は上がる．
1

11 / 12

レポートの提出方法
私宛にメールにて提出．
件名に 必ず「データ解析第 n 回レポート」と明記し，R のソースコードと結果をまとめたレポートを送付のこと．
氏名と学籍番号も忘れず明記すること．
レポートは本文に載せても良いが，pdf などの電子ファイルにレポートを出力して添付ファイルとして送付することが望ましい (これを期に tex の使い方を覚えることを推奨します)．
提出期限は講義最終回まで．
※相談はしても良いですが，コピペは厳禁です．

講義情報ページ
http://www.is.titech.ac.jp/~s-taiji/lecture/dataanalysis/dataanalysis.html

12 / 12

P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of Lasso andDantzig selector. The Annals of Statistics, 37(4):1705–1732, 2009.
T. Zhang. Some sharp performance bounds for least squares regression with l1
regularization. The Annals of Statistics, 37(5):2109–2144, 2009.

12 / 12