Árbol de Chow – Liu - Chow–Liu tree

Un árbol de dependencias de primer orden que representa el producto de la izquierda.

En teoría de probabilidad y estadística , el árbol de Chow-Liu es un método eficiente para construir una aproximación de producto de segundo orden de una distribución de probabilidad conjunta , descrita por primera vez en un artículo de Chow y Liu (1968) . Los objetivos de dicha descomposición, como ocurre con las redes bayesianas en general, pueden ser la compresión de datos o la inferencia .

La representación de Chow – Liu

El método de Chow-Liu describe una distribución de probabilidad conjunta como un producto de distribuciones condicionales y marginales de segundo orden. Por ejemplo, la distribución de seis dimensiones podría aproximarse como ${\ Displaystyle P (X_ {1}, X_ {2}, \ ldots, X_ {n})}$${\ Displaystyle P (X_ {1}, X_ {2}, X_ {3}, X_ {4}, X_ {5}, X_ {6})}$

${\ Displaystyle P ^ {\ prime} (X_ {1}, X_ {2}, X_ {3}, X_ {4}, X_ {5}, X_ {6}) = P (X_ {6} | X_ { 5}) P (X_ {5} | X_ {2}) P (X_ {4} | X_ {2}) P (X_ {3} | X_ {2}) P (X_ {2} | X_ {1} ) P (X_ {1})}$

donde cada nuevo término en el producto introduce solo una nueva variable, y el producto se puede representar como un árbol de dependencia de primer orden, como se muestra en la figura. El algoritmo de Chow-Liu (a continuación) determina qué probabilidades condicionales se utilizarán en la aproximación del producto. En general, a menos que no haya interacciones de tercer orden o de orden superior, la aproximación de Chow-Liu es de hecho una aproximación y no puede capturar la estructura completa de la distribución original. Pearl (1988) proporciona un análisis moderno del árbol de Chow-Liu como una red bayesiana .

El algoritmo de Chow-Liu

Chow y Liu muestran cómo seleccionar términos de segundo orden para la aproximación del producto de modo que, entre todas estas aproximaciones de segundo orden (árboles de dependencia de primer orden), la aproximación construida tenga la divergencia mínima de Kullback-Leibler con respecto a la distribución real , y sea por tanto, la aproximación más cercana en el sentido clásico de la teoría de la información . Se muestra que la divergencia de Kullback-Leibler entre una aproximación de producto de segundo orden y la distribución real es ${\ Displaystyle P ^ {\ prime}}$${\ Displaystyle P}$

${\ Displaystyle D (P \ paralelo P ^ {\ prime}) = - \ sum I (X_ {i}; X_ {j (i)}) + \ sum H (X_ {i}) - H (X_ {1 }, X_ {2}, \ ldots, X_ {n})}$

donde es la información mutua entre la variable y su padre y es la entropía conjunta del conjunto de variables . Dado que los términos y son independientes de la dependencia de pedidos en el árbol, sólo la suma de los pares informaciones mutuas , , determina la calidad de la aproximación. Por lo tanto, si a cada rama (borde) del árbol se le asigna un peso correspondiente a la información mutua entre las variables en sus vértices, entonces el árbol que proporciona la aproximación óptima de segundo orden a la distribución objetivo es solo el árbol de peso máximo . La ecuación anterior también destaca el papel de las dependencias en la aproximación: cuando no existen dependencias y el primer término de la ecuación está ausente, solo tenemos una aproximación basada en los marginales de primer orden y la distancia entre la aproximación y el verdadero La distribución se debe a las redundancias que no se tienen en cuenta cuando las variables se tratan como independientes. A medida que especificamos dependencias de segundo orden, comenzamos a capturar algo de esa estructura y reducimos la distancia entre las dos distribuciones. ${\ Displaystyle I (X_ {i}; X_ {j (i)})}$${\ Displaystyle X_ {i}}$${\ Displaystyle X_ {j (i)}}$${\ Displaystyle H (X_ {1}, X_ {2}, \ ldots, X_ {n})}$${\ Displaystyle \ {X_ {1}, X_ {2}, \ ldots, X_ {n} \}}$${\ Displaystyle \ sum H (X_ {i})}$${\ Displaystyle H (X_ {1}, X_ {2}, \ ldots, X_ {n})}$${\ Displaystyle \ sum I (X_ {i}; X_ {j (i)})}$

Chow y Liu proporcionan un algoritmo simple para construir el árbol óptimo; en cada etapa del procedimiento, el algoritmo simplemente agrega el par máximo de información mutua al árbol. Consulte el artículo original, Chow & Liu (1968) , para obtener todos los detalles. Meilă (1999) describe un algoritmo de construcción de árboles más eficiente para el caso común de datos escasos .

Chow y Wagner demostraron en un artículo posterior Chow y Wagner (1973) que el aprendizaje del árbol Chow-Liu es consistente dadas muestras (u observaciones) extraídas de una distribución estructurada en árbol. En otras palabras, la probabilidad de aprender un árbol incorrecto se reduce a cero cuando el número de muestras tiende a infinito. La idea principal en la demostración es la continuidad de la información mutua en la distribución marginal por pares. Recientemente, se proporcionó la tasa exponencial de convergencia de la probabilidad de error.

Variaciones de los árboles Chow-Liu

El problema obvio que ocurre cuando la distribución real no es, de hecho, un árbol de dependencia de segundo orden, todavía se puede abordar en algunos casos fusionando o agregando subconjuntos de variables densamente conectados para obtener un árbol de Chow-Liu de "nodo grande" ( Huang & King 2002 ) , o extendiendo la idea de una selección codiciosa del peso máximo de la rama a estructuras que no son árboles (padres múltiples) ( Williamson 2000 ). (Técnicas similares de sustitución y construcción de variables son comunes en la literatura de la red de Bayes , por ejemplo, para tratar con bucles. Véase Pearl (1988)) . error de harv: sin destino: CITEREFHuangKing2002 ( ayuda )

Las generalizaciones del árbol de Chow-Liu son los llamados árboles de unión de cereza t . Está demostrado que los árboles de unión de la cereza t proporcionan una mejor o al menos tan buena aproximación para una distribución de probabilidad multivariante discreta como la que da el árbol de Chow-Liu. Para el árbol de unión t-cherry de tercer orden, ver ( Kovács & Szántai 2010 ), para el árbol de unión t-cherry de k -ésimo orden, ver ( Szántai & Kovács 2010 ). El árbol de unión de la cereza t de segundo orden es, de hecho, el árbol Chow-Liu.

Ver también

• Red bayesiana
• Representación del conocimiento

Notas

Referencias