Razonamiento aproximado. Fundamentos teóricos de la inteligencia artificial (página 2)

9 Redes bayesianas A principio de los años 80, Judea Pearl retoma el modelo probabilístico creando las redes bayesianas Este acontecimiento cambia completamente el escenario Modelo probabilista inspirado en la causalidad El modelo probabilístico tiene asociado un modelo gráfico, cuyos nodos representan variables y cuyos arcos representan mecanismos causales Extraordinario desarrollo experimentado por las redes bayesianas en las dos últimas décadas Se han construido modelos de diagnóstico y algoritmos eficientes para problemas con miles de variables Las universidades más importantes y las empresas punteras de informática tienen grupos de investigación dedicados a este tema

10 Características principales de las redes bayesianas

La incertidumbre se representa basándose en teoría de la probabilidad La información se estructura en variables y relaciones de influencia causal entre ellas Relaciones de independencia condicional Parámetros: probabilidades condicionadas de cada variable dados sus padres Inferencias de tipo abductivo y predictivo

11 Ejemplos de empresas que utilizan redes bayesianas: Microsoft (Windows 95/98, Office 97/2000) Digital, Hewlett Packard, diagnóstico de problemas de impresión IBM, Intel, Siemens Nokia

12 Lógica difusa Introducción Teoría de conjuntos difusos Teoría de conjuntos clásica (conjuntos nítidos) Conjuntos Difusos Funciones de pertenencia Etiquetas lingüísticas Operaciones elementales con conjuntos difusos Complementario Intersección Unión Razonamiento difuso Inferencia difusa Decodificación Funcionamiento de un sistema difuso Conclusiones

13 Necesidad de razonamiento difuso En el mundo real existe mucho conocimiento no perfecto, es decir, conocimiento vago, impreciso, incierto, ambiguo, inexacto, o probabilístico por naturaleza. El razonamiento y pensamiento humano frecuen-temente conlleva información de este tipo: inexactitud inherente de los conceptos humanos y razonamiento basado en experiencias similares, pero no idéntica Problema: Poca capacidad de expresión de la lógica clásica. Ejemplo 1. Clasificación de personas en altas o bajas Ejemplo 2. Definición del término joven

14 Origen y éxito de los difusos El origen del interés actual por la teoría de conjuntos difusos se debe a un artículo publicado por Lofti Zadeh en 1.965. En la actualidad es un campo de investigación muy importante, tanto por sus implicaciones matemáticas o teóricas como por sus aplicaciones prácticas: Revistas (Fuzzy Sets and Systems, IEEE Transactions on Fuzzy Systems..) Congresos (FUZZ-IEEE, IPMU, EUSFLAT, ESTYLF…) Miles de aplicaciones reales: Control de sistemas: Tráfico, vehículos, compuertas en plantas hidroeléctricas, centrales térmicas, lavadoras, metros ascensores… Predicción y optimización: Predicción de terremotos, optimización de horarios… Reconocimiento de patrones y Visión por ordenador: Seguimiento de objetos con cámara, reconocimiento de escritura, reconocimiento de objetos, compensación de vibraciones en cámaras, sistemas de enfoque automático… Sistemas de información o conocimiento: Bases de datos, sistemas expertos…

15 Un poco de publicidad… Carga: 5kg Revoluciones: 1400 rpm Características energéticas: A+,A,B Multi-Display Fuzzy Logic Programas especiales: Lavado a mano, Seda, Lana Poderoso lente zoom de 4.3x, 28-120 con elementos de lentes de cristal ED Sistema de flash doble incorporado. Ajuste de Exposición Automática programada Sistema de Medición TTL: Fuzzy logic ESP, Promedio Balanceado al Centro OLYMPUS ERGONÓMICA SRL 28-120 (2995 dólares) AEG Lavamat 64600 (429 euros)

16 Funciones de pertenencia Algunas de las funciones de pertenencia más utilizadas son: Función GAMMA (?): Función LAMBDA o triangular Función L Puede definirse simplemente como 1 menos la función GAMMA

17 Funciones de pertenencia Función PI o trapezoidal

18 Funciones de pertenencia Función S Función P Función Z (opuesta de la S) mZ(x) = 1- mS(x)

19 Etiquetas lingüísticas Equivalentes a los adverbios del lenguaje natural Se utilizan para definir conjuntos difusos a partir de otros ya existentes. Por ejemplo, viejo —> MUY viejo Lo que se hace es componer la función de pertenencia con alguna otra función, de forma que la función resultante tenga la forma deseada Por ejemplo, función para el adverbio MUY —> f(y) = y2

viejo Muy viejo

20 Etiquetas lingüísticas (Gp:) Nombre del modificador

(Gp:) Descripción del modificador

(Gp:) not

(Gp:) 1-y

(Gp:) very (muy)

(Gp:) y2

(Gp:) somewhat (algo)

(Gp:) y1/3

(Gp:) more-or-less (más o menos)

(Gp:) y1/2

(Gp:) extremely (extremadamente)

(Gp:) y3

Existe todo un catálogo de adverbios/funciones

21 Etiquetas lingüísticas Otras operaciones usuales Concentración Intensificación contraste Dilatación Difuminación Normalización f(y) = y/Altura f(y)=yp, con p>1 f(y)=yp, con 0< p< 1

22 Operaciones con conjuntos difusos Siendo c: [0,1] ? [0,1]. La función c debería cumplir las siguientes propiedades c1. concordancia caso nítido c(1) = 0 y c(0) = 1 c2. estrictamente decreciente ?a,b? [0,1] a>b ? c(a) < c(b) c3. involución ?a? [0,1] c(c(a)) = a Las funciones más utilizadas son: Complementario Dado un conjunto difuso A, su complemento vendrá definido por c(a) = 1 – a. Sugeno cl(a) = (1-a)/(1-la) l? [0, 1] Yager cw(a) = ( 1 – aw)1/w w? [0, ?]

23 Operaciones con conjuntos difusos Siendo i: [0,1]x[0,1] ? [0,1]. La función i debería cumplir las siguientes propiedades: i1. concordancia caso nítido i(0,1) = i(0,0) = i (1,0) = 0; i(1,1) = 1 i2. conmutatividad i(a,b) = i(b,a) i3. asociatividad i(a,i(b,g)) = i(i(a,b),g) i4. identidad i(a,1) = a i5. monotonía si a?a’ b ? b’, entonces i(a,b) ? i(a’, b’) Intersección Dados dos conjuntos difusos A y B, su intersección vendrá definida por ([0,1],i) tiene estructura de semigrupo abeliano con elemento neutro.

Las funciones i que verifican esta propiedad se llaman normas triangulares (t-normas).

24 Operaciones con conjuntos difusos Algunas t-normas usuales: (Gp:) t-norma del mínimo imin(a,b) = min(a,b)

(Gp:) t-norma del producto i*(a,b) = ab

(Gp:) t-norma del producto drástico

Toda t-norma verifica las siguientes desigualdades: ?a,b? [0,1] iinf(a,b) ? i(a,b) ? imin(a,b) la menor t-norma es la t-norma del producto drástico la mayor t-norma es la norma del mínimo

25 Operaciones con conjuntos difusos Siendo u: [0,1]x[0,1] ? [0,1]. La función u debería cumplir las siguientes propiedades:

u1. concordancia con el caso nítido u(0,1)=u(1,1)=u(1,0) =1; u(0,0) = 0 u2. conmutatividad u(a,b) = u(b,a) u3. asociatividad u(a,u(b,g)) = u(u(a,b),g) u4. identidad (A ? ? = A) u(a,0) = a u5. monotonía Si a?a’ b?b’, entonces u(a,b)?u(a’, b’) Unión Dados dos conjuntos difusos A y B, su unión vendrá definida por mAuB(x) = u(mA(x), mB(x)) Además, podemos pedir que se cumpla: u6. Leyes de De Morgan u(a,b) = c(i(c(a),c(b)) i(a,b) = c(u(c(a),c(b)) Las funciones i que verifican estas seis propiedad se llaman conormas triangulares (t-conormas).

26 Operaciones con conjuntos difusos Si consideramos como complemento la función c(u) = 1-u, las t-conormas correspondientes a las t-normas anteriores son: t-conorma del máximo umax(a,b) = max(a,b) t-norma de la suma drástica Toda t-conorma satisface las siguientes desigualdades: ?a,b?[0,1] umax(a,b) ? u(a,b) ? usup(a,b) la menor t-conorma es la t-conorma del máximo la mayor t-conorma es la t-conorma de la suma drástica

(Gp:) t-conorma de la suma u*(a,b) = a+b-ab

27 Operaciones con conjuntos difusos Sin embargo, estas propiedades que les hemos pedido a las operaciones de unión e intersección no garantizan que se satisfagan estas otras propiedades: I1: Idempotencia (A ? A = A) i(a,a) = a I1: Distributividad (A ? (B ? C)) = … i(a,u(b,g)) = u(i(a,b),i(a,g)) U1 : Idempotencia (A ? A = A) u(a,a) = a U2 : Distributividad (A ? (B ? C)) = … u(a,i(b,g)) = i(u(a,b),u(a,g)) propiedades que sólo verifican la t-norma del mínimo junto con la t-conorma del máximo Conjuntos vacío y total: Conjunto vacío Conjunto total Sin embargo, con esta definición no se satisfacen algunos famosos principios de la lógica clásica, como por ejemplo: Principio de contradicción Principio del tercio excluso

28 Razonamiento difuso Proposición difusa simple: Proposición que asigna un valor a una variable difusa: “Pepe es de estatura mediana”. Tiene asociado un conjunto difuso y su función de pertenencia. Proposición difusa compuesta: Agrupación de dos o más proposiciones difusas simples “la velocidad es normal” Y “el objeto está cerca” “la velocidad es alta” O “el objeto está muy cerca” “la velocidad NO es alta” Necesidad de definir operadores difusos: NO (¬p) m¬A(u) = 1 – mA(u) Y (p?q) vendrá definida por una función de pertenencia tipo intersección, por ejemplo m A?B(u,v) = min( mA(u), mB(v)) O (p?q) vendrá definida por una función de pertenencia tipo unión, por ejemplo mAUB(u,v) = max(mA(u), mB(v))

29 Razonamiento difuso: implicaciones El siguiente paso es definir lo que es una implicación, es decir, asignar una función de pertenencia a una agrupación antecedente consecuente del tipo p?q Esto nos permitirá razonar con afirmaciones tales como: SI “la velocidad es normal” ENTONCES “la fuerza de frenado debe ser moderada” Opciones: Teórica: Dar a la implicación el mismo significado que en la lógica clásica. p?q ? ?p?q mp?q(u,v) = max(1-mA(u), mB(v)) p?q ? ~(p?(~q)) mp?q(u,v) = 1 – min[mA(u), 1-mB(v)] Práctica: Dar a la implicación el significado de relación causa-efecto: Implicación de Mamdani p?q ? A?B ? mp?q(u,v) = min( mA(u), mB(v))

30 Decodificación Una vez llevado a cabo el proceso de razonamiento difuso, es necesario dotar al sistema de la capacidad de tomar decisiones. Así por ejemplo, el sistema debe saber qué fuerza de frenado que debemos aplicar si la velocidad es alta Para ello se utilizan las llamadas técnicas de decodificación, que transforman un conjunto difuso en un valor nítido. Las más usuales son: El valor máximo (es decir, el más posible). El centroide o centro de gravedad difuso

31 Funcionamiento de un sistema de control basado en lógica difusa (Gp:) Reglas (Gp:) Inferencia

Codificador Decodificador (Gp:) u ?Up (Gp:) Conjuntos difusos entrada

(Gp:) v ?V (Gp:) Conjuntos difusos salida

(Gp:) Entrada nítida (Gp:) x ?Up

(Gp:) y=f(x) ?V (Gp:) Salida nítida

32 En resumen La lógica difusa se concibió originalmente como un método mejor para manejar y almacenar información imprecisa Ha demostrado ser una excelente alternativa para sistemas de control, ya que imita a la lógica de control humana Se pede incluir en cualquier sistema, desde dispositivos pequeños a sistemas de control complejos Usa un lenguaje impreciso pero muy descriptivo para operar con datos de entrada de una forma parecida a la usa un operador humano Es robusta y no demasiado dependiente de los datos de entrada y operadores elegido Incluso las primeras versiones funcionan bastante bien, con escasa necesidad de ajustes

33 Redes bayesianas Definición intuitiva Definición formal Teorema fundamental Algoritmos de propagación Ejemplo Herramientas Ejercicios

34 Redes bayesianas Una red bayesiana es:

Un conjunto de nodos que representan variables o entidades del mundo real Un conjunto de enlaces que representan relaciones de influencia causal entre los nodos Una serie de parámetros (probabilidades condicionadas de cada nodo dados sus padres) que cuantifican la relación entre los nodos.

35 P(gripe) = 0.3 P(tos/gripe) = 0.9 P(tos/no gripe) = 0.01

Tos

Gripe

Interpretación de los parámetros: (Gp:) Prevalencia

(Gp:) Sensibilidad

(Gp:) Especificidad

P(gripe) = 0.3 P(tos/gripe) = 0.9 P(no tos/no gripe) = 0.99 Ejemplo

36 Definición formal de red bayesiana Una red bayesiana es: Un conjunto exhaustivo y excluyente de variables proposicionales, V Un conjunto E de relaciones binarias definidas sobre las variables de V Una distribución de probabilidad conjunta P definida sobre las variables de V, tales que: (V, E) es un grafo acíclico, conexo y dirigido G. (G, P) cumple las hipótesis de independencia condicional ? X?V y ? Y ? V – {X ? de(X)} P(X/pa(X), Y) = P(X/pa(X))

37 Teorema fundamental Dada una red bayesiana, la distribución de probabilidad conjunta puede expresarse como: P(x1, …, xn) = ? P(xi /pa(xi))

38 Algoritmos de propagación Los algoritmos de propagación en redes bayesianas permiten hacer inferencias: De tipo abductivo: dado que el alumno ha respondido a ciertas preguntas, ¿cuál es la probabilidad de que conozca los conceptos? De tipo predictivo: dado que el alumno conoce ciertos conceptos, ¿cuál es la probabilidad de que responda correctamente a la pregunta? Cuando un nodo (grupo de nodos) se instancia, la información se propaga por la red de forma que se calculan las probabilidades a posteriori de cada uno de los nodos dado el valor que haya tomado el nodo (grupo de nodos) instanciado.

39

Ejemplo: la red Asia X D T A L B S E Asia Tuberculosis Cáncer pulmón Fumador Bronquitis Rayos X Disnea Enfermedad (Gp:) Explaining away

Abducción Predicción

40 Algoritmos de propagación Algoritmos exactos Estructuras especiales: árboles, poliárboles Caso general: Algoritmos de condicionamiento Algoritmos de agrupamiento Algoritmos aproximados

41 Herramientas Hugin http://www.hugin.dk Javabayes http://www-2.cs.cmu.edu/~javabayes/Home/ Algunas más: http://www.ia.uned.es/~fjdiez/bayes/software.html

42 Ingeniería del conocimiento con redes bayesianas Modelado con redes bayesianas: Nodos (variables), relaciones de influencia causal Parámetros (probabilidad condicionada de cada nodo dados sus padres) Mecanismos de propagación (herramientas)

Mucho más en:

http://www.lcc.uma.es/eva/doc/materiales/microsoft.pdf

43 Variables y relaciones En general, las redes bayesianas se han usado en: Problemas de diagnóstico: diagnóstico de averías (HP), diagnóstico médico, diagnóstico de problemas, diagnóstico de intenciones y objetivos (clip de Microsoft), etc. Problemas de clasificación Por tanto lo primero será identificar el tipo de problema que queremos resolver

44 Problemas de diagnóstico Preguntas relevantes: ¿Qué observaciones se han efectuado? ¿Qué posibles causas hay para explicar dichas observaciones? ¿Hay otros indicios que apoyen o ayuden a descartar alguna de esas posibles causas? ¿Cómo son las relaciones entre los nodos? ¿Qué tipo de relaciones existe entre las variables?.

45 Ejemplo 1: Luisito está enfermo Los padres de Luisito, que acaba de cumplir un año, deciden llevarlo al pediatra porque vomita con cierta frecuencia. Con el pediatra sostienen la siguiente conversación: Pediatra -. Denme toda la información que consideren que puede ser relevante. Mamá-. El otro día Luisito estaba resfriado. Vomitó el biberón de la noche, creo que por culpa de los mocos, ya que había muchos en el vómito. Otras veces parece que vomita por una pequeña indigestión. Papá-. Además creo que debe saber que mi hermano es celíaco (Aclaración: la celiaquía es una intolerancia al gluten, que poco a poco hace que se destruya el vello intestinal. Los vómitos son uno de sus síntomas más relevantes. Se cree que tiene cierta componente hereditaria). Pediatra-. ¿Y la dieta de Luisito incluye gluten? Ambos-. Sí, desde hace unos meses.

46 Ejemplo 2: ¿Se han copiado? Cuando el profesor de Métodos Computacionales de la Física Cuántica corrige los exámenes de Junio, encuentra que los resultados del mismo son muchísimo mejores que en convocatorias anteriores, y comienza a pensar en la posibilidad de que los alumnos hayan copiado, aunque también puede ocurrir que los alumnos de ese curso sean excepcionalmente buenos. Para averiguar lo que ha ocurrido, intenta también tener en cuenta otras informaciones que tiene disponibles, y que son las siguientes: Un par de días antes del examen dejó su despacho abierto por descuido. El enunciado del examen estaba ese día encima de la mesa. Un amplio grupo de alumnos ha cometido exactamente el mismo fallo en uno de los problemas. Los profesores que le han dado clase a ese grupo en años anteriores consideran que el grupo es bueno, pero no excepcional.

47 Problemas de clasificación Preguntas relevantes: ¿Qué objetos son los que se desea clasificar? ¿Cuáles son las diferentes categorías? ¿Puede un objeto pertenecer a más de una categoría? ¿Están contempladas en el problema todas las categorías posibles? Si el conjunto de posibles categorías es exhaustivo y excluyente -> un único nodo En otro caso ->un nodo por categoría ¿Qué rasgos o indicios se utilizan para realizar la clasificación?

48 Ejemplo 1: El planeta ZYX En el planeta Zyx se pueden encontrar varias clases de animales, llamemos a estas clases Wurros, Hobexas y Wackas. Todos tienen un tamaño muy pequeño, y sus pieles son o bien escamosas o bien están cubiertas de suave pelo. Además, una observación atenta ha permitido deducir lo siguiente: Todos los Wurros tienen 5 ó 6 patas. Su color es rojizo, y tienen la piel peluda y suave. El número de patas de las Hobexas es un entero que varía uniformemente entre 4 y 6, ambos inclusive. Su piel es escamosa. En cuanto a las Wackas, tienen 4 ó 5 patas, y ofrecen a la vista una tonalidad casi siempre azulada, pero a veces (20% de los casos) rojiza. Los animales que tienen un número impar de patas cojean siempre. Los animales que tienen un número par de patas cojean sólo cuando tienen alguna anomalía (malformación congénita, heridas, etc.), lo cual ocurre en el 10% de los casos para los animales de 4 patas, y en el 20% para los de seis.

49 Parámetros: modelos canónicos Puerta OR

Puerta AND Faringitis Otitis Fiebre Alergia Olivo Estornudo