similarity(類似性)マッチング手法での戦略(6)アライメントの抽出アプローチ

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

前回に引き続きオントロジーマッチングより。前回はアライメントのチューニングのアプローチについて述べた。今回はアライメントの抽出アプローチについて述べる。

アライメントの抽出
マッチングの目的は、オントロジー間の十分な対応関係のセットを特定することにある。両オントロジーのエンティティ間の（非）類似性測定により、対応関係の大きなセットが得られる。結果的にアライメントの一部となるものは、類似性に基づいて抽出する必要がある。これは、類似性マトリクスに作用する特別な抽出方法、または既に抽出された事前整列に作用する方法によって達成することができる。ここでは、（非）類似性行列をアライメントに変換する抽出器自体と、対応関係の候補をこれらのフォーマットのいずれかに縮小するフィルタを区別する。これは、図7.14に描かれている。

類似性フィルターは、例えば、ある閾値以下のセルをゼロにしたり、閾値以上のセルをユニット化したりすることで、（非）類似性マトリックスを変換する。アライメント抽出器は、類似性マトリックスからアライメントを生成する。これがこのセクションのメイントピックである。アライメントフィルターは、類似性フィルターと同じ種類の操作を使用して、アラインメントをさらに操作することができる。
ユーザーはアライメントフィルターとして機能することができる。アライメントは、エンティティペアをその類似性スコアとランクとともに表示し、適切なペアの選択をユーザーに委ねることで得られる。このユーザーの入力は、ヘルパー環境における決定的なアンカーとして、システムを助けるためのアンカーの定義として、あるいは学習アルゴリズムにおける関連性のフィードバックとして受け取ることができる。
さらに一歩進んで、類似性スコアからのアラインメント抽出を自動化するアルゴリズムを定義することも可能である。この課題には、対象となるアライメントの特性に応じて、様々な戦略を適用することができる。
この問題は以下のように定義できる。

定義 7.25 (アライメント抽出問題) 
二つのエンティティの集合 o と o′
と類似関数σ : o × o′ → [0 1] が与えられたとき、
アライメントA ⊆ o × o′ を抽出する。

この問題文は、o × o′がこの問題の解であるため、制約が不足している。そこで本節では、アライメント抽出の問題をさらに制約する方法を考える。そのための一つの指針として、前節でアラインメントの全体性制約と注入性制約を紹介した。
我々は、ある閾値以降の（非）類似度のトリミングと、抽出されたアラインメントの最適な全体の（非）類似度の決定に基づく2つの主な戦略を提示する。また、その間に、マッチング・アルゴリズムで有用とされている一種のフィルターを紹介する。

しきい値
どちらのオントロジーもアライメントで完全にカバーする必要がない場合、閾値ベースのフィルタリングでは、最も類似したエンティティペアのみを保持します。注入性の制約がなければ、閾値以上のスコアを持つペアは、賢明なアライメントを表す。

したがって、閾値を適用するには、抽出されたアラインメントが十分な品質であることが必要である。より簡単な方法は、ある特定の閾値以上の対応関係を選択することである。いくつかの方法が文献に記載されている(Do and Rahm 2002; Ehrig and Sure 2004)。

Hard threshold(ハード閾値) は、スレッショルドn以上の対応関係を全て保持する。
Delta threshold(デルタ閾値) は、特定の定数値nを差し引いた中で最も高い類似性の値を閾値として使用する。
Gap threshold(ギャップ閾値) は，類似度の低い順に並べられた対応関係を，2つの対応関係の間の類似度の差が大きくなるまで保持する．
Proportional threshold(比例閾値) は，最も高い類似度の値のパーセンテージを閾値として使用する。
Percentage(パーセンテージ) は、n %の対応関係を他の対応関係よりも保持する。

Rondoシステムは、独自のアライメント抽出方法（SelectThreshold）を提供しており、各ノードの類似度を他のノードとの最良の類似度で正規化する（結果はもはや対称的ではない）。そして、両ノードの正規化された類似度がある定義された閾値以上であるノードのペアをアライメントのために選択する。

しきい値法の例　Multidimensional Distances and Weighted Sumsの例で得られた1/4-3/4の重みを持つ加重和距離からスタートする。

この距離を次の表のように類似度に変換する。

• -ハード閾値を0.23とすると、⟨Provider, Publisher, =⟩、⟨Creator, Writer, =⟩、および⟨Creator, Translator, =⟩が対応するものとして選択される。
• 同じ0.23の値を持つデルタ閾値では、最初の2つだけが選択され、対応するハード閾値は0.75 – 0.23 = 0.52となる。
• ギャップ閾値を0.23とすると、0.69-0.25＞0.23となるため、同じ2つの対応関係が選択される。
• 逆に、比例しきい値を0.23とすると、ハードしきい値は0.75×0.23＝0.17となり、上記の3つに加えて、⟨Product, Book, =⟩が選択される。
• percentage thresholdの.23は、最初に選択された12×23%≒3のペアを選択することになる。
• しきい値を.23としたSelect Threshold法でも、上述の4つの対応関係のセットが得られる。

強化と弱体化
(Ehrig and Sure 2004）のように、0.と1.の間のシグモイド関数（siga(x) = 1/(1 + e-a(x-0.5))、aは傾きのパラメータ）を使用するアプローチもある。これにより，0.5よりも高い値を強化し，0.5よりも低い値を弱めることができる。この処理は、正の対応と負の対応の2つのゾーンを明確に分けるためのものである。

1-sin(arccos(x))のような他の関数は、逆の効果をもたらすことがある。つまり、結論の出ていない測定値をディスカードし、最も高い測定値を単位間隔でディスパッチする。この処理は、非常に似ているものは確かに似ているが、緩やかに似ているものは結論の出ない結果を与えることを考えると、十分に正当化される。もちろん、これらの関数をシフトして、0.5以外の閾値を選択することも可能となる。
強化と弱化の弱化の例　 前述の例の類似表をシグモイド関数である2つの関数でフィルタリングしたものが以下の2つの表となる。

シグモイド関数は，最良のマッチングには高い値を，悪いマッチングには低い値を与えるが，他の提案された関数では，0.75よりも高い類似度でないと選別できず，すべての値が減少してしまう。

結果の最適化
注入型アライメントが必要な場合、アライメントの品質を最大化するためにいくつかの選択を行う必要がある。この品質は通常、一致したエンティティペアの合計類似度で測定される。そのため、マッチングアルゴリズムは、各エンティティペアの局所的な類似性を最大化するのではなく、グローバルな基準を最適化する必要がある。
要約すると、アライメントの計算は、基本的なセットの類似性関数MSimの制約の少ないバージョンと見なすことができる。実際、その目標特性は、(1)最大のグローバルな類似性、(2)排他性、(3)最大のカーディナリティ（対応関係にあるもの）という点で同じである。ただし、(2)と(3)は必須ではなく、それぞれ注入性と全体性の要件に依存する。類似性テーブルからアライメントを抽出する方法は、一般的にはグラフマッチング（Berge 1970; Lovász and Plummer 1986）と呼ばれるもので、より正確には加重二部グラフマッチング（注入性アライメントの場合）またはカバリング（全体性アライメントの場合）となる。

グリーディなアライメント抽出アルゴリズムでは、対応関係を段階的に構築し、各段階で最も類似したペアを選択し、そのメンバーをテーブルから削除することができる。アルゴリズムは、類似度が閾値を超えるペアが残っていないときに停止する。グリーディな戦略は最適ではない。しかし、高い類似性を忘れて低い類似性が有利になるという根拠には疑問があり、状況によっては欲張りなアルゴリズムが好ましい場合もある。

この文脈では、2つの集合の最適なマッチングには2つの概念がある。1つ目は安定した結婚と呼ばれる局所的な最適で、2つ目は最大重みマッチングと呼ばれる大域的な最適となる。 安定した結婚とは、（第1の集合の1つのオブジェクトだけを第2の集合の1つのオブジェクトに）割り当てることであり、異なる対応関係にあるエンティティのペアで、両者が対応関係に置かれることを好むものが存在しないようなもの、すなわち、これら2つのエンティティ間の類似性が、それぞれが対応関係にあるエンティティと持つ類似性よりも高いものとなる。安定した結婚を計算するアルゴリズムとしては、Gale-Shapleyアルゴリズム(Gale and Shapley 1962)や、上で紹介したグリーディアルゴリズムがある。

定義 7. 28 (安定した結婚問題) 
2つの実体の集合oとo′、および類似性関数σ : o × o′ → [0 1] が与えられたとき、
任意の⟨p,q⟩∈Mと⟨r,s⟩∈Mに対して、
σ(p,q)≧σ(p,s)またはσ(r,s)≧σ(p,s)となるように、
M⊆ o × o′から一対一のアライメントを抽出する。

グリーディアルゴリズムでは、見つかった解が安定した結婚であることが保証されている。しかし、私たちは少し異なる問題を導入した。それは、2つの割り当ての任意の順列が、より悪い結果を提供するという制約となる。

定義 7. 29 (ペアワイズ・マキシマム・マッチング問題) 
2つのエンティティのセットoとo′，および類似性関数σ : o × o′ → [0 1] が与えられたとき、
M⊆o×o′から、任意の⟨p,q⟩∈Mと⟨r,s⟩∈M,σ(p,q)+σ(r,s)≧σ(p,s)+σ(r,q)となるような
一対一のアライメントを抽出する。

ペアでの最大割り当ては必ずしも安定した結婚ではなく、その逆もまた然りです。
第2の概念は、大域的最適、または最大ウェイトマッチングとなる。これは、より良い重み付けを持つ他の割り当てが存在しない割り当てとなる。これはハンガリアン法(Munkres 1957)によって計算される。

定義7.30（最大重みグラフマッチング問題） 
2つのエンティティーの集合oとo′、
類似性関数σ : o × o′ → [0 1]が与えられたとき、
M⊆ o × o′から一対一のアライメントを抽出し、
任意の一対一のアライメントM′⊆ o × o′に対して、
次のようにする。

\[ \displaystyle\sum_{<p,q>\in M}\sigma(p,q) \geq \sum_{<p,q>\in M’}\sigma(p,q)\]

重みが類似性ではなく非類似性を表す場合、解くべき問題は双対の最小重みグラフマッチングとなる。
安定した結婚、ペアごとの最大重みと最大重みのマッチングの例  下図の概念に対する以下の類似性表を考えてみる。

一対一のアライメントを抽出したい。

欲張りなアルゴリズムは、まず最高得点（0.90）の対応関係「⟨Product,Publisher⟩」を選択し、対応する行と列を破棄する。そして、次にスコアの高い（.84）「⟨Creator,Writer⟩」を選択し、残りの最良のもの「⟨Provider,Book⟩」を選択する。この結果は明らかに安定した結婚となるが（選択されたすべてのペアが対称的な個人の好みによって壊れることがないことをチェックすることは課題として残されている）、ペアごとの最大マッチングではない。これら3つの対応関係から作られたアライメントのスコアは1.96となる。
しかし、もっと良いアライメントもある。例えば、最後の2つの要素を⟨Creator, Book⟩と⟨Provider, Writer⟩に置き換えることで、スコア2.1のアライメントが得られる。このアライメントはペアワイズ最大化であるが、安定した結婚ではない。

これは、⟨Product,Book⟩、⟨Provider,Publisher⟩、⟨Creator,Writer⟩で構成されており、スコアは2.52となる。このアサインメントはペアワイズ最大化ですが、安定した結婚ではない。

アライメント抽出のまとめ
アライメントの抽出は、通常、類似性ベースのマッチングに必要なステップとなる。これまでに紹介した手法は、どのような類似性や非類似性の尺度にも適用できる。閾値を適用するような単純なものから、最適化問題を解くような高度なものまで様々になる。これらの手法を選択するための絶対的な基準はない。重要な基準は，期待される最終結果の形式となる。

次回はアライメントの曖昧性解消について述べる。