L_1正則化付きフルスパン対数線形モデルとその性能

社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
L1 正則化付きフルスパン対数線形モデルとその性能
高畠 一哉†
赤穂昭太郎†
† 産業総合技術研究所人間情報研究部門
〒 305-8568 茨城県つくば市梅園 1–1 産総研中央 2
E-mail: †{k.takabatake,s.akaho}@aist.go.jp
あらまし
Full-span log-linear モデルとは十分な数の基底を持ち全ての Gibbs 分布が表現可能な log-linear モデルであ
る．このモデルに L1 正則化を用いて学習を行うと，表現力が高くかつパラメータ数の少ないモデルが得られる．本論
文ではこの full-span log-linear モデルが隠れ変数を持つ場合の理論的な特徴について示し，さらに従来の Boltzmann
machine との性能比較を行う．
キーワード
スパースモデリング，L1 正則化，log-linear モデル，性能比較，高速計算
Full-span log-linear model with L1 regularization and its performance
Kazuya TAKABATAKE† and Shotaro AKAHO†
† Human Informatics Research Institute, AIST
AIST Central 2, Tsukuba, 305-8568, JAPAN
E-mail: †{k.takabatake,s.akaho}@aist.go.jp
Abstract The full-span log-linear model is a log-linear model that has a sufficient number of basis functions so
that it is able to represent arbitrary Gibbs distributions. Applying L1 regularization for learning of the full-span
log-linear model, we can automatically obtain a model that has a small numbers of parameters; nevertheless, it flexibly represents various distributions for various target systems. In this paper, theoretical properties of the full-span
log-linear model that has hidden variables are shown. Furthermore, we show performance comparisons between a
full-span log-linear model and a Boltzmann machine.
Key words sparse modeling, L1 regularization, log-linear model, performance comparison, fast algorithm.
1. は じ め に
あれば，元となる多パラメータモデルのパラメータ数は大きい
ほど自在に多種多様の分布を表せるようになるので好都合であ
|Y | 個の実数パラメータを持つ確率モデル pθ (x), θ = {θy }(y ∈
る．そこでモデル多様体 M を全ての分布の空間にとろうとい
Y ) とそのモデル多様体 M = {pθ |θ} を考える．パラメータ数
うのがここでいう full-span モデルである（注 1）．対象となるシ
が大きいほど M は多くの分布を表せる一方，対象とするシス
ステムの変数 X が有限離散値をとるならば，すなわち |X| が
テムの観測データから分布を学習する際にいわゆる過学習が起
有限ならば |X| 個（注 2） のパラメータを使って X 上の任意の分
こり汎化能力の無い役に立たないモデルになってしまう [1]．し
布が表せる．
かしながら最初からパラメータ数の少ないモデルを対象システ
ただし問題となるのは計算量である．例として 20 個の 2 値
ムに合うように設計することは，対象に対するエキスパート的
変数からなる対象のモデル化を考えてみよう．対象システムの
な知識が必要な面倒な作業である．
値域の大きさは |X| = 220 であるので全ての分布を表すには
そこで近年，多くのパラメータを持つモデルから少数のパラ
220 個のパラメータが必要となる．log-linear モデルでは通常
メータを持つモデルを自動的に作り出す手法が盛んに研究/実
負の対数尤度 L(θ) を含むスコア関数 s(θ) の反復法による最小
用化されており，その代表的な手法が「L1 正則化」である [2]．
化により学習が行われる [3]．そこでは反復法の 1 ステップ毎
対象システムを十分に表すと思われる多パラメータモデルに L1
正則化による学習を行うと，不要な大多数のパラメータは自動
的に θy = 0 と抑圧され少数のパラメータだけが生き残る．
さて L1 正則化により不要なパラメータが削り去られるので
（注 1）
：実際にはここで扱う Full-span log-linear モデルは log-linear モデル
なので M は全分布ではなく全 Gibbs 分布 (∀x, p(x) > 0) となる．
（注 2）
：厳密には総和が 1 になるという条件から |X| − 1 個．
—1—
に L の勾配ベクトル ∇L を求める必要があるが，この 1 成分
⟨ ⟩
t
(θy
− tanh−1 ϕy p
∂y L(θ)（注 3） の計算に |X| = 220 の何倍かの浮動小数点演算が必
要である．したがって ∇L 全体を求めるには |X| = 2
2
40
θt
⟨ ⟩
, − ϕy p
D
)
回の
図 1 ∂y L(θy ) の形状 (隠れ変数なし)
何倍もの浮動小数点演算が必要となり現実的ではない．ところ
が log-linear モデルの基底をうまく取ることによりこの計算量
を O(|X|n)（注 4） に落とせることが分かった [4]．∇L が求まるな
らば適当な最小化手法を用いてデータからモデルを学習するこ
G0x0 ...xn−1 = pθ (x) − pD (x)
∑ i
Gi+1
Gy0 ...yi−1 xi ...xn−1 ϕiyi xi
y0 ...yi xi+1 ...xn−1 =
とができる．
(3)
xi
本論文ではこの高速計算法をさらに隠れ変数がある場合に拡
張する．また隠れ変数のない場合において full-span log-linear
モデルと Boltzmann machine [5] との実験による性能比較を
行う．
∇L = Gn
y0 ...yn−1
Xi が a 個の値をとるものとすると計算量は O(|X|na) となり，
さらに a が大きい時には ϕiyi xi に高速アダマール変換行列や高
速フーリエ変換行列を使うことにより計算量を O(|X|n log a)
2. 隠れ変数がない場合
に落とせる．
隠れ変数のない場合については既に [4] で示したのでここで
さて ∂y L は次式で計算される [3]．
∂y L = ⟨ϕy ⟩pθ − ⟨ϕy ⟩pD
は結果だけ示す．まず記号について定めておく．
X = (X0 , ..., Xn−1 ): 対象システムの確率変数．Xi は有限離
散値 xi ∈ Xi をとる（注 5）．
Y = (Y0 , ..., Yn−1 ) : パラメータの添字の集合．|Xi | = |Yi | で
ある．
(4)
ここで θy 以外の全てのパラメータを固定した 1 変数関数 L(θy )
を考える．式 (4) 第 1 項を u(θy ) とおき，基底に ϕ2y ≡ 1 とい
う条件を課すると常微分方程式
u′ = 1 − u2
θ = {θy }(y ∈ Y ): パラメータ．θy ∈ R．
ϕ : Y × X → R: 基底関数．Y は基底の番号であり ϕy : X →
R は Y = y とした時の 1 個の基底である．Y = y, X = x と
とった時の値を ϕyx で表す．
本論文では L1 正則化項を多少拡張した以下のスコア関数 s(θ)
の最小化を考える．
が導かれ，境界条件として ⟨ϕy ⟩p
θt
が既知とするとその結果
∂y L は以下のように一意に定まる．
(
)
∂y L(θy ) = tanh θy − θyt + tanh−1 ⟨ϕy ⟩p t − ⟨ϕy ⟩pD
θ
(5)
s(θ) = L(θ) + R(θ)
となる．図 1 に ∂y L の形状を示す．
L(θ) = − ⟨ln pθ ⟩pD
∑
R(θ) =
wy |θy |,
(1)
wy >
=0
またこれを積分することにより L(θy ) も求められる．
式 (5) において第 1 項は (−1, 1)，第 2 項は [−1, 1] の範囲の
y
値しか取らないので ∂y L(θy ) は (−2, 2) の範囲の値しか取らな
L(θ) は負の対数尤度，R(θ) は L1 正則化項である．隠れ変数
い．θy =
| 0 なる s(θ) の極小点では ∂y L = wy か ∂y L = −wy
なしの場合は L, R はともに凸関数であるので s(θ) も凸関数と
なり，極小点は最小点であることが保証され [6] 山下り法や準
が成り立つ必要があるが，このことは逆に wy >
= 2 と取ると
s(θ) の極小点では必ず θy = 0 となることを意味している．こ
ニュートン法によって最小点を求めることができる．
の性質を用いれば意図的に不要な基底を使わないようにモデル
pθ (X) は以下に示す log-linear モデルである．
pθ (x) =
elθx
,
Z
lθx =
∑
θy ϕyx ,
Z=
y
∑
elθx
を設計することができる．
(2)
x
ここで基底 ϕy を以下のような xi に関する 1 変数関数 ϕiyi xi (ロー
カル基底と呼ぶ) の積とする．
ϕy =
∏
3. 隠れ変数がある場合
X = (V, H)，すなわち X が観測可能な変数 V と観測不能な
変数 H からなる場合スコアは以下のようになる．
s(θ) = L(θ) + R(θ)
ϕiyi xi
i
すると以下の漸化式により L の勾配ベクトル ∇L を求められる．
L(θ) = − ⟨ln pθ (V )⟩pD (V )
∑
R(θ) =
wy |θy |, wy >
=0
(6)
y
なお隠れ変数がない場合とは違い s(θ) の凸性は保証されな
い．したがって山下り法や準ニュートン法などの最小化手法で
（注 3）
：∂y = ∂/∂θy
（注 4）
：n は X に含まれる変数の個数
（注 5）
：本論文では確率変数には大文字，その具現値には小文字を使う．また混
乱の恐れが無い限り確率変数とその値域に同じ記号 (この場合 Xi ) を用いる
は最小点への収束は保証されないことに注意されたい．
3. 1 ∇L の求め方
L を θy で微分すると
—2—
∂y L = −∂y
∑
pD (v) ln pθ (v)
⟨ ⟩
ϕy p
θ
⟨ ⟩
ϕy p
η
v
=−
∑ pD (v)
∂y pθ (v)
pθ (v)
v
∑
∑ pD (v) ∑ e y θy ϕy
∑ ∑ θ ϕ
∂y
, Z=
e y y y
=−
p
(v)
Z
θ
v
h
h
(
)
∑
∑
∑ pD (v) ∑ ϕy e y θy ϕy
y
e θy ϕ y ∂ y Z
=−
−
pθ (v)
Z
Z2
v
h
(
)
∑ pD (v) ∑
pθ (x)∂y Z
pθ (x)ϕy −
=−
pθ (v)
Z
v
h
)
(
∑
∑
∑ pD (v) ∑
ϕy e y θy ϕy
=−
pθ (x) ϕy − x
pθ (v)
Z
v
h
∑ pD (v) ∑
pθ (x)(ϕy − ⟨ϕy ⟩pθ )
pθ (v)
v
h
∑
∑
pθ (h|v)ϕy
= ⟨ϕy ⟩pθ −
pD (v)
=−
v
= ⟨ϕy ⟩pθ
図 2 ∂y L(θy ) の形状 (隠れ変数あり)
)
(
ψyv (θy ) = tanh θy − θyt + tanh−1 ψyv (θt )
が得られる．これらの結果から
(
)
∂y L(θy ) = tanh θy − θyt + tanh−1 ⟨ϕy ⟩p t
θ
(
)
1 ∑
−
tanh θy − θyt + tanh−1 ψydi (θt )
|D| i
h
⟨
⟩
− ⟨ϕy ⟩pθ (h|v)
pD (v)
(8)
= ⟨ϕy ⟩pθ − ⟨ϕy ⟩pη , pη (vh) = pD (v)pθ (h|v)
∑
=
(pθ (x) − pη (x))ϕyx
となりその形状は図 2 のようになる．
x
(7)
これを全ての y について求め ∇L を得るには隠れ変数なしの
場合の式 (3) において G0x = pθ (x) − pη (x) とするだけでよい．
したがって隠れ変数ありの場合も ∇L は O(|X|n) の計算量で
計算できる（注 6）．
隠れ変数なしの場合 θy 以外のパラメータを固定した 1 変数
関数 ∂y L(θy ) を完全に決定することができたが，隠れ変数あり
式 (7) において ⟨ϕy ⟩pθ は隠れ変数なしの場合と同じで式 (5)
の右辺第 1 項である．
(
)
⟨ϕy ⟩pθ = tanh θy − θyt + tanh−1 ⟨ϕy ⟩p t
θ
一方 ⟨ϕy ⟩pη については
ψyv (θ) = ⟨ϕy ⟩pθ (H|v) =
∑
pθ (h|v)ϕy
h
とおくと |D| をデータ数，di を i 番目のデータとして
⟨ϕy ⟩pη =
pD (v)ψyv
v
1 ∑
=
ψydi
|D| i
となる．ここで v により条件化した確率もまた log-linear モデ
ルとなることから
⟨ ⟩
= ϕ2y p
とおくことにより ϕy の使用を禁ずることができる．
4. 実
験
ここでは隠れ変数のない場合について実験を行う．
関数 f の従属変数の個数，すなわち f が関わる変数の個数を
次数とよび Order(f ) と表すことにする．以下の 3 つの学習器
を用意した．
の場合もこれができる．
∑
tanh は (−1, 1) の範囲の値しか取らないので隠れ変数なしの
場合と同様に ∂y L(θy ) ∈ (−2, 2) である．したがって wy >
=2
4. 1 使用した学習器
3. 2 1 変数関数 ∂y L(θy )
∂y ψyv
∂y L
θ (h|v)
2
− ⟨ϕy ⟩2pθ (h|v) = 1 − ψyv
,
Boltzmann machine) 2 次までの基底を用いるモデル．すな
わち正則化項の重み wy は


2



wy = λ




2
Order(ϕy ) = 0
1<
= Order(ϕy ) <
=2
Order(ϕy ) > 2
3-body machine) 3 次までの基底用いるモデル．


2


wy = λ




2
Order(ϕy ) = 0
1<
=3
= Order(ϕy ) <
Order(ϕy ) > 3
full-span machine) 使う基底に制限のないモデル．

2
wy =
λ
Order(ϕy ) = 0
Order(ϕy ) > 0
t
常微分方程式を解いて境界条件 ψyv (θ ) が既知とすると
（注 6）
：厳密に言うと Xi の値域の大きさ a を変数と考えると O(|X|na)，さら
に高速変換を用いれば O(|X|n log a) であるがこれ以降では a は定数と考える．
いずれのモデルも Order(ϕy ) = 0 すなわち恒等的に定数であ
る基底は用いない．なぜなら指数部に定数を加えても正規化さ
れた pθ は不変であるためである．またこの実験では λ = 0.1
—3—
表1
dataset
Ising5x4
図 3 Ising5x4
BN20-37
X0
X1
実験結果 (|D| = 1024)
learner
score
JS
Boltzmann
9.76
.03
94
31
16
3-body
9.76
.03
94
31
16
full-span
9.68
.04
2592
55
42
Boltzmann
11.04
.25
57
26
13
3-body
10.63
.16
151
50
24
32
full-span
BN20-54
10.51 .15
721
59
Boltzmann
12.80
.35
56
11
5
3-body
12.29
.24
124
25
12
11.99 .19
1102
37
20
full-span
表2
dataset
Ising5x4
図 4 BN20-37
BN20-37
実験結果 (|D| = 1048576)
learner
score
JS
Boltzmann
9.91
.03
111
26
17
3-body
9.91
.03
111
26
15
full-span
9.90
.04
672
54
51
Boltzmann
11.10
.25
61
30
16
3-body
10.70
.16
125
46
24
10.65 .14
349
41
26
12.84
.35
52
10
6
12.37
.24
105
24
14
12.15 .18
171
33
19
full-span
と定めた．
Boltzmann
4. 2 使用した最適化法
負の対数尤度の勾配ベクトル ∇L が求まるならば後は適当な
BN20-54
#para step time(sec)
3-body
full-span
#para step time(sec)
最適化法を用いてスコア s(θ) の最小化が行える．ただし s(θ)
は θy = 0 で微分不可能なので，それを考慮した最適化手法
を用いなければならない．OWL-QN(Orthant-Wise Limited-
memory Quasi-Newton) 法 [7] はこの点を考慮した準ニュート
ン法である．最小化すべき多変数関数の次元 (ここでは |X|) に
対して，反復法の 1 ステップの計算量が O(|X|)，メモリ使用量
が O(|X|) であり，超高次元の多変数関数の最適化に向いてい
る．実験では勾配ベクトルの履歴を残すキューの深さは 10 と
した．また反復法の終了条件は s(θt−1 ) − s(θt ) < 10−4 とした．
4. 3 使用した問題
ングしそれぞれの学習器に学習させた．データ数 |D| は中規模
データと大規模データを想定し |D| = 210 = 1024, |D| = 220 =
1048576 の 2 通りについて実験した．
4. 4 実 験 環 境
実験には以下の計算機，プログラミング言語を用いた．
モデル:
DELL PRECISION M6400
CPU: Intel Core2 Extreme X9100 3.06GHz
メモリ:
16GB
プログラム:
以下の 3 つの問題を用いた．
Ising5x4) 図 3 に示す 20 ノードのイジングスピンモデル．各
ノードは値 ±1 をとりモデルの真の確率は
1 ∑
Preal (x) = e <i,j> θij xi xj
Z
Java 8，シングルスレッドプログラミング
4. 5 結
果
表 1,2 にそれぞれ中規模データ (データ数 1024)，大規模デー
タ (データ数 1048576) を学習させた結果を示す．表において
score は s(θ) の値，JS は真のモデル分布と学習したモデル分
布間の Jensen Shannon divergence（注 7）
こ こ で < i, j > は 図 で 隣 接 し た ノ ー ド の 組 を 表 す．ま た
i, j ∈ [0, 20] で x20 は常に値 1 をとる変数である．ここでは
θij

0
=
0.5
i>
= j
i<j
JS(p||q) =
1
(KL (p||r) + KL (q||r)) ,
2
r=
p+q
,
2
#para は学習結果の非ゼロのパラメータ数，step は OWL-QN
法での反復法にかかったステップ数，time は学習にかかった計
算時間である．また太字は 3 つの学習器の中での最良値である．
とした．
これらの項目の中で実用上最も重要な性能指標は真のモデルと
BN20-37) 図 4 に示す 20 ノード 37 枝のベイジアンネットワー
の近さを表す JS である (図 5)．
クであり X0 , X1 を除きどのノードも 2 個の親を持つ．各ノー
Ising5x4 の真のモデル分布は 2 次までの基底を使って表せる
ドは値 0, 1 をとる．各ノードの条件付き確率表には一様乱数を
のでどの学習器でも良く学習できている．full-span モデルは
用いて値を入れていてこの値は実験を通じて不変である．
score が小さいにも関わらず JS で負けているが，これは score
BN20-54) BN20-37 と同様の方法で作られたものであるが枝
がモデルの良さをうまく反映していないためであり，具体的
数は 54 で，X0 , X1 , X2 を除くノードは 3 個の親を持つ．
どの問題も人工的な問題なので真のモデル分布 preal (X) が
分かっている．この真のモデル分布から i.i.d. データをサンプリ
（注 7）
：KL divergence はモデルの分布とデータの分布間を測る距離としては
良いが 2 つのモデルの分布間の距離としては近い分布でも値が発散する等の悪い
性質を持つのでここでは Jensen Shannon divergence を使う．
—4—
Sheet1
•
JS(real||lezrned) |D|=1024 shorter is better
2 値変数 20 個程度の問題には市販のパソコンで 1 分程度
で学習が終了する．逆にそれ以上の規模の問題となると計算量，
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
メモリ使用量とも指数関数的に増えるので実用的でなくなる．
•
Ising5x4
Boltzmann
3-body
full-span
BN20-37
正則化項の重み wy のとり方については色々なバージョ
ンが考えられるが，それは今後の課題である．
謝辞
本研究は JSPS 科研費 25120011 および 25330276 の
助成を受けたものです．
文
BN20-54
JS(real||learned) |D|=1048576 shorter is better
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
Ising5x4
Boltzmann
3-body
full-span
BN20-37
BN20-54
献
[1] T. Hastie, R. Tibshirani, and J. Friedman, The Elements of
Statistical Learning; data mining, inference and prediction,
Springer-Verlag, 2001.
[2] J. Friedman, T. Hastie, and R. Tibshirani, “Regularization
paths for generalized linear models via coordinate descent,”
Journal of statistical software, vol.33, no.1, p.1, 2010.
[3] D. Koller and N. Friedman, Probabilistic Graphical Models,
MIT Press, 2009.
[4] 高畠一哉，赤穂昭太郎，“対数線形モデル高速学習のための基底
関数，
” 信学技報，vol.114，no.306，pp.307–312，2014．
[5] D.E. Rumelhart, J.L. McClelland, P.R. Group, et al., Parallel distributed processing, vol.1, MIT press, 1995.
[6] R.T. Rockafellar, Convex analysis, no.28, Princeton university press, 1997.
[7] G. Andrew and J. Gao, “Scalable training of l 1-regularized
log-linear models,” Proceedings of the 24th international
conference on Machine learningACM, pp.33–40 2007.
図5 性能比較
には正則化項が小さすぎたためと考えられる．パラメータ数
#para の多さからも過学習が疑われる．
BN20-37 の真のモデル分布は
preal (x) =
∏
p(xpi |xi )
i
(9)
Page 1
と表せる．ここで xpi は xi の親ノードであり BN20-37 では xpi
は 2 個のノードからなる．つまり p(xpi |xi ) の従属変数の数は
3 であり，この分布は 3 次までの基底を使って表せることにな
る．その結果 2 次までの基底しか使えない Boltzmann machine
は他に比べ大きく性能が劣り，3-body machine と full-span
machine はほぼ同等の性能となっている．
BN20-54 の真のモデル分布は同じく式 (9) で表せるが xpi は
3 個のノードからなり p(xpi |xi ) の従属変数の数は 4 となる．そ
の結果 3-body machine と full-span machine の間に性能差が
出てくる．
5. ま と め
本論文で紹介した L1 正則化による full-span log-linear モデ
ルは
•
全 Gibbs 分布を表現できるのでどんな対象システムも柔
軟に学習できる．
•
不要なパラメータは自動で削除されスパースなモデルが
できる．
•
正則化項の設定により要らないパラメータを予め省くこ
ともできる．例えば Boltzmann machine や n 体ポテンシャル
マシンなどを作ることができる．
•
隠れ変数のあるなしに関わらず計算量は O(|X|n)．
—5—