Download Universidad Veracruzana

Universidad Veracruzana
Facultad de Física e Inteligencia Artificial
BayesN: Un Algoritmo para Aprender Redes Bayesianas Clasificadoras a partir
de datos
Tesis
que para obtener el grado de:
Maestro en Inteligencia Artificial
Presenta:
José Luis Jiménez Andrade
Director:
Dr. Manuel Martínez Morales
Asesor:
Dr. Nicandro Cruz Ramírez
Xalapa~Enríquez, Ver., 2003
A mis padres: Isabel y Tomás. Nunca podré retribuir tanto sacrificio.
Agradecimientos
A Dios por permitirme existir.
A mis padres y hermanos por haberme apoyado y empujado siempre en todo lo
que inicie.
A mis padrinos, Estela y Daniel por que en verdad han sido siempre mis
segundos padres, gracias por su apoyo.
A la maestra Carmen García Cuevas, al Dr. Jesús Jiménez Castillo y Manuel
Jiménez García, por su amistad, por sus consejos, por que muchas veces me
aboné en su casa y por animarme a entrar a la maestría.
A mi novia Karla. Muchas gracias por tu apoyo, cariño y comprensión.
A mis asesores Dr. Manuel Martínez Morales y Dr. Nicandro Cruz Ramírez por
darme la oportunidad de trabajar con ellos.
Al Dr. Cesar de la Cruz Laso y al Dr. José Negrete por que gracias a ellos,
principalmente, obtuve la condonación de la colegiatura.
A mis compañeros, por que de cada uno aprendí algo.
A cada uno de las personas que laboran en la maestría, por que me aceptaron
en la gran familia que forman.
Índice
Introducción
1. Redes Bayesianas
1.1 Sistemas Expertos
1.2 Clasificación
1.3 Repaso de Probabilidad
1.4 Variables Aleatorias
1.5 Independencia Condicional
1.6 Grafos
1.7 Modelos de Dependencia y mapas de Dependencia
1
1
2
3
6
7
9
10
2. Aprendizaje de Redes Bayesianas
2.1 Problemas en el Aprendizaje de Redes Bayesianas
2.2 Aprendizaje de la Estructura
2.2.1 Enfoque Tradicional
2.2.2 Aprendizaje a Partir de Datos
2.2.2.1 Algoritmos Basados en Búsquedas
2.2.2.2 Algoritmos Basados en Restricciones
14
14
16
16
16
16
18
3. Familia de algoritmos bayes
3.1 Prueba Estadística para la Independencia Marginal
y Condicional
3.2 Bayes2
3.3 Bayes5
21
21
4. BayesN
4.1 Profundidad Variable
4.2 Control de Significancia
4.2.1 Ajuste de Bonferroni
4.2.2 Región de Indiferencia: Ganancia de Información Mínima
4.3 Sistema de Análisis Bayesiano (BANSY)
4.3.1 Módulo de Aprendizaje
4.3.2 Módulo de Aprendizaje de Parámetros (Probabilidades)
4.3.3 Módulo de Inferencia
4.3.4 Módulo de Bondad de Ajuste
4.3.5 Módulo de Clasificación
28
28
28
28
30
33
33
34
34
34
34
5. Pruebas de desempeño
5.1 Bases de Datos y Redes de Oro
5.2 Bondad de Ajuste
5.3 Algoritmos
5.3.1 K2
5.3.2 Pc (Tetrad)
36
36
39
41
41
41
23
25
5.4 Comparación de la Topología Generada por los Algoritmos
con la Red de Oro
5.4.1 Tablas de Resultados
5.4.2 Topología
5.4.3 Discusión
5.5 Clasificación
5.5.1 Hipótesis a Posteriori Máxima
5.5.2 Clasificador Naïve-Bayes
5.5.3 Redes Bayesianas Clasificadoras
5.5.4 Métodos para la Clasificación
5.5.5 Resultados del Método de Partición (Holdout)
5.5.6 Resultados con el Método de Validación
Cruzada(Cross-Validation)
5.5.7 Discusión
Conclusiones
Trabajo Futuro
Referencias
42
42
43
47
47
47
48
49
50
52
52
53
55
56
Introducción
Las redes Bayesianas juegan diversos papeles importantes dentro de la
Inteligencia Artificial. Uno de ellos es su actuación dentro del manejo de
incertidumbre en los sistemas expertos. Otro papel importante lo tienen en lo que
se conoce como descubrimiento de conocimiento en bases de datos; las redes
Bayesianas permiten encontrar, de una manera consistente, relaciones
probabilistas entre variables. Siendo entonces las redes Bayesianas modelos que
describen las relaciones (relaciones de independencia/dependencia) entre
variables, estas pueden ser aplicadas a casi cualquier tipo de problema. Sin
embargo este trabajo se centra en aquellos problemas en los que existe cierta
estructura en las relaciones de las variables. En este tipo de problemas hay una
variable dependiente (a explicar) y un conjunto de variables independientes o
explicativas ). La hipótesis subyacente es que el comportamiento de la variable
dependiente puede ser explicada como resultado de la acción de las variables
dependientes. Es por ello que se presenta a BayesN como un algoritmo de
generación de redes Bayesianas clasificadoras.
En la primera parte de este trabajo se presenta un repaso de redes
Bayesianas. Posteriormente se describe BayesN, no sin antes explicar a su
predecesores: Bayes2 y Bayes5. Finalmente se realiza una valoración de su
desempeño comparándolo con algoritmos competitivos con el estado del arte de
las redes Bayesianas.
_________________________________________________________________________
Capítulo 1.
Redes Bayesianas
¿Por qué Redes Bayesianas?. Para poder contestar esta pregunta, debemos
ubicar su uso y su importancia dentro de la Inteligencia Artificial. En este capítulo
se expone primeramente la importancia de las redes Bayesianas dentro de la
Inteligencia Artificial, Posteriormente se hace un repaso de las herramientas
matemáticas básicas para la comprensión de las redes Bayesianas. Finalmente se
presenta un serie de axiomas, teoremas y definiciones que respaldan la solidez
del algoritmo presentado y en general de la familia de algoritmos Bayes.
1.1 Sistemas Expertos
Uno de los primeros éxitos de la Inteligencia Artificial sin lugar a dudas
fueron los sistemas expertos: DENDRAL(Feigenbaum y Buchanan, 1978),
PROSPECTOR(Duda, Hart y Nilsson, 1976), MYCIN(Shortliffe, 1976). El uso de
los sistemas expertos es tan variado que los encontramos en la industria,
medicina, educación, e incluso en las ciencias sociales.
Ahora bien, ¿qué es un sistema experto, y donde entran las redes
bayesianas?
“Un sistema experto es una programa inteligente de computadora que usa
conocimiento y procedimientos de inferencia para resolver problemas que son lo
suficientemente difíciles para requerir cierta pericia humana para su solución. El
conocimiento de un sistema experto se basa
en hechos y heurísticas”
(Feigenbaum, 1979).
Otra definición es la dada por Nikolopoulos (Nikolopoulos, 1997): “Un
sistema experto o sistema basado en conocimiento utiliza conocimiento ganado a
través de razonamiento y heurísticas para resolver problemas complejos e
intratables del mundo real, con un alto grado de confiabilidad”.
Cabe mencionar que un sistema experto debería ser capaz de proveer
explicaciones acerca de las decisiones tomadas y además trabajar con datos
incompletos o bajo incertidumbre.
Inicialmente se intentaron sistemas que resolvieran problemas generales
como el GPS (General Problem Solver) (Newell & Simon, 1963), sin embargo se
vio que este tipo de sistemas no tenían una aplicación muy, además, para muchos
problemas no se proveían soluciones completas; esto causó que se cambiara
1
_________________________________________________________________________
enfoque; desarrollando así sistemas especializados aplicados a varios dominios.
De aquí podemos decir algo más de un sistema experto: “Un sistema experto
resuelve problemas en un dominio especifico” (Nikolopoulos, 1997).
Se habla de una primera y segunda generación de sistemas expertos. La
principal diferencia entre las dos generaciones se encuentra en la etapa de
construcción de la base de conocimiento. Existen técnicas para la extracción del
conocimiento a partir de un experto humano, sin embargo este proceso resulta
bastante tedioso y difícil. En la segunda generación de sistemas expertos, este
proceso es visto como una actividad de modelado. Es por eso que ahora se están
desarrollando sistemas más flexibles que sean capaces de construir
inductivamente estructuras de conocimiento; técnicas del subcampo de la IA
llamado aprendizaje automático (Machine Learning) están siendo utilizadas para
automatizar este proceso de generación de la base de conocimiento. Es aquí
donde encontramos una parte de la importancia de este trabajo; aprendizaje de
redes bayesianas, como una técnica automatizada para la adquisición del
conocimiento de un dominio específico.
Los sistemas expertos iniciales usaban el enfoque simbólico, por lo que
usaban lógica para la representación del conocimiento, así como para
razonamiento y deducción. Se vio que en dominios muy complejos del mundo real,
el conocimiento humano y su proceso mismo de razonamiento no podían ser
modelados usando lógica clásica y sus técnicas de inferencia.
En muchos problemas del mundo real la incertidumbre está presente y
puede manifestarse como información incompleta, imprecisión e información vaga.
Como resultado se han desarrollado varias teorías para el manejo de
incertidumbre; la mayoría son cuantitativas, se basan en la introducción de
esquemas en los que se introduce una medida numérica que cuantifica la
incertidumbre. Entre las diferentes teorías se pueden mencionar las siguientes: el
enfoque Bayesiano, que se basa en el uso de probabilidades condicionales y el
teorema de bayes; factores de certeza, que utiliza reglas con un factor de
confianza asociado; teoría de la evidencia de Dempster-Shafer, lógica difusa y las
redes bayesianas (Nikolopoulos, 1997).
1.2 Clasificación
Uno de los dominios mas investigados en el campo de aprendizaje
automático ha sido el problema de clasificación. Un sistema experto es
repetidamente confrontado a clasificar sus experiencias. Por ejemplo, un médico al
encontrar ciertos síntomas en un paciente, diagnostica un enfermedad específica.
A continuación se describe esta tarea.
La tarea de clasificar consiste en etiquetar casos a partir de un conjunto de
características (Friedman 1997). Esta tarea ha sido abordada con diferentes
2
_________________________________________________________________________
enfoques, entre ellos podemos mencionar los árboles de decisión, redes
neuronales y Naïve-Bayes (Friedman, 1997). Este último se considera bastante
efectivo, en el sentido de que es competitivo con el estado del arte de los
clasificadores; a pesar de la hipótesis tan fuerte que hace al considerar que los
atributos son condicionalmente independientes dada la variable clase. Esta
restricción hace que en ciertos casos Naïve-Bayes tenga un desempeño
ligeramente menor, sobre todo en aquellos casos en los que los atributos están
bastante correlacionados.(Friedman, 1997). En el capítulo 4 veremos que la red
Bayesiana construida por el algoritmo propuesto mejora en buena medida a este
clasificador y que además son al menos tan buenas clasificadoras como aquellas
generadas con algoritmos como el PC (Spirtes et al. 1990), K2 (Cooper &
Herskovits, 1992) y Bayes9(Cruz-Ramírez, 2001).
Hasta ahora hemos hablado de la importancia de las redes bayesianas, pero
¿qué es una red Bayesiana?.
Las redes bayesianas están basadas, básicamente en dos cosas: teoría de
la probabilidad y la teoría de grafos. Es por eso que si queremos entender qué es
una red bayesiana, es necesario conocer los principios básicos en los que se
fundamentan la probabilidad, y algunas nociones acerca de los grafos.
1.3 Repaso de Probabilidad
Usando el enfoque Bayesiano(Pearl 2001), la interpretación de probabilidad
es que éstas, codifican grados de creencia asignados a proposiciones. Por
ejemplo, A = ”Hoy lloverá”, es una proposición que tiene dos valores posibles:
verdadero(v) o falso(f). La probabilidad de que A sea verdadera se expresa como:
P(A = v), se usan letras minúsculas para denotar que la proposición esta tomando
cualquier valor de sus valores posibles. Ej. P(A = a), quiere decir que “A” toma a
“a”, donde “a” representa cualquier valor posible de A. La mayoría de las veces se
cambia P(A = a) simplemente por P(A), para simplificar las cosas.
Estas medidas de creencia obedecen a los axiomas básicos del calculo de
probabilidad:
Sea V un conjunto de proposiciones, en la que X1, X2, ..., Xi,... Xn son
proposiciones
A1.
A2.
0 ≤ P( X i ) ≤ 1
∑ P( X
i
) =1
i
A3.
P ( X i ∨ X j ) = P ( X i ) + P ( X j ) si X i y X j son
(1.3.1)
(1.3.2)
(1.3.3)
3
_________________________________________________________________________
mutuamente excluyentes. X i ∨ X j
1
denota la disyunción de las
proposiciones X i y X j .
El tercer axioma establece que la creencia asignada a un conjunto de
eventos o proposiciones, es la suma de las creencias asignadas a los mismos.
Dado que la probabilidad de cualquier evento A se puede expresar como la unión
de eventos ( A ∧ B ) ∧ ( A ∧ ¬B ) , entonces podemos calcular la probabilidad de A
como:
P ( A) = P ( A, B ) + P ( A, ¬B ),
(1.3.4)
donde P( A, B ) es una forma corta de expresar P ( A ∧ B ) . En forma general,
si B toma n valores, entonces podemos escribir P ( A) como:
n
P ( A) = ∑ P ( A, Bi ) , siempre que Bi forme una partición
(1.3.5)
i
La expresión anterior es conocida como la ley de la probabilidad total.
Realizar esta operación es lo que comúnmente se llama marginalizar sobre B, y el
resultado es la probabilidad de A, a la que se llama probabilidad marginal.
Del A2 (ecuación 1.3.2), se puede deducir que a una proposición y a su
negación, se le deba asignar una probabilidad de uno.
P ( A) + P (¬A) = 1
(1.3.6)
Una de las expresiones básicas en el formalismo Bayesiano son la
probabilidades condicionales, por ejemplo P ( A | B ) , que quiere decir: la creencia(o
probabilidad) de A bajo el supuesto de que conocemos a B con absoluta certeza.
Normalmente la probabilidad condicional se define en términos de la
probabilidad conjunta de la forma siguiente:
P( A | B) =
P ( A, B)
,
P( B)
(1.3.7)
Sin embargo, los filósofos Bayesianos ven de una forma más básica a las
relaciones condicionales que a las relaciones conjuntas, i.e., consideran que son
más compatibles con la organización del conocimiento humano (Pearl 1998, 2001,
otra refencia). Desde este punto de vista, B es el contexto o marco de referencia;
así A | B es el evento A en el contexto B. (Pearl 2001). De esta forma el
1
Los símbolos ∧,∨, ¬, ⇒ denotan los conectivos lógicos y, o, no e implica, respectivamente.
4
_________________________________________________________________________
conocimiento empírico siempre será codificado como probabilidades
condicionales, mientras que la creencia de eventos conjuntos será calculada a
partir del producto
P ( A, B ) = P ( A | B ) P ( B ) ,
(1.3.8)
De la ecuación (1.3.5), y utilizamos también la ecuación (1.3.8) podemos
calcular la probabilidad P(A) a partir de:
P( A) = ∑ P( A | Bi ) P( Bi ) ,
i
(1.3.9)
que también se puede ver como una marginalización sobre B. Ahora bien, si
queremos calcular la probabilidad de A en contexto más generalizado, digamos en
un contexto K, entonces podemos rescribir la ecuación (1.3.9) como:
P( A | K ) = ∑ P( A | Bi , K ) P( Bi | K )
(1.3.10)
en realidad se podría ver la ecuación 1.3.9 como un caso especial de esta
ecuación.
La generalización de la ecuación (1.3.8) es un resultado muy importante, y
se conoce como la regla de la cadena o del producto, establece que si tenemos un
conjunto de n eventos, E1 , E 2 ,..., E n , entonces la probabilidad conjunta
P( E1 , E 2 ,..., E n )
condicionales:
pude escribirse como un producto de
P( E1 , E 2 ,..., E n ) = P( E n | E n −1 ,..., E 2 , E 2 )...P( E 2 | E1 ) P ( E1 ).
n probabilidades
(1.3.11)
este producto se puede derivar aplicando la formula (1.3.8) repetidamente
en un orden conveniente.
La formula más importante en el razonamiento Bayesiano es la llamada
regla de Bayes:
P ( H | e) =
P (e | H ) P ( H )
P ( e)
(1.3.12)
La cual establece que la creencia para una hipótesis H sobre una evidencia
e puede calcularse multiplicando nuestra creencia previa P(H) por la probabilidad
de que e suceda dado que H ocurre, i.e. P(e|H). El denominador juega un papel
normalizador, que puede ser calculado al considerar que P(H|e) y P(¬H|e) suman
la unidad.
5
_________________________________________________________________________
Podría decirse que la ecuación (1.3.12) es una tautología proveniente de la
definición de probabilidades condicionales,
P( A | B) =
P ( A, B)
P ( A, B)
y P( B | A) =
P( B)
P ( A)
(1.3.13)
Su importancia radica, sin embargo, en que funciona como una regla de
actualización de creencias en respuesta a evidencia. Además, que expresa P(H|e)
en términos de cantidades que normalmente pueden se obtenidas directamente
de la experiencia, cuando esta cantidad resulta difícil de determinar.
Para completar esta breve introducción, debemos discutir la noción de
modelo probabilista. Un modelo probabilista es una codificación de la información,
que nos permite calcular la probabilidad de cada oración bien formada S de
acuerdo a los axiomas (1.1)-(1.3). Si consideramos un conjunto de proposiciones
atómicas A, B, C,..., el conjunto de oraciones bien formadas consiste de todas las
fórmulas boleanas que involucran a estas proposiciones, por ejemplo S =
(A∧B)∨¬C. El método tradicional para especificar un modelo probabilista es
emplear una función de distribución conjunta, la cual es una función que asigna
pesos no negativos a cada evento elemental en un lenguaje (donde un evento
elemental es la conjunción de las proposiciones o sus negaciónes), tal que se
cumplen A1-A3. Por ejemplo, si tenemos tres proposiciones atómicas, A, B y C,
entonces la función de distribución conjunta debe asignar un peso no negativo a
las ocho combinaciones –(A ∧ B ∧ C), (A ∧ B ∧ ¬C),..., (¬A ∧ ¬B ∧ ¬C)- tal que
los ocho pesos suman 1.
El conjunto de eventos elementales es lo que en textos de probabilidad se
le llama espacio muestral.
Las funciones de distribución conjunta representa de forma completa un
modelo probabilista. Sin embargo, en la practica éstas raramente son
especificadas explícitamente. En el análisis de variables aleatorias continuas, las
funciones de distribución están dadas por expresiones algebraicas tales como
aquellas que describen distribuciones normales o exponenciales; para variables
discretas, métodos indirectos de representación han sido desarrollados donde la
distribución completa es inferida a partir de relaciones locales entre grupos
pequeños de variables. Es aquí donde podemos mencionar otra gran importancia
de las redes bayesianas, que caen entre las representaciones desarrolladas para
un modelo probabilista.
1.4 Variables Aleatorias
6
_________________________________________________________________________
Entendemos por una variable un atributo o medida que puede tomar uno de
diferentes posibles resultados, o valores, de un dominio específico. Si tenemos las
creencias (i.e. probabilidades) de los valores posibles que la variable puede tomar,
entonces llamaremos a esa variable una variable aleatoria. Por ejemplo el color de
la camisa que me pondré mañana es una variable aleatoria llamada “color”, y sus
valores que puede tomar vienen del dominio{roja, verde,...}. Es decir una variable
aleatoria discreta es una función real definida sobre un conjunto discreto dado,
obedeciendo los axiomas A1-A3.
En este trabajo sólo usaremos conjuntos finitos de variables, donde cada
variable X ∈ V (V conjunto finito de variables) puede tomar valores de un dominio
finito Dx con elementos mutuamente exclusivos y exhaustivos. Usaremos letras
mayúsculas (e.g. X, Y, Z) para los nombres de las variables aleatorias y letras
minúsculas (x,y,z) para valores específicos tomados por la variable
correspondiente. Por ejemplo, si X es el color de mi camisa, entonces x designará
algún color escogido de algún elemento de Dx.
Otra consideración a tomar es que no haremos distinción en la notación
para variables y conjunto de variables, porque un conjunto de variables es
esencialmente una variable compuesta, cuyo dominio es el producto cartesiano de
los dominios de las variables. Así, si Z es un conjunto formado por {X,Y} entonces
z tomará valores por pares {x,y} tal que x ∈ Dx e y ∈ Dy.
Usaremos constantemente la abreviación P(x) para las probabilidades P(X
= x), x ∈ Dx. De igual forma, si Z es un conjunto {X,Y}, entonces P(z) quiere decir
P(Z = z), lo que a su vez indica P(X = x, Y = y), con x ∈ Dx e y ∈ Dy.
En adelante cuando digamos variable, entenderemos que se trata de
variable aleatoria discreta.
1.5 Independencia Condicional
Definición 1.5.1 (Independencia Condicional) (Pearl 2001)
Sea V = {V1, V2,...} un conjunto finito de variables. Sea P(.) una función de
probabilidad conjunta sobre las variables en V, y sea X, Y, Z tres subconjuntos de
variables cualquiera en V. Los conjuntos X y Y son condicionalmente
independientes dado Z si:
P ( x | y , z ) = p ( x | z ) siempre que p ( y , z ) > 0
(1.5.1)
En palabras, conocer Y no provee información adicional acerca de X, una vez que
conocemos a Z.
La notación para representar la independencia condicional es la siguiente:
7
_________________________________________________________________________
( X ⊥ Y | Z ) ⇔ P ( x | y, z ) = P( x | z )
(1.5.2)
Esto para todos los valores x ,y, z tal que P(y, z) > 0.
Alternativamente,
( X ⊥ Y | Z ) ⇔ P ( x, y | z ) = P ( x | z ) P ( y | z )
(1.5.3)
Ahora bien, si no condicionamos con ninguna variable, entonces estaremos
hablando de independencia marginal (no condicional), la cual se denota como
( X ⊥ Y | φ ) , y se define como:
( X ⊥ Y | φ ) ⇔ P ( x | y ) = P ( x)
(1.5.4)
Siguiendo con la misma notación, presentamos las propiedades fundamentales de
la relación de independencia condicional.
Simetría:
Descomposición:
Unión débil:
Contracción:
Intersección:
(X
(X
(X
(X
(X
⊥ Y | Z ) ⇔ (Y ⊥ X | Z ) .
⊥ YW | Z ) ⇒ ( X ⊥ Y | Z ) & ( X ⊥ W | Z ) .
⊥ YW | Z ) ⇒ ( X ⊥ Y | WZ ) .
⊥ Y | Z ) & ( X ⊥ W | ZY ) ⇒ ( X ⊥ YW | Z ) .
⊥ W | ZY ) & ( X ⊥ ZW ) ⇒ ( X ⊥ YW | Z ) .
(La propiedad de intersección se cumple en distribuciones de probabilidad
estrictamente positivas).
La prueba de estas propiedades puede derivarse a partir de los axiomas
básicos de la probabilidad y de la ecuación (1.5.2). Estas propiedades fueron
propuestas por Pearl y Paz (1988) para caracterizar las relaciones entre grafos y
relevancia informacional. Es decir estas propiedades de la independencia
condicional probabilista se pueden postular como axiomas para caracterizar
relaciones de independencia condicional en general, como interpretaciones
especificas en el dominio de la probabilidad, en el domino de los grafos o el
dominio del conocimiento.
A continuación se describe la interpretación intuitiva de los axiomas dada
por Pearl (2001). El axioma de simetría establece que, en cualquier estado de
conocimiento Z, si Y no nos dice nada nuevo acerca de X, entonces X no nos dice
nada nuevo acerca de Y. El axioma de descomposición dice que si dos evidencias
combinadas son juzgadas como irrelevantes, entonces cada evidencia separada
es también irrelevante. La unión débil establece que si agregamos información
irrelevante W no ayuda a información irrelevante Y a convertirse relevante para X.
8
_________________________________________________________________________
El axioma de contracción establece que si juzgamos W como irrelevante para X
después de conocer alguna información irrelevante Y, entonces W debe haber
sido irrelevante antes de que aprendiéramos Y. La unión débil y la contracción
indican que información irrelevante no altera el estatus de relevancia de otras
proposiciones en el sistema, lo que era relevante permanece relevante y lo que
era irrelevante permanece irrelevante. El axioma de intersección establece que si
Y es irrelevante para X cuando conocemos W y si W es irrelevante para X cuando
conocemos Y, entonces ni W ni Y (ni la combinación) es relevante para X.
1.6 Grafos
Un grafo es un conjunto V de vértices (nodos) y un conjunto E de flechas (arcos)
que conectan algún par de vértices. Los vértices en nuestros grafos corresponden
a variables aleatorias y los arcos denotan cierta relación entre el par de variables.
Cada arco en el grafo puede ser dirigido o no dirigido. La figura 1.6.1
muestra un grafo con arcos dirigidos. Si todos los arcos en un grafo son dirigidos,
entonces tenemos un grafo dirigido. Un camino en el grafo es una secuencia de
arcos (e.g. ((W,Z),(Z,Y),(Y,X)) en la figura 1.6.1) , tal que cada arco inicia con el
vértice que termina en el arco anterior. Si cada arco en el camino es una flecha
que apunta del primer vértice al segundo, entonces es una camino directo, de lo
contrario no lo será. En forma más general podemos llamarle camino de
adyacencia, lo cual aplica tanto para caminos directo, como no directos.
W
Z
X
Y
Fig. 1.6.1 Grafo dirigido
Hacemos uso de la terminología “familiar”, para denotar varias relaciones
en los grafos. Por ejemplo en la figura 1.6.1, Y tiene dos padres (X y Z), tres
ancestros (X, Z y W), y no tiene hijos, mientras que X no tiene padres y tiene un
hijo (Y). Una familia en un grafo es un conjunto de nodos que contiene a un nodo y
todos sus padres Pearl (2001). Por ejemplo , {W}, {Z, W}, {X}, y {Y, Z, X} son las
familias de la figura 1.6.1.
Un nodo se llama raíz si no tiene padres y se llama hoja si no tiene hijos. Un
grafo dirigido tiene al menos una raíz y una hoja.
9
_________________________________________________________________________
Un grafo que tiene todos los arcos dirigidos y que no tiene ciclos, i.e. que no
tiene caminos directos que te lleven de una variable a ella misma, se llama grafo
acíclico dirigido (GAD).
1.7 Modelos de Dependencia y Mapas de Dependencia
Sea U un conjunto finito de variables y sea X, Y y Z tres subconjuntos disjuntos en
U. Sea M un modelo de dependencia, es decir, un regla que asigna un valor de
verdad a predicados de la forma ( X ⊥ Y | Z ) M , o en otras palabras determina un
subconjunto I de tripletas ( X ⊥ Y | Z ) para las cuales se cumple la aseveración “X
es independiente de Y dado Z”. Cualquier distribución de probabilidad P es un
modelo de dependencia, porque para cada tripleta (X,Z,Y) podemos probar la
validez de ( X ⊥ Y | Z ) usando la ecuación (1.5.2).
Definición 1.7.1 Mapa de dependencia.(Pearl, 1988) Un grafo G es un mapa de
dependencia (o mapa-D) de M si existe una correspondencia uno a uno entre los
elementos de U y los nodos V de G, tal que para todos los subconjuntos disjuntos
X, Y, Z de elementos tenemos que:
( X ⊥ Y | Z ) M ⇒ ( X ⊥ Y | Z )G
(1.7.1))
Similarmente, G es un mapa de independencia (o Mapa-I) de M si:
( X ⊥ Y | Z ) M ⇐ ( X ⊥ Y | Z )G
(1.7.2)
Se dice que G es un mapa perfecto de M si es tanto un Mapa-D y un Mapa-I
Un mapa-D garantiza que si encontramos dos vértices conectados, estos
son verdaderamente dependientes en M, pero puede presentar dos variables
como independientes que en M son dependientes. Inversamente, un mapa-I
garantiza que dos vértices separados corresponden a variables independientes en
M, pero no garantiza que las variables que aparecen conectadas sean en realidad
dependientes.
Definición 1.7.2 Mapa-I mínimo. (Pearl, 1988) Un grafo es un mapa-I mínimo de
un modelo de dependencia M si borrando cualquier arco de G hace que G deje de
ser un mapa-I. Llamamos a este grafo una red de Markov de M.
Definition 1.7.3 Cobija de Markov. (Pearl, 1988) Una cobija de Markov BL(α) de
un elemento α ∈ U es cualquier subconjunto S de elementos para los cuales
(α ⊥ U − S − α | S ) con α ∉ U
(1.7.3)
10
_________________________________________________________________________
Un conjunto se llama límite de Markov de α, denotado por B(α) si éste es la
cobija de Markov mínima de α, i.e., ninguno de sus subconjuntos propios satisface
la ecuación (1.7.3).
El límite B(α) se interpreta como el conjunto más pequeño de elementos
que protegen a α de la influencia del resto de los elementos, incluyendo sus
descendientes.
Definición 1.8.1 d-separación. (Pearl, 1988) Si X, Y y Z son tres conjuntos
disjuntos de nodos en un DAG, entonces, se dice que Z d-separa X de Y, si a
través de cada camino entre un nodo en X y un nodo en Y hay un nodo w que
satisface alguna de las siguientes condiciones:
1) w tiene arcos que apuntan a el y ninguno de sus descendientes
pertenece a Z.
2) w tiene arcos que salen de el y w esta en Z
En la figura 1.8.1 se muestra un GAD. Si por ejemplo X = {2} , Y = {3} y Z =
{1}, entonces vemos que X y Y están d-separadas por Z. Se dice que el camino
2 ← 1 → 3 esta bloqueado por 1 ∈ Z; también, si Z = {4}, el camino 2 → 4 ← 3 esta
bloqueado por 4, ya que todos sus descendientes están fuera de Z. X y Y no están
d-separados por Z = {1, 5}, ya que al conocer la consecuencia 5, hace que 2 y 3 se
vuelvan dependientes.
1
2
3
4
5
Fig. 1.8.1 Grafo acíclico dirigido (DAG)
Definición 1.8.2 (Pearl, 1988) Un DAG D es un mapa-I de un modelo de
dependencia si cada condición d-separación en D corresponde a una relación de
independencia en M.
(X ⊥ Y | Z)D ⇒ (X ⊥ Y | Z)M
(1.8.1)
11
_________________________________________________________________________
un DAG es un mapa-I mínimo de M si ninguno de sus arcos puede ser
borrado sin que D deje de ser un mapa-I.
Definición 1.8.3 (Pearl, 1988) Dada una distribución de probabilidad P en un
→
conjunto de variables U, un DAG D = (U , E ) se llama red Bayesiana si y solo si D
es un mapa-I mínimo de P.
En palabras podemos decir que una red bayesiana es un grafo acíclico
dirigido que refleja las relaciones de independencias/dependencias contenidas en
un modelo, descrito por una distribución de probabilidad. Otra cuestión que no se
ha mencionado y que es en demasía importante, es que la red Bayesiana contiene
en cada vértice las probabilidades condicionales de los valores posibles de la
variable dados los padres (en el caso de un nodo raíz se tienen las probabilidades
marginales). Si por ejemplo tenemos variables binarias (i.e. el dominio es de dos
valores), y una variable tiene dos padres, entonces en el nodo se almacenará una
tabla con 2*2*(2 - 1) = 4 probabilidades(Esto por que la suma de probabilidades
debe ser uno). En el caso de un nodo raíz solo se guardaran dos probabilidades
que son las probabilidades marginales de cada valor.
Definición 1.8.4 (Pearl, 1988) Sea M un modelo de dependencia definido en un
conjunto U = { X 1 , X 2 ,..., X n } de elementos, y sea d un ordenamiento
( X 1 , X 2 ,..., X i ,...) de los elementos de U. El límite estrato(boundary strata) de M
relativo a d es un conjunto ordenado de subconjuntos de U, ( B1 , B2 ,...Bi ,...) , tal que
cada Bi es un límite de Markov de Xi con respecto a el conjunto
U ( i ) = { X 1 , X 2 ,..., X i −1 } , i.e. Bi es un conjunto mínimo que satisface Bi ⊆ U ( i ) y
( X i ⊥ U ( i ) − Bi | Bi ) . El DAG creado designando cada Bi como padres del vértice
Xi es un Mapa-I mínimo de M.
La definición anterior es muy importante para el algoritmo presentado en
este trabajo, ya que, al trabajar bajo el esquema de tal definición, se garantiza que
la red obtenida será un Mapa-I mínimo del modelo, i.e. una red Bayesiana.
Definición 1.8.5 Padres Markovianos. Sea V = { X 1 ,..., X n } un conjunto ordenado
de variables, y sea P la distribución de probabilidad de estas variables. Un
conjunto Π j se llama Padres Markovianos de Xj si es el conjunto mínimo de
predecesores que Xj que mantiene a Xj independiente del resto de los
predecesores. En otras palabras, Π j es cualquier subconjunto de {X1,...,Xj-1} que
satisface:
P ( X j | π j ) = P ( X j | X 1 ,..., X j −1 )
(1.8.2)
12
_________________________________________________________________________
y ningún subconjunto propio de PAj satisface la ecuación (1.8.2)
De la ecuación (1.3.11) podemos ver que la probabilidad conjunta de un
conjunto de variables la podemos expresar como un producto de probabilidades
condicionales, ahora bien, si tomamos en cuenta la definición 1.8.5, claramente
vemos que si la distribución satisface tal definición, entonces ésta se puede
descomponer como sigue:
P ( x1 ,..., x n ) = ∏ P( xi | π i )
(1.8.3)
i
por ejemplo el DAG presentado en la fig.1.8.1 induce la siguiente descomposición
P( x1 , x 2 , x3 , x 4 , x5 ) = P( x1 ) P( x 2 | x1 ) P( x3 | x1 ) P( P( x 4 | x 2 , x3 ) P( x5 | x 4 )
(1.8.4)
Como ya mencionamos anteriormente, la red guarda en cada uno de sus
nodos una tabla de probabilidades condicionales. Estas probabilidades son las
que se necesitan en la ecuación (1.8.4) para poder calcular la probabilidad
conjunta. De aquí que la red bayesiana guarda en sus vértices toda la distribución
conjunta de probabilidad de las variables en cuestión. Esta es otra de las grandes
virtudes de una red bayesiana, el hecho de poder almacenar en forma muy
económica la distribución conjunta de las variables.
13
_________________________________________________________________________
Capítulo 2.
Aprendizaje de Redes Bayesianas
2.1 Problemas en el Aprendizaje de Redes Bayesianas
Hasta ahora hemos descrito y definido lo que es una red bayesiana, así
como sus usos dentro de los sistemas expertos. En este capítulo se describen los
problemas típicos involucrados en el aprendizaje de las redes Bayesianas.
Básicamente podemos decir que los subproblemas relacionados con el
aprendizaje de redes bayesianas son los siguientes (Cruz-Ramírez, 2001):
•
•
•
•
•
Aprendizaje de la estructura
Aprendizaje de los parámetros
Propagación de probabilidades (o propagación de evidencia)
Determinación de valores faltantes
Descubrimiento o determinación de variables ocultas
Aprendizaje de la estructura. Consiste en la determinación de la topología de la
red, es decir, la construcción del grafo que contenga las relaciones
independencia/dependencia entre las variables. Básicamente hay dos enfoques: el
enfoque tradicional que consiste en aprender la red bayesiana a partir del
conocimiento de un experto, y el enfoque automático, utilizando técnicas que caen
dentro de minería de datos o KDD.
Aprendizaje de los parámetros de la red. Determinada la topología, es posible
entonces calcular las probabilidades asociadas a cada nodo, marginales o
condicionales, dependiendo si se trata de un nodo raíz o no. Al cálculo de estas
probabilidades se le llama aprendizaje de los parámetros. El aprendizaje de los
parámetros puede realizarse a partir de un experto, a partir de los datos o incluso
combinando los dos enfoques. La obtención de las probabilidades a partir del
conocimiento de un experto puede resultar demasiado laborioso, por lo que se han
formalizado diferentes métodos para la determinación de las probabilidades
condicionales a partir de datos, incluyendo variables continuas y discretas
(Neapolitan, 2003). En nuestro caso no trataremos este problema, ya que no es el
objetivo de este trabajo. Sin embargo, sí utilizamos el aprendizaje de los
parámetros, por que en la sección de clasificación necesitamos hacer inferencia y
para ello es necesario tener las probabilidades condicionales de la red. Para
calcular las probabilidades usamos el principio de máxima verosimilitud,
(Neapolitan, 2003). Consiste en tomar las probabilidades como las frecuencias
relativas.
14
_________________________________________________________________________
Propagación de probabilidades (inferencia). Esta es la parte más aplicada de
las redes Bayesianas. Dado que se conoce el valor de alguna(s) variable(s)
podemos actualizar las probabilidades del resto de las variables; esto
comúnmente se llama propagación de probabilidades, propagación de evidencia o
inferencia. En el caso de tener dos variables es directo el asunto, ya que solo
tenemos que aplicar la regla de bayes. En el caso de tener que propagar hacia
varias variables que no son descendientes o ancestros directos la cuestión se
complica bastante. Se han desarrollado diversos algoritmos para la inferencia en
redes bayesianas con una sola raíz (árboles) y para redes bayesianas generales2.
En el caso de árboles y poliárboles, Nilsson (Nilsson, 1998) describe tres métodos
para realizar inferencia que son: top-down (en el caso de tener evidencia arriba),
bottom-up (en el caso de tener evidencia abajo) y explaining away (en el caso de
tener evidencia tanto arriba como abajo). Estos métodos utilizan la regla de bayes
(ecuación 1.3.12) y la ley de la probabilidad total (ecuación 1.3.5). El algoritmo
más renombrado en redes bayesianas para realizar inferencia es el desarrollado
por Pearl (Pearl, 1998) y que se llama paso de mensajes. En términos generales
consiste en propagar la evidencia hacia los vecinos y de estos a sus vecinos y así
sucesivamente. El presente trabajo tampoco se centra en estas cuestiones, por lo
que no se discute con mayor detalle cada uno de los algoritmos mencionados. La
mayor parte de la inferencia realizada es bastante simple, sobre todo en las redes
generadas por bayes-N, ya que consiste en revisar las tablas de probabilidades
condicionales almacenadas en el nodo, para realizar clasificación. Fue necesario
implementar un algoritmo de inferencia general, pero no se trata del algoritmo de
Pearl (Pearl, 1998), se trata de uno descrito por Nilsson (Nilsson, 1998) y que él
llama método general. Dado que se usa para las pruebas realizadas en este
trabajo, será descrito en el capítulo 5.
Determinación de datos faltantes. El problema de datos faltantes se
presenta frecuentemente, y es que hay veces que por alguna razón no es posible
obtener el valor de alguna variable. El problema de determinar que valor es el más
probable de que suceda en esa instancia es lo que se llama determinación de
datos faltantes, o valores faltantes.(Cruz-Ramírez, 2001).
Determinación de variables ocultas. En muchas ocasiones es posible que
no se hayan determinado algunas variables que eran importantes para la
explicación del fenómeno bajo estudio, y es notado que existe un influencia en los
datos que no es percibida fácilmente, entonces es posible postular la existencia de
alguna o algunas variables ocultas como responsables de explicar esta producción
anormal de los datos(Cruz-Ramírez., 2001).
2
Redes Bayesianas no restringidas a una sola raíz y un solo camino entre cualquiera de dos nodos (árboles) o
restringidas a un solo camino entre dos nodos cualquiera (poliárboles). (Nilsson, 1998). O redes restringidas
como la red Naïve-Bayes (Langley, et. al., 1992).
15
_________________________________________________________________________
2.2 Aprendizaje de la Estructura
Básicamente existen tres enfoques para de determinar la topología de una red
Bayesiana: de forma manual o tradicional, de forma automática y el enfoque
Bayesiano que puede ser visto como una combinación de los dos anteriores
(Cruz-Ramírez, 2001).
2.2.1 Enfoque Tradicional.
En el enfoque tradicional, la estructura de una red bayesiana es dada
generalmente por el experto humano ayudado por el ingeniero del conocimiento.
Aunque ésta es una tarea bastante difícil y tardada, la construcción de la
estructura realizada de esta forma puede pensarse como la determinación de las
relaciones entre las variables de una manera causal. Esto significa que si dos
variables están conectadas, se piensa que la primera es la causa de la segunda,
representando esta relación con una flecha que va de la primera variable a la
segunda. Este proceso se puede hacer de manera recurrente; para cada par de
variables el experto necesita determinar si una variable es causa de la otra. Pearl
y Heckerman (Heckerman 1997; Heckerman 1998; Pearl 2000) señalan que si una
red es construida de esta forma, entonces la red incorpora conocimiento causal.
Probablemente este proceso resulte bastante difícil, sin embargo si lo combinamos
con datos estadísticos, entonces las redes construidas de esta forma pueden ser
más consistentes (Cruz-Ramírez, 2001).
2.2.2 Aprendizaje a Partir de Datos
Este enfoque ha sido el más explorado durante los últimos años, y existe una gran
variedad de algoritmos para la obtención del estructura de la red bayesiana a partir
de datos (Cheng, 1998; Cooper & HersKovits, 1992; Pearl, 1988; Spirtes et al.,
1991). La motivación de este enfoque surge, obviamente, para evitar el enfoque
tradicional en el que se extraía el conocimiento del experto. Con este enfoque el
tiempo de ingeniería del conocimiento se reduce considerablemente, al determinar
la estructura de manera automática. El aprendizaje de redes bayesianas a partir
de datos se divide en dos: métodos basados en búsquedas y métodos basados en
restricciones.
2.2.2.1 Algoritmos Basados en Búsquedas
La determinación de la estructura de la red es vista como un problema de
selección del modelo, en este caso probabilista. Los estadísticos, que
comúnmente trabajan con este tipo de problemas, usan dos enfoques para
resolver este problema: selección del modelo y selección del modelo promedio
(Selecting Model averaging), el primero consiste en seleccionar un solo modelo
“bueno” de entre todos los posibles modelos, y usarlo como si fuera el modelo
correcto, el segundo enfoque consiste en seleccionar un número manejable de
16
_________________________________________________________________________
modelos buenos de entre todos los modelos posibles y
modelos son exhaustivos (Heckerman 1995).
pretender que estos
A partir de lo anterior surgen varias cuestiones, entre ellas; ¿proveen estos
enfoques resultados apropiados cuando son aplicados al aprendizaje de la
estructura de una red bayesiana?, si es así, ¿Cómo buscamos buenos modelos?,
¿cómo decidimos si un modelo es o no “bueno”?.
La pregunta de si el modelo es apropiado es un poco difícil de contestar; sin
embargo algunos investigadores han demostrado que la selección de un simple
modelo a menudo da predicciones bastante exactas (Cooper & Herskovits, 1992,
Heckerman et al., 1995). Para la búsqueda del modelo, existen diferentes
enfoques de optimización, como los algoritmos genéticos (Larrañaga ) o
algoritmos “Greedy” (Cooper & Herskovits ). Ahora bien, para saber que tan bueno
es el modelo, se han desarrollado diferentes criterios para evaluar el modelo (en
este caso la estructura de la red bayesiana aprendida), llamándose, en general,
criterios de bondad de ajuste. Entre ellos figuran: método de calificación
Bayesiano (Cooper & Herskovits, 1992; Heckerman, 1994; Ramoni y Sebastián,
1996), métodos basados en entropía (Herskovits, 1991), método de evaluación
MDL (minimum description length) (Susuki, 1996; Lam and Bacchus, 1994;
Bouckaert, 1994) y método de evaluación MML(minimum message length)
(Wallace, 1996).
En general, el problema de la selección del modelo consiste en encontrar
un modelo que, basado en datos, incluya una aproximación de la distribución de
frecuencias relativas de dichos datos (i.e. distribución de probabilidad), pero que
además sea un modelo de dimensiones razonables; tal y como lo dice la siguiente
definición.
Definición 2.2.2.1.1(Neapolitan, 2003) Sea U conjunto de variables y sea D la
base de datos sobre U y sea N el número de casos en D. Sea S un criterio de
evaluación sobre alguna clase de modelo de las variables en U. Sea P la
distribución de probabilidad conjunta de las variables determinada a partir de D. Y
sean M1 y M2 dos modelos a evaluar.
1. Para N suficientemente grande, si M1 incluye a P y M2 no, entonces
score( D, M 1 ) > score( D, M 2 )
2. Para N suficientemente grande, si M1 y M2 incluyen a P y M1 tiene
dimensión menor que M2
score( D, M 1 ) > score( D, M 2 )
17
_________________________________________________________________________
La idea central del enfoque de búsquedas radica en encontrar el modelo
mas parsimonioso que describa de mejor manera la distribución de probabilidad
de los datos, basándose en algún criterio como el de S definido por Neapolitan.
Cuando se trata de pocas variables podemos realizar una búsqueda
exhaustiva, es decir evaluar cada posible estructura y escoger la mejor, de
acuerdo el criterio de evaluación. Sin embargo, cuando el número de variables no
es pequeño se vuelve intratable, computacionalmente hablando, una búsqueda
exhaustiva. Robinson (Robinson, 1977) demostró que el número de GADs para n
variables esta dado por la siguiente función recursiva:
n
⎛n⎞
f (n) = ∑ (−1) i +1 ⎜ ⎟2 i ( n −i ) f (n − i )
⎝i⎠
i =1
f ( 0) = 1
f (1) = 1
n>2
(2.2.2.1.1)
solo para darse una idea, f(2) = 3, f(3) = 25, f(5) = 29,000 y f(10) = 4.2 x
10 . Es claro que el número de GADs posibles es enorme. Ya mencionábamos
que se han desarrollado diferentes algoritmos para este enfoque. Uno de los
principales problemas encontrados en este tipo de métodos es la cantidad tan
grande de posibles estructuras; es por ello que se han desarrollado diferentes
heurísticas para no explorar todo el espacio de búsqueda, entre ellos figuran los
algoritmos genéticos (Larragaña) y algoritmos “greedy” como el K2 (Cooper &
Herskovits, 1992).
18
2.2.2.1 Algoritmos Basados en Restricciones
Este tipo de algoritmos asumen lo siguiente: dado un conjunto de
independencias condicionales en una distribución de probabilidad, hay que
encontrar el GAD que contenga todas y solamente estas independencias
condicionales (Neapolitan, 2003). Entonces, la clave de estos algoritmos es
determinar las relaciones de independencia (marginal o condicional)3, contenidas
implícitamente en los datos, con alguna medida de independencia condicional.
Una medida comúnmente usada para probar independencia marginal e
independencia condicional es la información mutua y la información mutua
condicional(Shannon & Weaver, 1949, Pearl, 1988), respectivamente. Si
contáramos con un ordenamiento de las variables, y el límite de Markov (definición
1.7.3) de cada variable podríamos construir la topología de la red dirigiendo arcos
desde los elementos del límite de Markov hasta la variable en cuestión. Si solo
3
En adelante cuando escribamos independencia se entenderá que nos referimos a cualquiera de las dos,
marginal o condicional
18
_________________________________________________________________________
contáramos con el ordenamiento, de las variables, entonces tendríamos que
determinar de alguna forma el conjunto mínimo de variables que separa a cada
variable de sus predecesores que no son padres, i.e. el límite de Markov. La forma
en que la mayoría algoritmos resuelven el problema de determinar el conjunto de
padres Markovianos, es llevando a cabo muchas pruebas de Independencia
condicional. El hecho de tener el ordenamiento de las variables como un
conocimiento a priori, es visto como una desventaja en los algoritmos de
construcción de redes bayesianas, ya que en dominios muy complejos donde hay
muchas variables y sus relaciones no son muy claras ni para el experto humano,
no es posible contar o determinar de manera adecuada el ordenamiento de las
variables[ Referencia ]. Es por eso que algunos autores han ideado algoritmos
más generales que prescindan de un ordenamiento. Solo por mencionar algunos,
(Spirtes et al., 1990; Spirtes and Glymour, 1991; Martínez-Morales, 1995; Cheng,
1998).
Existen algunos otros algoritmos que tampoco reciben un ordenamiento,
pero casi siempre construyen un grafo acíclico parcialmente orientado (pGAD. i.e.,
pattern GAD)(Heckerman 1997; Friedman and Goldszmidt 1998). Ejemplo de este
tipo es el Bayes9 (Cruz-Ramírez, 2001).
Estos dos enfoques para el aprendizaje de redes Bayesianas a partir de
datos son los más usados, aunque se ha sugerido un enfoque híbrido(CruzRamírez, 2001), es decir, combinar algún algoritmo de restricciones con uno de
búsquedas para tratar de aprovechar las ventajas de los dos enfoques y evadir las
desventajas de los mismos que en breve se tratará.
Hemos hablado de los enfoques e incluso de una posible combinación de
los dos para aprovechar las ventajas y evadir las desventajas de los enfoques,
pero ¿cuáles son las ventajas y cuales son las desventajas de ambos enfoques?.
La principal ventaja de los algoritmos basados en restricciones es su
velocidad, en redes no tan densas. Otra ventaja es que cuando se trata de bases
de datos muy grandes, las pruebas de independencia se realizan con mayor
confiabilidad. Pero resulta que en caso contrario, es decir cuando el volumen de
datos es pequeño, la confiabilidad de las pruebas no es buena; en otras palabras,
debido a que este tipo de algoritmos necesitan realizar pruebas de independencia
condicional, es necesario que el volumen de datos sea lo suficientemente grande,
sobre todo cuando el orden del conjunto condicionante es grande. Otra desventaja
surge con la necesidad de especificar un umbral para llevar a cabo la prueba de
independencia.
Una de las ventajas de los algoritmos basados en búsquedas es la no
necesidad de especificar un umbral. Otra ventaja es que incluyen implícitamente el
principio de la navaja de Occam (Cruz-Ramírez, 2001), i.e., las métricas usadas
por estos algoritmos favorecen modelos simples(Recordemos que el principio de
19
_________________________________________________________________________
la navaja de Occam sugiere que el mejor modelo es aquel que, además de
explicar los datos, es el más simple). Entre las desventajas, ya mencionábamos
anteriormente que se encuentra la intratabilidad computacional del problema
(espacio de búsqueda enorme). Esta desventaja ha sido evadida por algunos
autores introduciendo heurísticas e incluso asumiendo que existe un orden en el
conjunto de variables(Cooper & Herskovits, 1992), como ya explicábamos antes.
20
_________________________________________________________________________
Capítulo 3.
Familia de Algoritmos Bayes
Existen diversos problemas en la investigación científica en los que hay una
estructura particular en las relaciones entre las variables bajo consideración. En
los problemas de este tipo hay una variable dependiente o respuesta, y un
conjunto de variables independientes o explicativas (por ejemplo en diseño
experimental, modelos de regresión, diagnóstico médico, predicción, problemas de
clasificación, entre otros). La hipótesis subyacente es que el comportamiento de la
variable dependiente puede ser explicada como resultado de la acción de las
variables dependientes. En este capitulo presentamos la familia de algoritmos
Bayes, que abordan el problema anterior(con excepción de Bayes9). Describimos
la filosofía detrás de esta familia de algoritmos y la evolución que han sufrido para
intentar resolver ciertos problemas encontrados en ellos.
Esta familia de algoritmos son del tipo basados en restricciones y se han
venido desarrollando desde hace ya algunos años (Martínez-Morales, 1995; CruzRamírez, 1997; Cruz-Ramírez, 2001).
3.1 Prueba Estadística para la Independencia Marginal y Condicional
Como ya mencionábamos en el capítulo anterior, los algoritmos basados en
restricciones tratan de reflejar las independencias condicionales de la variables en
la base datos en la estructura de la red Bayesiana, para lo cual es necesario llevar
a cabo una serie de pruebas de independencia. Las pruebas realizadas por
Bayes-N y en general por la familia de algoritmos Bayes, están basadas en
medidas de información definidas en el campo de la teoría de la información como
información mutua e información mutua condicional (Kullback, 1959; Quinlan,
1993; Martínez-Morales, 1995). A continuación se exponen el conjunto de
ecuaciones que definen entropía, entropía condicional, información mutua e
información mutua condicional.
Sean X, Y variables aleatorias discretas, y sean x, y valores específicos
para X, Y respectivamente. Sea Z un conjunto de variables aleatorias y sea z una
combinación específica de las variables. ∑ denota la suma sobre todos los
x
valores de X.
Definición 3.1.1(Shannon, 1948). Entropía.
H ( X ) = −∑ p ( x) log p ( x)
x
(3.1.1)
donde p(x) es la probabilidad P(X=x)
21
_________________________________________________________________________
Definición 3.1.2 (Shannon, 1948). Entropía condicional de X dado Y.
H ( X / Y ) = −∑∑ p ( x, y ) log p ( x / y )
x
(3.1.2)
y
Definición 3.1.3 (Kullback, 1959; Quinlan, 1993;
Información mutua (ganancia de información)
I ( X , Y ) = H ( X ) − H ( X / Y ) = ∑ p ( x, y ) log
x, y
p ( x, y )
p( x) p( y )
Definición 3.1.4 3 (Kullback, 1959; Quinlan, 1993;
Información mutua condicional.
Martínez-Morales, 1995).
(3.1.3)
Martínez-Morales, 1995).
I ( X ,Y | Z ) = H ( X / Z ) − H ( X / Z ,Y ) =
∑ p( x, y, z ) log
x, y , z
p ( x, y | z )
p( x | z ) p( y | z )
(3.1.4)
La entropía es interpretada como el grado de incertidumbre de una variable.
Si por ejemplo una variable toma dos valores con una probabilidad de 0.5 para
cada valor, entonces se dice que la variable es muy incierta, y de hecho se
encuentra en la situación de máxima entropía, y por lo tanto, de
incertidumbre(Shannon, 1948).
La entropía condicional es interpretada como el grado de incertidumbre que
tiene una variable dado que conocemos otra. En otras palabras, que tan incierta
permanece la variable X dado que conocemos otra variable Y.
Si combinamos la entropía y la entropía condicional, entonces podemos
encontrar la ganancia de información. Esta se define como la diferencia de la
entropía menos la entropía condicional. Analicemos esta ecuación. H(X) define el
grado de incertidumbre de X y H(X|Y) define el grado de incertidumbre que tiene X
dado que conocemos a Y, entonces, si H(X) es igual a H(X|Y) entonces Y no está
haciendo que X sea menos incierta; i.e. Y no proporciona información acerca de X;
Por lo que I(X,Y) es igual a cero. (Notemos que H ( X ) ≥ H ( X | Y ) ). A esta medida
se le llama ganancia de información precisamente porque eso es lo que refleja al
restar las entropías (entropía y entropía condicional). Ahora bien, dado que I(X,Y)
= I(Y,X) a esta cantidad se le ha llamado información mutua. De aquí en adelante
usaremos este término.
La ecuación 3.1.4 define la ganancia de información condicional. La cual
podemos entenderla más o menos así: supongamos que conocemos la entropía
de X dado Z y ahora introducimos una nueva variable Y y calculamos la entropía
condicional de X dado Z y Y. Si restamos estas dos entropías condicionales lo que
22
_________________________________________________________________________
obtendremos será una nueva cantidad, que es la ganancia de información
adquirida con el conocimiento de Y, adicional al de Z, hacia X. Al igual que en el
caso de la información mutua, I(X,Y|Z)= I(Y,X|Z). Es por eso que a esta ganancia
de información condicional se le llama información mutua condicional.
El conjunto de definiciones descritas supone que se conocen, de manera
teórica, todas las probabilidades; esto casi nunca es posible, por lo que tienen que
ser estimadas a partir de datos. Bajo este esquema, denotaremos en adelante a
∧
∧
los estimadores de H y I como: H , I .
Prueba de independencia de Kullback (Kullback, 1959). Sea X, Y, Z variables
aleatorias discretas.
Por X ⊥ Y queremos decir que X y Y son marginalmente independientes, y por
X⊥Y,Z queremos decir que X y Y son condicionalmente independientes dado Z.
La prueba de independencia marginal entre X y Y puede ser establecida en
términos de medidas de ganancia de información como:
H 0 : I ( X / Y ) = 0, ( X ⊥ Y )
H 1 : I ( X / Y ) > 0, ( X ⊥
/ Y)
(3.1.5)
La prueba de independencia condicional de X y Y dado Z, tal y como la
propuso Kullback, esta basada en la información mutua condicional de X y Y dado
Z; las hipótesis a ser probadas son:
H 0 : I ( X / Z , Y ) = 0, ( X ⊥ Y , Z )
H 1 : I ( X / Z , Y ) > 0, ( X ⊥
/ Y,Z)
(3.1.6)
Kullback demostró (Kullback, 1959) que bajo la hipótesis nula H0
∧
(independencia marginal o independencia condicional) el estadístico T = 2 N I se
distribuye asintóticamente como la variable chi-cuadrada (con grados de libertad
apropiados). Bajo H1, T se distribuye como una chi-cuadrada no central.
En las secciones subsecuentes se describen los algoritmos Bayes2, Bayes5
y Bayes9. El seudocódigo y análisis de los algoritmos se extrajo de (CruzRamírez, 2001)
3.2 Bayes2
Este algoritmo fue propuesto, originalmente, por Martínez-Morales (MartínezMorales, 1995) y extendido después por Cruz-Ramírez (Cruz-Ramírez, 1997). La
idea básica detrás de Bayes2 es que la medida de información de la ecuación
23
_________________________________________________________________________
3.1.3 puede formar una sucesión descendente de variables; i.e., las variables
pueden ser ordenadas de acuerdo a la ganancia de información que proveen a
una variable dependiente de máximo a mínimo. La definición 1.8.4 establece que
si existe un orden de las variables, entonces es posible inducir un grafo acíclico
dirigido (GAD); y dado que una red Bayesiana es por definición un GAD, entonces
este orden nos permite construir una red Bayesiana.
Procedimiento Bayes2 (Martínez-Morales, 1995)
Sea X la variable aleatoria dependiente y sea Y1, Y2, ..., Yn el conjunto no
ordenado de variables aleatorias independientes.
Inicio del procedimiento bayes2
1. Calcular el valor de la información mutua (ecuación 3.1.3) que cada variable
Yi ( 1 ≤ i ≤ n ) proporciona a X y ordenarlas, de forma descendente, de
acuerdo a este valor. Las variables ordenadas serán etiquetadas ahora
como Y(1), Y(2), ...,Y(n). Se prueba la hipótesis H0 (las variables son
marginalmente independientes) para cada Y(i). Si se rechaza la hipótesis
nula, entonces dibujar un arco desde Y(i) ( 2 ≤ i ≤ n ) a X.
2. Calcular el valor de la información mutua condicional(ecuación 3.1.4) que
cada variable Y(i) (2 ≤ i ≤ n) provee a X dado Y(1). Después usar la ecuación
3.1.6 para ver si se rechaza o acepta H0 (Y(i) y X son independientes dado
Y(1)). Si se acepta, entonces remover el arco de Y(i) a X. Si se rechaza dejar
intacto el arco.
3. Hacer X = Y(1) y borrar Y(1) del conjunto de variables aleatorias
independientes. Hacer el número de variables independientes n = n – 1. si n
≥ 2, entonces ir al paso 1; de lo contrario parar.
fin del procedimiento Bayes2
Tal como lo habíamos mencionado, Bayes2 requiere la especificación de la
variable dependiente. Esto porque en el primer paso calcula la información mutua
entre esta variable y el resto, para formar posteriormente una lista ordenada de las
variables dependientes. En este mismo paso el algoritmo lleva a cabo una serie de
pruebas de independencia marginal entre la variable dependiente y las variables
independientes.
Una de las suposiciones fuertes de Bayes2 es que toma a Y(1) como el
conjunto condicionante. Si Y(1) es la variable que provee más información, es
posible que al conocerla las demás variables, o al menos algunas, se vuelvan
irrelevantes. En otras palabras, podemos eliminar los arcos que hay de estas
variables a la variable dependiente, si es que se cumple la independencia
condicional.
El primer problema que encontró Martínez-Morales (Martínez-Morales,
1995) en este algoritmo es que no se tiene control del nivel de significancia global;
i.e., en bases de datos muy grandes ganancias de información pequeñas resultan
24
_________________________________________________________________________
bastante significativas. Bayes2 solo incluye el control de la significancia local, pero
no de manera global. Para corregir este problema Martínez-Morales (MartínezMorales, 1995) sugiere realizar lo que se conoce como ajuste de Bonferroni. Este
ajuste es una de las mejoras que incluye BayesN. En la sección 4.4 se describirá
con detalle en que consiste este método.
Uno de los principales problemas (o limitación) de Bayes2 es que
solamente realiza pruebas de independencia condicional entre dos variables con
una variable como único elemento del conjunto condicionante; y en algunos casos
la d-separación puede darse con un conjunto condicionante de más de un
elemento. La consecuencia del problema anterior es que el algoritmo genera redes
muy densas, es decir, con muchos arcos. El sobreajuste(overfitting) obtenido es
malo, ya que estaríamos contradiciendo el criterio de la navaja de Occam.
Además, no obtiene todas las independencias condicionales contenidas en los
datos, contradiciendo así la filosofía de los algoritmos basados en restricciones, al
cual pertenece Bayes2.
3.3 Bayes5
Para corregir este problema se propone una primer mejora a Bayes2 y nace
Bayes5. La mejora consiste en el incremento en la cardinalidad del conjunto
condicionante. En este nuevo algoritmo se permite condicionar hasta con cinco
variables(si es que se puede). Este es el procedimiento.
Procedimiento Bayes5
Sea X la variable aleatoria dependiente y sea Y1, Y2,..., Yn el conjunto no
ordenado de variables aleatorias independientes.
Inicio del procedimiento Bayes5
1. Calcular el valor de la información mutua (ecuación 3.1.3) que cada variable
Yi ( 1 ≤ i ≤ n ) proporciona a X y ordenarlas, de forma descendente, de
acuerdo a este valor. Las variables ordenadas serán etiquetadas ahora
como Y(1), Y(2), ...,Y(n). Se prueba la hipótesis H0 (las variables son
marginalmente independientes) para cada Y(i). Si se rechaza la hipótesis
nula, entonces dibujar un arco desde Y(i) ( 2 ≤ i ≤ n ) a X.
2. Calcular el valor de la información mutua condicional(ecuación 3.1.4) que
cada variable Y(i) (2 ≤ i ≤ n) provee a X dado Y(1). Después usar la ecuación
3.1.6 para ver si se rechaza o acepta H0 (Y(i) y X son independientes dado
Y(1)). Si se acepta, entonces remover el arco de Y(i) a X. Si se rechaza dejar
intacto el arco.
3. Sea Y(1), Y(2), ..., Y(k) el conjunto ordenado de variables que tienen arco
directo hacia X; 1 ≤ k ≤ n.
For a = 2 to a = 5
Let b = a + 1
25
_________________________________________________________________________
If Y(b) ≠ Ø
Calcular el valor de la información mutua condicional (3.1.4)
que cada variable Y(b) provee a X dado el conjunto Y(1), …,
Y(a). Usar la ecuación 3.1.6 para verificar si la hipótesis nula
H0 es aceptada. Si es aceptada entonces remover el arco de
Y(b) a X. Si es rechazada, entonces dejar intacto el arco.
4. Hacer X = Y(1) y borrar Y(1) del conjunto de variables aleatorias
independientes. Hacer el número de variables independientes n = n – 1. si n
≥ 2, entonces ir al paso 1; de lo contrario parar.
fin del procedimiento Bayes5
Como puede observarse en el procedimiento, la única diferencia es que se
agrega un paso extra; el cual permite, cuando sea posible, llevar acabo pruebas
de independencia condicional desde segundo hasta quinto orden como máximo.
Bayes5 supera a Bayes2, pero aun se siguen teniendo problemas de
sobreajuste (overfitting), i.e., se siguen obteniendo muchos arcos que no van.
Las comparaciones que Cruz-Ramírez hace en su trabajo para determinar
el sobreajuste en las redes obtenidas por Bayes2 y Bayes5 es con respecto a
redes de oro (redes de las cuales se conoce su estructura original. Normalmente
se tiene la red de oro y se generan datos sintéticos a partir de ella. Se supone que
un buen algoritmo podría recobrar la estructura original, o al menos muy cercana).
Aunque Bayes5 mejora a Bayes2, sigue poniendo demasiados arcos, aun
después de aumentar la cardinalidad del conjunto condicionante.
Otro problema encontrado en estos dos algoritmos es el orden ancestral
inducido. Inicialmente se presentó como una virtud, pero Cruz-Ramírez (2001)
encontró que este orden es uno de los principales problemas en estos algoritmos,
ya que en algunos casos hace imposible d-separar variables. Esto es fácil de
entender. Puede ser que en los datos una variable Yi sea condicionalmente
independiente de X dada otra variable Yj, pero si Yj estaba antes en el orden
ancestral, entonces ya salió, es decir ya pasó a ser la variable dependiente mucho
antes en el algoritmo. Por lo tanto Yi no podrá ser d-separado de X.
Parta resolver este problema, Cruz-Ramírez (Cruz-Ramírez, 2001) presentó
otro algoritmo llamado Bayes9. Este algoritmo puede llevar a cabo pruebas de
independencia condicional de orden superior a uno, además prescinde del orden
ancestral generado por Bayes2 y Bayes5.
Este algoritmo es diferente a los dos algoritmos descritos anteriormente. En
forma muy breve podemos decir que Bayes9 sigue usando las medidas de
información descritas anteriormente, pero este algoritmo no genera un GAD.
26
_________________________________________________________________________
Genera lo que se llama pGAD, un grafo acíclico parcialmente orientado. En el
apéndice A se describe el procedimiento Bayes9, para una descripción a detalle
consultar el trabajo original (Cruz-Ramírez, 2001).
En este trabajo no se tiene como objetivo tratar de reconstruir la red de oro,
sino, encontrar un modelo Bayesiano que sea buen clasificador, aprovechando las
independencias condicionales reflejadas en una red Bayesiana, y que de paso que
tenga un buen ajuste con los datos. En el capítulo 5 se hablará del desempeño del
algoritmo como clasificador y además se hará la comparación de la bondad de
ajuste de la red generada con los datos utilizando la métrica llamada MDL
(Minimum Description Length). En el capítulo 5 se describirá con detalle esta
métrica.
En el siguiente capítulo se describe el algoritmo BayesN y en forma breve
se presenta la herramienta de software en la que se implementó el algoritmo.
27
_________________________________________________________________________
Capítulo 4.
BayesN
BayesN es un algoritmo descendiente de Bayes2 (Martínez-Morales, 1995) y
Bayes5 (Cruz-Ramírez, 2001), y surge a partir de dos propuestas hechas como
solución a problemas encontrados en Bayes2 y Bayes5: control de significancia
(Martínez-Morales, 1995)(problema en bayes2 y bayes5), y pruebas de
independencia condicional de orden superior (Cruz-Ramírez, 2001)(solo en
bayes2).
4.1 Longitud del Conjunto Condicionante Variable
El primer aspecto que incorpora BayesN es el control de la longitud del conjunto
condicionante (profundidad) que interviene en la etapa de eliminar arcos. En
Bayes2 solo se permite condicionar con una sola variable, la más informativa. En
Bayes5 se permite condicionar hasta con 5 variables, seleccionando las variables
más informativas. En BayesN la profundidad máxima la especifica el usuario, de
esta forma el puede decidir si quiere que el algoritmo lleve a cabo pruebas con
dos, tres, seis o el número de variables que desee(siempre y cuando sea posible).
De esta forma podemos evitar que el algoritmo lleve a cabo pruebas de
independencia condicional innecesarias, que por cierto son muy costosas en
tiempo, si sabemos de antemano que los datos no reflejan correlaciones que
pudieren tener independencias condicionales entre variables dadas mas de tres
variables, por ejemplo.
4.2 Control de Significancia
Uno de los problemas encontrados desde los orígenes de la familia de algoritmos
Bayes, y que no se había confrontado, es el nivel de significancia. Este problema
surge cuando se realizan muchas pruebas de hipótesis. La primer sugerencia
hecha para resolver este problema es la incorporación de lo que se conoce como
ajuste de Bonferroni (Martínez-Morales, 1995; Bickel & DokSum, 1977; Bland &
Altman, 1995). A continuación se describe dicho método.
4.2.1 Ajuste de Bonferroni
El ajuste de Bonferroni se basa en lo siguiente: si probamos una hipótesis nula, la
cual es verdadera, usando un nivel de significancia de 0.05, tenemos una
probabilidad de 0.95 de obtener una conclusión correcta. Si probáramos dos
hipótesis tenemos una probabilidad de 0.95*0.95=0.90 de que ninguna de las
pruebas resulte significativa; y si probáramos 20 hipótesis, la probabilidad de que
ninguna prueba será significativa es de 0.9520=0.36. Esto da una probabilidad de 1
- 0.36 = 0.64 de obtener al menos un resultado significativo.
28
_________________________________________________________________________
En nuestro caso, si realizáramos 20 pruebas de independencia, estaríamos
rechazando 0.64*20=12.8 pruebas; con lo estaríamos poniendo 12 arcos extras
por puro azar.
En general, si tenemos k pruebas independientes con nivel de significancia
α y todas las hipótesis nulas son verdaderas, la probabilidad de obtener resultados
k
significativos por azar es de 1 − (1 − α ) . A esta probabilidad se le llama nivel de
significancia global (αg) (Bickel & DokSum, 1977; Bland & Altman, 1995).
α g = 1 − (1 − α )k
(4.2.1.1)
El ajuste de Bonferroni consiste en escoger el nivel de significancia global
αg = 0.05, por ejemplo, y calcular el nivel de significancia para cada prueba.
α = 1 − (1 − α g )k
1
(4.2.1.2)
Para usar este ajuste debemos calcular el número de pruebas que realiza el
algoritmo. Es aquí donde surge un pequeño problema, veamos por qué y a la ves
tratemos de calcular k, el número de pruebas independencia.
Recordemos que tenemos n variables, que incluye la variable dependiente y
las ( n − 1) variables independientes. En el primer paso el algoritmo verifica la
independencia marginal entre la variable dependiente y las variables
independientes, esto es, realiza
( n − 1) pruebas de independencia marginal.
Veamos el segundo paso. Supongamos que se rechazan todas las hipótesis de
independencia marginal y se agregan los ( n − 1) arcos a la red bayesiana;
supongamos también que la profundidad especificada es de 2. El algoritmo toma
inicialmente la variable más informativa y la agrega al conjunto condicionante,
prueba la independencia condicional de la variable dependiente contra cada una
de las n − 2 variables dado el conjunto condicional. Entonces realiza ( n − 2)
pruebas de independencia condicional. Al agregar la segunda variable más
informativa al conjunto condicional se realizan otras n-3 pruebas. Como resultado
final tenemos que en esta pasada se realizaron (n − 1) + (n − 2) + (n − 3) pruebas. Al
cambiar la variable dependiente por la variable más informativa en la etapa, y
llamar al algoritmo nuevamente ahora se tienen n-1 variables, por lo que el primer
paso se realizan n-2 pruebas, en el segundo paso al condicionar con una variable
se realizan n-3 pruebas; finalmente en esta nueva pasada se
realizan (n − 2) + (n − 3) + (n − 4) .
29
_________________________________________________________________________
Hasta ahora van: (n − 1) + (n − 2) + (n − 3) + (n − 2) + (n − 3) + (n − 4) pruebas.
Claramente se observa que esto se puede expresar como sumatorias,
quedando como sigue:
n
p
k = ∑∑ (n − i ) + j
con j < (n − i )
i =1 j = 0
(4.2.1.3)
donde: p es la profundidad
n el número de variables
El valor obtenido para k en la formula anterior es el valor máximo de
pruebas que el algoritmo podría realizar con una profundidad p . He aquí donde
esta el problema en la determinación del numero de pruebas. Las pruebas de
independencia marginal siempre son las mismas, pero las pruebas de
independencia condicional depende del número de arcos agregados en la primera
etapa, es decir del número de hipótesis rechazadas en la primera etapa, por lo que
no podemos determinar, de forma a priori, el número exacto de pruebas de
independencia a realizar.
Otro problema que se presenta en las pruebas de significancia es que para
muestras muy grandes, la prueba es muy sensitiva, es decir, cambios pequeños
de la estadística resultan muy significativos(Bickel & DokSum, 1977).
4.2.2 Región de Indiferencia: Ganancia de Información Mínima
La familia de algoritmos a la que pertenece Bayes-N solamente usa la prueba de
significancia como prueba de independencia. Sin embargo, para bases de datos
muy grandes valores pequeños de información resultan bastante significativos,
incluso después del ajuste de Bonferroni. Es por eso que además Bayes-N incluye
otro criterio para determinar si dos variables son o no independientes, el
porcentaje de ganancia de información, que definimos como:
I ( A, B)
H ( A)
I ( X / Z ,Y )
% I g ( A, B) =
H (X / Z)
% I g ( A, B ) =
En el caso de probar independencia marginal (4.2.1.4)
En el caso de probar independencia
(4.2.1.5)
condicional
Esta medida define un nivel de indiferencia (Bickel & Doksum, 1977), para
decidir que cantidad de información es relevante, especificando de antemano un
umbral(%Igmin) que debe ser excedido para declarar dos variables como no
30
_________________________________________________________________________
independientes (marginal o condicionalmente). Su uso permite que, en los casos
de muestras grandes donde ganancias de información pequeñas resultan
significativas y en consecuencia redes densas, se pueda tener un algoritmo más
parsimonioso.
Incluir el porcentaje de información en el algoritmo solo implica agregar otra
condición a la prueba de independencia. Recordemos que en el primer paso del
algoritmo en el que se hacen las pruebas de independencia marginal entre la
variable dependiente y las explicativas, la hipótesis nula es que las dos variables
involucradas en la prueba son marginalmente independientes, y si ésta es
rechazada entonces se agrega un arco dirigido desde la variable explicativa a la
dependiente. Ahora se agrega además la condición de que la información marginal
entre las variables sea mayor o igual al umbral definido por el porcentaje de
información mínima, para dibujar el arco directo desde la variable independiente a
la variable dependiente.
Procedimiento BayesN
Sea Y la variable dependiente, y sea X = {X1, X2,...,Xn}el conjunto de variables
independientes. Sea p la longitud máxima del conjunto condicionante
(profundidad). Sea α G la significancia global definida anteriormente (ecuación
4.2.1.1). Sea k el número total de pruebas de independencia (ecuación 4.2.1.3).
Sea α la significancia local (ecuación 4.2.1.2). Sea I min , el umbral para la
ganancia de información. Y sea % Inf el porcentaje de información que provee a la
variable dependiente la variable independiente a probar.
Inicializar la lista vacía W
calcular k
calcular
α
para i = 0,hasta i = n
{
probar H0 := X ⊥ Yi
si se rechaza H0 y %I ≥ Imin
{
dibujar un arco directo de Yi a X
agregar Yi a W
}
}
if W ≠ φ
{
31
_________________________________________________________________________
ordenar W de acuerdo a la cantidad de información que provee cada
variable a la variable dependiente
inicializar C como el conjunto condicionante
con = 1
mientras con ≤ p
{
si con < |W|-2
{
para i = 0, hasta i = con
{
agregar Yi a C
}
para i = con, hasta |W|
{
probar H0 := X ⊥ Yi |C
si no se rechaza H0 or %I < Imin
{
remover el arco de Yi a X y remover Yi de W
}
}
reordenar W de acuerdo a la nueva información condicional
obtenida.
con++
}
}
}
Hacer X = Y(1), y repetir el procedimiento hasta que no haya mas variables. Y(1) es
la variable que provee la mayor cantidad de información.
Nota. La significancia global, αg, la profundidad p, y el porcentaje mínimo de
información, Imin, son parámetros definidos por el usuario.
El reordenamiento W después de probar la independencia condicional de X
y Yi dado C se hace por que la información entre las variables ha cambiando. Esto
se debe a que se ha agregado una nueva variable a C, en otras palabras, se ha
agregado nueva información. Una variable que era poco informativa se puede
volver muy informativa si conocemos otra.
32
_________________________________________________________________________
4.3 Sistema de Análisis Bayesiano (BANSY)
La implementación de BayesN se realizó en el lenguaje de programación Java. El
software(que esta en etapa de desarrollo) cuenta con una interfaz gráfica en la
que se puede visualizar las redes Bayesianas generadas. BANSY puede manejar
varias redes Bayesianas en memoria. Cuenta con un escritorio en el que se van
introduciendo diferentes redes en forma de ventanas internas. Esto permite que el
usuario puede hacer comparación de redes generadas con diferentes algoritmos.
Así es como luce:
Fig. 4.3.1 BANSY
4.3.1 Módulo de aprendizaje
El módulo principal es el de aprendizaje de la topología, en el se encuentran
implementados Bayes2(Martínez-Morales, 1995), Bayes5(Cruz-Ramírez, 2001),
Bayes9 (Cruz-Ramírez, 2001) Naïve-Bayes (Freidman et al., 1997) y BayesN.
33
_________________________________________________________________________
Cuando corremos un algoritmo de aprendizaje de la topología, BANSY
muestra una ventana de mensajes en el que el algoritmo va indicando en la etapa
en la que se encuentra y además despliega datos importantes que pueden ayudar
al usuario a identificar el por que la ausencia o presencia de un arco en la red
generada. La manera de desplegar los datos es en forma de texto. Esta misma
ventana de mensajes cuenta con una barra de progreso que permite al usuario
darse una idea del tiempo que tendrá que esperar. La ventana de mensajes no es
de uso específico del módulo de aprendizaje, también la usan el resto de los
módulos para el mismo fin.
4.3.2 Módulo de Aprendizaje de Parámetros (Probabilidades)
Este módulo se encarga de calcular las tablas de probabilidades condicionales
correspondientes a la red que en ese momento se encuentra activa en el
escritorio. Como ya se había mencionado en la sección 2.1, se emplea el método
frecuentista para calcular dichas probabilidades. Los algoritmos implementados en
el módulo de aprendizaje de la topología utilizan este módulo para calcular
automáticamente las tablas de probabilidades condicionales al terminar de
construir la topología.
4.3.3 Módulo de Inferencia
El método de inferencia implementado en este módulo es el que describe Nilsson
(Nilsson, 1998). El se llama método general, y consiste básicamente en utilizar la
definición de probabilidad condicional (ecuación 1.3.7). Para calcular las
probabilidades involucradas en esta ecuación simplemente realizamos conteos en
la tabla de distribución conjunta(calculada la ecuación 1.3.11). Esta es la principal
deficiencia del método general. Para poder llevar a cabo la inferencia en una red,
es necesario definir manualmente la(s) variable(s) de evidencia y la(s) variable(s)
de consulta. Una vez que definimos tanto las variables evidencia como las de
consulta, en el menú de inferencia seleccionamos inferencia general.
4.3.4 Módulo de Bondad de Ajuste
Este módulo incluye dos métricas de bondad de ajuste de las redes a los datos:
MDL(Susuki, 1996; Lam and Bacchus, 1994; Bouckaert, 1994) y métrica
Bayesiana (Cooper & Herskovits, 1992). Las dos métricas se programaron de
acuerdo a la descripción dada por Bouckaert (1994). En el capítulo cinco se
describe la métrica MDL, la métrica Bayesiana no se describe en este trabajo
porque no se usa.
4.3.5 Módulo de Clasificación
El módulo de clasificación incluye los métodos de holdout y cross-validation
(Kohavi, 1995) (Han & Kamber, 2001). Estos métodos serán descritos con detalle
34
_________________________________________________________________________
en el capítulo 5. Por el momento diremos que estos métodos sirven para
determinar el desempeño de un modelo (pude ser por ejemplo un árbol de
decisión, en nuestro caso es una red Bayesiana) en cuanto a su eficacia en
clasificación. En forma general estos métodos consisten en generar el modelo con
un subconjunto de datos(que son seleccionados aleatoriamente) y posteriormente
se prueba la exactitud de clasificación del modelo con el subconjunto de datos
restantes. BANSY puede ejecutar estos dos métodos en forma automática para
BayesN, Bayes9 y Naïve-Bayes. Tiene como opción poder guardar los conjuntos
de entrenamiento y de prueba generados. El propósito de guardar los datos es
para poder evaluar otros algoritmos que no están implementados en BANSY con
la misma partición de datos.
Dado que el sistema BANSY esta en etapa de desarrollo, no se ha
hecho una descripción detallada de cómo utilizarlo. La idea es que siga creciendo
de tal manera que cuente con el mayor número de herramientas necesarias para
el análisis de redes Bayesianas.
35
_________________________________________________________________________
Capítulo 5.
Pruebas de Desempeño
En este capitulo se muestran los resultados obtenidos en el desempeño de
BayesN. La primer prueba de desempeño consiste en proporcionarle al algoritmo
una base de datos de la cual conocemos su estructura (red de oro) y ver si es
capaz de recobrar dicha estructura. La segunda prueba consiste en evaluar el
desempeño en clasificación de la red generada por el algoritmo. Adicionalmente
también se muestran los resultados con MDL. Todas los resultados se comparan
con algunos algoritmos de generación de redes Bayesianas. En la primera sección
se presentan las bases de datos, en la segunda sección se presenta el MDL. En
las secciones restantes se presentan los resultados.
5.1 Bases de Datos y Redes de Oro
Uno de los métodos para determinar el desempeño en forma experimental de los
algoritmos de construcción de redes Bayesianas consiste en tomar una red
Bayesiana de estructura conocida y ver si el algoritmo a probar es capaz de
recuperar dicha estructura (Chickering 1996). A la estructura de la red Bayesiana
conocida se le llama red de oro.
Se usaron cuatro bases de datos para probar el desempeño de los cinco
algoritmos. La base de datos ASIA (Norsys, 2001). es la primera usada en las
pruebas. ASIA tiene 8 variables y 8 arcos. Esta base de datos viene de una red
Bayesiana muy pequeña para un ejemplo médico ficticio acerca de si un paciente
tiene tuberculosis, cáncer de pulmón o bronquitis de acuerdo a los resultados
obtenidos en rayos X, dyspnoea, si visitó Asia y si fuma. Cada nodo tiene 2
valores posibles diferentes. En la figura 5.5.1 se muestra la red de oro para la
base de datos ASIA. En esta base de datos hicimos una modificación. Como
estamos interesados en hacer una clasificación, fusionamos las variables “cáncer”,
“tuberculosis” y “tuberculosis o cáncer” en una sola que llamamos diagnóstico.
Esta variable puede tomar tres valores diferentes: “cáncer”, “tuberculosis” o
“nada”. Representa el diagnóstico hecho a partir del resto de las variables
La segunda base de datos es del mundo real que viene del campo de
patología y tiene que ver con el diagnóstico de cáncer de seno. Contiene 692
casos. La base de datos contiene 11 variables independientes y una variable
dependiente. Las variables independientes son: age, cellular dyshesion,
intracytoplasmic lumina, “three-dimensionality” of epithelial cells clusters, bipolar
“naked” nuclei, foamy macrophages, nucleoli, nuclear pleomorphism, nuclear size,
necrotic epithelial cells y apocrine change. Todas estas variables, excepto age,
son dicótomas y toman los valores verdadero o falso, para indicar la presencia o
ausencia de la característica de diagnóstico. La variable edad fue ordenada en
tres categorias diferentes: 1 (hasta 50 años de edad) 2 (de 51 a 70 años de edad)
36
_________________________________________________________________________
3 (más de 70 años de edad). La variable dependiente “outcome”, puede tomar dos
valores diferentes: benigno o maligno. En el caso de un resultado maligno, tal
resultado fue confirmado con una biopsia(cuando fue posible). Para esta base de
datos no hay una red de oro.
La tercera se llama ALARM. ALARM significa “A Logical Alarm Reduction
Mechanism”. Esta base de datos fue construida a partir de una red Bayesiana
construida por Beinlich (Cooper and Herskovits, 1992; Cooper, 1999) como un
prototipo inicial de investigación para modelar problemas potenciales de anestesia
en la sala de operaciones. ALARM tiene 37 variables (nodos) y 46 arcos. De las
37 variables, 8 variables representan problemas de diagnóstico, 16 variables
representan resultados y 13 variables conectan las variables de diagnóstico con
las de resultados. Cada nodo (variable) tiene de dos a cuatro valores posibles. El
tamaño de la base de datos ALARM usada es de 10, 000 casos. Como variable
dependiente usamos la variable número cinco (presión sanguínea). En la figura
5.5.2 se muestra la red de oro para la base de datos ALARM.
Fig. 5.5.1 Red ASIA. Ejemplo médico ficticio acerca de si
un paciente tiene tuberculosis, cáncer de pulmón o
bronquitis(Norsys, 2001).
37
_________________________________________________________________________
6
5
10
21
22
19
20
31
15
4
27
11
28
29
7
8
32
34
13
23
35
16
36
37
17
25
1
18
2
12
24
26
9
33
14
3
30
1.- central venous pressure
20.- insufficient anaesthesia
or analgesia
2.- pulmonary capillar wedge pressure
21.- pulmonary embolus
3.- history of left ventricular failure
22.- intubation status
4.- total peripheral resistance
23.- kinked ventilation tube
5.- blood pressure
24.- disconnected ventilation tube
6.- cardiac output
25.- left-ventricular
end-diastolic volume
7.- heart rate obtained from blood pressure monitor 26.- stroke volume
8.- heart rate obtained from electrocardiogram
27.- catecholamine level
9.- heart rate obtained from oximeter
28.- error in heart rate
reading due to low
10.- pulmonary artery pressure
cardiac output
11.- arterial-blood oxygen saturation
29.- true heart rate
12.- fraction of oxygen in inspired gas
30.- error in heart rate reading due to
13.- ventilation pressure
electrocautery device
14.- carbon-dioxide content of expired gas
31.- shunt
15.- minute volume, measured
32.- pulmonary-artery
oxygen saturation
16.- minute volume, calculated
33.- arterial carbon-dioxide content
17.- hypovolemia
34.- alveolar ventilation
18.- left-ventricular failure
35.- pulmonary ventilation
19.- anaphylaxis
36.- ventilation measured
at endotracheal tube
37.- minute ventilation measured at
the ventilator
Fig. 5.5.2 Red ALARM. Prototipo inicial de investigación para modelar
problemas potenciales de anestesia en la sala de operaciones.
(Cooper and Herskovits, 1992; Cooper, 1999)
38
_________________________________________________________________________
Fig. 5.5.3 La estructura más probable propuesta por el
algoritmo de Heckerman(1996) para College
También usamos la base de datos de SEWELL & SHAH (Heckerman 1996) que
llamaremos College. Los datos son reales y fueron recolectados por Sewell and
Shah mientras investigaban los factores que influencian a estudiantes de
preparatoria a tener planes para estudiar una carrera universitaria. Midieron 5
variables: sexo, estatus socioeconómico, coeficiente intelectual, si recibieron
estímulo de sus padres y por supuesto planes de estudiar una carrera
universitaria. La base de datos cuenta con 10,318 casos. En la figura 5.5.3 se
muestra la red de oro.
5.2 Bondad de Ajuste
Las métricas de bondad de ajuste son un buen parámetro para la
comparación de algoritmos de generación redes Bayesianas. En este sección se
describe la métrica llamada MDL (Minimum Description Length: longitud de la
descripción mínima) basado en la descripción de Bouckaert (Bouckaert, 1994).
El principio de MDL se puede enunciar como sigue: “La mejor estructura de
la red es aquella que mejor describe a los datos, con el menor número de
símbolos posibles”. En el caso de redes Bayesianas la interpretación sería como
sigue: “La mejor red es aquella que describe de mejor forma a los datos pero que
39
_________________________________________________________________________
además tiene menos arcos”. Y en términos de MDL, la red mejor es la que tiene
un MDL pequeño.
La fórmula para calcular el MDL es como sigue (Bouckaert, 1994):
MDL ( Bs D ) = log P ( Bs ) − NH ( Bs , D ) −
1
K log( N )
2
(5.2.1)
donde:
P ( Bs ) representa la probabilidad a priori de la estructura de red Bs
ri valores que puede tomar la variable X i
n
es el número de variables
qi
es el número de combinaciones de los valores de los padres de la
variable X i . A cada combinación se le llama instancia.
n
K = ∑ qi (ri − 1)
es el número de probabilidades que tienen que ser
i
estimadas de la base de datos. Otra interpretación es: la dimensión del
modelo.
ri
qi
n
N ijk
N ijk
H ( Bs , D ) = ∑ ∑ ∑ (−
log
)
N
N ij
k
i
j
NH ( Bs , D) representa la entropía condicional de la red dados los datos
D
Base de datos
N ijk número de casos(en los datos) en los que X i toma el valor xik
condicionado con la instancia actual de los padres. Si no tiene padres,
entonces nos e condiciona.
ri
N ij = ∑ N ijk
dado que la variable tendrá tantos N ijk ’s como valores tome,
k
entonces N ij representa la suma de estos.
El término P ( Bs ) puede ser eliminado en la comparación de dos medidas, si
consideramos que no tenemos información a priori acerca de la estructura de la
red.
El segundo término de la ecuación 5.2.1 representa la entropía condicional
de la estructura de la red dada la base de datos. Este término será máximo
cuando la incertidumbre es máxima y es cero cuando tenemos un conocimiento
completo. Entre más arcos tenga la red, la entropía descenderá, ya que se
describe mejor la distribución de probabilidad (Bouckaert, 1994).
40
_________________________________________________________________________
El tercer término representa el error introducido al estimar todas las
probabilidades(hay quienes le llaman término de castigo Cruz-Ramírez, 2001).
Este término introduce automáticamente el principio de la navaja de Occam: se
prefiere una estructura con menos arcos que otra que tiene más, a menos que la
entropía condicional de la red más compleja sea mucho más pequeña que la de la
estructura simple (Bouckaert, 1994).
5.3 Algoritmos
En esta sección se describe de forma breve los algoritmos con los que se
compara BayesN, que son K2(Cooper & Herskovits, 1992) y PC (TETRAD)
(Spirtes et al., 1991). También se compara BayesN contra Naïve-Bayes en
clasificación, pero será entonces, cuando se muestren los resultados de
clasificación, que se explique dicho algoritmo.
5.3.1 K2
Este algoritmo fue desarrollado por Cooper y Herskovits(1992). Se trata de un
algoritmo de búsquedas, muy rápido por cierto, que optimiza la probabilidad de la
red dada la base de datos. En realidad lo que hace este algoritmo es encontrar el
conjunto de padres más probables, utilizando la métrica Bayesiana, que mide
precisamente la probabilidad de la estructura dados los datos. La heurística de
este algoritmo se basa en un ordenamiento topológico que tiene que ser
especificado por el usuario. De esta forma se reduce considerablemente el
espacio de búsqueda, por que el ordenamiento hace que un nodo que esta
después en el ordenamiento que otro no pueda ser su padre. En este trabajo
usamos la implementación hecha de K2 en el programa Elvira (Elvira, 2000). Elvira
es un entorno de investigación de métodos y algoritmos de razonamiento
probabilístico. Fue desarrollado por las universidades españolas: Granada,
Almería, País Vasco y UNED.
5.3.2 PC
Este Algoritmo es del tipo basado en restricciones, fue desarrollado por (Spirtes et
al., 1991). Dicho algoritmo empieza por tener todo el esqueleto de la red (red
totalmente conectada) con arcos no dirigidos. En la primer fase quita todos los
arcos que considera no deben ir y finalmente orienta los arcos. Este algoritmo no
necesita un orden de las variables. En este trabajo usamos la implementación
hecha de PC en el programa Elvira (Elvira, 2000), con un nivel de significancia de
0.05.
41
_________________________________________________________________________
5.4 Comparación de la Topología Generada por los Algoritmos con la Red de
Oro
En esta sección se muestra la comparación en el desempeño de Bayes9, K2, PC y
BayesN en la recuperación de la red de oro. En la primera parte se muestran los
resultados en forma de tablas, en la segunda parte se muestran las redes
obtenidas.
5.4.1 Tablas de Resultados
En estas pruebas se considera un arco como correcto si aparece igual que en la
red de oro, independientemente de la dirección.
Las tablas 5.4.1 - 5.4.3 muestran el número de arcos correctos, extras y
faltantes para las bases de datos ASIA, College y ALARM para los algoritmos
Bayes9 (Cruz-Ramírez, 2001), K2 (Cooper & Herskovits, 1992), PC (Spirtes et al.,
1991), Bayes2, Bayes5 y BayesN.
Total
Correctos
Extras
Faltantes
Algoritmo
Bayes9
4
4
0
4
K2
8
7
1
1
PC
4
4
0
4
BayesN
6
5
1
3
Bayes2
8
6
2
2
Bayes5
8
6
2
2
Tabla 5.4.1 Desempeño en términos del número de arcos correctos e incorrectos para la red de oro
ASIA.
Total
Correctos
Extras
Faltantes
Algoritmo
Bayes9
7
7
0
0
K2
7
7
0
0
PC
7
7
0
0
BayesN
7
7
0
0
Bayes2
7
7
0
0
Bayes5
7
7
0
0
Tabla 5.4.2 Desempeño en términos del número de arcos correctos e incorrectos para la red de oro
College.
Total
Correctos
Extras
Faltantes
Algoritmo
Bayes9
44
43
1
3
K2
46
45
1
1
PC
49
46
3
0
BayesN
45
32
13
14
Bayes2
238
46
192
0
Bayes5
93
40
47
6
Tabla 5.4.3 Desempeño en términos del número de arcos correctos e incorrectos para la red de oro
ALARM
42
_________________________________________________________________________
5.4.2 Topología
A continuación se muestran las topologías de las redes Bayesianas para los
algoritmos en comparación, además se agrega el MDL para cada red. La primer
figura muestra la red de oro y las restantes son las generadas por los algoritmos.
Fig 5.4.2.1 Asia, Red de oro, MDL = 1180.2314
Fig 5.4.2.3 Asia, Bayes9
Fig 5.4.2.2 Asia, BayesN, MDL = 1182.8772
Fig 5.4.2.3 Asia, Bayes2, MDL = 1185.6670
43
_________________________________________________________________________
Fig 5.4.2.3 Asia, Bayes5, MDL = 1185.6670
Fig 5.4.2.4 Asia, K2, MDL = 1178.0996
Fig 5.4.2.5 Asia, PC, MDL = 1201.1491
44
_________________________________________________________________________
Las figuras 5.4.2.6 – 5.4.2.10 muestran las redes Bayesianas obtenidas por los
algoritmos en comparación para la red College. La primer red es la de oro y
enseguida se muestran las generadas por los algoritmos.
Fig 5.4.2.6 College, Rea de oro, MDL = 45498.6691
Fig 5.4.2.7 College, BayesN, MDL = 45540.8517
Fig 5.4.2.8 College, Bayes9.
Fig 5.4.2.7 College, Bayes2, MDL = 45540.8517
45
_________________________________________________________________________
Fig 5.4.2.9 College, K2, MDL = 45498.6691
Fig 5.4.2.7 College, Bayes5, MDL = 45540.8517
Fig 5.4.2.10 College, PC, MDL = 45540.8517
46
_________________________________________________________________________
5.4.3 Discusión
Si se analizan las figuras anteriores podemos ver que, los predecesores de
BayesN: Bayes2 y Bayes5, no son buenos en la recuperación de redes de oro, el
principal problema que presentan es el sobre ajuste (Cruz-Ramírez, 2001). En
bases de datos con pocas variables y pocos casos, su comportamiento es
aceptable (tablas 5.4.1, 5.4.2); sin embargo, en el caso de haber muchas variables
y en consecuencia muchos registros, las cosas no funcionan, ya que estos
algoritmos no tienen un control de significancia.
Analicemos las redes. En la red Asia BayesN quitó dos arcos más que
Bayes2 y Bayes5, desgraciadamente uno de los que quitó era correcto. En el caso
de la red ALARM, BayesN solo puso 45 arcos; quiere decir que si logró controlar
el nivel de significancia. Pero, de los 45 arcos solo 32 son correctos, el resto son
erróneos. En el caso de College todos los algoritmos recuperaron la red.
Con respecto al resto de los algoritmos, estos resultados ya han sido
reportados por los autores correspondientes(Cooper & Herskovits, 1992; Spirtes et
al., 1991; Cruz-Ramírez, 2001). Lo que podemos decir es que BayesN obtiene
resultados pobres en comparación a los obtenidos por estos algoritmos.
5.5 Clasificación
Un clasificador es una función que mapea un conjunto de casos (atributos) en una
clase específica (Kohavi, 1995) (Friedman 1997). La tarea consiste en clasificar
casos a partir de un conjunto de características (Friedman 1997). Esta tarea ha
sido abordada con diferentes enfoques, entre ellos podemos mencionar los
árboles de decisión y las redes neuronales(Freidman, 1997).
5.5.1 Hipótesis a posteriori máxima
Supongamos que tenemos un conjunto de hipótesis candidatas H y estamos
interesados en encontrar la hipótesis h ∈ H más probable dados los datos D
observados. Cualquier hipótesis de máxima probabilidad se llama hipótesis a
posteriori máxima (MAP, maximum a posteriori) (Mitchell, 1997).
Podemos usar el teorema de Bayes (ecuación 1.3.12) para calcular la
probabilidad a posteriori de cada hipótesis candidata, y la que tenga mayor
probabilidad será la hipótesis MAP, que denotaremos como hMAP
hMAP ≡ arg max P(h | D)
h∈H
47
_________________________________________________________________________
P ( D | h) P ( h)
P( D)
h∈H
= arg max P( D | h) P(h)
= arg max
(5.5.1.1)
h∈H
En algunos casos se asume que cada hipótesis en H tienen la misma
probabilidad a priori (P(hi) = P(h), para todo hi en H). En este caso podemos
simplificar aun más la ecuación y solamente necesitamos considerar el término
P(D|h) para encontrar la hipótesis más probable. P(D|h) es la probabilidad de los
datos D dado h. Cualquier hipótesis que maximice P(D|h) se llama hipótesis de
máxima verosimilitud(ML).
hML = arg max P ( D | h)
(5.5.1.2)
h∈H
Lo anterior, Mitchell (Mitchell, 1997) lo presenta como una conexión entre el
teorema de Bayes y los problemas de aprendizaje automático, refiriéndose a los
datos D como una conjunto de ejemplos de entrenamiento y a H como un espacio
de funciones que pueden describir los datos.
5.5.2 Clasificador Naïve Bayes (Friedman et al., 1997)
Sea X la variable aleatoria dependiente y sea Y = {Y1, Y2, ..., Yn} el conjunto
no ordenado de variables aleatorias independientes(atributos). Un clasificador
Naïve asume que X es padre de todas las variables del conjunto Y y a su vez
estas variables son independientes entre si dada la variable dependiente X. Una
red naive bayes
se vería más o
menos así:
Fig. 5.3.1.1 Red Naïve-Bayes (College). La
variable clase es “CollegePlans”
Para llevar a cabo la tarea de clasificación hacemos lo siguiente. Tomamos
el caso que queremos clasificar, caso seguido instanciamos la red con dicho caso,
es decir hacemos que cada variable independiente de la red tome el valor
48
_________________________________________________________________________
correspondiente del registro. Para saber a que valor mapea la red Naïve debemos
calcular la probabilidad de cada valor de la clase dado el conjunto de atributos, de
la forma siguiente usando la definición de la probabilidad condicional (ecuación
1.3.13):
P( X , Y )
P(Y )
P( X / Y ) =
(5.5.2.1)
donde:
P ( X , Y ) es la probabilidad conjunta de X y Y. Recordemos que esta
probabilidad se encuentra codificada en la red, y es el producto de todas las
probabilidades condicionales.
P ( X , Y ) = P( X ) P(Y1 | X ) P(Y2 | X )...P(Yn | X )
P(Y ) es la probabilidad del conjunto condicionante. Esta probabilidad no la
calcularemos, ya que se eliminará al normalizar las probabilidades calculadas.
Esto es fácil de ver; la normalización que haremos consiste en dividir cada valor
de probabilidad entre la suma de todas (todas las probabilidades condicionales de
la clase).
El enfoque Bayesiano para clasificar este nuevo caso, consiste en asignar
el valor con mayor probabilidad, lo cual corresponde a la hipótesis MAP.
v MAP = arg max P( x | y )
x
(5.5.2.1)
v MAP es pues el valor clasificado por Naïve-Bayes (la etiqueta asignada)
para el nuevo caso presentado y corresponde al valor con probabilidad máxima
a posteriori(MAP).
5.5.3 Redes Bayesianas Clasificadoras
En el caso de una red Bayesiana la clasificación se lleva a cabo de la misma
manera, la única diferencia es que las redes Bayesianas no consideran a las
variables explicativas como condicionalmente independientes dada la clase. En su
lugar si toma en cuenta estas posibles relaciones. Otra diferencia importante es
que una red Bayesiana puede sacar ventaja al prescindir de variables irrelevantes
para la clase, tomando en cuenta para la clasificación aquellas que le son
importantes. En otras palabras, solo se toma en cuenta la cobija de Markov
(Definición 1.7.3) como conjunto de atributos relevantes. El hecho que se
considera en este caso es que una variable es condicionalmente independiente
del resto dada la cobija de Markov.
49
_________________________________________________________________________
Si la cobija de Markov de la variable clase solo involucra a sus padres (no
tiene hijos), entonces en las tablas condicionales se encuentran las probabilidades
que necesitamos para llevar a cabo la clasificación. Se aplica también el enfoque
Bayesiano descrito en la sección anterior.
5.5.4 Métodos para la clasificación
Existen varios métodos para medir el desempeño, en términos de la
exactitud, de cualquier clasificador, entre ellos figuran: Método de partición
(holdout), validación cruzada (cross-validation) y bootstrap (Kohavi, 1995) (Han &
Kamber, 2001). En este trabajo usamos el método de partición (holdout) y el de
validación cruzada (cross-validation) para medir la exactitud del modelo construido
por los diferentes algoritmos comparados.
Lo que se hace comúnmente en el método de partición (holdout) es
partición aleatoriamente los dos datos en dos conjuntos de ejemplos mutuamente
exclusivos: el conjunto de entrenamiento y el conjunto de prueba. El conjunto de
prueba también es llamado conjunto holdout. El tamaño de los conjuntos puede
escogerse de la forma que uno desee, sin embargo, es práctica común escoger
2/3 de los datos como el conjunto de entrenamiento y 1/3 como el conjunto de
prueba. La exactitud del modelo se mide en términos del porcentaje de casos
clasificados correctamente del conjunto de prueba. En otras palabras la clase a la
que realmente pertenece el caso es comparada con la predicha por el modelo. La
razón de hacer partición de esta forma es para evitar el sobreajuste de los datos,
ya que, si la exactitud del modelo fuera estimada tomando solamente en cuenta el
conjunto de entrenamiento, entonces algunas posibles características anómalas
que no son representativas para el conjunto de los datos, podrían incluirse en el
subconjunto y el estimador podría reflejar una precisión errónea.
Así, el número total de clasificaciones correctas dividida por el tamaño del
conjunto de prueba es la estimación de la exactitud del método de partición
(holdout). La fórmula 5.5.4.1 (Kohavi, 1995) muestra como calcular la exactitud
usando el enfoque holdout.
acch =
1
∑δ(I(Dt,v i), yi)
h (vi ,yi ) ∈Dh
(5.5.4.1)
donde:
I(Dt, vi) denota la proposición vi construida por el modelo I en los datos Dt
(el conjunto de entrenamiento) el cual asigna una etiqueta yi. h es el tamaño de el
conjunto de prueba. si i=j δ(i,j)=1 de lo contrario δ(i,j)= 0. Esto quiere decir que la
función de pérdida usada para calcular la exactitud en el método de partición
(holdout) es una función de pérdida 0/1, lo cual considera que una clasificación
errónea tiene un mismo costo.
50
_________________________________________________________________________
La varianza del método de particiónt (holdout) se estima como sigue (Kohavi,
1995)
Var =
acc × (1 − acc)
h
(5.5.4.2)
donde h es el tamaño del conjunto de prueba.
El otro enfoque utilizado en este trabajo para medir la exactitud de
clasificación es el método de validación cruzada con k conjuntos (k-fold crossvalidation). En este método el conjunto total de datos se parte en k subconjuntos
del mismo tamaño mutuamente exclusivos D1, D2,..., Dk. El algoritmo de inducción
es probado k veces de la siguiente manera: en la primera iteración el algoritmo es
entrenado con los subconjuntos D2, …, Dk y probado con el subconjunto D1; en la
segunda iteración, el algoritmo se entrena con los subconjuntos D1, D3, …, Dk y se
prueba con el subconjunto D2 y así sucesivamente. El número total de
clasificaciones correctas de las k iteraciones se divide por el tamaño completo del
conjunto de datos para obtener la estimación de la exactitud en el método de
validación cruzada con k conjuntos (k-fold cross-validation). La fórmula 5.5.4.3
muestra como calcular la exactitud en el enfoque de validación cruzada (crossvalidation).
acccv =
1
∑ δ ( I ( D \ D(i ), vi), yi)
n ( vi , yi )∈D( i )
(5.5.4.3)
donde I(D\D(i),vi) denota la proposición vi construida por el modelo I en el
conjunto D\D(i), la cual es asignada a la etiqueta yi y probada en el conjunto D(i); n
es el tamaño total de conjunto de datos D. Si δ(i,j)=1 de lo contrario δ(i,j)=0. Como
en la ecuación 5.5.4.1 lo anterior quiere decir que la función de pérdida usada para
calcular la exactitud del con el método cross-validation es una función de pérdida
0/1, lo cual considera un costo igual para una clasificación errónea.
La ecuación 5.5.4.4 muestra la fórmula para estimar la varianza en este
método[16].
Varcv =
acccv × (1 − acccv )
n
(5.5.4.4)
donde n es el tamaño de los datos completos D.
51
_________________________________________________________________________
5.5.5 Resultados del Método de Partición (Holdout)
El primer paso para realizar esta prueba es la partición aleatoria de los datos, la
cual fue de 2/3 partes como conjunto de entrenamiento y 1/3 parte como conjunto
de prueba. Todos los algoritmos se entrenaron con el mismo conjunto den
entrenamiento y se probaron con el mismo conjunto de prueba. En el caso de
Naïve-Bayes, Bayes9 y BayesN el proceso se llevo a cabo de forma automática en
el programa BANSY. Para los algoritmos K2 y PC, tomamos el conjunto de
entrenamiento que se guardó y entrenamos en el programa Elvira, posteriormente
con la red obtenida realizamos la clasificación en el programa BANSY, usando por
supuesto el mismo conjunto de prueba.
La tabla 5.5.5.1 muestra el desempeño en clasificación, usando el método de
partición (holdout), de los cinco algoritmos: Naïve Bayes(Freidman et al., 1997),
Bayes-N, K2 (Cooper & Herskovits, 1992), PC (Spirtes et al., 1991) y Bayes9
(Cruz-Ramírez, 2001).
La tabla 5.5.5.2 muestra la MDL para las redes obtenidas en el método holdout,
para los cinco algoritmos.
Data set
Alarm
Cancer
Asia
Naïve Bayes
62.65 ± 0.84
92.80 ± 1.68
93.53 ± 1.63
Bayes-N
82.57 ± 0.66
95.34 ± 1.37
96.18 ± 1.04
K2
82.57 ± 0.66
95.34 ± 1.37
96.18 ± 1.04
Tetrad (PC)
82.57 ± 0.66
92.80 ± 1.68
95.01 ± 1.18
Bayes9
82.57 ± 0.66
95.34 ± 1.37
96.18 ± 1.04
Tabla 5.5.5.1 Desempeño en clasificación para el método de holdout de Naïve Bayes, BayesN, K2,
PC y Bayes9.
Base de datos
Alarm
Cancer
Asia
Naïve Bayes
143730.14
2685.4023
2387.2046
Bayes-N
78010.91
2679.55
2213.34
K2
71590.66
2648.20
2215.23
Tetrad (PC)
78845.10
2746.72
2211.79
Bayes9
79352.55
2759.91
2211.34
Table 5.5.5.2 Calificación MDL para las redes obtenidas en el método holdout.
5.5.6 Resultados con el Método de Validación Cruzada (cross-validation)
El programa BANSY también permite llevar a cabo el proceso de validación
cruzada en forma automática para los algoritmos Naïve-Bayes, Bayes9 y BayesN.
En este método el programa también hace la selección de los k conjuntos de
manera aleatoria. En cada una de las k pruebas se guardaron los conjuntos de
entrenamiento y de prueba para poder correr los algoritmos K2 y PC. El
entrenamiento se realizó en el programa Elvira y la clasificación en el programa
BANSY.
La tabla 5.5.6.1 muestra el desempeño en clasificación, usando el método de
validación cruzada con k = 5, de los cinco algoritmos: Naïve Bayes(Freidman et
52
_________________________________________________________________________
al., 1997), Bayes-N, K2 (Cooper & Herskovits, 1992), PC (Spirtes et al., 1991) y
Bayes9 (Cruz-Ramírez, 2001).
Data set
Alarm
Cancer
Asia
Naïve Bayes
61.52 ± 0.49
93.00 ± 0.97
89.63 ± 0.96
Bayes-N
82.25 ± 0.38
94.65 ± 0.85
94.30 ± 0.73
K2
82.25 ± 0.38
94.51 ± 0.86
94.20 ± 0.74
PC
82.13 ± 0.38
94.36 ± 0.88
95.80 ± 0.63
Bayes9
82.79 ± 0.38
94.36 ± 0.68
95.80 ± 0.63
Tabla 5.5.6.1 Desempeño en clasificación para el método 5-fold cross-validation de Naïve Bayes,
Bayes-N, K2, PC y Bayes9
5.5.7 Discusión
De las tablas podemos ver que BayesN tiene un desempeño mucho mejor que
Naïve-Bayes y un desempeño comparable al de K2, PC y Bayes9. Además el
MDL también es comparable con el obtenido con estos últimos tres algoritmos.
La ventaja de BayesN sobre Naïve-Bayes, además de la exactitud, es que
elige correctamente un conjunto de variables para el análisis y prescinde de
aquellas que considera irrelevantes. También, BayesN no sume que las variables
atributo son condicionalmente independientes dada la variables clase
(dependiente). Esto es, BayesN considera que si pueden existir interacciones
entre los atributos, lo que puede darle mayor riqueza al modelo además de un
mejor entendimiento del fenómeno bajo estudio. Podría pensarse que dado que
Naïve-Bayes toma en cuenta a todas las variables independientes para hacer el
diagnóstico, se desempeñaría mejor que aquellos algoritmos que solamente
toman un subconjunto de variables como BayesN. Sin embargo, los resultados
muestran que no es así. Esto da una indicación de que las medidas locales de
ganancia de información que usa BayesN representa un enfoque eficaz para la
construcción de clasificadores Bayesianos. Además, con la reducción de los
atributos redundantes, el uso de estas medidas permite obtener modelos
parsimoniosos.
La principal ventaja de BayesN sobre K2 es que no necesita un orden
ancestral para construir la red, mientras que K2 si lo necesita. En su lugar BayesN
induce un orden ancestral basado en medidas de ganancia de información. En el
caso de K2 el orden ancestral tiene que proveerse de forma externa y la estructura
generada es muy sensitiva a este orden(Cooper & Herskovits, 1992; Heckerman,
1994).
Comparado con PC y Bayes9, BayesN da todas las direcciones de los
arcos en la red, mientras que los otros dos pueden producir arcos no dirigidos.
Aunque este problema puede resolverse en algunos casos, es necesario llevar a
cabo cierta extracción de conocimiento para dirigir esto arcos.
53
_________________________________________________________________________
Algunas limitaciones de BayesN son que para realizar el ajuste de
Bonferroni, es necesario hacer el calculo, de forma a priori, del número de pruebas
de independencia que se realizan en el procedimiento. La otra limitación es el nivel
de indiferencia. Este parámetro tiene que ser ajustado manualmente., una mala
especificación del mismo puede arrojar malos resultados.
54
_________________________________________________________________________
Conclusión
La tarea de clasificar es un campo bastante amplio en el que se han sugerido
diversas formas de resolverla. El clasificador Naïve-Bayes pertenece al enfoque
Bayesiano y es uno de los más utilizados en la literatura; se ha demostrado que es
competitivo con los clasificadores que manejan otros enfoques, e incluso en
algunos dominios éste los ha superado (Friedman et al., 1997). En este trabajo se
presentó un algoritmo que genera redes Bayesianas que utiliza medidas locales
de información y se demostró que las redes generadas por éste superan a NaïveBayes en la tarea de clasificación. La principal razón de este hecho es que una red
Bayesiana no toma en cuenta a todos los atributos para realizar la clasificación, en
su lugar toma aquellos atributos que son relevantes prescindiendo de los que no lo
son. Otra cuestión importante que hace que Naïve-Bayes se vea superado es su
suposición de independencia condicional de los atributos dada la variable clase.
En una red Bayesiana no se hace tal suposición.
De todo lo anterior se concluye que las redes Bayesianas pueden ser
usadas como clasificadores aprovechando las independencias/dependencias
reflejadas en su topología. También podemos concluir que las medidas locales de
información usadas por la familia de algoritmos Bayes permiten una buena
selección de las variables relevantes logrando un muy buen desempeño en la
tarea de clasificación.
La incorporación del control de nivel de significancia global utilizando el
ajuste de Bonferroni, provee a BayesN con la capacidad de construir redes
Bayesianas más dispersas, es decir con menos arcos; evitando de esta forma el
sobreajuste en bases de datos grandes. Sin embargo lo anterior resulta
contraproducente cuando la base de datos es muy pequeña; se obtienen redes
con muy pocos arcos.
BayesN incorpora el porcentaje de información mínima como una región de
indiferencia para control de la sensitividad de las pruebas de independencia. Esto
también nos puede ayudar a controlar el sobreajuste, el problema es que BayesN
aún no provee una forma automática de selección de
este parámetro.
Actualmente la selección es muy subjetiva, depende del usuario.
Otra característica que aporta BayesN es el dinamismo de la cardinalidad
del conjunto condicionante en las pruebas de independencia condicional.
Nuevamente este parámetro es criterio del usuario.
El conjunto de mejoras, aunado a la interfaz gráfica desarrollada, hace que
BayesN sea muy flexible y robusto ante la experiencia del usuario.
55
_________________________________________________________________________
Trabajo Futuro
La discretización de los datos en el procesado de los datos es una tarea
nada trivial, es por eso que una extensión de BayesN al manejo de variables
continuas sería un buen trabajo futuro.
Otra extensión de BayesN, muy benéfica para el usuario, sería el manejo de
datos faltantes. Esto permitiría evitar la reducción de las base al sacar aquellos
casos en los que hubiera datos faltantes.
56
_________________________________________________________________________
Referencias
(Bickel & DokSum, 1977) P.J. Bickel, K.A. Doksum. Mathematical Statistics: Basic Ideas and
Selected Topics. Holden Day, Inc. Oakland, Cal. 1977.
(Bland & Altman, 1995) J.M. Bland, and D.G. Altman, Multiple significance tests: the Bonferroni
method. BMJ; 310: 170, (1995).
(Bouckaert, 1994) Bouckaert, R. R. (1994). Probabilistic Network Construction using the Minimum
Description Length Principle, Technical Report RUU-CS-94-27, Utrecht University.
(Feigenbaum y Buchanan, 1978)Feigenbaum, E. A. Buchanan, B. G., "DENDRAL and MetaDENDRAL: Their Applications Dimension", Artificial Intelligence, 11, 1978, pp. 5-24.
(Cheng & Greiner, 2001) Cheng, J. and Greiner, R., Learning Bayesian Belief Network Classifiers:
Algorithms and System. Proceedings of 14 Biennial conference of the Canadian society forcomputational
studies of intelligence, 2001.
th
(Cheng, et. al., 1998) J. Cheng, D.A. Bell, and W. Liu, Learning Bayesian Networks from data: An
efficientapproach based on Information Theory.Technical Report
(1998). (www)
http://www.cs.ualberta.ca/~jcheng/Doc/report98.pdf
(Chickering et. al., 1994) Chickering, D.M., Geiger, D., and Heckerman, D., Learning Bayesian
Networks is NP-Hard, Technical Report MSR-TR-94-17, Microsoft Research, Microsoft Corporation,
1994
(Cooper & HersKovits, 1992) G.F. Cooper, and E. Herskovits, A Bayesian Method for the induction
of probabilistic networks from data. Machine Learning, 9 (pp. 309-347), (1992).
(Cooper, 1999) G. F. Cooper, An Overview of the Representation and Discovery of Causal
Relationships using Bayesian Networks. Computation, Causation & Discovery. C. Glymour and G.
F. Cooper, AAAI Press / MIT Press: 3-62. (1999).
(Cruz-Ramírez, 1997) Cruz-Ramirez, N. Un algoritmo para generar redes probabilistas a partir de
datos estadisticos aplicadas a problemas de clasificacion y/o pronostico, Tesis de Maestria,
Maestria en Inteligencia Artificial, Universidad Veracruzana, Xalapa, Veracruz, Mexico, 1997.
(Cruz-Ramírez, 2001) N. Cruz-Ramirez, Building Bayesian Networks From Data: a Constraint
Based Approach. Ph D Thesis. Department of Psychology. The University of Sheffield. (2001).
(Elvira, 2000) Proyecto Elvira, Entorno de investigación de métodos y algoritmos de razonamiento
probabilístico. Universidades: Granada, Almería, País Vasco y UNED, 1997-2000. dirección
electrónica: http://www.ia.uned.es/~elvira/
(Feigenbaum 1979) Feigenbaum, E. A., “Themes and case studies of knowledge engineering”,
Expert Systems in the Micro-Electronic Age, Ed. D. Michie, Edinburg Univ. Press, 1979, p. 3-25.
(Freidman et al., 1997) N. Freidman, D. Geiger, S. Goldszmidt, Bayesian Networks classifiers.
Machine Learning, 29 (pp 131-161), (1997).
(Han & Kamber, 2001) J. Han, and M. Kamber, Data Mining. Concepts and Techniques, Morgan
Kaufmann , (2001).
_________________________________________________________________________
Heckerman, D. (1997). A Tutorial on Learning with Bayesian Networks, Technical Report
MSR-TR-95-06, Microsoft Research, Redmond, Washington, 1997.
(Heckerman 1997; Friedman and Goldszmidt 1998)
(Heckerman et al., 1994) Heckerman, D., Geiger, D. and Chickering, D.M., Learning Bayesian
networks: the combination of knowledge and statistical data, Technical Report MSR-TR-94-09,
Microsoft Research, 1994. To appear, Machine Learning Journal.
(Heckerman, 1995) Heckerman, D. A Tutorial on Learning With Bayesian Networks. Technical
report, MSR-TR-95-06. Microsoft Research, 1995.
(Herskovits, 1991) Herskovits, E., Computer-based probabilistic network construction, Doctoral
dissertation, Medical information sciences, Stanford University, Stanford, CA, 1991.
(Kohavi, 1995) R. Kohavi, A Study of Cross-Validation and Bootstrap for Accuracy Estimation and
Model Selection. 14th International Joint Conference on Artificial Intelligence IJCAI'95, Montreal,
Canada, Morgan Kaufmann. (1995).
(Kullback, 1959) S. Kullback, Information Theory and Statistics. Dover, New York, (1959).
(Lam and Bacchus, 1994) Lam, W. and Bacchus, F., Learning Bayesian belief networks: An
approach based on the MDL principle, Computational Intelligence, Vol 10:4, 1994.
(Langley, et. al., 1992) Langley, P., Iba, W. and Thompson, K.. An analysis of Bayesian classifiers.
In Proceedings of AAAI-92 (pp. 223-228). 1992.
(Martínez-Morales, 1995) M. Martinez-Morales, An Algorithm for the Induction of Probabilistic
Networks from Data. XII Reunion Nacional de Inteligencia Artificial, ITESM, Cuernavaca, Morelos,
Mexico, Limusa. (1995).
(Neapolitan, 2003) Neapolitan, R.E., Learning Bayesian Networks, Prentice Hall, Prentice Hall,
Upper Saddle River, NJ, 2003.
(Newell and Simon 1963) Newell, A., Simon. H.A., “GPS: A program that simulates Human
Thought”, Computers and Thought, ed. Feigenbaum, E., Feldman, J., NY, McGraw-Hill, 272-296.
1963.
(Nikolopoulos 1997) Nikolopoulos, Chris, “Experts Systems: Introduction to first and second
generation and hybrid knowledge based systems”. Marcel Dekker, inc. 1997.
(Nilsson, 1998) Nils J. Nilsson. Artificial Intelligence: A New Synthesis. Morgan Kaufmann
Publishiers. 1998.
(Norsys, 2001). Norsys Software Corporation, Electronic source: http://www.norsys.com. (2001).
(Pearl 2001) Pearl, J. Cusality, Models, Reasoning, and inference. Cambridge University Press,
2001.
(Pearl, 1988) Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible
inference, Morgan Kaufmann, 1988.
_________________________________________________________________________
(Quinlan, 1993) J.R.Quinlan, C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers.
(1993).
(Ramoni and Sebastiani, 1996) Ramoni, M. and Sebastiani, P., Robust learing with missing data,
Technical report, KMI-TR-28, 1996.
(Shannon, 1948) Shannon, C. E. and W. Weaver (1949). The mathematical theory of
communication.Urbana, University of Illinois Press
(Spirtes et al., 1991) Spirtes, P., Glymour, C. and Scheines, R., An algorithm for fast recovery of
sparse causal graphs, Social Science Computer Review, 9, 62-72, 1991.
(Spirtes et. al., 1990) Spirtes, P., Glymour, C. and Scheines, R., causality from probability,
proceedings of Advanced Computing for the Social Sciences, Williamsburgh, VA.
(Spirtes, & Glymour , 1993) P. Spirtes, and C. Glymour, Causation, Prediction and Search,
Springer-Verlag. (1993).
(Suzuki, 1996) Suzuki, J., Learning Bayesian belief networks based on the MDL principle: An
efficient algorithm using the branch and bound technique, Proceedings of the international
conference on machine learning, Bari, Italy, 1996
(Wallace et. al., 1996) Wallace, C., Korb, K.B. and Dai, H., Causal discovery via MML, Proceedings
of the thirteenth international conference on machine learning (ICML'96), Morgan Kaufmann
Publishers, San Francisco CA USA, pp. 516-524.