Modelos de redes bayesianas en el estudio de secuencias genómicas y otros problemas biomédicos (página 3)
Introducción
9
Novedad Científica
La novedad científica y el consecuente valor teórico del presente trabajo se resumen en los
siguientes puntos:
1. Se desarrollan y formalizan tres nuevos algoritmos de aprendizaje estructural de RB
combinando técnicas clásicas con árboles de decisión, técnicas novedosas de detección
de interacciones y el algoritmo de optimización inspirado en bandadas de pájaros que
permiten reducir la estructura de dependencias y los cálculos consecuentes.
2. Se muestran nuevos enfoques para afrontar problemas aún no resueltos cabalmente en
Bioinformática, relacionados con la localización de genes a través de sitios de splicing
y la detección de interacciones entre proteínas. Se ilustra además la generalidad de los
enfoques en un problema de diagnóstico médico relacionado con el diagnóstico de la
HTA.
La novedad está avalada por las publicaciones que se describen al final de la tesis.
Valor práctico
Desde este punto de vista, el valor del trabajo radica en la disponibilidad de la
implementación de los algoritmos, como extensiones al software libre Weka, con
distribución de datos para la ejecución de las validaciones cruzadas para ejecutar en un
cluster de computadoras o en máquinas conectadas en red. Ello facilita:
1. El uso libre por la comunidad científica a nivel nacional e internacional con
posibilidades de comparar con otros algoritmos implementados también sobre
Weka, tanto en aplicaciones bioinformáticas como en otras áreas.
2. El abordar en particular problemas que requieren inferencias en múltiples
direcciones además de clasificación (los modelos de RB implementados sobre Weka
solo trabajan como clasificadores).
3. El aportar nuevos algoritmos que resulten ser eficientes en la solución de problemas
planteados en la bioinformática actual.
Después de la revisión de la literatura y el desarrollo consecuente del marco teórico, se
formuló la siguiente hipótesis de investigación:
Introducción
10
Hipótesis de investigación
Los modelos gráfico probabilísticos, específicamente los árboles de decisión y las técnicas
de detección de interacciones, así como la optimización inspirada en bandadas de partículas
permiten definir nuevos algoritmos de aprendizaje estructural de RB que resultan más
simples y que pueden ser utilizadas con eficiencia similar o superior a los ya existentes, en
diversos problemas biológicos, específicamente en el análisis de regiones genómicas
codificantes para proteínas y en problemas Biomédicos.
Estructura de la tesis
El trabajo se presenta esencialmente en tres capítulos a partir de la presente Introducción.
El Capítulo 1 se dedica a la elaboración del marco teórico desde el punto de vista de las
tendencias actuales en el desarrollo y evaluación de las RB. Se muestran algunas
aplicaciones interesantes de estas técnicas, especialmente en el campo de la Bioinformática.
En el Capítulo 2 se propone y formalizan matemáticamente los tres nuevos algoritmos de
aprendizaje de la estructura de RB. Se realiza una validación de los algoritmos, para lo que
se utilizan 18 archivos de datos de la UCIML (UCI Repository of Machine-Learning
Databases) y un análisis de la complejidad temporal de los mismos. El Capítulo 3 está
dedicado a mostrar el comportamiento de los nuevos algoritmos en dos problemas
bioinformáticos y en la predicción de HTA como ejemplo de aplicación en otras ramas. Se
formulan finalmente las conclusiones y recomendaciones, se detallan las referencias
bibliográficas y se incluyen algunos anexos para mostrar detalles complementarios.
1. LAS REDES BAYESIANAS Y LA BIOINFORMÁTICA
El presente capítulo se dedica a sustentar teóricamente el tema de la tesis, por lo que se
analizan aquellos enfoques y antecedentes relacionados con las RB y su aplicación, por
ejemplo a problemas bioinformáticos de análisis de secuencias. Se provee un marco de
referencia para interpretar las soluciones a los problemas desarrollados, y se exponen los
conceptos relacionados con la Bioinformática en función de las aplicaciones que se
desarrollan. Se analizan los problemas actuales existentes en esta temática relacionados con
la obtención de RB desde datos y la posible aplicación en problemas de la vida real.
1.1
Redes Bayesianas
Las redes probabilistas son representaciones gráficas de las variables y de las relaciones
entre las variables que caracterizan un problema (Wiltaker 1990). Las RB son un tipo muy
popular de redes probabilísticas (Charles River Analytics 2004), que proveen información
sobre las relaciones de dependencia e independencia condicional existentes entre las
variables. La inclusión de las relaciones de independencia en la propia estructura de la red,
hace de las RB una buena herramienta para representar conocimiento de forma compacta
pues se reduce el número de parámetros necesarios. Estas relaciones simplifican la
representación de la función de probabilidad conjunta como el producto de las funciones de
probabilidad condicional de cada variable.
Al representar una distribución de probabilidad, las RB tienen una semántica clara, lo que
permite procesarlas para hacer diagnóstico, aprendizaje, explicación, e inferencias
(Heckerman 1996). Según la interpretación, pueden representar causalidad y se refieren
como redes causales (Spirtes 1993), (Pearl 1993), pero no necesariamente tienen que
representar relaciones de causalidad, sino de correlación (Grau et al. 2004).
Según (Stuart y Norvig 1996), (Stuart y Norvig 2003), una RB se define como un grafo que
cumple lo siguiente:
•
Los nodos de la red son variables aleatorias que se denotan con la letra X o con
subíndices X1, X2, …Xn. En principio estas variables pueden representar rasgos o
atributos, pero puede ocurrir también que un rasgo original tenga que ser
Capítulo I. Las redes bayesianas y la Bioinformática
12
•
•
•
descompuesto en varias variables aleatorias. Por ejemplo, si el rasgo tiene múltiples
valores puede desearse trabajar con variables aleatorias dicotómicas, una por cada
valor del rasgo original
Cada par de nodos se conecta entre sí mediante arcos dirigidos. El significado de
un enlace que va del nodo X al nodo Y es el de que X ejerce una influencia directa
sobre Y. En términos de probabilidades esto significa que hay una dependencia
condicional de Y respecto a X, esto es que la probabilidad de Y es diferente de la
probabilidad de Y dado X.
Por cada nodo hay una tabla de probabilidad condicional que sirve para cuantificar
los efectos de los padres sobre el nodo. Los padres de un nodo son aquellos nodos
cuyos arcos apuntan hacia éste.
El grafo no tiene ciclos dirigidos (por lo tanto es un GDA). Esto significa que no se
presentan ambigüedades en el encadenamiento de probabilidades condicionales por
el hecho de influencias directas cíclicas.
Vista la RB como el grafo junto con las tablas de probabilidad condicional, se puede
interpretar como una representación bien aproximada de la función de distribución de
probabilidad conjunta (DPC)6 de la variable clase y de todos los rasgos predictores. La red
en sí codifica un conjunto de aseveraciones de independencia condicional. Las tablas de
probabilidades condicionales completan la caracterización de la distribución conjunta.
El grafo es importante para construir la red en sí. Los valores que aparecen en las tablas de
probabilidad condicional son imprescindibles en el procedimiento de inferencia. Esta
representación es a lo que algunos autores llaman I–mapa minimal de la distribución
conjunta (Castillo et al. 1997), (García 1990).
Formalmente esta representación de la DPC define un modelo de RB, como un par (G, P),
donde G es un GDA, P= {p(X1|t1), p(X2|t2), …, p(Xn|tn)} es un conjunto de n
distribuciones de probabilidad condicionales, una por cada variable Xi (nodos del grafo), y
6
Ver definición en anexo 1 de conceptos básicos.
p(X) =? p(X it i)
Capítulo I. Las redes bayesianas y la Bioinformática
13
ti es el conjunto de padres del nodo Xi en G. El conjunto P define la DPC asociada, como
muestra la expresión:
X = (X1, X 2,…,X n)
n
i=1
(1.1)
1.1.1
Aprendizaje en Redes Bayesianas
¿Por qué es de interés el aprendizaje de redes probabilísticas o RB?. El interés de la IA en
el aprendizaje de RB, se debe a la asociación entre la incertidumbre y el aprendizaje
automático (Buntine 1994; Buntine 1995). El problema del aprendizaje bayesiano puede
describirse informalmente así: dado un conjunto de entrenamiento D = {d1, d2,…, dn} de
instancias del problema, encuéntrese la RB que se ajuste mejor a D. Típicamente, este
problema se divide en dos aspectos:
•
•
Aprendizaje estructural: obtener la estructura de la RB, es decir, las relaciones de
dependencia e independencia condicional entre las variables involucradas.
Aprendizaje paramétrico: dada una estructura de RB, obtener las probabilidades a
priori y condicionales requeridas.
Las técnicas de aprendizaje estructural dependen del tipo de estructura de red: árboles, poli
árboles y redes múltiplemente conexas. Otra alternativa es combinar conocimiento
subjetivo del experto con aprendizaje. Para ello se parte de la estructura dada por el
experto, la cual se valida y mejora utilizando datos estadísticos. Resulta evidente que la
calidad de una red obtenida de esta manera depende mucho del conocimiento sobre el
dominio de aplicación de los encuestados. Esta última opción no siempre es aplicable en
problemas bioinformáticos.
1.1.1.1
Aprendizaje estructural de Redes Bayesianas
Uno de los modelos más simples, y que por su facilidad de utilización se ha convertido en
un estándar con el cual comparar las bondades de los diferentes métodos, es el denominado
modelo bayesiano Naïve (MBN) o Naïve-Bayes (Duda y Hart 1973). Su denominación
proviene de la hipótesis de que las variables predictivas son condicionalmente
independientes dada la variable a clasificar y con esto ya queda definida una estructura, por
Capítulo I. Las redes bayesianas y la Bioinformática
14
lo que sólo se tienen que aprender las probabilidades de los valores de los atributos dada la
clase. Pero es obvio que esta suposición de independencia es demasiado fuerte.
Una forma de mejorar la estructura de un MBN se logra si se añaden arcos entre los nodos
o atributos que tengan cierta dependencia. Se han realizado varias generalizaciones del
MBN (Friedman y Goldszmidt 1996), (Larrañaga 2000). Otra forma es realizando
operaciones locales hasta que no mejore la predicción:
•
•
•
eliminar un rasgo o atributo,
unir dos atributos en una nueva variable combinada,
introducir un nuevo atributo que haga que dos atributos dependientes sean
independientes (nodo oculto).
Se pueden ir probando cada una de las opciones anteriores midiendo la dependencia de los
atributos dada la clase o información mutua condicional (IMC) según la expresión:
|C)
log(P(X i, X j |C)
P(X i |C) P(X j |C)
j
?P(X i, X
Xi, X j
IMC(X i, X j |C) =
(1.2)
Algoritmo para árboles
El método para aprendizaje estructural de árboles se basa en el algoritmo desarrollado por
(Chow y Liu 1968) para aproximar una distribución de probabilidad por un producto de
probabilidades de segundo orden.
Se trata de un problema de optimización para obtener la estructura en forma de árbol que
más se aproxime a la distribución “real”. Para ello se utiliza una medida de la diferencia de
información entre la distribución real (P) y la aproximada (P*) usando la expresión:
I(P, P*) =?P(X)log(P(X)/ P*(X))
x
(1.3)
El objetivo es minimizar I. Para ello se puede definir esta diferencia en función de la
información mutua entre pares de variables, de la siguiente forma:
Capítulo I. Las redes bayesianas y la Bioinformática
15
log (P(X i, X j))
P(X i) P(X j)
I(X i, X j) =?P(X i, X j)
x
(1.4)
Se puede demostrar (Chow y Liu 1968) que la diferencia de información es una función del
de la suma de las informaciones mutuas (pesos) de todos los pares de variables que
constituyen el árbol con signo cambiado. Por ello se necesita encontrar el árbol con mayor
peso. Basado en lo anterior, el algoritmo para determinar el árbol bayesiano óptimo a partir
de datos es el siguiente:
1. Calcular la información mutua entre todos los pares de variables (n(n-1)/2).
2. Ordenar las informaciones mutuas de mayor a menor.
3. Seleccionar la rama de mayor valor como árbol inicial.
4. Agregar la siguiente rama mientras no forme un ciclo; si lo forma, desechar.
5. Repetir (4) hasta que se cubran todas las variables (n-1 ramas).
El algoritmo no provee la direccionalidad de los arcos, por lo que ésta se puede asignar en
forma arbitraria o utilizando una semántica externa (experto). Además el algoritmo realiza
una búsqueda incompleta, por lo que se puede producir el problema de sobre ajuste, para lo
cual se sugiere en la literatura el uso del estadístico Chi-cuadrado.
El algoritmo no ejecuta vuelta atrás (backtracking) en su búsqueda. Una vez que el
algoritmo selecciona un atributo, nunca reconsiderará esta elección. Por lo tanto, es
susceptible a los mismos riesgos que los algoritmos de ascensión de colinas, por ejemplo,
caer en máximos o mínimos locales (Hernández 2004).
Algoritmo para poli árboles
En (Rebane y Pearl 1988) se extiende el algoritmo de Chow y Liu (Chow y Liu 1968) para
poli árboles. Para ello se parte del esqueleto (estructura sin direcciones) obtenido con el
algoritmo anterior y se determina la dirección de los arcos utilizando pruebas de
dependencia entre tripletas de variables. De esta forma se obtiene una red bayesiana en
forma de poli árbol (ver anexo 1 sobre conceptos básicos). El algoritmo de (Rebane y Pearl
1988) se basa en probar las relaciones de dependencia entre todas las tripletas de variables
en el esqueleto. Dadas tres variables, existen tres casos posibles:
Capítulo I. Las redes bayesianas y la Bioinformática
16
1. Arcos divergentes: X? Y ? Z
2. Arcos secuenciales: X ? Y ? Z
3. Arcos convergentes: X? Y ? Z
Los primeros dos casos son indistinguibles, pero el tercero es diferente, ya que las dos
variables “padre” son marginalmente independientes. Entonces el algoritmo consiste en:
1. Obtener el esqueleto utilizando el algoritmo de Chow y Liu.
2. Recorrer la red hasta encontrar una tripleta de nodos que sean convergentes (tercer
caso) o nodo “multipadre”.
3. A partir de un nodo “multipadre” determinar las direcciones de los arcos utilizando la
prueba de tripletas hasta donde sea posible (base causal).
4. Repetir 2-3 hasta que ya no se puedan descubrir más direcciones.
5. Si quedan arcos sin direccionar, utilizar semántica externa para obtener su dirección.
El algoritmo está restringido a poli árboles y no garantiza obtener todas las direcciones.
Desde el punto de vista práctico, un problema es que generalmente no se obtiene
independencia absoluta (información mutua cero), por lo que habría que considerar una
cota empírica que “aproxima” la independencia.
Algoritmos para redes múltiplemente conexas
Existen dos clases de métodos para el aprendizaje genérico de RB, que incluyen redes
múltiplemente conexas. Éstos son:
1.
2.
Métodos basados en medidas de ajuste y búsqueda.
Métodos basados en pruebas de independencia o basados en restricciones.
Los métodos del tipo uno, tienen dos aspectos principales: una medida para evaluar que tan
buena es cada estructura respecto a los datos y un método de búsqueda que genere
diferentes estructuras hasta encontrar la óptima, de acuerdo a la medida seleccionada.
Capítulo I. Las redes bayesianas y la Bioinformática
17
Esta es la ventaja esencial de estos métodos respecto a los basados en restricciones, pues
estos últimos encuentran un único modelo basado en la información categórica de la
independencia condicional entre las variables.
Entre los algoritmos de búsqueda, los clásicos son dos algoritmos de búsqueda golosa (en
inglés greedy search): K2 (Cooper y Herskovits 1992), que opera en el espacio de los
GDA que son compatibles con un orden dado y el algoritmo B de (Buntine 1994), el cual
no tiene en cuenta el orden de las variables. A continuación se describen ambos algoritmos.
Algoritmo K2
Entrada: Un conjunto de variables ordenadas: {X1, . . . , XN}.
Salida: Una estructura de RB G
Etapa de Iniciación:
Para i=1 hasta N hacer
?i = f
// El conjunto de padres de la variable i es vacío
Etapa Iterativa:
Para i=1 hasta N hacer
Repetir
// ?i conjunto de padres de la variable i y qi (?i) contribución de la variable Xi
con conjunto de padres ?i
Seleccionar el nodo Y ? {X1, . . . , Xi-1} ?i que maximiza g = qi(?i n {Y })
d ? g – qi(?i)
sí d > 0 entonces
?i ? ?i n {Y }
hasta que d = 0 ó ?i = {X1, . . . , Xi-1}
18
Capítulo I. Las redes bayesianas y la Bioinformática
Algoritmo B
Entrada: Un conjunto de variables {X1, . . . , XN}.
Salida: Una estructura de RB G
Etapa de Iniciación:
Para i=1 hasta N
?i= f
Para i=1 hasta N y Para j=1 hasta N hacer
sí i ? j entonces
A[i, j] = mi(Xj) . mi(f)
en otro caso
A[i, j]= -8
//no permitir Xi = Xj
y Desci son los
Etapa Iterativa:
repetir
Seleccionar los i, j, que maximizan A [i, j]
sí A[i, j] > 0 entonces
?i ? ?i n {Xj}
// Asceni son los ascendientes de la variable Xi
descendientes del nodo Xi (ver anexo 1)
para Xa ? Asceni, Xb ? Desci hacer
A[a, b]=-8
//no permitir ciclos
para k = 1 hasta N hacer
sí A[i, k] >-8 entonces
A[i, k] = mi(?i n {Xk}) . mi(?i)
hasta que A[i, j] = 0 o A[i, j] = -8, ? i, j
Capítulo I. Las redes bayesianas y la Bioinformática
19
Los algoritmos K2 y B, no garantizan encontrar la solución óptima. Por otra parte, es cierto
que el algoritmo K2 es uno de los más rápidos para aprendizaje en RB y puede utilizarse
para problemas supervisados y no supervisados, pero depende del orden que se establece
entre las variables. No siempre es posible obtener el orden, por ejemplo las posiciones de
las secuencias genómicas no son intercambiables y no es fácil establecer a priori un orden
total de importancia (Acid y De Campos 2003), (Kjærulff y Madsen 2008).
El algoritmo B al igual que el algoritmo K2 inicializa el conjunto de padres de un nodo
como vacío. En el caso del algoritmo K2 la no existencia de ciclos lo garantiza el orden
preestablecido en las variables; el algoritmo B por su parte, chequea en cada paso que no
se formen ciclos. Ambos algoritmos verifican además que al añadir un nuevo arco, este
mejore la medida de calidad que se emplea. El algoritmo K2 termina cuando al añadir un
padre a una variable no incrementa la medida de calidad que se utiliza y ya no quedan más
variables. Este algoritmo no garantiza obtener la red con mayor valor de probabilidad.
La complejidad computacional reportada para ambos algoritmos está basada en la
complejidad por nodo y las veces que se aplica la métrica de calidad. Concretamente, si
para un nodo la complejidad es del orden O(M.K.T), y su calidad se calcula a lo sumo en el
orden O(N2.K) veces, la complejidad del peor caso en ambos algoritmos es de orden
O(N2.K2.M.T), y como K=N se obtiene prácticamente una complejidad máxima O(N 4.M.T)
(Neapolitan 1990), (Bouckaert 1995).
En las expresiones anteriores, los parámetros considerados son:
M: número de casos en la base de ejemplos,
K: cantidad máxima de padres,
N: número de variables o rasgos del problema y
T: cantidad máxima de valores posibles para las variables.
Existen varias medidas para evaluar las RB obtenidas. En (Bouckaert 1995) se hace un
análisis de cada una; las más utilizadas son:
•
Medida bayesiana: estima la probabilidad de la estructura dado los datos
(verosimilitud) la cual se trata de maximizar.
Capítulo I. Las redes bayesianas y la Bioinformática
20
Considerando variables discretas y que los datos son independientes, para cada estructura
de red se puede calcular la frecuencia de los datos originales correctamente predichos por
dicha estructura y comparar estas ocurrencias.
•
Longitud de descripción mínima (en inglés Minimal Description Length, MDL): estima
la longitud (tamaño en bits) requerida para representar la probabilidad conjunta con
cierta estructura, la cual se compone de dos partes: representación de la estructura y
representación del error de la estructura respecto a los datos.
La medida MDL hace un compromiso entre la exactitud y la complejidad del modelo. La
exactitud se estima midiendo la información mutua entre los atributos y la clase; y la
complejidad contando el número de parámetros.
La exactitud se puede estimar en base al “peso” de cada nodo, en forma análoga a los pesos
en el método de aprendizaje de árboles. En este caso el peso de cada nodo se estima en base
a la información mutua con sus padres, el peso (exactitud) total está dado por la suma de
los pesos de cada nodo (Bouckaert 1995), (Morales 2006).
A diferencia del enfoque basado en una medida global, el enfoque basado en pruebas de
independencia usa medidas de dependencia local entre subconjuntos de variables.
Entre los algoritmos más populares para el aprendizaje de RB basado en pruebas de
independencias se encuentra el algoritmo PC (Power Constructor, Constructor eficiente) de
(Spirtes y Meek 1995). Estas pruebas de independencia resultan costosas y es obvio que se
convierte en un problema sobre todo cuando se analizan secuencias largas, por ejemplo de
una proteína mediana, para no citar un genoma completo. A continuación se describe
esqueléticamente el algoritmo.
Algoritmo PC
Entrada: Un conjunto de variables {X1, . . . , XN}.
Salida: Una estructura de red bayesiana G
Paso 1. Realizar pruebas de independencia condicional entre cada par de variables.
Paso 2. Identificar el esqueleto o grafo no dirigido en función de la independencia o no
entre las variables
Capítulo I. Las redes bayesianas y la Bioinformática
21
Paso 3. Identificar los arcos convergentes
Paso 4. Identificar los arcos secuenciales y los arcos divergentes
En general ninguno de los algoritmos para obtener la estructura de RB es considerado
mejor, se debe decidir cual es más conveniente usar. Esto depende del problema que se
quiere resolver. Si las variables del problema están fuertemente correlacionadas, no es
posible usar MNB, pues supone independencia entre todas las variables. Tampoco se debe
usar la arquitectura TAN, pues solo se tiene en cuenta la dependencia de las variables
predictivas y la clase, y a lo sumo la relación entre dos variables predictivas, o sea se puede
tener hasta dos padres, incluida la variable clase.
Estos modelos son simples, pero la suposición de independencia que se hace los limita.
Aunque hay muchas referencias de utilización en la bibliografía del modelo MNB, es solo
por su simplicidad.
Los algoritmos K2 y B, también tienen limitaciones, pues son algoritmos de búsqueda
golosa con todas las limitaciones de la misma. El algoritmo K2 además está limitado por el
orden que se debe establecer entre las variables. El algoritmo B está limitado también por
las pruebas para la no existencia de ciclos.
El uso del algoritmo PC está limitado por la cantidad de pruebas de independencia, sobre
todo cuando se consideran dominios de aplicación con muchas variables (por ejemplo más
de cien).
1.1.1.2
Aprendizaje paramétrico de Redes Bayesianas
El aprendizaje paramétrico consiste en encontrar los parámetros asociados a una estructura
dada de una RB. Dichos parámetros consisten en las probabilidades a priori de los nodos
raíz y las probabilidades condicionales de las demás variables, dados sus padres.
Para dominios de aplicación en los que existe conocimiento a priori es posible en principio,
determinar las probabilidades a partir de expertos. Para poder brindar esta información, por
ejemplo en dominios médicos, estos especialistas deberían ser capaces de brindar con
“bastante certeza” los valores de todas las probabilidades condicionales que exige la
estructura de la red. Sin embargo cuando esa estructura es medianamente compleja, la tarea
Capítulo I. Las redes bayesianas y la Bioinformática
22
de determinar las probabilidades de cada uno de los nodos a partir de conocimiento a priori
se hace difícil incluso para buenos expertos. En dominios bioinformáticos esta posibilidad
difícilmente se tiene, por la complejidad intrínseca de los problemas biológicos
involucrados. En cualquier caso, si se dispone de una base de datos, una opción más
prometedora o al menos tranquilizadora, es extraer el conocimiento desde los datos.
Si en la fase de aprendizaje se conocen datos con todas las variables, es fácil obtener las
probabilidades requeridas. Las probabilidades previas corresponden a las marginales de los
nodos raíz, y las condicionales se obtienen de las conjuntas de cada nodo con su(s)
padre(s).
El aprendizaje paramétrico depende de las características de los datos que se utilicen, si se
tiene en cuenta que estos pueden ser completos o no. En la tesis se trabaja
fundamentalmente con datos de aplicaciones Bioinformáticas, en los cuales no siempre hay
conocimiento a priori sobre la información de que se dispone (precisamente es lo que se
busca), y por tanto es necesario aprender desde los datos.
Aprendizaje paramétrico con datos completos
El aprendizaje de los parámetros es simple cuando todas las variables son completamente
observables en el conjunto de entrenamiento. El método más común es el llamado
estimador de máxima verosimilitud, que consiste esencialmente en estimar las
probabilidades deseadas a partir de la frecuencia de los valores de los datos de
entrenamiento.
La calidad de estas estimaciones dependerá de que exista un número suficiente de datos en
la muestra. Cuando esto no es posible se puede cuantificar la incertidumbre existente
representándola mediante una distribución de probabilidad a priori, para así considerarla
explícitamente en la definición de las probabilidades. Habitualmente se emplean
distribuciones Beta (Saucier 2000) en el caso de variables binarias, y distribuciones
Dirichlet (Neapolitan 1990) para variables multivaluadas. Esta aproximación es además útil
cuando se cuenta con el apoyo de expertos en el dominio de aplicación para concretar los
valores de los parámetros de las distribuciones.
Capítulo I. Las redes bayesianas y la Bioinformática
23
Si existen variables de tipo continuo la estrategia más habitual es discretizarlas antes de
construir el modelo estructural. Existen algunos modelos de RB con variables continuas,
pero están limitados a variables gaussianas relacionadas linealmente (Kenley 1986). La
mayoría de los modelos ya establecidos suponen variables discretas.
Aprendizaje paramétrico con datos incompletos
Aparecen mayores dificultades cuando los datos de entrenamiento no están completos. En
este sentido pueden plantearse dos tipos de información incompleta:
•
•
Valores faltantes: Faltan algunos valores de uno o varias variables en algunos ejemplos.
Nodo oculto: Faltan todos los valores de una variable.
El primer caso es más sencillo, y existen varias alternativas para tratarlos, entre ellas:
1. Eliminar los ejemplos con valores ausentes.
2. Considerar un nuevo valor adicional para la variable: ‘desconocido’.
3. Considerar el valor más probable a partir de los datos de la misma en las demás
instancias.
4. Considerar el valor más probable en base a las demás variables (supone cierto estudio
de correlación).
Las dos primeras opciones son habituales en problemas de aprendizaje, y válidas siempre y
cuando se cuente con un número elevado de datos completos. La tercera opción viene a
ignorar las posibles dependencias de la variable con las demás, cuando ya se cuenta con la
estructura que las describe en el grafo; no suele proporcionar los mejores resultados (Stuart
y Norvig 1996). La cuarta técnica se sirve de la red ya conocida para inferir los valores
desconocidos. Primero se rellenan las tablas de parámetros usando todos los ejemplos
completos. Después, para cada instancia incompleta, se asignan los valores conocidos a las
variables correspondientes en la red y se propaga su efecto para obtener las probabilidades
a posteriori de las variables no observadas. Entonces se toma como valor observado el más
probable y se actualizan todas las probabilidades del modelo antes de procesar la siguiente
instancia incompleta.
Capítulo I. Las redes bayesianas y la Bioinformática
24
La aparición de nodos ocultos requiere un tratamiento más complejo que no es objetivo de
esta investigación abordar. Para un mejor estudio de este tema consultar (Stuart y Norvig
1996).
1.1.2
Propagación en Redes Bayesianas
Para los distintos sistemas de inferencia probabilística, el objetivo principal es el cálculo de
la distribución de probabilidad posterior de un conjunto de variables de consulta, en base a
determinadas variables de evidencia. En (Castillo et al. 1997), se hace referencia a distintos
algoritmos para la propagación de evidencias.
La clasificación de estos algoritmos se basa en la forma en que se usa la red, o sea, si se
trabaja directamente con la red obtenida: algoritmo de inversión de arcos (Schachter 1990)
y algoritmo de eliminación de variables (Shenoy 1992) o con estructuras auxiliares para
propiciar el paso de mensajes: propagación en árboles de unión (junction trees) (Pearl
1988), (Castillo et al. 1997), (Jensen 2001), (Schachter 1994), (Baldi y Soren 2001), (El-
Hay 2001), (Jensen y Nielsen 2007),), (Kjærulff y Madsen 2008) y propagación perezosa
(lazy propagation) (Shenoy 1992), (Madsen y Jensen 1999).
En el presente trabajo, se describen dos algoritmos de propagación exacta: el primero
mediante árboles de unión (Pearl 1988), (Castillo et al. 1997), (Jensen 2001), (Schachter
1994), (Baldi y Soren 2001), (El-Hay 2001), (Jensen y Nielsen 2007),), (Kjærulff y Madsen
2008), (El-Hay 2001) y el segundo basado en la eliminación de variables (Shenoy 1992). El
primer algoritmo se puede utilizar para propagación de evidencias en redes múltiplemente
conexas, transformando la estructura inicial en un árbol de familias (ver anexo 1). Se
escoge este algoritmo teniendo en cuenta que según (El-Hay 2001) el algoritmo de
propagación en árboles de unión es uno de los más populares, de hecho es uno de los más
utilizados en las herramientas de RB revisadas, por ejemplo HUGIN. El algoritmo de
eliminación de variables se escoge basado en las experiencias de los miembros del proyecto
ELVIRA7, que manifiestan que es el algoritmo menos complejo para esta tarea.
7
Curso de Modelos Gráficos impartido por profesor Manuel Gómez, Departamento de Ciencias de la
Computación e IA, Universidad de Granada, en el doctorado curricular sobre Soft computing, desarrollado en
la UCLV.
Capítulo I. Las redes bayesianas y la Bioinformática
25
La propagación de evidencias, para el caso exacto, se realiza si se tiene en cuenta un
conjunto de variables evidenciales E ? D con valor evidencial E = e (e representa uno de
los posibles valores de la variable de evidencia) y el conjunto de variables no evidenciales
D | E para las cuales se calculan las probabilidades condicionales P(Xi | e). Una forma de
calcular P(Xi | e) es mediante la fórmula de Bayes, pero el método resulta ineficiente desde
el punto de vista computacional debido al elevado número de combinaciones de valores que
involucra. Si se tienen en cuenta las estructuras de independencias entre las variables se
reduce el número de cálculos considerablemente.
1.1.2.1
Propagación en árboles de unión
El método de agrupamiento, inicialmente desarrollado por (Lauritzen y Spiegelhalter
1988), se basa en la construcción de subconjuntos de nodos (aglomerados, conglomerados
o cliques) que capturan las estructuras locales del modelo probabilístico asociado al grafo.
De esta forma, el proceso de propagación de evidencia puede ser acometido calculando
probabilidades locales (que dependen de un número reducido de variables), evitando así
calcular probabilidades globales (que dependen de todas las variables). Los conglomerados
de un grafo son los subconjuntos que representan sus estructuras locales. A continuación, el
algoritmo de agrupamiento calcula los conglomerados del grafo, luego obtiene las
funciones de probabilidad condicionada de cada conglomerado, calculando de forma
iterativa varias funciones de probabilidad locales. Por último, se obtiene la función de
probabilidad condicionada de cada nodo marginalizando la función de probabilidad de
cualquier conglomerado en el que esté contenido. Algunas modificaciones de este método
utilizan una representación gráfica de la cadena de conglomerados para propagar la
evidencia de forma más eficiente (Castillo et al. 1997).
En el presente trabajo se utiliza un algoritmo que realiza una modificación del algoritmo de
agrupamiento, que se basa en el envío de mensajes en un árbol de unión construido a partir
P(x1,K,xN)=??i(ci)
Capítulo I. Las redes bayesianas y la Bioinformática
26
de una cadena de conglomerados. De igual forma que el método de agrupamiento, este
método de propagación en árboles de unión es válido para redes de Markov8 y RB.
Factorización de la DPC por potencias
Sean C1 C2,…, Cm subconjuntos de un conjunto de variables V = {X1, X2…, XN}. Si la DPC
de X1, X2…, XN puede ser escrita como un producto de m funciones no negativas ?i, (i = 1,
2, …, m), esto es,
m
i=1
(1.5)
donde ci es la realización de Ci, las funciones ?i se llaman factores potenciales o funciones
potenciales de la DPC.
Para RB, la representación potencial se construye a través del grafo no dirigido obtenido
moralizando9 y triangulando (ver anexo 1) el grafo original. Esta representación potencial
se obtiene asignando la función de probabilidad condicionada, P(xi | ?i), de cada nodo Xi a
la función potencial de un conglomerado que contenga a la familia del nodo (Castillo et al.
1997).
Por tanto, para describir el método de propagación mediante árboles de unión se supone
que se tiene un grafo no dirigido triangulado con conglomerados C = {C1, C2…, Cm} y una
representación potencial ? = {?1(c1),…, ?m (cm)}. Este método utiliza un árbol de unión del
grafo para propagar la evidencia.
Absorción de la evidencia
Si se modifican las funciones potenciales de los conglomerados que contienen nodos
evidenciales en la forma siguiente: para cada conglomerado Ci que contenga algún nodo
evidencial, la nueva función potencial ?i*(ci) se define como:
8
donde G es un grafo no dirigido y ?es un conjunto de funciones potenciales definidas en los conglomerados
asociados al grafo no dirigido G.
9
esto es “casar” a los padres de cada nodo.
?i*(ci)= ?
P(x | e)???i*(ci)
Capítulo I. Las redes bayesianas y la Bioinformática
27
si algún val orenci es inconsiste nte con e,
en otro caso
? 0,
??i(ci),
(1.6)
Para el resto de los conglomerados no es necesario realizar ningún cambio. Luego se tiene:
m
i=1
(1.7)
El algoritmo de propagación exacta mediante la unión de árboles puede enunciarse de la
siguiente forma:
Algoritmo de propagación exacta mediante árboles de unión
Entrada: Una RB (G, P) con variables aleatorias X y la distribución X | ?X
asociada a
cada nodo X y un conjunto de nodos de evidencia E ? G con valor evidencial E = e.
Salida: Dependencias de probabilidad condicional P(Xi| e) para cada nodo no evidencial Xi.
Pasos iniciales:
1. Obtener el árbol de familias para el GDA G. Sea C = {C1, C2, …, Cm} el conjunto de
conglomerados resultantes.
2. Asignar cada nodo Xi en G a uno y sólo un conglomerado que contenga Xi. Sea Ai el
conjunto de nodos asignados al conglomerado Ci.
3. Para cada conglomerado Ci en C definir:
i
?P(X
xi?Ai
?i(Ci)=
|p i)
(1.8)
4.
Si Ai = Ø, entonces definir ? i(Ci) = 1.
Absorber la evidencia E = e en las funciones potenciales ? = {?1(C1), ?1(C2)…,
?m(Cm)}.
Pasos iterativos
5.
Para i = 1, 2, …, m hacer: Para cada vecino Bj del conglomerado Ci, si Ci ya recibió
los mensajes de todos sus vecinos, calcular y enviar el mensaje Mij(Sij) a Bj, donde:
Capítulo I. Las redes bayesianas y la Bioinformática
Mij(sij)=??i(Ci)?Mki(ski)
ci sij k? j
28
(1.9)
6.
7.
Repetir el paso 5 hasta que no pueda ser calculado ningún nuevo mensaje.
Calcular la DPC de cada conglomerado Ci usando:
(1.10)
P(ci)=?i(Ci)?M ki(sik)
k
Para cada nodo no evidencial Xj en la red calcular P(Xj | e) usando:
? P(Ck)
ck x j
P(X j | e)=
(1.11)
donde Ck es el conglomerado menor que contiene a Xj.
1.1.2.2
Algoritmo de propagación mediante la eliminación de variables
Entrada: Una RB (G, P) en la que:
T: conjunto de factores potenciales iniciales. Inicialmente: distribuciones asociadas a las
variables de la red,
X: variables de la red,
H: variables objetivo, aquellas sobre las que versa la consulta,
E: conjunto de variables evidenciales, variables observadas,
Y: variables a eliminar de la red: Y = X {H, E} (siempre y cuando no estén d-separadas de
H dado E ni sean sumideros), ver anexo 1 sobre conceptos básicos.
Salida: Dependencias de probabilidad condicional P(Xi | e) para cada nodo no evidencial
Xi.
A continuación se describen los pasos del algoritmo basado en la eliminación de variables.
1. Para cada variable Z ? Y
•
Sea ?Z el conjunto de factores potenciales en T que contienen a la variable Z
?(x)= arg min k?c=1cost(k,c)p(c | x1, x2, …, xN )
Capítulo I. Las redes bayesianas y la Bioinformática
29
•
•
•
2.
1.1.3
Sea fZ el potencial obtenido de la combinación de todos los potenciales en ?Z
Marginalizar fZ para eliminar Z : f = ?Z fZ
Actualizar el conjunto de potenciales: T = (T – fZ ) n f
Aquí solo quedarán potenciales definidos sobre las variables de interés H
Las Redes Bayesianas como clasificadores
Un problema de clasificación se define así: dado un conjunto de entrenamiento T con un
conjunto de clases C, encontrar una descripción tal que se pueda encontrar la clase Cj de un
objeto ti sin hacer uso de T. Estrictamente, según (Aytug 2000) encontrar la función de
membresía: f: T ? C tal que la probabilidad P (f (ti)= cj ) sea aproximadamente 1, ti e T, cj e
C.
Una RB puede ser utilizada como un clasificador en el caso particular en el que el nodo no
evidenciado y a inferir es precisamente el que representa la variable clase o variable
dependiente; en este caso se habla de un clasificador bayesiano. Los clasificadores
bayesianos minimizan el costo del error en la clasificación usando la siguiente función:
ro
(1.12)
donde cost (k, c) denota el costo de una mala clasificación según cierto criterio. En el caso
de una función para dos clases, el clasificador asigna la clase a posteriori más probable
para una instancia dada, o sea:
?(X)= arg max C p(C | X 1, X 2, …, X N )= arg max C p(C)p(X 1, X 2, …, X N | C)
(1.13)
En dependencia de la forma en que se aproxime p(X1, X2, …,XN | C) se obtienen diferentes
clasificadores (Larrañaga et al. 2005).
Cuando las RB se usan como clasificadores, se está en presencia de problemas de
clasificación supervisada, pues la clase forma parte del conjunto de entrenamiento, o sea se
conoce para cada objeto o ejemplo, la clase a la que pertenece (Larrañaga 2000). En este
caso el problema se formula del siguiente modo: Sea Cj la variable clase, y {X1, X2 , …, XN}
Capítulo I. Las redes bayesianas y la Bioinformática
vector de rasgos que describen cada caso; p(Cj | {X1, X2,
…,
30
XN}) probabilidad de que un
objeto con las características {X1,X2, …,XN} pertenezca a la clase Cj. Se trata de encontrar la
clase Cj* verificando que p(Cj* | {X1,X2, …,XN})= maxj p(Cj | {X1,X2, …,XN}).
Para el clasificador Naïve Bayes (CNB) (Duda y Hart 1973) la probabilidad de que el i-
ésimo ejemplo pertenezca a la clase j-ésima puede calcularse aplicando el teorema de
Bayes. El clasificador CNB no obtiene resultados favorables en los casos de dominios en
los que las variables estén correlacionadas.
En (Friedman et al. 1997a) se presenta el método CNB aumentado a árbol, conocido en la
literatura como algoritmo TAN (Tree Augmented Naïve Bayes), con este modelo se obtienen
mejores resultados que con CNB, a la vez que mantiene la simplicidad computacional de
éste. El modelo TAN es una red bayesiana en la que la variable a clasificar no tiene padres,
mientras que el conjunto de variables padres de cada una de las variables predictoras, Xi,
contiene necesariamente a la variable a clasificar, y a lo sumo otra variable. El algoritmo
propuesto por (Friedman et al. 1997a) es una adaptación del algoritmo de (Chow y Liu
1968) y calcula la información mutua entre cada par de variables dada la clase. El mismo
garantiza que la estructura obtenida tiene asociada la máxima verosimilitud entre todas las
estructuras TAN posibles. El modelo TAN está limitado por el número de padres de las
variables predictivas. En la página 275 del libro de Jensen se puede obtener la descripción
detallada del mismo, (Jensen y Nielsen 2007). El k Dependence Bayesian classifier (kDB,
clasificador bayesiano con k dependencias) (Sahami 1996) evita esta restricción pues una
variable predictiva puede tener hasta k padres además de la clase. La complejidad de estos
algoritmos es O(N2) para la arquitectura TAN y O(N2 (M.C.T2 + K)) para la arquitectura
kDB, donde N es el número de variables del problema, C la cantidad de clases, T número
máximo de valores descritos que un rasgo puede tener y M el número de casos de la base de
ejemplos.
En (Pazani 1996) se presenta un modelo en el que se reduce el número de probabilidades a
considerar, pues las variables no relevantes para el problema se consideran como en el
modelo CNB y las condicionalmente dependientes dada la clase, se unen en una sola; para
ello proponen usar dos algoritmos voraces, que se basan en la teoría de modelización hacia
delante y hacia atrás (Larrañaga 2000).
Capítulo I. Las redes bayesianas y la Bioinformática
31
1.1.3.1
Necesidad de la reduccion de atributos en algunos casos
Uno de los problemas de todo proceso de aprendizaje es escoger los atributos para describir
los datos. Frecuentemente se dispone de más rasgos de los que son necesarios para
aprender, y muchos algoritmos de aprendizaje tienen problemas cuando hay bastantes
atributos irrelevantes. Por ello hacen falta técnicas que permitan reconocer atributos no
necesarios. Existen dos aproximaciones para la selección de atributos:
•
Transformación del conjunto de datos a un espacio de menor número de dimensiones
(técnicas no supervisadas de reducción de dimensiones: Análisis de
componentes
principales (Dillon y Goldstein 1984), (Escofier y Pages 1992), (Lebart 1998), escalado
multidimensional (Peña 2002), proyección aleatoria (Ruiz 2006).
•
Obtención del subconjunto de atributos más adecuado para la predicción (técnicas
supervisadas: técnicas de filtrado (Filters) o técnicas de envoltura (Wrappers), propuestas
por (John et al. 1994).
Técnicas de filtrado: Suponen que se tiene una medida de evaluación de cada atributo que
permite obtener su relevancia respecto al objetivo, establecen un orden para los atributos
midiendo su relevancia en la predicción de la clase separadamente (computacionalmente
barato) y a partir del orden se decide cuantos atributos eliminar. Son ejemplos: Entropía
(ID3), prueba Chi-cuadrado (por ejemplo CHAID), relief (creencia) (Larrañaga et al.
2003), (Lanzi 2006), (John et al. 1994).
Técnicas de envoltura: Evalúan subconjuntos de atributos hasta encontrar el más
adecuado (computacionalmente caro), para la evaluación utilizan un algoritmo de
aprendizaje y no se puede hacer una búsqueda exhaustiva. Entre estas técnicas se
encuentran Hill-climbing (ascensión de colinas), simulated annealing (recocido
simulado), best first (primero el mejor), algoritmos genéticos, etc. En general en estas
técnicas hay dos estrategias: Forward selection (selección hacia delante), backward
elimination (eliminación hacia atrás) (Larrañaga et al. 2003) (Lanzi 2006) (John et al.
1994), (Ruiz 2006).
Los problemas de bioinformática se caracterizan por un gran número de rasgos, por lo que
en la mayoría de los casos se hace necesario la reducción de dimensionalidad (Saeys 2004).
Capítulo I. Las redes bayesianas y la Bioinformática
32
Además, el alto costo en tiempo y recursos que han mostrado los algoritmos exactos de
búsqueda, ha conllevado al auge y desarrollo de heurísticas y metaheurísticas cuyo uso ha
arrojado resultados muy alentadores. Pueden citarse por ejemplo los algoritmos que usan
heurísticas aleatorias bioinspiradas como método de búsqueda en la selección de rasgos,
entre ellos, los algoritmos genéticos (Li et al. 2004), la optimización basada en enjambres
de partículas (Kennedy 1997), (Kennedy y Eberhart 1995b),(Kennedy y Eberhart 1995a),
(Kennedy y Spears 1998). y las colonias de hormigas (Dorigo y Stützle 2002), (Dorigo y
Stützle 2004), (Dorigo et al. 2006), (Dorigo 2007).
Dentro de los algoritmos bioinspirados usados para la selección de rasgos, la Inteligencia
de Enjambres (Swarm Intelligence, SI) ha sido objeto de estudio, investigación y de mucha
aplicación por su simplicidad y robustez.
1.1.3.2
Optimización de enjambres de partículas
La metaheurística PSO, fue desarrollada por Kennedy y Eberhart (Kennedy y Eberhart
1995b), (Kennedy y Eberhart 1995a) y está inspirada en el comportamiento social
observado en grupos de individuos tales como bandadas de pájaros, enjambres de insectos
o bancos de peces. Un enjambre se define como una colección estructurada de organismos
(agentes) que interactúan. La inteligencia no está en los individuos sino en la acción de
todo el colectivo. Tal comportamiento social se basa en la transmisión del éxito de cada
individuo a los demás del grupo, lo cual resulta en un proceso “sinergético” que permite a
los individuos satisfacer de la mejor manera posible sus necesidades más inmediatas, tales
como la localización de alimentos o de un lugar de cobijo. Cada organismo (partícula) se
trata como un punto en un espacio N dimensional el cual ajusta su propio “vuelo” de
acuerdo a su propia experiencia y la experiencia del resto de la banda. La banda (swarm)
“vuela” por el espacio de búsqueda localizando regiones o partículas prometedoras
(Kennedy y Spears 1998).
La metaheurística PSO ha mostrado ser muy eficiente para resolver problemas de
optimización de un sólo objetivo con rápidas tasas de convergencia (Kennedy et al. 2001).
Dado un espacio de decisión N-dimensional, cada partícula i del enjambre conoce su
posición actual Xi ={Xi1, Xi2,…, XiN}, la velocidad Vi = {Vi1, Vi2, …, ViN} con la cual ha
llegado a dicha posición, así como la mejor posición XiBest= {XiBest1, XiBest2,…, XiBestN} en la
Capítulo I. Las redes bayesianas y la Bioinformática
33
que se ha encontrado, denominada “mejor personal”. Además, todas las partículas conocen
la mejor posición encontrada dentro del enjambre XgBest denominada “mejor global”.
Si se supone el uso de la información proveniente del mejor global, en cada iteración t del
algoritmo PSO, cada componente j de la velocidad y la posición de cada partícula i del
enjambre se actualiza conforme a:
Vi = wVi +c1 rand(X iBesti – X i)+c2 Rand(X gBest – X i)
(1.14)
donde w es el parámetro de inercia que regula el impacto de las velocidades anteriores en la
nueva velocidad de la partícula. Típicamente a w se asigna un valor fijo, por ejemplo 0.8 y
en otros casos se le asigna un valor inicial entre 1 y 1.5 que se hace decrecer durante la
ejecución del algoritmo o funciones que garantizan esto, como por ejemplo w = 0.5 +
rand()/2. O sea, se proponen pesos de inercia altos al principio y se reducen con el número
de iteraciones. Si w=0 la velocidad de la partícula se determina por las mejores posiciones
ya sea su mejor posición o la mejor posición global alcanzada por todas las partículas.
Sí w toma un valor grande, significa que las partículas deben cambiar su velocidad
instantáneamente y moverse lejos de la mejor posición según su conocimiento, o sea se
favorece la exploración global (global search), si w es pequeño, la razón en la cual la
partícula debe cambiar su velocidad es baja, es decir la inercia sugiere continuar el camino
original, aún cuando se conozca el mejor estado (fitness), se favorece la exploración local
(local search).
El valor c1 es el parámetro cognitivo que indica la influencia máxima de la mejor
experiencia individual de la partícula en su nueva velocidad y c2 es el parámetro social que
indica la influencia máxima de la información social en el nuevo valor de velocidad de la
partícula; mientras que, rand() y Rand() son funciones que retornan un número aleatorio en
el intervalo [0, 1], mediante el cual se determina la influencia real de las informaciones
individual y social en la nueva velocidad para la partícula.
La selección de estos parámetros tiene impacto en la velocidad de convergencia y la
velocidad del algoritmo para encontrar el óptimo. En (Chávez et al. 2007c), se tomaron por
ejemplo los valores c1= c2=2, pero en realidad se recomienda en el trabajo que c1 y c2 no
Capítulo I. Las redes bayesianas y la Bioinformática
34
tomen necesariamente el mismo valor sino, que se generen aleatoriamente con distribución
uniforme en el intervalo [0, 2]. En (Beielstein et al. 2002) se recomienda que la suma de
estos valores sea menor o igual a 4. El trabajo de Beielstein et al. resulta interesante pues
hace un análisis de los parámetros del algoritmo PSO mediante técnicas de diseños
experimentales (Mahamed et al. 2005). Para obtener una mayor información acerca de la
influencia de estos parámetros en la efectividad del algoritmo PSO ver (Beielstein et al.
2002; Kennedy et al. 2001; Shi y Eberhart 1998).
En el presente trabajo se utiliza PSO binario como algoritmo de búsqueda de la estructura
simplificada, por selección de rasgos, de una RB.
1.1.3.3
Evaluación de las Redes Bayesianas como clasificadores
Cuando las RB se utilizan como un modelo clasificador, se hace necesario evaluar su
desempeño, al igual que se realiza la evaluación en cualquier problema de clasificación
supervisada. Para ello se utilizan criterios10 tales como: porciento de clasificaciones
correctas, diferentes medidas del error, el índice de Kappa (Brender et al. 1994), medida F
(Van Rijsbergen 1979), y funcionales de calidad y error (Ruiz-Shulcloper 2000), (Donald et
al. 1994). La capacidad del modelo para representar confiablemente el sistema real, se
relaciona esencialmente con la precisión (Daalen 1992), no existe un modelo clasificador
mejor que otro de manera general; para cada problema nuevo es necesario determinar con
cuál se pueden obtener mejores resultados, y es por esto que han surgido varias medidas
para evaluar la clasificación y comparar los modelos empleados para un problema
determinado. Las medidas más conocidas para evaluar la clasificación están basadas en la
matriz de confusión que se obtiene cuando se prueba el clasificador en el conjunto de datos
del entrenamiento o en un conjunto de datos externos que no intervienen en el aprendizaje.
En la Tabla 1.1 se muestra la matriz de confusión de un problema de dos clases, donde
Pos/poses la clase positiva y Neg/neg la clase negativa.
10
Indistintamente se utilizan los términos criterio o medida para hacer referencia a los aspectos cuantitativos
o cualitativos a considerar en la evaluación.
35
Capítulo I. Las redes bayesianas y la Bioinformática
Tabla 1.1. Matriz de confusión de un problema de dos clases
En la Tabla 1.1 las siglas VP y VN representan los elementos bien clasificados de la clase
positiva y negativa respectivamente y FP y FN identifican los elementos negativos y
positivos mal clasificados respectivamente. Basados en estas medidas, se calcula el error,
la exactitud, la razón de VP (rVP) o sensibilidad, la razón de FP (rFP), la precisión y la
especificidad, el coeficiente de correlación de Matthews (mcc), que se muestran en las
expresiones de la Tabla 1.2.
Tabla 1.2. Medidas de evaluación estándar
Capítulo I. Las redes bayesianas y la Bioinformática
36
Otra forma de evaluar el rendimiento de un clasificador es por las curvas ROC (Receiver
Operator Curve, Curva de operación del receptor) (Fawcett 2004). En esta curva se
representa el valor de razón de VP contra la razón de FP, mediante la variación del umbral
de decisión. Se denomina umbral de decisión a aquel que decide si una instancia x, a partir
del vector de salida del clasificador, pertenece o no a cada una de las clases. Usualmente,
en el caso de dos clases se toma como umbral por defecto 0.5; pero esto no es siempre lo
más conveniente. Se usa el área bajo esta curva, denominada AUC (Area Under the Curve,
área bajo la curva ROC) como un indicador de la calidad del clasificador. En tanto dicha
área esté más cercana a la unidad, el comportamiento del clasificador está más cercano al
clasificador perfecto (aquel que lograría 100% de VP con un 0% de FP).
En (Larrañaga et al. 2005) se hace una comparación de diferentes paradigmas de
clasificación supervisada en Bioinformática: bayesianos, estadísticos, inductivos y de IA.
Resulta interesante el uso de las curvas ROC para la comparación, así como análisis de la
razón de error basado en la matriz de confusión (Fawcett 2004). Además se describe como
estimar la razón de error cuando se usa el modelo para clasificar nuevas instancias. En
(Friedman y Goldszmidt 1996) se exponen en detalle los clasificadores bayesianos
explicados anteriormente y se hace una comparación de ellos con los criterios de medida
descritos y utilizando bases de datos disponibles en el sitio Web de la Universidad de
California Irvine: UCIML para el aprendizaje automático (Asuncion y Newman 2007).
1.1.4
Productos de software para Redes Bayesianas
Múltiples productos de software se han creado para el uso de RB. Los primeros resultaron
costosos, pues fueron el resultado de grandes proyectos de investigación como por ejemplo:
Netica, Elvira11, Hugin (Madsen et al. 2005). A Netica y Hugin se puede acceder
gratuitamente a una versión demostrativa de los mismos pero como se consideran software
propietario o comercial, esta versiones de prueba, no permiten utilizar todas sus
capacidades (Ver anexos 2 y 3). Por ejemplo en el caso de Hugin se puede trabajar en este
11
Elvira es fruto de un proyecto de investigación, en el que participan investigadores de varias universidades españolas y de otros
centros. Está destinado a la edición y evaluación de modelos gráficos probabilistas, concretamente RB y diagramas de influencia. Está
escrito y compilado en Java, lo cual permite que funcione en diferentes plataformas y sistemas operativos (MS-DOS/Windows, Linux,
Solaris, etc.)
Capítulo I. Las redes bayesianas y la Bioinformática
37
modo demo hasta con 20 variables solamente, lo que resulta evidentemente insuficiente
para resolver
problemas de análisis de secuencias aunque fuese con el objetivo de
comparar resultados con otras herramientas. El software Elvira tiene características
diferentes, de hecho se han realizado programas que permiten hacer la conversión de datos
entre Weka y Elvira. La tendencia en la actualidad es la de realizar herramientas con código
libre (open source) y hacer extensiones al mismo con los algoritmos que se proponen.
En (Murphy 2005) se hace una comparación detallada de 46 productos de software de RB,
la que se resume en el apéndice 2. En (KDnuggets 2008) se hace una descripción de otros
productos discretizados en software propietario y software libre, ver resumen en anexo 3.
En el trabajo de (Doldán 2007) se comentan los productos de software del anexo 2 y otras
direcciones de Internet con herramientas sobre RB. En (Charles River Analytics 2004) se
describe el software BNet: familia de herramientas para construir y usar redes de creencia
(se utiliza como ayuda en la predicción y visualización del pronóstico del tiempo). Incluye
dos productos:
•
•
BNet.Builder: Para crear RB, entrar información y obtener resultados.
BNet.EngineKit: Para incluir la tecnología de las RB en nuestras aplicaciones.
En el contexto de esta investigación se utiliza el software libre Weka al que se hace
extensiones para probar los algoritmos que se presentan. Se utiliza además una versión del
Weka que permite una cierta paralelización en un cluster de computadoras real, como el que
existe en la UCLV o un cluster virtual, todo lo cual ayuda a reducir la complejidad
computacional en tiempo de procesamiento.
1.2
Aplicaciones de las Redes Bayesianas en Bioinformática
Como se ha argumentado, las RB constituyen un formalismo muy atractivo de
representación del conocimiento con incertidumbre, resultado de la sinergia entre métodos
probabilísticos-estadísticos de análisis de datos y técnicas de IA. Ellas se han aplicado con
éxito en muy diversos campos, para modelar la incertidumbre en sistemas expertos, para
resolver problemas de clasificación, predicción, inferencia, sistemas de toma de decisiones,
entre otros. La Bioinformática no se exceptúa como campo de aplicación. Siempre que
surge la necesidad de extraer información desde datos, en presencia de incertidumbre, datos
Capítulo I. Las redes bayesianas y la Bioinformática
38
ruidosos o sujetos a errores, los métodos bayesianos son ampliamente utilizados por las
ventajas que ofrece sobre las técnicas estadísticas convencionales (Jeroen et al. 2008),
(Silva y Muñoz 2000).
También se ha comentado que el desarrollo alcanzado por las Ciencias Biológicas ha
permitido la acumulación de mucha información experimental disponible en grandes bases
de datos. La secuenciación del ADN (Consortium 2004 ), (Benson et al. 2005), produjo un
crecimiento exponencial de las descripciones lineales de proteínas y moléculas de ADN y
ARN (Ácido ribonucleico) y planteó los problemas informáticos de interés biológico: el
almacenamiento y manejo eficiente de la información y la extracción de información útil
para en última instancia, comprender las relaciones entre los genes, las proteínas, la
funcionabilidad, la vida y la salud. La Bioinformática constituye el campo de
conocimientos multidisciplinario entre la biología, la informática y la matemática que debe
abordar este problema. En ella surge en particular, la necesidad de desarrollar nuevos
algoritmos para el tratamiento de problemas de análisis de secuencias.
1.2.1
Estudio de secuencias genómicas
Los algoritmos de aprendizaje automático son ideales para dominios caracterizados por la
presencia de gran cantidad de datos, patrones ruidosos y la ausencia de teorías generales
determinísticas. La idea fundamental de estos algoritmos es aprender automáticamente la
“teoría” a partir de los datos, a través de un proceso de inferencia o inducción, modelación
o aprendizaje desde ejemplos, aunque la inducción sea incompleta, y por tanto
condicionada a una probabilidad, según criterios bayesianos.
En (Larrañaga et al. 2005) se describen los principales dominios biológicos donde son
necesarias las técnicas de aprendizaje automático. En dicho documento se hace una división
en seis dominios fundamentales: genómica, proteómica, micro-arreglos (antes citados como
matrices de ADN o micro arrays), sistemas biológicos, evolución y minería de texto. El
resto de las aplicaciones se agrupan en “otras”. Todos estos dominios tienen problemas en
los que se hace necesario el estudio de secuencias biológicas. La genómica es considerada
uno de los dominios más importantes pues como se ha descrito anteriormente, la cantidad
de secuencias identificadas se incrementa notablemente en esta época. El análisis de
Capítulo I. Las redes bayesianas y la Bioinformática
39
secuencias genómicas persigue fundamentalmente la búsqueda de genes, y de sus regiones
regulatorias. De igual modo, el dominio de la proteómica resulta de interés en la actualidad.
De hecho en la presente tesis se analizan dos problemas fundamentales, uno en el campo de
la genómica: localización de sitios de splicing o corte de intrones, y otro en el dominio de
la proteómica para la predicción de interacciones de proteínas.
En Internet se cuenta con herramientas para el análisis de secuencias, algunas de las que se
describen en el anexo 4, extraído del libro: (Gibas y Per 2001). Además en el artículo de
(Gilbert 2004) se hace una descripción de los principales productos de software de
Bioinformática libres en Internet. Este último documento es además, de acceso libre.
1.2.2
Problemas bioinformáticos que se resuelven mediante Redes Bayesianas
Las RB son valiosas siempre que sea necesario extraer información desde datos sujetos a
incertidumbre, subjetividad, cualquier tipo de error o ruidosos. Por tanto, no resulta
ninguna sorpresa que las RB se apliquen ampliamente en la actualidad a los campos de la
genética, la genómica, sistemas biológicos, etc. donde este tipo de datos complejos es una
norma. En el trabajo se mencionan sólo algunos ejemplos, pues la literatura en este campo
también crece notablemente con el número de aplicaciones que se realizan (Liu y
Logvinenco 2003), (Wilkinson 2007).
En (Pe’er et al. 2001) se presenta una RB de interacciones entre genes (interacciones de
causalidad, mediación, activación, e inhibición). El método se aplica a expresión de datos
de mutantes de levadura (Saccharomyces Cerevisiae) y se descubren una variedad de
estructuras metabólicas, señales y caminos regulatorios. En (Friedman 2004) se discute otro
problema aplicado a la bioinformática usando un modelo probabilístico.
Las interacciones entre proteínas son importantes para muchos procesos biológicos,
identificarlas resulta vital para comprender la maquinaria de la célula. Las RB han sido
ampliamente utilizadas con este objetivo; en (Wu et al. 2006) se hace uso de esta teoría
para redes de interacciones de proteínas en hongos utilizando solamente anotaciones de
genes ontólogos (Gene Ontology, GO). El nivel más alto de confianza obtenido para la
clasificación de verdaderas interacciones es de un 78 %. En (Jansen et al. 2003) se realizó
una aplicación similar utilizando otros rasgos desde datos genómicos. Resultados en
Capítulo I. Las redes bayesianas y la Bioinformática
40
arabidopsis se pueden ver en (Cui et al. 2007). Otras investigaciones de interacciones de
proteínas se describen en los trabajos (Long et al. 2005), (Lu et al. 2005) y (Qi et al. 2006).
En humanos hay resultados muy interesantes con RB en (Scott y Barton 2007). En
(Asthana et al. 2007) se hace uso de redes probabilistas para predicción de interacciones de
proteínas utilizando, para la propagación, algoritmos previamente usados para redes de
comunicación y en (Troyanskaya et al. 2003) se usan las RB para predicción de función de
genes desde distintas fuentes de datos en la levadura (Saccharomyces cerevisiae).
Otra aplicación bien interesante en este campo es la localización de genes en un genoma
completo, o en una larga secuencia genómica, lo cual fue considerado durante varios años
como el problema principal de la Bioinformática. Contribuye de manera importante a su
solución, la identificación de sitios de splicing, que separan zonas codificantes y no
codificantes. Este es un buen ejemplo de un problema abierto en Bioinformática (Saeys
2004).
El hecho de que el genoma de determinada especie esté completamente o casi
completamente secuenciado significa apenas que se conoce la secuencia de bases de ADN
que lo conforman, pero ello está lejos de implicar que se sabe el rol de todas sus partes,
incluso la localización de subsecuencias donde aparece o puede aparecer un gen, y mucho
menos su funcionalidad. En países como Estados Unidos de América, se da la situación
extrema, por demás sin ningún tipo de ética, que se patenta la información apenas
aproximada de una subsecuencia que probablemente “contiene un gen".
La localización in sílico de los genes se aborda desde varios puntos de vista. Se conoce en
primer lugar que todas las secuencias que representan un gen comienzan con un codón de
inicio y finalizan con uno de los tres codones de terminación, pero la presencia de tales
codones no siempre indica el inicio y el final del gen. Si a ello se une la posible existencia
de hasta seis marcos diferentes de lectura12, así como la presencia de zonas amplias no
12
En una secuencia de ADN, las tripletas codificantes (codones) pueden estar alternadas e incluso mezcladas
con secuencias no codificantes. Por tanto, al leer una secuencia de codones, aparecen tres marcos de lectura.
Si además, se tiene en cuenta que pueden aparecer producto de la doble hélice en sentido contrario, se habla
de 6 marcos posibles de lectura.
Capítulo I. Las redes bayesianas y la Bioinformática
41
codificantes y usualmente más largas que los genes mismos, se comprende la dificultad del
problema.
Se ha intentado abordar la localización de los genes a través de otras subsecuencias que
están relacionadas con la estructura primaria de los mismos o su expresión, en particular,
promotors, motifs o los sitios de splicing (splice sites). Se ha abordado el problema desde
diversas técnicas de clasificación de Estadística y de IA.
En general se han logrado buenos resultados, pero la supremacía de estas combinaciones en
lugares que no son verdaderos splice sites hace que, aunque los por cientos de clasificación
sean buenos, se comete un gran error en la predicción de falsos negativos. Otros autores
han centrado sus esfuerzos precisamente en reducir los falsos negativos en la clasificación,
y han logrado muy buenos resultados si se hace una buena selección de rasgos (Saeys 2004)
Con esta mejora se logra superar los índices de clasificación sin dañar el rendimiento del
sistema, recuérdese además que una pequeña cantidad de parámetros permite evitar
problemas como el sobre ajuste u overfitting (Cai et al. 2000).
1.3
Consideraciones finales del capítulo
En el presente capítulo se presentaron los fundamentos teóricos relacionados con el
concepto de RB, se analizaron los problemas actuales de estos sistemas concernientes con
el aprendizaje de la estructura y los parámetros de las mismas.
Se mostró la posible utilización de las RB como modelos de clasificación y más
generalmente, para la inferencia tanto de variables predictoras como de la variable objetivo
o dependiente. Además se plantearon ejemplos de aplicación de estos modelos en el campo
de la Bioinformática y se mostró un resumen de los productos de software más utilizados
para el trabajo con RB.
A partir del análisis realizado, se plantea la necesidad de buscar nuevos algoritmos de
búsqueda de la topología de RB desde datos, implementar en plataformas de software libre
los modelos propuestos para ser usados por la comunidad científica sin restricciones y
aplicar esta teoría en el análisis de secuencias genómicas y en dominios biomédicos.
En el próximo capítulo se proponen tres métodos para la primera tarea.
2. NUEVOS ALGORITMOS DE APRENDIZAJE
ESTRUCTURAL DE REDES BAYESIANAS
Como se ha mencionado, la definición de una RB supone siempre dos tareas. La primera es
caracterizar la estructura de dependencias entre las variables predictoras y la segunda es la
“determinación” de la distribución de probabilidades (parámetros) que permitirá hacer
inferencias. Ambas tareas son muy importantes, pero la primera es esencial por ser la más
complicada y además por ser imprescindible para poder realizar la segunda (Friedman et al.
1997b).
Así, las posibilidades del uso de las RB se amplían si es posible realizar el aprendizaje de
las mejores estructuras y parámetros. Ello es especialmente útil si se logra mejorar el
aprendizaje estructural acorde con el dominio del campo de aplicación, en este caso la
Bioinformática, en el análisis de regiones genómicas codificantes para proteínas, o en un
domino de diagnóstico médico.
Los enfoques propuestos hasta el momento para la primera tarea: (Neapolitan
1990),(Heckerman 1997), (Acid y De Campos 2003), (Acid et al. 2005), (Bouckaert 2007),
(Kjærulff y Madsen 2008), demuestran insatisfacción aún con las soluciones.
A continuación se proponen tres nuevos algoritmos que han sido publicados en detalles en
diversas formas y resumidos en (Chávez et al. 2008d). Dos de ellos están basados en
pruebas de independencia según el estadístico Chi-cuadrado y el tercero está basado en
medidas de ajuste y búsqueda.
2.1
Aprendizaje Estructural de Redes Bayesianas basado en técnicas
estadísticas
Los dos algoritmos que se describen en los siguientes epígrafes permiten obtener la
estructura de una RB desde datos. En ambos casos se utiliza la prueba Chi-cuadrado (ver
prueba Chi-cuadrado en anexo 5) para buscar las variables más significativamente
relacionadas con la variable dependiente (Silva 1997).
Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas
43
En el primer algoritmo se construyen árboles de decisión basados en la técnica CHAID(ver
algoritmo de obtención de árboles de decisión CHAID en el anexo 5); el segundo parte de
esta misma idea, pero se obtienen dependencias entre las variables, no mediante los árboles
de decisión completos, sino que se busca selectivamente a lo ancho y en profundidad en el
árbol de todas las interacciones posibles.
Técnicas estadísticas usadas en el manejo de información en Redes Bayesianas
Por su propia semántica, las RB se basan en la teoría de las probabilidades, lo que las hace
un formalismo fuerte. Ellas procuran buscar una versión simplificada de la DPC (Ver anexo
1 sobre conceptos básicos) de un conjunto de variables supuestamente relacionadas, a
diferencia de otros métodos estadísticos clásicos que se condicionan a priori o posteriori de
una distribución de probabilidad, tal es el caso, por ejemplo, del análisis discriminante y la
regresión.
Los métodos estadísticos tradicionales no resultan del todo adecuados para el análisis y
modelado de datos de sistemas biológicos. Ocurre con frecuencia que una similitud o una
significación estadística no se corresponde necesariamente con una similitud o
significación biológica (entendida la significación como probabilidad de la diferencia). Se
requieren nuevos modelos, así como la integración de diferentes paradigmas para abordar
los problemas actuales.
Se han desarrollado modelos de RB multinomiales y gaussianas (Castillo et al. 1997). En el
trabajo se usan los primeros, propios de variables discretas, lo que exige que si se trata de
un dominio con variables continuas sería imprescindible discretizar estas variables
previamente con la posible pérdida de información. Aunque los problemas de pérdida de
información por discretización son discutibles, particularmente en el área biológica donde
los números aparentemente reales tienen realmente un carácter ordinal. Con independencia
de este problema, las RB con variables discretas son ampliamente utilizadas en la
actualidad, lo cual se ha descrito a grandes rasgos en la presente tesis.
Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas
44
2.1.1
Aprendizaje Estructural de Redes Bayesianas basado en árboles de decisión
obtenidos con el algoritmo CHAID
En este epígrafe se describe el algoritmo ByNet, el cual obtiene árboles de decisión al estilo
CHAID (Ver algoritmo de obtención de árboles de decisión CHAID en el anexo 5).
El usuario es quién decide cuántos árboles obtener. Una vez que se construye el primer
árbol se descarta el conjunto de variables que forman parte de él, lo cual contribuye a la
reducción de variables. Este algoritmo tiene la limitante de que puede obtenerse un modelo
asimétrico.
En una RB un modelo asimétrico significa que un nodo en la red tiene muchos padres. Ello
trae consigo que se necesita cubrir todas las combinaciones de valores entre la variable
asociada al nodo y las variables de los nodos que apuntan a ella. Esto no siempre se logra,
incluso en dominios bioinformáticos caracterizados por grandes volúmenes de datos.
2.1.1.1
Fundamentos generales del Algoritmo
Para obtener la topología de la RB se aplica la técnica CHAID, más que segmentar la
población; en este caso se usa para:
•
•
•
Conocer cuáles, entre decenas de variables pueden ser eliminadas.
Comprender el orden de importancia de los rasgos desde el punto de vista estadístico.
o en las investigaciones epidemiológicas: para comprender el orden de los factores de
riesgo en la caracterización de una enfermedad
o en estudios de secuencias: conocer las posiciones más importantes para el análisis
que se hace
Entender cómo interactúan los rasgos unos con otros
o en las investigaciones epidemiológicas: para entender cómo ciertos factores de
riesgo se relacionan con otros
o
en estudios de secuencias: saber cómo interactúan estas posiciones
El CHAID permite obtener un árbol en forma automática con las características
mencionadas.
Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas
45
Los parámetros que utiliza el algoritmo ByNet para acotar la búsqueda y obtener
determinada estructura de RB se describen a continuación:
•
•
•
•
Cota máxima de la probabilidad del estadístico Chi-cuadrado que será aceptado por el
método como una posible interacción. El dominio de dicha probabilidad es el intervalo
de números reales entre cero y uno. A medida que este valor se aproxima a cero, el
algoritmo es más exigente para declarar una interacción y consecuentemente, se
observará una disminución en la cantidad de interacciones aceptadas por el método y
disminuirá la cantidad de arcos y de nodos en la red. De esta forma, no sólo constituye
un método de aprendizaje automatizado sino que además obtiene una selección de
atributos (ChiSquareMaxSignificance). En caso de que el valor observado sea inferior a
0.05, las variables seleccionadas para formar parte de la red serán estadísticamente
significativas.
Mínima cantidad de casos que debe tener una población para que el método considere
su posible subdivisión. Esta es una cota necesaria para lograr cierto nivel de fiabilidad
ante los test Chi-cuadrado. Debe tratarse de acuerdo al tamaño de la población, la
distribución de la clase y los posibles grados de libertad de las tablas de contingencias
aspirantes (MinCountOfInstancesToSplit).
Cota sobre la máxima cantidad de arcos que pudiese tener el camino más largo dentro
de la topología generada. Su mayor influencia se sienta en la complejidad de la red a
obtener. Tiene amplia repercusión en el espacio de búsqueda cuando las aplicaciones
tienen muchos casos y rasgos (MaxDepth).
Se sugiere que los niveles de profundidad en los árboles sean pequeños, a lo sumo tres.
Esto está relacionado con que las relaciones entre variables a gran distancia en la red no
son fuertes, y tienden a complejizar la estructura de la misma.
Cantidad máxima de árboles de decisión que deben obtenerse, la variable clase depende
de cada uno de los nodos origen de dichos árboles (m_nMaxNrOfTrees). Se sugiere que
el mayor valor por defecto sea a lo sumo 10. Las pruebas que se han realizado han
mostrado que este valor se considera suficientemente grande, sobre todo en el caso que
las variables predictivas puedan tomar varios valores. El algoritmo puede llevar a
Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas
46
estructuras de red con una distribución asimétrica para la variable clase; pues como se
mencionó con anterioridad, a pesar de que las bases de datos tengan muchas instancias,
no siempre se tiene un cubrimiento del dominio para todas las combinaciones que se
presentan entre las variables que son raíz de los distintos árboles y la variable clase.
La estructura de RB se obtiene si se establece un enlace desde los nodos que representan a
las variables más significativas en los árboles creados hasta el nodo asociado a la variable
dependiente o clase, esto significa que se establece un arco dirigido de cada variable más
significativa en cada uno de los árboles hacia la variable clase. El algoritmo no descarta la
participación de los expertos pues posibilita obtener distintos árboles si se cambian
parámetros o se hace interactivamente con el usuario, lo que permite que se tenga en cuenta
la valoración del especialista en el campo de aplicación a la hora de seleccionar la topología
más adecuada.
Pudiera pensarse que la ventaja de experiencia anterior es poco aplicable en problemas de
Bioinformática, donde se pretende casi siempre descubrir conocimiento. Sin embargo, la
valoración del especialista en bioinformática no solo se basa en la experiencia anterior
adquirida en su rama, sino, además, en los resultados obtenidos por otras áreas de las
ciencias biológicas como la paleontología, la filogenia y la genómica comparativa, etc., por
solo citar algunas. Además, se debe tener presente que en ocasiones una significación
estadística no necesariamente coincide con una significación biológica, y se hace necesario
introducir en el modelo, variables con significado biológico, el cual puede ser inferido a
partir del conocimiento establecido en cualquiera de las áreas de investigación antes
mencionadas.
Como es posible obtener más de un árbol usando este método, el número de árboles a
generar se considera un parámetro y para evitar ciclos se eliminan sucesivamente las
variables incluidas (Chávez et al. 1999), (Chávez et al. 2005), (Grau et al. 2006), (Chávez
et al. 2007a), (Grau et al. 2007b).
El aporte del algoritmo ByNet está en la forma en que se construye la RB a partir de árboles
de decisión que se crean mediante la técnica CHAID, estos árboles obtienen las relaciones
Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas
47
fundamentales entre las variables desde el punto de vista estadístico (Chávez et al. 2008a),
(Grau et al. 2007b).
2.1.1.2
Algoritmo ByNet
A continuación se describe el Algoritmo ByNet que implementa la elaboración de la
estructura de la red utilizando los árboles de decisión.
Entrada: Un conjunto de variables {X1, …,XN, C}
Salida: Una estructura de RB G
Paso 1. Inicializar:
•
•
•
•
La red G como un grafo vacío
ListaVariablesSign = []; // Lista que almacena las variables significativas (Chi-
cuadrado)
ListaVariablesPosibles = [X1, X2, …, XN];
m_nMaxNrOfTrees es seleccionado por el usuario (Por defecto se toma valor 10).
Paso 2. Para i =1 hasta N hacer
Prob [i] = ChiCuadrado [Xi ; C]
Sí Prob [i] < 0.05 entonces Adicionar (Xi , ListaVariablesSign)
Paso 3. Ordenar (ListaVariablesSign)
Paso 4. Mientras (ListaVariablesSign ? f) y (m_nMaxNrOfTrees = 0) hacer
raíz = Primero (ListaVariablesSign);
a = TREECHAID (raíz , ListaVariablesPosibles);
m_nMaxNrOfTrees = m_nMaxNrOfTrees-1;
Borrar las variables que forman el árbol almacenado en a de ListaVariablesSign
Borrar las variables que forman el árbol almacenado en a de
ListaVariablesPosibles
Paso 5. Retornar (Red G)
Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas
48
En el Paso 1 de inicialización, G representa la estructura de RB, en ListaVariablesSign se
almacenan las variables predictivas que resultan significativas acorde a la prueba Chi-
cuadrado y ListaVariablesPosibles almacena todas las variables predictivas del problema.
En el Paso 2 se llama a una función, a la que denominamos ChiCuadrado que calcula la
significación estadística mediante la prueba Chi-cuadrado, entre las variables predictivas y
la variable clase.
En el Paso 3 se ordenan ascendentemente las variables predictivas acorde al valor de
probabilidad obtenido en el paso dos.
En el Paso 4 se selecciona la primera variable en la lista. TREECHAID es una función que
obtiene los árboles al estilo de la técnica CHAID (como se describió en el Anexo 5), pero el
nodo raíz se pasa como parámetro a la función, además de la lista de variables posibles. En
el Paso 5 se devuelve la RB en G.
Entre el Paso 3 y el Paso 4, es posible dar la posibilidad de interactuar con especialistas del
dominio de aplicación, de modo que no se tengan en cuenta sólo la dependencia estadística
entre las variables, sino que se puedan introducir en el modelo en otro orden. Esto significa
que se puede forzar el orden de entrada de las variables, teniendo en cuenta la opinión del
experto.
2.1.1.3
Algunas consideraciones sobre el algoritmo ByNet
El algoritmo ByNet parte de la construcción sucesiva de árboles de decisión utilizando la
técnica CHAID. El primer árbol obtenido romperá por la variable más significativa acorde
al test Chi-cuadrado. Las siguientes variables que formen parte de ese árbol estarán en
niveles inferiores, lo que significa que su posición dentro de la red estará más alejada de la
clase. Como que se construye un árbol para cada variable que esté significativamente
asociada a la clase y que no haya estado presente en árboles anteriores, la variable por la
que rompe el último de ellos, puede tener menor importancia que otras ya incorporadas a
otros árboles, y sin embargo, ella tendrá una dependencia directa de la clase.
Esta forma de proceder se realiza para evitar ciclos, pero de hecho trae consigo que el
algoritmo ByNet no siempre ofrezca buenos resultados cuando la correlación entre las
variables predictivas es muy elevada. En ese caso, los primeros árboles de decisión
Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas
49
recogerán la información más importante contenida en los datos, mientras que los últimos
ofrecerán una información mucho menor. La red conformada con la unión de todos los
árboles no hace distinción entre unos y otros.
Por otra parte, originalmente la elección de cuántos árboles de decisión crear, es o bien
puramente estadística, basada en la significación del Chi-cuadrado o se puede hacer que
pertenezca por entero al usuario. Pudiera pensarse en el empleo de alguna heurística que lo
ayudara a tomar una decisión en este sentido, pero ello hace más complejo el proceso de
obtención de la estructura de la red.
Basados en las limitaciones aquí mencionadas, surgió la idea del siguiente algoritmo,
también para el aprendizaje estructural en RB.
2.1.2
Aprendizaje Estructural de Redes Bayesianas basado en el algoritmo CHAID
El algoritmo BayesChaid se basa, como su nombre lo indica, en ideas de la técnica de
CHAID con adaptaciones. Estas consisten esencialmente en hacer la búsqueda de las
dependencias entre las variables no mediante los árboles de decisión completos, sino que
busca a lo ancho y en profundidad en el árbol de interacciones posibles (Chávez et al.
2008b).
2.1.2.1
Fundamentos generales del Algoritmo
Para realizar la búsqueda de la estructura de la red, ésta se acota por un conjunto de
parámetros que impone el usuario y que fueron explicados previamente en el epígrafe 2.1.1,
pues algunos coinciden con los del algoritmo ByNet.
Para comprender la idea del algoritmo BayesChaid, se decidió utilizar en su cuerpo una
función booleana “Terminar” que, dadas dos variables predictivas que se pasan como
parámetros, devuelve “verdadero” en caso de que se cumpla una de las condiciones de
terminación. Ellas son:
•
Mínima cantidad de casos que debe tener una población para que el método considere
su posible subdivisión (MinCountOfInstancesToSplit). Condición que se usa en el
algoritmo ByNet, pues es una cota necesaria para lograr cierto nivel de fiabilidad ante
los test Chi-cuadrado.
Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas
50
•
•
Cota sobre la máxima cantidad de arcos que pudiese tener el camino más largo dentro
de la topología generada (MaxDepth). En el algoritmo ByNet se usa como niveles de
los árboles que se obtienen, y en el algoritmo BayesChaid se utiliza para evitar caminos
largos. Esto influye en la complejidad de los algoritmos de propagación.
En este algoritmo se incluye un nuevo parámetro, MaxNrOfParents, que es la cantidad
de padres que podrán tener los nodos de la red a generar. Esto influye de forma especial
en las tablas de probabilidades condicionadas generadas para la red.
El algoritmo por pasos se describe a continuación.
2.1.2.2
Algoritmo BayesChaid
Entrada: Un conjunto de variables {X1, …,XN, C}
Salida: Una estructura de RB G
Paso 1. Inicializar:
•
•
•
La red G como un grafo vacío
ListaVariablesSign = []; // Lista que almacena las variables significativas (Chi-cuadrado)
ListaVariablesPosibles = [X1, X2, …, XN];
Paso 2. Para i =1 hasta N hacer
Prob [i] = ChiCuadrado [Xi ; C]
Sí Prob [i] < 0.05 entonces A
 Página anterior | Volver al principio del trabajo | Página siguiente  |