Medición de la entropía de un grafo que representa una matriz de probabilidad de transición de una cadena de markov de primer orden

Question

Hay un proyecto de investigación en el que estoy trabajando actualmente que requiere que analice varios aspectos de "mundos" representados por matrices de probabilidad de transición, donde los nodos representan objetos en el mundo por el que nuestro "aprendiz" viaja. Estoy buscando una manera de medir el grado en que la estructura de las conexiones en un gráfico dado proporciona al aprendiz algún poder de predicción, por ejemplo, en un gráfico donde todos los vértices tienen el mismo valor, el aprendiz no tiene absolutamente ninguna capacidad de predecir el siguiente nodo/nodos dado el actual.

Los gráficos son todos ponderados y dirigidos, con la suma de las conexiones salientes de cada nodo normalizada a uno.

Estoy teniendo un poco de problemas para encontrar una buena manera de medir esto y realmente agradecería algún consejo, Gracias, Ron

Answer 1

No estoy seguro de entender su pregunta exacta, pero existe una fórmula explícita para la entropía teórica de una cadena de Markov de primer orden (que es lo que representa su gráfico dirigido y ponderado). Tienes que calcular el vector estacionario $p$ para su matriz estocástica $P$ (la dada por los pesos en su grafo dirigido) y entonces la fórmula para la entropía es simplemente:

$h(p,P)=-\sum_{i,j\in V}p_iP_{i,j}\log P_{i,j}$

donde la suma recorre todos los pares de vértices de su gráfico, $p_i$ es la probabilidad inicial del vértice $i$ y $P_{i,j}$ la probabilidad de transición (es decir, el peso de su arista $i,j$ ).

Answer 2

Aquí hay un ejemplo (aunque no muy bonito):

$P=\begin{pmatrix}1/6&1/2&1/3\\1/2&0&1/2\\0&1/3&2/3\end{pmatrix}$

Vector propio para el valor propio 1: $p=(1, 5/3, 7/2)$

Normalización: $p_\text{normalized}=(36/577, 60/577, 126/577)$

Así que la entropía (después de simplificar un poco juntando términos) es:

$h(p,P)=-\frac{6}{577}\cdot\log(1/6)-\frac{54}{577}\cdot\log(1/3)-\frac{78}{577}\cdot\log(1/2)-\frac{84}{577}\cdot\log(2/3)$

Esto da un valor real aproximado de:

$h(p,P)\approx 0.274\ldots$

Una última cosa: si su matriz $P$ tiene cero entradas, el producto $P_{i,j}\log P_{i,j}$ será cero para la entrada correspondiente, incluso así el logaritmo sería infinito negativo (aquí gana la multiplicación por cero).