Teoría de la Información: Shannon-Fano

Shannon-Fano

Este post forma parte de una serie de 5 pequeños artículos sobre Teoría de la Información.
Se trata de dar un breve repaso a esta rama de las matemáticas mediante un ejemplo aplicado.

Los cinco artículos son: Búsqueda Binaria, Búsqueda Jerárquica, Shannon-Fano, Huffman y Entropía.
Pueden leerlos ya o esperar a que se vayan publicando diariamente durante esta semana.

En los capítulos anteriores…

Hasta ahora hemos propuestos un par de métodos para resolver un problema sencillo: hay que adivinar, mediante preguntas de Si o No, la letra correcta de entre 8 posibles opciones. Además no todas las opciones tienen la misma probabilidad: la A tiene una probabilidad del 35%, la B del 25%, la C del 12%, la D del 10%, la E del 8%, la F del 6%, la G del 3% y finalmente la H tiene una probabilidad del 1%.

Un poco de teoría

En nuestra búsqueda del Santo Grial de las Preguntas nos hemos topado con un grave inconveniente: los métodos escogidos pueden ser mejores o peores según la distribución de probabilidades de nuestras letras. Llegados a este punto conviene abstraerse un poco de los problemas concretos y atacar directamente al corazón del problema abstracto. ¿Qué sería lo ideal a la hora de plantear una pregunta? Muy sencillo, lo ideal sería que la probabilidad del Si y la probabilidad del No sean de, aproximadamente, el 50% porque eso nos permitiría eliminar la mitad de las opciones cada vez. En el caso equiprobable ya encontramos un método que, casualmente, hacía eso: la Búsqueda Binaria. Ahora se trata de encontrar un método que haga algo equivalente para el caso no equiprobable para intentar mejorar el resultado anterior.

Shannon-Fano

Claude Shannon es el padre de la Teoría de la Información y Robert Fano era un colega suyo del MIT. Ambos siguieron la idea que acabo de citar para crear el método de Shannon-Fano. La idea es sencilla y se basa en lo ya citado, cada pregunta deberá plantearse de manera que el Si y el No tengan unas probabilidades de, aproximadamente, el 50%.

El problema es que es difícil hacer esto para un conjunto de datos suficientemente grande y complicado. Y además hay muchas maneras de implementar esto de manera más o menos eficiente que dan resultados diferentes entre sí lo cual nos indica que probablemente no sea un algoritmo óptimo.

Un posible método para nuestro ejemplo sería el que ven en la imagen superior. La primera pregunta divide las opciones en dos mitades con la misma probabilidad. En el siguiente nivel ya llegamos a una división del 35%-15% por un lado y a otra del 25%-25% por el otro, etc…

En definitiva, la cosa queda como:

0,35×2 + 0,25×2 + 0,12×3 + 0,10×4 + 0,08×4 + 0,06×4 + 0,03×3 + 0,01×4 = 2,65

Así que, con este método usamos 2,65 preguntas de media que es una mejora de más del 6% sobre el anterior y de casi el 12% sobre el primero que vimos.

Además, como el método depende de la distribución de probabilidades seguramente se adaptará bien al caso equiprobable. De hecho se adapta tan y tan bien, que en el caso equiprobable da como resultado las mismas preguntas que el primer método (que ya hemos dicho que es el que mejor funciona en ese caso).

BOLAEXTRA: ¿Pero podemos hacerlo mejor? No se pierdan el próximo capítulo.

Escrito en 10/12/08 09:07 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

buen articulo, pero si es posible conseguir la otra parte.

José A. Concepción B | 18/10/11 04:03 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)