株式会社NTTデータ数理システム

アルゴリズムと評価指標について

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. 石富 妙)。

バックナンバー一覧

バックナンバー Vol.4 2018 年 4 月 5 日発行

アルゴリズムと評価指標について

バックナンバー Vol.4　2018 年 4 月 5 日発行