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