Escalabilidad en los Algoritmos de Aprendizaje de Redes Bayesianas

ISL – Dpto de Informática –UCLM - Albacete

2

Motivación

La mayoría de los algoritmos de aprendizaje no pueden tratar con conjuntos grandes de datos y/o con un gran número de variables en el dominio

Las bases de datos actuales permiten almacenar del orden de TeraBytes.

Como el costo es “bajo” se suele almacenar un gran número de variables

Incluso preseleccionando variables, existen problemas con un gran número de ellas

Llegan los “data streams”

3

Introducción

En cuanto a las bases de datos:– Estáticas– Dinámicas

En cuanto al modelo:– Modelo estático: el modelo se genera

introduciendo conocimiento– Modelo dinámico: el modelo se modifica en

función de la “tendencia” de los datos

4

Introducción

¿por qué diseñar nuevas técnicas?– A mayor tamaño, mayor precisión– Con tamaño pequeño overfitting– Con muchas variables Espacio poco poblado

¿cuándo una base de datos es muy grande?– Desde el punto de vista de la “Minería de datos” significa a

partir de 100Mb / 1Gb, dependiendo de número de variables

Def: Un algoritmo es escalable cuando es capaz de aprender un modelo a partir de bases de datos de cualquier tamaño (al menos tan rápido como su equivalente no escalable y con la misma eficacia)

5

Algoritmos de aprendizaje de RB Escalabilidad: Trabajos previos

Utilización de algoritmos con técnicas de “divide y vencerás”– N. Friedman et al. Learning of Bayesian Network Structure from

Massive Datasets: The "Sparse Candidate" Algorithm (1999).– R. Castelo and A. Siebes. Scaling Bayesian network discovery

through incremental recovery. Technical Report INS-R9901, CWI, Amsterdam, (1999).

Utilización de técnicas de sub-muestreo– G. Hulten and P. Domingos. Mining complex models from

arbitrarily large databases in constant time. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. (2002).

– N. Friedman and Z. Yakhini. On the complexity of learning Bayesian networks. UAI (1996).

Híbrido– G. Hulten, D. Chickering and D. Heckerman. Learning Bayesian

networks from dependence networks: A preliminary study. W. On AI & Statistics (2003)

6

Objetivo

Diseñar algoritmos escalables para el aprendizaje de Redes Bayesianas:– Diseñar algoritmos escalables en anchura: Muchas

variables, tamaño de los casos fijo– Diseñar algoritmos escalables en profundidad:

Número de variables “manejable”, tamaño de los casos incluso infinito

– Diseñar algoritmos escalables en anchura / profundidad: Combinación de los dos anteriores

7

Algoritmo ELBN en anchura

Tanto el trabajo de Friedman et al. Y el de Castelo et al. Necesitan un orden de cálculos de estadísticos de orden 2

Igualmente los dos trabajos se basan en métodos de búsqueda local (HC)

Friedman et al. Utiliza medidas “estándares” en el aprendizaje. Castelo et al. Utilizan una media de correlación para realizar la división

)( 2nO

8

Algoritmo ELBN en anchura

El método desarrollado está muy relacionado con el de Castelo et al.

La idea de ambos es realizar agrupamiento de variables “lo más independientes” posible unos de otros y “lo más dependientes” posibles dentro de cada grupo, para dividir el espacio de búsqueda.

Ambos utilizan técnicas de Clustering Una vez realizado el agrupamiento búsquedas

independientes en cada grupo Una vez que tenemos una RB por cada grupo, se

realiza una composición de los resultados

9

Algoritmo ELBN en anchura

Diferencias: – Castelo et al. Utilizan una técnica de clustering

jerárquico no hace especificar el nº de grupos– Nosotros utilizamos un algoritmo basado en PAM

(centroides) necesita “a priori” especificar un nº de grupos

– Castelo et al. Utiliza una medida de correlación, nosotros utilizamos medidas “estándares” en LBN

En principio ambos utilizan la misma técnica de composición de resultados

10

Algoritmo ELBN en anchura

11

Algoritmo de agrupamiento

En principio se fija un número de grupos k Se eligen k variables aleatorias como centroides Para el resto de variables se mira el grupo donde “cae

más cerca”, con la medida

Una vez formados los k grupos, entonces se reeligen los nuevos centroides de cada grupo

Como nuevo centroide se elige aquel de su grupo que esté más cercano al resto de variables del grupo y se reitera el proceso un nº de iteraciones

)(}){)(|(),( ijiiji cfxcPacfxcd

12

Inicialización

Podemos fijar un nº k de grupos o podemos plantearnos que un algoritmo previo nos lo fije

Podemos diseñar un algoritmo que además de fijar un nº de grupos nos de una inicialización de estos grupos

Algoritmo de inicialización:– Elegimos un nodo al azar como centroide del primer grupo.– Para el resto de variables hasta que todas este procesadas:

Si d(c_i,x_j) > 0, para algún c_i, entonces x_j entra en el grupo de c_i de mayor medida (mayor d(c_i,x_j)

Si d(c_i,x_j) < 0, para todo c_i, entonces se fija x_j como nuevo centroide para otro grupo.

Una vez inicializado los grupos procedemos igual que antes

13

Ejemplo: ALARM k=2

N: 620 i: 10

14

Ejemplo: ALARM k sin fijar

N: 500 i: 12

15

Conclusiones

Es fundamental considerar tamaños muy grandes de bases de datos

Los algoritmos de aprendizaje de RB deterioran rápidamente con este tipo de bases de datos

Por consiguiente, es necesario diseñar algoritmos que trabajen de forma adecuada con este tipo de bases de datos

Hemos utilizado una técnica de “divide y vencerás para diseñar un algoritmo de aprendizaje de RB cuando tenemos un número muy elevado de variables en el dominio

16

Trabajos futuros

Realizar un método de composición más eficiente más que considerar un búsqueda completa

Diseñar métodos de aprendizaje cuando tenemos “data stream”:– Suponer misma distribución subyacente en los

datos– Suponer que puede cambiar esta distribución

subyacente Aprendizaje secuencial