[Teoria] Ruolo della distribuzione geometrica in Teoria dell'Informazione

[Ambaraba]

Ciao a tutte e a tutti, di recente mi sono imbattuto in una serie di articoli nei quali concetti presi dalla teoria dell'informazione sono applicati allo studio del linguaggio umano.

L'autore degli articoli afferma che "power laws are not the most efficient distributions for codewords in variable length codes" (cfr. [1], metà di pagina 5). A suo dire la distribuzione ottimale sarebbe invece quella geometrica in quanto "geometric (exponential) distributions enable the average information in a set of codewords to be minimized (such that we ought to expect an optimal communicative code to employ geometric rather than Zipfean distributions)" (cfr. [1], inizio di pagina 20).

Lo stesso autore, in un altro articolo, torna ad affermare che "Information theory [...] shows that the most efficient way of distributing codewords [...] is by distributing their probabilities geometrically" (cfr. [2], inizio di pagina 1001).

Queste affermazioni purtroppo non sono motivate con dimostrazioni formali e l'unico riferimento fornito è [3], in cui sostanzialmente si afferma che data una sorgente i cui elementi sono distribuiti secondo una geometrica è possibile ottenere una codifica ottimale tramite Golomb o Huffman. Questo però non giustifica le affermazioni dell'autore che sembra identificare la geometrica come la migliore distribuzione in assoluto.

Sono io che mi sto perdendo qualcosa? È possibile giustificare e dimostrare queste affermazioni?

[1] Ramscar, M. (2019). Source codes in human communication.
[2] Ramscar, M. (2021). How children learn to communicate discriminatively.
[3] Gallager, R., & Van Voorhis, D. (1975). Optimal source codes for geometrically distributed integer alphabets (corresp.). IEEE Transactions on Information theory, 21(2), 228-230.

[apatriarca]

Non sono un esperto del settore (anzi probabilmente ne sai più di me), ma forse la distribuzione geometrica è l'unica per cui si riesce a ottenere una codifica ottimale. Ti consiglio di chiedere a un professore/ricercatore del campo o addirittura all'autore dell'articolo.

[Ambaraba]

Non sono un esperto del settore (anzi probabilmente ne sai più di me), ma forse la distribuzione geometrica è l'unica per cui si riesce a ottenere una codifica ottimale. Ti consiglio di chiedere a un professore/ricercatore del campo o addirittura all'autore dell'articolo.

Ciao, grazie per essere intervenuto! Ho provato a contattare l'autore più di una volta. Purtroppo però la spiegazione che mi ha dato non è stata molto convincente. Come accennavo nel messaggio iniziale non ha saputo motivare "formalmente" le sue affermazioni e l'unico riferimento che mi ha dato è l'articolo di Gallager e Van Voorhis.

Non esagero nel dire che sono ormai settimane che cerco una dimostrazione del fatto che la geometrica sia la distribuzione che permette di ottenere una codifica ottimale, ma finora nulla.

Tornando all'articolo che mi ha segnalato, nelle prime righe si legge quanto segue:

"we show how the Huffman algorithm can be used indirectly to prove the optimality of a code for an infinite alphabet if one can guess what the code should be first. Naturally it is not always easy to guess the structure of an optimal code, but if the structure is simple enough, and if one starts with the simplest cases, guessing often works. The particular case that we deal with here is that of the non-negative integers with a geometric probability assignment".

A me sembra che gli autori non stiano dicendo che la distribuzione geometrica è quella che in assoluto permette di ottenere una codifica ottimale. Mi pare piuttosto che abbiano preso la distribuzione geometrica come un esempio per motivare quanto affermato nelle righe precedenti. Con un po' di fortuna magari un professore/ricercatore del campo passerà da queste parti

[apatriarca]

Non ho modo di accedere all'articolo che hai postato per cui ho qualche difficoltà a comprendere esattamente di cosa stia parlando. Quella frase sembra tuttavia suggerire che, nonostante l'obiettivo sia quello di mostrare come usare l'algoritmo di Huffman per provare l'ottimalità in casi generali, il metodo viene applicato con successo nel mostrare che i numeri non-negativi distribuiti secondo una distribuzione geometrica sono ottimali.

Non credo il risultato sia tuttavia necessariamente presentato per la prima volta in quell'articolo. Cercando online ho trovato che l'algoritmo di Huffman è il più corto tra quelli che rappresentano ogni simbolo separatamente e che è ottimale se i simboli seguono una distribuzione geometrica. Supponendo di avere quindi una codifica che rappresenta ogni simbolo separatamente, la distribuzione che permette codici più corti e ottimali è quella in cui la distribuzione è geometrica. Tuttavia il linguaggio naturale non segue una tale codifica ottimale e non mi è quindi chiaro dove voglia arrivare con questo discorso.

[Ambaraba]

Grazie di nuovo per essere intervenuto!

Tuttavia il linguaggio naturale non segue una tale codifica ottimale e non mi è quindi chiaro dove voglia arrivare con questo discorso.

Il discorso ha senso proprio perché ci sono evidenze empiriche che dimostrano come il linguaggio umano presenti, quantomeno all'interno di determinati campi semantici, una distribuzione geometrica. Ad esempio, prendendo un corpus e campionando parole dal campo semantico degli ortaggi, giusto per fare un esempio, si nota come la distribuzione dei termini sia geometrica. Lo stesso accade per altri campi semantici: termini legati alla famiglia, all'arredamento, al lavoro...
L'idea di questi articoli è perciò quella di suggerire che le regole alla base del linguaggio umano seguono un criterio di massima efficienza che può essere formalizzato ricorrendo alla teoria dell'informazione.

Non credo il risultato sia tuttavia necessariamente presentato per la prima volta in quell'articolo. Cercando online ho trovato che l'algoritmo di Huffman è il più corto tra quelli che rappresentano ogni simbolo separatamente e che è ottimale se i simboli seguono una distribuzione geometrica. Supponendo di avere quindi una codifica che rappresenta ogni simbolo separatamente, la distribuzione che permette codici più corti e ottimali è quella in cui la distribuzione è geometrica.

Ciò che intuitivamente fatico ad accettare è il fatto che l'autore affermi che la distribuzione geometrica è la migliore in assoluto, quantomeno nel caso di un supporto discreto infinito. Il fatto che l'algoritmo di Huffman garantisca la migliore codifica possibile data una sorgente con distribuzione geometrica, giustifica davvero la sua affermazione? Come posso essere sicuro che non esista una distribuzione migliore dato un altro algoritmo di codifica?

[apatriarca]

La mia interpretazione è che l'algoritmo di Huffman fornisce una codifica ottimale (che associa simboli a simboli*) per un dato alfabeto con date probabilità, ma che la lunghezza di tale codifica è ottimale solo nel caso in cui le probabilità siano distribuite secondo una distribuzione geometrica. Tuttavia si tratta di una idea che mi sono fatto basato su alcune letture sparse online e mancano dimostrazioni..

* Esistono modi di codificare l'informazione alternativi che ottengono compressioni maggiori.