グローバルマッチングでのsimilarity(類似性)(4)最適化マッチング手法

人工知能技術　ウェブ技術　知識情報処理技術　セマンティックウェブ技術   自然言語処理　機械学習技術 　オントロジー技術　オントロジーマッチング技術

前回は類似性を表す方程式のセットを用いた反復的な類似性計算アプローチについて述べた。今回はそれらを更に拡張した最適化アプローチについて述べる。今回はそれらの中からまず、期待値最大化と粒子群最適化の2つの手法について述べる。

期待値最大化(EM)
期待値最大化(EM)は，最尤推定問題に対する反復アプローチとなる(Dempster et al. 1977)。隠れマルコフモデルのように、観測データが欠損していたり、部分的にしか存在しない場合に、（パラメトリックな確率分布の）パラメータの推定に用いられ、最大の事後評価を行う。欠損データは，観測されたデータをもとに，条件付期待確率によって推定される。言い換えれば，欠損データは，その上に潜在的に有用な情報を推測することで強化される。そして，欠損データが既知であると仮定して，尤度関数を最大化する。つまり、EMの各反復は、Eステップと呼ばれる期待と、Mステップと呼ばれる最大化の2つのステップで構成され、Eステップで近似された尤度関数の連続した局所的な改善を最大化するものとなる。これは固定点法であり、各反復において尤度を増加させることで収束が保証される。

期待値の最大化の例。オントロジーマッチング問題は、(Doshi et al. 2009; Thayasivam and Doshi 2011) において最尤推定として扱われている。この方法では、隠れた変数として扱われる対応関係の欠落がある場合に、観測されたデータからアライメントの最尤推定値を探索する。Mをバイナリマッチマトリックスとする(行と列が一致するオントロジーのエンティティを表し、対応するセルには、一致した場合は「1」、そうでない場合は「0」が入力される)。この方法は、ターゲットのオントロジーo′と、マッチマトリックスMを介して行われたマッチ割り当てと、初期対応関係が与えられた場合に、ソースオントロジーoの最大条件付き確率P(o|o′,M)を提供するマッチマトリックスMを反復的に探索する。EMの用語では、各マッチ割り当て変数をモデルと見なし、したがってマッチマトリックスを混合モデルと見なす。Xは観測されたデータインスタンスのセット、Yは欠損値のセット、Mはマッチマトリックスまたは混合モデルであると仮定する。2つのEMステップは以下のように形式化される。

E-step E-stepでは、log-likelihoodの加重和を以下のように計算する。

\[Q(M^{i+1}|M^i)=\displaystyle\sum_{y\in Y}P(y|X,M^i)L(M^{i+1}|X,y) \]

ここで，iは反復番号，重みは隠れ変数（対応関係）の条件付き確率，L(Mⁱ⁺¹|X,y)は反復i + 1におけるモデルの対数尤度である．Lとlog(L)の最大値は同じであるため，計算を簡単にするために対数を用いている．初期のマッチシードと隠れ変数の確率は、用語の類似性や、「2つのエンティティがマッチする場合、その親ノードもマッチする可能性が高い」などの単純な構造的ヒューリスティックによって推定することができる。

M-step このステップでは、（E-stepの）期待対数尤度を最大化するパラメータが計算され、その期待値を最大化するマッチマトリックス（混合モデル）が選択される。実際には、一般化された期待値最大化法として知られているように、前のモデルを改善するだけの混合モデルを選択することで、最大化の条件を緩和することが多い。

\[ M_*^{i+1}\in {M:Q(M|N^i)\geq Q(M^i|M^i)}\]

そして、このマッチマトリックスは、次のEステップで隠れ変数の分布を決定するための入力となる。このように、EM法は、これらのモデルの対数尤度の加重和を最大化することにより、マッチマトリックス（混合モデル）を反復的に修正する。

粒子群の最適化(Particle Swarm Optimisation: PSO)
PSOは、非決定論的な最適化手法であり、群知能(Swarm Intelligence)に属する手法となる(Engelbrecht 2005)。PSOは、いつでも動作するメタヒューリスティックで、いつでも中断することができ、これまでに見つかった最良の結果を提供する。これは、鳥の群れや魚の群れなど、パーティクルと呼ばれる単純なエージェントのグループが、自分たちの住む環境に適応していく集合的な知性にヒントを得たものとなる（Kennedy and Eberhart 1995）。
粒子は、ランダムに生成された解答の初期群が与えられると、それまでに見た最良の解答を記憶して共有する。粒子群は、この共有された空間の情報に基づいて、解の空間上を移動（消去）する。このように、粒子群は有望な領域を探しながら解空間を探索していく。特に、パーティクルの動きは、速度ベクトルを用いて評価される。これらのベクトルは、個人的影響力成分として知られるパーティクルの個々のベストポジション（pBest）、および社会的影響力成分として知られるパーティクルのグループ全体の結果（gBest）に基づいている（簡略化して表示）。各反復において、パーティクルはpBestおよび/またはgBestに基づいて、より良い位置に向かってベロシティを変更します。このように、進化は最良のソリューションのみを探索します。PSOは、遺伝的アルゴリズムとは異なり、クロスオーバーやミューテーションなどの遺伝的操作を行わない。その代わり、粒子は速度ベクトルによって更新される。

PSOの例。 オントロジーマッチングは、離散型粒子群最適化（DPSO）ソリューションを用いて取り組む最適化問題と見なすことができる(Bock and Hettenhausen 2012)。DPSOは(Kennedy and Eberhart 1997)で紹介され、(Corea et al. 2006)では各粒子に可変次元性を使用することでさらに改良されている。最適化される目的関数はアラインメント品質となる。粒子はアラインメントの候補を表し、その次元はアラインメントにおける対応関係の数を表す。粒子は、記憶（pBest）と粒子間の通信（gBest）に基づいて、解空間における粒子の新しい位置を確立する速度ベクトルを使用することで、集団が事前に定義され、例えば50個の粒子で、事前に定義された数の反復（例えば200回）によって進化する。対応関係の評価は、フィットネス関数を用いて行われる。この目的のために、（2つのオントロジーのエンティティに適用された）様々な照合器の結果は、1つのフィットネス値に集約される。DPSOは、フィットネス関数に関して、グローバルベストアライメント(gBest)を返す。

この手法は基本的に3つのステップで構成されている。

1. 初期化：各粒子にランダムな数の対応関係を割り当て（正しい対応関係の数は事前にわからないため）、フィットネス関数で評価し、各粒子のpBestアライメントを計算する。
2. 群反復：新たに最適な粒子が現れた場合、グローバルに最適なアライメントgBestを更新する。
3. 速度ベクトルの更新では、収束性を確保するために、粒子のランダムな再初期化を制限する。具体的には、グローバルまたはパーソナルベストアライメントに存在する対応関係について、速度ベクトルの各成分を増加させる。これらは専用のパラメータで制御される：βは対応関係がpBestにある場合、γは対応関係がgBestにある場合、それぞれに対応する。これらの対応関係は、保存されるようにマークされている(したがって、繰り返しの中でランダムな再初期化によって置き換えられることはない)。これらの対応関係は、カスタマイズ可能なしきい値を用いて、粒子内で決して置き換えられない相関関係としてさらに促進することができる。各粒子のフィットネスおよび速度ベクトルの更新は、並行して計算することができる。

最適化手法のまとめ
アラインメントを最適化問題として計算するために、類似性尺度の品質を最適化する方法と、アラインメントの品質を直接最適化する方法の2種類の手法を紹介した。これらの例に限らず、どのような最適化手法を用いてもよい。このような手法をオントロジーマッチングに用いることはまだ始まったばかりであるが、問題を最適化問題として再定式化することができれば、すぐに使えるようになるだろう。
ここでは、計算された類似性やアラインメントに特定の解釈を与えるグローバルな手法を検討する。最初のものは、アラインメントに確率的な解釈を与えるものである。2つ目は、アラインメントとオントロジーのセマンティクスを利用する方法である。

次回は確率的手法について述べる。