Structuur mapping engine - Structure mapping engine

In kunstmatige intelligentie en cognitieve wetenschap is de structuurmapping-engine ( SME ) een implementatie in software van een algoritme voor analogische matching gebaseerd op de psychologische theorie van Dedre Gentner . De basis van Gentners idee van het in kaart brengen van structuren is dat een analogie het in kaart brengen van kennis van het ene domein (de basis) naar het andere (het doelwit) is. De structuur-mapping-engine is een computersimulatie van de analogie- en gelijkenisvergelijkingen.

Vanaf 1990 hadden meer dan 40 projecten er gebruik van gemaakt [Falkenhainer, 2005]. RM French zei dat de theorie van het in kaart brengen van structuren "ongetwijfeld het meest invloedrijke werk tot nu toe is van het modelleren van analogieën" [2002].

De theorie is nuttig omdat het oppervlakkenmerken negeert en overeenkomsten vindt tussen potentieel zeer verschillende dingen als ze dezelfde representatiestructuur hebben. Het MKB zou bijvoorbeeld kunnen vaststellen dat een pen als een spons is, omdat beide betrokken zijn bij het uitgeven van vloeistof, ook al doen ze dat heel anders.

Structuur mapping theorie

Structure mapping theory is gebaseerd op het systematiciteitsprincipe, dat stelt dat verbonden kennis de voorkeur heeft boven onafhankelijke feiten. Daarom zou de structuurmapping-engine geïsoleerde brondoel-toewijzingen moeten negeren, tenzij ze deel uitmaken van een grotere structuur. De KMO, zo luidt de theorie, zou objecten in kaart moeten brengen die gerelateerd zijn aan kennis die al in kaart is gebracht.

De theorie vereist ook dat toewijzingen één-op-één worden gedaan , wat betekent dat geen enkel deel van de bronbeschrijving kan worden toegewezen aan meer dan één item in het doel en geen enkel deel van de doelbeschrijving kan worden toegewezen aan meer dan één deel van het doel. bron. De theorie vereist ook dat als een match het onderwerp van het doelwit in kaart brengt, de argumenten van het onderwerp en het doel ook moeten worden afgebeeld. Als aan beide voorwaarden is voldaan, wordt gezegd dat de afbeelding "structureel consistent" is.

Concepten in het MKB

Het MKB brengt kennis van een bron in kaart in een doelwit. SME noemt elke beschrijving een dgroup . Dgroups bevatten een lijst met entiteiten en predikaten . Entiteiten vertegenwoordigen de objecten of concepten in een beschrijving, zoals een input-versnelling of een schakelaar. Predikaten zijn een van de drie typen en vormen een algemene manier om kennis uit te drukken voor het MKB.

  • Relatiepredikaten bevatten meerdere argumenten, dit kunnen andere predikaten of entiteiten zijn. Een voorbeeldrelatie is: (verzend (wat van naar)). Deze relatie heeft een functor- overdracht en heeft drie argumenten: wat, van en naar.
  • Attribuutpredikaten zijn de eigenschappen van een entiteit. Een voorbeeld van een attribuut is (red gear), wat betekent dat gear het attribuut rood heeft.
  • Functiepredikaten wijzen een entiteit toe aan een andere entiteit of constante. Een voorbeeld van een functie is ( joules power source) die de entiteit power source afbeeldt op de numerieke hoeveelheid joules.

Functies en attributen hebben verschillende betekenissen, en bijgevolg verwerkt het MKB ze anders. In de echte analogieregelset van SME verschillen attributen bijvoorbeeld van functies omdat ze niet kunnen matchen, tenzij er een match van een hogere orde tussen hen is. Het verschil tussen attributen en functies wordt verder uitgelegd in de voorbeelden van deze sectie.

Alle predikaten hebben vier parameters. Ze hebben (1) een functor, die het identificeert, en (2) een type, dat ofwel relatie, attribuut of functie is. De andere twee parameters (3 en 4) zijn om te bepalen hoe de argumenten in het SME- algoritme moeten worden verwerkt . Als de argumenten op volgorde moeten worden gevonden, is commutatief onwaar. Als het predikaat een willekeurig aantal argumenten kan hebben, is N-ary onwaar. Een voorbeeld van een predikaatdefinitie is: (kmo: defPredicate behavior-set (predicate) relation: n-ary? T: commutative? T) De functor van het predikaat is 'behavior-set', het type is 'relation' en zijn n -ary en commutatieve parameters zijn beide ingesteld op true. Het "(predikaat)" -gedeelte van de definitie specificeert dat er een of meer predikaten zullen zijn binnen een instantiatie van gedragsset.

Algoritme details

Het algoritme heeft verschillende stappen. De eerste stap van het algoritme is het creëren van een set matchhypothesen tussen bron- en doelgroepen. Een matchhypothese vertegenwoordigt een mogelijke mapping tussen een deel van de bron en het doel. Deze mapping wordt bepaald door een set matchregels. Door de matchregels te veranderen, kan men het type redenering dat SME doet, veranderen. Een set matchregels kan bijvoorbeeld een soort analogie uitvoeren die letterlijke gelijkenis wordt genoemd. en een ander voert een soort analogie uit die ware analogie wordt genoemd. Deze regels zijn niet de plaats waar domeinafhankelijke informatie wordt toegevoegd, maar waar het analogieproces wordt aangepast, afhankelijk van het type cognitieve functie dat de gebruiker probeert te emuleren.

Voor een bepaalde matchregel zijn er twee soorten regels die verder bepalen hoe deze worden toegepast: filterregels en interne regels. Interne regels gebruiken alleen de argumenten van de uitdrukkingen in de matchhypothesen die de filterregels identificeren. Deze beperking maakt de verwerking efficiënter te maken door het beperken van het aantal match hypothesen die worden gegenereerd. Tegelijkertijd helpt het ook om de structurele consistenties op te bouwen die later in het algoritme nodig zijn. Een voorbeeld van een filterregel uit de true-analogy-regelset creëert matchhypothesen tussen predikaten die dezelfde functor hebben. De true-analogy-regelset heeft een interne regel die de argumenten van elke matchhypothese herhaalt, waardoor meer matchhypothesen worden gecreëerd als de argumenten entiteiten of functies zijn, of als de argumenten attributen zijn en dezelfde functor hebben.

Om te illustreren hoe de matchregels matchhypothesen opleveren, moet u rekening houden met deze twee predicaten:

transmit torque inputgear secondgear (p1)

transmit signal switch div10 (p2)

Hier gebruiken we ware analogie voor het type redenering. De filterovereenkomstregel genereert een overeenkomst tussen p1 en p2 omdat ze dezelfde functor delen, namelijk verzenden. De interne regels produceren vervolgens nog drie matchhypothesen: koppel naar signaal, inputgear om te schakelen en secondgear naar div10. De interne regels creëerden deze matchhypothesen omdat alle argumenten entiteiten waren.

Als de argumenten functies of attributen waren in plaats van entiteiten, zouden de predikaten worden uitgedrukt als:

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

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

Deze aanvullende predikaten maken inputgear, secondgear, switch en div10 functies of attributen afhankelijk van de waarde die is gedefinieerd in het taalinvoerbestand. De weergave bevat ook extra entiteiten voor versnelling en circuit.

Afhankelijk van het type inputgear, secondgear, switch en div10 , veranderen hun betekenissen. Als attributen is elk een eigenschap van de versnelling of het circuit. De versnelling heeft bijvoorbeeld twee attributen, inputgear en secondgear. Het circuit heeft twee attributen, schakelaar en circuit. Als functies worden inputgear, secondgear, switch en div10 hoeveelheden van de uitrusting en het circuit. In dit voorbeeld zijn de functies inputgear en secondgear nu toegewezen aan de numerieke grootheden "torque from inputgear" en "torque from secondgear". Voor het circuit verwijzen de grootheden naar logische grootheid 'schakelaar ingeschakeld' en de numerieke grootheid 'huidige telling op de verdeler per 10 teller. "

Het MKB verwerkt deze anders. Het staat niet toe dat attributen overeenkomen, tenzij ze deel uitmaken van een hogere-orde relatie, maar het staat wel toe dat functies overeenkomen, zelfs als ze geen deel uitmaken van een dergelijke relatie. Hiermee kunnen functies overeenkomen omdat ze indirect naar entiteiten verwijzen en dus moeten worden behandeld als relaties waarbij geen entiteiten betrokken zijn. Zoals de volgende sectie laat zien, kennen de interne regels echter lagere gewichten toe aan overeenkomsten tussen functies dan aan overeenkomsten tussen relaties.

De reden dat SME niet overeenkomt met attributen is omdat het probeert om verbonden kennis te creëren op basis van relaties en zo te voldoen aan het systematiciteitsprincipe. Als bijvoorbeeld zowel een klok als een auto inputgear-attributen hebben, zal SME deze niet als vergelijkbaar markeren. Als dat het geval was, zou het een match maken tussen de klok en de auto op basis van hun uiterlijk - niet op basis van de relaties tussen hen.

Wanneer de aanvullende predikaten in p3 en p4 functies zijn, zijn de resultaten van het matchen van p3 en p4 vergelijkbaar met de resultaten van p1 en p2, behalve dat er een aanvullende overeenkomst is tussen versnelling en circuit en de waarden voor de matchhypothesen tussen (inputgear-versnelling) en (schakelcircuit), en (tweede versnelling) en (div10 circuit), zijn lager. In de volgende paragraaf wordt de reden hiervoor nader beschreven.

Als de inputgear, secondgear, switch en div10 attributen zijn in plaats van entiteiten, vindt SME geen overeenkomsten tussen de attributen. Het vindt alleen overeenkomsten tussen de overdrachtspredikaten en tussen koppel en signaal. Bovendien nemen de structurele evaluatiescores voor de overige twee wedstrijden af. Om de twee predikaten overeen te laten komen, zou p3 moeten worden vervangen door p5, wat hieronder wordt gedemonstreerd.

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

Aangezien de true-analogy rule set identificeert dat de div10-attributen hetzelfde zijn tussen p5 en p4 en omdat de div10-attributen beide deel uitmaken van de match met een hogere relatie tussen koppel en signaal, maakt SME een match tussen (div10 gear) en (div10 circuit) - wat leidt tot een match tussen versnelling en circuit.

Deel uitmaken van een match van een hogere orde is alleen een vereiste voor attributen. Als (div10-versnelling) en (div10-circuit) bijvoorbeeld geen deel uitmaken van een match van hogere orde, creëert SME geen matchhypothese tussen hen. Als div10 echter een functie of relatie is, creëert SME wel een match.

Structurele evaluatiescore

Zodra de matchhypothesen zijn gegenereerd, moet het MKB een evaluatiescore voor elke hypothese berekenen. SME doet dit door een reeks interne matchregels te gebruiken om positief en negatief bewijs voor elke match te berekenen. Meerdere hoeveelheden bewijs worden gecorreleerd met behulp van de regel van Dempster [Shafer, 1978] resulterend in positieve en negatieve overtuigingswaarden tussen 0 en 1. De overeenkomstregels kennen verschillende waarden toe voor overeenkomsten die betrekking hebben op functies en relaties. Deze waarden zijn echter programmeerbaar en enkele standaardwaarden die kunnen worden gebruikt om het systematiciteitsprincipe af te dwingen, worden beschreven in [Falkenhainer et al., 1989].

Deze regels zijn:

  1. Als de bron en het doel geen functies zijn en dezelfde volgorde hebben, krijgt de overeenkomst +0,3 bewijs. Als de orders binnen 1 van elkaar liggen, krijgt de wedstrijd +0,2 bewijs en -0,05 bewijs.
  2. Als de bron en het doel dezelfde functor hebben, krijgt de match 0,2 bewijs als de bron een functie is en 0,5 als de bron een relatie is.
  3. Als de argumenten overeenkomen, krijgt de overeenkomst +0,4 bewijs. De argumenten kunnen overeenkomen als alle paren argumenten tussen de bron en het doel entiteiten zijn, als de argumenten dezelfde functoren hebben, of als het doel nooit een entiteit is, maar de bron niet.
  4. Als het predikaattype overeenkomt, maar de elementen in het predikaat komen niet overeen, dan krijgt de overeenkomst -0,8 bewijs.
  5. Als de bron- en doelexpressies deel uitmaken van een overeenkomende overeenkomst van hogere orde, voegt u 0,8 van het bewijs voor de overeenkomst van hogere orde toe.

In de voorbeeldovereenkomst tussen p1 en p2 geeft SME de overeenkomst tussen de verzendrelaties een positieve bewijswaarde van 0,7900, en de anderen krijgen waarden van 0,6320. De transmit-relatie ontvangt de bewijswaarde van 0,7900 omdat het bewijs verkrijgt van regel 1, 3 en 2. De andere matches krijgen een waarde van 0,6320 omdat 0,8 van het bewijs van de transmissie wordt doorgegeven aan deze matches vanwege regel 5.

Voor predikaten p3 en p4 kent SME minder bewijs toe omdat de argumenten van de transmit-relaties functies zijn. De transmit-relatie krijgt een positief bewijs van 0,65 omdat regel 3 geen bewijs meer toevoegt. De overeenkomst tussen (ingaande versnelling) en (schakelcircuit) wordt 0,7120. Deze match krijgt 0,4 bewijs vanwege regel 3 en 0,52 bewijs dat wordt gepropageerd vanuit de verzendrelatie vanwege regel 5.

Wanneer de predikaten in p3 en p4 attributen zijn, voegt regel 4 -0,8 bewijs toe aan de verzendingsovereenkomst omdat - hoewel de functoren van de verzendrelatie overeenkomen - de argumenten niet het potentieel hebben om overeen te komen en de argumenten geen functies zijn.

Samenvattend berekenen de interne matchregels een structurele evaluatiescore voor elke matchhypothese. Deze regels versterken het systematiciteitsbeginsel. Regel 5 levert trickle-down bewijs om matches te versterken die betrokken zijn bij relaties van hogere orde. Regel 1, 3. en 4 voegen ondersteuning toe of trekken af ​​voor relaties die overeenkomende argumenten kunnen hebben. Regel 2 voegt ondersteuning toe voor de gevallen waarin de functoren overeenkomen. waardoor ondersteuning wordt toegevoegd voor overeenkomsten die relaties benadrukken.

De regels dwingen ook het verschil af tussen attributen, functies en relaties. Ze hebben bijvoorbeeld controles die minder bewijs geven voor functies dan voor relaties. Attributen worden niet specifiek behandeld door de interne matchregels, maar de filterregels van het MKB zorgen ervoor dat ze alleen in aanmerking komen voor deze regels als ze deel uitmaken van een hogere-orde relatie, en regel 2 zorgt ervoor dat attributen alleen overeenkomen als ze identiek zijn. functoren.

Gmap-creatie

De rest van het SME-algoritme is betrokken bij het creëren van maximaal consistente sets matchhypothesen. Deze sets worden gmaps genoemd. Het MKB moet ervoor zorgen dat eventuele hiaten die het creëert, structureel consistent zijn; met andere woorden, dat ze één-op-één zijn - zodat geen bron wordt toegewezen aan meerdere doelen en geen doel wordt toegewezen aan meerdere bronnen. De gmaps moeten ook worden ondersteund, wat betekent dat als er een matchhypothese in de gmap staat, dat ook geldt voor de matchhypothese die betrekking heeft op de bron- en doelitems.

Het aanmaakproces van gmap verloopt in twee stappen. Ten eerste berekent SME informatie over elke matchhypothese - inclusief entiteitstoewijzingen, eventuele conflicten met andere hypothesen en welke andere matchhypothesen waarmee deze mogelijk structureel inconsistent is.

SME gebruikt deze informatie vervolgens om matchhypothesen samen te voegen - met behulp van een hebberig algoritme en de structurele evaluatiescore. Het voegt de matchhypothesen samen tot maximaal structureel consistente, onderling verbonden grafieken van matchhypothesen. Vervolgens worden hiaten gecombineerd die een overlappende structuur hebben als ze structureel consistent zijn. Ten slotte combineert het onafhankelijke hiaten samen met behoud van structurele consistentie.

Het vergelijken van een bron met een doelgroep kan een of meer hiaten opleveren. Het gewicht voor elke gmap is de som van alle positieve bewijswaarden voor alle matchhypothesen die bij de gmap zijn betrokken. Als bijvoorbeeld een bron met p1 en p6 hieronder wordt vergeleken met een doel dat p2 bevat, genereert SME twee hiaten. Beide gmaps hebben een gewicht van 2,9186.

Bron:

transmit torque inputgear secondgear (p1)

transmit torque secondgear thirdgear (p6)

Doelwit: transmit signal switch div10 (p2)

Dit zijn de hiaten die het resultaat zijn van het vergelijken van een bron met een p1 en p6 en een doel met p2.

Gmap nr. 1: 

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

Gmap nr. 2 : 

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

De tussenruimten tonen paren van predikaten of entiteiten die overeenkomen. Bijvoorbeeld, in gmap nr. 1 komen de koppel en het signaal van de entiteiten overeen en de gedragingen zenden de tweede versnelling van de koppelinvoer uit en de zendsignaalschakelaar div10 komen overeen. Gmap nr. 1 staat voor het combineren van p1 en p2. Gmap nr. 2 staat voor het combineren van p1 en p6. Hoewel p2 compatibel is met zowel p1 als p6, dwingt de een-op-een toewijzingsbeperking af dat beide toewijzingen niet in dezelfde gmap kunnen staan. Daarom produceert het MKB twee onafhankelijke hiaten. Bovendien zou het combineren van de twee gmaps de entiteitstoewijzingen tussen thirdgear en div10 in conflict brengen met de entiteitstoewijzing tussen secondgear en div10.

Kritiek

Chalmers, French, en Hofstadter [1992] bekritiseren het MKB vanwege zijn afhankelijkheid van handmatig geconstrueerde LISP- representaties als input. Ze beweren dat er te veel menselijke creativiteit nodig is om deze representaties te construeren; de intelligentie komt van het ontwerp van de input, niet van het MKB. Forbus et al. [1998] probeerde deze kritiek te weerleggen. Morrison en Dietrich [1995] probeerden de twee standpunten met elkaar te verzoenen. Turney [2008] presenteert een algoritme dat geen LISP-invoer vereist, maar toch de principes van Structure Mapping Theory volgt. Turney [2008] stelt dat ook hun werk niet immuun is voor de kritiek van Chalmers, French en Hofstadter [1992].

In haar artikel Hoe creatieve ideeën vorm krijgen, schrijft Liane Gabora: "Volgens de helende theorie van creativiteit werkt creatief denken niet op individueel overwogen, discrete, vooraf gedefinieerde representaties, maar op een contextueel opgewekte amalgaam van items die bestaan ​​in een staat van potentialiteit en Dit leidt tot de voorspelling dat het maken van analogieën niet voortkomt uit het in kaart brengen van overeenkomsten van kandidaat-bronnen naar het doelwit, zoals voorspeld door de analogie-theorie van de structuurtoewijzing, maar door niet-overeenkomsten weg te werken, waardoor de potentie wordt weggenomen. ''

Referenties

Verder lezen