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 . Ésta 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 a otro o viceversa. La distancia de información se definió e investigó por primera vez en [2] basándose en principios termodinámicos , ver también.[3] Posteriormente, alcanzó la forma final en. [4] Se aplica en la distancia de compresión normalizada y la distancia de Google normalizada .
Propiedades
Formalmente la distancia de la información Entre y es definido por
con un programa binario finito para la computadora universal fija con cadenas binarias finitas como entradas. En [4] se comprueba que con
dónde es la complejidad de Kolmogorov definida por [1] del tipo de prefijo. [5] Este es la cantidad importante.
Universalidad
Dejar ser la clase de distancias semicomputables superiores que satisfacen la condición de densidad
Esto excluye distancias irrelevantes como por ; tiene cuidado de que si la distancia aumenta, el número de objetos dentro de esa distancia de un objeto dado aumenta. Si luego hasta un término aditivo constante. [4] Las expresiones probabilísticas de la distancia son la primera clase cohomológica en cohomología simétrica de información, [6] que puede ser concebida como una propiedad de universalidad.
Metricidad
La distancia es una métrica hasta un aditivotérmino en las igualdades (in) métricas. [4] La versión probabilística de la métrica es de hecho única, según demostró Han en 1981. [7]
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 son de formato auto-delimitante , 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 superponer al máximo: Para se puede dividir en un programa que convierte objeto al objeto , y otro programa que se concatenó con los primeros conversos a mientras que la concatenación de estos dos programas es el programa más corto para convertir entre estos objetos. [4]
Superposición mínima
Los programas para convertir entre objetos y también se puede hacer una superposición mínima. Existe un programa de longitud hasta un término aditivo de que mapas a y tiene poca complejidad cuando es conocida (). 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 .
Aplicaciones
Teórico
El resultado de An.A. Muchnik sobre superposición mínima anterior es una aplicación teórica importante que muestra que existen ciertos códigos: para ir a un objeto objetivo finito desde cualquier objeto, ¡hay un programa que casi solo depende del objeto objetivo! Este resultado es bastante preciso y el término de error no se puede mejorar significativamente. [9] La información sobre distancias era material en el libro de texto, [10] aparece en la Enciclopedia sobre distancias. [11]
Práctico
Para determinar la similitud de objetos como genomas, idiomas, música, ataques de Internet y gusanos, programas de software, etc., la distancia de información se normaliza y los términos de complejidad de Kolmogorov se aproximan mediante compresores del mundo real (la complejidad de Kolmogorov es un límite inferior a 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 refiere a objetos proporcionados como archivos de computadora, como el genoma de un mouse o el texto de un libro. Si los objetos se dan simplemente por su nombre, como 'Einstein' o 'tabla' o el nombre de un libro o el nombre 'mouse', 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. Cada motor de búsqueda en una base de datos que proporciona recuentos de páginas agregados se puede utilizar en la distancia de Google normalizada (NGD). Está disponible un paquete de Python para calcular todas las distancias y volúmenes de información, información mutua multivariante, información mutua condicional, entropías conjuntas, correlaciones totales, en un conjunto de datos de n variables. [12]
Referencias
- ^ a b A.N. Kolmogorov, Tres enfoques para la definición cuantitativa de información, Los problemas informan. Transmission, 1: 1 (1965), 1-7
- ^ M. Li, PMB Vitanyi, Teoría de la termodinámica de la computación, Proc. Taller de Física de Computación IEEE, Dallas, Texas, EE. UU., 1992, 42–46
- ^ M. Li, PMB Vitanyi, Reversibilidad y cálculo adiabático: comercio de tiempo y espacio por energía, Proc. R. Soc. Lond. A 9 de abril de 1996 vol. 452 no. 1947 769–789
- ^ a b c d e C.H. Bennett, P. Gacs, M. Li, PMB Vitanyi, W. Zurek, Distancia de la información, IEEE Transactions on Information Theory, 44: 4 (1998), 1407–1423
- ^ LA Levin, Leyes de conservación de la información (no crecimiento) y aspectos de la base de la teoría de la probabilidad, Los problemas informan. Transmission, 10: 3 (1974), 30–35
- ^ P. Baudot, La máquina de Poincaré-Shannon: aspectos de la física estadística y el aprendizaje automático de la cohomología de la información, entropía, 21: 9 - 881 (2019)
- ^ Te Sun Han, Una singularidad de la distancia de información de Shannon y problemas de no negatividad relacionados, Diario de combinatoria. 6: 4 págs. 320-331 (1981), 30-35
- ^ Muchnik, Andrej A. (2002). "Complejidad condicional y códigos" . Informática Teórica . 271 (1–2): 97–109. doi : 10.1016 / S0304-3975 (01) 00033-0 .
- ^ NK Vereshchagin, MV Vyugin, Programas independientes de longitud mínima para traducir entre cadenas dadas, Proc. 15th Ann. Conf. Complejidad computacional, 2000, 138–144
- ^ M.Hutter, Inteligencia artificial universal: decisiones secuenciales basadas en la probabilidad algorítmica, Springer, 1998
- ^ MM Deza, E Deza, Enciclopedia de distancias, Springer, 2009, doi : 10.1007 / 978-3-642-00234-2
- ^ "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
- Arkhangel'skii, AV; Pontryagin, LS (1990), Topología general I: Teoría de la dimensión de conceptos básicos y construcciones , Enciclopedia de Ciencias Matemáticas, Springer , ISBN 3-540-18178-4