El algoritmo Rete ( / r i t i / REE -Tee , / r eɪ t i / RAY -Tee , rara vez / r i t / REET , / r ɛ t eɪ / reh- TAY ) es una coincidencia de patrones algoritmo para implementar sistemas basados en reglas . El algoritmo fue desarrollado para aplicar de manera eficiente muchas reglas.o patrones a muchos objetos, o hechos , en una base de conocimiento . Se utiliza para determinar cuál de las reglas del sistema debe activarse en función de su almacén de datos, sus hechos. El algoritmo Rete fue diseñado por Charles L. Forgy de la Universidad Carnegie Mellon , publicado por primera vez en un documento de trabajo en 1974 y elaborado posteriormente en su Ph.D. de 1979. tesis y un artículo de 1982. [1]
Descripción general
Una implementación ingenua de un sistema experto podría comparar cada regla con hechos conocidos en una base de conocimiento , activando esa regla si es necesario, luego pasando a la siguiente regla (y volviendo a la primera regla cuando haya terminado). Incluso para bases de conocimiento de hechos y reglas de tamaño moderado, este enfoque ingenuo funciona con demasiada lentitud. El algoritmo Rete proporciona la base para una implementación más eficiente. Un sistema experto basado en Rete construye una red de nodos , donde cada nodo (excepto la raíz) corresponde a un patrón que ocurre en el lado izquierdo (la parte de condición) de una regla. La ruta desde el nodo raíz hasta un nodo hoja define una regla completa en el lado izquierdo. Cada nodo tiene una memoria de hechos que satisfacen ese patrón. Esta estructura es esencialmente un ensayo generalizado . A medida que se afirman o modifican nuevos hechos, se propagan a lo largo de la red, lo que hace que los nodos se anoten cuando ese hecho coincide con ese patrón. Cuando un hecho o combinación de hechos hace que se cumplan todos los patrones de una regla determinada, se llega a un nodo hoja y se activa la regla correspondiente.
Rete se utilizó por primera vez como el motor central del lenguaje del sistema de producción OPS5 , que se utilizó para construir los primeros sistemas, incluido R1 para Digital Equipment Corporation. Rete se ha convertido en la base de muchos motores de reglas populares y shells de sistemas expertos, incluidos Tibco Business Events, Newgen OmniRules, CLIPS , Jess , Drools , IBM Operational Decision Management , OPSJ, Blaze Advisor, BizTalk Rules Engine , Soar , Clara y Sparkling Logic SMARTS . La palabra 'Rete' en latín significa 'red' o 'peine'. La misma palabra se usa en italiano moderno para significar red . Según los informes, Charles Forgy ha declarado que adoptó el término 'Rete' debido a su uso en anatomía para describir una red de vasos sanguíneos y fibras nerviosas. [2]
El algoritmo Rete está diseñado para sacrificar memoria por una mayor velocidad. En la mayoría de los casos, el aumento de velocidad en implementaciones ingenuas es de varios órdenes de magnitud (porque el desempeño de Rete es teóricamente independiente del número de reglas en el sistema). Sin embargo, en sistemas expertos muy grandes, el algoritmo original de Rete tiende a tener problemas de consumo de memoria y del servidor. Desde entonces se han diseñado otros algoritmos, tanto novedosos como basados en Rete, que requieren menos memoria (por ejemplo, Rete * [3] o Coincidencia orientada a colecciones [4] ).
Descripción
El algoritmo Rete proporciona una descripción lógica generalizada de una implementación de la funcionalidad responsable de hacer coincidir tuplas de datos ("hechos") con producciones (" reglas ") en un sistema de producción de coincidencia de patrones (una categoría de motor de reglas ). Una producción consta de una o más condiciones y un conjunto de acciones que pueden emprenderse para cada conjunto completo de hechos que coincidan con las condiciones. Las condiciones prueban los atributos de hechos , incluidos los especificadores / identificadores de tipos de hechos. El algoritmo de Rete presenta las siguientes características principales:
- Reduce o elimina ciertos tipos de redundancia mediante el uso de nodos compartidos.
- Almacena coincidencias parciales al realizar combinaciones entre diferentes tipos de hechos. Esto, a su vez, permite que los sistemas de producción eviten una reevaluación completa de todos los hechos cada vez que se realizan cambios en la memoria de trabajo del sistema de producción. En cambio, el sistema de producción solo necesita evaluar los cambios (deltas) en la memoria de trabajo.
- Permite la eliminación eficiente de elementos de la memoria cuando los hechos se retiran de la memoria de trabajo.
El algoritmo Rete se usa ampliamente para implementar la funcionalidad de coincidencia dentro de los motores de coincidencia de patrones que explotan un ciclo de coincidencia-resolución-acción para admitir el encadenamiento directo y la inferencia .
- Proporciona un medio para hacer coincidir muchos-muchos, una característica importante cuando se deben encontrar muchas o todas las soluciones posibles en una red de búsqueda.
Las retes son gráficos acíclicos dirigidos que representan conjuntos de reglas de nivel superior. Por lo general, se representan en tiempo de ejecución mediante una red de objetos en memoria. Estas redes hacen coincidir las condiciones de las reglas (patrones) con los hechos (tuplas de datos relacionales). Las redes Rete actúan como un tipo de procesador de consultas relacionales, realizando proyecciones , selecciones y uniones condicionalmente en números arbitrarios de tuplas de datos.
Las producciones (reglas) suelen ser capturadas y definidas por analistas y desarrolladores utilizando un lenguaje de reglas de alto nivel. Se recopilan en conjuntos de reglas que luego se traducen, a menudo en tiempo de ejecución, en un Rete ejecutable.
Cuando los hechos se "afirman" en la memoria de trabajo, el motor crea elementos de la memoria de trabajo (WMEs) para cada hecho. Los hechos son n-tuplas y, por lo tanto, pueden contener un número arbitrario de elementos de datos. Cada WME puede contener una n-tupla completa o, alternativamente, cada hecho puede estar representado por un conjunto de WME donde cada WME contiene una tupla de longitud fija. En este caso, las tuplas suelen ser tripletes (3 tuplas).
Cada WME ingresa a la red Rete en un solo nodo raíz. El nodo raíz pasa cada WME a sus nodos secundarios, y cada WME puede luego propagarse a través de la red, posiblemente almacenándose en memorias intermedias, hasta que llega a un nodo terminal.
Red alfa
El lado "izquierdo" ( alfa ) del gráfico de nodos forma una red de discriminación responsable de seleccionar WMEs individuales basándose en pruebas condicionales simples que comparan atributos 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 se compara con éxito con las condiciones representadas por un nodo, se pasa al siguiente nodo. En la mayoría de los motores, los nodos secundarios inmediatos del nodo raíz se utilizan para probar el identificador de entidad o el tipo de hecho de cada WME. Por tanto, todos los WMEs que representan el mismo tipo de entidad atraviesan típicamente una rama determinada de nodos en la red de discriminación.
Dentro de la red de discriminación, cada rama de los nodos alfa (también denominados nodos de 1 entrada) termina en una memoria, denominada memoria alfa . Estas memorias almacenan colecciones de WMEs que coinciden con cada condición en cada nodo en una rama de nodo determinada. Los WMEs que no cumplen con al menos una condición en una rama no se materializan dentro de la memoria alfa correspondiente. Las ramas del nodo alfa pueden bifurcarse para minimizar la redundancia de condiciones.
Red beta
El lado "derecho" ( beta ) del gráfico realiza principalmente uniones entre diferentes WMEs. Es opcional y solo se incluye si es necesario. Consiste en 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. En este artículo, sin embargo, describiremos la propagación de datos en términos de listas WME, en lugar de tokens, en reconocimiento de las diferentes opciones de implementación y el propósito subyacente y el uso de los tokens. A medida que una lista WME pasa a través de la red beta, se le pueden agregar nuevas WME y la lista puede almacenarse en memorias beta. Una lista de WME en una memoria beta representa una coincidencia parcial de las condiciones en una producción determinada.
Las listas de 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 p-nodos , donde "p" significa producción . Cada nodo terminal representa una producción única, y cada lista WME que llega a un nodo terminal representa un conjunto completo de WMEs coincidentes para las condiciones de esa producción. Por cada lista de WME que reciba, un nodo de producción "activará" una nueva instancia de producción en la "agenda". Las agendas se implementan típicamente como colas priorizadas .
Los nodos beta suelen realizar uniones entre listas WME almacenadas en memorias beta y WMEs individuales almacenadas en memorias alfa. Cada nodo beta está asociado con dos memorias de entrada. Una memoria alfa contiene WM y realiza activaciones "correctas" en el nodo beta cada vez que almacena un nuevo WME. Una memoria beta contiene listas WME y realiza activaciones "izquierdas" 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 WMEs específicos en cada lista de WME contenida en la memoria beta de entrada. Cuando un nodo de unión se activa a la izquierda, atraviesa una única lista WME recién almacenada en la memoria beta, recuperando valores de atributo específicos de WMEs dados. Compara estos valores con los valores de atributo 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 de WME se almacenan en memorias beta siempre que el motor realice activaciones izquierdas adicionales en los nodos beta posteriores.
Lógicamente, un nodo beta a la cabeza de una rama de nodos beta es un caso especial porque no recibe entrada de ninguna memoria beta superior en la red. Los diferentes motores manejan este problema de diferentes maneras. Algunos motores utilizan nodos adaptadores especializados para conectar las memorias alfa a la entrada izquierda de los nodos beta. Otros motores permiten que los nodos beta reciban entradas directamente de dos memorias alfa, tratando una como entrada "izquierda" y la otra como entrada "derecha". En ambos casos, los nodos beta "principales" toman su entrada de dos memorias alfa.
Para eliminar las redundancias de nodos, se puede utilizar cualquier memoria alfa o beta para realizar activaciones en múltiples nodos beta. Además de unirse a los nodos, la red beta puede contener tipos de nodos adicionales, algunos de los cuales se describen a continuación. Si una Rete no contiene una red beta, los nodos alfa alimentan tokens, cada uno con un solo WME, directamente a los p-nodos. En este caso, puede que no sea necesario almacenar WME en memorias alfa.
La resolución de conflictos
Durante cualquier ciclo de coincidencia-resolución-acto, el motor encontrará todas las coincidencias posibles para los hechos actualmente afirmados en la memoria de trabajo. Una vez que se han encontrado todas las coincidencias actuales y se han activado las instancias de producción correspondientes en la agenda, el motor determina un orden en el que se pueden "disparar" las instancias de producción. 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 las reglas ( prominencia ), el orden de las reglas, el momento en que los hechos contenidos en cada instancia se afirmaron en la memoria de trabajo, la complejidad de cada producción o algún otro criterio. Muchos motores permiten a los desarrolladores de reglas seleccionar entre diferentes estrategias de resolución de conflictos o encadenar una selección de múltiples estrategias.
La resolución de conflictos no se define como parte del algoritmo Rete, pero se utiliza junto con el algoritmo. Algunos sistemas de producción especializados no realizan la resolución de conflictos.
Ejecución de producción
Una vez realizada la resolución de conflictos, el motor ahora "dispara" la primera instancia de producción, ejecutando una lista de acciones asociadas con la producción. Las acciones actúan sobre los datos representados por la lista WME de la instancia de producción.
De forma predeterminada, el motor continuará disparando cada instancia de producción en orden hasta que se hayan disparado todas las instancias de producción. Cada instancia de producción se disparará solo una vez, como máximo, durante cualquier ciclo de partido-resolución-acto. Esta característica se denomina refracción . Sin embargo, la secuencia de disparos de la instancia de producción puede interrumpirse en cualquier etapa al realizar cambios en la memoria de trabajo. Las acciones de reglas pueden contener instrucciones para afirmar o retirar WMEs de la memoria de trabajo del motor. Cada vez que una sola instancia de producción realiza uno o más de estos cambios, el motor entra inmediatamente en un nuevo ciclo de emparejar-resolver-actuar. Esto incluye "actualizaciones" a los WMEs actualmente en la memoria de trabajo. Las actualizaciones se representan retractando y luego reafirmando el WME. El motor realiza la comparación de los datos modificados que, a su vez, pueden dar lugar a 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 cualquier instancia de producción específica, las instancias activadas previamente pueden haber sido desactivadas y eliminadas de la agenda, y pueden haberse activado nuevas instancias.
Como parte del nuevo ciclo de emparejar-resolver-actuar, el motor realiza la resolución de conflictos en la agenda y luego ejecuta la primera instancia actual. El motor continúa disparando instancias de producción y entrando en nuevos ciclos de emparejar-resolver-actuar, hasta que no existan más instancias de producción en la agenda. En este punto, se considera que el motor de reglas ha completado 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 existan en la agenda.
Es posible que el motor entre en bucles interminables en los que la agenda nunca llega al estado vacío. Por esta razón, la mayoría de los motores admiten verbos de "detención" explícitos que se pueden invocar desde listas de acciones de producción. También pueden proporcionar detección automática de bucles en la que los bucles interminables 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, el disparo de instancias de producción activadas no es una característica del algoritmo Rete. Sin embargo, es una característica central de los motores que utilizan redes Rete. Algunas de las optimizaciones ofrecidas por las redes Rete solo son útiles en escenarios donde el motor realiza múltiples ciclos de coincidencia-resolución-acción.
Cuantificaciones existenciales y universales
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, es posible que las redes Rete realicen cuantificaciones . La cuantificación existencial implica probar la existencia de al menos un conjunto de WMEs coincidentes en la memoria de trabajo. La cuantificación universal implica probar que un conjunto completo de WMEs en la memoria de trabajo cumple una condición determinada. Una variación de la cuantificación universal podría probar que un número determinado de WMEs, extraído de un conjunto de WMEs, cumple con determinados criterios. Esto podría ser en términos de pruebas para un número exacto o un número mínimo de coincidencias.
La cuantificación no se implementa universalmente en los motores Rete y, cuando se admite, existen varias variaciones. Una variante de la cuantificación existencial a la que se hace referencia como negación tiene un apoyo amplio, aunque no universal, y se describe en documentos fundamentales. Las condiciones y conjunciones existencialmente negadas implican el uso de nodos beta especializados que prueban la inexistencia de WMEs coincidentes o conjuntos de WMEs. Estos nodos propagan listas 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 conteo simple en cada lista WME que recibe de su entrada izquierda. El recuento especifica el número de coincidencias encontradas con WMEs recibidas de la entrada correcta. El nodo solo propaga listas WME cuyo recuento es cero. En otro enfoque, el nodo mantiene una memoria adicional en cada lista WME recibida de la entrada izquierda. Estas memorias son una forma de memoria beta y almacenan listas WME para cada coincidencia con las WME recibidas en la entrada correcta. 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 más nodos beta directamente, en lugar de almacenar su salida en una memoria beta adicional. Los nodos de negación proporcionan una forma de " negación como fracaso ".
Cuando se realizan cambios en la memoria de trabajo, una lista de WME que anteriormente no coincidía con ningún WME ahora puede coincidir con los WME recién confirmados. En este caso, la lista WME propagada y todas sus copias extendidas deben retirarse de las memorias beta más abajo de la red. El segundo enfoque descrito anteriormente se usa a menudo para respaldar mecanismos eficientes para la eliminación de listas WME. Cuando se eliminan las listas de WME, las instancias de producción correspondientes se desactivan y 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 hay ningún WME coincidente, entonces ..."). Este es un enfoque común adoptado por varios sistemas de producción.
Indexación de memoria
El algoritmo de Rete no exige ningún enfoque específico para indexar 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 importante para decidir el rendimiento general de un sistema de producción, especialmente cuando se ejecutan conjuntos de reglas que dan como resultado una coincidencia de patrones altamente combinatoria (es decir, el uso intensivo de nodos de unión beta) o, para algunos motores, al ejecutar reglas conjuntos que realizan un número significativo de retractaciones de WME durante múltiples ciclos de coincidencia-resolución-acto. Las memorias a menudo se implementan usando combinaciones de tablas hash, y los valores hash se usan para realizar uniones condicionales en subconjuntos de listas WME y WMEs, en lugar de en todo el contenido de las memorias. Esto, a su vez, a menudo reduce significativamente el número de evaluaciones realizadas por la red Rete.
Eliminación de listas de WMEs y WME
Cuando un WME se retira de la memoria de trabajo, debe eliminarse de cada memoria alfa en la que está almacenado. Además, las listas WME que contienen el WME deben eliminarse de las memorias beta, y las instancias de producción activadas para estas listas WME deben desactivarse y eliminarse de la agenda. Existen varias variaciones de implementación, incluida la eliminación basada en árbol y basada en revancha. La indexación de memoria se puede utilizar en algunos casos para optimizar la eliminación.
Manejo de condiciones ORed
Al definir producciones en un conjunto de reglas, es común permitir que las condiciones se agrupen usando una conectiva OR . En muchos sistemas de producción, esto se maneja interpretando una sola producción que contiene múltiples patrones ORed como el equivalente de múltiples producciones. La red Rete resultante contiene conjuntos de nodos terminales que, juntos, representan producciones individuales. Este enfoque no permite ninguna forma de cortocircuito de las condiciones ORed. También puede, en algunos casos, llevar a que se activen instancias de producción duplicadas en la agenda donde el mismo conjunto de WMEs coincide con múltiples producciones internas. Algunos motores proporcionan deduplicación de la agenda para manejar este problema.
Diagrama
El siguiente diagrama ilustra la topografía básica de Rete y muestra las asociaciones entre diferentes tipos de nodos y memorias.
- La mayoría de las implementaciones utilizan nodos de tipo para realizar el primer nivel de selección en elementos de memoria de trabajo n-tuplos. Los nodos de tipo se pueden considerar como nodos selectos especializados. Discriminan entre diferentes 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 proporciona una vista lógica de la Rete. Las implementaciones pueden diferir en los detalles físicos. En particular, el diagrama muestra entradas ficticias que proporcionan activaciones correctas en la cabeza 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 compartir 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 (consulte el enlace a continuación).
Alternativas
Red Alfa
Una posible variación es introducir memorias adicionales para cada nodo intermedio en la red de discriminación. Esto aumenta la sobrecarga de Rete, pero puede tener ventajas en situaciones en las que las reglas se agregan o eliminan dinámicamente de Rete, lo que facilita la variación de la topología de la red de discriminación de forma dinámica.
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 se puede implementar usando una tabla hash . Cada memoria contiene WMEs que coinciden con un único patrón condicional, y el índice se utiliza para hacer referencia a las memorias por su patrón. Este enfoque solo es práctico cuando las WMEs 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 valores constantes . Cuando un WME ingresa al Rete, el índice se usa para ubicar un conjunto de memorias cuyo patrón condicional coincide con los atributos de WME, y luego el WME se agrega directamente a cada una de estas memorias. En sí misma, esta implementación no contiene nodos de 1 entrada. Sin embargo, para implementar pruebas de no igualdad, el Rete puede contener redes de nodos de 1 entrada adicionales a través de las cuales se pasan los WMEs antes de colocarse en una memoria. Alternativamente, las pruebas de no igualdad se pueden realizar en la red beta que se describe a continuación.
Red Beta
Una variación común es crear listas vinculadas de tokens donde cada token contiene un solo WME. En este caso, las listas de WMEs para una coincidencia parcial están representadas por la lista enlazada de tokens. Este enfoque puede ser mejor porque elimina la necesidad de copiar listas de WMEs de un token a otro. En cambio, un nodo beta solo necesita crear un nuevo token para contener un WME que desea unir a la lista de coincidencias parcial, y luego vincular el nuevo token a un token principal almacenado en la memoria beta de entrada. El nuevo token ahora forma el encabezado 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 dentro de las memorias alfa donde se utilizan para contener WMEs individuales. Estos tokens luego se pasan a la red beta.
Cada nodo beta realiza su trabajo y, como resultado, puede crear nuevos tokens para contener una lista de WMEs que representan una coincidencia parcial. Estos tokens extendidos se almacenan en memorias beta y se pasan a los nodos beta posteriores. En este caso, los nodos beta normalmente pasan listas de WMEs a través de la red beta copiando listas de WME existentes de cada token recibido en tokens nuevos y luego agregando más WMEs a las listas como resultado de realizar una unión o alguna otra acción. Los nuevos tokens se almacenan en la memoria de salida.
Consideraciones varias
Aunque no está definido por el algoritmo de Rete, algunos motores proporcionan una funcionalidad ampliada para admitir un mayor control del mantenimiento de la verdad . Por ejemplo, cuando se encuentra una coincidencia para una producción, esto puede resultar en la afirmación de nuevas WMEs que, a su vez, cumplen las condiciones para otra producción. Si un cambio posterior en la memoria de trabajo hace que la primera coincidencia deje de ser válida, es posible que esto implique que la segunda coincidencia también sea inválida. El algoritmo de Rete no define ningún mecanismo para definir y manejar estas dependencias de verdad lógica automáticamente. Sin embargo, algunos motores admiten funciones adicionales en las que las dependencias de verdad se pueden mantener automáticamente. En este caso, la retracción de un WME puede conducir a la retracción automática de WME adicionales para mantener afirmaciones de verdad lógica.
El algoritmo de Rete no define ningún enfoque de justificación. La justificación se refiere a los mecanismos comúnmente requeridos en los sistemas expertos y de decisión en los que, en su forma más simple, el sistema informa cada una de las decisiones internas utilizadas para llegar a una conclusión final. Por ejemplo, un sistema experto podría justificar la conclusión de que un animal es un elefante informando que es grande, gris, tiene orejas grandes, trompa y colmillos. Algunos motores proporcionan sistemas de justificación integrados junto con su implementación del algoritmo Rete.
Este artículo no proporciona una descripción exhaustiva de todas las posibles variaciones o extensiones del algoritmo de Rete. Existen otras consideraciones e innovaciones. Por ejemplo, los motores pueden proporcionar soporte especializado dentro de la red Rete para aplicar el procesamiento de reglas de coincidencia de patrones a fuentes y tipos de datos específicos , como objetos programáticos , datos XML o tablas de datos relacionales . Otro ejemplo se refiere a las instalaciones de sellado de tiempo adicionales proporcionadas por muchos motores para cada WME que ingresa a una red Rete, y el uso de estos sellos de tiempo junto con estrategias de resolución de conflictos. Los motores muestran una variación significativa en la forma en que permiten el acceso programático al motor y su memoria de trabajo, y pueden extender el modelo básico de Rete para admitir formas de procesamiento paralelo y distribuido.
Optimización y rendimiento
Se han identificado y descrito varias optimizaciones para Rete en la literatura académica. Sin embargo, varios de estos se aplican solo en escenarios muy específicos y, por lo tanto, a menudo tienen poca o ninguna aplicación en un motor de reglas de propósito general. Además, se han formulado algoritmos alternativos como TREAT, desarrollado por Daniel P. Miranker [6] LEAPS, y Design Time Inferencing (DeTI) que pueden proporcionar mejoras de rendimiento adicionales.
El algoritmo de Rete es adecuado para escenarios donde el encadenamiento hacia adelante y la "inferencia" se utilizan para calcular nuevos hechos a partir de hechos existentes, o para filtrar y descartar hechos con el fin de llegar a alguna conclusión. También se explota como un mecanismo razonablemente eficiente para realizar evaluaciones altamente combinatorias de hechos en las que se debe realizar un gran número de combinaciones entre tuplas de hechos. Otros enfoques para realizar la evaluación de reglas, como el uso de árboles de decisión o la implementación de motores secuenciales, pueden ser más apropiados para escenarios simples y deben considerarse como posibles alternativas.
El rendimiento de Rete también depende en gran medida de las opciones de implementación (independientemente de la topología de la red), una de las cuales (el uso de tablas hash) conduce a importantes mejoras. La mayoría de los puntos de referencia y las comparaciones de rendimiento disponibles en la web están sesgados de una forma u otra. Para mencionar solo un sesgo frecuente y un tipo de comparación injusta: 1) el uso de problemas de juguetes como los ejemplos de Modales y Vals; tales ejemplos son útiles para estimar propiedades específicas de la implementación, pero pueden no reflejar el desempeño real en aplicaciones complejas; 2) el uso de una implementación antigua; por ejemplo, las referencias en las siguientes dos secciones (Rete II y Rete-NT) comparan algunos productos comerciales con versiones totalmente desactualizadas de CLIPS y afirman que los productos comerciales pueden ser órdenes de magnitud más rápidos que CLIPS; esto es olvidar que CLIPS 6.30 (con la introducción de tablas hash como en Rete II) es órdenes de magnitud más rápido que la versión utilizada para las comparaciones (CLIPS 6.04).
Variantes
Rete II
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 revelado. 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 de C / ++ y en OPSJ, una implementación de Java en 1998. Rete II da alrededor de 100 Mejora del rendimiento de 1 orden de magnitud en problemas más complejos, como muestran los puntos de referencia de KnowledgeBased Systems Corporation [9] .
Rete II se puede caracterizar 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 en la parte superior de la red Rete. El encadenamiento hacia atrás por sí solo puede explicar los cambios más extremos en los puntos de referencia relacionados con Rete vs. Rete II. Rete II se implementa en el asesor de productos comerciales de FICO, anteriormente llamado Fair Isaac [10]
Jess (al menos las versiones 5.0 y posteriores) también agrega un algoritmo comercial de encadenamiento hacia atrás en la parte superior de la red Rete, pero no se puede decir que implemente completamente Rete II, en parte debido al hecho de que no hay una especificación completa disponible públicamente.
Rete-III
A principios de la década de 2000, Charles Forgy desarrolló el motor Rete III en cooperación con los 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. Es básicamente el motor Rete II con una API que permite el acceso al motor Advisor porque el motor Advisor puede acceder a otros productos FICO. [11]
Rete-NT
En 2010, Forgy desarrolló una nueva generación del algoritmo Rete. En una prueba de referencia de InfoWorld, el algoritmo se consideró 500 veces más rápido que el algoritmo original de Rete y 10 veces más rápido que su predecesor, Rete II. [12] Este algoritmo ahora tiene licencia para Sparkling Logic, la compañía a la que Forgy se unió como inversionista y asesor estratégico, [13] [14] como motor de inferencia del producto SMARTS.
ReteOO
Rete solo admite lógica booleana de primer orden . [15]
Ver también
- Mecanismo de selección de acciones
- Máquina de inferencia
Referencias
- ^ Charles Forgy: Rete: Un algoritmo rápido para el problema de coincidencia de patrones de muchos patrones / muchos objetos. En: Inteligencia artificial, vol. 19, págs. 17–37, 1982.
- ^ "Algoritmo de Rete desmitificado! - Parte 1" por Carole-Ann Matignon
- ^ Ian Wright; James Marshall. "El núcleo de ejecución de RC ++: RETE * Un Rete más rápido con TREAT como caso especial" (PDF) . Archivado desde el original (PDF) el 25 de julio de 2004 . Consultado el 13 de septiembre de 2013 .
- ^ Anurag Acharya; Milind Tambe. "Coincidencia orientada a colecciones" (PDF) . CIKM '93 Actas de la segunda conferencia internacional sobre gestión de la información y el conocimiento. doi : 10.1145 / 170088.170411 . Archivado desde el original (PDF) el 18 de marzo de 2012.
- ^ Coincidencia de producción para grandes sistemas de aprendizaje de la colección de informes técnicos de SCS, Escuela de Ciencias de la Computación, Universidad Carnegie Mellon
- ^ http://dl.acm.org/citation.cfm?id=39946 "TREAT: un nuevo y eficiente algoritmo de coincidencia para sistemas de producción de IA"
- ^ RETE2 de Tecnologías de sistemas de producción
- ^ Evaluación comparativa CLIPS / R2 de Production Systems Technologies
- ^ KBSC
- ^ http://dmblog.fico.com/2005/09/what_is_rete_ii.html
- ^ http://dmblog.fico.com/2005/09/what_is_rete_ii.html
- ^ Owen, James (20 de septiembre de 2010). "Motor de reglas más rápido del mundo | Sistemas de gestión de reglas de negocio" . InfoWorld . Consultado el 7 de abril de 2012 .
- ^ "Es oficial, el Dr. Charles Forgy se une a Sparkling Logic como asesor estratégico" . PR.com. 2011-10-31 . Consultado el 7 de abril de 2012 .
- ^ "Dr. Charles Forgy, PhD" . www.sparklinglogic.com . Consultado el 7 de abril de 2012 .
- ^ Sottara, Davide; Mello, Paola; Proctor, Mark (2010). "Un motor configurable Rete-OO para razonar con diferentes tipos de información imperfecta". Transacciones IEEE sobre conocimiento e ingeniería de datos . 22 (11): 1535-1548. doi : 10.1109 / TKDE.2010.125 .
- Charles Forgy , "Una rutina de combinación de redes para sistemas de producción". Documento de trabajo, 1974.
- Charles Forgy, " " Sobre la implementación eficiente de los sistemas de producción " . Tesis doctoral, Carnegie-Mellon University, 1979.
- Charles, Forgy (1982). "Rete: un algoritmo rápido para el problema de coincidencia de patrones de muchos patrones / muchos objetos". Inteligencia artificial . 19 : 17–37. doi : 10.1016 / 0004-3702 (82) 90020-0 .
enlaces externos
- Rete Algorithm explicó Bruce Schneier, Dr. Dobb's Journal
- Coincidencia de producción para grandes sistemas de aprendizaje: R Doorenbos Descripción detallada y accesible de Rete, también describe una variante llamada Rete / UL, optimizada para sistemas grandes (PDF)
- De acuerdo con las Reglas (una breve introducción de cut-the-knot )