Least Mean Square

I Least Mean Squares (LMS) sono una classe di algoritmi adattivi usati per imitare un filtro desiderato, cercando i coefficienti del filtro che producono il minimo errore quadratico medio (differenza tra il segnale vero e quello registrato). Si tratta di un metodo di discesa stocastica del gradiente nel senso che il filtro viene adattato solo in base all'errore al tempo presente. Fu inventato nel 1960 dal professor Bernard Widrow e il suo primo studente di dottorato, Ted Hoff, presso l'Università di Stanford.

Esempio

Per comprendere meglio l'algoritmo, consideriamo un semplice caso pratico, in cui l'algoritmo LMS è attualmente impiegato con successo: la cancellazione dell'eco acustico tra un altoparlante ed un microfono. Supponiamo che qualcuno stia parlando al microfono, un altoparlante riproduce la voce dell'oratore e degli altri suoni, in un ambiente chiuso. Se venissero riprodotti dall'altoparlante anche i suoni originati dall'altoparlante stesso, si innesterebbe un loop di guadagno che renderebbe instabile il sistema portando all'effetto Larsen con la comparsa di fischi e fastidiosi effetti sul suono. Durante il percorso tra l'altoparlante ed il microfono, il segnale sonoro viene riprodotto dall'altoparlante, che introduce le prime distorsioni (qui distorsioni è inteso come una qualsiasi alterazione del segnale, anche una equalizzazione, riverbero o cammini multipli) del segnale riprodotto, poi sarà riflesso dalle pareti dell'ambiente, che introduce ulteriore distorsione, l'eco, infine giunge al microfono che a sua volta sarà fonte di ulteriore distorsione, sia per l'inserzione fisica del microfono stesso che altera il campo sonoro, sia per l'equalizzazione introdotta; in definitiva, si può considerare una risposta impulsiva dell'ambiente, che porta dal segnale di ingresso, al segnale desiderato. Il segnale si dice desiderato perché in uscita dal filtro vorrei avere lo stesso segnale che ho in uscita dal microfono. Se il filtro adattativo riproduce esattamente la risposta impulsiva del sistema fisico, posso creare un segnale elettronico identico al segnale desiderato, la loro differenza permette di togliere dall'uscita del microfono la parte di segnale che proviene dagli altoparlanti.

Formalizzazione del problema

Sia y[n] l'uscita del filtro adattativo w quando in ingresso ho il segnale x, e sia h la risposta impulsiva complessiva del sistema e dell'ambiente. L'uscita desiderata o misurata d sarà data dalla convoluzione

$d[n]=x[n]*h[n],$

che confrontata con l'uscita stimata (y) del filtro adattativo w

$y[n]=x[n]*w[n],$

ci permette di definire l'errore e del filtro, banalmente, come la differenza tra i due segnali

$e[n]=d[n]-y[n]=d[n]-x[n]*w[n],$

in cui si è esplicitato solo il segnale stimato, poiché in generale d[n] è un segnale noto del sistema, ad esempio il segnale proveniente da un microfono.

L'algoritmo LMS ha il compito di stimare la risposta impulsiva h, e di ricrearne una sua replica w. L'algoritmo confronta il segnale desiderato $d=x*h$ con il segnale ottenuto dalla simulazione $y=x*w$, se questi segnali non sono uguali ho un segnale di errore e[n] non nullo, dato dalla loro differenza, con il quale posso costruire una funzione costo

Funzione costo

Gli algoritmi adattativi si possono classificare in base alla funzione costo J, che può essere di tipo deterministico, definita come Sum of Squared Error (SSE):

$J(w)=\sum {|e[n]|}^{2},$

o di tipo stocastico se la funzione costo è definita come Mean Square Error (MSE)

$J(w)=\sum E{\bigl \{}|e[n]|^{2}{\bigr \}},$

come nel caso dell'algoritmo LMS.

Minimizzare la funzione costo, vuol dire minimizzare la distanza tra il segnale desiderato ed il segnale stimato. È proprio dalla minimizzazione della funzione costo che si ricava l'algoritmo di aggiornamento dei coefficienti del filtro.

L'algoritmo LMS considera l'errore quadratico istantaneo $e^{2}[n]$ al posto della sua aspettazione. Per ciascuna iterazione calcolo l'errore in un istante n fissato che chiameremo k, per cui la funzione costo MSE si riduce ad una semplice

${\tilde {J}}(w)=e^{2}[k]$

stimata, come indicato dal simbolo di tilde sulla funzione J.

Algoritmo aggiornamento dei coefficienti

Mimizzando la funzione costo, minimizzo l'errore, quindi ottengo un filtro che approssima la risposta impulsiva dell'ambiente. La direzione verso il minimo si ottiene dal gradiente (cambiato di segno), mi sposto nella direzione indicata dal gradiente ad ogni iterazione, si ottiene così la funzione di aggiornamento dei coefficienti del filtro adattativo w all'iterazione k-esima

$w_{k}=w_{k-1}+{\frac {1}{2}}\mu {\bigl (}-\nabla {\tilde {J}}(w){\bigr )}.$

Calcolando il gradiente all'istante k-esimo, sostituendo alla funzione costo la sua definizione, si ottiene infine la funzione esplicita di aggiornamento dei coefficienti dell'algoritmo LMS:

$w_{k}=w_{k-1}+\mu e[k]x_{k}.$

Bibliografia

• Yiteng Huang, Jacob Benesty e Jingdong Chen - Acoustic MIMO signal processing, Springer 2006