Redundancia (teoría de la información)

Un mensaje codificado con más bits de los necesarios

En teoría de la información , la redundancia mide la diferencia fraccionaria entre la entropía H(X) de un conjunto X y su valor máximo posible . ^{[1] [2]} De manera informal, es la cantidad de "espacio" desperdiciado que se utiliza para transmitir ciertos datos. La compresión de datos es una forma de reducir o eliminar la redundancia no deseada, mientras que la corrección de errores hacia adelante es una forma de agregar redundancia deseada con fines de detección y corrección de errores cuando se comunica a través de un canal ruidoso de capacidad limitada . ${\displaystyle \log(|{\mathcal {A}}_{X}|)}$

Definición cuantitativa

Al describir la redundancia de datos brutos, la tasa de una fuente de información es la entropía media por símbolo. Para fuentes sin memoria, esto es simplemente la entropía de cada símbolo, mientras que, en el caso más general de un proceso estocástico , es

${\displaystyle r=\lim _{n\to \infty }{\frac {1}{n}}H(M_{1},M_{2},\dots M_{n}),}$

en el límite, cuando n tiende a infinito, de la entropía conjunta de los primeros n símbolos dividida por n . Es común en la teoría de la información hablar de la "velocidad" o " entropía " de un lenguaje. Esto es apropiado, por ejemplo, cuando la fuente de información es prosa en inglés. La velocidad de una fuente sin memoria es simplemente , ya que por definición no hay interdependencia de los mensajes sucesivos de una fuente sin memoria. ^{[ cita requerida ]} ${\displaystyle H(M)}$

La tasa absoluta de un idioma o fuente es simplemente

${\displaystyle R=\log |\mathbb {M} |,\,}$

el logaritmo de la cardinalidad del espacio del mensaje, o alfabeto. (Esta fórmula a veces se denomina función Hartley ). Esta es la velocidad máxima posible de información que se puede transmitir con ese alfabeto. (El logaritmo debe llevarse a una base apropiada para la unidad de medida en uso). La velocidad absoluta es igual a la velocidad real si la fuente no tiene memoria y tiene una distribución uniforme .

La redundancia absoluta puede entonces definirse como

${\displaystyle D=R-r,\,}$

la diferencia entre la tasa absoluta y la tasa.

La cantidad se denomina redundancia relativa y proporciona la máxima relación de compresión de datos posible , cuando se expresa como el porcentaje en el que se puede reducir el tamaño de un archivo. (Cuando se expresa como una relación entre el tamaño del archivo original y el tamaño del archivo comprimido, la cantidad proporciona la relación de compresión máxima que se puede lograr). Complementaria al concepto de redundancia relativa está la eficiencia , definida como tal que . Una fuente sin memoria con una distribución uniforme tiene redundancia cero (y, por lo tanto, una eficiencia del 100 %) y no se puede comprimir. ${\displaystyle {\frac {D}{R}}}$ ${\displaystyle R:r}$ ${\displaystyle {\frac {r}{R}},}$ ${\displaystyle {\frac {r}{R}}+{\frac {D}{R}}=1}$

Otras nociones

Una medida de redundancia entre dos variables es la información mutua o una variante normalizada. Una medida de redundancia entre muchas variables está dada por la correlación total .

La redundancia de datos comprimidos se refiere a la diferencia entre la longitud esperada de datos comprimidos de los mensajes (o tasa de datos esperada ) y la entropía (o tasa de entropía ). (Aquí asumimos que los datos son ergódicos y estacionarios , por ejemplo, una fuente sin memoria). Aunque la diferencia de tasa puede ser arbitrariamente pequeña a medida que aumenta, la diferencia real no puede, aunque teóricamente puede estar limitada superiormente por 1 en el caso de fuentes sin memoria de entropía finita. ${\displaystyle n}$ ${\displaystyle L(M^{n})\,\!}$ ${\displaystyle L(M^{n})/n\,\!}$ ${\displaystyle nr\,\!}$ ${\displaystyle r\,\!}$ ${\displaystyle L(M^{n})/n-r\,\!}$ ${\displaystyle n\,\!}$ ${\displaystyle L(M^{n})-nr\,\!}$

La redundancia en un contexto de teoría de la información también puede referirse a la información que es redundante entre dos informaciones mutuas. Por ejemplo, dadas tres variables , , y , se sabe que la información mutua conjunta puede ser menor que la suma de las informaciones mutuas marginales: . En este caso, al menos parte de la información sobre divulgada por o es la misma. Esta formulación de redundancia es complementaria a la noción de sinergia, que ocurre cuando la información mutua conjunta es mayor que la suma de las marginales, lo que indica la presencia de información que solo es divulgada por el estado conjunto y no por cualquier conjunto más simple de fuentes. ^{[3] [4]} ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle Y}$ ${\displaystyle I(X_{1},X_{2};Y)<I(X_{1};Y)+I(X_{2};Y)}$ ${\displaystyle Y}$ ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$

Redundancia de grupo

La medida de redundancia por pares anterior se puede generalizar a un conjunto de n variables.

${\displaystyle Redundancy=I(X_{1},X_{2},...,X_{n};Y)-\left(I(X_{1};Y)+I(X_{2};Y)+...I(X_{n};Y)\right)}$. ^[5] Como en la medida por pares anterior, si este valor es negativo, se dice que el conjunto de variables es redundante.

Véase también

• Codificación de redundancia mínima
  • Codificación de Huffman
• Compresión de datos
• Función Hartley
• Negentropía
• Teorema de codificación de fuentes
• Sobrecompletitud

Referencias

1. Aquí se supone que son los conjuntos en los que se definen las distribuciones de probabilidad. ${\displaystyle {\mathcal {A}}_{X}}$
2. MacKay, David JC (2003). "2.4 Definición de entropía y funciones relacionadas". Teoría de la información, inferencia y algoritmos de aprendizaje. Cambridge University Press . pág. 33. ISBN 0-521-64298-1La redundancia mide la diferencia fraccionaria entre H(X) y su valor máximo posible , ${\displaystyle |\log(|{\mathcal {A}}_{X}|)}$
3. Williams, Paul L.; Beer, Randall D. (2010). "Descomposición no negativa de información multivariada". arXiv : 1004.2515 [cs.IT].
4. Gutknecht, AJ; Wibral, M.; Makkeh, A. (2021). "Bits and pieces: Understanding information decomposition from part-whole relationships and formal logic". Actas de la Royal Society A: Ciencias matemáticas, físicas y de ingeniería . 477 (2251). arXiv : 2008.09535 . Bibcode :2021RSPSA.47710110G. doi :10.1098/rspa.2021.0110. PMC 8261229. PMID 35197799.  S2CID 221246282  . 
5. Chechik, Gal; Globerson, Amir; Anderson, M.; Young, E.; Nelken, Israel; Tishby, Naftali (2001). "Las medidas de redundancia grupal revelan una reducción de la redundancia en la vía auditiva". Avances en sistemas de procesamiento de información neuronal . 14 . MIT Press.

• Reza, Fazlollah M. (1994) [1961]. Introducción a la teoría de la información . Nueva York: Dover [McGraw-Hill]. ISBN 0-486-68210-2.
• Schneier, Bruce (1996). Criptografía aplicada: protocolos, algoritmos y código fuente en C. Nueva York: John Wiley & Sons, Inc. ISBN 0-471-12845-7.
• Auffarth, B; Lopez-Sanchez, M.; Cerquides, J. (2010). "Comparación de medidas de redundancia y relevancia para la selección de características en la clasificación de tejidos de imágenes de TC". Avances en minería de datos. Aplicaciones y aspectos teóricos . Springer. págs. 248–262. CiteSeerX  10.1.1.170.1528 .