Levenberg-Marquardt

Nelle sezioni precedenti gli algoritmi di risoluzione di sistemi non lineari sono stati divisi tra algoritmi di discesa del gradiente o algoritmi di Gauss-Newton. Per una lettura più approfondita consiglio (MBT04). Nei metodi Gauss-Newton quando $\mathbf{J}^{\top}\mathbf{J}$ è definita positiva il metodo può sempre indicare una direzione dove il costo diminuisce. Quando $\mathbf{J}^{\top}\mathbf{J}$ diventa singolare, il metodo Gauss-Newton diventa numericamente instabile.

La tecnica proposta da Levenberg-Marquardt cerca di lavorare nei punti di forza di Gauss-Newton e discesa del gradiente in modo da trarne vantaggio da entrambi.

L'algoritmo di Levenberg Marquardt (LM) è una tecnica di regressione iterativa ormai ritenuta standard per risolvere problemi non lineari multivariabili. Una ottima descrizione dell'algoritmo può essere trovata in (Lou05). L'algoritmo si può vedere come composto da una fase di discesa del gradiente, lenta ma che converge, seguita da un risolutore di tipo Gauss-Newton, più veloce.

L'algoritmo di Levenberg-Marquardt risolve invece una versione leggermente differente dell'equazione (3.45), caso particolare dell'equazione (3.35), conosciuta come augmented normal equations:

$$\mathbf{N} \delta_\beta = -\mathbf{J}_{r}^{\top} \mathbf{r}$$ (3.49)

dove $\mathbf{N} = \mathbf{H}_{S} + \mu \mathbf{I}$ con $\mu>0$ un fattore di attenuazione (damping factor): quando il fattore $\mu$ è elevato, la matrice $\mathbf{N}$ è pressoché diagonale e l'algoritmo si avvicina a un metodo di discesa del gradiente (steepest descent gradient), mentre quando il termine $\mu$ è vicino a zero, l'algoritmo approssima il metodo di Newton. Invece che una ricerca lungo una linea (line search), Levenberg-Marquardt è una tecnica che implementa il concetto di regione di confidenza (trust region).

Anche in Levenberg-Marquardt normalmente viene sfrutta l'approssimazione, vista già in Gauss-Newton, dell'Hessiana $\mathbf{H}_S(\boldsymbol\beta) \approx \mathbf{J}_{r}^{\top}\mathbf{J}_{r}$ limitatamente al caso in cui la loss-function è quadratica.

Come impostare e come modificare tra le iterazioni $\mu$ tuttavia è un problema lasciato al risolutore e diverse tecniche sono proposte in letteratura.

Una delle implementazioni più diffuse (Nie99) sceglie come $\mu_0$ un valore del tipo

$$\mu_0 = \tau \max \trace \mathbf{H}$$ (3.50)

con $\tau$ scelto liberamente dall'utente basandosi sulla propria fiducia rispetto al valore di $\boldsymbol\beta$. La modifica di $\mu$ tra le varie iterazioni viene gestita dal fattore di guadagno $\rho$ (gain ratio):

$$\rho = \frac{ S(\boldsymbol\beta) - S(\boldsymbol\beta + \bo... ...\mu \boldsymbol\delta_\beta + \mathbf{J}^{\top} \mathbf{r} ) }$$ (3.51)

Un elevato valore di $\rho$ indica che la versione linearizzata di $f$ è molto buona e si può diminuire $\mu$. Viceversa se $\rho$ è elevato, allora il valore di $\mu$ è da aumentare. Infine quando $\rho \approx 1$ c'è una buona corrispondenza tra il modello predetto e i dati. Caso limite, quando $\rho$ è negativo indica una soluzione peggiorativa da scartare e $\mu$ è da aumentare in modo da avvicinarsi a un metodo a discesa del gradiente. Attraverso $\rho$ è possibile modificare $\mu$ secondo la regola