DSI tema 4

2 files changed, 695 insertions, 0 deletions

diff --git a/dsi/n.lyx b/dsi/n.lyx
index c3fded1..d40ea5e 100644
--- a/dsi/n.lyx
+++ b/dsi/n.lyx
@@ -196,6 +196,18 @@ https://dle.rae.es/lexic%C3%B3n
  el 25 de septiembre de 2022.
 \end_layout
 
+\begin_layout Itemize
+Charles L.
+ Forgy.
+ 
+\emph on
+\lang english
+Rete: A Fast Algorithm for the May Pattern/Many Object Pattern Match Problem
+\emph default
+\lang spanish
+ (1981).
+\end_layout
+
 \begin_layout Chapter
 Ontologías
 \end_layout
@@ -238,5 +250,19 @@ filename "n3.lyx"
 
 \end_layout
 
+\begin_layout Chapter
+Técnicas de equiparación
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n4.lyx"
+
+\end_inset
+
+
+\end_layout
+
 \end_body
 \end_document
diff --git a/dsi/n4.lyx b/dsi/n4.lyx
new file mode 100644
index 0000000..4787691
--- /dev/null
+++ b/dsi/n4.lyx
@@ -0,0 +1,669 @@
+#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{<<regla>>} & \to\text{\textbf{SI}}\,\text{<<antecedente>>}\,\text{\textbf{ENTONCES}}\,\text{<<consecuente>>}\\
+\text{<<antecedente>>} & \to\text{<<condición>>}\mid\text{<<condición>>}\land\text{<<antecedente>>}\\
+\text{<<condición>>} & \to\text{<<patrón>>}\mid\neg\text{<<patrón>>}\mid(\mathtt{test}\,\text{<<sexpr>>})\\
+\text{<<consecuente>>} & \to\mathtt{Añadir}\text{<<patrón>>}\mid\mathtt{Borrar}\text{<<patrón>>}\\
+\text{<<patrón>>} & \to(\text{<<constante>>}\,\text{<<parámetros>>})\\
+\text{<<parámetros>>} & \to\mid\text{<<constante>>}\,\text{<<parámetros>>}\mid\text{<<variable>>}\,\text{<<parámetros>>}\\
+\text{<<constante>>} & \to\mathtt{[\mathcircumflex?)\ ][\mathcircumflex)\ ]*}\\
+\text{<<variable>>} & \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{<<sexpr>>}$
+\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{<<sexpr>>}$
+\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