アルゴリズムと評価指標について
BayoLinkSメールマガジン
【今回のテーマ】
構造学習アルゴリズムと評価指標について
一般的に、モデル構造を導き出すためには、データを元にアルゴリズムが複数のモデル候補を作成、
そして、その中で評価指標が最大となる構造を見つける、というステップを踏んでいます。
今回は、この 2 つのステップについてお話したいと思います。
◆モデルの構造アルゴリズムについて
まずは、モデル構造を導き出すアルゴリズムについてのお話です。
アルゴリズムは、データを元に複数のモデル候補を選び出す、という構造探索を行います。
しかし、データから考えられる全てのパターンを候補とすると、途端に計算量が爆発してしまいます。
そこで、構造探索においては、計算量を減らすための何らかの工夫が必要です。
ベイジアンネットワークにおける探索空間を減らす工夫としては、K2 アルゴリズムや
PC アルゴリズムなどがよく知られています。
BayoLink では K2 アルゴリズムをベースとする手法が実装されています。
各ノードについて親となり得る候補を指定 (★) すると、K2 アルゴリズムがある子ノードに対して
各親候補を一つづ加えてモデル構造を作成します。
そして、その構造を評価し、評価が高い場合はその親子関係を採用します。
すべての子ノードで上記を繰り返し、モデル構造を決定していきます。
★ 親候補は BayoLink 構造学習ウィザードの 2 ページ目で指定します。
また、全ての組合せを網羅的に探索するのではなく Greedy Search などの近似解法で構造探索を
行うことで、計算量を減らすことが可能です。
★ 構造学習ウィザードの 3 ページ目「アルゴリズム」で、Greedy Search、Stingy Search を
選択できます。
◆モデルの評価指標について
次に、モデルの評価指標についてお話します。
上記の方法では、各親候補をそれぞれ加えた際、モデル構造を評価する必要がありますが、
そこでは、評価指標を使います。
評価指標が最大となる構造が 1 番良いモデルである、と判断するのです。
ベイジアンネットワークの構造学習では、評価指標として、情報量規準がよく利用されます。
今回は、代表的な情報量規準である、ML, AIC について紹介したいと思います。
★ BayoLink の評価指標については『操作マニュアル (p.96)』に記載されています。
・ML 最大対数尤度 (Maximum log likelihood)
尤度関数を以下で定義すると
L(θ;X) = p(x1; θ) .... p(xn; θ)
これは パラメータ θ を与えたときの X の同時確率となります。
(x1, x2..xn は確率変数を表す)
対数をとって
lnL(θ;X) = Σ logp(xt;θ)
とした方が扱いやすくなります。ここで lnL が最大となるのが最大対数尤度 (ML) です。
ML はモデルを構成する各ノードのクロス集計より算出され、値が大きいほうがよい、とされます。
ML は 学習データに対するあてはまりの良さを評価します。
しかしモデルのパラメータ数 (BayoLink の場合は 条件付確率テーブルのサイズ) が大きいほど
ML は増加する傾向があり、この問題を考慮していないのが弱点となります。
・AIC (Akaike information criterion)
AIC は モデルの良さを測る規準で 1971 年頃に編み出されました。
以下の式で示されます。
AIC = -2lnL + 2M
lnL は モデルにおける最大対数尤度の値を表しており、M はモデルのパラメータ数です。
第一項はデータに対する当てはまりの良さを評価し、パラメータが増えることによるペナルティを
第二項で与えています。
AIC を最小化するモデルが最適なモデルとなります。
AIC は推定されたモデルの分布と真の分布との間の距離を表す KL (Kullback-Leibler) 情報量の
推定値の近似から導かれます。
このことにより、AIC は学習データのあてはまりの良さより、モデルが未知の状況を予測するのに
良いか、ということを表現します。
このように、評価指標を基準として、モデル構造が導き出されています。
★ BayoLink では、構造学習ウィザード 3 ページ目で「評価指標」を選択することができます。
いかがでしたでしょうか。ご参考になりましたら幸いでございます。
(2018.4.5. 石富 妙)。