Material De Apoyo. Unidades 7, 8 Y 9

ING. GERSSON FANEITE. INTRODUCCIÓN A LA INTELIGENCIA ARTIFICIAL Y LOS SISTEMAS EXPERTOS 

INTRODUCCIÓN



OBJETIVOS



METODOLOGÍA



MÓDULO I. INTRODUCCIÓN A LA INTELIGENCIA ARTIFICIAL.









•

UNIDAD I: AGENTES DE ESTÍMULO - RESPUESTA.

•

UNIDAD II: REDES. INTRODUCCION A LAS REDES NEURONALES.

MÓDULO II: BÚSQUEDA EN ESPACIO DE ESTADOS. •

UNIDAD III: BÚSQUEDA A CIEGAS.

•

UNIDAD IV: BÚSQUEDA HEURÍSTICA. ALGORITMO A

*

MÓDULO III: REPRESENTACIÓN DEL CONOCIMIENTO. •

UNIDAD V: CÁLCULO PROPOCICIONAL Y CÁLCULO DE PREDICADOS.

•

UNIDAD VI: SISTEMAS BASADOS EN EL CONOCIMIENTO.

MÓDULO IV: REPRESENTACIÓN DEL RAZONAMIENTO. •

UNIDAD VII: REPRESENTACIÓN DEL SENTIDO COMÚN.

•

UNIDAD VIII: RAZONAMIENTO CON INCERTIDUMBRE.

MÓDULO V: SISTEMAS EXPERTOS. •

UNIDAD IX: DESARROLLO DE UN SISTEMA EXPERTO.

MÓDULO IV REPRESENTACIÓN DEL SENTIDO COMÚN Se puede decir que en el campo de la Inteligencia Artificial el conocimiento que se tiene sobre algo es en general difícil de conceptualizar formalmente, se ha intentado dotar de sentido común a las maquinas. Algunos hechos como el fuego quema son sencillos de comprender desde nuestro punto de vista, pero podrían ser difíciles de representar formalmente. En las redes semánticas se utiliza el razonamiento basado en herencia lo cual tiene relación con la herencia de clases, terminología utilizada en los lenguajes orientados a objetos. En esta unidad se hará un intento por representar el sentido común, particularmente se utilizarán dos tipos de representación del conocimiento: las Redes Semánticas y los Guiones o Frames. UNIDAD VII: REDES SEMÁNTICAS. Una red semántica es una estructura que se utiliza para representar el conocimiento sobre algo en particular. Se representa como un grafo dirigido, constituido por:

1

 

nodos: representan conceptos (un objeto individual o una clase de objetos) arcos: representan relaciones binarias entre los conceptos.

A través de ellas se puede hacer inferencia gracias a la herencia de propiedades, es decir; los elementos de una clase (subclase) heredan los atributos de una clase más general (superclase) en la que están incluidos. Ejemplo 4.1. (Representación de un conocimiento empleando una Red Semántica - Extractos tomados de las diapositivas: Inteligencia Artificial /Departamento de Sistemas Informáticos y Computación/Facultad de Informática/ UPV) En la figura 24 se presenta una red semántica, en ella (y en las siguientes figuras) se destaca la facilidad de presentación, el razonamiento y las relaciones de pertenencia. Es importante aclarar que esta representación considera sólo una parte de nuestro sistema cardiovascular.

Figura 24: Red Semántica. Fragmento del Sistema Cardiovascular

2

Figura 25: Red Semántica. Reemplaza el uso de la relación “es un” para enfatizar subclases e instancias

Figura 26: Ejemplos. Herencia de una Red Semántica

3

Figura 27: Ejemplo. Excepciones de la Herencia

Redes Semánticas Extendidas. Las Redes Semánticas Extendidas (A. Deliyanni y R. A. Kowalski): formalismo de representación alternativo a la forma clausal de la lógica con la restricción de solo poder utilizar símbolos de predicado binarios. Debido a la equivalencia sintáctica entre redes semánticas extendidas y la forma clausal de la lógica, las reglas de inferencia definidas para la forma clausal de la lógica pueden ser aplicadas para manipular arcos y nodos de una red semántica extendida. Un predicado binario puede ser traducido en una red en la que:  

los nodos representan términos el arco representa la relación (predicado) Pared (Arteria, Muscular)

La restricción a símbolos de predicado binarios no es crítica, ya que cualquier átomo que contenga un símbolo de predicado n-ario puede ser reemplazado por una conjunción de átomos que contengan solo símbolos de predicado binarios. Si n > 2 se requieren n +1 nuevos predicados. Si n = 1, solo se requiere un nuevo predicado. Ejemplo 4.2. PresiónSangre(x, y, z) = “la presión sanguínea de “x” varía entre “y” mmHg y “z” mmHg” El predicado PresiónSangre (arteria, 40, 80) Puede ser reemplazado por la conjunción de predicados binarios: Instancia_de(Presión1, PresiónSangre) 4

Sujeto(presión1, arteria) LímiteInferior(presión1, 40) LímiteSuperior(presión1, 80) Red semántica equivalente:

Ejemplo 4.3. Traducción predicado unario a binario. Supongamos el siguiente predicado unario: Arteria(x) = “x es una arteria” y las cláusulas: Arteria(aorta) y Arteria(arteria-grande) Estas cláusulas pueden ser reemplazadas por las cláusulas: Instancia_de(aorta, arteria) Subclase_de(arteria-grande, arteria)

TAREA: Representar mediante redes semánticas y escriba las expresiones lógicas de la siguiente información:     

Una persona tiene dos brazos y dos piernas. Las personas pueden ser hombres y mujeres. Un jugador de baloncesto es un hombre. Michael Jordan es un jugador de baloncesto y juega de escolta. Shaquille O’Neil es un jugador de baloncesto y juega de pívot. 5

     

La media de puntos de un escolta es 20. La media de puntos de Michael Jordan es 20. La media de puntos de un pívot es 20. El peso de un jugador de baloncesto es 120 kilos Michael Jordan pertenece al equipo de los Bulls. Shaquille O’Neil pertenece al equipo de los Lakers.

GUIONES, MARCOS O FRAMES. El guion o frame se emplea para representar el conocimiento sobre un tema concreto, se concibe conformado por varios campos o ranuras (slots) y los valores que introducimos en ellos son los rellenos. 









El conocimiento relevante de un concepto (objeto individual o clase de objetos) es representado mediante entidad compleja de representación llamada frame, constituida por un conjunto de propiedades (atributos) Las frame proporcionan un formalismo para agrupar explícitamente todo el conocimiento concerniente a las propiedades de objetos individuales o clases de objetos. Tipos de frames:  frames clase, o frames genéricas, que representan conocimiento de clases de objetos.  frames instancia, representan conocimiento de objetos individuales. El conocimiento de un dominio de interés es organizado jerárquicamente en una taxonomía de frames. La taxonomía es representada mediante un grafo dirigido acíclico (generalmente un árbol) en el que solo se dan las relaciones:  instancia-de  subclase-de donde cada nodo denota una frame.

  



Cada frame de una taxonomía tiene un nombre único. Una frame solo puede tener una superclase (herencia simple). La información (propiedades) específica al concepto representado por una frame es representada mediante atributos o slots Los atributos ofrecen un medio de representar las propiedades de objetos individuales o clases de objetos. 6

Ejemplo 4.4.



La información especificada en las partes atributo de las frames instancia sigue las siguientes reglas:  todos los atributos que ocurren en las instancias de una frame clase deben haber sido

declarados en dicha frame clase o en una de sus generalizaciones.  los valores asignados a los atributos de la instancia deben ser del tipo de datos definido en alguna de sus generalizaciones. Ejemplo 4.5. 

En la declaración de una frame clase también se puede asignar valor a un atributo (están permitidos los pares atributo valor)

“se considera adecuado especificar el valor rica-oxigeno del atributo sangre en la especificación de la clase, con lo que no es necesario especificarlo en sus subclases o instancias, ya que está propiedad será heredada por todos los descendientes de la clase” Ejemplo 4.6. (Equivalencia Frames vs Redes Semánticas)

7



El símbolo “nil” denota que una frame es la raíz de la taxonomía.

Ejemplo 4.7. (Redes Semánticas. Elementos de la Representación en Prolog)

Representación: Relaciones entre clases: es_un(persona, inicio). es_un(alumno, persona). es_un(profesor, persona). Relaciones entre instancias y clases: inst(juan, alumno). inst(luis, alumno). inst(pablo, profesor). inst(pedro, profesor). 8

Propiedades de clases: prop(persona, ciudad, sevilla). prop(alumno, estado, soltero). prop(profesor, estado, casado). Propiedades de instancias: prop(juan,edad,19). prop(luis,edad,24). prop(luis, estado, casado). prop(pablo,edad,44). prop(pablo, ciudad, mairena). prop(pedro,edad,47). Razonamiento: 

Sesión ?- propiedades_rs(luis, P). P = [ciudad:sevilla, edad:24, estado:casado]



Definición

propiedades_rs(Inst, Props) :props(Inst, P_Especificas), inst(Inst, Clase), herencia_rs(Clase, P_Especificas,Props). props(X, Props) :findall(Atr:Valor, prop(X, Atr, Valor), Props). herencia_rs(inicio, Props, Props). herencia_rs(Clase, P_Actuales, Props) :props(Clase, P_Generales), actualiza(P_Actuales, P_Generales, N_P_Actuales), es_un(Clase, Super_clase), herencia_rs(Super_clase, N_P_Actuales, Props). actualiza(Props,[],Props). actualiza(P_Actuales, [Atr:_Valor[P_Generales], Props) :member(Atr:_V,P_Actuales), actualiza(P_Actuales, P_Generales, Props). actualiza(P_Actuales,[Atr:Valor|P_Generales], [Atr:Valor|Props]) :not(member(Atr:_V, P_Actuales)), actualiza(P_Actuales, P_Generales, Props). Elementos de la representación:   

Las instancias se representan por constantes Las clases se representan por constantes Las relaciones clase–superclase se representan por hechos de la forma: es un(,<super-clase>) 9

   

Las relaciones instancia–clases se representan por hechos de la forma: inst(,) Cada propiedad se representa por un predicado binario de la forma: prop(,<propiedad>,valor>) La constante inicio representa la clase inicial de la jerarquía Las propiedades de una instancia es una lista de pares atributo–valor

Razonamiento sobre clases, p.e. “¿Cuáles son las subclases de persona” ?- es_un(X, persona). X = alumno ; X = profesor ; No Ejemplo 4.8. (Guiones, Marcos o Frames. Elementos de la Representación en Prolog)

Representación: Clases: clase(persona,inicio, [ciudad:sevilla]). clase(alumno, persona, [estado:soltero]). clase(profesor, persona, [estado:casado]). Instancias: instancia(juan, alumno, [edad:19]). instancia(luis, alumno, [edad:24,estado:casado]). instancia(pablo, profesor, [edad:44,ciudad:mairena]). instancia(pedro, profesor, [edad:47]).

10

Razonamiento: 



Sesión ?- propiedades_marco(luis, P). P = [ciudad:sevilla, edad:24, estado:casado] Definición: propiedades_marco(Inst, Props) :instancia(Inst, Clase, PropsInst), herencia_marco(Clase, PropsInst, Props). herencia_marco(inicio, Props, Props). herencia_marco(Clase, P_Actuales, Props) :clase(Clase, Super_clase, P_Generales), actualiza(P_Actuales, P_Generales, N_P_Actuales), herencia_marco(Super_clase, N_P_Actuales, Props).

Elementos de la representación.    

 

Las instancias se representan por constantes Las clases se representan por constantes Cada propiedad se representa por una igualdad de la forma: : Las relaciones clase–superclase se representan por hechos de la forma: clase(,<supclase>,[<prop-1>,..,<prop-n>])Las relaciones instancia–clase se representan por hechos de la forma: instancia(,<sup-clase>,[<prop-1>,..,<prop-n>]) La constante inicio representa la clase inicial de la jerarquía Las propiedades de una instancia es una lista de pares atributo–valor

Razonamiento sobre clases, p.e. “¿Cuáles son las subclases de persona?” ?- es_un(X, persona, _). X = alumno ; X = profesor ; No TAREA: Representa mediante una estructura de Frames la siguiente información acerca de la organización de un Congreso: 

 



En dicho Congreso se debe poder almacenar información acerca de las presentaciones que se van a realizar que serán bien artículos aceptados, conferencias invitadas o posters. De cada una de estas presentaciones se desea conocer su título, numero de referencia, autor/es, su lista de descriptores y si está confirmada su presentación en el Congreso. Se desea también almacenar información de los diferentes autores con datos como nombre, apellidos, universidad o centro donde trabajan y número de artículos presentados. Por otro lado se debe mantener una lista de las personas inscritas, indicando su nombre, cantidad abonada, número de tarjeta de crédito y si es estudiante o no. En el caso de ser estudiante se deberá guardar información acerca de la universidad donde está estudiando. Se quiere disponer de una estructura que refleje las sesiones del Congreso por días. El Congreso dura 3 días (Miércoles, Jueves y Viernes) y hay 3 sesiones diarias (MAÑANA1, MAÑANA2 y 11

TARDE1) donde en cada sesión puede haber o bien 3 artículos o 1 conferencia invitada o un número indeterminado de posters (no puede haber mezclas de presentaciones diferentes) Cada uno de los descriptores del Congreso debe asociarse a una descripción del mismo que explique el significado del descriptor. UNIDAD VIII: AGENTES QUE RAZONAN BAJO INCERTIDUMBRE. Incertidumbre. 





En muchas aplicaciones en el “mundo real” existe incertidumbre, por ejemplo:  Un sistema de diagnóstico médico no cuenta con toda la información del paciente.  Un robot tiene sensores con limitaciones y ruidosos.  Un agente financiero tiene información limitada de las empresas y no puede conocer todos los factores que las afectan. Un sistema inteligente debe poder tomar decisiones aunque no tenga toda la información o conocimiento necesarios, e incluso cuando existan errores en la información que recibe o en su conocimiento. Ejemplos de dominios con incertidumbre:  Diagnóstico médico o industrial  Predicción financiera  Exploración minera / petrolera  Interpretación de imágenes (visión)  Reconocimiento de voz  Monitoreo / control de procesos industriales complejos  Robótica

Los sistemas inteligentes deben ser capaces de representar y razonar con incertidumbre. Existen varias causas de incertidumbre que tienen que ver con la información, el conocimiento y la representación: Información:  Incompleta  Poco confiable  Ruido, distorsión Conocimiento:  Impreciso  Contradictorio Representación:  No adecuada  Falta de poder descriptivo Se han desarrollado diversas técnicas para manejo de incertidumbre en sistemas inteligentes. En el caso que nos ocupa emplearemos una técnica probabilística conocida como Redes Bayesianas, para ellos se hace necesario repasar algunos conceptos ya vistos en cursos anteriores. ¿Qué es probabilidad?

12

Dado un experimento E y el espacio de muestreo S, a cada evento A le asociamos un número real P(A), el cual es la probabilidad de A y satisface los siguientes axiomas .

Axioms:   

0 <= P(A) <= 1 P(S) = 1 P(A ∪ B ∪ C … ) = P(A) + P(B) + P(C) + … A, B, C … mutuamente exclusivos.

Teoremas:   

P (0) = 0 P (¬A) = 1 – P(A) P(A ∪ B) = P(A) + P(B) – P(A ∩ B)

Probabilidad Condicional: P(A | B) = P(A ∩ B) / P(B) 

Probabilidad de que ocurra un evento dado que ocurrió otro:  Dado que el dado cayó par, cuál es probabilidad de que sea un número primo?  Dado que tiene catarro, cuál es la probabilidad de que tenga gripe?

Una forma de representar la probabilidad condicional se puede ver en el siguiente ejemplo: Supongamos que tomamos una muestra al azar de 100 estudiantes y obtenemos los siguientes resultados: 15 mujeres reciben ayuda económica y trabajan 45 mujeres reciben ayuda económica 20 mujeres trabajan 55 de los estudiantes son mujeres 25 estudiantes reciben ayuda económica y trabajan 60 estudiantes reciben ayuda económica 40 estudiantes trabajan Se puede traducir estos datos en porcentajes y representar en un Diagrama de Venn, como se muestra en la Figura 28.

Figura 28: Diagrama de Venn que representa el resultado de una encuesta a 100 estudiantes

13

El conjunto M representa todas las mujeres en la muestra, A el conjunto que representa los estudiantes que reciben ayuda económica y T el conjunto de estudiantes en la muestra que trabajan. Nos proponemos seleccionar al azar una persona de estos 100 estudiantes en la muestra. Entonces podemos hablar acerca de la probabilidad que la persona seleccionada es una mujer, por ejemplo. Sin temor a confundirnos, usaremos los nombres A, T y M para denotar el evento que la persona seleccionada recibe ayuda humanitaria, trabaja o es una mujer, respectivamente. Entonces tenemos: P(M) = 0,30 + 0,05 + 0,05 + 0,15 = 0,55 De este diagrama podemos contestar preguntas que a primera vista parecen complicadas, tal como: ¿Qué proporción de estudiantes son mujeres que no trabajan y reciben ayuda económica? Esta pregunta es equivalente a encontrar P(M y A y no T). La solución 0,30 se encuentra en la intersección de los tres conjuntos M, no T, A. La probabilidad se ve en situaciones donde queremos saber, por ejemplo, ¿Qué proporción de estudiantes que trabajan son mujeres?. Esto equivale a encontrar P(M | T). La proporción de estudiantes que trabajan es 0,40, la proporción de mujeres que trabajan es 0,20. De esta manera la proporción de mujeres de entre los estudiantes que trabajan, es 0,20 / 0,40 = 0,50, es decir, la mitad de los estudiantes que trabajan son mujeres. Igual a las ideas desarrolladas previamente podemos escribir la solución como: P(M | T) = P(M y T) / P(T) = 0,20 / 0,40 = 0,50. Regla de Bayes: 

De la definición de probabilidad condicional se puede deducir: P(B | A) = P(B) P(A | B) / P(A), dado P(A) > 0



Esto permite “invertir” las probabilidades, por ejemplo obtener la P de una enfermedad dado un síntoma, con conocimiento de la P de los síntomas dado que alguien tiene cierta enfermedad.

Ejemplo 4.7. Un médico pediatra sabe que la enfermedad rubeola, se manifiesta además de fiebre y erupción cutánea en el niño, con inflamación de los ganglios del cuello y de la ingle, este último síntoma ocurre en el 60% de los casos. Por otra parte se conocen algunos hechos basados en datos estadísticos, entre ellos la probabilidad a priori de que un paciente tenga rubeola es 1 / 25.000 y la probabilidad a priori de que un paciente tenga los ganglios inflamados es de 1 / 15. Sea: r : el niño tiene rubeola. g : el niño tiene los ganglios inflamados. Las probabilidades son: P(g | r) = 0,60 P(r) = 1 / 25.000 P(g) = 1 / 15 P(r | g) = P(r) P(g | r) / P(g) = (1 / 25.000 x 0,60) / (1 / 15) = 0,00036 Esto significa que 9 de 25.000 niños realmente tienen rubeola. 14

Probabilidad Total: Dada una partición, B, de S, la probabilidad de un evento A se puede obtener como: P(A) = Σ P(A | Bi )P(Bi)

Teorema de Bayes: Con la definición de probabilidad total, el teorema de Bayes se puede escribir como: P(B | A) = P(B) P(A | B) / Σ P(A | Bi ) P(Bi) Ejemplo 4.8. Supongamos que unas bolas coloreadas se colocan en tres cajas. C1, C2 y C3, del siguiente modo: C1 C2 C3 ROJA

2

4

3

BLANCA

3

2

4

AZUL

6

3

3

Si se selecciona una bola cualquiera de las tres cajas, responda las siguientes preguntas: a.

¿Cuál es la probabilidad que la bola seleccionada sea roja?

b. Si la bola seleccionada resultó ser roja, ¿cuál es la probabilidad que provenga de la caja uno?

Solución a: Dada una partición, Ci (i = 1.2 y 3) de S, la P(Roja) se obtiene como la probabilidad total, es decir; P(Roja) = Σ P(Roja | Bi )P(Ci): P(Roja) = P(Roja | C1 )P(C1) + P(Roja | C2 )P(C2) + P(Roja | C3 )P(C3) P(Roja) = 1 / 3(2 / 11 + 4 / 9 + 3 / 10) = 1 / 3 x 917 / 990 = 0,3088 Solución b: Previamente ocurrió el evento, “la bola es roja”, luego aplicando el Teorema de Bayes tenemos: P(C1 | Roja) = P(C1) P(Roja | C1) / P(Roja) = (1 / 3 x 2 / 11) / (1 / 3 x 917 / 990 ) = 0,1963 Eventos independientes: 

Dos eventos son independientes si la ocurrencia de uno no altera la probabilidad de ocurrencia del otro: P(A | B) = P(A) ó P(B | A) = P(B)



Lo que es equivalente a: 15

P(A ∩ B) = P(A) P(B) 

Independientes ≠ mutuamente exclusivos

Independencia condicional: 

A es condicionalmente independiente de B dado C, si el conocer C hace que A y B sean independientes: P(A | B,C) = P(A | C)



Ejemplo:  A – regar el jardín  B – predicción del clima  C – lluvia

Regla de la Cadena: De la definición de probabilidad condicional, se puede evaluar la probabilidad de A1 ∩ A2 ∩ A3 ... ∩ An (probabilidad conjunta) como: P(A1, A2, ..., An ) = P(A1 | A2, ..., An ) P(A2 | A3, ..., AN ) ... P(An ) REDES BAYESIANAS (RB). (Extractos tomados de L. Sucar (INAOE). Tecnología de la Información - UPAEP) También llamadas Redes de creencia, Redes probabilísticas o Redes causales. Es una Estructura de datos para representación de que muestra el conocimiento incierto. Representa la dependencia entre variables y especifica en forma concisa la distribución de probabilidad conjunta. Cada nodo de la red representa una variable aleatoria. Un arco del nodo X al nodo Y, significa que la variable X tiene una influencia sobre Y. Cada nodo X tiene una tabla de probabilidad condicional que cuantifica el efecto que los padres de X tienen sobre X. Es un grafo dirigido acíclico (GDA). Ejemplo 4.9. – Probabilidad Condicional en RB.

Tipos de Estructura: Grafos conexos y poliárboles. 

Grafo conexo: entre cualquier par de nodos hay al menos un camino (una ruta no dirigida). A veces se distingue entre camino abierto y cerrado, que corresponde a ciclos y bucles). 16

  

Grafo simplemente conexo o poliárbol: entre cualquier par de nodos hay un único camino. Grafo múltiplemente conexo: contiene bucles o ciclos. Árbol: poliárbol en el que cada nodo tiene un solo padre, menos el nodo raíz que no tiene.

Probabilidades conjuntas en una RB. Una RB proporciona una descripción completa del dominio. Cualquier elemento de P(X1,..Xn) se puede calcular a partir de la red:

P(x ,..,x ) P(xi | Padres(xi )) Ejemplo - Probabilidades conjuntas. Se tiene un nuevo sistema de alarma antirrobo instalado en casa. Este sistema es bastante fiable en detectar un allanamiento de morada, pero también se activa a veces con el más pequeño terremoto. También se tienen dos vecinos Juan y María, que han prometido llamar al dueño a su lugar de trabajo si oyen la alarma. Las llamadas de Juan cuando oye la alarma son absolutamente fiables, pero a veces Juan confunde la alarma con el teléfono e igualmente llama. Por otro lado, María le gusta la música ruidosa, y algunas veces se olvida de la alarma. A continuación la RB:

 

Calcular la Probabilidad de que la Alarma suene, no haya Robo ni Terremoto, Juan y María llamen. P(A,¬R, ¬T,J,M) ? 17

 

Utilizando la expresión para probabilidad conjunta P(x ,..,x ) P(xi | Padres(xi )), tenemos: P(A| ¬R, ¬T)P(¬ R) P(¬T) P(J|A)P(M|A) = 0.90 x 0.70 x 0.001 x 0.999 x 0.998=0.00062 P(R|J,¬ M,T) ?

Construcción.    

P(x1,...,xn) = P(xn|xn-1,...,x1)P(xn-1,...,x1) P(x1,...,xn) = P(xn|xn-1,...,x1)P(xn-1|xn-2,...,x1)…P(x2|x1)P(x1) P(Xi | Xi-1,...,X1) = P(Xi | Padres(Xi)), si Padres(Xi) ⊆ { xi-1,...,x1} Para satisfacer esa condición, entonces debe etiquetar los nodos de forma consistente con el orden parcial implícito en la RB.

Metodología de Construcción. Escoger conjunto de variables. Definir un orden parcial para el conjunto de variables; primero los nodos causales y luego los nodos efecto. 3. Mientras queden variables a. Escoger siguiente variable Xi y añadir nodo a la RB. b. Asigne Padres(Xi) a un conjunto mínimo de nodos presente en la red, de manera que sea satisfecha la propiedad de independencia condicional. c. Elaborar la tabla de probabilidad condicional de Xi 1. 2.

Este método garantiza la obtención de redes acíclicas, evita la redundancia en la definición de probabilidades. Evita que se violen los axiomas de probabilidad.

Propiedades de independencia condicional. 





Una RB es representación correcta del dominio si cada nodo es condicionalmente independiente respecto de antepasados de sus padres, entonces se debe escoger a los padres de manera que se satisfaga la condición anterior. En el ejemplo, no hay relación directa entre el hecho de que María o Juan llamen y el que se produzca un terremoto o un robo, relación mediada por el hecho de que suene la alarma, luego:  P(M | J,A,T,R) = P(M | A)  P(J | J,A,T,R) = P(J | A) Una RB es más compacta que la distribución de probabilidad conjunta correspondiente, esto permite manejar muchas evidencias sin el problema del crecimiento exponencial. 18

 

Sistema localmente estructurado (sparse system), el crecimiento es lineal (en vez de exponencial). Si las variables de una RB reciben influencias directas de un promedio de k variables, y hay un total de N variables booleanas, entonces la RB queda especificada por N⋅2k probabilidades.

Inferencia probabilística. En RB, la inferencia probabilística consiste en: “dadas ciertas variables conocidas (evidencia), calcular la probabilidad posterior de las demás variables (desconocidas)”. Es decir, calcular: P(Xi | E), donde:  

E es un subconjunto de variables de la RB (posiblemente vacío). Xi es cualquier variable en la RB, no en E.

Tipos de Inferencia.      

Usando el ejemplo de la alarma. Modelo diagnóstico: efectos (síntomas) causas (diagnóstico).  P(R|J), P(R|J,M) Modelo causal: Causas efectos.  P(J|R), P(M,R) Inferencias intercausales: entre las causas de un efecto común.  P(R|A,T) Inferencias mixtas: combinación de las anteriores  P(A|J,¬T), P(R|J,¬T) Además de estimar la probabilidad de cierto eventos (la variable de consulta), las RB permiten:  Estimar que variables de evidencia hay que observar para obtener información útil.  Hacer análisis de sensibilidad: determinar que variables tienen más peso en las probabilidades de las variables consultadas.  Explicar al usuario los resultados de una inferencia probabilista.

Evidencia total vs parcial.  



 

Evidencia dura (hard). Conocimiento determinista: P(A)=1 ó P(A)=0. Al asignar evidencia dura al nodo, se le llama instanciación. Evidencia parcial (soft). Conocimiento probabilístico (distinto a 0 y a 1). Incluye a las probabilidades priori y a las actualizadas tras instanciarse alguna variable.

Sin ninguna información adicional L y R son dependientes  Evidencia 1: T  R y L son independientes dado T La evidencia puede ser transmitida a través de un nodo lineal a menos que esté instanciado. En un nodo lineal T los nodos vecinos son condicionalmente independientes respecto a T, es decir, son dependientes si T no está instanciado y viceversa.

19



 



 

Sin ninguna información adicional J y M son dependientes.  Evidencia 1: ¬H  J y M son independientes dado ¬H La evidencia puede ser transmitida a través de un nodo divergente a menos que esté instanciado En un nodo divergente H sus hijos son condicionalmente independientes respecto a H, es decir, son dependientes si H no está instanciado y viceversa.

Sin ninguna información adicional L y A son independientes  Evidencia 1: H  L y A son dependientes dado H La evidencia puede ser transmitida a través de un nodo convergente si no está instanciado. En un nodo convergente H no instanciado, sus padres son independientes, pero son condicionalmente dependientes dado H.

Resumen de las propiedades de independencia condicional. Independencia a priori de los nodos que no tienen ningún antepasado común. 2. Independencia condicional de los nodos hermanos con respecto a su padre. 3. Independencia condicional entre un nodo y los antepasados de sus padres. 4. Dependencias condicionales por descendientes comunes instanciados. 1.

20

Hemos visto como una RB expresa la independencia entre un nodo y sus antepasados. ¿Es posible saber si un conjunto de nodos X es independiente de otro conjunto Y con base en el conjunto de los nodos de evidencia E? Método General. Mediante el empleo del teorema de factorización:

Ejemplo 4.10. (Independencias, distribuciones condicionadas y distribución conjunta) En un sistema de diagnóstico médico, supongamos que tenemos la siguiente información:    

Metástasis (M) causa tumor cerebral (T) e incremento en los niveles de calcio (I). Tumor cerebral causa coma (C). Incremento en nivel de calcio causa coma. Tumor cerebral causa fuertes jaquecas (J)

Representamos dicha información en una siguiente red bayesiana:

¿Qué independencias implica la red?    

I es independiente de T, J dado M. Así por ejemplo dado metástasis, el incremento de calcio no depende de si hay o no tumor cerebral. T independiente de I dado M. C independiente de M, J dados {T, I}. J independiente M, I, C dado T.

Según el teorema de factorización, los únicos datos que debemos pedir al experto son: P(m1) = 0.2 P(i1/m1) = 0.8 P(i1/m2) = 0.2 P(t1/m1) = 0.2 P(t1/m2) = 0.05 P(c1/i1,t1) = 0.8 P(c1/i1,t2) = 0.9 P(c1/i2,t1) = 0.7 21

P(c1/i2,t2) = 0.05 P(j1/t1) = 0.8 P(j1/t2) = 0.6 Y a partir de estas probabilidades podríamos construir la distribución conjunta. Por ejemplo: P(m1,i2,t1,j2,e2) = P(m1)·P(i2/m1)·P(t1/m1)·P(c2/i2,t1)·P(j2/t1) = 0.2 ·0.2·0.2·0.3·0.2 = 0,00048. Con la distribución conjunta P así construida tenemos una red causal que representa a la perfección la noción humana de causalidad. Una vez obtenida la distribución conjunta, podemos a partir de ella obtener la distribución de probabilidad que queramos. Por ejemplo, si queremos saber P(M/C,J):

Como vemos, una vez conocida la distribución conjunta es posible conocerla distribución de cualquier conjunto de variables, condicionadas o no condicionadas. Ejemplo 4.11. (Independencias, distribuciones condicionadas y distribución conjunta) Supongamos que hay dos eventos los cuales pueden causar que la hierba esté húmeda: que el rociador esté activado o que esté lloviendo. También supongamos que la lluvia tiene un efecto directo sobre el uso del rociador (usualmente cuando llueve el rociador se encuentra apagado). Entonces la situación puede ser modelada con una red Bayesiana (como hemos visto). Las tres variables tienen dos posibles valores, T (para verdadero) y F (para falso). La función de probabilidad conjunta es:

donde los nombres de las variables han sido abreviados a G = Hierba húmeda, S = Rociador activado, y R = Lloviendo. El modelo puede responder preguntas como "¿Cuál es la probabilidad de que esté lloviendo dado que la hierba está húmeda?" usando la fórmula de probabilidad condicional y sumando sobre todas las variables incordias:

22

Como está señalado explícitamente en el numerador del ejemplo, la función de probabilidad conjunta es usada para calcular cada iteración de la función de sumatoria, marginalizando sobre S en el numerador y sobre S y R en el denominador. Si, por otra parte, deseamos responder una pregunta intermedia: "¿Cuál es la probabilidad de que llueva dado que la hierba está húmeda?" la respuesta puede ser dada por la post-intervención de la función de distribución conjunta P(S, R | do(G = T)) = P(S | R) P(R) obtenida eliminando el factor P(G | S, R) de la distribución de pre-intervención. Como era de esperarse, la probabilidad de que llueva no es afectada por la acción: P(R | do(G = T)) = P(R). Si por otra parte queremos predecir el impacto que tendrá encender el rociador, tenemos entonces P(R, G | do(S = T)) = P(R) P(G | R, S = T) con el término P(S = T) | R) eliminado, mostrando que la acción tiene efecto sobre la hierba pero no sobre la lluvia. Ejemplo a.12. Problema del Paludismo.

23

TAREA:

24

MÓDULO V SISTEMAS EXPERTOS UNIDAD IX: DESARROLLO DE UN SISTEMA EXPERTO. Sistema Experto: Sistema informático que simula a los expertos humanos en un área específica dada. Debería ser capaz de: ➢ Procesar y memorizar información ➢ Aprender y razonar en determinadas situaciones ➢ Comunicación con el experto u otros sistemas ➢ Toma de decisiones ➢ ... Aplicaciones: ➢ Meteorología. ➢ Transacciones bancarias. ➢ Control de tráfico en una ciudad. ➢ Diagnóstico médico. ➢ Enfoque automático de imágenes fotográficas. ➢ Diagnóstico de problemas en automóviles. ➢ Interfaces de ordenador en lenguaje hablado. ➢ Gestión distribuida de redes de ordenador. ➢ Urbanismo y Gestión del territorio. ➢ Administración local. ➢ Navegación terrestre y marítima.

25

Definiciones: Base de Conocimiento Conocimientos del experto humano codificado (estático). Base de Hechos Memoria temporal de trabajo (dinámico). Motor de Inferencia Combina BC y BH para deducir nuevos hechos => resolver problema. Interfaz de Usuario Comunicación entre el SE y el usuario final. Módulo de Explicación Justificación y explicación de los resultados obtenidos. Módulo de Adquisición de Conocimiento Añadir nuevo conocimiento a la BC. Módulo de Aprendizaje Aprender a partir de la resolución de problemas.

Algo de historia. 

Mediados de los sesenta (IA): Alan Newell y Herbert Simon desarrollan GPS (General Problem Solver).



Centrarse en áreas de conocimientos muy concretos => surgen los SE.



DENDRAL (Ledeberg y Feigenbaum): considerado el primer SE (1967), deducía estructuras químicas a partir de su análisis espectográfico.



MYCIN (Univ. Stanford): diagnóstico de enfermedades infecciosas (1970-80). Separa la base de conocimiento del motor de inferencia. IF the infection is pimary-bacteremia AND the site of the culture is one of the sterile sites AND the suspected portal of entry is the gastrointestinal tract THEN there is suggestive evidence (0.7) that infection is bacteroid.



MYCIN da lugar a otros sistemas expertos como:

26

➢ EMYCIN : contiene el sistema de manejo de la BC y la inferencia del MYCIN, para su uso en otros SE. ➢ SACON : generación de estructuras de ingeniería. ➢ PUFF : estudio médico de enfermedades pulmonares. ➢ GUIDON: elección de tratamientos terapeúticos. HEARSAY: identificación de la palabra hablada. PROSPECTOR: búsqueda de yacimientos minerales (Bayes). A partir de 1980 se “ponen de moda” y se extiende su uso en industrias y empresas. Tipos de sistemas expertos (según naturaleza del problema): ➢ Deterministas => el estado actual depende del estado anterior y las acciones sobre el entorno. Son los Sistemas Expertos basados en reglas, que usan un mecanismo de razonamiento lógico para sacar sus conclusiones. ➢ Estocásticos => sistemas en los que existe incertidumbre, por lo que necesita ser tratada. Son los Sistemas Expertos Probabilísticos y la estrategia de razonamiento usada es el razonamiento probabilístico. Pero... ¿Qué es exactamente la incertidumbre? Se define como la falta de certidumbre o certeza, siendo certeza el conocimiento seguro y claro de algo. ¿En qué situaciones se da incertidumbre? ➢ Cuando los hechos o datos pueden no ser conocidos con exactitud (por ej, un paciente puede no estar seguro de haber tenido fiebre la noche pasada) => subjetividad, imprecisión, errores, datos ausentes... ➢ Cuando el conocimiento no es determinista. Por ej, las relaciones entre enfermedades y síntomas; un mismo conjunto de síntomas puede estar asociado a varias enfermedades.

27

En los primeros Sistemas Expertos, se usaba la probabilidad para tratar la incertidumbre, pero al encontrarse algunos problemas por el uso incorrecto de algunas hipótesis, se desechó. Con la aparición de redes probabilísticas (Redes Bayesianas y Cadenas de Markov, principalmente) el uso de la probabilidad para el tratamiento de la incertidumbre ha vuelto a ser aceptado y hoy en día es la forma más usada. Sistemas Expertos basados en reglas. 

Una regla es una afirmación lógica que relaciona información conocida con otra que puede ser inferida o se sabe que es cierta.  Una regla se compone de la premisa y el consecuente. Premisa: condiciones para que la regla se ejecute. Consecuente: conclusiones deducidas. Ejemplo de regla: IF TarjetaNoValida THEN PagoNoAutorizado ELSE PagoAutorizado El Motor de Inferencia. La Inferencia permite deducir nuevo conocimiento a partir de conocimiento que se sabe que es cierto. Usa la Base de Hechos y el Conocimiento Base para obtener nuevas conclusiones o hechos. Existen diferentes reglas de inferencia (Modus Ponens, Modus Tollens) y diferentes estrategias de inferencia (Encadenamiento de reglas hacia delante y hacia atrás).

Encaminamiento (de reglas) hacia delante ➢ Obtiene nuevos hechos a partir de la evaluación de reglas. ➢ Comienza insertando unos hechos iniciales en la BH. ➢ Se exploran las reglas de la BC y se añaden nuevos hechos a la BH. Termina cuando no se cumple ninguna regla. ➢ El objetivo es deducir todo el conocimiento posible.

28

Encaminamiento (de reglas) hacia atrás ➢ Deducir el conocimiento necesario para demostrar un hecho. ➢ Comienza fijando un hecho o meta a demostrar. ➢ Se busca la regla que contiene dicho hecho como consecuente y se demuestran los hechos del antecedente de la regla. ➢ El objetivo es demostrar una meta. Método de construcción de Sistemas Expertos (Dr. Ramón García Martínez) La idea de este método es observar al experto cuando lleva adelante tareas que usualmente ejecuta. Se debe documentar la información obtenida en estas observaciones para utilizarla en la profundización de áreas específicas del conocimiento del experto en posteriores sesiones. En esta observación el Ingeniero de Conocimiento debe establecer: [a] Las similitudes y diferencias establecidas por el experto de entre el problema en curso de solución y otros resueltos previamente. [b] Las diferencias de términos y categorías establecidas por el experto. [c] La habilidad puesta en juego por el experto para inferir nueva información y plantear nuevas hipótesis. Entrevistas   

La idea central de este método consiste en que el ingeniero de conocimiento identifique los módulos de conocimiento a partir del discurso del experto. Debe priorizarse el acceso al experto y minimizarse las interrupciones. Existen dos tipos de entrevistas:  no estructurada  estructurada.

Entrevista no estructurada  

La entrevista no estructurada consiste en hacer preguntas espontáneas al experto. Una técnica muy utilizada es hacer que el ingeniero de conocimiento se ponga en el lugar del novato y hacer preguntas sobre procedimientos, ideas sobreentendidas por el experto, tratando en todo momento que el experto piense en voz alta.

Entrevista estructurada  

La entrevista estructurada consiste en combinar la técnica de tareas familiares con entrevistas no estructuradas. Formular un protocolo de preguntas sobre áreas mal definidas o vacantes en los procesos de educción de conocimiento previamente realizados.

Tareas de procesamiento restringido La idea de este método consiste en recurrir a distintas técnicas para deliberadamente forzar al experto a que comprima o altere las estrategias de razonamiento.

29

Técnicas para tareas de procesamiento restringido    



Limitar la cantidad de tiempo que el experto tiene para absorber información. Limitar la cantidad de tiempo que el experto tiene para emitir juicios. Elaborar cuestionarios sobre puntos específicos del problema a resolver. Aplicar el método de tareas familiares simuladas que consiste en cuestionar al experto a partir de información de archivo. Aplicar al método de escenarios que consiste en forzar al experto a que establezca analogías entre casos similares. Aplicar el método de restricciones combinadas que puede ser descripto por el siguiente algoritmo: COMIENZO Tomar un caso de estudio. Tomar la información pertinente al diagnóstico de la solución. Recortar la Información. Suministrar la información resultante al experto de campo. Observar las diferencias entre el diagnóstico dado por el experto de campo y el diagnóstico dado en el caso de estudio. FIN

Tareas de información limitada La idea de este método consiste en explorar alternativas que en una primera recopilación de información no han sido suministradas por el experto; tomando cada tarea y profundizando sobre aspectos que al experto puedan parecerle más relevantes. Puede comenzarse con el método de tareas familiares para recopilar información y profundizar utilizando las técnicas de procesamiento restringido. Simulación del escenario hacia adelante  

En esta técnica el experto elige un escenario muy elemental y verbalmente “camina por entre” los razonamientos necesarios para llegar al objetivo. Esta técnica toma lugar en condiciones de laboratorio, no en el ambiente de trabajo del experto.

Esta técnica tiene por lo menos dos dificultades: La exploración a través del cuerpo de conocimiento durante el proceso de refinamiento del mismo involucra el manejo de términos y definiciones cuyos detalles pueden no haber sido claramente establecidos en la definición del dominio resultando en demoras y confusiones. 2. Se pueden confundir los métodos de razonamiento y los métodos del trabajo del experto. 1.

Descomposición de objetivos  

La descomposición de objetivos es el acercamiento al problema por la técnica de reducción tradicional y es útil para enumerar estados objetivos y describir categorías generales de objetivos. La técnica puede empezar con “Suponga que hay una X” pero colapsa en “Qué está impidiendo a X lograr su misión?”.

30

31

Problemas en bases de conocimiento. Según las reglas: Tipos de inconsistencias Según los componentes de las reglas: Problemas de integridad Tipos de inconsistencias     

Reglas redundantes Reglas conflictivas Reglas incluidas en otras Condiciones SI innecesarias Reglas cíclicas

Problemas de integridad    

Valores de atributo sin referencia Condiciones SI de punto muerto Objetivos de punto muerto Conclusiones inalcanzables

32



Reglas redundantes Dos reglas son redundantes si las precondiciones son equivalentes y una o más conclusiones son equivalentes. Este problema no causa problemas lógicos pero afecta a la eficiencia. Ejemplo: P(x) => Q(x) P(y) => Q(y) X e Y son variables y P y Q son predicados verificados por X e Y. P(x) => Q(x) P(x) => Q(y) ˆ T(y)



Reglas conflictivas Dos reglas son conflictivas si tienen equivalentes pre-condiciones y conclusiones contradictoras. Ejemplo: P(x) => Q(x) P(x) => ¬Q(x) ó P(x) => Q(x) P(y) => ¬Q(y) ˆ T(y)



Reglas incluidas en otras Una regla está incluida dentro de otra, si ambas tienen las mismas conclusiones y las precondiciones de una se satisfacen si las precondiciones de la otra se satisfacen. Ejemplo: P(x) => Q(x) P(x) ˆ T(y) => Q(x)



Condiciones si innecesarias Dos reglas presentan este problema cuando las conclusiones de ambas son equivalentes y una de las pre-condiciones en la primer regla es la negación de una de las pre-condiciones en la segunda regla, siendo el resto de las precondiciones equivalentes. Ejemplo: P(x) ˆ T(y) => Q(x) P(x) ˆ ¬T(y) => Q(x) Es evidente que Q(x) se deduce independientemente de la verdad o falsedad de T(x) por lo que la regla resultante será: P(x) => Q(x)

33



Reglas cíclicas Este problema se presenta cuando el encadenamiento lógico de un conjunto de reglas genera un ciclo. Ejemplo: P(x) => Q(x) Q(x) => R(x) R(x) => P(x)



Valores de atributo sin referencia Ocurre cuando se han definido valores en el dominio de un atributo o pre-condición que no son utilizados por ninguna regla. No involucra problemas lógicos pero es un problema para el mantenimiento de la Base de Conocimiento. Ejemplo: Una pre-condición numérica que fue definida como real y solo toma valores enteros.



Condiciones si de punto muerto Ocurre cuando en determinadas reglas encontramos condiciones que son inalcanzables por disparo de otras reglas. Ejemplo: Podemos tomar la siguiente Base de Conocimiento: P(x) => T(x) T(y) => Q(x) R(x) => Q(x) La precondición de la tercera regla R(X) no es disparada como conclusión por ninguna de las otras dos reglas.



Objetivos de punto muerto Ocurre cuando se plantea un objetivo que es inalcanzable por disparo de las reglas pertenecientes a la Base de Conocimiento. Ejemplo: Podemos tomar la siguiente Base de Conocimiento: P(x) => T(x) T(x) => Q(x) Para este ejemplo el objetivo R(x) sería de punto muerto pues no es disparado como conclusión por ninguna de las reglas.



Conclusiones inalcanzables Este tipo de conclusiones pertenecen a reglas con pre-condiciones que son de punto muerto. Ejemplo: Podemos tomar la siguiente Base de Conocimiento: P(x) => T(x)

34

T(x) => S(x) R(x) => Q(x) La pre-condición de la tercera regla R(X) no es disparada como conclusión por ninguna de las otras dos reglas, por lo que Q(x) se convierte en una conclusión inalcanzable. Criterios de evaluación de una base de conocimiento. Exactitud: Cuan bien el Sistema Experto refleja el comportamiento del experto humano. Adaptabilidad: Posibilidad de extender la experticia del Sistemas Experto en un desarrollo futuro. Envergadura: Cantidad de tareas que el sistema experto es capaz de llevar adelante. Normalmente está relacionado con la cantidad de reglas o con grupos de estas asociadas a tareas o problemas. Profundidad: Cantidad necesaria de restricciones a satisfacer para lograr la identificación de un problema o tarea. Generalidad: Capacidad de un Sistemas Experto de ser utilizado en un amplio rango de problemas. Validez: Capacidad de un Sistemas Experto de producir predicciones “empíricamente” correctas. Robustez: Capacidad del Sistemas Experto de determinar la relevancia de determinada información en orden a obtener sus objetivos. Disponibilidad: La posibilidad de poder construir un modelo más simple que con pocas restricciones exhiba un comportamiento similar al del Sistemas Experto.

35