24 Settembre 2007
The Gray Code
Non credo sia diventato famoso quanto il codice Da Vinci e non credo neppure che mai lo sarà. Ma sempre di un codice si tratta. E pure furbo. Il Gray Code, che prende il nome dal suo inventore Frank Gray, non è altro che una versione alternativa della codifica booleana tradizionale, aggiustata in maniera tale da far sì che due valori tra loro successivi possano variare al massimo di un bit.
Il tutto è più semplice da capire vedendo un esempio, piuttosto che cercando uno pseudo-formalismo matematico che notoriamente non è mai stato il mio forte. Ad esempio, per 3 bit succede questo:
Qual è il vantaggio di utilizzare una codifica di questo tipo al posto di quella booleana tradizionale? Beh, in ambito di Artificial Life questi vantaggi sono evidentissimi. Spesso, infatti, quando vi è la necessità di campionare lo spazio percettivo, possono sorgere problemi di vario genere.
Una rete neurale deve imparare a discriminare tra le varie possibili percezioni sensoriali ed adottare la risposta più appropriata in ciascuna circostanza. Immaginiamo ad esempio i miei aeroplanini, in grado di percepire in ogni momento l’angolo che li separa dal target. Se non si adottasse nessuna codifica particolare, ma ci si limitasse a normalizzare l’angolo (compreso tra 0 e 360°) in un intervallo più ristretto e quindi più adatto a fungere da input per un neurone artificiale (mettiamo ad esempio [0->1°]), succederebbe una cosa strana. Due angoli tecnicamente molto vicini tra loro, come potrebbero essere 359° e 2°, verrebbero codificati in maniera diametralmente opposta. Creando alla rete neurale notevoli difficoltà di apprendimento. Il comportamento, infatti, nei due casi dovrebbe essere del tutto simile (gli aeroplanini dovrebbero, in entrambi i casi, andare tendenzialmente dritti, virando di pochissimo in una direzione o nell’altra), ma l’input sarebbe rappresentato in maniera estremamente diversa. Le reti neurali sono solitamente in grado di riuscire a discriminare tra input non-perfetti come potrebbero essere questi, ma non si tratta di un compito semplice. Tra gli effetti collaterlai, il più rischioso è un notevole “raffreddamento” dell’efficacia training (o, in caso di evoluzione genetica, un più ampio numero di generazioni richieste).
L’alternativa è quella di utilizzare una codifica più intelligente. Nel mio caso, ho segmentato l’angolo in 8 intervalli di 45° ciascuno. Al primo, ]337.5;22.5°], ho assegnato la codifica 000; al secondo, ]22.5;67.5°], la codifica 001 e via di seguito, in senso orario, utilizzando la Gray Code di cui sopra. Ed i risultati sono, al momento, estremamente incorraggianti.
Comments(10)
mi hai fatto per un istante ricordare il professore di sistemi di terza superiore.
Il che non mi pare un complimento, dico bene?
no, era un severissimo vecchietto che ci rompeva il culo facendoci fare operazioni matematiche in binario, base 4,7,8 ed esadecimale. alla lavagna. durante le interrogazioni.
Perché non usare una codifica continua per una quantità continua ???
A me è sempre sembrato una forzatura inutile discretizzare quantità continue in intervalli arbitrari (ad esempio otto nel tuo caso)… anche se (purtroppo) lo fanno in molti.
La miglior cosa secondo me è usare una codifica circolare dell’angolo in modo continuo … ad esempio il seno. Ovviamente, il seno non fa bene perché discrimina solo meta del cerchio degli angoli. Ma esistono tante alternative. Una molto elegante che a me piace molto, è rappresentare l’angolo con l’esponente della sua rappresentazione esponenziale.
Davide: e mado, per due numeri…
SNVA200: l’esponente della sua rappresentazione esponenziale… uhm… sarebbe? :-p
Scusami… ho scritto una cosa complicata per dire intendere una cosa semplice
Il succo è che usi due neuroni che variano fra [-1:+1] ed in ingresso gli metti ad uno il seno(theta) e all’altro il coseno(theta).
Ottieni una codifica che non ha discontinuità… e che corrisponde alla rappresentazione sul piano immaginario dell’angolo.
Infatti, l’angolo può essere espresso con una funzione complessa, exp(t*i), che corrisponde a coseno(t)+i*seno(t).
Uhm, non mi e’ nuovo e infatti… Chi ha letto e trattato algebra booleana sa che questo sistema potrebbe tornare utile in molte occasioni. In ambito IA ho solo letto qualcosa e ad un livello appunto “letturiero”. In piu’ mi ricordo di vecchi esercizi a Reti Logiche. Dopo Shannon, molti si sono cimentati nelle aritmetiche e schemi di aritmetica piu’ disparati. Pero’ adesso, Fabio, sono curioso su come potresti e dove potresti applicare questa logica. Insomma, mi aspetto un seguito di questo post.
SVNA200: deciso, domani la provo. Confronto secco con le due codifiche che ho usato io (angolo segmentato in 8 spazi, codificati in maniera booleana “tradizionale” o con la Gray Code)… e che vinca il migliore!
Kiko: trovi la descrizione del progetto su cui sto lavorando qui. Domani conto di riuscire a finire anche la pagina con la descrizione del modello ed infilare i primi risultati.
l’ho sempre detto anch’io.
so che la discussione si è chiusa un po’ di tempo fa’ ma volevo chiedere in che modo si associa il codice Gray ai vettori coponenti un segnale che è stato modulato. Sto preparando un esame di trasmissione numerica e uno dei quesiti negli esercizi riguardanti le costellazioni è quello di scrivere il labeling di Gray ma non ho capito come…come al solito il mio docente mi ha detto che devo cercare di capirlo da sola…non so se sono stata chiara, ma se ne avete capito il senso vi prego aiutatemi, ho un materiale di studio abominevole!
grazie