Teoría de la información

Introducción

¿Se te ha ocurrido qué tan útil es la información que obtienen las compañías de internet cuando te piden tu nombre, dirección, tal vez tu fecha de nacimiento, y hasta mucho más? ¿Porqué es útil esa información? ¿Podemos cuantificar esta información?

Este artículo es para la gente que le gusta las matemáticas, pero puede ser recreacional y no pasa de matemáticas de nivel universidad. Si recuerdas como funciona el logaritmo, vas a estar bien, pero trataré de ir lento de todas maneras. La probabilidad se reduce aquí a fracciones simples, así que no necesitas conocimiento avanzado de ese campo, excepto que las probabilidades independientes se multiplican. Sólo una vez use una distribución de Bernoulí, la cual puedes ignorar con seguridad.

Para terminar, las ecuaciones en esta página estan escritas usando MathML, que funciona automáticamente con Firefox pero no con el resto de los navegadores, aunque hay plugins de MathML para IE (MathPlayer). Creo que no tienes opción si usas Safari o Chrome excepto esperar a que esos navegadores lo soporten. Esta página no tendrá sentido sin las ecuaciones.

Teoría

Shannon, el inventor de la moderna teoría de la información, usa esta definición como la base de información,

I_{x} = - \log_{2} p_{x},

lo cual significa que la información de un evento x es más grande si la probabilidad de ese evento es más pequeña. En otras palabras, un evento tiene más información si es más dificil de adivinar. Pero eso no es todo. La información de la unión de dos eventos independientes es la suma de sus informaciones individuales. Explicitamente, en equaciones,

p_{x,y} = p_{x} \cdot p_{y}

I_{x,y} = - \log_{2} p_{x,y} = - \log_{2} (p_{x} \cdot p_{y}) = - \log_{2} p_{x} - \log_{2} p_{y} = I_{x} + I_{y} .

Esta es una de las razones el logaritmo es la opción natural para convertir probabilidades en información, ya que sólo el logaritmo (de cualquier base) puede convertir productos arbitrarios en sumas.

Muy seguido no sabes el valor exacto de tu variable aleatoria X, pero te gustaría saber qué tan informativa X es en promedio. Sucede que esta cantidad se usa todo el tiempo en probabilidad, y se le llama la Entropía de X (o H(X)).

H (X) = E [I_{X}] = \sum_{x} p_{x} \cdot I_{x} = - \sum_{x} p_{x} \log_{2} p_{x} .

La población humana como espacio de probabilidad

Es fácil hablar acerca de información de gente. En esta teoría, necesitamos un espacio probabilistico en que podamos asignar información. El experimento más simple involucra considerar a cada persona como una entidad en este espacio de probabilidad, y cada propiedad (o variable aleatoria) X adquiere una probabilidad sumando el número de la gente que tiene esa propiedad y dividiendolo entre la poblacón humana.

De acuerdo a la Agencia de Censo de los E.U., la población mundial está proyectada a ser 7 mil millones en Abril del 2012 (accesado en 2011-09-04). Eso significa que la información máxima posible en este problema, suficiente para reducirla a una sola persona, corresponde a

I_{x} = - \log_{2} \frac{1}{n} = \log_{2} n = \log_{2} 7,000,000,000 = 32.7 bits .

Por supuesto, la información mínima en este y cualquier otro problema es 0 bits, correspondiendo aquí en cualquier propiedad que todos los humanos tienen (p=1). Por ejemplo, si yo te dijera que tengo un corazón, eso tendría cero información en reducir cual de todos los humanos soy yo.

Información definida de esta manera también corresponde a la cantidad mínima de almacenaje necesario para identificar eventos en este espacio. Por eso me parece increible que podríamos identificar únicamente a cada humano vivo en este instante usando sólo 33 bits (o un poco más de 4 bytes). Usando el estimado de Carl Haub, el número de gente que han vivido en la historia de la Tierra suman 106 mil millones de personas, así que el número de bits necesarios para identificar a cualquiera de ellos es

I_{x} = \log_{2} 106,456,367,669 = 36.63 bits .

Género: 1 bit

La población humana es casi exactamente pareja entre hombres y mujeres,

p_{masculino} = p_{femenino} = \frac{1}{2},

así que saber mi género vale

I_{x} = - \log_{2} \frac{1}{2} = 1 bit.

Aunque parezca poco, el género es comunmente independiente de otros tipos de información (por ejemplo, geografía, pero no nombres), así que puedes añadir fácilmente y seguramente 1 bit de información preguntando por el sexo.

Geografía (direción): altamente informativa

Usando estadísticas publicadas acerca de la población de estas regiones distintas (usualmente aproximaciones de Wikipedia), saber dónde vivo con resolución mayor y mayor te provée con la siguiente información.

I_{EUA} = - \log_{2} \frac{312,138,791}{7,000,000,000} = 4.49 bits.

I_{NJ} = - \log_{2} \frac{8,791,894}{7,000,000,000} = 9.64 bits.

I_{ZIP 08540} = - \log_{2} \frac{56,534}{7,000,000,000} = 16.92 bits.

I_{Princeton} = - \log_{2} \frac{30,000}{7,000,000,000} = 17.83 bits.

Me sorprende que la ciudad provée más información que el código postal en este caso, pero estoy seguro que varía dependiendo en qué tan grande es tu ciudad (si tiene múltiples códigos postales).

Me dió un poco de miedo las estadísticas detalladas de mi código postal disponible en city-data.com. Por ejemplo, si sabes que soy un hispano viviendo en 08540, tendrías

I_{ZIP 08540 & Hispano} = - \log_{2} \frac{1,757}{7,000,000,000} = 21.93 bits.

Si sabes dónde trabajo o estudio, tendrías una cantidad similar de información.

I_{estudiante de la Universidad de Princeton} = - \log_{2} \frac{7,567}{7,000,000,000} = 19.82 bits.

I_{estudiante de posgrado de la Universidad de Princeton} = - \log_{2} \frac{2,479}{7,000,000,000} = 21.43 bits.

No sé qué tan informativa una dirección con calle es. Mi calle es muy corta, con 16 edificios, cada uno con 3 unidades, y cada unidad alberga al menos 2 personas, pero a veces un poco más. Si quedamos con un promedio de 3 personas por unidad, tendríamos

I_{mi calle} = - \log_{2} \frac{16 \cdot 3 \cdot 3}{7,000,000,000} = 25.53 bits.

Y si tienes el número de mi unidad, tendrías casi la información máxima,

I_{mi calle & número de unidad} = - \log_{2} \frac{3}{7,000,000,000} = 31.12 bits,

ya que actualmente esa información reduce las posibilidades a mí, mi esposa, y mi bebé. Sin embargo, la realidad es menos ideal. Las direcciónes expiran regularmente, especialmente en un poblado estudiantil. Regularmente recibo correo destinado a gente que solía vivir aquí, así que todas esas compañías tienen información vieja. Mi dirección ha sido usada para identificar hasta tal vez 7 parejas o compañeros de cuarto en los últimos 10 años, lo cual reduce la información a

I_{mi calle & número de unidad, corregida} = - \log_{2} \frac{3 \cdot 7 \cdot 2}{7,000,000,000} = 27.31 bits.

Nombres: > 12 bits

Limitado a los EUA, podrás encontrar qué tan comunes son tus nombres y apellidos en HowManyOfMe.com. Aunque esta página sugiera saber cuánta gente tiene tu nombre y apellido, lectura mas detallada revela que ellos asumen independencia, y admiten que esta es una suposición incorrecta. Por ello ignoramos esta información.

Recibí las siguientes estadísticas para mi nombre

I_{Alejandro} = - \log_{2} \frac{67,092}{312,138,791} = 12.18 bits.

I_{Ochoa} = - \log_{2} \frac{66,179}{312,138,791} = 12.20 bits.

I_{García} = - \log_{2} \frac{992,848}{312,138,791} = 8.30 bits.

Nótese que incluí mi segundo apellido, una propiedad de nombres de países hispanohablantes. Me imagino que en esos casos los dos apellidos se combinan independiente (o sea que las parejas no escogen con quien casarse a partir de sus apellidos). En ese caso, la información contenida en dos apellidos es, en promedio, el doble de un sólo apellido, como se usa en los EUA. Sin embargo, esto todavía no garantiza que mi nombre me identifique únicamente. De hecho, sé de una persona con un nombre completo (de dos apellidos) idéntico al mío de mi misma ciudad de Juárez, y tal vez menos sorprendentemente, su hermano también tiene un nombre completo idéntico al de mi hermano también.

El mismo sitio de internet sugiere que James y Smith son independientemente el nombre y apellido más comunes de los EUA. Los numeros para estos nombres mínimamente informativos se ven así.

I_{James} = - \log_{2} \frac{5,192,584}{312,138,791} = 5.91 bits.

I_{Smith} = - \log_{2} \frac{2,748,738}{312,138,791} = 6.83 bits.

Similarmente, Muhammad y Zhang han sido reportados de ser respectivamente el nombre y apellido más comunes del mundo. Sus contenido de información son

I_{Muhammad} = - \log_{2} \frac{150,000,000}{7,000,000,000} = 5.54 bits.

I_{Zhang} = - \log_{2} \frac{100,000,000}{7,000,000,000} = 6.13 bits.

Así que añadiendo estos contenidos de información mínimos, y redondeando para arriba con optimismo, vemos que el mínimo contenido de un nombre completo es de 12 bits. Así que aunque hay nombres muy informativos (creo que mi hijo tiene un nombre único, que es una combinación de nombres escocés, inglés, vasco, y holandés), es muy interesante saber que hay un nivel mínimo relativamente alto de información en un nombre. Esto tiene sentido, de lo contrario los nombres serían inútiles, ya que no servirían su propósito de identificar gente.

Nótese que los nombres tienen alta correlación con género (un Alejandro es casi seguramente hombre). La conversión es obviamente complicada, así que muchos sitios de internet te pedirán los dos datos de todas maneras, pero su información usualmente no es aditiva. Similarmente, los nombres y la geografía tienen correlación alta (mi nombre es mucho más informativo en los EUA que en México). Por el otro lado, los nombres son probablemente independientes de las fechas de nacimiento (siguiente), así que podemos añadir su información.

Quería mencionar unas excepciones interesantes a la independencia entre nombres y fechas de nacimiento. Una que recuerdo es de México, donde la gente solía ser nombrada (al menos uno de sus nombres) después del santo en cuyo onomástico nacieron. Al menos creo que así fueron nombradas algunas de mis tías, pero Wikipedia sólo confirmó esta tradición en Italia. En un ejemplo diferente, los nombres ghaneses usualmente son escogidos a partir del día de la semana en que la persona nació. En ambos ejemplos, la información de un nombre y un cumpeaños es más pequeña que la suma de sus informaciones independientes, pero podemos corregir fácilmente los componentes que son dependientes (usualmente un solo nombre) para tener una aproximación más decente.

Fechas de nacimiento: ~ 14 bits

¿Cuánta información hay en un cumpleaños (día y mes, pero ignorando el año por el momento)? Para tener una respuesta rápida, vamos a simplificar el problema. Asumiremos que hay exactamente 365 días en el año y que la probabilidad de nacer en cualquiera de esos días es la misma. En ese caso un cumpleaños tiene la siguiente información.

I_{día y mes de nacimiento} = \log_{2} 365 = 8.51 bits.

Claro es que las cosas son más complicadas. Roy Murphy encontró que los cumpleaños son significantemente no uniformes. Él encontró específicamente que los naciemientos son un poco más comunes entre julio y octubre, mientras que son un poco menos comunes entre marzo y mayo. David Glech encontró una inclinación significante de fechas por día de la semana, en un grupo de americanos, con menos nacimientos durante el fin de semana, que podría ser explicado por las cesareas e inducciones siendo más comunes durante la semana.

Al final, una distribución de cumpleaños menos uniforme inplica que en promedio el contenido informático de un cumpleaños es menor de lo que hemos estimado. Esto es porque la entroía de una variable aleatoria es máxima cuando su distribución es uniforme.

Si tenemos el año de nacimiento, esta información adicional es equivalente a saber tu edad. Asumiendo que sigues con vida, los límites de edades son en la mayoría entre 0 y 85 años. Si otra vez asumimos una distribución uniformes con esos límites, encontrarás que tu edad/año de nacimiento tiene esta cantidad de información.

I_{año de nacimiento} = \log_{2} 86 = 6.43 bits.

Así que combinando el día y mes con el año de nacimiento, que probablemente son independientes, tenemos un total de 14.94 bits con una fecha de nacimiento completa.

La distribución de edades tiene una inclinación bien sabida hacia las edades menores. Puedes ver la distribución exacta para Americanos. Así que otra vez, la implicación es que la verdadera información de una edad es menor de lo que hemos calculado. Las edades menores son menos informativas, mientras que las edades mayores son más informativas.

Número de piernas: muy poco informativo

Quería tener un ejemplo detallado de algo que es muy poco informativo. La gran mayoría de la gente tiene 2 piernas, pero una cantidad pequeña tiene 1 o hasta 0, habiéndolas perdido en accidentes o por otras razones. Me imagino que hay gente con más de dos piernas, por anormalidades genéticas o de desarrollo, pero para simplificar este análisis ignoraré estos casos. Busqué distribuciones de piernas en el internet, pero no pude encontrar nada. Así que inventaré datos para mi ejemplo.

Asumase que la probabilidad de perder una pierna es

p_{pierna perdida} = \frac{1}{10,000},

y que la perdidad de cada pierna es un evento independiente, así que la distribución de número de piernas perdidas es binomial con n=2. En este caso cada evento tiene esta información.

I_{2 piernas} = \log_{2} {(1 - \frac{1}{10,000})}^{2} = 0.000289 bits.

I_{1 pierna} = \log_{2} (2 \cdot \frac{1}{10,000} (1 - \frac{1}{10,000})) = 12.29 bits.

I_{0 piernas} = \log_{2} {(\frac{1}{10,000})}^{2} = 26.58 bits.

Interesantemente, saber que alguien tiene menos de 2 piernas puede ser extremadamente informativo. Entonces, ¿porque los sitios de internet no preguntan tu número de piernas más seguido? El secreto está en el contenido promedio de información, o la entropía, del número de piernas. El problema es que los casos más informativos son precisamente los más raros, así que pesando su información por su probabilidad, el efecto se reduce comparado a la mayoría de los casos poco informativos de 2 piernas. En ecuaciones,

H (piernas) = - p_{2 piernas} \log_{2} p_{2 piernas} - p_{1 pierna} \log_{2} p_{1 pierna} - p_{0 piernas} \log_{2} p_{0 piernas} = 0.002746 bits.

En general, tenemos un bajo contenido promedio de información (o baja entropía) cuando uno o pocos casos dominan. Esta es la razón los sitios de internet no suelen preguntarte cuántas piernas tienes.

Color de ojos: ~ 1.5 bits en los EUA

Traté de buscar datos acerca de los colores de ojos, pero esto es lo mejor que encontré, hayado en respuestas Yahoo, y excepto por la "Academia Americana de Optalmología", no pude encontrar la fuente ni ninguna otra información acerca de estos datos.

I_{írises azules/grises} = \log_{2} \frac{32}{100} = 1.64 bits.

I_{írises azules/grises/verdes con puntos cafés/amarillos} = \log_{2} \frac{15}{100} = 2.74 bits.

I_{írises verdes/café claro con puntos mínimos} = \log_{2} \frac{12}{100} = 3.06 bits.

I_{írises cafés con puntos} = \log_{2} \frac{16}{100} = 2.64 bits.

I_{írises café oscuro} = \log_{2} \frac{25}{100} = 2 bits.

H (color de ojos) = 1.54 bits.

La situación es mucho peor mundialmente, ya que los ojos cafes dominan sobre los demás, y consecuentemente la entroía baja a casi cero (igual que en el ejemplo del "número de piernas").

Aunque hay un poco más de información que el género en los EUA (y son independientes), el color de ojos no es independiente de geografía y nombres, los cuales son mucho más informativos por sí mismos, así que tiene sentido que nadie pregunte por tu color de ojos en los sitios de internet.

Conclusiones

Pudimos estimar que la información de los nombres y fechas de nacimiento es independiente y altamente informativa, combinada proveyendo al menos 26 bits de información, a veces mucho más dependiendo del nombre. La geografía, o dirección postal, también es altamente informativa, y aunque no es independiente de las cantidades anteriores, combinadas probablemente se reducen a una sola persona en la mayoría de los casos.

Espero que este ejercicio les haya ayudado comprender en términos intuitivos cómo funciona la teoría de la información, y tal vez puedan aplicarla a tus datos de interés.