Moteur de cartographie de structure - Structure mapping engine

En intelligence artificielle et en sciences cognitives , le moteur de cartographie de structure ( SME ) est une implémentation en logiciel d'un algorithme de mise en correspondance analogique basé sur la théorie psychologique de Dedre Gentner . La base de l'idée de cartographie de structure de Gentner est qu'une analogie est une cartographie des connaissances d'un domaine (la base) à un autre (la cible). Le moteur de cartographie de structure est une simulation informatique des comparaisons d'analogie et de similitude.

En 1990, plus de 40 projets l'avaient utilisé [Falkenhainer, 2005]. RM French a déclaré que la théorie de la cartographie des structures est "incontestablement le travail le plus influent à ce jour sur la modélisation de l'analogie" [2002].

La théorie est utile car elle ignore les caractéristiques de surface et trouve des correspondances entre des choses potentiellement très différentes si elles ont la même structure représentationnelle. Par exemple, SME pourrait déterminer qu'un stylo est comme une éponge parce que les deux sont impliqués dans la distribution de liquide, même s'ils le font très différemment.

Théorie de la cartographie des structures

La théorie de la cartographie des structures est basée sur le principe de systématique, qui stipule que les connaissances connectées sont préférées aux faits indépendants. Par conséquent, le moteur de mappage de structure doit ignorer les mappages source-cible isolés à moins qu'ils ne fassent partie d'une structure plus grande. La PME, selon la théorie, devrait cartographier des objets liés à des connaissances déjà cartographiées.

La théorie exige également que les mappages soient effectués un à un , ce qui signifie qu'aucune partie de la description de la source ne peut être mappée à plus d'un élément de la cible et qu'aucune partie de la description de la cible ne peut être mappée à plus d'une partie de la cible. la source. La théorie exige également que si une correspondance correspond au sujet de la cible, les arguments du sujet et de la cible doivent également être cartographiés. Si ces deux conditions sont remplies, la cartographie est dite «structurellement cohérente».

Concepts dans les PME

Les PME mappent les connaissances d'une source vers une cible. SME appelle chaque description un dgroup . Les Dgroups contiennent une liste d'entités et de prédicats . Les entités représentent les objets ou concepts dans une description - comme un engrenage d'entrée ou un interrupteur. Les prédicats sont l'un des trois types et constituent un moyen général d'exprimer des connaissances pour les PME.

  • Les prédicats de relation contiennent plusieurs arguments, qui peuvent être d'autres prédicats ou entités. Un exemple de relation est: (transmettre (de quoi à)). Cette relation a un foncteur de transmission et prend trois arguments: quoi, de et vers.
  • Les prédicats d'attribut sont les propriétés d'une entité. Un exemple d' attribut est (engrenage rouge), ce qui signifie que l' engrenage a l'attribut rouge.
  • Les prédicats de fonction mappent une entité dans une autre entité ou constante. Un exemple de fonction est ( source d'énergie joules ) qui mappe la source d'alimentation d' entité sur la quantité numérique joules.

Les fonctions et les attributs ont des significations différentes et, par conséquent, SME les traite différemment. Par exemple, dans l'ensemble de règles de véritable analogie de SME, les attributs diffèrent des fonctions car ils ne peuvent pas correspondre à moins qu'il n'y ait une correspondance d'ordre supérieur entre eux. La différence entre les attributs et les fonctions sera expliquée plus en détail dans les exemples de cette section.

Tous les prédicats ont quatre paramètres. Ils ont (1) un foncteur, qui l'identifie, et (2) un type, qui est soit une relation, un attribut ou une fonction. Les deux autres paramètres (3 et 4) servent à déterminer comment traiter les arguments dans l' algorithme SME . Si les arguments doivent être mis en correspondance dans l'ordre, commutatif est faux. Si le prédicat peut prendre n'importe quel nombre d'arguments, N-aire est faux. Un exemple de définition de prédicat est: (sme: defPredicate relation (prédicat) ensemble de comportements: n-aire? T: commutative? T) Le foncteur du prédicat est «ensemble de comportements», son type est «relation», et son n Les paramètres -ary et commutatifs sont tous deux définis sur true. La partie «(prédicat)» de la définition spécifie qu'il y aura un ou plusieurs prédicats à l'intérieur d'une instanciation de l'ensemble de comportements.

Détails de l'algorithme

L'algorithme comporte plusieurs étapes. La première étape de l'algorithme consiste à créer un ensemble d'hypothèses de correspondance entre les dgroups source et cible. Une hypothèse de correspondance représente un mappage possible entre n'importe quelle partie de la source et la cible. Ce mappage est contrôlé par un ensemble de règles de correspondance. En changeant les règles de correspondance, on peut changer le type de raisonnement que fait la PME. Par exemple, un ensemble de règles de correspondance peut effectuer une sorte d'analogie appelée similarité littérale. et un autre effectue une sorte d'analogie appelée analogie vraie. Ces règles ne sont pas le lieu où des informations dépendant du domaine sont ajoutées, mais plutôt où le processus d' analogie est modifié, en fonction du type de fonction cognitive que l'utilisateur tente d'imiter.

Pour une règle de correspondance donnée, il existe deux types de règles qui définissent plus précisément comment elle sera appliquée: les règles de filtrage et les règles internes. Les règles internes utilisent uniquement les arguments des expressions dans les hypothèses de correspondance identifiées par les règles de filtrage. Cette limitation rend le traitement plus efficace en limitant le nombre d' hypothèses de correspondance générées. En même temps, cela aide également à construire les consistances structurelles nécessaires plus tard dans l'algorithme. Un exemple de règle de filtrage du jeu de règles de vraie analogie crée des hypothèses de correspondance entre des prédicats qui ont le même foncteur. Le jeu de règles de vraie analogie a une règle interne qui itère sur les arguments de n'importe quelle hypothèse de correspondance, créant plus d'hypothèses de correspondance si les arguments sont des entités ou des fonctions, ou si les arguments sont des attributs et ont le même foncteur.

Afin d'illustrer comment les règles de correspondance produisent des hypothèses de correspondance, considérez ces deux prédicats:

transmit torque inputgear secondgear (p1)

transmit signal switch div10 (p2)

Ici, nous utilisons la vraie analogie pour le type de raisonnement. La règle de correspondance de filtre génère une correspondance entre p1 et p2 car ils partagent le même foncteur, transmettre. Les règles internes produisent ensuite trois autres hypothèses de correspondance: couple à signal, appareillage d'entrée à commuter et deuxième engrenage à div10. Les règles internes ont créé ces hypothèses de correspondance car tous les arguments étaient des entités.

Si les arguments étaient des fonctions ou des attributs au lieu d'entités, les prédicats seraient exprimés comme suit:

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

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

Ces prédicats supplémentaires font des fonctions ou des attributs inputgear, secondgear, switch et div10 en fonction de la valeur définie dans le fichier d'entrée de langue. La représentation contient également des entités supplémentaires pour l'équipement et le circuit.

Selon le type d' équipement d'entrée, de second équipement, de commutateur et de div10 , leur signification change. En tant qu'attributs, chacun est une propriété de l'équipement ou du circuit. Par exemple, l'engrenage a deux attributs, inputgear et secondgear. Le circuit a deux attributs, interrupteur et circuit. En tant que fonctions inputgear, secondgear, switch et div10 deviennent des quantités de l'engrenage et du circuit. Dans cet exemple, les fonctions engrenage d'entrée et deuxième engrenage mappent maintenant aux grandeurs numériques «couple de l'engrenage d'entrée» et «couple du deuxième engrenage», pour le circuit les quantités correspondent à la quantité logique «interrupteur engagé» et à la quantité numérique «comptage actuel sur la division par 10 contre. »

Les PME les traitent différemment. Il ne permet pas aux attributs de correspondre à moins qu'ils ne fassent partie d'une relation d'ordre supérieur, mais il permet aux fonctions de correspondre, même si elles ne font pas partie d'une telle relation. Il permet aux fonctions de correspondre car elles font indirectement référence à des entités et doivent donc être traitées comme des relations n'impliquant aucune entité. Cependant, comme le montre la section suivante, les règles internes attribuent des poids plus faibles aux correspondances entre fonctions qu'aux correspondances entre relations.

La raison pour laquelle SME ne correspond pas aux attributs est qu'elle essaie de créer des connaissances connectées basées sur des relations et de satisfaire ainsi le principe de systématique. Par exemple, si une horloge et une voiture ont toutes deux des attributs d'équipement d'entrée, SME ne les marquera pas comme similaires. Si c'était le cas, ce serait faire un match entre l'horloge et la voiture en fonction de leur apparence - pas sur les relations entre eux.

Lorsque les prédicats supplémentaires dans p3 et p4 sont des fonctions, les résultats de l'appariement de p3 et p4 sont similaires aux résultats de p1 et p2 sauf qu'il y a une correspondance supplémentaire entre l'engrenage et le circuit et les valeurs des hypothèses de correspondance entre (engrenage d'entrée) et (circuit de commutation), et (deuxième engrenage) et (circuit div10), sont inférieurs. La section suivante en décrit plus en détail la raison.

Si inputgear, secondgear, switch et div10 sont des attributs au lieu d'entités, SME ne trouve aucune correspondance entre les attributs. Il trouve des correspondances uniquement entre les prédicats de transmission et entre le couple et le signal. De plus, les scores d'évaluation structurelle pour les deux autres correspondances diminuent. Pour que les deux prédicats correspondent, p3 devrait être remplacé par p5, ce qui est démontré ci-dessous.

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

Étant donné que l'ensemble de règles de vraie analogie identifie que les attributs div10 sont les mêmes entre p5 et p4 et que les attributs div10 font tous deux partie de la correspondance de relation supérieure entre le couple et le signal, SME établit une correspondance entre (engrenage div10) et (div10 circuit) - ce qui conduit à une correspondance entre l'engrenage et le circuit.

Faire partie d'une correspondance d'ordre supérieur est une exigence uniquement pour les attributs. Par exemple, si (engrenage div10) et (circuit div10) ne font pas partie d'une correspondance d'ordre supérieur, SME ne crée pas d'hypothèse de correspondance entre eux. Cependant, si div10 est une fonction ou une relation, SME crée une correspondance.

Score d'évaluation structurelle

Une fois les hypothèses de correspondance générées, SME doit calculer un score d'évaluation pour chaque hypothèse. SME le fait en utilisant un ensemble de règles de correspondance internes pour calculer les preuves positives et négatives pour chaque correspondance. Plusieurs quantités de preuves sont corrélées à l'aide de la règle de Dempster [Shafer, 1978], ce qui donne des valeurs de croyance positives et négatives entre 0 et 1. Les règles de correspondance attribuent des valeurs différentes pour les correspondances impliquant des fonctions et des relations. Ces valeurs sont cependant programmables, et certaines valeurs par défaut qui peuvent être utilisées pour appliquer le principe de systématicité sont décrites dans [Falkenhainer et al., 1989].

Ces règles sont:

  1. Si la source et la cible ne sont pas des fonctions et ont le même ordre, la correspondance obtient +0,3 preuves. Si les ordres sont à moins de 1 l'un de l'autre, le match obtient +0,2 preuves et -0,05 preuves.
  2. Si la source et la cible ont le même foncteur, la correspondance obtient 0,2 preuve si la source est une fonction et 0,5 si la source est une relation.
  3. Si les arguments correspondent, la correspondance obtient +0,4 preuves. Les arguments peuvent correspondre si toutes les paires d'arguments entre la source et la cible sont des entités, si les arguments ont les mêmes foncteurs, ou si la cible n'est jamais une entité mais pas la source.
  4. Si le type de prédicat correspond, mais que les éléments du prédicat ne correspondent pas, la correspondance obtient une preuve de -0,8.
  5. Si les expressions source et cible font partie d'une correspondance d'ordre supérieur, ajoutez 0,8 de la preuve pour la correspondance d'ordre supérieur.

Dans l'exemple de correspondance entre p1 et p2, SME donne à la correspondance entre les relations de transmission une valeur de preuve positive de 0,7900, et les autres obtiennent des valeurs de 0,6320. La relation de transmission reçoit la valeur de preuve de 0,7900 car elle obtient des preuves des règles 1, 3 et 2. Les autres correspondances obtiennent une valeur de 0,6320 car 0,8 de la preuve de la transmission est propagée à ces correspondances en raison de la règle 5.

Pour les prédicats p3 et p4, SME attribue moins de preuves car les arguments des relations de transmission sont des fonctions. La relation de transmission obtient une preuve positive de 0,65 car la règle 3 n'ajoute plus de preuve. La correspondance entre (engrenage d'entrée) et (circuit de commutation) devient 0,7120. Cette correspondance obtient une preuve de 0,4 à cause de la règle 3 et une preuve de 0,52 propagée à partir de la relation de transmission à cause de la règle 5.

Lorsque les prédicats dans p3 et p4 sont des attributs, la règle 4 ajoute -0,8 preuve à la correspondance de transmission car - bien que les foncteurs de la relation de transmission correspondent - les arguments n'ont pas le potentiel de correspondre et les arguments ne sont pas des fonctions.

Pour résumer, les règles de correspondance internes calculent un score d'évaluation structurelle pour chaque hypothèse de correspondance. Ces règles appliquent le principe de systématique. La règle 5 fournit des preuves de retombées afin de renforcer les correspondances impliquées dans des relations d'ordre supérieur. Les règles 1, 3 et 4 ajoutent ou soustraient la prise en charge des relations qui pourraient avoir des arguments correspondants. La règle 2 ajoute la prise en charge des cas où les foncteurs correspondent. ajoutant ainsi un support pour les correspondances qui mettent l'accent sur les relations.

Les règles appliquent également la différence entre les attributs, les fonctions et les relations. Par exemple, ils ont des contrôles qui donnent moins de preuves de fonctions que de relations. Les attributs ne sont pas spécifiquement traités par les règles de correspondance internes, mais les règles de filtrage SME garantissent qu'ils ne seront pris en compte pour ces règles que s'ils font partie d'une relation d'ordre supérieur, et la règle 2 garantit que les attributs ne correspondront que s'ils sont identiques. foncteurs.

Création Gmap

Le reste de l'algorithme SME est impliqué dans la création d'ensembles d'hypothèses de correspondance au maximum cohérents. Ces ensembles sont appelés gmaps. Les PME doivent s'assurer que les écarts qu'elles créent sont structurellement cohérents; en d'autres termes, qu'ils sont un-à-un - de sorte qu'aucune source n'est mappée à plusieurs cibles et qu'aucune cible n'est mappée à plusieurs sources. Les gmaps doivent également avoir un support, ce qui signifie que si une hypothèse de correspondance est dans la gmap, alors l'hypothèse de correspondance qui implique les éléments source et cible le sont également.

Le processus de création de gmap se déroule en deux étapes. Premièrement, SME calcule des informations sur chaque hypothèse de correspondance - y compris les mappages d'entités, tout conflit avec d'autres hypothèses et les autres hypothèses de correspondance avec lesquelles elle pourrait être structurellement incohérente.

SME utilise ensuite ces informations pour fusionner les hypothèses de correspondance - en utilisant un algorithme glouton et le score d'évaluation structurelle. Il fusionne les hypothèses de correspondance en graphes connectés structurellement cohérents au maximum d'hypothèses de correspondance. Ensuite, il combine les gmaps qui ont une structure qui se chevauchent si elles sont structurellement cohérentes. Enfin, il combine des gmaps indépendantes tout en conservant la cohérence structurelle.

La comparaison d'une source à un dgroup cible peut produire une ou plusieurs gmaps. Le poids de chaque gmap est la somme de toutes les valeurs de preuve positives pour toutes les hypothèses de correspondance impliquées dans le gmap. Par exemple, si une source contenant p1 et p6 ci-dessous, est comparée à une cible contenant p2, SME générera deux gmaps. Les deux gmaps ont un poids de 2,9186.

La source:

transmit torque inputgear secondgear (p1)

transmit torque secondgear thirdgear (p6)

Cibler: transmit signal switch div10 (p2)

Ce sont les gmaps qui résultent de la comparaison d'une source contenant un p1 et p6 et une cible contenant p2.

Gmap n ° 1: 

(TORQUE SIGNAL)
(INPUTGEAR SWITCH)
(SECONDGEAR DIV10)
(*TRANSMIT-TORQUE-INPUTGEAR-SECONDGEAR *TRANSMIT-SIGNAL-SWITCH-DIV10)

Gmap n ° 2 : 

(TORQUE SIGNAL)
(SECONDGEAR SWITCH)
(THIRDGEAR DIV10)
(*TRANSMIT-TORQUE-SECONDGEAR-THIRDGEAR *TRANSMIT-SIGNAL-SWITCH-DIV10)

Les gmaps affichent des paires de prédicats ou d'entités qui correspondent. Par exemple, dans la gmap n ° 1, les entités couple et signal concordent et les comportements transmettent le couple d'entrée du deuxième engrenage et transmettent la correspondance du commutateur de signal div10. Gmap n ° 1 représente la combinaison de p1 et p2. Gmap n ° 2 représente la combinaison de p1 et p6. Bien que p2 soit compatible avec p1 et p6, la contrainte de mappage un-à-un impose que les deux mappages ne puissent pas être dans le même gmap. Par conséquent, SME produit deux gmaps indépendantes. De plus, combiner les deux gmaps ensemble rendrait les mappages d'entité entre thirdgear et div10 en conflit avec le mappage d'entité entre secondgear et div10.

des reproches

Chalmers, French et Hofstadter [1992] reprochent aux PME de s'appuyer sur des représentations LISP construites manuellement comme entrée. Ils soutiennent qu'il faut trop de créativité humaine pour construire ces représentations; l'intelligence vient de la conception de l'entrée, pas de la PME. Forbus et coll. [1998] a tenté de réfuter cette critique. Morrison et Dietrich [1995] ont tenté de concilier les deux points de vue. Turney [2008] présente un algorithme qui ne nécessite pas d'entrée LISP, mais qui suit les principes de la théorie de la cartographie des structures. Turney [2008] affirment que leur travail n'est pas non plus à l'abri des critiques de Chalmers, French et Hofstadter [1992].

Dans son article Comment les idées créatives prennent forme, Liane Gabora écrit: "Selon la théorie de la créativité, la pensée créative ne travaille pas sur des représentations individuelles, discrètes et prédéfinies, mais sur un amalgame contextuel d'éléments qui existent dans un état de potentialité et peut ne pas être facilement séparable. Cela conduit à prédire que la réalisation de l'analogie ne se fait pas en mappant les correspondances des sources candidates à la cible, comme le prédit la théorie de la cartographie de structure de l'analogie, mais en éliminant les non-correspondances, réduisant ainsi la potentialité. "

Les références

Lectures complémentaires