algoritmo rete

Algoritmo Rete
El algoritmo Rete es un algoritmo de reconocimiento de patrones eficiente para implementar un sistema de producción de reglas. Fue creado por el Dr. Charles L. Forgy en la Carnegie Mellon University. Su primera referencia escrita data de 1974, y apareció de forma más detallada en su tesis doctoral (en 1979) y en un artículo científico de 1982.
Es una red donde todos los nodos(excepto las hojas) representan un patrón del L. Izq. de una regla.
Un camino entre la raíz y una hoja forma una regla.
Cada nodo tiene una memoria.
Cada nuevo hecho se propaga haciendo que los nodos puedan cambiar sus memorias.
Si la propagación alcanza una hoja se dispara una regla
Reglas
1) A(x)  B(x)  C(y)  add D(x)
2) A(x)  B(y)  D(x)  add E(x)
3) A(x)  B(x)  E(z)  delete A(x)Memoria de Trabajo
{A(1), A(2), B(2), B(3), B(4), C(5)}
Estructura o enfoque tradicional




Nodos
Tipos de nodos
1 Entrada / 1 Salida (Tipo A)
Son reductores y únicamente permiten el paso de tuplas que cumplen con la condición requerida.
2 Entradas / 1 Salida (Tipo B)
Conectan la salida de otros dos nodos (cualquier tipo).
Mantienen una memoria con las tuplas que cumplen lacondición. Esto evita repetir comparaciones en vano.
Nodos tipo A forman la entrada de la red.
Cada tupla tiene un tipo determinado.
Una condición es un patrón que especifica las características que una tupla debe cumplir.
Ciclo Básico
Mientras se produzcan cambios en la MT.
IDENTIFICAR
Construir un conjunto con todos los pares (R,H) donde R es una regla y H es un subconjunto dehechos que se unifican con las condiciones del lado izquierdo de R.

RESOLVER CONFLICTOS
Seleccionar un par (R,H) del conjunto-conflicto para ejecución.

ACTUAR
Ejecutar las acciones relacionadas con el lado derecho de R.

Conflictos
Refracción
Una regla sólo puede utilizarse una vez para cada conjunto de hechos vigente.
Nuevos hechos primero
Utilizar reglas queutilizan los hechos agregados más recientemente.
Especificidad
Utilizar la regla más específica (i.e. la más “pequeña”)
Prioridades
Asignar prioridades a las reglas (e.g. MYCIN)



Ejemplo RETE

(deftemplatex (slot a) )
(deftemplatey (slot b) )
(deffactshechos (x (a 5)) (y (b 5)) )

(defruleejemplo-1
(x (a ?v1))
(x (a ?v1))
=> (assert(p)))

(defruleejemplo-2
(x (a ?v2))(y (b ?v2))
(z)
=> (assert(q)))
Heurística al construir reglas
Patrones específicos.
Deben tener preferencia en el lado izquierdo.
Variables sin ligar o comodines deben ir más a la derecha.
Patrones con pocas condiciones
se deben colocar al principio para minimizar correspondencias parciales.
Patrones volátiles
Deben ser colocados de último en la lista.
Mejoras de rendimientoCompartir Nodos-Patrón

Compartir Nodos-Unión



Ventajas
Una implementación simple de un sistema experto basado en reglas comprobaría cada regla con los hechos de la base de conocimiento activando la regla si corresponde, y pasando a evaluar la siguiente. Este algoritmo, incluso para un número bajo de reglas y hechos, tiene un tiempo de ejecución muy alto (haciéndolo inadecuado para sistemasde producción reales).
El algoritmo Rete (cuya pronunciación suele ser 'REET', 'REE-tee' o, en Europa, 're-tay' que viene de su pronunciación en Latín, dado que 'rete' significa red en Latín) es la base de diversas implementaciones más eficientes de sistemas expertos. Un sistema experto basado en Rete construye una red de nodos, donde cada uno de ellos (excepto el nodo raíz) representa un patrónque aparece en la parte izquierda (el condicional) de una regla. Por lo tanto, el camino desde el nodo raíz a una hoja define la parte condicional entera de una regla. Cada nodo tiene una memoria de hechos que satisfacen su patrón. Esta estructura es, básicamente, un Trie.
A medida que se añaden o modifican hechos, se propagan los cambios por la red, haciendo que los nodos que se activan con...