構造マッピングエンジン

人工知能と認知科学において、構造マッピングエンジン（SME ）は、デドレ・ゲントナーの心理学理論に基づく類推マッチングアルゴリズムのソフトウェア実装です。ゲントナーの構造マッピングの考え方は、類推とは、ある領域（ベース）から別の領域（ターゲット）への知識のマッピングであるというものです。構造マッピングエンジンは、類推と類似性の比較をコンピュータシミュレーションで行います。 ^[1]

この理論は、表面的な特徴を無視し、同じ表現構造を持つ場合、潜在的に大きく異なるもの同士の対応関係を見つけるという点で有用です。例えば、SMEは、ペンとスポンジはどちらも液体を分配する役割を担っているため、ペンがスポンジに似ていると判断できます。ただし、その動作は大きく異なります。

構造マッピング理論

構造マッピング理論は、独立した事実よりも関連した知識が優先されるという体系性原理に基づいています。したがって、構造マッピングエンジンは、より大きな構造の一部でない限り、孤立したソース-ターゲットマッピングを無視する必要があります。理論によれば、SMEは、既にマッピングされている知識に関連するオブジェクトをマッピングする必要があります。

この理論では、マッピングは一対一で行われることが求められます。つまり、ソース記述のどの部分もターゲットの複数の項目にマッピングできず、ターゲット記述のどの部分もソースの複数の部分にマッピングできないということです。また、一致が主語をターゲットにマッピングする場合、主語とターゲットの引数もマッピングされなければならないことも求められます。これらの条件が両方とも満たされている場合、マッピングは「構造的に一貫している」と言われます。

中小企業における概念

SMEは、ソースからターゲットへと知識をマッピングします。SMEでは、それぞれの記述をdgroupと呼びます。dgroupには、エンティティと述語のリストが含まれます。エンティティは、入力ギアやスイッチなど、記述内のオブジェクトまたは概念を表します。述語は3つのタイプのうちの1つであり、SMEにおける知識を表現する一般的な方法です。

関係述語には複数の引数が含まれ、引数は他の述語または実体になります。関係の例としては、(transmit (what from to)) があります。この関係は関数 transmit を持ち、 what、from、 toの3つの引数を取ります。
属性述語は実体のプロパティです。属性の例としては、(red gear) が挙げられます。これは、ギアが属性red を持つことを意味します。
関数述語は、ある実体を別の実体または定数にマッピングします。関数の例としては、( joules power source) があり、これは実体power source を数値量joules にマッピングします。

関数と属性は意味が異なるため、SMEでは異なる方法で処理されます。例えば、SMEの真相類推ルールセットでは、属性と関数は高階一致がない限り一致しないため、属性と関数は異なります。属性と関数の違いについては、このセクションの例で詳しく説明します。

すべての述語には 4 つのパラメーターがあります。それらは (1) 述語を識別するファンクターと、(2) 関係、属性、または関数のいずれかの型です。他の 2 つのパラメーター (3 と 4) は、SMEアルゴリズムで引数を処理する方法を決定するためのものです。引数を順番に一致させる必要がある場合、commutativeは false です。述語が任意の数の引数を取ることができる場合、N-aryは false です。述語定義の例は次のとおりです: (sme:defPredicate behavior-set (predicate) relation :n-ary? t :commutative? t) 述語のファンクターは「behavior-set」、型は「relation」、n-ary パラメーターと commutative パラメーターは両方とも true に設定されています。定義の「(predicate)」の部分は、behavior-set のインスタンス化内に 1 つ以上の述語があることを指定します。

アルゴリズムの詳細

このアルゴリズムにはいくつかのステップがあります。^[2] アルゴリズムの最初のステップは、ソースとターゲットの dgroup 間の一致仮説のセットを作成することです。一致仮説は、ソースとターゲットの任意の部分間の可能なマッピングを表します。このマッピングは、一致ルールのセットによって制御されます。一致ルールを変更することで、SME が行う推論の種類を変更できます。たとえば、1 つの一致ルールセットは、文字どおりの類似性と呼ばれる一種の類推を実行し、別の一致ルールセットは、真の類推と呼ばれる一種の類推を実行します。これらのルールは、ドメインに依存する情報が追加される場所ではなく、ユーザーがエミュレートしようとしている認知機能の種類に応じて、類推プロセスが調整される場所です。

特定の一致ルールには、その適用方法をさらに定義する 2 種類のルール、フィルタールールと内部ルールがあります。内部ルールは、フィルタールールが識別する一致仮説内の式の引数のみを使用します。この制限により、生成される一致仮説の数を制限して、処理がより効率的になります。同時に、アルゴリズムで後で必要になる構造の一貫性の構築にも役立ちます。真類推ルールセットのフィルタールールの例では、同じ関数を持つ述語間の一致仮説を作成します。真類推ルールセットには、一致仮説の引数を反復処理して、引数がエンティティまたは関数である場合、または引数が属性で同じ関数を持つ場合に、より多くの一致仮説を作成する内部ルールがあります。

一致ルールが一致仮説を生成する仕組みを説明するために、次の 2 つの述語を考えてみましょう。

transmit torque inputgear secondgear (p1)

transmit signal switch div10 (p2)

ここでは、推論の種類として真のアナロジーを採用しています。フィルター一致規則は、p1とp2が同じ関数transmitを共有しているため、両者の一致を生成します。次に、内部規則は、torqueからsignal、inputgearからswitch、secondgearからdiv10という3つの一致仮説を生成します。内部規則は、すべての引数がエンティティであるため、これらの一致仮説を作成しました。

引数がエンティティではなく関数または属性である場合、述語は次のように表現されます。

transmit torque (inputgear gear) (secondgear gear) (p3)

transmit signal (switch circuit) (div10 circuit) (p4)

これらの追加述語は、言語入力ファイルで定義された値に応じて、inputgear、secondgear、switch、div10 などの関数または属性を作成します。また、この表現には gear と circuit という追加エンティティも含まれます。

inputgear、secondgear、switch、 div10は、その型によって意味が変わります。属性として、それぞれはギアまたは回路の特性を表します。例えば、ギアには inputgear と secondgear という 2 つの属性があります。回路には switch と circuit という 2 つの属性があります。関数として、inputgear、secondgear、switch、div10 はギアと回路の量になります。この例では、関数 inputgear と secondgear は数値「inputgear からのトルク」と「secondgear からのトルク」にマッピングされます。回路の場合、これらの量は論理量「スイッチのオン」と数値量「10 除算カウンタの現在のカウント」にマッピングされます。

SMEはこれらを異なる方法で処理します。属性は高階関係の一部でない限り一致しませんが、関数は高階関係の一部でなくても一致します。関数は間接的に実体を参照するため、実体を含まない関係と同様に扱うべきであり、一致を許可します。ただし、次のセクションで示すように、内部ルールでは関数間の一致に関係間の一致よりも低い重みを割り当てます。

SMEが属性をマッチングしない理由は、関係性に基づいて連結知識を構築し、体系性原則を満たそうとするためです。例えば、時計と車の両方に入力ギア属性がある場合、SMEはこれらを類似としてマークしません。もしマークすると、時計と車のマッチングは、両者の関係性ではなく、外観に基づいて行われることになります。

p3とp4の追加述語が関数である場合、p3とp4のマッチング結果はp1とp2の結果と似ていますが、gearとcircuitのマッチングが追加され、(inputgear gear)と(switch circuit)、(secondgear gear)と(div10 circuit)のマッチング仮説の値が低くなります。次のセクションでは、この理由をより詳しく説明します。

inputgear、secondgear、switch、div10が実体ではなく属性である場合、SMEはこれらの属性間の一致を見つけられません。transmit述語間とtorqueとsignal間の一致のみを見つけます。さらに、残りの2つの一致に対する構造評価スコアは低下します。2つの述語を一致させるには、p3をp5に置き換える必要があります。これは以下で示されます。

transmit torque (inputgear gear) (div10 gear) (p5)

真の類推ルールセットは、div10 属性が p5 と p4 の間で同じであると識別し、div10 属性は両方ともトルクと信号間の高関係一致の一部であるため、SME は (div10 ギア) と (div10 回路) を一致させます。これにより、ギアと回路が一致します。

高次一致の一部であることは、属性の場合のみ必須です。例えば、(div10 gear) と (div10 circuit) が高次一致の一部でない場合、SME はそれらの間の一致仮説を作成しません。ただし、div10 が関数または関係である場合は、SME は一致仮説を作成します。

構造評価スコア

マッチング仮説が生成されると、SMEは各仮説の評価スコアを計算する必要があります。SMEは、一連の内部マッチングルールを用いて、各マッチングの肯定的証拠と否定的証拠を計算します。複数の証拠量はデンプスターの法則[Shafer, 1978]を用いて相関され、0から1の間の肯定的および否定的確信値が生成されます。マッチングルールは、関数と関係を含むマッチングに対して異なる値を割り当てます。ただし、これらの値はプログラム可能であり、[Falkenhainer et al., 1989]には、体系性原則を適用するために使用できるデフォルト値がいくつか記載されています。

これらのルールは次のとおりです。

ソースとターゲットが関数ではなく、同じ順序を持つ場合、一致の証拠は+0.3になります。順序の差が1以内の場合、一致の証拠は+0.2、証拠は-0.05になります。
ソースとターゲットが同じファンクタを持つ場合、ソースが関数であれば一致の証拠は 0.2 になり、ソースが関係であれば一致の証拠は 0.5 になります。
引数が一致する場合、一致の証拠は+0.4になります。引数が一致する可能性があるのは、ソースとターゲットの間の引数のペアがすべてエンティティである場合、引数が同じ関数を持つ場合、またはターゲットがエンティティであるがソースがエンティティではないという状況が決してない場合です。
述語タイプが一致しても、述語内の要素が一致しない場合は、一致の証拠は -0.8 になります。
ソース式とターゲット式が一致する高次一致の一部である場合、高次一致の証拠の 0.8 を追加します。

p1とp2の一致例では、SMEは送信関係の一致に正の証拠値0.7900を与え、その他の一致には0.6320を与えます。送信関係はルール1、3、2から証拠を得るため、証拠値0.7900を受け取ります。その他の一致には、ルール5により送信関係からの証拠の0.8がこれらの一致に伝播されるため、証拠値0.6320が与えられます。

述語p3とp4については、送信関係の引数が関数であるため、SMEはより少ない証拠を割り当てます。送信関係は、ルール3によって証拠が追加されなくなったため、肯定的な証拠が0.65になります。(入力ギア)と(スイッチ回路)の一致は0.7120になります。この一致は、ルール3により証拠が0.4、ルール5により送信関係から伝播された証拠が0.52になります。

p3 と p4 の述語が属性の場合、ルール 4 は、送信関係の関数が一致しても、引数が一致する可能性がなく、引数が関数ではないため、送信一致に -0.8 の証拠を追加します。

要約すると、インターンマッチルールは、各マッチ仮説の構造評価スコアを計算します。これらのルールは体系性原則を強制します。ルール5は、高階関係に関係するマッチを強化するために、トリクルダウン証拠を提供します。ルール1、3、4は、一致する引数を持つ可能性のある関係のサポートを追加または削除します。ルール2は、関数が一致する場合のサポートを追加します。これにより、関係を強調するマッチのサポートが追加されます。

これらのルールは、属性、関数、関係の違いも強制します。例えば、関数に対しては関係よりも証拠が少ないチェックが行われます。属性は内部一致ルールでは特に扱われませんが、SMEのフィルタールールは、属性が高階関係の一部である場合にのみこれらのルールの対象となるようにし、ルール2は、属性が同一の関数を持つ場合にのみ一致するようにしています。

Gmapの作成

SMEアルゴリズムの残りの部分は、最大限に一貫性のある一致仮説セットの作成に関係します。これらのセットはgmapと呼ばれます。SMEは、作成するgmapが構造的に一貫していること、つまり1対1であること、つまりソースが複数のターゲットにマッピングされず、ターゲットが複数のソースにマッピングされないことを保証する必要があります。gmapにはサポートも必要です。つまり、一致仮説がgmapに含まれる場合、ソース項目とターゲット項目を含む一致仮説もgmapに含まれる必要があります。

gmapの作成プロセスは2つのステップで行われます。まず、SMEは各一致仮説に関する情報（エンティティマッピング、他の仮説との競合、構造的に矛盾する可能性のある他の一致仮説など）を計算します。

SMEはこの情報を用いて、貪欲アルゴリズムと構造評価スコアを用いて一致仮説を統合します。一致仮説を、構造的に最大限に一貫性のある一致仮説の連結グラフに統合します。次に、構造的に一貫性がある場合、重複構造を持つgmapを統合します。最後に、構造的一貫性を維持しながら、独立したgmapを統合します。

ソースとターゲットのdgroupを比較すると、1つ以上のgmapが生成される場合があります。各gmapの重みは、そのgmapに含まれるすべての一致仮説の肯定的な証拠値の合計です。例えば、以下のp1とp6を含むソースとp2を含むターゲットを比較する場合、SMEは2つのgmapを生成します。どちらのgmapも重みは2.9186です。

ソース：

transmit torque inputgear secondgear (p1)

transmit torque secondgear thirdgear (p6)

ターゲット： transmit signal switch div10 (p2)

これらは、p1 と p6 を含むソースと、p2 を含むターゲットを比較して生成された gmap です。

GマップNo.1:

（トルク信号）
（入力ギアスイッチ）
（セカンドギア DIV10）
（*トランスミット-トルク-入力ギア-セカンドギア *トランスミット-信号-スイッチ-DIV10）

GマップNo.2：

（トルク信号）
（セカンドギアスイッチ）
（サードギア DIV10）
（*トランスミット-トルク-セカンドギア-サードギア *トランスミット-信号-スイッチ-DIV10）

gmapsは、一致する述語またはエンティティのペアを示します。例えば、gmap No. 1では、エンティティtorqueとsignalが一致し、動作transmit torque inputgear secondgearとtransmit signal switch div10が一致しています。gmap No. 1はp1とp2の組み合わせを表しています。gmap No. 2はp1とp6の組み合わせを表しています。p2はp1とp6の両方と互換性がありますが、1対1のマッピング制約により、両方のマッピングを同じgmapに含めることはできません。そのため、SMEは2つの独立したgmapを生成します。さらに、2つのgmapを組み合わせると、thirdgearとdiv10間のエンティティマッピングが、secondgearとdiv10間のエンティティマッピングと競合してしまいます。

批判

Chalmers、French、Hofstadter [1992] は、SME が入力として手動で構築されたLISP表現に依存していることを批判している。彼らは、これらの表現の構築には人間の創造性が過度に必要であり、その知性は SME ではなく入力の設計から生まれると主張している。Forbus ら [1998] はこの批判に反論しようとした。Morrison と Dietrich [1995] は、この 2 つの視点を調和させようとした。Turney [2008] は、LISP 入力を必要としないが構造マッピング理論の原則に従うアルゴリズムを提示している。Turney [2008] は、彼らの研究も Chalmers、French、Hofstadter [1992] の批判から逃れられないと述べている。

リアン・ガボラは、論文「創造的なアイデアはどのように形作られるか」^[3]の中で、「創造性のホーニング理論によれば、創造的思考は、個別に検討された、離散的で、事前に定義された表現ではなく、文脈的に誘発された、潜在的状態にあり、容易に分離できない可能性のある項目の混合体に基づいて機能します。このことから、類推形成は、類推の構造マッピング理論が予測するように、候補となる情報源から対象への対応関係をマッピングするのではなく、非対応関係を淘汰することで、それによって潜在的可能性を削ぎ落とすという予測が導き出されます。」と述べています。

参考文献

^ 「構造マッピング：類推と類似性の計算モデル」ノースウェスタン大学. 2012年1月16日閲覧。
^ Brian Falkenhainer、Kenneth D. Forbus、Dedre Gentner (1989). 「構造マッピングエンジン：アルゴリズムと例」(PDF) .人工知能. 41 : 1– 63. CiteSeerX 10.1.1.26.6432 . doi :10.1016/0004-3702(89)90077-5 . 2012年1月16日閲覧。
^ ガボラ、リアン（2015）「創造的なアイデアはどのように形作られるか」arXiv：1501.04406 [q-bio.NC]。

さらに読む

ノースウェスタン大学の質的推論グループの論文
Chalmers, DJ, French, RM, Hofstadter, DR: 1992, 「高レベル知覚、表現、類推：人工知能方法論批判」Journal of Experimental & Theoretical Artificial Intelligence , 4(3), 185–211.
Falkenhainer, B: 2005, Structure Mapping Engine の実装。sme 実装
Falkenhainer, B, Forbus, K , Gentner, D: 1989, 「構造マッピングエンジン：アルゴリズムと例」人工知能、20(41): 1–63.
Forbus, KD, Gentner, D., Markman, AB, Ferguson, RW: 1998, 「アナロジーは高次の知覚に似ている：アナロジーマッピングへのドメインジェネラルアプローチが正しい理由」Journal of Experimental and Theoretical Artificial Intelligence , 10(2), 231–257.
French, RM: 2002.「アナロジー形成の計算モデル化」認知科学の動向、6(5)、200-205。
ゲントナー、D：1983、「構造マッピング：アナロジーの理論的枠組み」、認知科学7（2）
シェーファー、G：1978年、「証拠の数学的理論」、プリンストン大学出版局、プリンストン、ニュージャージー州。ISBN 0-691-08175-1。
モリソン, C.T.、ディートリッヒ, E.（1995）「構造マッピング vs. 高次知覚：類推の説明をめぐる誤った争い」認知科学会第17回年次大会議事録、678-682ページ。
Turney, PD: 2008、「潜在関係マッピングエンジン：アルゴリズムと実験」、Journal of Artificial Intelligence Research (JAIR)、33、615–655。

[1] 「構造マッピング：類推と類似性の計算モデル」ノースウェスタン大学. 2012年1月16日閲覧。

[2] Brian Falkenhainer、Kenneth D. Forbus、Dedre Gentner (1989). 「構造マッピングエンジン：アルゴリズムと例」(PDF) .人工知能. 41 : 1– 63. CiteSeerX 10.1.1.26.6432 . doi :10.1016/0004-3702(89)90077-5 . 2012年1月16日閲覧。

[3] ガボラ、リアン（2015）「創造的なアイデアはどのように形作られるか」arXiv：1501.04406 [q-bio.NC]。