Distribuzioni

Questa settimana sono successe un po’ di cose. Non sono riuscito a fare il post ieri sera per svariate ragioni, tra cui il fatto che sono arrivato lungo e non ho fatto in tempo a preparare quello che mi serviva e come lo volevo. Oggi è andata un po’ meglio, e uno dei motivi è che il fine settimana appena trascorso è stato esteso di due giorni per i festeggiamenti del giubileo di diamante della regina. Sabato se n’è andata alle corse dei cavalli, ieri ha partecipato alla regata sul Tamigi con mille barche al seguito, questa sera ci sarà un concerto di fronte a Buckingham Palace, e quel poveraccio del duca di Edimburgo è finito in ospedale per una bazzeccola—che però a 90 anni non si sa mai—e quindi si perderà sia il concerto che la chiusura delle celebrazioni. Sarebbe stato carino ieri essere andati a Londra a vedere le barche—c’era una gondola in assetto da regata—ma avrei dovuto prepararmi per tempo per non spendere un capitale di treni, e già la settimana scorsa si sapeva che avrebbe fatto brutto. Vabè, insomma: avevo altre cose da fare, articoli da leggere, e quindi sono sopravvissuto lo stesso alla noia.

La seconda cosa che è successa è che ho deciso di dare definitivo respiro al vecchio e fedele portatile, sgravandolo dal peso di Gentoo anche se col Mac comunque riuscivo ad alleviargli le pene via distcc. Il problema è che c’è stato un inghippo sulla macchina virtuale che usavo a tale scopo e sulla quale avevo installato Gentoo, e quindi mi è sembrato un buon momento per alzare bandiera bianca.

Detto fatto ho valutato offline alcune distribuzioni, tra le quali Arch sembrava la migliore: binaria ma con sorgenti compilabili via package manager, rolling release, community attiva e con un approccio minimalista ed elegante che non guasta mai. Scaricata e installata, le rogne sono iniziate subito. Ora, anche Gentoo ha avuto un momentaccio in cui il CD di installazione aveva più bachi che soluzioni, però non è che se pacman [1] ti installa il db dei pacchetti con i permessi sbagliati e, nel mentre che forzi il di lui medesimo aggiornamento, esce un conflitto la cui risoluzione—stando al forum ufficiale—è cancellare una fila di file in /usr/bin e /usr/sbin nonché /etc/mtab [2] come se niente fosse. Mettici poi che all’installazione di KDE non fa seguito l’installazione di Xorg [3] e non fa seguito nemmeno all’installazione dei driver della scheda video [4] ed evidentemente non fa seguito nemmeno alla sua propria installazione dato che ho dovuto installare esplicitamente alcuni pacchetti per avere il server finalmente installato ed avviabile.

Insomma, nel frattempo la ISO di Ubuntu era scesa e, siccome era un po’ che la curiosità mi perseguitava, ho deciso di provarci. Confesso che la cosa che mi ha trascinato a schiacciare il bottone “SÌ, INSTALLAMI TUTTO!” è stato il fatto che la scheda wireless ha funzionato dal primo istante senza (troppo) singhiozzo, mentre in anni di Gentoo si scollegava e ricollegava senza apparente motivo con intervalli tra i 2 secondi e i 5 minuti. Al confronto le tre ore abbondanti prima di notare il primo reset sono state un sensibile miglioramento [5]. A conti fatti mi sa che provo questa Ubuntu per un po’ e poi vediamo.

La terza cosa che è successa è che ho smanacciato un po’ il codice che avevo messo insieme per generare numeri casuali con iOS e finalmente sono riuscito ad ottenere una distribuzione decentemente uniforme [6].

Istogramma del dataset con 64 bin (PNG, 560x420, 8.7 kB)

A questo punto però la tentazione è di volere numeri casuali distribuiti diversamente. Per esempio, vediamo chi sa dirmi cosa c’è disegnato in questo grafico [7]:

PNG, 560x420, 17 kB

Ebbene sì, è il celeberrimo grafico a campana, per gli amici la distribuzione Normale, per gli amici intimi la distribuzione di Gauss:

$$ f(x;\mu,\sigma^2) = \frac{1}{\sigma\sqrt{2\pi}} e^{ -\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^2 } $$

Normalmente per passare dalla distribuzione uniforme ad un’altra, la strada più semplice sarebbe calcolare il quantile della distribuzione che si vuole ottenere e passarci attraverso i numeri distribuiti uniformemente. Purtroppo calcolare questa cosa non è affatto semplice, ma c’è un trucco che può cavarci d’impiccio, anche se non con tutta l’eleganza matematica dell’approccio precedente. Si tratta di convolvere i numeri casuali con la distribuzione desiderata, che detta così non è che sembri molto più semplice.

La trasformata di Fourier è uno dei più begli oggetti matematici a disposizione di chi tratta segnali [8] e ha una serie di proprietà che non starò qua ad elencare perché se le capiste le avreste studiate e quindi non servirebbe elencarle, e se non avete studiato matematica o ingegneria è inutile che stia qua a spiegarvele perché non le capireste.

Comunque una di queste proprietà è che trasforma l’operazione di convoluzione in un più semplice prodotto. Una volta calcolata la trasformata (discreta) del segnale in questione [9] è sufficiente effettuare il prodotto per componenti del vettore con la trasformata col vettore con la distribuzione [10] e poi calcolare la trasformata inversa del risultato. Qualcuno ha detto DSP? Esattamente. Qualcun altro ha detto “ma così sono un sacco di moltiplicazioni senza contare la trasformata che è difficilissima”? Fortunatamente l’ingegno umano, sotto opportune ipotesi, ci fornisce la tecnologia per ridurre drasticamente i tempi, e così vi ho rivelato che le trasformate di Fourier le fa tutti i giorni il vostro lettore MP3, non solo per riprodurre la musica in sè ma anche per applicarci tutti quegli equalizzatori a cui siamo costretti da produttori incompetenti. Vabbè, fine della lamentela.

Gli istogrammi del segnale una volta passato attraverso le tre distribuzioni (PNG, 560x420, 17 kB)

C’è qualcosa che non mi convince nell’istogramma rosso: se qualcuno può offrire spiegazioni sono le benvenute. Comunque, è ora di fare l’antitrasformata, no? Ebbene.

Bon, direi che per questa settimana la missione è compiuta.

  1. No, non il gioco, PACkage MANager è il fantasioso nome del gestore dei pacchetti di Arch.
  2. Mi sto ancora chiedendo perché un pacchetto debba confliggere con un file creato dinamicamente all’avvio…
  3. Mi fanno notare dalla regia che è concettualmente giusto che un DE non dipenda da Xorg, ma è quantomeno bizzarro che nessuno lo spieghi dato che ormai è una di quelle cose che più o meno tutti si aspettano.
  4. Questo è un po’ meno giustificabile…
  5. E comunque un campanello d’allarme che mi dice che alla fine questa ipw2200 non è proprio così spettacolare come ci hanno dato a intendere.
  6. Tanto per chiudere il caso: gli estremi li genera, solo che è estremamente improbabile… d’altro canto stiamo parlando di una probabilità su $2^{30}$.
  7. Lo ammetto, questo fatto dei grafici mi sta prendendo un po’ la mano.
  8. Una variabile aleatoria è un segnale, e campionarla produce un segnale discreto che, guardacaso, è proprio quello che abbiamo qui. Ok, no, qui abbiamo un segnale digitale, che è un particolare segnale discreto, ma non sottilizziamo.
  9. Occhio che questo dataset è compreso tra 0 e 1, quello che ho usato per fare i disegni è compreso tra -0.5 e 0.5, ma la trasformazione è banale e se non la sapete fare francamente come avete fatto ad arrivare fino a qui?
  10. Non serve dire che devono avere lo stesso numero di componenti, vero?

Commenti

gianduja » 

Io sapevo solo il metodo del quantile, pur non chiamandolo così, bensì “coso con tanti integrali e inversi di funzioni che proprio nun poi capi’ e funziona davvero solo per le rette”.

Bene. Quindi non so che c’entrino la convoluzione e Fourier. Solo che quella gaussiana rossa è brutta forte.

(cmq: non è che c’entra la frequenza di campionamento o l’analogo di questo concetto nel caso che vuoi analizzare tu? E’ passato del tempo e sono cose che ho capito solo superficialmente, però boh :P)

Ma per la distribuzione normale, che è un caso notevole, mi suggeriscono ci sia un modo relativamente semplice di costruirla a partire da una distribuzione uniforme: solo che si va in 2d. BTW, non so se hai mai visto la dimostrazione che l’integrale della gaussiana è 1; il concetto di salire in 2d perché poi della roba si semplifica si utilizza anche lì.

http://www.brighton-webs.co.uk/distributions/normal.htm

Non ho capito in che intervallo possono variare i due numeri tirati fuori dall’uniforme, ma suppongo siano i soliti 0 e 1.

E poi con una bella affinità si trasforma questa normale in una con la varianza e la media che ci aggradano di più.

Comunque il sito riporta anche altre distribuzioni, casomai ti servissero.

Ah, e non vorrei sbagliarmi ma questa roba c’è pure in Numerical Recipes (in C).

Andrea Franceschini » 

Sì, poesse che c’entri la frequenza di campionamento (o analogo concetto che poi in realtà è la dimensione della trasformata) perché mi è parso di notare che la cosa succeda quando le code escono dagli estremi del grafico (aka la dimensione della trasformata) con valori non proprio prossimi a zero.

In realtà il quantile è probabilmente il metodo più efficiente, è che coinvolge carta, penna e sudore della fronte e volevo evitarlo :P Se però vuoi farmi tu i conti, per me va bene :)

gianduja » 

Scusa ma perché non adottare quel metodo che ti ho linkato? Mi sembra piuttosto semplice.

Per il quantile devi conoscere, a naso, l’inversa di erf(x) o erfc(x) (non mi ricordo mai qual è quella giusta, ma tanto penso che bisogna in ogni modo comporla con delle affinità e quindi queste due sono “la stessa cosa”). Se hai qualche libreria che te la calcola senza bestemmiare, ha senso, se no no. Per converso l’altra vuole logaritmo, seno, coseno e radice quadrata, che saranno fastidiosi ma sono certo che li hai a disposizione.

(Ah e probabilmente anche erf(x) coinvolge pigrechi e radici quadrate, mica penserai che.)

Andrea Franceschini » 

Il metodo linkato è Box-Muller di cui ho ricordi vaghi, devo riguardarmelo. Il fatto è che non so quanto bene funzionino le operazioni trigonometriche sull’ARM (mentre su Intel-like ci sono specifiche istruzioni parallele, tipo fsincos che addirittura ti permetterebbe di calcolare entrambi i valori allo stesso tempo). Dovrò investigare.

L’altra ragione per non usare Box-Muller (o ogni altro metodo specializzato) è che volevo cercare un metodo generale per ottenere numeri in qualsiasi distribuzione, e questo della trasformata di Fourier (che poi altro non è che una specie di filtraggio spettrale se così si può dire dato che non siamo strettamente in un dominio di frequenze vero e proprio) sembra il più flessibile ed efficiente.

gianduja » 

Eh, qualsiasi distribuzione, ‘na parola. Anche volendo adottare Fourier, temo ricapiterebbero tanti casi analoghi a quello della tua normale spiaccicata. A quanto pare, quello funziona bene quando hai una distribuzione a valori limitati in un intervallo: ma ce ne sono tante che non lo sono. Se riesci ogni volta a trovare un dominio limitato al di fuori del quale la distribuzione ha valori trascurabili, forse neanche trovi molta immondizia. Prova, prova molto :P

GiRa » 

Uno dei post più belli e ben scritti degli ultimi tempi.

Complimentissimi.

PS: però le note a pié di pagina non le riesco a digerire ancora…

Andrea Franceschini » 

Grazie per i complimentoni :)

Circa le note, un po’ ti capisco: quando iniziano ad essere troppe infastidiscono anche me, però spesso è difficile inserirle nel discorso senza divagare troppo.

Rispondi