Algoritmo Rete

El lado izquierdo ( alfa ) del grafo de nodos forma una red de discriminación responsable de seleccionar WME individuales basándose en pruebas condicionales simples que comparan los atributos de WME con valores constantes. Los nodos de la red de discriminación también pueden realizar pruebas que comparan dos o más atributos del mismo WME. Si un WME coincide con las condiciones representadas por un nodo, se pasa al siguiente. En la mayoría de los motores, los nodos hijos inmediatos del nodo raíz se utilizan para probar el identificador de entidad o el tipo de hecho de cada WME. Por lo tanto, todos los WME que representan el mismo tipo de entidad suelen recorrer una rama determinada de nodos en la red de discriminación.

Dentro de la red de discriminación, cada rama de nodos alfa (también llamados nodos de una entrada) termina en una memoria denominada memoria alfa . Estas memorias almacenan conjuntos de WME que coinciden con cada condición en cada nodo de una rama determinada. Los WME que no coinciden con al menos una condición en una rama no se materializan en la memoria alfa correspondiente. Las ramas de los nodos alfa pueden bifurcarse para minimizar la redundancia de condiciones.

El lado "derecho" ( beta ) del gráfico realiza principalmente uniones entre diferentes WME. Es opcional y solo se incluye si es necesario. Consta de nodos de 2 entradas, donde cada nodo tiene una entrada "izquierda" y una "derecha". Cada nodo beta envía su salida a una memoria beta .

En las descripciones de Rete, es común referirse al paso de tokens dentro de la red beta. Sin embargo, en este artículo describiremos la propagación de datos en términos de listas WME, en lugar de tokens, teniendo en cuenta las diferentes opciones de implementación y el propósito y uso subyacentes de los tokens. A medida que una lista WME pasa por la red beta, se pueden agregar nuevos WME a ella, y la lista puede almacenarse en memorias beta. Una lista WME en una memoria beta representa una coincidencia parcial con las condiciones de una producción dada.

Las listas WME que llegan al final de una rama de nodos beta representan una coincidencia completa para una sola producción y se pasan a los nodos terminales. Estos nodos a veces se denominan nodos p , donde "p" significa producción . Cada nodo terminal representa una sola producción, y cada lista WME que llega a un nodo terminal representa un conjunto completo de WME coincidentes para las condiciones de esa producción. Por cada lista WME que recibe, un nodo de producción "activará" una nueva instancia de producción en la "agenda". Las agendas se implementan normalmente como colas priorizadas .

Los nodos beta suelen realizar uniones entre listas WME almacenadas en memorias beta y WME individuales almacenadas en memorias alfa. Cada nodo beta está asociado a dos memorias de entrada. Una memoria alfa almacena WM y realiza activaciones "derecha" en el nodo beta cada vez que almacena un nuevo WME. Una memoria beta almacena listas WME y realiza activaciones "izquierda" en el nodo beta cada vez que almacena una nueva lista WME. Cuando un nodo de unión se activa a la derecha, compara uno o más atributos del WME recién almacenado de su memoria alfa de entrada con atributos dados de WME específicos en cada lista WME contenida en la memoria beta de entrada. Cuando un nodo de unión se activa a la izquierda, recorre una única lista WME recién almacenada en la memoria beta, recuperando valores de atributos específicos de WME dados. Compara estos valores con los valores de atributos de cada WME en la memoria alfa.

Cada nodo beta genera listas WME que se almacenan en una memoria beta o se envían directamente a un nodo terminal. Las listas WME se almacenan en las memorias beta siempre que el motor realice activaciones adicionales a la izquierda en nodos beta subsiguientes.

Lógicamente, un nodo beta al inicio de una rama de nodos beta constituye un caso especial, ya que no recibe información de ninguna memoria beta superior en la red. Los distintos motores abordan este problema de diferentes maneras. Algunos utilizan nodos adaptadores especializados para conectar las memorias alfa a la entrada izquierda de los nodos beta. Otros permiten que los nodos beta reciban información directamente de dos memorias alfa, tratando una como entrada "izquierda" y la otra como entrada "derecha". En ambos casos, los nodos beta "al inicio" reciben su información de dos memorias alfa.

Para eliminar la redundancia de nodos, cualquier memoria alfa o beta puede utilizarse para activar múltiples nodos beta. Además de los nodos de unión, la red beta puede contener otros tipos de nodos, algunos de los cuales se describen a continuación. Si una red no contiene ninguna red beta, los nodos alfa envían tokens, cada uno con un único WME, directamente a los nodos p. En este caso, puede que no sea necesario almacenar los WME en las memorias alfa.

Durante cualquier ciclo de coincidencia-resolución-acción, el motor encontrará todas las coincidencias posibles para los hechos actualmente registrados en la memoria de trabajo. Una vez encontradas todas las coincidencias y activadas las instancias de producción correspondientes en la agenda, el motor determina el orden en que se pueden ejecutar dichas instancias. Esto se denomina resolución de conflictos , y la lista de instancias de producción activadas se denomina conjunto de conflictos . El orden puede basarse en la prioridad de la regla ( relevancia ), el orden de la regla, el momento en que los hechos contenidos en cada instancia se registraron en la memoria de trabajo, la complejidad de cada producción u otros criterios. Muchos motores permiten a los desarrolladores de reglas seleccionar entre diferentes estrategias de resolución de conflictos o encadenar varias estrategias.

La resolución de conflictos no está definida como parte del algoritmo Rete, pero se utiliza junto con él. Algunos sistemas de producción especializados no realizan la resolución de conflictos.

Tras resolver el conflicto, el motor inicia la primera instancia de producción, ejecutando una lista de acciones asociadas a ella. Estas acciones actúan sobre los datos representados por la lista WME de la instancia de producción.

Por defecto, el motor continuará ejecutando cada instancia de producción en orden hasta que todas se hayan ejecutado. Cada instancia de producción se ejecutará solo una vez, como máximo, durante cualquier ciclo de coincidencia-resolución-acción. Esta característica se denomina refracción . Sin embargo, la secuencia de ejecuciones de instancias de producción puede interrumpirse en cualquier etapa mediante cambios en la memoria de trabajo. Las acciones de las reglas pueden contener instrucciones para afirmar o retirar WME de la memoria de trabajo del motor. Cada vez que una instancia de producción realiza uno o más de estos cambios, el motor entra inmediatamente en un nuevo ciclo de coincidencia-resolución-acción. Esto incluye las "actualizaciones" de los WME que se encuentran actualmente en la memoria de trabajo. Las actualizaciones se representan retirando y volviendo a afirmar el WME. El motor realiza la coincidencia de los datos modificados, lo que, a su vez, puede resultar en cambios en la lista de instancias de producción en la agenda. Por lo tanto, después de que se hayan ejecutado las acciones para una instancia de producción específica, las instancias previamente activadas pueden haberse desactivado y eliminado de la agenda, y pueden haberse activado nuevas instancias.

Como parte del nuevo ciclo de coincidencia-resolución-acción, el motor resuelve los conflictos en la agenda y luego ejecuta la primera instancia actual. El motor continúa generando instancias de producción e iniciando nuevos ciclos de coincidencia-resolución-acción hasta que no queden más instancias de producción en la agenda. En ese momento, se considera que el motor de reglas ha finalizado su trabajo y se detiene.

Algunos motores admiten estrategias de refracción avanzadas en las que ciertas instancias de producción ejecutadas en un ciclo anterior no se vuelven a ejecutar en el nuevo ciclo, aunque todavía figuren en la agenda.

Es posible que el motor entre en bucles infinitos en los que la agenda nunca llega al estado vacío. Por este motivo, la mayoría de los motores admiten verbos de "detención" explícitos que se pueden invocar desde las listas de acciones de producción. También pueden ofrecer detección automática de bucles, en la que los bucles infinitos se detienen automáticamente después de un número determinado de iteraciones. Algunos motores admiten un modelo en el que, en lugar de detenerse cuando la agenda está vacía, el motor entra en un estado de espera hasta que se afirman nuevos hechos externamente.

En cuanto a la resolución de conflictos, la activación de instancias de producción no es una característica del algoritmo Rete. Sin embargo, sí es una característica fundamental de los motores que utilizan redes Rete. Algunas de las optimizaciones que ofrecen las redes Rete solo son útiles en escenarios donde el motor realiza múltiples ciclos de coincidencia, resolución y ejecución.

Las pruebas condicionales se utilizan con mayor frecuencia para realizar selecciones y uniones en tuplas individuales. Sin embargo, al implementar tipos de nodos beta adicionales, las redes Rete pueden realizar cuantificaciones . La cuantificación existencial implica comprobar la existencia de al menos un conjunto de WME coincidentes en la memoria de trabajo. La cuantificación universal implica comprobar que un conjunto completo de WME en la memoria de trabajo cumple una condición dada. Una variante de la cuantificación universal podría comprobar que un número determinado de WME, extraído de un conjunto de WME, cumple con ciertos criterios. Esto podría consistir en comprobar un número exacto o un número mínimo de coincidencias.

La cuantificación no está implementada universalmente en los motores Rete y, donde sí lo está, existen varias variantes. Una variante de cuantificación existencial, denominada negación , cuenta con amplio soporte, aunque no universal, y se describe en documentos fundamentales. Las condiciones y conjunciones negadas existencialmente implican el uso de nodos beta especializados que comprueban la inexistencia de WME coincidentes o conjuntos de WME. Estos nodos propagan listas de WME solo cuando no se encuentra ninguna coincidencia. La implementación exacta de la negación varía. En un enfoque, el nodo mantiene un contador simple en cada lista de WME que recibe de su entrada izquierda. El contador especifica el número de coincidencias encontradas con los WME recibidos de la entrada derecha. El nodo solo propaga listas de WME cuyo contador es cero. En otro enfoque, el nodo mantiene una memoria adicional en cada lista de WME recibida de la entrada izquierda. Estas memorias son una forma de memoria beta y almacenan listas de WME para cada coincidencia con los WME recibidos en la entrada derecha. Si una lista WME no tiene ninguna lista WME en su memoria, se propaga por la red. En este enfoque, los nodos de negación generalmente activan directamente otros nodos beta, en lugar de almacenar su salida en una memoria beta adicional. Los nodos de negación proporcionan una forma de « negación como fallo ».

Cuando se modifica la memoria de trabajo, una lista WME que antes no coincidía con ninguna WME ahora puede coincidir con WME recién identificadas. En este caso, la lista WME propagada y todas sus copias extendidas deben eliminarse de las memorias beta en la red. El segundo método descrito anteriormente se utiliza a menudo para implementar mecanismos eficientes de eliminación de listas WME. Al eliminar las listas WME, las instancias de producción correspondientes se desactivan y se eliminan de la agenda.

La cuantificación existencial se puede realizar combinando dos nodos beta de negación. Esto representa la semántica de la doble negación (por ejemplo, "Si NO NO hay ningún WME coincidente, entonces..."). Este es un enfoque común en varios sistemas de producción.

El algoritmo Rete no exige ningún enfoque específico para la indexación de la memoria de trabajo. Sin embargo, la mayoría de los sistemas de producción modernos proporcionan mecanismos de indexación. En algunos casos, solo se indexan las memorias beta, mientras que en otros, la indexación se utiliza tanto para las memorias alfa como para las beta. Una buena estrategia de indexación es un factor clave para determinar el rendimiento general de un sistema de producción, especialmente al ejecutar conjuntos de reglas que dan como resultado una coincidencia de patrones altamente combinatoria (es decir, un uso intensivo de nodos de unión beta) o, para algunos motores, al ejecutar conjuntos de reglas que realizan un número significativo de retracciones de WME durante múltiples ciclos de coincidencia-resolución-acción. Las memorias a menudo se implementan utilizando combinaciones de tablas hash, y los valores hash se utilizan para realizar uniones condicionales en subconjuntos de listas de WME y WME, en lugar de en todo el contenido de las memorias. Esto, a su vez, suele reducir significativamente el número de evaluaciones realizadas por la red Rete.

Cuando un WME se retira de la memoria de trabajo, debe eliminarse de todas las memorias alfa en las que esté almacenado. Además, las listas de WME que contienen el WME deben eliminarse de las memorias beta, y las instancias de producción activadas para estas listas de WME deben desactivarse y eliminarse de la agenda. Existen varias variantes de implementación, incluyendo la eliminación basada en árboles y la eliminación basada en coincidencias. En algunos casos, se puede utilizar la indexación de memoria para optimizar la eliminación.

Al definir producciones en un conjunto de reglas, es común permitir que las condiciones se agrupen mediante un conector OR . En muchos sistemas de producción, esto se gestiona interpretando una única producción que contiene múltiples patrones con OR como el equivalente a múltiples producciones. La red Rete resultante contiene conjuntos de nodos terminales que, en conjunto, representan producciones individuales. Este enfoque impide cualquier forma de cortocircuito de las condiciones con OR. También puede, en algunos casos, provocar la activación de instancias de producción duplicadas en la agenda cuando el mismo conjunto de WME coincide con múltiples producciones internas. Algunos motores proporcionan deduplicación de agenda para solucionar este problema.

El siguiente diagrama ilustra la topología básica de Rete y muestra las asociaciones entre los diferentes tipos de nodos y las memorias.

• La mayoría de las implementaciones utilizan nodos de tipo para realizar la primera fase de selección en los elementos de la memoria de trabajo de tuplas. Los nodos de tipo pueden considerarse nodos de selección especializados, ya que permiten diferenciar entre los distintos tipos de relaciones de tuplas.
• El diagrama no ilustra el uso de tipos de nodos especializados, como los nodos de conjunción negada. Algunos motores implementan varias especializaciones de nodos diferentes para ampliar la funcionalidad y maximizar la optimización.
• El diagrama ofrece una representación lógica de la red neuronal. Las implementaciones pueden diferir en detalles físicos. En particular, el diagrama muestra entradas ficticias que proporcionan activaciones correctas al inicio de las ramas del nodo beta. Los motores pueden implementar otros enfoques, como adaptadores que permiten que las memorias alfa realicen activaciones correctas directamente.
• El diagrama no ilustra todas las posibilidades de compartición de nodos.

Para obtener una descripción más detallada y completa del algoritmo Rete, consulte el capítulo 2 de Production Matching for Large Learning Systems de Robert Doorenbos (véase el enlace a continuación).

Una posible variante consiste en introducir memorias adicionales para cada nodo intermedio en la red de discriminación. Esto aumenta la sobrecarga de la red, pero puede tener ventajas en situaciones donde se añaden o eliminan reglas dinámicamente, facilitando así la modificación dinámica de la topología de la red de discriminación.

Doorenbos describe una implementación alternativa. ^{[ 5 ]} En este caso, la red de discriminación se reemplaza por un conjunto de memorias y un índice. El índice puede implementarse mediante una tabla hash . Cada memoria almacena WME que coinciden con un único patrón condicional, y el índice se utiliza para referenciar las memorias según su patrón. Este enfoque solo es práctico cuando los WME representan tuplas de longitud fija y la longitud de cada tupla es corta (por ejemplo, 3-tuplas). Además, el enfoque solo se aplica a patrones condicionales que realizan pruebas de igualdad con respecto a valores constantes . Cuando un WME ingresa a la red, el índice se utiliza para localizar un conjunto de memorias cuyo patrón condicional coincide con los atributos del WME, y este se agrega directamente a cada una de estas memorias. En sí misma, esta implementación no contiene nodos de una entrada. Sin embargo, para implementar pruebas de desigualdad, la red puede contener redes adicionales de nodos de una entrada por las que se pasan los WME antes de colocarlos en una memoria. Alternativamente, las pruebas de desigualdad pueden realizarse en la red beta descrita a continuación.

Una variante común consiste en crear listas enlazadas de tokens, donde cada token contiene un único WME. En este caso, las listas de WME para una coincidencia parcial se representan mediante la lista enlazada de tokens. Este enfoque puede ser mejor porque elimina la necesidad de copiar listas de WME de un token a otro. En cambio, un nodo beta solo necesita crear un nuevo token para almacenar el WME que desea agregar a la lista de coincidencia parcial y, a continuación, enlazar el nuevo token con un token padre almacenado en la memoria beta de entrada. El nuevo token ahora forma la cabecera de la lista de tokens y se almacena en la memoria beta de salida.

Los nodos beta procesan tokens. Un token es una unidad de almacenamiento dentro de una memoria y también una unidad de intercambio entre memorias y nodos. En muchas implementaciones, los tokens se introducen en las memorias alfa, donde se utilizan para almacenar WME individuales. Estos tokens se transfieren posteriormente a la red beta.

Cada nodo beta realiza su trabajo y, como resultado, puede crear nuevos tokens para almacenar una lista de WME que representan una coincidencia parcial. Estos tokens extendidos se almacenan en las memorias beta y se transmiten a los nodos beta subsiguientes. En este caso, los nodos beta suelen transmitir listas de WME a través de la red beta copiando las listas de WME existentes de cada token recibido en nuevos tokens y, posteriormente, añadiendo más WME a las listas como resultado de una unión u otra acción. Los nuevos tokens se almacenan en la memoria de salida.

En la década de 1980, Charles Forgy desarrolló un sucesor del algoritmo Rete llamado Rete II . ^{[ 7 ]} A diferencia del Rete original (que es de dominio público), este algoritmo no fue divulgado. Rete II afirma tener un mejor rendimiento para problemas más complejos (incluso órdenes de magnitud ^{[ 8 ]} ), y está implementado oficialmente en CLIPS/R2, una implementación en C/++ y en OPSJ, una implementación en Java desde 1998. Rete II proporciona una mejora de rendimiento de aproximadamente 100 a 1 orden de magnitud en problemas más complejos, como lo demuestran las pruebas de rendimiento de KnowledgeBased Systems Corporation ^{[ 9 ]} .

Rete II se caracteriza por dos áreas de mejora: optimizaciones específicas relacionadas con el rendimiento general de la red Rete (incluido el uso de memorias hash para aumentar el rendimiento con conjuntos de datos más grandes) y la inclusión de un algoritmo de encadenamiento hacia atrás diseñado para ejecutarse sobre la red Rete. El encadenamiento hacia atrás por sí solo puede explicar los cambios más drásticos en las pruebas comparativas entre Rete y Rete II. Rete II está implementado en el producto comercial Advisor de FICO, anteriormente llamado Fair Isaac ^{[ 10 ].}

Jess (al menos en las versiones 5.0 y posteriores) también añade un algoritmo comercial de encadenamiento hacia atrás sobre la red Rete, pero no se puede decir que implemente completamente Rete II, en parte debido a que no hay una especificación completa disponible públicamente.

A principios de la década de 2000, Charles Forgy desarrolló el motor Rete III en colaboración con ingenieros de FICO. El algoritmo Rete III, que no es Rete-NT, es la marca registrada de FICO para Rete II y se implementa como parte del motor FICO Advisor. Básicamente, es el motor Rete II con una API que permite el acceso al motor Advisor, ya que este último puede acceder a otros productos de FICO. ^{[ 11 ]}

En 2010, Forgy desarrolló una nueva generación del algoritmo Rete. En una prueba comparativa de InfoWorld , el algoritmo fue considerado 500 veces más rápido que el algoritmo Rete original y 10 veces más rápido que su predecesor, Rete II. ^{[ 12 ]} Este algoritmo ahora está licenciado a Sparkling Logic, la empresa a la que Forgy se unió como inversor y asesor estratégico, ^{[ 13 ] [ 14 ]} como motor de inferencia del producto SMARTS.

Considerando que Rete tiene como objetivo admitir lógica de primer orden (básicamente sentencias if-then-else ), Rete-OO ^{[ 15 ]} tiene como objetivo proporcionar un sistema basado en reglas que admita incertidumbre (donde la información para tomar una decisión es incompleta o inexacta). Según la propuesta del autor, la regla " si Peligro entonces Alarma " se mejoraría a algo como " dada la probabilidad de Peligro, habrá una cierta probabilidad de oír una Alarma " o incluso " cuanto mayor sea el Peligro, más fuerte debería sonar la Alarma ". Para ello, extiende el lenguaje Drools (que ya implementa el algoritmo Rete) para que admita lógica probabilística , como lógica difusa y redes bayesianas .