En inteligencia artificial y ciencia cognitiva , el motor de mapeo de estructuras ( SME ) es una implementación en software de un algoritmo de emparejamiento analógico basado en la teoría psicológica de Dedre Gentner . La base de la idea del mapeo de estructuras de Gentner es que una analogía es un mapeo del conocimiento de un dominio (la base) a otro (el objetivo). El motor de mapeo de estructuras es una simulación por computadora de las comparaciones de analogías y similitudes. [1]
En 1990, más de 40 proyectos lo habían utilizado [Falkenhainer, 2005]. RM French dijo que la teoría del mapeo de estructuras es "sin duda el trabajo más influyente hasta la fecha en el modelado de la creación de analogías" [2002]. [ cita requerida ]
La teoría es útil porque ignora las características de la superficie y encuentra coincidencias entre cosas potencialmente muy diferentes si tienen la misma estructura de representación. Por ejemplo, SME podría determinar que un bolígrafo es como una esponja porque ambos están involucrados en la dispensación del líquido, aunque lo hacen de manera muy diferente.
Teoría del mapeo de estructuras
La teoría del mapeo de estructuras se basa en el principio de sistematicidad, que establece que se prefiere el conocimiento conectado sobre los hechos independientes. Por lo tanto, el motor de mapeo de estructuras debe ignorar los mapeos de origen-destino aislados a menos que sean parte de una estructura más grande. La PYME, según la teoría, debería mapear objetos que estén relacionados con el conocimiento que ya ha sido mapeado.
La teoría también requiere que las asignaciones se realicen uno a uno , lo que significa que ninguna parte de la descripción de la fuente se puede asignar a más de un elemento en el destino y ninguna parte de la descripción del destino se puede asignar a más de una parte del fuente. La teoría también requiere que si una coincidencia mapea sujeto a objetivo, los argumentos de sujeto y objetivo también deben mapearse. Si se cumplen ambas condiciones, se dice que el mapeo es "estructuralmente consistente".
Conceptos en PYME
Las PYME mapean el conocimiento de una fuente a un destino. SME llama a cada descripción un dgroup . Dgroups contiene una lista de entidades y predicados . Las entidades representan los objetos o conceptos en una descripción, como un engranaje de entrada o un interruptor. Los predicados son uno de los tres tipos y son una forma general de expresar conocimientos para las PYME.
- Los predicados de relación contienen varios argumentos, que pueden ser otros predicados o entidades. Un ejemplo de relación es: (transmitir (qué desde hasta)). Esta relación tiene un funtor de transmisión y toma tres argumentos: qué, desde y hacia.
- Los predicados de atributo son las propiedades de una entidad. Un ejemplo de atributo es (engranaje rojo), que significa que el engranaje tiene el atributo rojo.
- Los predicados de función asignan una entidad a otra entidad o constante. Un ejemplo de una función es ( fuente de energía en julios ) que asigna la fuente de energía de la entidad a la cantidad numérica en julios.
Las funciones y atributos tienen significados diferentes y, en consecuencia, las PYME los procesan de manera diferente. Por ejemplo, en el conjunto de reglas de analogía real de las PYME, los atributos difieren de las funciones porque no pueden coincidir a menos que exista una coincidencia de orden superior entre ellos. La diferencia entre atributos y funciones se explicará con más detalle en los ejemplos de esta sección.
Todos los predicados tienen cuatro parámetros. Tienen (1) un funtor, que lo identifica, y (2) un tipo, que es relación, atributo o función. Los otros dos parámetros (3 y 4) sirven para determinar cómo procesar los argumentos en el algoritmo SME . Si los argumentos deben coincidir en orden, conmutativo es falso. Si el predicado puede tomar cualquier número de argumentos, N-ary es falso. Un ejemplo de una definición de predicado es: (sme: defPredicate comportamiento-conjunto (predicado) relación: n-ary? T: conmutativo? T) El functor del predicado es "comportamiento-conjunto", su tipo es "relación" y su n -ary y los parámetros conmutativos se establecen en verdadero. La parte “(predicado)” de la definición especifica que habrá uno o más predicados dentro de una instanciación de conduct-set.
Detalles del algoritmo
El algoritmo tiene varios pasos. [2] El primer paso del algoritmo es crear un conjunto de hipótesis de coincidencia entre los grupos d de origen y destino. Una hipótesis de coincidencia representa un posible mapeo entre cualquier parte del origen y el destino. Este mapeo está controlado por un conjunto de reglas de coincidencia. Al cambiar las reglas de coincidencia, se puede cambiar el tipo de razonamiento que hace la PYME. Por ejemplo, un conjunto de reglas de coincidencia puede realizar una especie de analogía llamada similitud literal. y otro realiza una especie de analogía llamada analogía verdadera. Estas reglas no son el lugar donde se agrega información dependiente del dominio, sino más bien donde se ajusta el proceso de analogía , dependiendo del tipo de función cognitiva que el usuario está tratando de emular.
Para una regla de coincidencia determinada, hay dos tipos de reglas que definen con más detalle cómo se aplicará: reglas de filtrado y reglas internas. Las reglas internas usan solo los argumentos de las expresiones en las hipótesis de coincidencia que identifican las reglas de filtro. Esta limitación hace que el procesamiento sea más eficiente al restringir el número de hipótesis de coincidencia que se generan. Al mismo tiempo, también ayuda a construir las consistencias estructurales que se necesitan más adelante en el algoritmo. Un ejemplo de una regla de filtro del conjunto de reglas de analogía verdadera crea hipótesis de coincidencia entre predicados que tienen el mismo functor. El conjunto de reglas de analogía verdadera tiene una regla interna que itera sobre los argumentos de cualquier hipótesis de coincidencia, creando más hipótesis de coincidencia si los argumentos son entidades o funciones, o si los argumentos son atributos y tienen el mismo functor.
Para ilustrar cómo las reglas de coincidencia producen hipótesis de coincidencia, considere estos dos predicados:
transmit torque inputgear secondgear (p1)
transmit signal switch div10 (p2)
Aquí usamos una verdadera analogía para el tipo de razonamiento. La regla de coincidencia de filtro genera una coincidencia entre p1 y p2 porque comparten el mismo functor, transmitir. Las reglas internas luego producen tres hipótesis de coincidencia más: par a la señal, engranaje de entrada al interruptor y segundo engranaje a div10. Las reglas internas crearon estas hipótesis de coincidencia porque todos los argumentos eran entidades.
Si los argumentos fueran funciones o atributos en lugar de entidades, los predicados se expresarían como:
transmit torque (inputgear gear) (secondgear gear) (p3)
transmit signal (switch circuit) (div10 circuit) (p4)
Estos predicados adicionales hacen funciones o atributos inputgear, secondgear, switch y div10 según el valor definido en el archivo de entrada de idioma. La representación también contiene entidades adicionales para engranajes y circuitos.
Dependiendo del tipo de inputgear, secondgear, switch y div10 , sus significados cambian. Como atributos, cada uno es propiedad del engranaje o circuito. Por ejemplo, el engranaje tiene dos atributos, inputgear y secondgear. El circuito tiene dos atributos, interruptor y circuito. Como funciones inputgear, secondgear, switch y div10 se convierten en cantidades del engranaje y del circuito. En este ejemplo, las funciones inputgear y secondgear ahora se asignan a las cantidades numéricas "torque from inputgear" y "torque from secondgear". Para el circuito, las cantidades se asignan a la cantidad lógica "interruptor activado" y la cantidad numérica "cuenta actual en la división". por el contador de 10 ".
SME los procesa de manera diferente. No permite que los atributos coincidan a menos que sean parte de una relación de orden superior, pero permite que las funciones coincidan, incluso si no forman parte de dicha relación. Permite que las funciones coincidan porque se refieren indirectamente a entidades y, por lo tanto, deben tratarse como relaciones que no involucran entidades. Sin embargo, como muestra la siguiente sección, las reglas internas asignan pesos más bajos a las coincidencias entre funciones que a las coincidencias entre relaciones.
La razón por la que SME no coincide con los atributos es porque está tratando de crear conocimiento conectado basado en relaciones y así satisfacer el principio de sistematicidad. Por ejemplo, si tanto un reloj como un automóvil tienen atributos de entrada, SME no los marcará como similares. Si lo hiciera, sería una coincidencia entre el reloj y el automóvil en función de su apariencia, no en las relaciones entre ellos.
Cuando los predicados adicionales en p3 y p4 son funciones, los resultados de la coincidencia de p3 y p4 son similares a los resultados de p1 y p2 excepto que hay una coincidencia adicional entre el engranaje y el circuito y los valores para las hipótesis de coincidencia entre (engranaje de entrada) y (circuito de conmutación), y (engranaje de segunda marcha) y (circuito div10), son más bajos. La siguiente sección describe la razón de esto con más detalle.
Si inputgear, secondgear, switch y div10 son atributos en lugar de entidades, SME no encuentra coincidencias entre ninguno de los atributos. Encuentra coincidencias solo entre los predicados de transmisión y entre el par y la señal. Además, los puntajes de evaluación estructural para los dos partidos restantes disminuyen. Para que los dos predicados coincidan, p3 debería ser reemplazado por p5, que se demuestra a continuación.
transmit torque (inputgear gear) (div10 gear) (p5)
Dado que el conjunto de reglas de analogía verdadera identifica que los atributos div10 son los mismos entre p5 y p4 y debido a que los atributos div10 son parte de la relación de relación superior entre el par y la señal, SME hace una coincidencia entre (div10 engranaje) y (div10 circuito), lo que conduce a una coincidencia entre el engranaje y el circuito.
Ser parte de una coincidencia de orden superior es un requisito solo para los atributos. Por ejemplo, si (div10 engranaje) y (div10 circuito) no forman parte de una coincidencia de orden superior, SME no crea una hipótesis de coincidencia entre ellos. Sin embargo, si div10 es una función o relación, SME crea una coincidencia.
Puntaje de evaluación estructural
Una vez que se generan las hipótesis de coincidencia, la PYME debe calcular una puntuación de evaluación para cada hipótesis. SME lo hace mediante el uso de un conjunto de reglas de coincidencia interna para calcular la evidencia positiva y negativa para cada coincidencia. Múltiples cantidades de evidencia se correlacionan usando la regla de Dempster [Shafer, 1978] dando como resultado valores de creencias positivos y negativos entre 0 y 1. Las reglas de coincidencia asignan valores diferentes para coincidencias que involucran funciones y relaciones. Sin embargo, estos valores son programables y en [Falkenhainer et al., 1989] se describen algunos valores predeterminados que pueden usarse para hacer cumplir el principio de sistematicidad.
Estas reglas son:
- Si la fuente y el destino no son funciones y tienen el mismo orden, la coincidencia obtiene +0,3 pruebas. Si las órdenes están dentro de 1 entre sí, la coincidencia obtiene +0,2 evidencia y -0,05 evidencia.
- Si la fuente y el destino tienen el mismo functor, la coincidencia obtiene 0.2 evidencia si la fuente es una función y 0.5 si la fuente es una relación.
- Si los argumentos coinciden, la coincidencia obtiene +0,4 pruebas. Los argumentos pueden coincidir si todos los pares de argumentos entre la fuente y el destino son entidades, si los argumentos tienen los mismos functores, o nunca se da el caso de que el destino sea una entidad pero la fuente no.
- Si el tipo de predicado coincide, pero los elementos del predicado no coinciden, la coincidencia obtiene una evidencia de -0,8.
- Si las expresiones de origen y destino son parte de una coincidencia de orden superior coincidente, agregue 0,8 de la evidencia para la coincidencia de orden superior.
En el ejemplo de coincidencia entre p1 y p2, SME da a la coincidencia entre las relaciones de transmisión un valor de evidencia positiva de 0,7900 y los demás obtienen valores de 0,6320. La relación de transmisión recibe el valor de evidencia de 0.7900 porque obtiene evidencia de las reglas 1, 3 y 2. Las otras coincidencias obtienen un valor de 0.6320 porque 0.8 de la evidencia de la transmisión se propaga a estas coincidencias debido a la regla 5.
Para los predicados p3 y p4, SME asigna menos evidencia porque los argumentos de las relaciones de transmisión son funciones. La relación de transmisión obtiene evidencia positiva de 0.65 porque la regla 3 ya no agrega evidencia. La coincidencia entre (engranaje de entrada) y (circuito de conmutación) se convierte en 0,7120. Esta coincidencia obtiene 0.4 evidencia debido a la regla 3 y 0.52 evidencia propagada desde la relación de transmisión debido a la regla 5.
Cuando los predicados en p3 y p4 son atributos, la regla 4 agrega -0,8 evidencia a la coincidencia de transmisión porque, aunque los functores de la relación de transmisión coinciden, los argumentos no tienen el potencial de coincidir y los argumentos no son funciones.
En resumen, las reglas de coincidencia de los internos calculan una puntuación de evaluación estructural para cada hipótesis de coincidencia. Estas reglas refuerzan el principio de sistematicidad. La regla 5 proporciona evidencia de filtración para fortalecer las coincidencias que están involucradas en relaciones de orden superior. Las reglas 1, 3. y 4 suman o restan soporte para relaciones que podrían tener argumentos coincidentes. La regla 2 agrega soporte para los casos en que los functores coinciden. agregando así soporte para partidos que enfatizan las relaciones.
Las reglas también refuerzan la diferencia entre atributos, funciones y relaciones. Por ejemplo, tienen verificaciones que dan menos evidencia de funciones que de relaciones. Los atributos no se tratan específicamente en las reglas de coincidencia de pasantes, pero las reglas de filtro de SME aseguran que solo se considerarán para estas reglas si son parte de una relación de orden superior, y la regla 2 asegura que los atributos solo coincidirán si tienen idénticos functors.
Creación de Gmap
El resto del algoritmo SME está involucrado en la creación de conjuntos de hipótesis de coincidencia con la máxima coherencia. Estos conjuntos se denominan gmaps. La PYME debe asegurarse de que los gmaps que cree sean estructuralmente coherentes; en otras palabras, que son uno a uno, de modo que ninguna fuente se asigna a varios objetivos y ningún objetivo se asigna a varias fuentes. Los gmaps también deben tener soporte, lo que significa que si hay una hipótesis de coincidencia en el gmap, también lo son las hipótesis de coincidencia que involucran los elementos de origen y destino.
El proceso de creación de gmap sigue dos pasos. Primero, SME calcula información sobre cada hipótesis de coincidencia, incluidas las asignaciones de entidades, cualquier conflicto con otras hipótesis y qué otras hipótesis de coincidencia con las que podría ser estructuralmente inconsistente.
Luego, SME usa esta información para fusionar hipótesis coincidentes, usando un algoritmo codicioso y la puntuación de evaluación estructural. Fusiona las hipótesis de coincidencia en gráficos conectados de máxima coherencia estructural de hipótesis de coincidencia. Luego combina gmaps que tienen una estructura superpuesta si son estructuralmente consistentes. Finalmente, combina gmaps independientes juntos mientras mantiene la consistencia estructural.
La comparación de una fuente con un dgroup de destino puede producir uno o más gmaps. El peso de cada gmap es la suma de todos los valores de evidencia positiva para todas las hipótesis de coincidencia involucradas en el gmap. Por ejemplo, si una fuente que contiene p1 y p6 a continuación se compara con un objetivo que contiene p2, SME generará dos gmaps. Ambos gmaps tienen un peso de 2.9186.
Fuente:
transmit torque inputgear secondgear (p1)
transmit torque secondgear thirdgear (p6)
Objetivo: transmit signal switch div10 (p2)
Estos son los gmaps que resultan de comparar una fuente que contiene p1 y p6 y una diana que contiene p2.
Gmap No. 1:
(SEÑAL DE PAR)(INTERRUPTOR DE ENGRANAJES)(SECONDGEAR DIV10)(* TRANSMISIÓN-PAR-ENTRADA-ENGRANAJE-SECUNDARIO * TRANSMISIÓN-INTERRUPTOR-SEÑAL-DIV10)
Gmap No. 2 :
(SEÑAL DE PAR)(INTERRUPTOR SECUNDARIO)(THIRDGEAR DIV10)(* TRANSMISIÓN-PAR-SECONDGEAR-THIRDGEAR * TRANSMISIÓN-INTERRUPTOR-SEÑAL-DIV10)
Los gmaps muestran pares de predicados o entidades que coinciden. Por ejemplo, en el gmap No. 1, el par de entidades y la señal coinciden y los comportamientos transmiten el par de entrada del engranaje segundo engranaje y el interruptor de la señal de transmisión div10 coinciden. Gmap No. 1 representa la combinación de p1 y p2. Gmap No. 2 representa la combinación de p1 y p6. Aunque p2 es compatible con p1 y p6, la restricción de mapeo uno a uno obliga a que ambos mapeos no puedan estar en el mismo gmap. Por lo tanto, SME produce dos gmaps independientes. Además, la combinación de los dos gmaps juntos haría que las asignaciones de entidades entre thirdgear y div10 entren en conflicto con la asignación de entidades entre secondgear y div10.
Criticas
Chalmers, French y Hofstadter [1992] critican a las PYME por su dependencia de representaciones LISP construidas manualmente como entrada. Argumentan que se requiere demasiada creatividad humana para construir estas representaciones; la inteligencia proviene del diseño del insumo, no de la PYME. Forbus y col. [1998] intentó refutar esta crítica. Morrison y Dietrich [1995] intentaron conciliar los dos puntos de vista. Turney [2008] presenta un algoritmo que no requiere entrada LISP, pero sigue los principios de la teoría de mapeo de estructuras. Turney [2008] afirma que su trabajo tampoco es inmune a las críticas de Chalmers, French y Hofstadter [1992].
En su artículo Cómo toman forma las ideas creativas, [3] Liane Gabora escribe: "Según la teoría del perfeccionamiento de la creatividad, el pensamiento creativo no funciona en representaciones predefinidas, discretas y consideradas individualmente, sino en una amalgama de elementos provocados por el contexto que existen en un estado de potencialidad y pueden no ser fácilmente separables. Esto lleva a la predicción de que la creación de analogías procede no mapeando correspondencias de las fuentes candidatas al objetivo, como predice la teoría de la analogía del mapeo de estructuras, sino eliminando las no correspondencias, eliminando así potencialidad."
Referencias
- ^ "Mapeo de estructuras: un modelo computacional de analogía y similitud" . Universidad de Northwestern . Consultado el 16 de enero de 2012 .
- ^ Brian Falkenhainer; Kenneth D. Forbus; Dedre Gentner (1989). "El motor de mapeo de estructuras: algoritmo y ejemplos" (PDF) . Inteligencia artificial . 41 : 1–63. CiteSeerX 10.1.1.26.6432 . doi : 10.1016 / 0004-3702 (89) 90077-5 . Consultado el 16 de enero de 2012 .
- ^ Gabora, Liane (2015). "Cómo toman forma las ideas creativas". arXiv : 1501.04406 [ q-bio.NC ].
Otras lecturas
- Artículos del Qualitative Reasoning Group de la Northwestern University
- Chalmers, DJ, French, RM y Hofstadter, DR: 1992, Percepción, representación y analogía de alto nivel: una crítica de la metodología de la inteligencia artificial . Revista de inteligencia artificial experimental y teórica , 4 (3), 185-211.
- Falkenhainer, B: 2005, Implementación del motor de mapeo de estructuras. implementación de pyme
- Falkenhainer, B, Forbus, K y Gentner, D: 1989, "El motor de mapeo de estructuras: algoritmo y ejemplos" . Inteligencia artificial, 20 (41): 1–63.
- Forbus, KD, Gentner, D., Markman, AB y Ferguson, RW: 1998, Analogy Just Looks Like High Level Perception: Why a Domain-General Approach to Analogical Mapping is Right . Revista de Inteligencia Artificial Experimental y Teórica , 10 (2), 231-257.
- Francés, RM: 2002. "El modelado computacional de la creación de analogías" . Tendencias en ciencias cognitivas, 6 (5), 200-205.
- Gentner, D: 1983, "Mapeo de estructuras: un marco teórico para la analogía" , Ciencia cognitiva 7 (2)
- Shafer, G : 1978, Una teoría matemática de la evidencia , Princeton University Press, Princeton, Nueva Jersey. ISBN 0-691-08175-1 .
- Morrison, CT y Dietrich, E .: 1995, Mapeo de estructuras versus percepción de alto nivel: la lucha equivocada sobre la explicación de la analogía . Actas de la Decimoséptima Conferencia Anual de la Sociedad de Ciencias Cognitivas, 678-682.
- Turney, PD: 2008, El motor de mapeo de relaciones latentes: algoritmos y experimentos , Journal of Artificial Intelligence Research (JAIR), 33, 615-655.