構造マッピングエンジン

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

この理論は、表面的な特徴を無視し、同じ表現構造を持つ潜在的に非常に異なるものの間で一致を見つけるので便利です。たとえば、SME は、ペンとスポンジはどちらも液体を分配する役割を担っていますが、そのやり方は非常に異なるため、ペンはスポンジに似ていると判断できます。

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

この理論では、マッピングは1 対 1 で行われることも要求されます。つまり、ソース記述のどの部分もターゲットの複数の項目にマッピングできず、ターゲット記述のどの部分もソースの複数の部分にマッピングできません。また、一致がサブジェクトをターゲットにマッピングする場合、サブジェクトとターゲットの引数もマッピングされる必要があります。これらの条件が両方とも満たされている場合、マッピングは「構造的に一貫している」と言われます。

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

• 関係述語には複数の引数が含まれ、他の述語またはエンティティにすることができます。関係の例は、(transmit (what from to)) です。この関係には関数 transferがあり、 what、from、およびto の3 つの引数を取ります。
• 属性述語はエンティティのプロパティです。属性の例は(red gear) で、これはギアに属性red があることを意味します。
• 関数述語は、エンティティを別のエンティティまたは定数にマップします。関数の例としては、エンティティpower source を数値量joulesにマップする ( joules power source) があります。

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

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

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

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

一致ルールがどのように一致仮説を生成するかを説明するために、次の 2 つの述語を検討します。

transmit torque inputgear secondgear (p1)

transmit signal switch div10 (p2)

ここでは、推論の種類に真の類推を使用します。フィルター一致ルールは、同じファンクタである送信を共有するため、p1 と p2 間の一致を生成します。次に、インターン ルールは、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 が属性を一致させない理由は、関係性に基づいて関連知識を作成し、体系性原則を満たそうとしているためです。たとえば、時計と車の両方に inputgear 属性がある場合、SME はこれらを類似としてマークしません。マークすると、時計と車のマッチングは、それらの関係性ではなく、外観に基づいて行われます。

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

inputgear、secondgear、switch、div10 がエンティティではなく属性である場合、SME はどの属性間の一致も見つけません。送信述語間と、トルクと信号間の一致のみを見つけます。さらに、残りの 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 他、1989] で説明されています。

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

1. ソースとターゲットが関数ではなく、同じ順序である場合、一致は +0.3 の証拠を取得します。順序が互いに 1 以内である場合、一致は +0.2 の証拠と -0.05 の証拠を取得します。
2. ソースとターゲットが同じファンクタを持つ場合、ソースが関数の場合は一致の証拠が 0.2 になり、ソースが関係の場合は一致の証拠が 0.5 になります。
3. 引数が一致する場合、一致の証拠は +0.4 になります。ソースとターゲット間の引数のペアがすべてエンティティである場合、引数に同じファンクタがある場合、またはターゲットがエンティティであるがソースがそうでない場合は、引数は一致する可能性があります。
4. 述語タイプが一致しても、述語内の要素が一致しない場合は、一致の証拠は -0.8 になります。
5. ソース式とターゲット式が一致する高次一致の一部である場合、高次一致の証拠の 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 は、属性が同一の関数を持つ場合にのみ一致することを保証します。

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)

gmap は、一致する述語またはエンティティのペアを表示します。たとえば、gmap No. 1 では、エンティティのtorqueとsignalが一致し、動作のtransmittorque 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]で、「創造性のホーニング理論によれば、創造的思考は、個別に考慮された、離散的で、事前に定義された表現ではなく、潜在的状態で存在し、容易に分離できない可能性のある、文脈的に引き出された項目の混合物に基づいて機能します。これにより、類推の作成は、類推の構造マッピング理論によって予測されるように、候補ソースからターゲットへの対応をマッピングすることによってではなく、非対応を排除することによって、潜在性を削ぎ落とすことによって進むという予測につながります。」と書いています。

• ノースウェスタン大学の定性的推論グループによる論文
• Chalmers, DJ, French, RM, & Hofstadter, DR: 1992, 「高レベルの知覚、表現、類推：人工知能の方法論の批評」。実験的および理論的人工知能ジャーナル、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）
• Shafer, G : 1978, A Mathematical Theory of Evidence 、プリンストン大学出版局、プリンストン、ニュージャージー。ISBN 0-691-08175-1。 
• Morrison, CT、Dietrich, E.: 1995、「構造マッピング対高レベル知覚：類推の説明をめぐる誤った争い」認知科学会第17回年次大会議事録、678-682。
• Turney, PD: 2008、「潜在関係マッピングエンジン: アルゴリズムと実験」、Journal of Artificial Intelligence Research (JAIR)、33、615–655。