Árbol por etapas (matemáticas)

Un árbol por etapas es un modelo probabilístico para un proceso que consiste en una secuencia de eventos de valor discreto descritos por un diagrama de árbol (también conocido como árbol de eventos o árbol de probabilidad). Un árbol por etapas establece relaciones de igualdad en las distribuciones de probabilidad condicional de un árbol de eventos. Estas relaciones de igualdad se representan visualmente mediante el color de los vértices para formar un modelo gráfico . Un árbol por etapas también tiene una representación visual más compacta llamada grafo de eventos en cadena . ^{[ 1 ] [ 2 ]}

Los árboles de etapas y los gráficos de eventos en cadena se desarrollaron originalmente como una herramienta para la obtención de información de expertos . Las personas suelen comprender las cosas a través de historias, y los expertos suelen explicar su dominio mediante secuencias de eventos y sus efectos en cadena. ^{[ 3 ]} El árbol de etapas y el gráfico de eventos en cadena proporcionan una representación visual de dichas secuencias de eventos y la relacionan con una clase de distribuciones de probabilidad para crear un modelo probabilístico formal. Cuando hay datos suficientes, los árboles de etapas pueden utilizarse como una herramienta de aprendizaje automático para encontrar la historia que mejor describe los datos. De esta forma, se pueden descubrir nuevas explicaciones para la evolución del proceso. También se han utilizado para el análisis causal , ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ]} se han extendido a modelos dinámicos que evolucionan con el tiempo ^{[ 8 ]} y para modelar datos faltantes informados . ^{[ 9 ]}

La construcción de un árbol de eventos comienza con el dibujo del árbol de eventos que describe todas las posibles evoluciones del proceso. Un árbol de eventos es una arborescencia : un grafo de árbol enraizado dirigido con todas las aristas apuntando hacia afuera del vértice raíz. La raíz representa el inicio del proceso, mientras que las hojas del árbol representan todos los posibles puntos finales del proceso. Todos los vértices que no son hojas, incluida la raíz, se denominan situaciones y representan puntos intermedios en la evolución del proceso. Las aristas del árbol están etiquetadas con un identificador del evento al que corresponden. ^{[ 10 ]}

Cada situación y sus aristas salientes se asocian a una distribución de probabilidad, denominada probabilidad de transición , que describe las probabilidades del siguiente evento dado que el proceso alcanza dicha situación. Las probabilidades de transición son suficientes para determinar de forma unívoca la distribución de probabilidad completa del proceso. ^{[ 10 ]}

Un árbol de eventos se denomina compatible con x si puede relacionarse con una secuencia de variables aleatorias discretas (una por cada capa del árbol) y todas las combinaciones posibles de estas variables tienen una probabilidad distinta de cero. Los árboles no compatibles con x, en cambio, permiten ceros estructurales —cuando ciertas combinaciones de las variables ocurren con probabilidad cero— o que los posibles valores de eventos futuros dependan de eventos pasados. ^{[ 11 ]}

Ejemplo

Consideremos un escenario simplificado para un ensayo clínico aleatorizado de un nuevo tratamiento médico. A los pacientes se les diagnostican síntomas leves o graves y se les asigna aleatoriamente el nuevo tratamiento o el tratamiento estándar. Se determina si los efectos del tratamiento fueron positivos o negativos. Este proceso se puede representar mediante el árbol de eventos compatible con x que se muestra a la derecha.

Un árbol por etapas es un modelo probabilístico que restringe el espacio de distribuciones de probabilidad en un árbol de eventos al especificar relaciones de igualdad entre las probabilidades de transición de diferentes situaciones. Específicamente, si dos situaciones se encuentran en la misma etapa , comparten una distribución de probabilidad de transición común. ^{[ 1 ]} En otras palabras, las situaciones se agrupan en etapas según sus probabilidades de transición.

En términos generales, dos situaciones cualesquiera con el mismo número de aristas salientes pueden estar en la misma etapa. Sin embargo, la definición de etapa suele estar restringida, de modo que solo las situaciones con las mismas etiquetas de aristas salientes pueden estar en la misma etapa, y la relación de igualdad de las probabilidades de transición coincide con las etiquetas de las aristas. Un árbol por etapas se denomina estratificado si solo las situaciones en la misma capa del árbol pueden estar en la misma etapa. ^{[ 11 ]}

El conjunto de todas las etapas en un árbol de etapas se describe mediante una partición de las situaciones del árbol denominada etapa . Un modelo de árbol de etapas se define completamente mediante el árbol de eventos y la etapa, y se representa gráficamente coloreando los vértices del árbol de eventos según su pertenencia a una etapa. Es decir, a todas las etapas se les asigna un color y a todas las situaciones dentro de una etapa se les asigna este color en el árbol. Generalmente, las etapas únicas (etapas con una sola situación) permanecen sin color. ^{[ 10 ]}

Ejemplo

Volviendo al ejemplo anterior, supongamos que asumimos que:

1. El ensayo se diseñó de forma aleatoria correcta, de modo que la probabilidad de que un paciente reciba el nuevo tratamiento no depende de sus síntomas.
2. El nuevo tratamiento y el tratamiento estándar tienen la misma eficacia para quienes presentan síntomas leves.

Estas dos suposiciones están representadas en el árbol por etapas que se muestra a la derecha. La suposición 1 se refleja en situaciones${\displaystyle s_{1}}$y${\displaystyle s_{2}}$ambos están coloreados en rojo, mientras que la suposición 2 se refleja en situaciones${\displaystyle s_{3}}$y${\displaystyle s_{4}}$ambos coloreados de verde. Situaciones${\displaystyle s_{5}}$y${\displaystyle s_{6}}$Ambos no tienen color, lo que refleja que no se hacen suposiciones sobre sus distribuciones de probabilidad.

Un grafo de eventos en cadena es una representación visual más compacta de un modelo de árbol por etapas. Dos situaciones se encuentran en la misma posición si están en la misma etapa y el desarrollo futuro del proceso es probabilísticamente idéntico desde ambas situaciones. En otras palabras, los subárboles que comienzan en las dos situaciones son idénticos tanto en términos de topología como de pertenencia/coloración de etapas. Un grafo de eventos en cadena se construye fusionando todos los vértices que se encuentran en la misma posición, así como fusionando todos los vértices hoja en un único vértice sumidero . ^{[ 1 ] [ 10 ]}

Ejemplo

Volviendo al ejemplo anterior, situaciones${\displaystyle s_{3}}$y${\displaystyle s_{4}}$están en la misma posición y, por lo tanto, pueden fusionarse en el gráfico de eventos en cadena. Situaciones${\displaystyle s_{1}}$y${\displaystyle s_{2}}$Se encuentran en la misma etapa, pero no en la misma posición porque los subárboles que parten de estos vértices tienen colores diferentes. Por lo tanto, no se fusionan en el grafo de eventos en cadena. El grafo de eventos en cadena resultante se muestra a la derecha.

Al estimar las probabilidades de transición en un árbol de eventos, solo se pueden usar las muestras que alcanzan la situación relevante. Sin embargo, los árboles por etapas pueden tener una ligera ventaja, ya que las muestras se pueden compartir entre cualquier situación en la misma etapa, puesto que todas se usan para estimar la misma distribución de probabilidad. Siempre que la suposición de etapas sea cierta, esto resulta en tamaños de muestra mayores y, por lo tanto, en una mejor estimación de las probabilidades de transición. ^{[ 12 ]}

Cuando no se conoce a priori un árbol por etapas, se puede aprender a partir de los datos. Es decir, se selecciona un modelo de árbol por etapas que mejor represente los datos. De esta manera, se pueden descubrir igualdades en las probabilidades de transición. ^{[ 13 ]}

La selección de modelos se realiza comúnmente combinando una función de puntuación con un algoritmo de búsqueda de modelos . El algoritmo de búsqueda de modelos busca en el conjunto de modelos posibles el que tenga la puntuación más alta. Las opciones estándar para la función de puntuación son la probabilidad posterior del modelo ^{[ 14 ]} y el criterio de información bayesiano , mientras que las opciones para el algoritmo de búsqueda de modelos incluyen el agrupamiento jerárquico aglomerativo ^{[ 14 ]} y el ascenso de colinas .

A menudo, en la selección de modelos de árboles por etapas, se asume que el árbol de eventos subyacente es fijo en función de información específica del dominio (como un ordenamiento temporal o causal de las variables). Una extensión se da cuando el árbol de eventos no es fijo y se incluye en la selección del modelo. Muchos árboles de eventos diferentes pueden describir el mismo conjunto de datos (por ejemplo, cambiando el orden de las variables en árboles compatibles con x), pero cada uno induce diferentes probabilidades de transición y, por lo tanto, diferentes clases de modelos de árboles por etapas. ^{[ 15 ]} Para explorar el espacio de posibles árboles de eventos, se dispone de un enfoque de programación dinámica. ^{[ 16 ]}

Las redes bayesianas son una clase de modelos gráficos capaces de codificar relaciones de independencia condicional entre grupos de vértices. De manera similar, las etapas de un árbol estratificado pueden usarse para codificar independencias condicionales. ^{[ 17 ]} De hecho, los árboles estratificados compatibles con x pueden considerarse una extensión de las redes bayesianas discretas: toda red bayesiana discreta puede representarse mediante un árbol estratificado compatible con x. ^{[ 1 ]} Sin embargo, los árboles estratificados también pueden especificar independencias condicionales específicas del contexto que no pueden representarse mediante una red bayesiana estándar. De esta forma, la clase de modelos de árboles estratificados es más amplia que la de la red bayesiana estándar. Además, los árboles estratificados no compatibles con x pueden usarse para procesos que no pueden modelarse mediante redes bayesianas estándar.

El software para la selección de modelos y la estimación de probabilidades mediante árboles escalonados está disponible en R con el paquete stagedtrees ^{[ 11 ]} y en Python con el paquete cegpy. ^{[ 18 ]}

Los árboles estratificados se han aplicado con éxito en varias áreas, incluyendo medicina y epidemiología, ^{[ 19 ] [ 20 ] [ 21 ]} investigaciones criminales, ^{[ 22 ] [ 23 ]} rutas migratorias, ^{[ 24 ]} transporte, ^{[ 25 ]} y derecho. ^{[ 26 ] [ 27 ] [ 28 ]}

Una limitación principal de los modelos de árbol por etapas es el tipo de datos con los que se pueden utilizar. Específicamente, los datos deben poder representarse mediante un árbol de eventos, lo cual solo es posible para espacios de muestra finitos. Cuando los datos no tienen un espacio de muestra finito , por ejemplo, si contienen una variable continua, no pueden representarse mediante un árbol de eventos y, por lo tanto, los modelos de árbol por etapas no se pueden aplicar directamente. Una solución sencilla a esto es discretizar cualquier variable con un espacio de muestra infinito. ^{[ 2 ]}

Otra limitación similar de los modelos de árbol por etapas se da cuando el tamaño del espacio de muestra finito es grande. Esto podría ocurrir porque el árbol contiene muchas capas (largas secuencias de eventos) o cuando las situaciones tienen muchas aristas salientes (muchos eventos posibles). Por ejemplo, un árbol de eventos de${\displaystyle N}$Las variables binarias tienen${\displaystyle 2^{N}}$Rutas de raíz a hoja. La representación visual de un árbol por etapas se vuelve más difícil de comprender a medida que aumenta su tamaño y, por lo tanto, una de las principales ventajas de los árboles por etapas —la interpretación y visualización sencillas— puede perderse. Los grafos de eventos en cadena mejoran esto al proporcionar una representación visual más compacta, pero aun así, eventualmente sufren el mismo problema a medida que aumenta el tamaño del árbol. ^{[ 2 ]}

Este problema es más pronunciado en la selección de modelos. Para un árbol de eventos de${\displaystyle N}$variables binarias, el número de posibles modelos de árbol estratificados por etapas es${\textstyle \prod _{i=1}^{N}B(2^{N-1})}$^{[ 16 ]} donde${\displaystyle B(m)}$es el${\displaystyle m}$Número de Bell . Esto significa que una búsqueda exhaustiva de modelos es inviable incluso para árboles de tamaño moderado, lo que requiere el uso de algoritmos de búsqueda de modelos. ^{[ 29 ]} Además, los métodos de selección de modelos pueden ser inestables cuando el tamaño de la muestra es pequeño en relación con el tamaño del árbol.