Mecanismo de mapeamento de estrutura - Structure mapping engine

Em inteligência artificial e ciência cognitiva , o mecanismo de mapeamento de estrutura ( SME ) é uma implementação em software de um algoritmo de correspondência analógica baseado na teoria psicológica de Dedre Gentner . A base da ideia de mapeamento de estrutura de Gentner é que uma analogia é um mapeamento de conhecimento de um domínio (a base) para outro (o alvo). O mecanismo de mapeamento de estrutura é uma simulação de computador das comparações de analogia e similaridade.

Em 1990, mais de 40 projetos o haviam usado [Falkenhainer, 2005]. RM French disse que a teoria do mapeamento de estrutura é "inquestionavelmente o trabalho mais influente até o momento da modelagem da criação de analogias" [2002].

A teoria é útil porque ignora características de superfície e encontra correspondências entre coisas potencialmente muito diferentes se elas tiverem a mesma estrutura representacional. Por exemplo, o SME pode determinar que uma caneta é como uma esponja porque ambas estão envolvidas na distribuição de líquidos, embora façam isso de maneira muito diferente.

Teoria de mapeamento de estrutura

A teoria do mapeamento de estrutura é baseada no princípio da sistematicidade, que afirma que o conhecimento conectado é preferível a fatos independentes. Portanto, o mecanismo de mapeamento de estrutura deve ignorar mapeamentos de origem-destino isolados, a menos que eles façam parte de uma estrutura maior. O SME, diz a teoria, deve mapear objetos que estão relacionados ao conhecimento que já foi mapeado.

A teoria também requer que os mapeamentos sejam feitos um a um , o que significa que nenhuma parte da descrição de origem pode ser mapeada para mais de um item no destino e nenhuma parte da descrição do destino pode ser mapeada para mais de uma parte do fonte. A teoria também exige que, se uma correspondência mapeia sujeito a alvo, os argumentos de sujeito e alvo também devem ser mapeados. Se ambas as condições forem atendidas, o mapeamento é considerado "estruturalmente consistente".

Conceitos em PME

O SME mapeia o conhecimento de uma fonte para um alvo. O SME chama cada descrição de dgroup . Dgroups contém uma lista de entidades e predicados . As entidades representam os objetos ou conceitos em uma descrição - como uma engrenagem de entrada ou uma chave. Predicados são um dos três tipos e são uma forma geral de expressar conhecimento para as PME.

  • Os predicados de relação contêm vários argumentos, que podem ser outros predicados ou entidades. Um exemplo de relação é: (transmitir (de que para)). Essa relação tem um functor transmitido e recebe três argumentos: o quê, de e para.
  • Predicados de atributo são as propriedades de uma entidade. Um exemplo de atributo é (engrenagem vermelha), o que significa que a engrenagem tem o atributo vermelho.
  • Os predicados de função mapeiam uma entidade em outra entidade ou constante. Um exemplo de função é ( fonte de energia em joules ) que mapeia a fonte de energia da entidade na quantidade numérica de joules.

Funções e atributos têm significados diferentes e, consequentemente, o SME os processa de forma diferente. Por exemplo, no verdadeiro conjunto de regras de analogia do SME, os atributos diferem das funções porque não podem corresponder, a menos que haja uma correspondência de ordem superior entre eles. A diferença entre atributos e funções será explicada mais adiante nos exemplos desta seção.

Todos os predicados têm quatro parâmetros. Eles têm (1) um functor, que o identifica, e (2) um tipo, que é relação, atributo ou função. Os outros dois parâmetros (3 e 4) são para determinar como processar os argumentos no algoritmo SME . Se os argumentos precisam ser combinados em ordem, comutativo é falso. Se o predicado pode receber qualquer número de argumentos, N-ário é falso. Um exemplo de definição de predicado é: (sme: defPredicado conjunto de comportamento (predicado) relação: n-ária? T: comutativa? T) O functor do predicado é “conjunto de comportamento”, seu tipo é “relação” e seu n Os parâmetros -ary e commutative são ambos definidos como true. A parte “(predicado)” da definição especifica que haverá um ou mais predicados dentro de uma instanciação do conjunto de comportamento.

Detalhes do algoritmo

O algoritmo possui várias etapas. A primeira etapa do algoritmo é criar um conjunto de hipóteses de correspondência entre os dgroups de origem e de destino. Uma hipótese de correspondência representa um possível mapeamento entre qualquer parte da origem e do destino. Esse mapeamento é controlado por um conjunto de regras de correspondência. Ao mudar as regras de jogo, pode-se mudar o tipo de raciocínio que o SME faz. Por exemplo, um conjunto de regras de correspondência pode realizar um tipo de analogia chamada similaridade literal. e outro realiza um tipo de analogia chamada analogia verdadeira. Essas regras não são o lugar onde as informações dependentes do domínio são adicionadas, mas sim onde o processo de analogia é ajustado, dependendo do tipo de função cognitiva que o usuário está tentando emular.

Para uma determinada regra de correspondência, existem dois tipos de regras que definem melhor como ela será aplicada: regras de filtro e regras internas. As regras internas usam apenas os argumentos das expressões nas hipóteses de correspondência que as regras de filtro identificam. Essa limitação torna o processamento mais eficiente ao restringir o número de hipóteses de correspondência que são geradas. Ao mesmo tempo, também ajuda a construir as consistências estruturais que são necessárias posteriormente no algoritmo. Um exemplo de regra de filtro do conjunto de regras de analogia verdadeira cria hipóteses de correspondência entre predicados que têm o mesmo functor. O conjunto de regras de analogia verdadeira tem uma regra interna que itera sobre os argumentos de qualquer hipótese de correspondência, criando mais hipóteses de correspondência se os argumentos forem entidades ou funções, ou se os argumentos forem atributos e tiverem o mesmo functor.

Para ilustrar como as regras de correspondência produzem hipóteses de correspondência, considere estes dois predicados:

transmit torque inputgear secondgear (p1)

transmit signal switch div10 (p2)

Aqui usamos a verdadeira analogia para o tipo de raciocínio. A regra de correspondência de filtro gera uma correspondência entre p1 e p2 porque eles compartilham o mesmo functor, transmitir. As regras internas, então, produzem mais três hipóteses de correspondência: torque para sinal, engrenagem de entrada para alternar e segunda engrenagem para div10. As regras internas criaram essas hipóteses de correspondência porque todos os argumentos eram entidades.

Se os argumentos fossem funções ou atributos em vez de entidades, os predicados seriam expressos como:

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

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

Esses predicados adicionais fazem funções ou atributos inputgear, secondgear, switch e div10, dependendo do valor definido no arquivo de entrada de idioma. A representação também contém entidades adicionais para engrenagem e circuito.

Dependendo do tipo de engrenagem de entrada, engrenagem secundária, interruptor e div10 , seus significados mudam. Como atributos, cada um é uma propriedade da engrenagem ou circuito. Por exemplo, a engrenagem tem dois atributos, inputgear e secondgear. O circuito tem dois atributos, switch e circuito. À medida que as funções inputgear, secondgear, switch e div10 tornam-se quantidades da engrenagem e do circuito. Neste exemplo, as funções inputgear e secondgear agora mapeiam para as quantidades numéricas "torque do inputgear" e "torque do secondgear", para o circuito, as quantidades mapeiam a quantidade lógica "interruptor engatado" e a quantidade numérica "contagem de corrente na divisão por 10 contadores. ”

A SME os processa de maneira diferente. Ele não permite que atributos correspondam, a menos que sejam parte de uma relação de ordem superior, mas permite que funções correspondam, mesmo que não façam parte de tal relação. Ele permite a correspondência de funções porque indiretamente se referem a entidades e, portanto, devem ser tratadas como relações que não envolvem entidades. No entanto, como mostra a próxima seção, as regras internas atribuem pesos menores às correspondências entre funções do que às correspondências entre relações.

A razão pela qual o SME não combina atributos é porque ele está tentando criar conhecimento conectado com base em relacionamentos e, assim, satisfazer o princípio de sistematicidade. Por exemplo, se um relógio e um carro tiverem atributos de engrenagem de entrada, o SME não os marcará como semelhantes. Se isso acontecesse, seria fazer uma correspondência entre o relógio e o carro com base em sua aparência - não nas relações entre eles.

Quando os predicados adicionais em p3 e p4 são funções, os resultados da correspondência p3 e p4 são semelhantes aos resultados de p1 e p2, exceto que há uma correspondência adicional entre a engrenagem e o circuito e os valores para as hipóteses de correspondência entre (engrenagem de entrada) e (interruptor de circuito), e (segunda marcha) e (circuito div10), são mais baixos. A próxima seção descreve o motivo disso com mais detalhes.

Se inputgear, secondgear, switch e div10 forem atributos em vez de entidades, o SME não encontrará correspondências entre nenhum dos atributos. Ele encontra correspondências apenas entre os predicados de transmissão e entre o torque e o sinal. Além disso, as pontuações da avaliação estrutural para as duas partidas restantes diminuem. Para que os dois predicados coincidam, p3 precisaria ser substituído por p5, o que é demonstrado a seguir.

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

Uma vez que o conjunto de regras de analogia verdadeira identifica que os atributos div10 são os mesmos entre p5 e p4 e porque os atributos div10 são ambos parte da correspondência de relação mais alta entre torque e sinal, SME faz uma correspondência entre (div10 engrenagem) e (div10 circuito) - o que leva a uma correspondência entre a engrenagem e o circuito.

Fazer parte de uma correspondência de ordem superior é um requisito apenas para atributos. Por exemplo, se (div10 gear) e (div10 circuit) não fizerem parte de uma correspondência de ordem superior, o SME não cria uma hipótese de correspondência entre eles. No entanto, se div10 for uma função ou relação, o SME cria uma correspondência.

Pontuação de avaliação estrutural

Uma vez que as hipóteses de correspondência são geradas, o SME precisa calcular uma pontuação de avaliação para cada hipótese. O SME faz isso usando um conjunto de regras de correspondência interna para calcular as evidências positivas e negativas para cada correspondência. Múltiplas quantidades de evidências são correlacionadas usando a regra de Dempster [Shafer, 1978], resultando em valores de crença positivos e negativos entre 0 e 1. As regras de correspondência atribuem valores diferentes para correspondências envolvendo funções e relações. Esses valores são programáveis, no entanto, e alguns valores padrão que podem ser usados ​​para reforçar o princípio de sistematicidade são descritos em [Falkenhainer et al., 1989].

Essas regras são:

  1. Se a origem e o destino não são funções e têm a mesma ordem, a correspondência obtém +0,3 de evidência. Se as ordens estiverem dentro de 1 uma da outra, a correspondência obtém +0,2 de evidência e -0,05 de evidência.
  2. Se a origem e o destino têm o mesmo functor, a correspondência obtém 0,2 evidência se a origem for uma função e 0,5 se a origem for uma relação.
  3. Se os argumentos corresponderem, a correspondência obterá evidência de +0,4. Os argumentos podem corresponder se todos os pares de argumentos entre a origem e o destino forem entidades, se os argumentos tiverem os mesmos functores ou nunca for o caso de o destino ser uma entidade, mas a origem não.
  4. Se o tipo de predicado corresponder, mas os elementos no predicado não corresponderem, a correspondência obterá evidência de -0,8.
  5. Se as expressões de origem e destino fizerem parte de uma correspondência de ordem superior correspondente, adicione 0,8 da evidência para a correspondência de ordem superior.

No exemplo de correspondência entre p1 e p2, SME fornece à correspondência entre as relações de transmissão um valor de evidência positivo de 0,7900 e as outras obtêm valores de 0,6320. A relação de transmissão recebe o valor de evidência de 0,7900 porque ganha evidência das regras 1, 3 e 2. As outras correspondências obtêm um valor de 0,6320 porque 0,8 da evidência da transmissão é propagado para essas correspondências devido à regra 5.

Para os predicados p3 e p4, SME atribui menos evidências porque os argumentos das relações de transmissão são funções. A relação de transmissão obtém evidência positiva de 0,65 porque a regra 3 não adiciona mais evidência. A correspondência entre (engrenagem de entrada) e (circuito da chave) torna-se 0,7120. Essa correspondência obtém 0,4 de evidência por causa da regra 3 e 0,52 de evidência propagada da relação de transmissão por causa da regra 5.

Quando os predicados em p3 e p4 são atributos, a regra 4 adiciona -0,8 evidência à correspondência de transmissão porque - embora os functores da relação de transmissão correspondam - os argumentos não têm potencial para corresponder e os argumentos não são funções.

Para resumir, as regras de correspondência interna calculam uma pontuação de avaliação estrutural para cada hipótese de correspondência. Essas regras reforçam o princípio da sistematicidade. A regra 5 fornece evidências gradativas para fortalecer as correspondências que estão envolvidas em relações de ordem superior. As regras 1, 3. e 4 adicionam ou subtraem suporte para relações que podem ter argumentos correspondentes. A regra 2 adiciona suporte para os casos em que os functores combinam. adicionando assim suporte para correspondências que enfatizam os relacionamentos.

As regras também reforçam a diferença entre atributos, funções e relações. Por exemplo, eles têm verificações que fornecem menos evidência de funções do que relações. Os atributos não são tratados especificamente pelas regras de correspondência interna, mas as regras de filtro do SME garantem que eles só serão considerados para essas regras se fizerem parte de uma relação de ordem superior, e a regra 2 garante que os atributos só corresponderão se forem idênticos functores.

Criação Gmap

O resto do algoritmo SME está envolvido na criação de conjuntos de hipóteses de correspondência com consistência máxima. Esses conjuntos são chamados de gmaps. O SME deve garantir que quaisquer gmaps que ele crie sejam estruturalmente consistentes; em outras palavras, eles são um para um - de forma que nenhuma origem seja mapeada para vários destinos e nenhum destino seja mapeado para várias fontes. O gmaps também deve ter suporte, o que significa que se uma hipótese de correspondência está no gmap, então também estão as hipóteses de correspondência que envolvem os itens de origem e destino.

O processo de criação do gmap segue duas etapas. Primeiro, o SME calcula informações sobre cada hipótese de correspondência - incluindo mapeamentos de entidade, quaisquer conflitos com outras hipóteses e quais outras hipóteses de correspondência com as quais pode ser estruturalmente inconsistente.

O SME então usa essas informações para mesclar hipóteses de correspondência - usando um algoritmo ganancioso e a pontuação de avaliação estrutural. Ele funde as hipóteses de correspondência em gráficos conectados estruturalmente consistentes com as hipóteses de correspondência. Em seguida, ele combina gmaps que têm estrutura sobreposta, se forem estruturalmente consistentes. Finalmente, ele combina gmaps independentes enquanto mantém a consistência estrutural.

Comparar uma fonte com um dgroup alvo pode produzir um ou mais gmaps. O peso para cada gmap é a soma de todos os valores de evidências positivas para todas as hipóteses de correspondência envolvidas no gmap. Por exemplo, se uma fonte contendo p1 e p6 abaixo, for comparada a um destino contendo p2, o SME irá gerar dois gmaps. Ambos os gmaps têm um peso de 2,9186.

Fonte:

transmit torque inputgear secondgear (p1)

transmit torque secondgear thirdgear (p6)

Alvo: transmit signal switch div10 (p2)

Estes são os gmaps que resultam da comparação de uma fonte contendo um p1 e p6 e um destino contendo p2.

Gmap No. 1: 

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

Gmap No. 2 : 

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

Os gmaps mostram pares de predicados ou entidades que correspondem. Por exemplo, no gmap No. 1, o torque das entidades e o sinal combinam e os comportamentos transmitem o torque da engrenagem de entrada da segunda engrenagem e transmitem a combinação do interruptor do sinal div10. Gmap No. 1 representa a combinação de p1 e p2. Gmap No. 2 representa a combinação de p1 e p6. Embora p2 seja compatível com p1 e p6, a restrição de mapeamento um para um impõe que ambos os mapeamentos não possam estar no mesmo gmap. Portanto, a SME produz dois gmaps independentes. Além disso, combinar os dois gmaps faria com que os mapeamentos de entidade entre a terceira marcha e div10 entrassem em conflito com o mapeamento de entidade entre a segunda marcha e div10.

Críticas

Chalmers, French e Hofstadter [1992] criticam o SME por sua confiança em representações LISP construídas manualmente como entrada. Eles argumentam que muita criatividade humana é necessária para construir essas representações; a inteligência vem do design da entrada, não do SME. Forbus et al. [1998] tentou refutar essa crítica. Morrison e Dietrich [1995] tentaram conciliar os dois pontos de vista. Turney [2008] apresenta um algoritmo que não requer entrada LISP, mas segue os princípios da Teoria de Mapeamento de Estrutura. Turney [2008] afirma que seu trabalho também não está imune às críticas de Chalmers, French e Hofstadter [1992].

Em seu artigo Como as ideias criativas tomam forma, Liane Gabora escreve "De acordo com a teoria de aprimoramento da criatividade, o pensamento criativo não funciona em representações individualmente consideradas, discretas e predefinidas, mas em um amálgama contextualmente eliciado de itens que existem em um estado de potencialidade e pode não ser facilmente separável. Isso leva à previsão de que fazer analogias prossegue não mapeando correspondências de fontes candidatas para o alvo, como previsto pela teoria de analogia de mapeamento de estrutura, mas eliminando não correspondências, reduzindo assim a potencialidade. "

Referências

Leitura adicional