Moindres carrés non linéaires

Les moindres carrés non linéaires est une forme des moindres carrés adaptée pour l'estimation d'un modèle non linéaire en n paramètres à partir de m observations (m > n). Une façon d'estimer ce genre de problème est de considérer des itérations successives se basant sur une version linéarisée du modèle initial.

La théorie

Considérons un jeu de $m$ couples d'observations, $(x 1, y 1), (x 2, y 2),...,(x m, y m)$ , et une fonction de régression du type $y = f (x, β)$ . Cette fonction dépend des explicatives $x$ mais aussi du vecteur des n paramètres $β = (β 1, β 2, ..., β n)$ avec $m \geq n$ . On souhaite trouver le vecteur de paramètres $β$ qui ajuste au mieux les données, au sens des moindres carrés :

S=\sum _{i=1}^{m}r_{i}^{2}

est minimisée en $β$ , où les résidus $r i$ sont donnés par

r_{i}=y_{i}-f(x_{i},{\boldsymbol {\beta }}),\ i=1,2,\dots ,m.

Le minimum de la somme des carrés des résidus S est atteint lorsque le gradient s'annule (condition nécessaire). Puisque le problème est formulé avec n paramètres, il y a donc n équations normales :

{\frac {\partial S}{\partial \beta _{j}}}=2\sum _{i}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}=0\ (j=1,\ldots ,n).

Dans un système non linéaire, les dérivées ${\frac {\partial r_{i}}{\partial \beta _{j}}}$ dépendent aussi bien des variables explicatives que des paramètres : il faut donc renoncer à résoudre les équations normales aussi simplement que dans le cas linéaire. On a alors recours à une résolution numérique, à l'aide d'un procédé itératif

{\boldsymbol {\beta }}^{k+1}={\boldsymbol {\beta }}^{k}+\Delta {\boldsymbol {\beta }}.

qui fournit des approximations successives $β k$ de plus en plus proches de la vraie valeur (inconnue) des paramètres, $β 0$ .

À chaque itération, le modèle initial est linéarisé par un développement de Taylor autour de $β k$ comme suit :

f(x_{i},{\boldsymbol {\beta }}_{0})\approx f(x_{i},{\boldsymbol {\beta }}^{k})+\sum _{j}{\frac {\partial f(x_{i},{\boldsymbol {\beta }}^{k})}{\partial \beta _{j}}}\left(\beta _{j}-\beta _{j}^{k}\right)\approx f(x_{i},{\boldsymbol {\beta }}^{k})+\sum _{j}J_{ij}\Delta \beta _{j}.

La matrice jacobienne $J$ dépend des données et de l'approximation en cours, aussi change-t-elle d'une itération à l'autre. Ainsi, en termes du modèle linéarisé, ${\frac {\partial r_{i}}{\partial \beta _{j}}}=-J_{ij}$ et les résidus sont donnés par

r_{i}=\Delta y_{i}-\sum _{j=1}^{n}J_{ij}\Delta \beta _{j};\ \Delta y_{i}=y_{i}-f(x_{i},{\boldsymbol {\beta }}^{k}).

Les équations normales deviennent

-2\sum _{i=1}^{m}J_{ij}\left(\Delta y_{i}-\sum _{s=1}^{n}J_{is}\Delta \beta _{s}\right)=0

ou encore

\sum _{i=1}^{m}\sum _{s=1}^{n}J_{ij}J_{is}\Delta \beta _{s}=\sum _{i=1}^{m}J_{ij}\Delta y_{i}\;(j=1,..,n).\,

Matriciellement, on en arrive à

\mathbf {\left(J^{T}J\right)\Delta {\boldsymbol {\beta }}=J^{T}\Delta } y.

La linéarisation permet donc d'écrire :

{\boldsymbol {\beta }}^{k+1}={\boldsymbol {\beta }}^{k}+\left(\mathbf {J^{T}J} \right)^{-1}\mathbf {J^{T}\Delta } y.

Il faut remarquer que l'ensemble du terme de droite dépend seulement de l'itération en cours, à savoir $β k$ , et permet donc de trouver la prochaine itération $β k +1$ .

On peut aisément généraliser l'approche précédente en considérant une somme pondérée des carrés des résidus

S=\sum _{i=1}^{m}W_{ii}r_{i}^{2}.

Idéalement, chaque élément de la matrice diagonale de pondération $W$ devrait être égal à l'inverse de la variance de l'observation [1] Les équations normales deviennent alors

\mathbf {\left(J^{T}WJ\right)\Delta {\boldsymbol {\beta }}=J^{T}W\Delta y}

ce qui procure la base de l'algorithme d'optimisation de Gauss-Newton.

Différences entre les moindres carrés linéaires et non linéaires

Il y a de nombreuses divergences entre les moindres carrés linéaires (MCL) et non linéaires (MCN) :

les MCN sont un procédé itératif, qui nécessitent donc un point de départ et des critères d'arrêt. Les MCL sont directs (algèbre linéaire) ;
les MCN nécessitent de calculer la matrice jacobienne (dérivées premières). Une expression analytique peut être compliquée à obtenir : si c'est le cas, une différentiation numérique s'impose ;
la divergence est un problème courant des MCN : en effet, il n'est pas rare de voir augmenter la fonction objectif (somme des carrés des résidus) d'une itération à l'autre. Cela peut être dû au manque de précision de l'approximation linéaire par le développement de Taylor ;
Pour les MCL, la solution est unique mais pas pour les MCN : plusieurs minima (locaux) peuvent exister.

Interprétation géométrique

Dans le cas des moindres carrés linéaires, la fonction objectif S est une fonction quadratique des paramètres

S=\sum _{i}W_{ii}\left(y_{i}-\sum _{j}X_{ij}\beta _{j}\right)^{2}

Lorsqu'il y a un seul paramètre à estimer β, la fonction S est une parabole en β. Pour deux paramètres ou plus, le contour de S est constitué d'ellipses concentriques, à condition que la matrice $X T WX$ soit définie positive. Le minimum, atteint pour la valeur optimale des paramètres, est le centre de ces ellipses concentriques.

Dans le cas non linéaire, le contour en ellipses concentriques n'est vrai qu'au voisinage du minimum, puisque dans ce cas l'approximation linéaire de Taylor s'avère être une bonne approximation de la fonction objectif.

S\approx \sum _{i}W_{ii}\left(y_{i}-\sum _{j}J_{ij}\beta _{j}\right)^{2}

Plus les paramètres s'éloignent de leur valeur optimale, plus le contour dévie de sa forme ellipsoïdale. Ceci signifie qu'il est essentiel de choisir l'approximation initiale $β 0$ du procédé itératif proche des valeurs optimales, qui sont par définition inconnues.

Astuces calculatoires

Choix du vecteur d'incrément

Dans le procédé itératif

{\boldsymbol {\beta }}^{k+1}={\boldsymbol {\beta }}^{k}+\Delta {\boldsymbol {\beta }}.

il est impératif de se prémunir contre la divergence. Plusieurs astuces concernant le choix de $Δ β$ peuvent être considérées :

changer sa norme sans pour autant changer sa direction. On peut alors introduire une proportion p (entre 0 et 1) et amender le procédé itératif en ${\boldsymbol {\beta }}^{k+1}={\boldsymbol {\beta }}^{k}+p\Delta {\boldsymbol {\beta }}$ . Par exemple, on peut diviser par deux la valeur de p jusqu'à observer une réelle diminution de la fonction objectif. On peut aussi rechercher la valeur de p par recherche linéaire[2] : pour une grille de valeurs de p, on cherche la valeur de p provoquant la diminution la plus importante de S. Mais une telle méthode est couteuse en calculs, car il faut à chaque fois re-calculer la fonction objectif ;
si la direction de l'incrément est trop éloigné de sa direction « optimale » et que la méthode précédente échoue, il faudra peut-être changer légèrement la direction du vecteur d'incrément $Δ β$ . Pour cela, les équations normales sont transformées en $\mathbf {\left(J^{T}WJ+\lambda I\right)\Delta {\boldsymbol {\beta }}=\left(J^{T}W\right)\Delta y}$ , où $\lambda$ est le paramètre de Marquardt[3] et I la matrice identité. On consultera avec profit la page consacrée à la méthode de Levenberg-Marquardt.

QR

Le minimum de la somme des carrés des résidus peut se trouver sans former les équations normales. Les résidus du modèle linéarisé s'écrivent

\mathbf {r} =\Delta \mathbf {y} -\mathbf {J} \Delta {\boldsymbol {\beta }}

La jacobienne fait l'objet d'une décomposition orthogonale, comme la décomposition QR :

\mathbf {J} =\mathbf {QR}

où $Q$ est une matrice orthogonale $m \times m$ et où $R$ est une matrice $m \times n$ , partitionnée en un bloc $R n$ , de dimension $n \times n$ , et en un bloc nul, de dimension $(m - n) \times n$ . De plus, $R n$ est triangulaire supérieure.

\mathbf {R} ={\begin{bmatrix}\mathbf {R} _{n}\\\mathbf {0} \end{bmatrix}}

Le vecteur de résidu est pré-multiplié par $Q T$ .

\mathbf {Q^{T}r=Q^{T}\Delta y-R\Delta {\boldsymbol {\beta }}} ={\begin{bmatrix}\mathbf {\left(Q^{T}\Delta y-R\Delta {\boldsymbol {\beta }}\right)} _{n}\\\mathbf {\left(Q^{T}\Delta y\right)} _{m-n}\end{bmatrix}}

La somme des carrés reste inchangée puisque $S = r T Q Q T r = r T r$ . Le minimum de S est atteint lorsque le bloc supérieur est nul. Par conséquent, le vecteur d'incrément recherché $\Delta {\boldsymbol {\beta }}$ se trouve en résolvant

\mathbf {R} _{n}\Delta {\boldsymbol {\beta }}=\left(\mathbf {Q} ^{T}\Delta \mathbf {y} \right)_{n}

La résolution est facile d'accès car la matrice $R$ a été prise triangulaire supérieure.

Décomposition en valeurs singulières

Une variante de la méthode précédente fait intervenir la décomposition en valeurs singulières, dans laquelle $R$ est diagonalisée :

\mathbf {J=U{\boldsymbol {\Sigma }}V^{T}}

où $U$ est orthogonal, $Σ$ est une matrice diagonale de valeurs singulières et $V T$ est la matrice orthogonale des vecteurs propres de $R n$ . Dans cette configuration, l'incrément est donné par

\mathbf {{\boldsymbol {\Delta }}\beta =V{\boldsymbol {\Sigma }}^{-1}\left(U^{T}{\boldsymbol {\Delta }}y\right)} _{n}

La relative simplicité de cette expression est très utile dans l'analyse théorique des moindres carrés. Cette méthode est largement détaillée dans Lawson et Hanson[4].

Critères de convergence

Le critère de convergence le plus immédiat est que la somme des carrés ne doit pas décroître d'une itération à l'autre. Ce critère est souvent difficile à implémenter. Aussi, on préfère le critère de convergence suivant

\left|{\frac {S^{k}-S^{k+1}}{S^{k}}}\right|<\varepsilon

La valeur du seuil est arbitraire et doit être adaptée en fonction du problème. En particulier, il faudra augmenter cette valeur lorsque les erreurs expérimentales sont importantes. Un critère alternatif est

\left|{\frac {\Delta \beta _{j}}{\beta _{j}}}\right|<\varepsilon ,\,j=1,n.

Minimums multiples

On peut trouver plusieurs minimums de S dans certaines circonstances:

Un paramètre intervenant à une certaine puissance. Par exemple, pour ajuster des données à une courbe de Lorentz :

f(x_{i},{\boldsymbol {\beta }})={\frac {\alpha }{1+\left({\frac {\gamma -x_{i}}{\beta }}\right)^{2}}}

Il y a alors deux solution pour le paramètre β : ${\hat {\beta }}$ ainsi que $-{\hat {\beta }}$ donnent la même valeur optimale de la fonction critère ;

Deux paramètres peuvent s'interchanger sans changer le critère. Par exemple, cela survient lorsqu'on rencontre le produit de deux paramètres : ainsi $\alpha \beta$ donnera la même chose que $\beta \alpha$ ;
Un paramètre intervient dans une fonction périodique, comme dans $\sin \beta \,$ . Dans ce cas, ${\hat {\beta }}+2n\pi$ donne la même valeur critère.

Tous les minimums multiples ne donnent pas la même valeur de la fonction objectif. Un autre problème concerne les minimums locaux. Par exemple, dans le modèle

f(x_{i},\beta )=\left(1-3\beta +\beta ^{3}\right)x_{i}

il y a un minimum local en $β = 1$ et un minimum global en ${\hat {\beta }}\,$ = -3[5].

Pour être certain d'avoir obtenu un minimum global, il est souhaitable de recommencer la procédure de minimisation en changeant le point de départ. Quand on obtient le même résultat quel que soit le point de départ, on peut alors penser obtenir un minimum global. On utilise typiquement des points de départ aléatoires, par exemple déterminés par l'algorithme de Metropolis-Hastings ; c'est la méthode du recuit simulé.

L'existence de minimums multiples a une conséquence importante: la fonction objectif admet une valeur maximum quelque part entre les deux minimums. Les équations normales en ce maximum fait intervenir des matrices non définies positives. Une telle situation est à proscrire, en particulier comme initialisation du procédé itératif. Par exemple, pour le cas de l'ajustement du modèle de Lorentz, le cas $β = 0$ est à éviter.

Autres méthodes

Linéarisation

Un modèle non linéaire peut parfois se transformer en modèle linéaire. Par exemple, lorsque le modèle est une simple fonction exponentielle,

f(x_{i},{\boldsymbol {\beta }})=\alpha e^{\beta x_{i}}

on peut obtenir un modèle linéaire par transformation logarithmique.

\log f(x_{i},{\boldsymbol {\beta }})=\log \alpha +\beta x_{i}

La somme des carrés devient

S=\sum _{i}(\log y_{i}-\log \alpha -\beta x_{i})^{2}\!

Toutefois, si on n'a aucun renseignement sur la structure des aléas, cette transformation peut être problématique: de toute évidence, les erreurs expérimentales sur y ne sont pas les mêmes que sur log y. Estimer le modèle initial et celui linéarisé donnera des estimations différentes et des variances estimées. En pratique, le modèle exponentiel s'estime dans une procédure à part.

Quelques ajustements

On peut considérer quelques ajustements

Calcul de la matrice jacobienne par approximation numérique. Dans certains modèles, obtenir des dérivées analytiques peut s'avérer délicat. On doit avoir recours à une approximation numérique de la jacobienne; par exemple, l'approximation de son entrée (i,j) est:

\mathbf {J} _{i,j}={\frac {\partial f(x_{i},{\boldsymbol {\beta }})}{\partial \beta _{j}}}\approx {\frac {\delta f(x_{i},{\boldsymbol {\beta }})}{\delta \beta _{j}}}

Cette approximation s'obtient par le calcul de $f(x_{i},{\boldsymbol {\beta }})\,$ pour $\beta _{j}\,$ et $\beta _{j}+\delta \beta _{j}\,$ . L'incrément, $\delta \beta _{j}\,$ , doit être choisi ni trop grand ni trop petit (afin d'éviter les erreurs d'arrondi);

L'inclusion des dérivées secondes dans le développement de Taylor. On obtient la méthode classique de Newton.

f(x_{i},{\boldsymbol {\beta }})=f^{k}(x_{i},{\boldsymbol {\beta }})+\sum _{j}J_{ij}\Delta \beta _{j}+{\frac {1}{2}}\sum _{j}\sum _{k}\Delta \beta _{j}\Delta \beta _{k}H_{jk_{(i)}},\ H_{jk_{(i)}}={\frac {\partial ^{2}f(x_{i},{\boldsymbol {\beta }})}{\partial \beta _{j}\partial \beta _{k}}}

La matrice H est la Matrice hessienne. Bien que présentant de bien meilleures propriétés de convergence près de l'optimum, ce modèle se comporte mal quand les paramètres sont loin de leur valeur optimale. Le calcul de la Hessienne ajoute à la complexité de l'algorithme. Cette méthode n'est pas utilisée en général;

On peut remplacer l'algorithme de Newton par un algorithme de pseudo-Newton, où on calcule numériquement la hessienne par approximations successives. C'est l'algorithme de Davidon-Fletcher-Powell (DFP);

Implémentations de résolution

La bibliothèque logicielle en C++ Ceres Solver a été spécifiquement conçue pour résoudre le problème des moindres carrés non linéaires[6]. Elle est utilisée dans divers produits Google comme Street View[7].

Voir aussi

Bibliographie

C. T. Kelley, Iterative Methods for Optimization, SIAM Frontiers in Applied Mathematics, no 18, 1999, (ISBN 0-89871-433-8). Online copy

Notes et références

Ceci implique que les observations ne soient pas corrélées. Dans le cas contraire, on utilise plutôt la quantité
$S=\sum _{k}\sum _{j}r_{k}W_{kj}r_{j}\,$
Dans ce cas, la matrice idéale de pondération devrait être égale à l'inverse de la matrice de variance-covariance des observations.
M.J. Box, D. Davies and W.H. Swann, Non-Linear optimisation Techniques, Oliver & Boyd, 1969
Cette technique a été proposée indépendamment par Levenberg (1944), Girard (1958), Wynne (1959), Morrison (1960) et Marquardt (1963). C'est le nom de ce dernier que la littérature scientifique a généralement conservé.
C.L. Lawson and R.J. Hanson, Solving Least Squares Problems, Prentice-Hall, 1974
P. Gans, Data Fitting in the Chemical Sciences, Wiley, 1992, p. 71.
Sameer Agarwal, Keir Mierle et al., Ceres Solver.
« Users », sur Ceres Solver (consulté le 15 octobre 2016).

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.