Aprendiendo C#, Python, C++, A.I, BASIC...: Entropía de Shannon

"El hombre más importante del que probablemente no hayas oído hablar jamás."

En el ámbito de la teoría de la información la entropía, también llamada entropía de la información y entropía de Shannon (en honor a Claude E. Shannon), mide la incertidumbre de una fuente de información.

La entropía también se puede considerar como la cantidad de información promedio que contienen los símbolos usados. Los símbolos con menor probabilidad son los que aportan mayor información; por ejemplo, si se considera como sistema de símbolos a las palabras en un texto, palabras frecuentes como «que», «el», «a» aportan poca información, mientras que palabras menos frecuentes como «corren», «niño», «perro» aportan más información. Si de un texto dado borramos un «que», seguramente no afectará a la comprensión y se sobreentenderá, no siendo así si borramos la palabra «niño» del mismo texto original. Cuando todos los símbolos son igualmente probables (distribución de probabilidad plana), todos aportan información relevante y la entropía es máxima.

El concepto entropía es usado en termodinámica, mecánica estadística y teoría de la información. En todos los casos la entropía se concibe como una «medida del desorden» o la «peculiaridad de ciertas combinaciones». La entropía puede ser considerada como una medida de la incertidumbre y de la información necesarias para, en cualquier proceso, poder acotar, reducir o eliminar la incertidumbre. Resulta que el concepto de información y el de entropía están básicamente relacionados entre sí, aunque se necesitaron años de desarrollo de la mecánica estadística y de la teoría de la información antes de que esto fuera percibido.

Claude Elwood Shannon (30 de abril de 1916 – 24 de febrero de 2001) fue un matemático, ingeniero eléctrico y criptógrafo estadounidense recordado como «el padre de la teoría de la información».

Shannon es reconocido por haber fundado el campo de la teoría de la información con la publicación Una teoría matemática de la comunicación, que supuso un hito en 1948. Es quizás igualmente conocido por haber sentado las bases de la teoría del diseño del ordenador digital y el circuito digital en 1937. Con 21 años, mientras realizaba su maestría en el Massachusetts Institute of Technology (MIT), demostró con su tesis, que las aplicaciones electrónicas de álgebra booleana podrían construir cualquier relación lógico-numérica. Shannon contribuyó asimismo al campo del criptoanálisis para la defensa de Estados Unidos durante la Segunda Guerra Mundial, con trabajos sobre el descifrado de códigos y la seguridad en las telecomunicaciones.
Claude Elwod Shannon definió una forma de medir la cantidad de información que contiene una variable aleatoria, es lo que se conoce como Entropía de Shannon y su formula es la siguiente:

Esta obra está bajo una: Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional. Autor: Ondiz Zarraga
https://ondahostil.wordpress.com/2015/04/16/lo-que-he-aprendido-entropia-de-shannon/

The Man Who Turned Paper Into Pixels from Adam Westbrook on Vimeo.

La entropía definida por Shannon , referida a la teoría de la información, hace referencia a la cantidad media de información que contiene una variable aleatoria (psicológica) o, en particular, una fuente transmisión binaria. La información que aporta un determinado valor, xi, de una variable aleatoria discreta X, se define como:

I(xi) = log2(1/p(xi))

cuya unidad es el bit si se utiliza el logaritmo en base 2 (por ejemplo, cuando se emplea el logaritmo neperiano o natural se habla de nats).

La entropía o información media de la variable aleatoria discreta, X, se determina como la información media del conjunto de valores discretos que puede adoptar (también medida en bits):

H(x) = Σip(xi) •log2(1/p(xi))

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace EntropíaShannon_I
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

private void button1_Click(object sender, EventArgs e)
{
Application.Exit();
}

public static double logaritmo(double num)
{
return Math.Log(num) / Math.Log(2);
}
private void button2_Click(object sender, EventArgs e)
{

string entrada = textBox1.Text;
double entropia = 0;
Dictionary<char, double> tabla = new Dictionary<char, double>();

foreach (char c in entrada)
{
if (tabla.ContainsKey(c))
tabla[c]++;
else
tabla.Add(c, 1);

}
double frecuencia;
foreach (KeyValuePair<char, double> letra in tabla)
{
frecuencia = letra.Value / entrada.Length;
entropia += frecuencia * logaritmo(frecuencia);
}
entropia *= -1;
textBox2.Text = entropia.ToString();
}
}
}

Además de su definición y estudio, Shannon demostró analíticamente que la entropía es el límite máximo al que se puede comprimir una fuente sin ninguna pérdida de información.

La entropía de Shannon es el número de preguntas sí/no que se necesitan para llegar a la respuesta correcta. Es decir, imaginamos que hay un oráculo que siempre acierta y tenemos que hacerle preguntas hasta que lleguemos al valor de la variable. Esto lo podemos hacer de varias maneras: podemos ir dándole opciones una a una empezando en un valor y subiendo, dándole números al azar… O podemos hacer una búsqueda binaria. Si los valores límite de la variable son a y b y el punto medio entre ellos es c, hacemos lo siguiente:
Preguntamos si el valor está entre a y c
Si nos dice que sí descartamos el trozo entre c y b. En caso contrario el a – c
Calculamos el punto medio del trozo y repetimos la operación hasta llegar al valor.

El coste de este sistema es de log2(N), donde N es el número de puntos entre a y b.

Imaginemos que queremos saber cuál es la entropía de Shannon de tirar un dado. Los estados posibles son {1,2,3,4,5,6} y la probabilidad de todos es la misma. Si le preguntamos al oráculo por los números de uno en uno siguiendo el orden de mayor a menor en el mejor de los casos necesitaremos una única pregunta y en el peor 6 preguntas. Para saber cuántas preguntas necesitamos de media debemos tener en cuenta todos los casos posibles y cómo de probables son. Esto es más rápido si usamos el truco, se ve fácilmente que siempre necesitamos 2 o 3 preguntas (haced la prueba en casa ). Si repetimos este proceso para muchas tiradas de dados, de media necesitaremos log2(6)= 2.58 preguntas. Esto coincide con la entropía de Shannon que para este caso es: