Variación de la información

Medida de distancia entre dos agrupaciones relacionadas con información mutua

En teoría de la probabilidad y teoría de la información , la variación de la información o distancia de información compartida es una medida de la distancia entre dos agrupaciones ( particiones de elementos ). Está estrechamente relacionada con la información mutua ; de hecho, es una expresión lineal simple que involucra la información mutua. Sin embargo, a diferencia de la información mutua, la variación de la información es una métrica verdadera , ya que obedece a la desigualdad triangular . ^{[1] [2] [3]}

Diagrama de información que ilustra la relación entre las entropías de información , la información mutua y la variación de la información.

Definición

Supongamos que tenemos dos particiones y de un conjunto en subconjuntos disjuntos , a saber, y . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle A}$ ${\displaystyle X=\{X_{1},X_{2},\ldots ,X_{k}\}}$ ${\displaystyle Y=\{Y_{1},Y_{2},\ldots ,Y_{l}\}}$

Dejar:

${\displaystyle n=\sum _{i}|X_{i}|=\sum _{j}|Y_{j}|=|A|}$

${\displaystyle p_{i}=|X_{i}|/n}$y ${\displaystyle q_{j}=|Y_{j}|/n}$

${\displaystyle r_{ij}=|X_{i}\cap Y_{j}|/n}$

Entonces la variación de información entre las dos particiones es:

${\displaystyle \mathrm {VI} (X;Y)=-\sum _{i,j}r_{ij}\left[\log(r_{ij}/p_{i})+\log(r_{ij}/q_{j})\right]}$.

Esto es equivalente a la distancia de información compartida entre las variables aleatorias i y j con respecto a la medida de probabilidad uniforme en definida por para . ${\displaystyle A}$ ${\displaystyle \mu (B):=|B|/n}$ ${\displaystyle B\subseteq A}$

Contenido de información explícita

Podemos reescribir esta definición en términos que resalten explícitamente el contenido de información de esta métrica.

El conjunto de todas las particiones de un conjunto forma una red compacta donde el orden parcial induce dos operaciones, el encuentro y la unión , donde el máximo es la partición con un solo bloque, es decir, todos los elementos agrupados, y el mínimo es , la partición formada por todos los elementos como singletons. El encuentro de dos particiones y es fácil de entender como aquella partición formada por todas las intersecciones de pares de un bloque de, , de y uno, , de . Entonces se sigue que y . ${\displaystyle \wedge }$ ${\displaystyle \vee }$ ${\displaystyle {\overline {\mathrm {1} }}}$ ${\displaystyle {\overline {\mathrm {0} }}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X_{i}}$ ${\displaystyle X}$ ${\displaystyle Y_{i}}$ ${\displaystyle Y}$ ${\displaystyle X\wedge Y\subseteq X}$ ${\displaystyle X\wedge Y\subseteq Y}$

Definamos la entropía de una partición como ${\displaystyle X}$

${\displaystyle H\left(X\right)\,=\,-\sum _{i}\,p_{i}\log p_{i}}$,

donde . Claramente, y . La entropía de una partición es una función monótona en la red de particiones en el sentido de que . ${\displaystyle p_{i}=|X_{i}|/n}$ ${\displaystyle H({\overline {\mathrm {1} }})=0}$ ${\displaystyle H({\overline {\mathrm {0} }})=\log \,n}$ ${\displaystyle X\subseteq Y\Rightarrow H(X)\geq H(Y)}$

Entonces la distancia VI entre y está dada por ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle \mathrm {VI} (X,Y)\,=\,2H(X\wedge Y)\,-\,H(X)\,-\,H(Y)}$.

La diferencia es una pseudométrica, ya que no implica necesariamente que . Según la definición de , es . ${\displaystyle d(X,Y)\equiv |H\left(X\right)-H\left(Y\right)|}$ ${\displaystyle d(X,Y)=0}$ ${\displaystyle X=Y}$ ${\displaystyle {\overline {\mathrm {1} }}}$ ${\displaystyle \mathrm {VI} (X,\mathrm {1} )\,=\,H\left(X\right)}$

Si en el diagrama de Hasse dibujamos un borde desde cada partición hasta el máximo y le asignamos un peso igual a la distancia VI entre la partición dada y , podemos interpretar la distancia VI como básicamente un promedio de las diferencias de los pesos de los bordes hasta el máximo ${\displaystyle {\overline {\mathrm {1} }}}$ ${\displaystyle {\overline {\mathrm {1} }}}$

${\displaystyle \mathrm {VI} (X,Y)\,=\,|\mathrm {VI} (X,{\overline {\mathrm {1} }})\,-\,\mathrm {VI} (X\wedge Y,{\overline {\mathrm {1} }})|\,+\,|\mathrm {VI} (Y,{\overline {\mathrm {1} }})\,-\,\mathrm {VI} (X\wedge Y,{\overline {\mathrm {1} }})|\,=\,d(X,X\wedge Y)\,+\,d(Y,X\wedge Y)}$.

Como se definió anteriormente, se cumple que la información conjunta de dos particiones coincide con la entropía de la unión. ${\displaystyle H(X)}$

${\displaystyle H(X,Y)\,=\,H(X\wedge Y)}$

y también tenemos que coincide con la entropía condicional del encuentro (intersección) relativa a . ${\displaystyle d(X,X\wedge Y)\,=\,H(X\wedge Y|X)}$ ${\displaystyle X\wedge Y}$ ${\displaystyle X}$

Identidades

La variación de la información satisface

${\displaystyle \mathrm {VI} (X;Y)=H(X)+H(Y)-2I(X,Y)}$,

donde es la entropía de , y es la información mutua entre y con respecto a la medida de probabilidad uniforme en . Esto se puede reescribir como ${\displaystyle H(X)}$ ${\displaystyle X}$ ${\displaystyle I(X,Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle A}$

${\displaystyle \mathrm {VI} (X;Y)=H(X,Y)-I(X,Y)}$,

¿Dónde está la entropía conjunta de y , o ${\displaystyle H(X,Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle \mathrm {VI} (X;Y)=H(X|Y)+H(Y|X)}$,

donde y son las respectivas entropías condicionales . ${\displaystyle H(X|Y)}$ ${\displaystyle H(Y|X)}$

La variación de la información también puede ser limitada, ya sea en términos del número de elementos:

${\displaystyle \mathrm {VI} (X;Y)\leq \log(n)}$,

O con respecto a un número máximo de clústeres, : ${\displaystyle K^{*}}$

${\displaystyle \mathrm {VI} (X;Y)\leq 2\log(K^{*})}$

Desigualdad triangular

Para verificar la desigualdad del triángulo , desarrollamos usando la identidad . Basta con demostrar que el lado derecho tiene un límite inferior que no es menor que el lado izquierdo. ${\displaystyle \mathrm {VI} (X;Z)\leq \mathrm {VI} (X;Y)+\mathrm {VI} (Y;Z)}$ ${\displaystyle \mathrm {VI} (X;Y)=H(X|Y)+H(Y|X)}$ $${\displaystyle H(X|Z)\leq H(X|Y)+H(Y|Z)}$$ $${\displaystyle H(X|Y)+H(Y|Z)\geq H(X|Y,Z)+H(Y|Z)=H(X,Y|Z)}$$

Referencias

1. Arabie, P.; Boorman, SA (1973). "Escalamiento multidimensional de medidas de distancia entre particiones". Revista de Psicología Matemática . 10 (2): 148–203. doi :10.1016/0022-2496(73)90012-6.
2. WH Zurek, Nature, vol. 341, pág. 119 (1989); WH Zurek, Physics Review A, vol. 40, pág. 4731 (1989)
3. Meilă, Marina (2003). "Comparación de agrupamientos por la variación de la información". En Bernhard Schölkopf; Manfred K. Warmuth (eds.). Teoría del aprendizaje y máquinas de núcleo . 16.ª Conferencia anual sobre teoría del aprendizaje computacional y 7.º taller de núcleo. Lecture Notes in Computer Science, vol. 2777. Springer. págs. 173–187. doi :10.1007/978-3-540-45167-9_14. ISBN 978-3-540-40720-1. Número de identificación del sujeto  4341039.

Lectura adicional

• Meila, M. (2007). "Comparación de agrupamientos: una distancia basada en la información". Journal of Multivariate Analysis . 98 (5): 873–895. doi : 10.1016/j.jmva.2006.11.013 .
• Kingsford, Carl (2009). "Information Theory Notes" (PDF) . Consultado el 22 de septiembre de 2009 .
• Kraskov, Alexander; Harald Stögbauer; Ralph G. Andrzejak; Peter Grassberger (2003). "Agrupamiento jerárquico basado en información mutua". arXiv : q-bio/0311039 .

Enlaces externos

• Partanalyzer incluye una implementación en C++ de VI y otras métricas e índices para analizar particiones y agrupaciones.
• Implementación en C++ con archivos mex de MATLAB