交差検定法に基づく一般化情報量規準の近似計算

交差検定法に基づく一般化情報量規準の近似計算

Approximated Calculation for the Generalized Information Criteria

based on Cross Varidations.

力徳正輝

1,2∗

Masaki Rikitoku

1,2

1

_{(株) ジャストシステム イノベーティブテクノロジー研究開発部}

1

_{Justsystems Corporation Innovative Technology R&D Division}

2

_{九州大学大学院数理学府}

2

_{Graduate School of Mathematics, Kyushu University}

Abstract: We propose the approximated calculation for the Generalized Information Crite-ria(GIC) in which the influence function is approximately calculated based on cross validations. By this method, We can estimate the GIC for the L1 regularized log linear model and Support Vector Machine. The GIC for these models have never been estimated exactly.

The experiments shows that proposed approximated GIC is effective to estimate the valid regular-ized parameter for models.

1

はじめに

一般化情報量規準 (GIC) は、統計モデルを分布の汎 関数としてとらえ、その分布による変分を評価するこ とで、統計モデルのバイアス補正項を導出し、それに よって得られる情報量規準の 1 つである。 GICは、通常の最尤法だけでなく、罰則つき最尤法、 正則化項付最尤法に基づく統計モデルの情報量規準を も計算できる、最も一般的な情報量規準の 1 つである。 GICは、統計モデルのパラメータの分布に対する変 分である影響関数を解析的に評価し、導出し、バイアス 補正項を計算する。そのためモデルの目的関数に微分可 能性を要求し、Support Vector Machine(SVM) や L1 正則化項付モデル (Lasso) の場合、そのままでは GIC の計算ができない。 また、バイアス補正項の解析的評価の結果得られた GICの表式は、モデルの素性空間の次元サイズの行列 の逆行列を必要とする。そのため、高次元素性空間上 で定義されたモデルの場合、その逆行列の計算コスト は大きくなる。これらの点を改善するために、交差検 定法に基づく GIC の近似計算法を提案する。 本来、GIC は、モデルパラメータの経験分布に対す る変分を解析的評価することで影響関数を導出した。そ こで、経験分布に対する変分を有限微小変分によって ∗_{連絡先：(株) ジャストシステム イノベーティブテクノロジー研} 究開発部       〒 107-8640 東京都港区北青山 1-2-3 青山ビルヂング ジャストシステム東京支社        E-mail: [email protected]

近似し、影響関数を Leave One Out(LOO) 法による交 差検定法に基づいて近似計算する。そしてこの近似さ れた影響関数を使ってバイアス補正項を近似計算する。 通常、LOO 法による交差検定法は訓練データ数回の 学習処理を必要とし計算コストが非常大きい。そこで、 この計算コストが大きい問題を緩和するために、各交 差検定での学習のパラメータの初期値として、全訓練 データによって学習された最適パラメータを利用する。 交差検定の各ステップでの訓練データの分布の変化 は微小なので、最適解は、全訓練データによる最適解 付近の存在し、一般の初期値から、学習を実行する場 合に比べて学習処理コストの削減が期待できる。

2

一般化情報規準

(GIC)

本研究で考える統計モデルとは、素性ベクトル空間 上の点 x に対して確率値 p(x) を与えるものであり、具 体的には p(x) = f (θ· x + b). (1) である。f (z) は、個別の統計モデルに依存するが、本 研究では logistic 関数 f (z) = _1+exp(1 _−z) を考える。 統計モデルを決定する最適パラメータ ˆθ, ˆbはモデル の学習に対応する最適化問題によって決定される。 統計モデル p の GIC は次で定義される。[1] 人工知能学会研究会資料 SIG-DMSM-A803-14 (3/4)

GIC = −2 n X i=1 log(p(xi|ˆθ)) +2 n n X i=1 tr ( T(1)(xi; G) ∂ log(p(xi|θ 0 )) ∂θ0 ¯¯ ¯¯ ¯ θ0= ˆθ ) . (2) ここで、分布 G の汎関数 T の x における影響関数 T(1)_{(x; G)は} T(1)(x; G) = lim ²_→0 T((1− ²)G + ²Ix)− T(G) ² (3) で定義される。ここで、Ixは x における階段関数で ある。 (2)式からわかるように GIC は統計モデルの影響関 数を陽に求めることで計算できる。 正則化法 (罰則付最尤法) などの統計モデルの中で、 最適パラメータを決定する最適化問題の目的関数 L が、 パラメータに関して微分可能な場合、 上記の影響関数 T(1)を解析的に計算することができ て、その場合、GIC、バイアス補正項は陽に GIC =−2 n X i log p(xi; ˆθ) + 2tr © R(Ψ, G)−1Q(Ψ, G)ª. (4) と表される。ここで、R, Q は R = −1 n n X i=1 ∂Ψ ∂θ ¯¯ ¯¯ ¯ θ= ˆθ (5) Q = 1 n n X i=1 Ψ∂ log p ∂θ ¯¯ ¯¯ ¯ θ= ˆθ (6) Ψ = ∂L ∂θ (7) である。 一般に、正則化法に基づく統計モデルの GIC の計算 を実行しようとすると、R−1のように統計モデルのパ ラメター空間の次元サイズの行列の逆行列を計算する 必要がある。近年、活発に応用研究されている分野で は、モデルのパラメーター空間の次元が非常に大きい 場合がある。その場合に上式に基づく GIC の計算は、 計算機処理的に実行が困難になる。 また上式からわかるように、統計モデルの学習の最 適化問題の目的関数は全点で微分可能でなければなら ない。 これらの問題は、GIC の計算において、影響関数 T(1) の解析的な計算、導出の結果得られた明示的なバイア ス補正項の表式を用いているためである。 そこで、影響関数 T(1)_{を分布 G に対する変分とし} て解析的に計算せずに 表式 (3) を有限微小変化 ∆ と 経験分布 ˆGによって近似的に計算する。 すなわち、 T(1)(x) = T((1− ∆) ˆG + ∆Ix)− T( ˆG) ∆ , (8) で影響関数を近似する。 ここで、 ˆ G(x) = 1 n n X i=1 I(x, xi), (9) である、I(x, y) は階段関数である。 (8)式より、影響関数 T(1)_{を近似的に計算するには、} 訓練データ中のデータ xiに関して、分布を変化させ、 その分布に対しての統計モデルを作成、学習する一種 の交差検定法を実行する必要がある。

3

交差検定法に基づく

GIC

の計算

経験分布 ˆGの xiによる変動 ˆGi ˆ Gi = (1− ∆) ˆG + ∆I(x, xi) (10) として、確率密度関数による期待値計算は具体的には、 Z f (x)d ˆGi = 1 n n X j=1 (1− ∆)f(xj) + ∆δijf (xi) = n X j6=i 1 n(1− ∆)f(xj) + 1− (1 − n)∆ n f (xi) , (11) となる。つまり、影響関数の計算に表れる分布の変化 は、i 番目の訓練データに対する重みを増加させ、他の 重みを減少させ、学習を実行し最適パラメータを求め る、一種の交差検定法を実行しているとみなせる。こ の変動した分布 ˆGiに基づく最適パラメータの有限変 分によって影響関数を近似計算する。 このとき、変化した経験分布 ˆGiの汎関数である最 適パラメータは θ0 は、学習の最適化問題の解法アルゴ リズムにおいて ˆGiによる重み付損失関数、重み付尤度 関数として計算することで求めることができる。 さらに、全学習データ、経験分布 ˆGに基づく学習を 行いその結果最適パラメータが得られている場合、各 訓練データによる摂動による最適パラメータの変動は、 比較的微小だと考えられ、全訓練データによる最適解 の付近に摂動された最適解は存在すると考えられる。 そこで各交差検定のステップに対応する最適化問題に

関して、モデルパラメータの初期値を全体の最適モデ ルパラメータとすることで、計算コストを削減するこ とが期待できる。 よって、本研究で提案する統計モデルに対する GIC の近似的計算アルゴリズムは次となる。 交差検定法に基づく GIC の近似計算アルゴリズム 1. 全訓練データで統計モデルの学習を実行。モデル の最適パラメーターを取得 2. (11)式に基づいて訓練データ xiに関して、経験 分布 G を変化させ、最適パラメータを計算。こ の際、パラメータの初期値は全訓練データによる 最適パラメーターとする。 3. (8)式によって影響関数を近似計算する。 4. 近似された影響関数と (2) 式により近似 GIC を 計算する。 次節で、本研究の実験で使用した統計モデル、L1, L2 正則化項付 logistic 回帰モデルと、原理的に上記のアル ゴリズムを適用可能で、従来の厳密な GIC 計算を実行 できない Support Vector Machine(SVM) を簡単に説 明する。

3.1

L2

正則化項付 logistic 回帰モデル

logistic回帰モデルは p(y = 1|x) = 1 1 + exp(−(θ · x + b)), (12) で表される統計モデルである。 L2正則化項付 logistic 回帰モデルのパラメーター θ, b であり、学習の最適化問題の目的関数は L = −1 n n X i=1 log p(xi) + C 1 2|θ| 2 = − Z log p(x)d ˆG + C 1 2|θ| 2_{, (13)} となる。C がモデルの複雑度を制御する正則化パラメー タである。 この L2 正則化付 logistic 回帰モデルは、目的関数が パラメータに関して微分可能であり、厳密な手法によ り GIC が計算可能なモデルある。 上式の最適化問題は無制約の 2 次計画問題であり、解 法アルゴリズムとしては limited memory BFGS 法 [5] が実装も比較的簡易で、計算コストも比較的低いため によく使用されている。今回の実験においても、解法 アルゴリズムは limited memory BFGS 法を使用した。

3.2

L1

正則化項付 logistic 回帰モデル

L1正則化項付 logistic 回帰モデルの最適化問題は L = −1 n n X i=1 log p(xi) + C X i |θi| = − Z log p(x)d ˆG + C X i |θi|, (14) である。 L1正則化項付 logistic 回帰モデルの場合、目的関数 が原点で微分不可能な点を持つため、厳密な手法での GICが計算できない。 また、最適パラメータを決定する最適化問題の解法ア ルゴリズムとして、通常の降下法を利用した手法を適用 できないが、Andrew, Gao によって提案された orthant wise limited memory BFGS法 [3] により大規模データ に対しても、現実的な計算コストで最適パラメーターを 求めることができる。今回の実験においても、orthant wise limited memory BFGS法に基づく実装を用いて 実験を行った。

3.3

Support Vector Machine(SVM)

SVM[2]は線形カーネルを利用する場合は線形分類器 であり、logistic 関数により確率値を出力することで、 logistic回帰モデルともみなせる。 SVMの最適パラメータを求める最適化問題の目的関 数は L = C1 n n X i=1 Lsvm(xi) + 1 2|θ| 2 = C Z Lsvm(x)d ˆG +1 2|θ| 2_{, (15)} であり、最適化問題は制約式を持つ 2 次計画問題であ る。ここで、Lsvm(x) は、Hinge 損失関数であり、C は正則化パラメータである。 SVMは logistic 関数を用いて、logistic 回帰モデルと みなしても、損失関数が微分不可能な点を持っている 点、また、学習の最適化問題が、制約式を持つ 2 次計 画問題である点で、L1 正則化項付 logistic 回帰モデル と同じく、従来の方法では GIC 計算ができない。

4

実験

交差検定法に基づく GIC の近似計算法の有効性、近 似誤差等を測定するために、GIC 測定の実験を行った。 近似誤差を評価するために、厳密法によって GIC の 計算が可能な L2 正則化項付 logistic 回帰モデルに対し

て、厳密法、交差検定法による GIC の正則化パラメー タ依存を 2 つの 2 値分類データに対して実行した。 また、厳密法によって GIC の計算ができない L1 正 則化項付 logistic 回帰モデル, SVM に対しても有効性 を検証するために、同じデータを使用して GIC の近似 計算を実行した。 GICの値による正則化パラメータの決定に関する有 効性を評価するために、同時に 5-fold の交差検定法に より、正例の適合率、再現率から F1 値精度指標を測 定、GIC との比較を実施した。

4.1

測定環境

実験データには libsvm のサイトで公開されている 2 値分類データ a1a, w1a を使用した。[4] データ データ数 正例数 次元 a1a 1605 395 123 w1a 2270 66 300 表 1: a1a, w1a データ L1正則化項付 logistic 回帰モデルの学習には、An-drew, Gaoによる orthant-wise limited memory BFGS アルゴリズムの C++実装を java に移植した実装を使 用した。[3]

L2正則化項付 logistic 回帰モデルの学習には、上記 の orthant-wise limited memory BFGS アルゴリズム に変更を加えた limited memory BFGS アルゴリズム の実装を使用した。全ての測定で、limited memory の サイズを 10 に設定した。

SVM の実装には、一般的に使用されている SVM packageである libsvm [4] の java 実装と基本的に同じ である独自 java 実装を使用した。なお、libsvm からの 変更点は基本的に、shrinking heuristic を利用しない、 各訓練データの重みを考慮する点のみである。 交差検定法に基づく GIC の計算で使用される重み付 損失関数の計算は、L1, L2 正則化付 logistic 回帰モデ ルの学習アルゴリズムの損失関数の計算で各学習デー タの重みを考慮するように変更実装を行った。 SVMでは、重み付損失関数の計算は、正則化パラ メータ C に重みを乗じることに対応するので、各訓練 データに依存する C パラメータを表現するように変更 実装を行った。 本文書で扱った、交差検定法による GIC の近似計算 法で使用した微小数 ∆ は 10−5に設定した。 最適正則化パラメータの決定の目安となる、正例 F1 値精度指標の測定には、L1, L2 正則化項付 logistic 回帰 モデルは、実験で使用した独自実装を利用した。SVM は、オリジナルの libsvm とその交差検定オプションを 使用して測定した。

4.2

測定結果

4.2.1 L2,L1正則化項付 logistic 回帰モデルの測定 結果 L2正則化項付 logistic 回帰モデルに対する厳密法、 近似法による GIC、交差検定 F1 値の測定結果を 表 2: 表 3:に記載する。 C 厳密 GIC 近似 GIC F1値 1.0× 10−3 546.5 553.0 63.66 1.0× 10−2 547.6 551.3 63.91 1.0× 10−1 553.2 551.7 63.72 1.0 580.0 553.4 62.88 1.0× 101 _{615.5 566.3 58.89} 1.0× 102 689.1 647.1 41.98 1.0× 103 830.9 916.3 -表 2: a1a データによる L2 正則化項 logistic 回帰モデ ルの測定結果 C 厳密 GIC 近似 GIC F1値 1.0× 10−3 37.68 37.32 51.06 1.0× 10−2 47.76 45.81 59.01 1.0× 10−1 69.44 64.02 57.40 1.0 149.2 117.3 41.30 1.0× 101 378.7 200.7 14.08 1.0× 102 _{560.1 270.0 0.0} 1.0× 103 _{390.0 - 0.0} 表 3: w1a データによる L2 正則化項 logistic 回帰モデ ルの測定結果 表 2:, 3:から、交差検定法に基づく近似 GIC は、厳 密法による GIC とほぼ同じ値をとっていることがわか る。また、a1a データは GIC 最小に対応する正則化パ ラメータ付近で F1 値も最大となっており、GIC 値が モデル選択に有効であることがわかる。 一方、w1a データでは a1a データに比べて最大 F1 値 に対応する GIC と、最小 GIC との差が比較的大きい。 これは、w1a データが、正例数が負例数に比べて少な く、モデル選択には θ パラメータの複雑さよりも b パ ラメータのバイアスの方が大きく寄与しているためだ と考えられる。今回の、GIC 計算においては、b パラ メータのバイアス補正は考慮されていない。

C 近似 GIC F1値 1.0× 10−3 557.5 63.73 1.0× 10−2 563.6 63.92 1.0× 10−1 541.4 63.90 1.0 549.3 62.23 1.0× 101 _{576.7 55.92} 1.0× 102 _{846.5 0} 1.0× 103 _900.4 -表 4: a1a データによる L1 正則化項 logistic 回帰モデ ルの測定結果 C 近似 GIC F1値 1.0× 10−3 32.13 47.88 1.0× 10−2 35.83 51.51 1.0× 10−1 52.14 60.86 1.0 118.1 46.93 1.0× 101 _{272.2 0} 1.0× 102 _{300.2 0} 1.0× 103 300.1 0 表 5: w1a データによる L1 正則化項 logistic 回帰モデ ルの測定結果 厳密法では、GIC の計算が困難な、L1 正則化項付 logistic回帰モデルに対する、近似 GIC 値、交差検定 F1値を表 4:, 表 5:に記載する。 L2正則化項付 logistic 回帰モデルの場合と同じく、 a1aデータでは最小 GIC と最大 F1 値に対応する正則 化パラメータは比較的合致しているのに対して、w1a データでは、その差が大きい。 4.2.2 SVMの測定結果

SVMに対しても、近似 GIC 測定、libsvm tool によ る 5-fold 交差検定 F1 値の測定を行った。表 6:, 表 7: の結果によると、最小近似 GIC に対応する正則化パラ メータ C は、最大 F1 値に対応しており、近似 GIC に よるモデル選択が有効に働いていることが見て取れる。 C 近似 GIC F1値 1.0× 10−3 863.24 0 1.0× 10−2 681.08 44.36 1.0× 10−1 595.29 60.17 1.0 577.46 62.51 1.0× 101 _{611.91 61.80} 表 6: a1a データによる SVM の測定結果 なお、SVM に対する近似 GIC の測定には、特別な heuresticを使用したので説明する。 まず、非サポートベクターに対応する交差検定のス テップは省略した。これは、非サポートベクターの重 み (=准頻度) を大きくしても、他の重みがほぼ一定で あれば、学習結果が変わらないという事実に基づいて いる。他の重みがほぼ一定であるたみは、∆× C が微 小量である必要がある。そのため、SVM の測定に対し ては C× ∆ = 10−5になるように設定した。

5

むすび

本研究で、交差検定法に基づく GIC の近似計算法を 提案した。この手法は、モデルの学習の最適化問題の 目的関数に、微分不可能な点を含む場合でも GIC の計 算が可能であるメリットを持つ。また、厳密法による GICで必要とされる素性空間の次元サイズの逆行列計 算を含まないため、超高次元の素性空間で定義される 統計モデルにも適用が簡易である点もメリットである。 近似誤差や、最小 GIC のモデル選択の有効性を検証 するために、2 種類のデータセットに対して、厳密法、 近似法による GIC 値と 5-fold の交差検定法による F1 値を測定した。 その結果、厳密な GIC 値の計算が可能な L2 正則化 付 logistic 回帰モデルに対しては、近似法による GIC 値はほぼ厳密値と同じ値を取ることがわかった。また、 交差検定法による最大 F1 値により、θ パラメータの複 雑さが最適モデル選択、最適正則化パラメータ選択に 関して大きく寄与していると考えられる場合には厳密、 近似法による GIC 値による選択が有効であることが示 された。 本研究で提案した GIC の近似計算法は、交差検定法 に基づく手法であり、訓練データ数回の学習を必要と する。その際に全訓練データに対する最適パラメータ 値を各交差検定に対応する学習の最適化問題の初期値 とすることで、学習処理コストの削減を計っているが、 それでも一般に学習処理コストは大きいと思われる。 この手法が、最も有効なのは、次元の大きい素性空 C 近似 GIC F1値 1.0× 10−3 773.35 0 1.0× 10−2 740.22 0 1.0× 10−1 597.10 35.00 1.0 374.94 58.40 1.0× 101 _{259.08 59.50} 1.0× 102 345.09 55.40 表 7: w1a データによる SVM の測定結果

間上で定義された L1 正則化項付の統計モデルを比較 的少数の訓練データで学習する場合だと考える。 その場合、厳密法による GIC の計算は困難であり、 また、訓練データ数が少ない場合は、交差検定法に基 づく近似 GIC の計算コストも比較的小さいと考えられ るためである。その場合には、確率的漸近性に基づく GICの適用妥当性の問題を別途考える必要があるが、 その点に関しては今後の研究課題としたい。

謝辞

L1正則化項付統計モデルと GIC に関して、有益な コメント、議論をしていただいた九州大学の小西貞則 教授、松井秀俊両氏に謝意を表します。

参考文献

[1] Konish, S. and Kitagawa, G., Generalised infor-mation criteria in model selection, Biometrika, Vol. 83, No. 4, pp. 875–890 (1996)

[2] Cortes, C. and Vapnik, V., Support-vector net-works, Machine Learning, Vol. 20, No. 3, pp. 273–297 (1995)

[3] Andrew, G. and Gao, J., Scalable training of L 1-regularized log-linear models, Proceedings of the 24th international conference on Machine learn-ing, pp. 33–40 (2007)

[4] Chang, C.C. and Lin, C.J., Software available at http://www.csie.ntu.edu.tw/cjlin/libsvm, [5] Liu, D.C. and Nocedal, J., On the limited

mem-ory BFGS method for large scale optimization, Mathematical Programming, Vol. 45, pp. 503– 528 (1989)