Árbol Chow-Liu

Un árbol de dependencia 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 , descrito por primera vez en un artículo de Chow y Liu (1968). Los objetivos de dicha descomposición, al igual que 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 puede representarse como un árbol de dependencia de primer orden, como se muestra en la figura. El algoritmo de Chow-Liu (abajo) determina qué probabilidades condicionales se deben usar en la aproximación del producto. ^[1] 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 esas 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, por lo tanto, sea 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\parallel 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 del orden de dependencia en el árbol, solo la suma de las informaciones mutuas por pares , , determina la calidad de la aproximación. Por lo tanto, si a cada rama (arista) del árbol se le da 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 simplemente el árbol de peso máximo . La ecuación anterior también resalta el papel de las dependencias en la aproximación: cuando no existen dependencias y el primer término en la ecuación está ausente, solo tenemos una aproximación basada en marginales de primer orden, y la distancia entre la aproximación y la distribución verdadera 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 ofrecen un algoritmo simple para construir el árbol óptimo; en cada etapa del procedimiento, el algoritmo simplemente agrega el par de información mutua máxima al árbol. Consulte el artículo original, Chow & Liu (1968), para obtener detalles completos. En Meilă (1999) se describió un algoritmo de construcción de árboles más eficiente para el caso común de datos dispersos.

Chow y Wagner demostraron en un artículo posterior Chow & Wagner (1973) que el aprendizaje del árbol de Chow-Liu es consistente dadas las muestras (u observaciones) extraídas iid de una distribución estructurada en árbol. En otras palabras, la probabilidad de aprender un árbol incorrecto decae a cero a medida que el número de muestras tiende a infinito. La idea principal de la prueba es la continuidad de la información mutua en la distribución marginal por pares. Más recientemente, se proporcionó la tasa exponencial de convergencia de la probabilidad de error. ^[2]

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 resolver en algunos casos fusionando o agregando subconjuntos de variables densamente conectados para obtener un árbol de Chow-Liu de "nodos grandes" (Huang, King y Lyu 2002), o extendiendo la idea de la selección voraz de peso máximo de rama a estructuras que no son árboles (múltiples padres) (Williamson 2000). (Técnicas similares de sustitución y construcción de variables son comunes en la literatura de redes de Bayes , por ejemplo, para tratar con bucles. Véase Pearl (1988).)

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

Véase también

• Red bayesiana
• Representación del conocimiento

Notas

1. Permuter, Haim. "Conferencia sobre distribución de árboles" (PDF) . Archivado desde el original (PDF) el 2021-08-27 . Consultado el 2021-08-27 .
2. Un análisis de gran desviación para el aprendizaje de máxima verosimilitud de estructuras arbóreas. VYF Tan, A. Anandkumar, L. Tong y A. Willsky. En el simposio internacional sobre teoría de la información (ISIT), julio de 2009.

Referencias

• Chow, CK; Liu, CN (1968), "Aproximación de distribuciones de probabilidad discretas con árboles de dependencia", IEEE Transactions on Information Theory , IT-14 (3): 462–467, CiteSeerX  10.1.1.133.9772 , doi :10.1109/tit.1968.1054142.
• Huang, Kaizhu; King, Irwin; Lyu, Michael R. (2002), "Construcción de un árbol Chow-Liu de nodos grandes basado en conjuntos de elementos frecuentes", en Wang, Lipo; Rajapakse, Jagath C.; Fukushima, Kunihiko; Lee, Soo-Young; Yao, Xin (eds.), Actas de la 9.ª Conferencia internacional sobre procesamiento de información neuronal ({ICONIP}'02) , Singapur , págs. 498–502{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).
• Pearl, Judea (1988), Razonamiento probabilístico en sistemas inteligentes: redes de inferencia plausible , San Mateo, CA : Morgan Kaufmann
• Williamson, Jon (2000), "Aproximación de distribuciones de probabilidad discretas con redes bayesianas", Actas de la Conferencia Internacional sobre Inteligencia Artificial en Ciencia y Tecnología , Tasmania , págs. 16-20{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).
• Meilă, Marina (1999), "Un algoritmo acelerado de Chow y Liu: ajuste de distribuciones de árboles a datos dispersos de alta dimensión", Actas de la decimosexta conferencia internacional sobre aprendizaje automático , Morgan Kaufmann, págs. 249-257.
• Chow, CK; Wagner, T. (1973), "Consistencia de una estimación de la distribución de probabilidad dependiente del árbol", IEEE Transactions on Information Theory , IT-19 (3): 369–371, doi :10.1109/tit.1973.1055013.
• Kovács, E.; Szántai, T. (2010), "Sobre la aproximación de una distribución de probabilidad multivariante discreta utilizando el nuevo concepto de árbol de uniones t-Cherry", Coping with Uncertainty , Lecture Notes in Economics and Mathematical Systems, vol. 633, Parte 1, págs. 39–56, doi :10.1007/978-3-642-03735-1_3, ISBN 978-3-642-03734-4.
• Szántai, T.; Kovács, E. (2010), "Hipergrafos como medio para descubrir la estructura de dependencia de una distribución de probabilidad multivariada discreta", Anales de investigación de operaciones.