Arboricultura: parte 1

Leí algo que había leído hace como un millón de años: los arboles de Huffman. La pregunta que responde es simple: dado un texto formado por símbolos, ¿cual es la forma de codificar cada símbolo para minimizar el tamaño final del texto codificado? Para responder esto, se arma un árbol binario, de abajo para arriba. Pensando en los tipos de árboles que se pueden generar, me intrigó uno en particular: Desde la raíz para abajo, todos los nodos tienen: una hoja y una bifurcación. (mas abajo hay dibujitos donde queda claro). Como se genera este tipo de arboles? Si $\left\vert{\text{simbolo}_i}\right\vert > \sum_{j > i}\left\vert{\text{simbolo}_j}\right\vert$, entonces vamos a generar ese tipo de árbol. En particular, si  $\left\vert{\text{simbolo}_i}\right\vert = 2^{n-i}$, vamos a estar observando ese tipo de árbol. O, si vemos ese tipo de árbol, podemos hacer una transformación a un texto donde los símbolos tienen esta relación de ocurrencia: existe una ley de potencia detrás. Entonces, refinando la pregunta: sirve analizar la topología del árbol de Huffman para detectar leyes de potencia? Existe la definición de distribuciones Fat-tailed , que no es la misma que Heavy-tailed. El tema es que esta definición pide que exista una ley de potencia en la cola de la distribución. No hace falta que sea en toda la distribución. Entonces, podremos detectar este tipo de distribuciones usando los árboles? No lo sé, pero creo que sí :)

Para probarlo hice lo siguiente:

• generé muestras de tamaño $n = 100000$ de varias distribuciones. 
• de cada distribución tomé el histograma usando nBins ($\approx 1000$ )
• Usando este histograma armé el árbol de Huffman, pero solo tomando los bins con al menos una ocurrencia

Existen dos casos patológicos: la (predecible) uniforme, mostrando un árbol binario perfecto y la distribución de plank, que es un perfecto ejemplo del tipo de árbol que quería encontrar.

 

(para la uniforme utilicé solamente 10 bins porque de otra forma necesitaba hacer un gran zoom para notar la estructura).

Las distribuciones Heavy tailed muestran la estructura similar a la de Plank (sin ser tan extremo), pero ademas, hay distribuciones que tienen (en sus colas) una estructura similar a la de Plank. Dos casos que me llamaron la atención son: la Geometrica y la Poisson

Posiblemente esto esta relacionado con lo que dice (not-so)weak-pedia:

"Fat tail distributions have power law decay in the tail of the distribution, but do not necessarily follow a power law everywhere"

Puede ser que sean solo propiedades de muestra finita.

Ahora queda esta pregunta: ¿como detectar numéricamente esta estructura analizando el grafo? Sería agradable encontrar un estadístico (una variable aleatoria con una distribución de probabilidad) sobre la cual hacer test de hipótesis. No encontré nada de eso.
Probé varias medidas, pero ninguna me convence. Las que pongo acá son las siguientes:

• el número de Strahler: mide la complejidad de las ramas. Los resultados son interesantes. Va de $1$ a $\lceil\log_2 \text{nBins}\rceil$. La uniforme tiene el número mas alto
• Bifurcation Ratio (bf): En teoría hay un Teorema Central del Limite sober este estadistico y arboles aleatorios, pero los resultados no fueron para nada buenos
• $\psi$: Es el promedio de la distancia de los leafs al root dividido por $\lceil\log_2 \text{nBins}\rceil$ (la cantidad de bits necesaria para representar a los leafs)

resultado para nBins = 1025

*** normal ***

bf ratio: 1.30154390424

strahler: 9

distance (psi): 1.222749 upperBound: 41.100122

*** uniform ***

bf ratio: 1.82279829545

strahler: 11

distance (psi): 1.004502 upperBound: 47.727359

*** weibull ***

bf ratio: 1.33107640276

strahler: 9

distance (psi): 1.233694 upperBound: 41.600120

*** Heavyweibull ***

bf ratio: 1.25439814815

strahler: 6

distance (psi): 1.665082 upperBound: 11.500679

*** pareto ***

bf ratio: 1.2426702689

strahler: 6

distance (psi): 1.843468 upperBound: 13.875563

*** lognormal ***

bf ratio: 1.26271929806

strahler: 6

distance (psi): 1.539683 upperBound: 19.111435

*** lognormalHeavy ***

bf ratio: 1.25248954477

strahler: 5

distance (psi): 1.705980 upperBound: 6.144518

*** vonmises ***

bf ratio: 1.34570436657

strahler: 9

distance (psi): 1.279363 upperBound: 39.300127

*** expovariate ***

bf ratio: 1.32432288929

strahler: 8

distance (psi): 1.311187 upperBound: 36.700136

*** zipf ***

bf ratio: 1.16205357143

strahler: 4

distance (psi): 2.105769 upperBound: 4.336538

*** planck ***

bf ratio: 1.09090909091

strahler: 2

distance (psi): 1.750000 upperBound: 1.522727

*** burr ***

bf ratio: 1.22805961483

strahler: 6

distance (psi): 1.878981 upperBound: 9.875796

*** cauchy ***

bf ratio: 1.29671439671

strahler: 5

distance (psi): 1.650579 upperBound: 5.287645

*** levy ***

bf ratio: 1.25

strahler: 3

distance (psi): 1.250000 upperBound: 1.277778

*** geom ***

bf ratio: 1.125

strahler: 3

distance (psi): 1.965517 upperBound: 3.006897

*** t ***

bf ratio: 1.25474980384

strahler: 6

distance (psi): 1.484777 upperBound: 15.667062

*** poisson ***

bf ratio: 1.11538461538

strahler: 3

distance (psi): 1.487500 upperBound: 1.612500

*** gamma ***

bf ratio: 1.31289744848

strahler: 8

distance (psi): 1.257250 upperBound: 33.500149

Acá va el resto de los grafos

El proximo post, va a compartir con este solo las hormigas (espero)

[EX-POST: como los árboles de Huffman están relacionados con la entropía, y esta es una propiedad de las distribuciones, puede ocurrir que la estructura sea un invariante de las distribuciones. Esto sería muy bueno. Por ejemplo, se podría determinar la distribución (o familia de) mirando la estructura. Supongo que hay que hacer bastante trabajo para demostrar esto]

apéndice

parámetros de las funciones

  normal(0, 1), uniform(0, 1) weibull(1, 1.7) weibull(1, 0.3) (heavy) pareto(2.5)  lognormvariate(0, 1) lognormvariate(0, 2.5)(heavy) vonmises(0, 4) exponential(4) zipf(3) planck(1) burr(2, 1) cauchy() levy(c=4) geom(0.3) t(4) poisson(4) gamma(2, 2)