similarity(類似性)マッチング手法での戦略(3)重み付けによる選択アプローチ

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

前回はオントロジーマッチング戦略の一つであるコンテキストベースのマッチングについて述べた。今回は別のアプローチのひとつである重み付けによる選択に対して述べる。

類似性とアライメントの集約
前節で示したように、類似性を集約することで、マッチャーの構成を実現することができる。この集約は、異なるマッチャーから提供された類似性を取り、それらを単一の類似性にまとめる。マッチャーには、同じタイプのエンティティをそれぞれの類似性の異なる評価でマッチングさせる競合型と、異なるタイプのエンティティの類似性を特定する補完型がある。これらはそれぞれ異なった形で集約されなければならない。本節では、重み付け(マッチャーに異なる重みを与えて類似性を算術的に結合するもの)、投票、論証の3種類の集約を挙げている。

重み付け
複合的な類似性は、異質な類似性の集約に関するものとなる。前節で説明したように、構造化されたオブジェクト（クラス、個人）は、多くの異なる関係に関与していることが多いため、2つのオブジェクトが関係しているオントロジーエンティティのそれぞれの間の類似性を計算することができる。例えば、2つのクラスの類似性は、それらの名前から得られる類似性、それらのスーパークラスの類似性、それらのインスタンスの類似性、およびそれらのプロパティの類似性に依存する。これらの類似性は、1つの類似性測定に集約されなければならない。

Triangle Norm(三角ノルム)
三角ノルムは不確実性計算の接続演算子として使用される。

定義 7.3 (三角ノルム) 
三角ノルム T は，D × D → D 
(D は ≤ で順序付けられた集合であり，上界⊤が与えられている) 
からの関数であり，以下の条件を満たす．

\[\begin{eqnarray} T(x,T)&=&x \ &(boundary\ condition)&\\ x\leq y \ &\Rightarrow& \ T(x,z)\leq T(y,z) \ &(monotony)&\\T(x,y)&=&T(y,x) \ &(commutativity)&\\T(x,T(y,z))&=&T(T(x,y),z) \ &(associativity)& \end{eqnarray} \]

典型的な三角ノルムの例はmin(x,)、x x y、max(x + y – 1, 0)となる。すべては規格化されている。minは、唯一のidempotent normとなる（∀x, min(x, x)=x）。三角ノルムは、すべての集約された値から最高のスコアを必要とする組み合わせの候補となる。連想性により、三角ノルムはn-ary測度に拡張することができる。単位区間上の任意の三角ノルムは、これら3つの関数の組み合わせとして表現できる(Hájek 1998)。
複数の次元を集約するためのもう一つの三角ノルムは、Weighted product(加重積)となる。

定義 7.4 (Weighted Product) 
oをn次元で分析可能なオブジェクトの集合とすると、
そのような2つのオブジェクト間の加重積は、∀x, x′∈oとなる。

\[\delta(x,x’)=\displaystyle \prod_{i=1}^n \delta(x_i,x’_i)^{w_i}\]

δ(x_i,x_i′)はi次元におけるオブジェクトのペアの非類似度、w_iはi次元の重みとなる。
これらの演算子は、ある次元の尺度が0であれば、結果も0になってしまうという欠点がある。
三角ノルムの例。このセクションでは、1つ目のオントロジーはProduct, Provider, Creator、2つ目のオントロジーはBook, Translator, Publisher, Writerの概念からなる2つのオントロジーを考える。以下の2つの表は、これらのラベルに編集距離とWordNetベースの距離を適用した結果を示している。

次の表は、これらの距離を三角ノルムで集計したもの、つまりmin演算と加重積を表示したものとなる。

最初の表のデータの類似性は互いにあまり似ていないが、三角ノルムで集計したものでは非常に似た結果となる。
多次元アグリゲータとは逆に、三角法は異なる次元の値の間に依存性を示唆する傾向があり、ある次元で与えられた値が他の次元の値を上書きすることができる。

多次元距離と重み付けされた総和
いくつかの特性の違いを集約する必要がある場合、最も一般的な距離の種類の1つがMinkowski距離である。前述のものとは異なり、これらの尺度は独立した次元に適しており、次元間の値のバランスをとる傾向がある。

定義 7.6 (Minkowski distance) 
oをn次元で分析可能なオブジェクトの集合とすると、
そのような2つのオブジェクト間のMinkowski距離は∀x, x′∈oである。

\[\delta(x,x’)=\sqrt[p]{\displaystyle\sum_{i=1}^n\delta(x_i,x’_i)^p}\]

δ(x_i,x_i′)はi次元におけるオブジェクトのペアの非類似度である。
ミンコフスキー距離の例としては、ユークリッド距離（p = 2の場合）、マンハッタン（別名シティブロック）距離（p = 1の場合）、チェビシェフ距離（p = +∞の場合）などがある。これらは、独立した次元の測定値を集約する際に使用する。
ミンコフスキー距離の例。前述のmin集約演算子でラベル上に計算された距離と、概念のインスタンスの集合上のハミング距離から得られた距離から始める。これらの距離は通常、独立した次元を考慮している。

この2つの距離を、（正規化された）ユークリッド距離とマンハッタン距離を用いて集計すると、以下のようになる。

ユークリッド距離の値は、マンハッタン距離の値よりも低いが、非常に近い値を示している。
これらの距離は、いくつかのディメンションをより重要視するために重み付けすることができる。これらの距離は、その結果を最大可能距離で割ることで正規化することができる（これは必ずしも可能ではない)。しかしながらp≠1の場合、線形ではないという主な欠点がある。これは、これらの距離が互いの関数として定義されている場合に、これらの距離を見つけようとする際の問題の原因となる(Valtchev 1999)。
単純な線形集約は、この和に重みを加えることでさらに洗練される。重み付き線形集約では、集約される値の重要性が同じでないことを考慮する。例えば、プロパティの類似性は、コメントの類似性よりも重要である。そのため、集約関数は、クラスやプロパティなどのエンティティのカテゴリに対応する重みw₁,…,w_nのセットを使用する。集約関数は以下のように定義できる。

定義 7.8 (Weighted sum) 
oをn次元で分析可能なオブジェクトの集合とすると、
そのような2つのオブジェクト間の加重和は∀x, x′∈oとなる。

\[\delta(x,x’)=\displaystyle\sum_{i=1}^nw_i\times \delta(x_i,x’_i)\]

δ(x_i,x_i′)はi次元におけるオブジェクトのペアの非類似度、w_iはi次元の重みである。

加重和は，マンハッタン距離を一般化し，各次元に重みをつけたものと考えることができる。また，これは，正規化された重みを持つ加重平均にも相当する。実際，重みは，集約されるオブジェクトのカテゴリに応じて異なることがある。そして，この関数は，オブジェクトのカテゴリに依存する重みのセットwCPを使用することができる。 また，Candは，計算されたPの価値の種類を表す。
この種の尺度は，すべての値が正規化されている場合，次のようにして(\(\sum_{i=1}^n w_i=1\))正規化することができる。

例加重和の例。 前例から、インスタンスに関する尺度はラベルに関する尺度よりも正確であるように見える。これは、両方のラベルセットに共通の名前がないことや、後者の場合に距離が低いことから推測できる。このように、これらの次元に重み付けをすることは有望となる。前例と同じ入力セットを考えてみたとき、計算された加重和は以下のようになる。

上記の結果から、⟨Provider, Publisher⟩と⟨Creator, Writer⟩が一致候補として明確になった。ProductとBookの類似度が低いため、マッチ候補として選択することができない。

ファジー集計と加重平均
ファジー集約演算子は、集約されたドメインの構造を保持する方法で、同種の量を同化するために使用される。

定義 7.10 (ファジー集計演算子) 
ファジー集計演算子 f は、Dn → D (D は ≤ で順序付けられた集合で、
上界⊤が与えられている)からの関数で、
∀x, x1, ... ... , xn, y1, ... ... を満たすものである。,
 xn, y1, .. . , yn ∈Dは以下の条件を満たす。

\[\begin{eqnarray} f(x,\dots,x)&=&x \ &(idempotency)&\\ \forall x_i,\ y_i,x_i\leq y_i&\Rightarrow& f(x_1,\dots,x_n)\leq f(y_1,\dots,y_n)&(increasing\ monotony)&\\f \ is\ a\ &continuous&\ function\ &(continuity)&\end{eqnarray}\]

minもファジィ集約関数である。これらの尺度に関する一般的な結果は，任意のファジー集約関数fに対して，集約はf (x , y ) ≧ min(x, y) ≧ x × y ≧ max(x + y – 1, 0)で順序付けられるというものとなる。ファジー集計演算子の典型的な例は，加重平均となる(Gal 2011)．

定義 7.11 (加重平均) 
oをn次元で分析可能なオブジェクトの集合とすると
そのような2つのオブジェクト間の加重平均は、∀x, x′∈oとする。

\[\delta(x,x’)=\frac{\sum_{i=1}^nw_i\times\delta(x_i,x’_i)}{\sum_{i=1}^nw_i}\]

δ(x_i,x_i′)は，i次元におけるオブジェクトのペアの非類似度であり，w_iはi次元の重みとなる。
単純平均関数は，すべての重みが等しくなるような関数となる。．値が正規化されていれば、加重平均も正規化されている。実際，正規化された加重和は，加重平均でもある。
ファジー集約関数は、競合するアルゴリズム(ある側面に関しては効率的だが、他の側面に関しては効率的ではない)の結果を集約し、それらのすべてを活用しようとする場合に使用しなければならない。これらは、測定値の重みを学習するために学習アルゴリズムを使用したい場合に非常に有用となる。(Gal et al. 2005a)は、信頼度測定値を集約するためには、これらの測定値が三角ノルムよりも常に好ましいと主張している。
LCSや MoToなどのいくつかのシステムでは、ファジィ集約関数を定義するために、「most of」などの言語的な量詞 (Yager 1988, 1993) からヒントを得ている。

ハーモニック適応型加重和
(Mao et al. 2010) は，異なるマッチャーを重み付けするために，調和的適応加重和の概念を導入した．この演算では、より識別性の高いメジャーに高い重みを与える。この演算子は、各メジャーについて、類似度が同じ行と列の他のすべてのセルよりも劣る（非類似度の場合）行列のセルの比率を、可能な限り最大の値（最小のオントロジーのサイズ）で計算する。

定義7.12 (ハーモニック適応型加重和) 
oとo′をn個の尺度で比較できる2つの対象物の集合とすると，
そのような2つの対象物の間の尺度の調和的適応加重和は，∀x∈o, x′∈o′である。

\[\delta(x,x’)=\displaystyle\sum_{i=1}^n h(\delta_i)\times\delta(x,x’)\]

δi(x,x′)は、i番目の尺度に沿ったオブジェクトのペアの非類似性の尺度であるようなものです。
尺度であり、hは次のようなものとなる。

\[h(\delta_i)=\frac{|\{\begin{eqnarray}<e,e’>\in o \times o’;∧\begin{cases}\forall y \in o’ | {e’},\sigma(e,y)\gt \sigma(e,e’)\\ \forall x \in o | {e},\sigma(x,e’) \gt \sigma(e,e’)\end{cases}\end{eqnarray}\}|}{min(|o|,|o’|)}\]

この尺度は、結果を重みの合計で割ることで正規化できまる。この指標は、より識別性の高い類似性または距離を優先する。

順序付き加重平均
ここでのもう1つの集計演算子は，順序付き加重平均となる(Yager 1988)．これは，次元そのものではなく，次元値のそれぞれの位置に重みを関連付ける。これにより，特に，最高（または最低）の値がより重視される。このことは，マッチャーの結果を集約する際に重要となる。なぜなら，この方法では，どの次元から来たかを無視して，最も高いマッチの結果のみを保持できるからである。．

定義 7.13 (順序付き加重平均) 
oをn次元で分析可能なオブジェクトの集合とし、
順序付き加重平均演算子fは、Dn → D (Dは≦で順序付けられ、
上界⊤が与えられた集合)から、
∀x, x1, ... ... , xn∈Dを満足する関数である。, xn ∈ D, として定義される。

\[f(x_1,\dots,x_n)=\displaystyle\sum_{i=1}^n w_i\times x’_i \]

順序付き加重平均は、平均演算子の特性（可換性、単調性、偶任性）を持ってい.。max, min, average関数は順序付き加重平均の特別な場合となる。

投票
アラインメントの集約は、各マッチャーが独立した情報源であり、対応関係をアラインメントに含めるかどうかの判断は、この対応関係を支持する投票であると考えることで行うことができる。これは単純な多数決で決めることができる。

定義7.14（多数決） 
{Ai }i∈Iを同じオントロジーoとo′に対するアライメントの集合とすると、
{Ai}i∈Iから多数決で選ばれたアライメントAは次のようになる。
wi ×xi′
- w1,...,wnは、ni=1 wi = 1となるような[0 1]の重みの集合である。

\[ A= \{c\in \bigcup_{i\in I}A_i||\{A_i|c\in A_i\}_{i\in I}|\gt\frac{|I|}{2}\} \]

これは、相関関係に関連する信頼性を重みとして考慮することで、より洗練されたものにすることができる。

定義7.15 (Majority weighted vote) 
{Ai}i∈Iを同一のオントロジーoとo′に対するアライメントの集合とすると、
{Ai}i∈Iから多数決で選出されたアライメントAは以下のようになる。

\[ A= \{c\in \bigcup_{i\in I}A_i|\displaystyle\sum_{i\in I}kì(c)\gt\frac{|I|}{2}\} \]

また、多数決ではなく、分配された重みに応じて閾値を設定することも可能となる。
実際、アライメント調整には、任意の投票技術（Taylor 2005）を適用することができ、以前に検討したすべての合計尺度（加重和、加重平均、順序付き加重平均）は、閾値を追加することで投票技術に変えることができる。

デンプスター・シェーファー理論
デンプスター・シェイファー証拠理論は、不確実な情報を修正し、推論するための数値的なメカニズムを提供する。デンプスター・シェーファー理論は、独立した情報源からの証拠の組み合わせを可能にし、デンプスター結合規則として知られる単純な規則を提唱していることが最大の強みとなる。(Dempster 1967; Shafer 1976)
デンプスター・シェーファー理論では、サンプル空間を「フレーム・オブ・ディスカンスメント」または単に「フレーム」と呼ぶ。これはΩで示され、一意で相互に排他的な仮説のセットから構成されている。エビデンスは、Ωの中で最適な仮説を選択するために用いられ、言い換えれば、仮説を暗示するエビデンスの一部となる。専門家やセンサーなどのデータソースは，そのような証拠となる主張を提供する．
フレームΩ上の証拠は、基本的な割り当て関数としても知られる質量関数m、すなわち、m : 2^Ω → [0 1] で表され、以下の2つの条件が成立するようなものとなる。

\[\begin{eqnarray} m(\emptyset)&=&0\\ \displaystyle\sum_{A⊆\Omega}m(A)&=&1\end{eqnarray}\]

また，AはΩの部分集合であり，m(A)は主張Aを正確に支持する証拠の強さを表す．上記の第1条件は，集合Ωが完全でなければならないことを意味し，これは閉世界の仮定に対応する。第2の条件は，専門家の発言が正規化されていなければならず，証拠の各ソースが等しく重要であることを意味する。質量関数に基づいて，いくつかの尺度が定義される．

特に、Aの部分集合のような、より具体的な命題に対する信念は、Bel : 2^Ω → [0 1] という信念尺度を用いて、以下のように管理される。

\[Bel(A)=\displaystyle\sum_{B⊆A}m(B) \]

Bel(A)は、Aに割り当てられている全体（つまり、特定のサブセットを含む）の信念や正当な支持の尺度となる。
さらに、Aと一致する（オーバーラップする）別の信念Bが存在するかもしれない。これは、次のようなもっともらしい尺度Pl : 2^Ω → [0 1]によって処理される。

\[ Pl(A)=\displaystyle\sum_{A\cap B\neq\emptyset}m(B)\]

Pl(A)は，追加情報によって正当化される場合に，Aに割り当てられる可能性のある最大のサポートの尺度となる。

質量関数によって割り当てられた質量は、単位区間のセグメントと見なすことができる。集合Aに対する信念の尺度に関する完全な情報は、信念区間[Bel(A), P l(A)]で表される。一方、Pl(A) – Bel(A)は、Aに関する無知（データの欠落）や不確実性区間を表している。

デンプスター・シェイファー理論における信念、妥当性、不確実性のつながり。

デンプスター結合規則は、結合された証拠と相反するものとのバランスをとることにより、2つの質量関数を集約する。

定義7.16 (デンプスター結合規則) 
2つの質量関数mとm′が与えられたとき、
非ヌル仮説Aの結合質量関数m⊕m′は次のように定義される。

\[m\oplus m'(A)=\frac{\sum_{B\cap B’=A}m(B)\times m'(B’)}{1-\sum_{B\cap B’=\emptyset}m(B)\times m'(B’)}\]

正規化は、専門家間の合意を重視し、相反する証拠を無視するルールであるため、相反する証拠を組み合わせた場合、直感に反する結論を導く可能性がある(Zadeh 1984)。この問題を解決するには、閉ざされた世界の仮定を緩和することが考えられる(Smets 1990)。

Dempster-Shafer 理論の使用例。Dempster-Shafer 理論は、(Besana 2006; Wang et al. 2007; Nagy and Vargas-Vera 2010) において、様々なマッチング結果を組み合わせるために使用されている。このような設定では、編集距離やWordNetなどの異なるマッチャーが提供する類似性測定は、裏付けとなる証拠を提供する主観的な専門家の評価と見なされる。具体的には、正規化された類似性の値は、マッチングされるエンティティのペアに割り当てられた質量値に対応し、フレームの要素を構成する。例えば、 mwordnet (paper, article) = 0.86 は、WordNet マッチャーによると、paper が article に対応するという主張をサポートする質量関数が 0.86 という値になることを意味する。フレームには、関係するマッチャーによって評価されたすべての可能な対応関係が含まれる。マッチャーによって提供された質量は、Dempster ルールによって結合される。結合された証拠に基づいて、質量分布から最も可能性の高い対応関係を選択する必要がある。これは、例えば、信憑性が非常に高く、信念の尺度が非常に低いエンティティのペアを拒否するしきい値によって行うことができる。

アーギュメント(論証)
論証とは、特定の立場に賛成または反対の論証を行うことで、当事者間の合意を得るための手法である。オントロジーマッチングでは、以下の2つの役割がある。

• 2つのエージェントが互いの主張を受け入れた場合、2つのエージェント間の整合性を交渉する。
• マッチングによる整合性の実現。特に、マルチエージェントによる整合性の交渉は、2つの整合性の間の別の集約技術と見なすことができる。(Silva et al. 2005)は、論証ではなく、定量的な交渉に基づいたこのようなシステムを提示している。

論証とは、エージェントが反論を提供したり、好みに応じて論証を選択することを可能にするものとなる。これは、オントロジーマッチングにおいて、アラインメント間の合意を見つけるために使用されている(Trojahn et al. 2011)。この場合、対応関係は議論とみなされ、互いに矛盾しているかどうかや、異なるエージェントが事前に提案した技術に基づいているかどうかによって、互いに攻撃し合う傾向がある。したがって、対応関係に関するメタデータは、特定の対応関係を、その対応関係の出所、入手方法、あるいはその対応関係に付随する信頼性に基づいて、好むか攻撃するかの根拠となるため、重要となる。

整列の論証の例。用いて，次のように記述論理で表現されたオントロジーoとo′に対応する2つのエージェントCとPを考える。
\[ \begin{eqnarray} o &=& \{Micro-company ≡ Company ⊓ ≤5 employee\}\\o′ &= &\{SME ≡ Firm ⊓ ≤10 associate\}\end{eqnarray}\]

彼らが以下のようなアライメントAを発見したと仮定する。

\[\begin{eqnarray}A=\{&<Company,Firm,=>&, \ &(\gamma_1)&\\&<emploee,associate,≤>&,\  &(\gamma_2)&\\&<Micro-company,SME,≤>&\}\ &(\gamma_3)&\end{eqnarray}\]

この3つの対応関係を、それぞれγ₁、γ₂、γ₃で表す。γ₁を支持する論拠は以下の通りである。
a1：一方の側で知られているすべてのCompanyは、他方の側ではFirmであり、その逆もまた然りである。
a2：CompanyとFirmの2つの名前は、WordNetでは同義語である。
γ₃を支持する論拠は以下の通りである。
a3：アライメント（γ3なし）に加えて、2つのオントロジーが対応していることを意味する。
a4：一方の側で知られているマイクロ企業は、他方の側ではSMEである（その逆はない）。
また、反論としては
a5：Micro-companyとSMEという2つの名称は、どのような文字列距離でも類似しておらず、WordNetでは同義語ではないとされている。
a6： 両者に共通する特徴は associate と employee だけであり、ドメインとカーディナリティが異なる。
(Laera et al. 2006）では、議論は価値に基づく議論のフレームワーク（Bench-Capon 2003）に従って表現されている。これらは、対応関係に賛成（＋）か反対（-）かを示すフラグと、この対応関係をサポートする方法の種類（基本的な方法）で構成されている。これらの議論を簡単に表現すると、次のようになる。

\[\begin{eqnarray} &a_1:& <Company,Firm,=, &<+,extensional>&>\\&a_2:&<Company,Firm,=, &<+,terminological>&>\\&a_3:&<Micro-company,SME,≤, &<+,semantic>&>\\&a_4:&<Micro-company,SME,≤, &<+extensional>&>\\&a_5:&<Micro-company.SME,≤, &<-,terminological>&>\\&a_6:&<Micro-company,SME,≤, &<-,structual>&> \end{eqnarray}\]

このような引数は、既存の基本的なマッチャーによって提供することができる。引数を定義するもう一つの、よりエラボーな方法は、対応関係自体が正当化されることを認めることである。これは、例えば、Micro-companyとSMEの構造的な類似性が、employeeとassociateの用語的な類似性に依存することを表現するのに十分な表現力を持っている。
このような議論の根拠は、エージェントによっては、ある技術を他の技術よりも好んだり、信頼したりする場合があることによる。

例えば、エージェントCは拡張的な議論よりも用語的な議論を、意味的な議論よりも外延的な議論を、そして構造的な議論よりも意味的な議論を好むと想像することができる。同様に、Pは構造的な議論、意味的な議論、用語的な議論、そして拡張的な議論を好むという異なる優先順位を持つことができる。
論理的な理論（Dung 1995; Amgoud et al. 2000）では、論証のセットとエージェントの選好が与えられた場合、両当事者の間のコンセンサスの配置を定義することができる。論証フレームワークは、論証のセットと攻撃関係で構成される（Dung 1995）。議論の集合は、その要素のどれもが他の要素を攻撃しておらず、すべての要素が受け入れ可能である場合、許容可能であると呼ばれる。最後に、優先拡張は包含最大許容セットとなる。

エージェントの目的は、(i)共通の議論に取り組めるように議論を交換すること、(ii)どの議論、そしてポジションを一緒に受け入れられるかを決定することになる。この目的のために、彼らはすべての好ましい拡張の一部である議論のみを選択する慎重なアプローチ、または各エージェントの少なくとも1つの好ましい拡張にあるすべての議論を選択する信憑性の高いアプローチを採用することができる。
例えば、Cは{a5, a1, a2, a6}という好ましい拡張を持ち、Pは{a6, a5, a2, a1}という好ましい拡張を持ちます。しかし、CとPの間の引数の最大の共通部分集合は{a1,a2,a5,a6}であり、これはγ1とγ2からなる好ましい配列を選択することになる。
論証の様々な改良を用いて、異なる結果が得られている。論証間の異なるプリファレンスを可能にする価値ベースの論証(Laera et al. 2006)、エージェント間のコンフィデンスと投票にそれぞれプリファレンスを構築する強度価値ベースの論証、投票価値ベースの論証(Trojahn et al. 2008)となる。

類似度とアライメントの集計に関するまとめ
複数のマッチャーや類似性測定を同時に使用することは一般的に行われている。アライメントを提供するためには、これらの尺度を統合する必要がある。統合は、類似性の値またはランクの集約に基づいている場合がある。また、利害関係者（マッ チャーまたはエージェント）の意見に基づいて、単純な投票や、より精巧な議論戦略を用いて統合することもできる。
統合が実行されると、結果として得られた類似性は、アラインメントの抽出、またはさらなる合成や集約に使用することができる。また、マッチャーの学習やチューニングの基礎にもなる。

次回はアライメントのソートのための学習について述べる。