Distancia de información

La distancia de información es la distancia entre dos objetos finitos (representados como archivos de computadora ) expresada como el número de bits en el programa más corto que transforma un objeto en otro o viceversa en una computadora universal . Esta es una extensión de la complejidad de Kolmogorov . ^[1] La complejidad de Kolmogorov de un solo objeto finito es la información en ese objeto; la distancia de información entre un par de objetos finitos es la información mínima requerida para ir de un objeto al otro o viceversa. La distancia de información se definió e investigó por primera vez en ^[2] con base en principios termodinámicos , ver también. ^[3] Posteriormente, alcanzó su forma final en. ^[4] Se aplica en la distancia de compresión normalizada y la distancia de Google normalizada .

Propiedades

Formalmente la distancia de información entre y se define por ${\displaystyle ID(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle ID(x,y)=\min\{|p|:p(x)=y\;\&\;p(y)=x\},}$

con un programa binario finito para la computadora universal fija con cadenas binarias finitas como entradas . En ^[4] se demuestra que con ${\displaystyle p}$ ${\displaystyle x,y}$ ${\displaystyle ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})}$

${\displaystyle E(x,y)=\max\{K(x\mid y),K(y\mid x)\},}$

donde es la complejidad de Kolmogorov definida por ^[1] del tipo de prefijo. ^[5] Esta es la cantidad importante. ${\displaystyle K(\cdot \mid \cdot )}$ ${\displaystyle E(x,y)}$

Universalidad

Sea la clase de distancias semicomputables superiores que satisfacen la condición de densidad ${\displaystyle \Delta }$ ${\displaystyle D(x,y)}$

${\displaystyle \sum _{x:x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y:y\neq x}2^{-D(x,y)}\leq 1,}$

Esto excluye distancias irrelevantes como para ; se ocupa de que si la distancia crece, entonces el número de objetos dentro de esa distancia de un objeto dado crece. Si entonces hasta un término aditivo constante. ^[4] Las expresiones probabilísticas de la distancia son la primera clase cohomológica en la cohomología simétrica de la información, ^[6] que puede concebirse como una propiedad de universalidad. ${\displaystyle D(x,y)={\frac {1}{2}}}$ ${\displaystyle x\neq y}$ ${\displaystyle D\in \Delta }$ ${\displaystyle E(x,y)\leq D(x,y)}$

Métrica

La distancia es una métrica hasta un término aditivo en las (in)igualdades métricas. ^[4] La versión probabilística de la métrica es de hecho única, como demostró Han en 1981. ^[7] ${\displaystyle E(x,y)}$ ${\displaystyle O(\log .\max\{K(x\mid y),K(y\mid x)\})}$

Superposición máxima

Si , entonces hay un programa de longitud que convierte a , y un programa de longitud tal que el programa convierte a . (Los programas tienen el formato autodelimitador, lo que significa que uno puede decidir dónde termina un programa y comienza el otro en la concatenación de los programas). Es decir, los programas más cortos para convertir entre dos objetos se pueden hacer superpuestos al máximo: Porque se puede dividir en un programa que convierte objeto a objeto , y otro programa que concatenado con el primero convierte a mientras que la concatenación de estos dos programas es un programa más corto para convertir entre estos objetos. ^[4] ${\displaystyle E(x,y)=K(x\mid y)}$ ${\displaystyle p}$ ${\displaystyle K(x\mid y)}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle q}$ ${\displaystyle K(y\mid x)-K(x\mid y)}$ ${\displaystyle qp}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle K(x\mid y)\leq K(y\mid x)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$

Superposición mínima

Los programas para convertir entre objetos y también pueden hacerse con una superposición mínima. Existe un programa de longitud hasta un término aditivo de que se aplica a y tiene una complejidad pequeña cuando se conoce ( ). Intercambiando los dos objetos tenemos el otro programa ^[8] Teniendo en cuenta el paralelismo entre la teoría de la información de Shannon y la teoría de la complejidad de Kolmogorov , se puede decir que este resultado es paralelo a los teoremas de Slepian-Wolf y Körner–Imre Csiszár–Marton. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle p}$ ${\displaystyle K(x\mid y)}$ ${\displaystyle O(\log(\max\{K(x\mid y),K(y\mid x)\}))}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle K(p\mid x)\approx 0}$

Aplicaciones

Teorético

El resultado de An.A. Muchnik sobre la superposición mínima anterior es una aplicación teórica importante que demuestra que existen ciertos códigos: para ir a un objeto objetivo finito desde cualquier objeto, existe un programa que depende casi exclusivamente del objeto objetivo. Este resultado es bastante preciso y el término de error no se puede mejorar significativamente. ^[9] La distancia de información era material en el libro de texto, ^[10] aparece en la Enciclopedia de distancias. ^[11]

Práctico

Para determinar la similitud de objetos como genomas, idiomas, música, ataques y gusanos de Internet, programas de software, etc., se normaliza la distancia de información y se aproximan los términos de complejidad de Kolmogorov mediante compresores del mundo real (la complejidad de Kolmogorov es un límite inferior de la longitud en bits de una versión comprimida del objeto). El resultado es la distancia de compresión normalizada (NCD) entre los objetos. Esto se aplica a objetos que se dan como archivos de computadora, como el genoma de un ratón o el texto de un libro. Si los objetos se dan solo por su nombre, como "Einstein" o "mesa" o el nombre de un libro o el nombre "ratón", la compresión no tiene sentido. Necesitamos información externa sobre lo que significa el nombre. El uso de una base de datos (como Internet) y un medio para buscar en la base de datos (como un motor de búsqueda como Google) proporciona esta información. Cualquier motor de búsqueda en una base de datos que proporcione recuentos agregados de páginas se puede utilizar en la distancia normalizada de Google (NGD). Está disponible un paquete de Python para calcular todas las distancias y volúmenes de información, información mutua multivariada, información mutua condicional, entropías conjuntas y correlaciones totales en un conjunto de datos de n variables. ^[12]

Referencias

1. AN Kolmogorov, Tres enfoques para la definición cuantitativa de la información, Problemas Inform. Transmisión, 1:1 (1965), 1–7
2. M. Li, PMB Vitanyi, Teoría de la termodinámica de la computación, Proc. Taller de física de la computación del IEEE, Dallas, Texas, EE. UU., 1992, 42–46
3. M. Li, PMB Vitanyi, Reversibilidad y computación adiabática: Intercambio de tiempo y espacio por energía, Proc. R. Soc. Lond. A 9 de abril de 1996 vol. 452 núm. 1947 769–789
4. CH Bennett, P. Gacs, M. Li, P. MB Vitanyi, W. Zurek, Distancia de información, IEEE Transactions on Information Theory, 44:4(1998), 1407–1423
5. LA Levin, Leyes de conservación de la información (sin crecimiento) y aspectos de la base de la teoría de la probabilidad, Problemas Inform. Transmisión, 10:3 (1974), 30–35
6. P. Baudot, La máquina de Poincaré-Shannon: física estadística y aspectos del aprendizaje automático de la cohomología de la información, Entropy, 21:9 - 881 (2019)
7. Te Sun Han, Una singularidad de la distancia de información de Shannon y problemas de no negatividad relacionados, Journal of combinatorics. 6:4 p.320-331 (1981), 30–35
8. Muchnik, Andrej A. (2002). "Complejidad condicional y códigos". Ciencias de la Computación Teórica . 271 (1–2): 97–109. doi : 10.1016/S0304-3975(01)00033-0 .
9. NK Vereshchagin, MV Vyugin, Programas independientes de longitud mínima para traducir entre cadenas dadas, Proc. 15th Ann. Conf. Computational Complexity, 2000, 138–144
10. M. Hutter, Inteligencia artificial universal: decisiones secuenciales basadas en probabilidad algorítmica, Springer, 1998
11. MM Deza, E Deza , Enciclopedia de distancias, Springer, 2009, doi :10.1007/978-3-642-00234-2
12. "InfoTopo: Análisis de datos de información topológica. Aprendizaje estadístico profundo supervisado y no supervisado - Intercambio de archivos - Github". github.com/pierrebaudot/infotopopy/ . Consultado el 26 de septiembre de 2020 .

Literatura relacionada

• Arkhangelskii, AV; Pontryagin, LS (1990), Topología general I: conceptos básicos y construcciones Teoría de la dimensión , Enciclopedia de ciencias matemáticas, Springer , ISBN 3-540-18178-4