Motor de cartografiere a structurii - Structure mapping engine

În inteligența artificială și știința cognitivă , motorul de cartografiere a structurilor ( IMM ) este o implementare în software a unui algoritm de potrivire analogică bazat pe teoria psihologică a lui Dedre Gentner . Baza ideii de mapare a structurii lui Gentner este că o analogie este o cartografiere a cunoașterii dintr-un domeniu (baza) în altul (ținta). Motorul de mapare a structurii este o simulare pe computer a analogiei și a comparațiilor de similaritate.

Începând cu 1990, peste 40 de proiecte îl folosiseră [Falkenhainer, 2005]. RM French a spus că teoria cartografierii structurilor este „fără îndoială cea mai influentă lucrare de până acum a modelării analogiei” [2002].

Teoria este utilă deoarece ignoră trăsăturile suprafeței și găsește potriviri între lucruri potențial foarte diferite dacă au aceeași structură reprezentativă. De exemplu, IMM-urile ar putea determina faptul că un stilou este ca un burete, deoarece ambii sunt implicați în distribuirea lichidului, chiar dacă fac acest lucru foarte diferit.

Teoria cartografierii structurilor

Teoria cartografierii structurilor se bazează pe principiul sistematicității, care afirmă că cunoașterea conectată este preferată fațelor independente. Prin urmare, motorul de mapare a structurii ar trebui să ignore mapările sursă-țintă izolate, cu excepția cazului în care fac parte dintr-o structură mai mare. Teoria spune că IMM-urile ar trebui să mapeze obiecte care sunt legate de cunoștințe care au fost deja mapate.

Teoria necesită, de asemenea, ca mapările să fie făcute unu-la-unu , ceea ce înseamnă că nicio parte a descrierii sursei nu poate fi mapată la mai mult de un element din țintă și nici o parte a descrierii țintei nu poate fi mapată la mai mult de o parte a sursă. Teoria impune, de asemenea, că, dacă o potrivire mapează subiectul țintei, argumentele subiectului și țintei trebuie, de asemenea, mapate. Dacă ambele condiții sunt îndeplinite, cartarea se spune că este „structurală consecventă”.

Concepte în IMM-uri

IMM-urile mapează cunoștințele dintr-o sursă într-o țintă. IMM-urile numesc fiecare descriere un grup de grupuri . Grupurile D conțin o listă de entități și predicate . Entitățile reprezintă obiectele sau conceptele dintr-o descriere - cum ar fi o treaptă de intrare sau un comutator. Predicații sunt unul dintre cele trei tipuri și reprezintă un mod general de exprimare a cunoștințelor pentru IMM-uri.

  • Predicatele de relație conțin mai multe argumente, care pot fi alte predicate sau entități. Un exemplu de relație este: (transmite (ce de la până la)). Această relație are un functor de transmisie și ia trei argumente: ce, de la, și la.
  • Predicatele de atribute sunt proprietățile unei entități. Un exemplu de atribut este (roata roșie) care înseamnă că roata are atributul roșu.
  • Predicatele funcționale mapează o entitate într-o altă entitate sau constantă. Un exemplu de funcție este ( sursa de putere în juli ) care mapează sursa de energie a entității pe cantitatea de juli numerică .

Funcțiile și atributele au semnificații diferite și, în consecință, IMM-urile le procesează diferit. De exemplu, în setul de reguli de analogie adevărat al IMM-urilor, atributele diferă de funcții deoarece nu se pot potrivi decât dacă există o potrivire de ordin superior între ele. Diferența dintre atribute și funcții va fi explicată în continuare în exemplele acestei secțiuni.

Toate predicatele au patru parametri. Au (1) un functor, care îl identifică, și (2) un tip, care este fie relație, atribut sau funcție. Ceilalți doi parametri (3 și 4) sunt pentru a determina modul de procesare a argumentelor din algoritmul IMM . Dacă argumentele trebuie potrivite în ordine, comutativul este fals. Dacă predicatul poate lua orice număr de argumente, N-ary este fals. Un exemplu de definiție a predicatului este: (sme: defPredicate comportament-set (predicat) relație: n-ary? T: comutativ? T) Functorul predicatului este „comportament-set”, tipul său este „relație”, iar n -ar și parametrii comutativi sunt ambii setați la adevărat. Partea „(predicat)” din definiție specifică faptul că vor exista unul sau mai multe predicate în interiorul unei instanțieri a setului de comportament.

Detalii algoritm

Algoritmul are mai mulți pași. Primul pas al algoritmului este de a crea un set de ipoteze de potrivire între grupurile d sursă și țintă. O ipoteză de potrivire reprezintă o posibilă mapare între orice parte a sursei și țintă. Această mapare este controlată de un set de reguli de potrivire. Prin modificarea regulilor de potrivire, se poate schimba tipul de raționament pe care îl face IMM-ul. De exemplu, un set de reguli de potrivire poate efectua un fel de analogie numită similaritate literală. iar altul efectuează un fel de analogie numită adevărată-analogie. Aceste reguli nu sunt locul în care se adaugă informații dependente de domeniu, ci mai degrabă unde procesul de analogie este modificat, în funcție de tipul de funcție cognitivă pe care utilizatorul încearcă să o emule.

Pentru o anumită regulă de potrivire, există două tipuri de reguli care definesc în continuare modul în care va fi aplicată: reguli de filtrare și reguli interne. Regulile interne utilizează numai argumentele expresiilor din ipotezele de potrivire pe care regulile de filtrare le identifică. Această limitare face procesarea mai eficientă prin constrângerea numărului de ipoteze de potrivire care sunt generate. În același timp, ajută și la construirea consistențelor structurale necesare mai târziu în algoritm. Un exemplu de regulă de filtrare din setul de reguli de analogie adevărată creează ipoteze de potrivire între predicate care au același functor. Setul de reguli de analogie adevărată are o regulă internă care iterează asupra argumentelor oricărei ipoteze de potrivire, creând mai multe ipoteze de potrivire dacă argumentele sunt entități sau funcții sau dacă argumentele sunt atribute și au același functor.

Pentru a ilustra modul în care regulile de potrivire produc ipoteze de potrivire, luați în considerare aceste două predicate:

transmit torque inputgear secondgear (p1)

transmit signal switch div10 (p2)

Aici folosim analogia adevărată pentru tipul de raționament. Regula de potrivire a filtrului generează o potrivire între p1 și p2 deoarece împărtășesc același functor, transmite. Regulile interne produc apoi încă trei ipoteze de potrivire: cuplu pentru semnal, intrare pentru a comuta și a doua pentru a div10. Regulile interne au creat aceste ipoteze de potrivire deoarece toate argumentele erau entități.

Dacă argumentele ar fi funcții sau atribute în loc de entități, predicatele ar fi exprimate ca:

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

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

Aceste predicate suplimentare fac funcții sau atribute inputgear, secondgear, switch și div10 în funcție de valoarea definită în fișierul de introducere a limbii. Reprezentarea conține, de asemenea, entități suplimentare pentru transmisie și circuit.

În funcție de ce tip sunt inputgear, secondgear, switch și div10 , semnificațiile lor se schimbă. Ca atribute, fiecare este o proprietate a angrenajului sau circuitului. De exemplu, angrenajul are două atribute, inputgear și secondgear. Circuitul are două atribute, comutator și circuit. Ca funcții inputgear, secondgear, switch și div10 devin cantități ale angrenajului și circuitului. În acest exemplu, funcțiile inputgear și secondgear se mapează acum la mărimile numerice „cuplu de la inputgear” și „cuplu de la secondgear”, pentru circuit, cantitățile se mapează la mărimea logică „comută cuplat” și cantitatea numerică „contează curentul pe divizare cu 10 contra. "

IMM-urile le procesează diferit. Nu permite ca atributele să se potrivească decât dacă fac parte dintr-o relație de ordin superior, dar permite funcțiilor să se potrivească, chiar dacă nu fac parte dintr-o astfel de relație. Permite funcțiilor să se potrivească deoarece se referă indirect la entități și, prin urmare, ar trebui tratate ca relații care nu implică entități. Cu toate acestea, după cum arată secțiunea următoare, regulile interne atribuie greutăți mai mici meciurilor dintre funcții decât meciurilor dintre relații.

Motivul pentru care IMM-ul nu se potrivește cu atributele este că încearcă să creeze cunoștințe conectate bazate pe relații și astfel să satisfacă principiul sistematicității. De exemplu, dacă atât un ceas cât și o mașină au atribute inputgear, IMM-urile nu le vor marca ca similare. Dacă ar face-o, ar fi să facă o potrivire între ceas și mașină pe baza aspectului lor - nu pe relațiile dintre ei.

Când predicatele suplimentare din p3 și p4 sunt funcții, rezultatele din potrivirea p3 și p4 sunt similare cu rezultatele din p1 și p2, cu excepția faptului că există o potrivire suplimentară între treaptă și circuit și valorile pentru ipotezele potrivirii dintre (treapta de transmisie) și (circuitul de comutare) și (treapta de viteză secundară) și (circuitul div10), sunt mai mici. Următoarea secțiune descrie motivul pentru aceasta în detaliu.

Dacă inputgear, secondgear, switch și div10 sunt atribute în loc de entități, IMM-ul nu găsește potriviri între niciunul dintre atribute. Acesta găsește potriviri numai între predicatele de transmisie și între cuplu și semnal. În plus, scorurile de evaluare structurală pentru celelalte două meciuri scad. Pentru ca cele două predicate să se potrivească, p3 ar trebui înlocuit cu p5, lucru demonstrat mai jos.

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

Deoarece setul de reguli de analogie adevărată identifică faptul că atributele div10 sunt aceleași între p5 și p4 și deoarece atributele div10 fac parte din relația superioară dintre cuplu și semnal, SME face o potrivire între (div10 gear) și (div10 circuit) - care duce la o potrivire între treaptă de viteză și circuit.

A face parte dintr-o potrivire de ordin superior este o cerință numai pentru atribute. De exemplu, dacă (div10 gear) și (div10 circuit) nu fac parte dintr-un meci de ordin superior, IMM-urile nu creează o ipoteză de match între ele. Cu toate acestea, dacă div10 este o funcție sau o relație, IMM-ul creează o potrivire.

Scorul de evaluare structurală

După generarea ipotezelor de potrivire, IMM-urile trebuie să calculeze un scor de evaluare pentru fiecare ipoteză. IMM-urile fac acest lucru utilizând un set de reguli de meci intern pentru a calcula dovezi pozitive și negative pentru fiecare meci. Cantități multiple de dovezi sunt corelate folosind regula lui Dempster [Shafer, 1978], rezultând valori de credință pozitive și negative între 0 și 1. Regulile de potrivire atribuie valori diferite pentru potrivirile care implică funcții și relații. Aceste valori sunt totuși programabile, iar unele valori implicite care pot fi utilizate pentru a impune principiul sistematicității sunt descrise în [Falkenhainer și colab., 1989].

Aceste reguli sunt:

  1. Dacă sursa și ținta nu sunt funcții și au aceeași ordine, meciul obține +0,3 dovezi. În cazul în care ordinele se află la 1 unul de celălalt, meciul primește +0,2 probe și -0,05 probe.
  2. Dacă sursa și ținta au același functor, potrivirea obține 0,2 dovezi dacă sursa este o funcție și 0,5 dacă sursa este o relație.
  3. Dacă argumentele se potrivesc, meciul obține +0,4 dovezi. Argumentele s-ar putea potrivi dacă toate perechile de argumente dintre sursă și țintă sunt entități, dacă argumentele au aceleași funcții sau nu este niciodată cazul în care ținta este o entitate, dar sursa nu.
  4. Dacă tipul de predicat se potrivește, dar elementele din predicat nu se potrivesc, atunci meciul obține -0,8 dovezi.
  5. Dacă expresiile sursă și țintă fac parte dintr-o potrivire de ordine superioară potrivită, adăugați 0,8 din dovezile pentru potrivirea de ordin superior.

În exemplul de potrivire dintre p1 și p2, IMM-ul conferă potrivirii dintre relațiile de transmisie o valoare pozitivă a dovezilor de 0,7900, iar celelalte obțin valori de 0,6320. Relația de transmisie primește valoarea dovezii de 0,7900 deoarece câștigă dovezi din regulile 1, 3 și 2. Celelalte potriviri obțin o valoare de 0,6320 deoarece 0,8 din dovezile din transmisiune se propagă la aceste potriviri din cauza regulii 5.

Pentru predicatele p3 și p4, IMM-urile atribuie mai puține dovezi, deoarece argumentele relațiilor de transmisie sunt funcții. Relația de transmisie obține dovezi pozitive de 0,65 deoarece regula 3 nu mai adaugă dovezi. Potrivirea dintre (treapta de intrare) și (circuitul de comutare) devine 0,7120. Această potrivire obține 0,4 dovezi din cauza regulii 3 și 0,52 dovezi propagate din relația de transmisie din cauza regulii 5.

Când predicatele din p3 și p4 sunt atribute, regula 4 adaugă -0,8 dovezi la potrivirea de transmisie, deoarece - deși functorii relației de transmisie se potrivesc - argumentele nu au potențialul de a se potrivi și argumentele nu sunt funcții.

Pentru a rezuma, regulile meciului intern calculează un scor de evaluare structurală pentru fiecare ipoteză meci. Aceste reguli impun principiul sistematicității. Regula 5 oferă dovezi de scurgere pentru a întări meciurile implicate în relații de ordin superior. Regulile 1, 3. și 4 adaugă sau scad suport pentru relații care ar putea avea argumente potrivite. Regula 2 adaugă suport pentru cazurile în care funcțiile se potrivesc. adăugând astfel suport pentru meciurile care pun accentul pe relații.

Regulile impun, de asemenea, diferența dintre atribute, funcții și relații. De exemplu, au verificări care oferă mai puține dovezi pentru funcții decât relațiile. Atributele nu sunt tratate în mod specific de regulile de potrivire internă, dar regulile de filtrare ale IMM-urilor asigură că vor fi luate în considerare pentru aceste reguli numai dacă fac parte dintr-o relație de ordin superior, iar regula 2 asigură că atributele se vor potrivi numai dacă au identice functori.

Crearea Gmap

Restul algoritmului IMM-urilor este implicat în crearea unor seturi maxime consistente de ipoteze de potrivire. Aceste seturi se numesc gmaps. IMM-urile trebuie să se asigure că orice lacune pe care le creează sunt consistente din punct de vedere structural; cu alte cuvinte, că sunt unu-la-unu - astfel încât nici o sursă nu se mapează la mai multe ținte și nici o țintă nu este mapată la mai multe surse. Gmaps trebuie să aibă, de asemenea, suport, ceea ce înseamnă că, dacă o ipoteză de potrivire este în gmap, la fel și ipoteza de potrivire care implică elementele sursă și țintă.

Procesul de creare a gmap urmează doi pași. În primul rând, IMM-urile calculează informații despre fiecare ipoteză de potrivire - inclusiv mapări de entități, orice conflicte cu alte ipoteze și ce alte ipoteze de potrivire cu care ar putea fi inconsecventă din punct de vedere structural.

IMM-urile folosesc apoi aceste informații pentru a îmbina ipotezele potrivirii - folosind un algoritm lacom și scorul de evaluare structurală. Fuzionează ipotezele potrivirii în grafice conectate din punct de vedere structural corespunzătoare ale ipotezelor potrivirii. Apoi combină gmaps care au structură suprapusă dacă sunt consistente din punct de vedere structural. În cele din urmă, combină gmaps independente împreună, menținând în același timp consistența structurală.

Compararea unei surse cu un grup de țintă țintă poate produce unul sau mai multe gmaps. Ponderea pentru fiecare gmap este suma tuturor valorilor dovezilor pozitive pentru toate ipotezele de potrivire implicate în gmap. De exemplu, dacă o sursă care conține p1 și p6 de mai jos, este comparată cu o țintă care conține p2, IMM-ul va genera două gmaps. Ambele gmaps au o greutate de 2,9186.

Sursă:

transmit torque inputgear secondgear (p1)

transmit torque secondgear thirdgear (p6)

Ţintă: transmit signal switch div10 (p2)

Acestea sunt lacunele care rezultă din compararea unei surse care conține p1 și p6 și o țintă care conține 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)

Gmaps arată perechi de predicate sau entități care se potrivesc. De exemplu, în gmap nr. 1, cuplul entităților și semnalul se potrivesc și comportamentele transmit cuplul de intrare second-gear și transmit semnalul comutator div10 meci. Gmap No. 1 reprezintă combinarea p1 și p2. Gmap nr. 2 reprezintă combinarea p1 și p6. Deși p2 este compatibil atât cu p1 cât și cu p6, constrângerea de mapare one-to-one impune că ambele mapări nu pot fi în același gmap. Prin urmare, IMM-urile produc două gmaps independente. În plus, combinarea celor două gmaps împreună ar face ca mapările entității dintre thirdgear și div10 să intre în conflict cu maparea entității între secondgear și div10.

Critici

Chalmers, French și Hofstadter [1992] critică IMM-urile pentru dependența de reprezentări LISP construite manual ca input. Ei susțin că este necesară prea multă creativitate umană pentru a construi aceste reprezentări; inteligența vine de la proiectarea intrării, nu de la IMM-uri. Forbus și colab. [1998] a încercat să respingă această critică. Morrison și Dietrich [1995] au încercat să împace cele două puncte de vedere. Turney [2008] prezintă un algoritm care nu necesită intrare LISP, însă urmează principiile teoriei mapării structurilor. Turney [2008] afirmă că și munca lor nu este imună la criticile lui Chalmers, French și Hofstadter [1992].

În articolul său How Creative Ideas Take Shape, Liane Gabora scrie „Conform teoriei de perfecționare a creativității, gândirea creativă nu funcționează pe reprezentări individuale luate în considerare, discrete, predefinite, ci pe un amalgam contextual de elemente care există într-o stare de potențialitate și s-ar putea să nu fie ușor de separat. Acest lucru duce la prezicerea faptului că realizarea analogiei are loc nu prin maparea corespondențelor de la sursele candidate la țintă, așa cum se prezice prin teoria cartografierii structurii analogiei, ci prin eliminarea necorespondențelor, reducând astfel potențialitatea. "

Referințe

Lecturi suplimentare