Definición de búsqueda de solución.

Uno de los métodos de búsqueda de soluciones para problemas poco estructurados (no existe un algoritmo bien definido), son los espacios de estado

Ejemplo: Imaginemos que estamos en un parque (un Zoológico) que tiene varias entradas y varias salidas y que existen diferentes lugares donde se exhibe o se vende algo (estado).

Un algoritmo lo que haría seria dado una entrada encontrar un camino que me lleve a una salida (sin explorar las demás posibilidades).

Ejemplo de algoritmo, sea el camino: Entrada 1, estado 1, estado 4, Salida 2.

En cambio a través de una exploración no algoritmica yo podría visitar todos los lugares (estados).

Definiciones:.

Problemas numéricos: Se busca una representación numérica del problema. Casi siempre aplicando un método de aproximaciones sucesivas.

Características de los algoritmos:
• Finitud: que termine.
• Definibilidad: orden de ejecución y representación de instrucciones.
• Determinismo: que siempre haya solución.

Los problemas numéricos son siempre estructurados, donde los datos y las soluciones están bien definidos, así como los pasos a seguir para llegar a las ultimas.
Y pueden ser:
• Algoritmos exactos (solución exacta).
• Algoritmos aproximados (solución basada en iteraciones).

Problemas lógicos: El hallazgo de la solución de un problema mediante un “espacio”de estado y los métodos de búsqueda en este espacio de solución.

Espacio de estado: se trata de definir el problema mediante estados posibles.

Estado: Estructura de datos que representan una fotografía de un momento dado en una etapa de solución.

Es necesario hacer cambios en el espacio de estado para que pase a otro estado (movimiento), el cual también sufrirá nuevas transformaciones. Por lo cual hay que definir una serie de operadores.

Operador: convierte un estado en otro.

Pero hace falta definir el conjunto de acciones para llevar a cabo las transformaciones entre estados.

No todos los estados son admisibles a partir del estado inicial. Debe existir un conjunto de transferencias que lleve a la estado final:
E0 ~ E1 ~ E2 ~……En

Al conjunto de transferencias también se le llaman reglas del tipo:
Antecedente  Acción.
Que sirven para realizar todos los estados.

Heurística: es una estrategia que limita drásticamente la búsqueda de soluciones de un problema.

Búsqueda exhaustiva: exploración (normalmente en forma de árbol) de todos los caminos posibles.

Estrategias de control sistemático

Como ya se vio la MI tiene asociada una estrategia de control para poder manejar la BC y esa estrategia de control debe conducir a la solución del problema.

Existen dos tipos de estrategia de control:
• Estrategia de control sistemática.
• Estrategia de control heurística.

Estrategias de tipo sistemático:
1. Encadenamiento hacia delante.
2. Encadenamiento hacia atrás.
3. Búsqueda en profundidad.
4. Búsqueda a lo ancho.
5. Régimen de control irrevocable.
6. Régimen de control por tentativa.

La filosofía de estas metodológicas sistemáticas en los sistemas expertos se fundamenta en la necesidad de obtener una movilidad global durante la invocación de las reglas en el ciclo de evaluación y ejecución.

Según el sentido de enlace entre las reglas:
• Encadenamiento hacia delante (foward-chaining).
• Encadenamiento hacia atrás (backward-chaining).

Según la dirección en la topografía que desarrollan las reglas:
• Búsqueda en profundidad.
• Búsqueda a lo ancho.

Según la estrategia de unificación (pattern-matching).
• Régimen de control irrevocable.
• Régimen de control por tentativas.

Para un sistema experto basado en el proceso deductivos seria:
Si hay una absoluta credibilidad A y existe la regla A  B entonces hay absoluta credibilidad en B.
Y si A es un conjunto de cláusulas del tipo A1, A2,…An. pero puede ser que B no sea totalmente cierta.

Cuando el conocimiento no es confiable

A sugiere B con un factor de confianza
H y B sugieren C con otro factor de confianza.

Formas de resolver esto.
1) Aplicando probabilidades.
P(B/A): probabilidad de que se presente B a partir de A (encadenamiento hacia delante).
2) Aplicando conjuntos difusos.

Y tendremos:

A  B cf (dado que B no esta totalmente cierta se da un cf: coeficiente de certeza)

También puede suceder que A no sea totalmente creíble.
Acf’  Bcf
O sea
A1cf1  A2cf2  …  Bcf

Cuando el conocimiento no es confiable

A sugiere B con un factor de confianza
H y B sugieren C con otro factor de confianza.

Formas de resolver esto.
2) Aplicando probabilidades.
P(B/A): probabilidad de que se presente B a partir de A (encadenamiento hacia delante).
2) Aplicando conjuntos difusos.

El problema de totalizar el valor de la incertidumbre implica el calculo sobre un conjunto de coeficientes relacionados por los operadores lógicos AND, OR y 

A tal efecto se consideran los siguientes conceptos:

1. Determinar el valor de la premisa de una regla por efecto de la conjunción de las cláusulas contenida en la misma (AND).
2. Determinar la propagación del valor de la premisa de una regla sobre la conclusión de la misma (  ).
3. Determinar el valor de la disyunción por efecto de la combinación de varias reglas con la misma conclusión (OR).

VP: valor de la premisa de una regla (cf1 AND cf2 AND cf3 …)
También: VP = cf1  cf2  cf3 … = min (cf1, cf2, cf3,…).

VR: valor de la regla por la propagación (VP  cf)
También: VR = VP  cf = min (VP, cf)

VC: valor de la conclusión por la combinación de las VR (VR1 OR VR2)
También: VC = VR1 + VR2 – VR1  VR2 = max (VR1, VR2).

Ejemplo de calculo de los factores de certeza

R1: Si A1cf11 y B1cf12 entonces C1cf1
R2: Si A2cf21 y B2cf22 entonces C2cf2

Para hallar el valor de la premisa

R1: VP1 = min {cf11, cf12}
R2: VP2 = min {cf21, cf22}

Para hallar el valor de la regla (propagación).
R1: VR1 = Vp1  cf1
R2: VR2 = Vp2  cf2

Para hallar el valor de las conclusiones (combinación)
VC = VR1 + VR2 – VR1  VR2

Hay que hallar un valor mínimo (umbral) tal que VC  Vmin

Para ello se halla el valor máximo que puede tener ese umbral dándole a todos los Cf de las premisas el valor de uno y se tendrá.

R1: Si A1(1) y B1(1) entonces C1cf1
R2: Si A2(1) y B2(1) entonces C2cf2

VP1 = 1
VP2 = 1

Por tanto.
VR1 = 1  cf1 = cf1
VR2 = 1  cf2 = cf2

Donde
VC = cf1 + cf2 – cf1  cf2 = Vi = Vmax

Y se tendrá Vmin  Vmax
Para cada conclusión del mismo tipo se obtiene:
Vmin  Vi

Ejemplo de conocimiento incierto:

H1: Te sugiero ir al cine.
H2: Te sugiero quedarte en casa.
H3: Tienes dinero.
H4: Tienes tiempo suficiente
H5: Esta lloviendo.
H6: La película esta buena.
H7: La película es de acción.
H8: La película es un drama.
H9: La película es de amor.
H10: La película es una comedia.

R1: Si H10 entonces H6 80%
R2: Si H8 entonces H6 60%
R2: Si H7 entonces H6 70%
R3: Si H6 entonces H1 60%
R4: Si H6 y H3 entonces H1 80%
R5: Si H6 y H3 y H4 entonces H1 95%.

El valor de certeza se da en % entre [0 , 100]

El sistema experto MYCIN opera sobre una Base de Conocimientos (BC), bien organizada sobre las enfermedades infecciosas, donde el conocimiento es inexacto por lo que el punto central son las técnicas para expresar medidas de opinión, llamadas factores de certeza.

La estructura de control es simple y esta basada en un sistema de producción.
1) Una colección de hechos.
2) Un conjunto de reglas de producción.
3) Un generador de inferencias con encadenamiento hacia delante o hacia a tras (o ambos), junto a una estructura de conocimiento que capacita a la estructura de control para disidir que reglas, de todas las posibles, debe tomar parte en el mecanismo de inferencia.
4) Un mecanismo que realice inferencias, a partir de evidencias inciertas o incompletas..

En MYCIN las agrupaciones de reglas dentro de un determinado contexto se definen en tiempo de generación. El generador de inferencias proporciona una búsqueda dirigida por objetivos o por datos.

La existencia de una estructura de control dependiente del dominio, la hace específica. Por eso se han extraído de MYCIN las partes independientes del dominio para formar el MYCIN “vacio” o “hueco”, EMYCIN. El cual se ha empleado en otros dominios tales como PUFF (cuidado respiratorio intensivo), SACON (calculo de estructuras de ingeniería), GRAVIDA (consejos para el embarazo), CLOT (desordenes de la sangre) y VM (manejo de la ventilación).

Hechos.
(contexto)(parametro)(valor)

El contexto es alguna entidad del mundo real. Ejemplo: un paciente.
Un parámetro es un atributo del contexto. Ejemplo: la edad.
El valor es una particularización del pararámetro. Ejemplo: 25 años.
A cada terna se le asocia un valor de certeza (FC).
FC toma valores en el intervalo (-1, 1) donde -1 es la negación, 0 la ignorancia absoluta y 1 total certidumbre.

Ejemplo:
Organismo 1 – Identidad pseudomonas .8 (La identidad del organismo 1 es, con un factor de certeza 0.8, pseudomonas).

Reglas de producción.

Si premisa entonces acción (FC).

En MYCIN las reglas se definen para poder encadenar hacia delante o hacia a tras. Las reglas se utilizan repetidamente utilizando el conocimiento dependiente del dominio para decidir que reglas se deben considerar, hasta que se de un contenido a los hechos. En algunos casos, las reglas darán contenido a los hechos mediante preguntas al medico.

Ejemplo de reglas:

Si (no se sabe si el organismo fue capaz de desarrollarse en presencia del aire (aerobicamente))
Y (el lugar de cultivo es la sangre)
O (el laboratorio ha intentado que el organismo se desarrolle sin la presencia del aire (anaerobicamente)
Y (el organismo fue capaz de desarrollarse anaerobicamente)
Entonces (hay evidencias de que el organismo es aerobio (.5) O anaerobio (.2).

Las premisas serán verdad si todos los hechos son verdad.

Factor de certeza.

En general:
Si (contexto-parametro-valor (FC1)) y/o (contexto-parametro-valor (FC2)) y/o…….
Entonces (contexto-parametro-valor (FC)).

FCMin(FC1, FC2,….) = RC

Si la regla no venia arrastrando ningún valor de certeza entonces RC se colocara como su factor de certeza (FC) , si ya tenia con un valor IC. Se calculara el FC actual.

FC = IC + |RC| (1- |IC|) 0RC, IC

FC = -(|IC| + |RC| (1- |IC|)) 0RC, IC

IC + RC
Fc = —————- RC . IC 0
1 – min(|IC|, |RC|)

La combinación de –1 y 1 se define como 1.

Este metodo del facto de certeza permite que el sistema se pueda enfrentar al razonamiento de juicios.

Estructura de control dependiente del dominio

El orden de las reglas no es significativo se aplican todas las reglas relevantes hasta que una determinada consigue un objetivo con certeza, en cuyo caso el resto de las reglas se ignora. La relevancia de una regla se define por la estructura del control dependiente del dominio, la cual se organiza como un árbol de contexto donde se organizan los hechos de la BC en una jerarquía, y se utiliza para definir el flujo de la consulta. Las reglas se agrupan en conjuntos de reglas definidas por el conjunto de tipos de contexto de aplicación de las mismas (una regla siempre se refiere a un determinado tipo de contexto).

Obtención de información a partir del usuario.

Las preguntas se hacen o bien cuando fallan las reglas o bien cuando la información ha de provenir del usuario (ejemplo: datos de laboratorio). Se puede reelaborar una pregunta y permite diferentes conjunto de preguntas para usuarios con experiencia y sin ella, y se basa en la propiedad de “preguntar – primero”, el sistema siempre procura primero obtener el valor de un parámetro a partir del usuario.

El diseñador debe proporcionar un medio aceptable de comunicación con el usuario, MYCIN no fue totalmente satisfactorio en ese aspecto, lo cual se resolvió en ONCOCIN.

Facilidades de explicación

MYCIN como muchos otros SE tienen la facilidad de explicar y justificar su funcionamiento, lo cual es útil para funciones educativas. En cualquier momento el usuario puede preguntarle “como” o “porque” , tomo tal decisión. Esto es a través de reglas

Ejemplo:
Si “esta nublado” entonces “va a llover”
“Si “va a llover ”entonces “coger la capa”

Ahora se le puede pregunta al sistema:
Porque “coger la capa”?
Porque “esta nublado” y “va a llover”.

Los Se son el resultado de una serie de consultas entre los constructores del sistema y expertos en el dominio de conocimiento de interés. Este proceso es laborioso y propenso a errores. Los expertos saben normalmente, mas de lo que piensan y no siempre pueden expresar fácilmente sus procesos de ra

Veremos algunos ejemplos que han sido paradigmas de SE dentro de la IA.

Dendral : Reducción de grandes espacios de búsqueda mediante factorización (heurística).

Ayudar a los químicos a inferir la estructura de los componentes químicos a partir de los datos del espectro de masa.

Se partió de la técnica de generar y probar la cual depende de la forma en la que se desarrolla el espacio de estados y de predecir que ramas conducirán a la solución, hasta que profundidad se debe explorar una rama sin que se pierda una posible solución.

Fue el pionero en el cambio de enfoque hacia las estructuras de control dependientes del dominio.

MYCIN. El manejo de evidencia incierta.

Sistema para el diagnostico de infecciones bacterianas.

Se basa en conocimientos indefinidos y datos imprecisos en vez de los manejos del espacio del problema.

DENDRAL

El paradigma de búsqueda en espacios de estados. El cual se basa en una búsqueda a través de una red de nodos, donde cada uno representa un posible estado del problema, donde casi siempre una búsqueda exhaustiva de todo el espacio es imposible (explosión combinatoria). Un método es controlar la búsqueda en el espacio de estado basándose en la relación que hay entre los estados.

Una técnica muy conocida es la de “generar y probar”. Comenzando por algún estado inicial, se utiliza un generador para producir un conjunto de estados descendentes, se aplica entonces a ese conjunto una serie de pruebas de validez para reducirlo a un tamaño más manejable. Estas pruebas adoptan normalmente la forma de restricciones, también es posible incorporar estas restricciones al generador reduciendo el numero de estados descendientes a probar. El método “generar y probar” solo funciona, si cuando un estado se declara invalido, todos sus estados descendientes lo son.

DENDRAL, fue el primer sistema basado en conocimientos que utilizo el método de “generar y probar” para las conexiones de las estructuras de compuestos de química orgánica. El proyecto comenzó en 1965 con el objetivo de proporcionar un soporte en la computadora a los químicos, profesionales que no eran expertos en determinadas técnicas analíticas y tubo tal éxito que inspiro a la creación del área de los sistemas expertos en la IA.

La tarea de la aplicación.

DENDRAL: es un sistema diseñado para ayudar a los químicos a determinar la estructura de algún compuesto desconocido, con especial énfasis e el uso de los datos provenientes de un espectrometro de masas.

El programa de planificación de DENDRAL

En la practica hizo falta un programa de planificación para producir las restricciones a la hora de generar. El ciclo completo es PLANFICAR – GENERAR – PROBAR.

Con el planificador se evita la generación superflua y simplifica la fase de prueba.

Semejante a MYCIN, DENDRAL no pretende simular los procesos interpretativos que utilizan los químicos. No obstante si pretende complementar los métodos de estos.

Con la planificaron se infiere una lista con las estructuras necesarias(1) y con las prohibidas (2) las cuales ayudaran, mas tarde a limitar las estructuras proporcionadas por el generador .

(1) Lista correcta (2) Lista incorrecta

Ejemplo de regla:

R1: Si hay dos picos de las unidades de masa X1 y X2, de modo que
X1 + X2 = M + 28
X1 – 28 es un pico alto
X2 – 28 es un pico alto
Al menos, o X1 es alto o X2 es alto
Entonces CETONA

R2: Si se satisface las condiciones para ser una CETONA
43 es un pico alto
58 es un pico alto
M – 43 es un pico bajo
M – 15 es bajo o, posiblemente 0
Entonces METIL-CETONA.

Encadenando hacia delante si se aplica la regla R1 el PLANIFICADOR puede considerar aquellas reglas que tenga en sus condiciones el grupo CETONA.

R3: Si es CETONA y …… Entonces ETIL-CETONA.

O sea encadena con las reglas R2 y R3 de acuerdo con su espectro de masa y la correcta la incluye en la lista correcta y la otra en la lista incorrecta. Lo cual permite al planificador determinar la posición de un grupo funcional y registrar la información adicional para que sea utilizada mas tarde por el generador.

Generador de estructura: es un programa que genera el espacio de búsqueda con las posibles estructuras químicas.