Distanza di Hamming

Data 1999 08 27, ritoccato il 2003 01 18.

È un concetto semplice, ma con molte applicazioni e molti collegamenti con altri concetti.
Si noti che le formule di questo articolo sono visualizzabili bene solo su Internet Explorer (e sfortunatamente non su Mozilla).
 

Punto di vista matematico - geometrico

Nella figura sotto vediamo un insieme di punti che formano il cubo di Hamming quadrimensionale. In generale lo spazio di Hamming n-dimensionale è l'insieme di vettori n-dimensionali le cui componenti sono ristrette ai soli valori ±1 o {0,1}. Questo spazio ha 2n punti, tutti equidistanti dall'origine dello spazio euclideo.

Il cubo di Hamming (a quattro dimensioni) nello spazio tridimensionale.

Questo insieme di vettori lo si può immaginare anche indipendente, e non solo come sottoinsieme dello spazio euclideo, per cui tale insieme induce una geometria discreta, (cioè definita in uno spazio con un numero finito di elementi), detta di Hamming.

Esistono molte differenti misure di distanza, tra due vettori o scalari. In generale si definisce distanza d(x,y) tra x e y se d rispetta le seguenti tre proprietà:

1) d(x,y) ³ 0; d(x,y)=0 Ûx=y.
2) d(x,y) = d(y,x).
3) " z Î R, d(x,y) £ d(x,z) + d(z,y).    (disuguaglianza triangolare)

Anche nella geometria di Hamming può essere definita una metrica e una distanza, che si chiama distanza di Hamming. La definirò sfruttando le sue relazioni con quella nello spazio euclideo.

    Siano x = (x1, x2,. . . , xn)t e y = (y1, y2,. . . , yn)t due vettori nello spazio euclideo n-dimensionale soggetti alla restrizione che "i  xi , yi Î {±1}, così che x e y siano anche vettori nello spazio di Hamming a n dimensioni. La distanza euclidea tra i punti finali dei due vettori é:
 
d = Ö`((x1 - y1)2 + (x2 - y2)2 + ... + (xn- yn)2)
 (1.1)
dato che xi , yi Î {±1}, allora (xi - yi)2Î {0,4}: 
Equazione 1.2
 (1.2)
Quindi la distanza euclidea può essere riscritta come:
  
d = Ö`4(# componenti differenti tra x e y)
 (1.3)
Si definisce la distanza di Hamming come:
  
h = # componenti differenti tra x e y
 (1.4)
Per cui, la distanza di Hamming è legata alla distanza euclidea come:
  
d = 2Ö`h
 (1.5)

Punto di vista della teoria dell'informazione e trasmissione

Per cui la distanza di Hamming tra due parole binarie della stessa lunghezza è il numero delle posizioni di cifre (cioè coordinate) nelle quali le cifre corrispondenti di due parole binarie della stessa lunghezza differiscono. Ad esempio la distanza di Hamming tra 1011101 e 1001001 è due. Si noti che il concetto può essere esteso ad altri sistemi di notazione. In generale se si comparano due liste ordinate di oggetti, la distanza di Hamming tra le due è il numero di oggetti che non concidono. Ad esempio la distanza di Hamming tra 2143896 e 2233796 è tre (solo tre simboli differiscono), e tra "gelato" e "rosata" è quattro. La distanza di Hamming così generalizzata è detta anche distanza di segnale (signal distance).
    Questa distanza è applicabile ad ogni informazione codificata, ed è una metrica comparativa veramente semplice, spesso più utile della distanza Manhattan (detta anche ad isolati) definita come la somma dei valori assoluti delle distanza lungo gli assi, o della distanza euclidea.

Codifica di canale

[Questa parte è stata copiata da un articolo trovato sul Web.]

The task of source coding is to represent the source information with the minimum of symbols. When a code is transmitted over a channel in the presence of noise, errors will occur. The task of channel coding is to represent the source information in a manner that minimises the error probability in decoding.
    It is apparent that channel coding requires the use of redundancy. If all possible outputs of the channel correspond uniquely to a source input, there is no possibility of detecting errors in the transmission. To detect, and possibly correct errors, the channel code sequence must be longer than the source sequence. The rate R of a channel code is the average ratio of the source sequence length to the channel code length. Thus, R < 1.
    A good channel code is designed so that, if a few errors occur in transmission, the output can still be identified with the correct input. This is possible because although incorrect, the output is sufficiently similar to the input to be recognisable. The idea of similarity is made more firm by the use of the Hamming distance. Suppose the code x is transmitted over the channel. Due to errors, y is received. The decoder will assign to y the code x that minimises the Hamming distance between x and y. For example, consider the codewords: 

    a    10000
    b    01100
    c    10011
If the transmitter sends 10000 but there is a single bit error and the receiver gets 10001, it can be seen that the "nearest" codeword is in fact 10000 and so the correct codeword is found.
    It can be shown that to detect n bit errors, a coding scheme requires the use of codewords (Ci and Cj) with a Hamming distance of at least n + 1.

It can also be shown that to correct n bit errors requires a coding scheme with at least a Hamming distnace of 2n + 1 between the codewords.

By designing a good code, we try to ensure that the Hamming distance between possible codewords x is larger than the Hamming distance arising from errors.

Spero che questa parte sia risultata chiara. In caso contario si facciano delle prove con carta e lapis per convincersi di ciò.

A covering code in a Hamming space is a set of codewords with the property that any word in the space is within a specified Hamming distance, the covering radius, from at least one codeword.

È un problema generalmente molto difficile da risolvere. Come si è dettto questo problema nasce nel cercare di trasmettere in maniera affidabile un messaggio attraverso un canale, ad esempio un cavo elettrico, che è soggetto a rumore. Nel cavo i simboli 0 e 1 sono codificati con impulsi elettrici, ad esempio con -5 e 5 volt, o con 0 e 2 volt. Questo problema ha forte correlazione col problema dell'impaccamento più denso possibile di sfere in spazi n-dimensionali.
 

Applicazione alla genetica e agli AG

Per questa parte mi inspiro al saggio "Gradini verso la vita", di Manfred Eigen, Biblioteca Scientifica Adelphi, scheda 12 da p. 172.

Il concetto di spazio delle sequenze

Per rappresentare le sequenze di basi serve uno spazio opportuno in modo che sequenze simili corrispondano a punti dello spazio pure vicini, e questo non solo in relazione ad una data sequanza (come quella del tipo selvatico), ma anche le reciproche distanze tra tutti i mutanti. Le soluzioni piane così sono inutilizzabili, occorre uno spazio a molte dimensioni. Si utilizza così uno spazio di Hamming, o suoi derivati.
    In tale spazio, che può essere associato a un sottoinsieme dei punti dello spazio euclieo a n dimensioni, il volume é enorme, ad esempio una stringa binaria lunga solo 360 posizioni può essere messa in corrispondenza biunivoca con tutti gli atomi che possono entrare nel nostro universo. Ma in tale spazio discreto le distanze sono molto piccole, infatti sono sempre minori od uguali ad n. (In un cubo euclideo a n dimensioni si può invece far entrare una "iper-assicella" arbitrariamente lunga al crescere di n, infatti la diagonale di un ipercubo é la radice ennesima del numero di dimensioni, la quale é una funzione monotona crescente. In una ipersfera le cose vanno diversamente al crescere del numero di dimensioni, infatti oltre un certo punto il volume di una ipersfera comincia a calare al crescere del numero di dimensioni).
    La distanza di mutazione è la distanza di Hamming stessa tra due sequanze. Ma gli acidi nucleici possiedono quattro classi di simboli (cardinalità alfabeto = 4), per cui come si può raffigurare uno spazio del genere? La cosa migliore pare essere dividere questi quattro lettere in due classi, ad esempio Y e R. Allora data una sequenza lunga n di basi si può costruire uno spazio binario (di Hamming) a n dimensioni, ai cui vertici stanno le combinazioni di Y e R. Poi ad ogniuno di questi vertici si può associare un sottospazio di Hamming con la stessa cardinalità n.

Il concetto di distanza di Hamming è così molto utile, quasi indispensabile, sia in genetica che per gli AG, che ne sono una sua astrazione. Anche se il concetto é semplice, si é visto che l'applicazione può non esserlo.
    Di sotto riporto un mio utilizzo di tale concetto per fare misurazioni e grafici in una simulzione di selezione ottenuta con un LLGA (Linkage Learning GA, un algoritmo genetico sofisticato, di seconda generazione). Il problema da risolvere era composto dalla giustapposizione di cinque problemi percettivi (se chi legge non capisce tutto quello che dico, non importa, non sono i dettagli che voglio mostrare qui). Questi sono i parametri della simulazione ed i grafici ottenuti:
 

Simulazione con LLAG:
Popolazione = 300
# problemi percettivi = 5
# geni = # geni problema * 6
Prob. mutazione gene = 0.005
Prob. innesti = 0.75
Pressione selettiva = 2.5

Distribuzione di Hamming popolazione


Densità fitness popolazione (100 bins)

Entrambi i grafici hanno sull'asse orizzontale il numero di generazioni (cioè il tempo evolutivo), e codificano con punti più chiari i valori più elevati.
    Il primo grafico riporta sull'asse verticale la distanza di hamming media tra due genomi qualsiasi della popolazione, per ogni data generazione. Il secondo grafico mostra l'istogramma di densità di fitness della popolazione, per ogni data generazione.
    Il primo grafico mostra che inizialmente la popolazione é uniforme, cioè ha una distribuzione di hamming approssimativamente gaussiana, infatti la popolazione é generata con geni casuali ed indipendenti. Poi la popolazione si divide in due, ciascuna delle quali insegue in massimo locale di fitness. Si noti anche la forte concentrazione che si ha a circa il 20% di tutto il tempo della simulazione.
    Così la distanza di Hamming può essere usata per misurare la diversità all'interno di una popolazione (é solo una delle tante misure, c'é ad esempio l'entropia di Shannon, quella di Kolmogorov, ecc).

Lo spazio di Hamming può essere utilizzato come luogo in cui piazare il "paesaggio adattativo", invece del piano collinoso bidimensionale immerso nello spazio 3D, come lo si immagina di solito. Le sequnze di una popolazione si possono pensare come particelle che si muovono in qusto spazio, ma non sono distribuite unformemente, ma invece sono di solito concentrate attorno a pochi punti, i massimi locali di fitness finora trovati (la dinamica di tali punti é stata studiata da Eigen nel suo concetto di Quasispecie). Il paesaggio adattativo é un concetto euristico che é stato più volte modificato, ed alcuni si sono chiesti se sia utile modificarlo anche per rappresentare i particolari operatori genetici di cui la popolazione dispone per spostarsi nello spazio genomico. Per altre informazioni vedi la filata di comenti sul  Digest sugli AG, tratto dal Newsgroup relativo, a partire dal 28 Mar 1994.

Un'ultima nota. Nello spazio di Hamming come abbiamo detto le distanze sono brevi, e a ciascun punto sono vicini moltissimi altri punti (pari al numero di dimensioni), per cui dato un genoma, ogni altro non é molto lontano, per cui la probabilità di trovare una via che conduce al massimo (locale o assoluto) é piuttosto alta. Questo concetto, sviluppato e formalizzato, spiega il motivo per cui le ricerche in spazi discreti (ad esempio tramite AG) conviene farle quasi sempre utilizzando alfabeti di cardinalità minore, possibilmente due (binari). E anche l'utilità di una codifica con codici di Gray.