Redundancia (teoría de la información)

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]} Informalmente, 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 directa es una forma de agregar la 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 sin procesar, la tasa de una fuente de información es la entropía promedio 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 al infinito, de la entropía conjunta de los primeros n símbolos dividida por n . Es común en teoría de la información hablar de "tasa" o " entropía " de una lengua. Esto es apropiado, por ejemplo, cuando la fuente de información es la prosa inglesa. La tasa de una fuente sin memoria es simplemente , ya que por definición no existe interdependencia de los mensajes sucesivos de una fuente sin memoria. ^{[ cita necesaria ]} ${\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 de Hartley ). Ésta 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 tasa absoluta es igual a la tasa real si la fuente no tiene memoria y tiene una distribución uniforme .

La redundancia absoluta se puede definir entonces 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). Complementario al concepto de redundancia relativa es la eficiencia , definida como tal que . Una fuente sin memoria con una distribución uniforme tiene redundancia cero (y por lo tanto 100% de eficiencia) 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. La correlación total da una medida de redundancia entre muchas variables .

La redundancia de datos comprimidos se refiere a la diferencia entre la longitud esperada de los datos comprimidos de los mensajes (o velocidad de datos esperada ) y la entropía (o tasa de entropía ). (Aquí suponemos que los datos son ergódicos y estacionarios , por ejemplo, una fuente sin memoria). Aunque la diferencia de tasas puede ser arbitrariamente pequeña a medida que aumenta, la diferencia real no puede hacerlo, aunque teóricamente puede tener un límite superior de 1 en el caso de datos finitos. -entropía fuentes sin memoria. ${\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 contextos 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 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 los marginales, lo que indica la presencia de información que solo es revelada por el estado conjunto y no por una colección 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.

Ver también

• Codificación de redundancia mínima
  • Codificación Huffman
• Compresión de datos
• función Hartley
• Negentropía
• Teorema de codificación fuente
• 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. Prensa de la Universidad de Cambridge . pag. 33.ISBN​ 0-521-64298-1. La redundancia mide la diferencia fraccionaria entre H(X) y su valor máximo posible, ${\displaystyle |\log(|{\mathcal {A}}_{X}|)}$
3. Williams, Paul L.; Cerveza, Randall D. (2010). "Descomposición no negativa de información multivariada". arXiv : 1004.2515 [cs.IT].
4. Gutknecht, AJ; Wibral, M.; Makkeh, A. (2021). "Brocos y piezas: comprensión de la descomposición de la información a partir de relaciones parte-todo y lógica formal". Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería . 477 (2251). arXiv : 2008.09535 . Código Bib : 2021RSPSA.47710110G. doi :10.1098/rspa.2021.0110. PMC 8261229 . PMID  35197799. S2CID  221246282. 
5. Chechik, Gal; Globerson, Amir; Anderson, M.; Joven, 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 los sistemas de procesamiento de información neuronal . 14 . Prensa del MIT.

• Reza, Fazlollah M. (1994) [1961]. Una 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; López-Sánchez, 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 . Saltador. págs. 248–262. CiteSeerX  10.1.1.170.1528 .