#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \begin_preamble \input{../defs} \end_preamble \use_default_options true \maintain_unincluded_children false \language spanish \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style french \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Standard El rendimiento del proceso de equiparación en un sistema basado en reglas es afectado por un número elevado de reglas en la base de conocimiento y por la aparición de variables en los antecedentes de las reglas, que en general siempre se da al escribir las reglas con la mayor generalidad posible, convirtiendo la equiparación en un proceso no trivial. \end_layout \begin_layout Standard Para mitigar los problemas por el número elevado de reglas usamos \series bold técnicas de indexado \series default . Una de ellas consiste en dividir el problema en varias etapas y agrupar las reglas según dichas etapas, añadiendo condiciones en el antecedente de las reglas relacionadas con las etapas. Sin embargo, esto reduce la generalidad de las reglas. \end_layout \begin_layout Section Equiparación con variables \end_layout \begin_layout Standard Representamos reglas con una sintaxis basada en el lenguaje CLIPS: \end_layout \begin_layout Standard \begin_inset Formula \begin{align*} \text{<>} & \to\text{\textbf{SI}}\,\text{<>}\,\text{\textbf{ENTONCES}}\,\text{<>}\\ \text{<>} & \to\text{<>}\mid\text{<>}\land\text{<>}\\ \text{<>} & \to\text{<>}\mid\neg\text{<>}\mid(\mathtt{test}\,\text{<>})\\ \text{<>} & \to\mathtt{Añadir}\text{<>}\mid\mathtt{Borrar}\text{<>}\\ \text{<>} & \to(\text{<>}\,\text{<>})\\ \text{<>} & \to\mid\text{<>}\,\text{<>}\mid\text{<>}\,\text{<>}\\ \text{<>} & \to\mathtt{[\mathcircumflex?)\ ][\mathcircumflex)\ ]*}\\ \text{<>} & \to\mathtt{\backslash?[\mathcircumflex)\ ]*} \end{align*} \end_inset \end_layout \begin_layout Standard Una \series bold condición negada \series default es un patrón inmediatamente precedido por \begin_inset Formula $\neg$ \end_inset . Todas las variables en el consecuente de una regla deben aparecer en algún patrón no negado en el antecedente. \end_layout \begin_layout Standard Los elementos o hechos de la BH son patrones sin variables. Usamos la \series bold hipótesis del mundo cerrado: \series default todo hecho que no aparece en la BH se considera falso. \end_layout \begin_layout Standard Una \series bold instanciación \series default es un par formado por una regla de la BC y una lista de hechos de la BH de forma que: \end_layout \begin_layout Enumerate La lista tiene tantos elementos como patrones no negados en el antecedente. \end_layout \begin_layout Enumerate Existe una asignación de las variables que aparecen en la regla a constantes tal que, al sustituir en la regla: \end_layout \begin_deeper \begin_layout Enumerate Los hechos de la lista son iguales a los correspondientes patrones no negados del antecedente de la regla. \end_layout \begin_layout Enumerate Los patrones negados no aparecen en la BH. \end_layout \begin_layout Enumerate Los \begin_inset Formula $\text{<>}$ \end_inset en la regla evalúan a un valor verdadero en un entorno léxico resultante de añadir al entorno global esta asignación de variables en el espacio de nombres de valores. \begin_inset Foot status open \begin_layout Plain Layout La terminología es del estándar de Common Lisp ( \begin_inset Flex URL status open \begin_layout Plain Layout http://www.lispworks.com/documentation/HyperSpec/Body/03_a.htm \end_layout \end_inset ), pero básicamente esto significa que cada \begin_inset Formula $\text{<>}$ \end_inset es una condición en la que aparecen las variables y que deben cumplir los valores asignados a estas variables. \end_layout \end_inset \end_layout \end_deeper \begin_layout Standard El conjunto conflicto es el conjunto de instanciaciones posibles. \end_layout \begin_layout Section Algoritmo RETE \end_layout \begin_layout Standard \series bold RETE \series default ( \series bold REdundancia TEmporal \series default ) es un algoritmo propuesto por Forgy en 1979 y 1982 para calcular el conjunto conflicto de forma incremental, teniendo en cuenta que cada ejecución de una regla hace pocos cambios a la BH y por tanto al conjunto conflicto. \end_layout \begin_layout Standard Un \series bold testigo \series default es un par formado por una etiqueta \begin_inset Formula $+$ \end_inset o \begin_inset Formula $-$ \end_inset y una lista de hechos. Cada vez que se añade o borra un hecho de la BH se crea un \series bold testigo \series default con etiqueta \begin_inset Formula $\mathtt{+}$ \end_inset o \begin_inset Formula $\mathtt{-}$ \end_inset respectivamente y el hecho, y se envía al nodo raíz de la \series bold red RETE \series default , un grafo dirigido cuyos nodos reciben testigos o listas de testigos, los procesan y pueden propagarlos a sus sucesores. Tipos de nodos en la red: \end_layout \begin_layout Enumerate \series bold Raíz: \series default Hay uno. Recibe testigos de fuera y los propaga. \end_layout \begin_layout Enumerate \series bold De componente: \series default Contiene un índice (de la lista de los componentes de los hechos en el testigo) y una constante. Recibe un testigo y lo propaga sólo si tiene esa constante en ese índice. \end_layout \begin_layout Enumerate \series bold Terminal: \series default Contiene una regla. Cuando recibe un testigo positivo, crea una instanciación con dicha regla y los hechos, y cuando recibe uno negativo la borra. \end_layout \begin_layout Enumerate \series bold De comprobación de variables: \series default Contiene dos índices. Recibe un testigo de un solo hecho y lo propaga sólo si los valores en esos índices del hecho son iguales. \end_layout \begin_layout Enumerate \series bold De unión de elementos condición de una misma regla: \series default Le llegan testigos de un puerto izquierdo y uno derecho, y cada puerto tiene asociada una memoria de testigos positivos. Cuando recibe un testigo positivo, lo añade a la memoria de ese puerto, y cuando recibe uno negativo lo borra de esa memoria. Entonces, para cada testigo en la memoria del otro puerto, propaga un testigo con la etiqueta del testigo recibido cuyos hechos resultan de concatenar los del testigo recibido y el de la memoria, primero los de la izquierda y luego los de la derecha. \end_layout \begin_layout Enumerate \series bold De unión de elementos condición de una misma regla que contiene varias variables : \series default Como el anterior pero además contiene una lista de pares de índice del testigo izquierdo e índice del derecho, y sólo propaga los testigos concatenado s si en cada par de índices de la lista los valores son iguales. \end_layout \begin_layout Enumerate \series bold De unión de elementos de condición negados con los restantes elementos de condición de una misma regla: \series default También tiene dos puertos, una memoria de testigos positivos en cada uno y una lista de pares de índices, pero los testigos en la memoria izquierda tienen un contador asociado. Cuando llega un testigo positivo por la izquierda, se guarda con un contador igual al número de testigos por la derecha para los que se da la igualdad en los pares de índices, y se propaga si el contador es 0. Cuando llega uno negativo, si había uno positivo, se borra, y si su contador era 0, se propaga el testigo negativo. Cuando llega un testigo positivo por la derecha, se guarda y se aumenta en 1 el contador de los testigos de la izquierda para los que se da la igualdad en los pares de índices, y para los que dejan de estar a 0 se propaga un testigo igual pero negativo. Cuando llega uno negativo por la derecha, si había uno igual positivo, se borra y, para cada testigo de la izquierda para el que se da la igualdad, el contador se reduce en 1, propagando el testigo si llega a 0. \end_layout \begin_layout Standard Podemos suponer que todos los hechos con igual primer elemento tienen la misma longitud, pues de lo contrario basta renombrarlo. Podemos suponer que toda regla tiene un patrón no negado en el antecedente, pues de lo contrario basta crear un hecho \family typewriter (T) \family default que siempre está en la base de hechos y añadirlo al antecedente de la regla. \end_layout \begin_layout Standard Para compilar un conjunto de reglas en una red: \end_layout \begin_layout Enumerate Se crea el nodo raíz. \end_layout \begin_layout Enumerate Para cada patrón del antecedente de cada regla: \end_layout \begin_deeper \begin_layout Enumerate Se crea un nodo componente por cada componente constante del patrón. \end_layout \begin_layout Enumerate Para cada variable que aparece \begin_inset Formula $n\geq2$ \end_inset veces en el patrón, se crean \begin_inset Formula $n-1$ \end_inset nodos de comprobación de variables para asegurar que las apariciones son iguales. \end_layout \begin_layout Enumerate Se crea un eje del nodo raíz al primer nodo creado en este paso y uno de cada nodo al siguiente. \end_layout \end_deeper \begin_layout Enumerate Para cada regla con \begin_inset Formula $n\geq2$ \end_inset patrones: \end_layout \begin_deeper \begin_layout Enumerate Elegimos un patrón no negado del antecedente y llamamos \begin_inset Formula $L$ \end_inset al último nodo de su secuencia. \end_layout \begin_layout Enumerate Para cada otro patrón del antecedente: \end_layout \begin_deeper \begin_layout Enumerate Llamamos \begin_inset Formula $R$ \end_inset al último nodo del patrón. \end_layout \begin_layout Enumerate Creamos un nodo de unión de elementos de condición, o de elementos de condición negados si el patrón de \begin_inset Formula $R$ \end_inset está negado. \end_layout \begin_layout Enumerate Conectamos \begin_inset Formula $L$ \end_inset al puerto izquierdo y \begin_inset Formula $R$ \end_inset al derecho. \end_layout \begin_layout Enumerate Para cada variable que aparezca tanto en algún patrón de \begin_inset Formula $L$ \end_inset como en el de \begin_inset Formula $R$ \end_inset , añadimos un par de índices a la lista del nodo creado para asegurar que sean iguales. \end_layout \end_deeper \end_deeper \begin_layout Enumerate Mientras haya dos nodos iguales con el mismo predecesor, estos nodos se unen en uno solo. \end_layout \begin_layout Standard Esta versión no considera \emph on \lang english tests \emph default \lang spanish en el antecedente, pero estos se representan trivialmente como variantes de nodos de componente, comprobación de variables o unión que en vez de comprobar igualdades, o además, comprueba la condición. \end_layout \begin_layout Standard Muchos de estos pasos no especifican exactamente el orden de los elementos, por lo que estos se pueden reordenar para poner las comprobaciones de \emph on \lang english tests \emph default \lang spanish y otras con más posibilidades de fallar lo más arriba posible y maximizar el número de uniones de nodos, aumentando la eficiencia. \end_layout \begin_layout Section Resolución de conflictos \end_layout \begin_layout Standard Consiste en elegir qué instanciación se ejecuta del conjunto conflicto. Algunas estrategias: \end_layout \begin_layout Enumerate \series bold Selección arbitraria. \series default Se elige aleatoriamente. \begin_inset Quotes cld \end_inset Sólo es aplicable cuando todas las reglas tienen la misma posibilidad de ser efectivas. \begin_inset Quotes crd \end_inset \end_layout \begin_layout Enumerate \series bold Selección de la primera regla. \series default Se elige la primera instanciación en un cierto buen orden del conjunto conflicto, o una de la primera regla en un cierto buen orden de la base de reglas. \begin_inset Foot status open \begin_layout Plain Layout Las diapositivas dicen una cosa y luego la otra, y la segunda sería una forma de selección por prioridad. \end_layout \end_inset Hay problemas en los que establecer un buen orden de la base de reglas no es deseable. \end_layout \begin_layout Enumerate \series bold Selección por prioridad. \series default Cada regla tiene asignada una prioridad y se elige una instanciación con máxima prioridad de su regla. Algunos sistemas permiten establecer la prioridad según el orden de escritura de la base de conocimiento. \end_layout \begin_layout Enumerate \series bold Regla más específica. \series default Una regla es más o igual de específica que otra si tiene todas las condiciones de la otra. Se ignora la instanciación más genérica. \end_layout \begin_layout Enumerate \series bold Elemento añadido más recientemente. \series default Cada elemento de la BH tiene asociada una marca de tiempo con el momento de su creación o última modificación (regeneración del hecho por parte de una regla), medida bien en número de ciclos (actualizaciones del CC), o en número de acciones ejecutadas, en cuyo caso no todos los elementos añadidos por la misma instanciación de una regla tienen la misma prioridad. Se elige la instanciación que contiene el hecho más reciente en la CC. \end_layout \begin_layout Enumerate \series bold Seleccionar una nueva regla. \series default Se elige una instanciación no ejecutada previamente, evitando que una misma regla se ejecute indefinidamente ( \series bold principio de refracción \series default ). Una instanciación que desaparece del conjunto conflicto y luego vuelve a aparecer no se considera ejecutada. \end_layout \begin_layout Enumerate \series bold Seleccionar todas las reglas. \series default Se aplican todas las reglas a la vez en el mismo ciclo. Es especialmente útil en dominios médicos para examinar todas las posibilidades , pero hay que tener cuidado de no incurrir en una explosión combinatoria o recorrer caminos idénticos. \end_layout \begin_layout Standard Cada una de estas estrategias salvo la última se puede ver como una función que recibe un conjunto de instanciaciones no vacío y devuelve un subconjunto de este. Dadas dos estrategias \begin_inset Formula $f$ \end_inset y \begin_inset Formula $g$ \end_inset de este tipo, llamamos \begin_inset Formula $f\CIRCLE g$ \end_inset a la estrategia dada por \begin_inset Formula $A\mapsto f(A)\cap g(A)$ \end_inset , y \begin_inset Formula $f\to g$ \end_inset a la estrategia dada por \begin_inset Formula \[ A\mapsto\begin{cases} f(A), & |f(A)|\leq1,\\ g(f(a)), & \text{en otro caso}. \end{cases} \] \end_inset Ambos operadores son asociativos, y el segundo no necesita que la estrategia \begin_inset Formula $g$ \end_inset sea de este tipo pero si no lo es la estrategia \begin_inset Formula $f\to g$ \end_inset en general tampoco lo es. \end_layout \end_body \end_document