jueves, 20 de noviembre de 2008

Inferencia usando un heap con distribución de probabilidad conjunta

En el campo de Inteligencia Artificial, los modelos probabilísticos han sido adoptados como una opción a las redes neuronales. Modelos probabilísticos como las redes bayesianas, han sido adaptadas a un sin número de aplicaciones: diagnóstico médico, modos de búsquedas 'inteligentes' en motores de búsqueda conocidos, reconocimiento de patrones en imágenes, entre otras. La red bayesiana es un grafo dirigido, cuyos nodos representan las variables que se requieren para modelar el entorno, sin embargo, el modo de inferencia es inmensamente variado, existen inferencias completas y aproximadas. La inferencias completas, incluyen en el cálculo de una consulta, todos los nodos, la distribución conjunta completa. Las inferencias aproximadas, buscan los nodos que pertenecen a la línea de ascendientes o descendientes (según sea el caso), del nodo involucrado en la consulta.

El modo de consulta más común, el cual se pretende manejar aquí, es P(e|X), donde se desea saber la probabilidad de que ocurra la variable 'e' (que es el nodo padre o ascendiente del conjunto de nodos X), dado que han aparecido (o desaparecido) un conjunto 'X' de variables ligadas (como síntomas de una enfermedad o palabras que un usuario final ha colocado en un motor de búsqueda).
Aquí un modo de inferencia con distribución conjunta completa usando un método que hice junto con mis compañeros Jorge Valverde R. y Juan Grados V., basándonos en el comportamiento de la red cuando hay una instanciación, utilizando una estructura de datos Heap. El mecanismo de inferencia es parecido al método de Enumeración.

Tabla de probabilidades conjunta

Esquema que representa la distribución de probabilidades


Para implementar la estructura, lo hacemos a través de una cola de prioridad. Donde cada nodo tiene dos hijos, y cumple con la siguiente norma:

Si un nodo está en la posición “i”, entonces sus hijos están en la posición: 2*i y (2*i+1).


Relación entre la matriz y la estructura árbol

Como puede observarse, todo el contenido de la matriz se encuentra en las hojas. Además mientras va subiendo de nivel, a partir de las hojas, los valores obtenidos en los nodos internos son las sumas de sus descendientes.

Por ejemplo, queremos hallar la probabilidad de caries con dolor.


Luego, si queremos hallar la probabilidad de dolor, el esquema sería:

Para cada profundidad del árbol, existe una variable diferente. Y el número de veces que se repite una variable en su ply es: el cual llamaremos: grado de repetición, a la cual llamaremos simplemente grado.


Algoritmo P(a^b)


1. Determinar la variable de mayor grado “m” entre “a” y “b”.

2. La variable de menor grado “n” entre “a” y “b”.

3. x ß hallar la probabilidad de todos los subárboles “m”

4. y ß hallar la probabilidad dentro de los subárboles “-m”, de las variables “n”

5. retornar x+y



Algoritmo P(a|b)


1. Determinar la variable de mayor grado “m” entre “a” y “b”

2. Si “a” es “m”, entonces

3. n ß b

4. Sino

5. n ß a

6. Fin-si

7. suma ß 0

8. prob ß hallar probabilidad de subárbol “n”

8. Para cada subárbol “m” hacer

9. suma ß suma + hallar probabilidad de subárbol “n”

10. Fin-para

11. retornar suma/prob

1 comentario:

Jorge Valverde-Rebaza dijo...

El uso del heap para realizar la inferencia es muy bueno (Y) y permite un acceso más rápido a la información que se requiera...bien ahi Peter (Y)