Clojure DAG (red bayesiana)

Question

Me gustaría construir una red bayesiana en clojure, ya que no he encontrado ningún proyecto similar.

He estudiado mucha teoría de la BN, pero aún no veo cómo implementar la red (no soy lo que la gente llama "gurú" para nada, pero especialmente no para la programación funcional).

Sé que un BN no es más que un DAG y una tabla de muchas probabilidades (una para cada nodo) pero ahora no tengo pegamento para implementar el DAG.

Mi primera idea era un gran conjunto (el DAG) con algunos mapas pequeños (el nodo del DAG), cada mapa debe tener un nombre (probablemente una clave) una tabla de probabilidades (¿otro mapa?) Un vector de padres y finalmente un vector de no -descendiente.

Ahora no sé cómo implementar la referencia de los padres y los no descendientes (lo que debería poner en los dos vectores). Supongo que un puntero debería ser perfecto, pero la ausencia de él; Podría poner en el vector el: nombre del otro nodo, pero va a ser lento, ¿no?

Estaba pensando que en lugar de un vector podría usar más conjunto, de esta manera sería más rápido encontrar los descendientes de un nodo.

Problema similar para la tabla de probabilidades donde todavía necesito alguna referencia en los otros nodos.

Finalmente también me gustaría aprender el BN (construir la red comenzando por los datos) esto significa que voy a cambiar mucho ambas tablas de probabilidad, borde y nodos.

¿Debo usar tipos mutables o solo aumentarían la complejidad?

Answer 1

Puede intentar ir aún más plano y tener varios mapas indexados por identificadores de nodo: un mapa para tablas de probabilidades, uno para padres y otro para no descendientes (no soy experto en BN: ¿qué es esto? ¿Cómo se usa? etc. Se siente como algo que podría ser recalculado desde la tabla de padres^W relation^W map).

Answer 2

Esto no es una respuesta completa, pero aquí hay una posible codificación para la red de ejemplo del wikipedia article. Cada nodo tiene un nombre, una lista de sucesores (niños) y una tabla de probabilidad:

(defn node [name children fn] 
    {:name name :children children :table fn}) 

nuevo, aquí hay pequeñas funciones de ayuda para la construcción de probabilidades de verdadero/falso:

;; builds a true/false probability map 
(defn tf [true-prob] #(if % true-prob (- 1.0 true-prob))) 

Los anteriores devuelve las un cierre, que, cuando se le da un valor de true (respectivamente false valor), devuelve la probabilidad del evento X=true (para la variable de probabilidad X que estamos codificando).

Dado que la red es un DAG, podemos hacer referencia directamente a nodos entre sí (exactamente como los punteros que mencionó) sin tener que preocuparse por las referencias circulares. Acabamos de construir la gráfica de la orden topológico:

(let [gw (node "grass wet" [] (fn [& {:keys [sprinkler rain]}] 
          (tf (cond (and sprinkler rain) 0.99 
             sprinkler 0.9 
             rain 0.8 
             :else 0.0)))) 

    sk (node "sprinkler" [gw] 
      (fn [& {:keys [rain]}] (tf (if rain 0.01 0.4)))) 

    rn (node "rain" [sk gw] 
      (constantly (tf 0.2)))] 

    (def dag {:nodes {:grass-wet gw :sprinkler sk :rain rn} 
     :joint (fn [g s r] 
       (* 
        (((:table gw) :sprinkler s :rain r) g) 
        (((:table sk) :rain r) s) 
        (((:table rn)) r)))})) 

La tabla de probabilidad de cada nodo se da en función de los estados de los nodos padre y devuelve la probabilidad de true y false valores.Por ejemplo,

((:table (:grass-wet dag)) :sprinkler true :rain false) 

... devuelve {:true 0.9, :false 0.09999999999999998}.

La función de la articulación resultante combina probabilidades según la siguiente fórmula:

P(G,S,R) = P(G|S,R).P(S|R).P(R) 

Y ((:joint dag) true true true) rendimientos 0.0019800000000000004. De hecho, cada valor devuelto por ((:table <x>) <args>) es un cierre alrededor de if, que devuelve probabilidad conociendo el estado de la variable de probabilidad. Llamamos a cada cierre con el valor respectivo true/false para extraer la probabilidad apropiada y multiplicarlas.

Aquí, estoy engañando un poco porque supongo que la función conjunta debe calcularse atravesando el gráfico (una macro podría ayudar, en el caso general). Esto también se siente un poco desordenado, especialmente con respecto a los estados de los nodos, que no son necesariamente solo verdaderos y falsos: lo más probable es que utilice un mapa en el caso general.

Answer 3

En general, la forma de calcular la distribución conjunta de un BN es

prod(P(node | parents of node)) 

Para achive esto, necesita una lista de nodos, donde cada nodo contiene

• nombre de nodo
• lista de padres
• tabla de probabilidad
• lista de niños

tabla de probabilidad tal vez es más fácil de manejar cuando está plano con cada valor de fila correspondiente a una configuración primaria y cada columna corresponde a un valor para el nodo. Esto supone que estás usando un registro para mantener todos los valores. El valor del nodo también puede estar contenido dentro del nodo.

Los nodos sin padres tienen solo una fila.

Cada fila debe normalizarse después de lo cual P (nodo | padres) = tabla [fila, columna]

Usted realmente no necesita la lista de los niños, sino que tiene que podría hacer más fácil la clasificación topológica. Un DAG debe poder clasificarse topológicamente.

El mayor problema surge porque la cantidad de celdas en la tabla de probabilidades es el producto de todas las dimensiones de los padres y de uno mismo. Manejé esto en C++ usando una tabla dispersa utilizando mapeo de filas.

Consultar el DAG es una cuestión diferente y el mejor método para hacerlo depende del tamaño y si la respuesta aproximada es suficiente. No hay espacio suficiente para cubrirlos aquí. Buscar Murphy y Bayes Net Toolbox podría ser útil

Me doy cuenta de que está buscando específicamente una implementación pero, con un poco de trabajo, puede hacer la suya.