混合整数二次錐計画法を用いた回帰式の変数選択

数理解析研究所講究録
第 1879 巻 2014 年 222-229
222
混合整数二次錐計画法を用いた回帰式の変数選択
宮代隆平
東京農工大学大学院工学研究院
Ryuhei Miyashiro
Institute of Engineering,
Tokyo University of Agriculture and Technology
高野祐一
東京工業大学
大学院社会理工学研究科
Yuichi Takano
Graduate School of Decision Science and Technology,
Tokyo Institute of Technology
1 回帰分析における変数選択と情報量規準
統計学における回帰分析では，変数選択は重要な課題として知られている．本稿では，赤池情報
量規準を始めとするいくつかの代表的な情報量規準を考え，それらを最小にする変数選択問題が混
合整数二次錐計画問題として定式化できることを示す．
$n$
$1,2,$
個の観測値
$\ldots,$
$k)$
を
$k$
$x_{ij}(j=$
が与えられ，跳を被説明変数，
種類の説明変数とする．重回帰分析では，以下の線形モデルによって被説明変数
$(y_{i};x_{i1}, x_{i2}, \ldots, x_{ik})(i=1,2, \ldots, n)$
の値を予測する:
$y_{i}=b+a_{1}x_{i1}+a_{2}x_{i2}+\cdots+a_{k}x_{ik}+\epsilon_{i}$
ただし
このとき，候補となる
$p$
$\epsilon_{i}$
は
$i$
,
(1)
番目の観測値の予測残差．
種類の変数の中から最適な説明変数集合を選択する変数選択問題を考
える．
一般に，説明変数を多く含むモデルは与えられたデータに対しては当てはまりが良いものの，未
知のデータに対しては予測能力が低くなる．モデルの複雑さ (説明変数の個数) とモデルの当ては
まりの良さ (所与のデータに対する誤差の小ささ) とのバランスを考慮した適合度指標の代表的な
ものとして，赤池情報量規準 (AIC; [1]) がある．回帰モデル (1) に対するいくつかの自然な仮定の
223
下で，定数項を削除した
AIC 値は
(2)
$n \log(\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}^{2})+2k$
と表わされ，この値が小さいほど良いモデルとされる．以下では AIC の最小化を例にとり説明を
行うが，AIC 以外にもベイジアン情報量規準 (BIC; [13])
を始め，多数の適合度指標がこれまでに
提案されている ([9] などを参照のこと).
2
$A$
に最小化問題
AIC を適合度指標とした説明変数の選択には，ステップワイズ変数選択がしばしば用いられる．
ステップワイズ変数選択は短時間で良いモデル (AIC が小さいモデル) を導くことができるが，
ヒューリスティクスであるため必ずしも
一方で
$k$
を定数と見なすと，関数 (2)
AIC が最小のモデルを選択するわけではない．
の最小化は
$\sum_{i=1}^{n}\epsilon_{i}^{2}$
の説明変数候補から，残差二乗和を最小化するように
$k$
の最小化と等価になり，これは「
個
個の説明変数を選ぶ問題」になる．この問
題は以下の混合整数二次計画問題として定式化できることが知られている
$izea,$
minim,
$p$
(例えば
[6]):
$\sum_{i=1}^{n}\epsilon_{i}^{2}$
$b,\epsilon z$
subject to
$\epsilon_{i}=y_{i}-(b+j\sum_{=1}^{p}ajX_{i}j) (i=1,2, \ldots, n)$
,
$-Mz_{j}\leq a_{j}\leq Mz_{j} (j=1,2, \ldots,p)$ ,
$\sum_{J^{=1}}^{p}z_{j}=k\prime$
,
$M$
しかしながら，上記の定式化では
る説明変数の個数
3
$A|C$
$k$
(4)
(5)
$z_{j}\in\{0,1\} (j=1,2, \ldots,p)$ ,
ただし
(3)
(6)
は十分に大きい正の定数．
$k$
を所与の定数として扱っており，現実には AIC を最小にす
は事前にはわからないという問題点がある．
最小化の混合整数二次錐計画問題としての定式化
本研究では，選択される説明変数の個数
計画問題 (Mixed Integer
$k$
が未知の場合の
AIC 最小化問題を，混合整数二次錐
SOCP; MISOCP) として定式化する．
AIC 最小化問題は，関数 (2) を最小化すればよいことから，直接的には以下の非線形混合整数計
224
画問題として定式化できる (
$k$
も変数である点に注意) :
(7)
$minimizea,b,\epsilon, k,z n\log(\frac{1}{n}\sum_{i=1}^{\mathfrak{n}}\epsilon_{i}^{2})+2k$
制約式 (3), (4), (5), (6).
subject to
しかし，この定式化の目的関数 (7) は非凸な非線形関数であり，0-1 変数
$z_{j}$
の整数性を緩和した上
でもこの問題を解くことは困難である．整数計画問題に対して分枝限定法がうまく働くには，その
連続緩和問題が効率的に解ける形になっている必要がある．以下ではそれを念頭におき，問題を等
価変形する．
目的関数 (7) を以下のように変換する．
$minimizea,b,e, k,z n\log(\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}^{2})+2k$
$\Leftrightarrow minimizea,b,\epsilon, k,z \exp(\log(\frac{1}{n}\sum_{\prime,\iota=1}^{n}\epsilon_{i}^{2})+\frac{2k}{n})$
$\Leftrightarrow minim1zea,b,\epsilon, k,z \exp(\frac{2k}{n})\cdot\sum_{i=1}^{n}\epsilon_{i}^{2}$
項
$\exp(2k/n)\cdot\sum_{i=1}^{n}\epsilon_{i}^{2}$
きる
の上界を表す連続変数
$f$
を導入することにより，問題は以下の形に変形で
:
$\min_{a,b,\epsilon}imizef^{k,z} f$
subject to
$\sum_{i=1}^{n}\epsilon_{i}^{2}\leq f\cdot\exp(-\frac{2k}{n})$
(8)
,
制約式 (3), (4), (5), (6).
次に，制約式 (8) の非線形性を解消する．新たな 0-1 変数 $wj(j=0,1, \ldots,p)$ を定義し，
関して制約式
り
$k$
$\sum_{j=0}^{p}(wj.j)=k$
および
は常に整数値を取るため，
なる．この
$wj$
$w_{j}$
$\sum_{jj}^{p_{=0^{w=}}}1$
は鴎
$=k$
を付け加える．すると，制約式 (5)
の時，またその時のみ $wj=1$ 」
を用いることにより，非線形の制約式 (8)
線形化手法は，整数計画の分野では SOS type 1 [4, 5]
に
(6)
よ
を満たす 0-1 変数と
は以下の線形制約式で表現できる (この
として知られている)
:
$\sum_{i=1}^{n}\epsilon_{i}^{2}\leq f\cdot\exp(-\frac{2k}{n})$
$\Leftrightarrow \sum_{i=1}^{n}\epsilon_{i}^{2}\leq f\cdot g, g=\exp(-\frac{2k}{n})$
$\Leftrightarrow$
と
$wj$
$\{\begin{array}{l}\sum_{i=1}^{n}\epsilon_{i}^{2}\leq f\cdot g, g=\sum_{j=0}^{p}(w_{j}\cdot\exp(-\frac{2j}{n})) ,k=\sum_{j=0}^{p}(w_{J}\cdot j) , \sum_{j=0}^{p}w_{j}=1.\end{array}$
225
ここで $g= \sum_{j}^{p_{=0}}(wj. \exp(-2j/n))$
式
$wj$
に関して線形であることに留意されたい．制約
は非線形であるが，これは以下に示す通り二次錐制約として表現できることが
$\sum_{i=1}^{n}\epsilon_{i}^{2}\leq f\cdot g$
知られている [10]
は，変数
$($
ただしここで
$\Vert u\Vert=(u^{T}u)^{1/2})$
:
$\epsilon^{T}\epsilon\leq f\cdot g, f\geq 0, g\geq 0$
$\Leftrightarrow \Vert(\begin{array}{l}2\epsilon f-g\end{array})\Vert\leq f+g.$
これらをまとめ，AIC 最小化問題の定式化として以下を得る:
minimize
$f$
$g,k,w,za,b,\epsilon,f$
subject to
$\epsilon_{i}=y_{i}-(b+\sum_{j=1}^{p}a_{j}x_{ij}) (i=1,2, \ldots, n)$
$\sum_{i=1}^{n}\epsilon_{i}^{2}\leq f\cdot g, g=\sum_{j=0}^{p}(w_{j}\cdot\exp(-\frac{2j}{n}))$
,
,
$\sum_{j=0}^{p}(w_{j}\cdot j)=k, \sum_{j=0}^{p}w_{j}=1, \sum_{j=1}^{p}z_{j}=k,$
$-Mz_{j}\leq a_{j}\leq Mz_{j} (j=1,2, \ldots,p)$
,
$w_{j}\in\{0,1\} (j=0,1, \ldots,p)$ ,
$z_{j}\in\{0,1\} (j=1,2, \ldots,p)$
.
この定式化で表される問題は，線形制約，二次錐制約，整数制約の下で線形目的関数を最小化する
MISOCP
である．MISOCP の連続緩和問題は二次錐計画問題
(SOCP; [2]) であり，内点法を用
いることにより多項式時間で解を求めることができる．また，内点法をベースにした分枝限定法が
実装された，MISOCP を扱うことのできる数理計画ソルバーが複数存在する．
なお上記の定式化のうち，制約式
$\exp((ln)/n))=\sum_{j}^{p_{=0}}(w\cdot n^{-j/n})$
として定式化できる．また，AIC
$g$
$=$
$\sum_{j}^{p_{=0}}(wj \exp(-2j/n))$
を
$g$
$=$
$\sum_{jj}^{p_{=0(w}}$
に置きかえることにより，BIC 最小化問題を
MISOCP
の有限修正 (corrected AIC; [14]), Hannan-Quinn 情報量規準
residual 情報量規準 (RIC) などの様々な情報量規準の最小化問題，あるいは自由度調
整済決定係数
の最大化問題も同様に MISOCP として定式化できるが，ここでは省略する．
$(HQ;[7])$ ,
$\overline{R}^{2}[15]$
詳細は [12] を参照されたい．
4 計算機実験および考察
計算機実験では，AIC の最小化問題について，ステップヮイズ変数選択との比較を通じて提案手
法の有効性を検証した．実験には UCI Machine Learning Repository [3]
使用した (表 1).
からの 10 つのデータを
226
表1
略称
$n$
$p$
Servo
506
167
13
19
AutoMPG
392
25
1066
1066
1066
194
26
26
26
32
63
65
100
Housing
SolarFlare
$C$
SolarFlare
$M$
SolarFlare
$X$
BreastCancer
ForestFires
Automobile
Crime
517
159
1993
データのリスト
データセット [3]
Housing
Servo
Auto MPG
Solar Flare ( -class flares production)
Solar Flare ( $M$-class flares production)
$C$
Solar Flare ( -class flares production)
Breast Cancer Wisconsin
$X$
Forest Fires
Automobile
Communities and Crime
AIC の最小化に際して，MISOCP の求解には数理計画ソルバー CPLEX12.5[8] を使用した．計
算機環境は，CPU: Intel Xeon W55903.33 GHz ;RAM: 24 $GB$ ; $OS$ : $64bit$ Windows 7Ultimate
$SP$ l; chipset:
Inte15520 のマシンを使用し，各 MISOCP に対して並列分枝限定法 (8 スレッド)
$\cross 2$
を最大 10000 秒実行した
また比較のため，MATLAB $R2012b[11]$
の
LinearModel. stepwise
関数を用いて，ステップワイズ選択による変数選択を行った．こちらの計算機環境は CPU: Intel
Core i7- $2600S$ 2.80 GHz; RAM: 8 $GB$ ;
Q67 Express
である．
$OS$
:
$64bit$
Windows 7 Professional
$SP$
l; chipset: Intel
227
表2
データ
Housing
$n$
$p$
506
13
167
Servo
19
AIC 最小化の実験結果
AIC 値
$SWR_{const}$
776.36
$SWR_{a11}$
776.36
MISOCP776.36
手法
25
$SWR_{const}$
2816.34
2819.73
2816.34
2926.93
2926.93
2926.93
2882.81
9
13
9
7
7
7
3
$SWR_{a11}$
2882.81
3
MISOCP
2882.81
3
509.72
510.58
8
$SWR_{const}$
$SWR_{a11}$
MISOCP
SolarFlare
$C$
1066
26
$SWR_{const}$
$SWR_{a11}$
MISOCP
SolarFlare
$M$
1066
26
$SWR_{const}$
$SWR_{a11}$
MISOCP
SolarFlare
$X$
BreastCancer
1066
194
26
32
$SWR_{const}$
$SWR_{a11}$
MISOCP
ForestFires
517
63
$SWR_{const}$
$SWR_{a11}$
MISOCP
Automobile
159
65
1993
100
258.66
266.36
258.66
508.73
1429.81
1429.81
1430.25
計算時間 (s)
1.31
0.51
10.62
1.85
0.75
8.41
3.96
1.59
51.23
3.09
4.02
227.25
2.38
5.99
92.18
1.20
7.59
10.73
14
3.07
8.13
$10$
$>10000$
12
9.56
71.19
$13$
$>10000$
12
$SWR_{const}$
$-26.87$
21
14.20
$SWR_{a11}$
$-47.50$
38
24.75
$-58.49$
$32$
$>10000$
3424.26
3410.92
3419.65
41
50
84.94
312.82
$51$
$>10000$
MISOCP
Crime
垣
333.22
339.44
333.22
MISOCP
392
11
11
9
14
9
15
19
15
$SWR_{const}$
$SWR_{a11}$
AutoMPG
$k$
$SWR_{const}$
$SWR_{a11}$
MISOCP
228
「手法」はそれぞれ
表 2 に，AIC 最小化の計算機実験の結果を示す．
$\bullet$
$\bullet$
$\bullet$
$SWR_{const}$
$SWR_{a11}$
: 初期変数集合が切片のみのステップワイズ変数選択
: 初期変数集合が全変数からのステップワイズ変数選択
MISOCP: MISOCP を用いた提案手法
を示し，AIC 値が最もよかった手法の値を太字で示してある．また
$k$
は選択された説明変数の個
数である．計算時間について，MISOCP の計算時間が 10000 秒を超えた場合は分枝限定法の計算
を打ち切っているため，その場合は得られた変数集合および AIC 値は最適解とは限らない．
計算結果を分析する．まず，二種類のステップワイズ法によって得られた解は，選択された変数
$SWR_{const}$
集合がかなり異なっていることがわかる．
と
$SWR_{a11}$
では
$k$
の値がかなり異なるほ力
$\searrow$
AIC 値が 20 以上異なり，これは無視できない差と言える．
$p<30$ であるような小さなデータセットに対しては，MISOCP は高速に最適解を計算で
次に，
特に Automobile では
きていることがわかる．また，大きなデータセットに対しては，10000 秒以内で最適解を求めるこ
とはできていないが，その場合でも二種類のステップワイズ法とほぼ同等またはそれ以上の解を出
$SWR_{const}$
力できている．特に Automobile では，
と
$SWR_{a11}$
の良い方と比較しても
AIC 値が 10
以上小さな変数集合を得ることができている．
一方で計算時間に関しては，MISOCP はステップワイズ法よりかなり長い時間を要している．
これは，ヒューリスティクスと厳密解法との違いではあるが，特に MISOCP では，分枝限定法の
実行中に解くべき連続緩和問題が
SOCP になり内点法が必要となるため，通常の線形整数計画問
題と異なり双対単体法を利用したホットスタートが働かない．これが計算時間増大の理由であると
考えられる．
5
まとめ
本稿では，AIC 最小化問題の混合二次錐整数計画問題 (MISOCP)
による定式化を提案した．ま
た，提案した定式化により計算機実験を実施し，ステップワイズ変数選択法との比較を行った．小
規模なデータセットに対しては，提案手法は高速に最適解を求めることができ，大規模なデータに
対してもステップワイズ法と同等またはそれ以上の解を求めることが可能なことを確認した．
参考文献
[1] H. Akaike, “A New Look at the Statistical Model Identification,” IEEE Transactions on
Automatic Control, Vol. 19, No. 6, pp. 716-723 (1974).
[2] F. Ahzadeh and D. Goldfarb, “Second-Order Cone Programming,” Mathematical Programming, Vol. 95, No. 1, pp. 3-51 (2003).
[3] K. Bache and M. Lichman: UCI Machine Learning Repository. University of California,
Scho of Information and Computer Science, Irvine, 2013. http://archive.ics.uci.edu $/m1$
$o1$
229
[4] E.M.L. Beale, “Two Thransportation Problems,” Proceedings
ference on
of the 3rd International Con-
Operational Research, pp. 780-788 (1963).
[5] E.M.L. Beale and J.A. Tomlin, “Special Facilities in a General Mathematical Programming System for Non-Convex Problems Using Ordered Sets of Variables,” Proceedings
the 5th International Conference on Operational Research, pp. 447-454 (1970).
of
[6] D. Bertsimas and R. Shioda, “Algorithm for Cardinality-Constrained Quadratic Optimization,” Computational optimization and Applications, Vol. 43, No. 1, pp. 1-22 (2009).
[7] E.J. Hannan and B.G. Quinn, “The Determination of the Order of an Autoregression,”
Journal of the Royal Statistical Society, Series , Vol. 41, No. 2, pp. 190-195 (1979).
$B$
[S] IBM ILOG, IBM ILOG CPLEX 12.5, 2012.
[9] 小西貞則，北川源四郎: 情報量規準．シリーズ予測と発見の科学 2, 朝倉書店，東京，2004.
[10] M.S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret, “Applications of Second-Order
Cone Programming,” Linear Algebra and its Applications, Vol. 284, No. 1, pp. 193-228
(1998).
2012.
[12] R. Miyashiro and Y. Takano, “Mixed Integer Second-Order Cone Programming Formu[11] The MathWorks Inc., MATLAB
$R2012b$ ,
lations for Variable Selection,” Technical Report, No. 2013-7, Department of Industrial
Engineering and Management, Tokyo Institute of Technology, 2013.
http: $//www$ . me. titech. ac.jp/technicalreport/h25/2013-7. pdf
[13] G. Schwarz, “Estimating the Dimension of a Model,” Annals
of Statistics, Vol.
6, No. 2,
pp. 461-464 (1978).
[14] N. Sugiura, “Further Analysts of the Data by Akaike’s Information Criterion and the
Theory and Methods, Vol. 7, No. 1
Finite Corrections,” Communications in Statistics
(1978), pp. 13-26.
–
[15] R.J. Wherry, “A New Formula for Predicting the Shrinkage of the Coefficient of Multiple
Correlation,” The Annals
of Mathematical Statistics,
Vol. 2, No. 4, pp. 440-457 (1931).

Download Report