Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Optimisation non linéaire sans contraintes Recherche opérationnelle GC-SIE Mo

1 Optimisation non linéaire sans contraintes Recherche opérationnelle GC-SIE Moindres carrés 2 Moindres carrés • gi: IRm→IRr(i) est continûment différentiable, i=1,…,m • On a souvent r(i) = 1. Moindres carrés Michel Bierlaire 3 Moindres carrés Exemple : Estimation des paramètres d’un modèle • Soit un modèle mathématique z=h(x,y) • x est le vecteur des paramètres inconnus. • y est le vecteur d’entrée du modèle. • z est le vecteur de sortie du modèle. • On dispose de m observations (yi,zi) Moindres carrés Michel Bierlaire 4 3 Moindres carrés • Question : quelles sont les valeurs des paramètres telles que le modèle reproduise le mieux les observations ? Moindres carrés Michel Bierlaire 5 Moindres carrés Exemple : • On veut mesurer la résistivité du cuivre. • On dispose d’une barre de 1m de cuivre, de section 1cm2. • L’expérience consiste à envoyer des courants de diverses intensités et de mesurer la différence de potentiel. • Le modèle mathématique est donné par la loi d’Ohm. Moindres carrés Michel Bierlaire 6 4 Moindres carrés • Paramètre inconnu : résistance R • Entrée du modèle : intensité I • Sortie du modèle : diff. potentiel V • Modèle mathématique : V = R I = (λ/S) ρ I où λ est la longueur, S la section et ρ la résistivité du cuivre. Moindres carrés Michel Bierlaire 7 Moindres carrés • Données récoltées : Moindres carrés Michel Bierlaire 8 Intensité Voltage 0.100 1.70E-05 0.105 1.74E-05 0.110 1.89E-05 0.115 2.01E-05 0.120 1.94E-05 0.125 2.16E-05 0.130 2.01E-05 0.135 2.28E-05 0.140 2.37E-05 0.145 2.34E-05 Intensité Voltage 0.150 2.19E-05 0.155 2.68E-05 0.160 2.67E-05 0.165 2.76E-05 0.170 2.72E-05 0.175 2.77E-05 0.180 2.62E-05 0.185 2.78E-05 0.190 2.80E-05 0.195 3.09E-05 0.200 3.45E-05 5 1.50E-05 2.00E-05 2.50E-05 3.00E-05 3.50E-05 4.00E-05 0.100 0.120 0.140 0.160 0.180 0.200 0.220 Intensité Voltage 1.50E-05 2.00E-05 2.50E-05 3.00E-05 3.50E-05 4.00E-05 0.100 0.120 0.140 0.160 0.180 0.200 0.220 Intensité Voltage Voltage mesuré Modèle 6 Moindres carrés Réseaux de neurones. • Modèle spécifié par un système multi- niveaux. • Le niveau consiste en nk unités d’activitation ou neurone. • Chaque unité d’activation est une relation entrée-sortie φ:IR→IR Moindres carrés Michel Bierlaire 11 Moindres carrés Moindres carrés Michel Bierlaire 12 φ + xj k+1 xs k us k u0 k 7 Moindres carrés • La sortie de la jième unité d’activation du niveau k+1 est notée xj k+1. • L’entrée est une fonction linéaire des sorties du niveau k. • Donc Moindres carrés Michel Bierlaire 13 Moindres carrés • Les uk s sont appelés « poids » • Ce sont les paramètres à déterminer. • Pour un ensemble de paramètres donnés, et si N est le nombre de niveaux, à chaque vecteur d’entrée x0 du niveau 0 correspond un vecteur de sortie xN du niveau N. Moindres carrés Michel Bierlaire 14 8 Moindres carrés • Le réseau de neurones peut donc être considéré comme un modèle mathématique z=h(x,y) • où – x est le vecteur de poids – y est le vecteur d’entrées au niveau 0 – z est le vecteur de sorties au niveau N Moindres carrés Michel Bierlaire 15 Moindres carrés • La phase d’entrainement du réseau, ou phase d’apprentissage peut donc être considérée comme la résolution d’un problème de moindres carrés. • Exemples typiques de fonctions d’activation : Fonction sigmoidale : Fonction hyperbolique tangente : Moindres carrés Michel Bierlaire 16 9 Moindres carrés • Le problème d’entrainement de réseaux neuronaux est souvent très compliqué. Les fonctions de coûts associées sont non- convexes et possèdent souvent des minima locaux multiples. • Exemple à deux paramètres. Moindres carrés Michel Bierlaire 17 Source: Bertsekas (1995) Nonlinear programming, Athena Scientific 10 Gauss-Newton Idée • Travailler sur g et non sur f. • Linéarisation de g : Moindres carrés Michel Bierlaire 19 Gauss-Newton • Minimiser la norme de m(x) Moindres carrés Michel Bierlaire 20 11 Gauss-Newton • Si f(x) = ½ ¦¦m(x)¦¦2, alors Moindres carrés Michel Bierlaire 21 Le minimum est atteint en si la matrice est inversible. ( ) ( ) ( ) ( ) ) ( ( ) T k k k k k g x g x x x g x f x g x = ∇ ∇ − + ∇ ∇ ( ) 1 ( ) ( ) ( ) ( ) T k k k k k x x g x g x g x g x − = −∇ ∇ ∇ Gauss-Newton • Une itération Gauss-Newton pure est Moindres carrés Michel Bierlaire 22 ∇g(xk)g(xk) est le gradient de ½¦¦g(x)¦¦2 en xk Si ∇g(xk)∇g(xk)T est définie positive, nous avons donc une direction de descente. 12 Gauss-Newton • Tout comme la méthode de Newton pure pour le cas général, la méthode de Gauss-Newton pure pour les moindres carrés peut ne pas converger. • Solution : Moindres carrés Michel Bierlaire 23 Gauss-Newton • αk est choisi par la règle d’Armijo. • ∆k est une matrice diagonale telle que ∇g(xk)∇g(xk)T+∆ksoit défini positif. • Méthode de Levenberg-Marquardt : ∆k = multiple de l’identité Moindres carrés Michel Bierlaire 24 13 Gauss-Newton Cas linéaire • g(x)=Cx-z • ∇g(x) = CT • xk+1 = xk-(CTC)-1CT(Cxk-z) = (CTC)-1CTz ∀k • La solution est obtenue en une itération • Note: le système d’équations CTCx=CTz est appelé équations normales. Moindres carrés Michel Bierlaire 25 Gauss-Newton Relation avec la méthode de Newton • Soit g:IRn →IRm • f(x)= ½ ¦¦g(x)¦¦2 Moindres carrés Michel Bierlaire 26 14 Gauss-Newton Gauss-Newton = Newton en négligeant le second terme Moindres carrés Michel Bierlaire 27 Régression orthogonale Moindres carrés Michel Bierlaire 28 Moindres carrés Régression orthogonale 15 Régression orthogonale Moindres carrés Michel Bierlaire 29 (y,h(x,y)) (yi,zi) minx miny (yi-y)2+(zi-h(x,y))2 Régression orthogonale Notes : • Cette régression est utilisée lorsque des erreurs sont présentes aussi dans les entrées du modèle. • On suppose que les erreurs dans les entrées et les erreurs dans les sorties sont indépendantes, de moyenne nulle. • Même si le modèle est linéaire, le problème de moindres carrés n’est pas linéaire. Moindres carrés Michel Bierlaire 30 16 Régression orthogonale • Exemples : – Résistivité du cuivre • Moindres carrés : r = 1.61046 10-8 • Régression orthogonale : 1.60797 10-8 – Modèle sphérique : • z = x1 + [x2 2-(y-x3)2]½ Moindres carrés Michel Bierlaire 31 Régression orthogonale Moindres carrés : • x1 = 1.9809 • x2 = 4.7794 • x3 = 2.9938 Orthogonale : • x1 = 3.2759 • x2 = 3.8001 • x3 = 3.0165 Moindres carrés Michel Bierlaire 32 y z 0.0000 5.8776 0.0974 5.7608 0.2042 5.5878 0.3090 5.7680 0.3911 6.0966 0.5092 6.3744 0.5972 5.9919 5.2431 6.4085 5.8022 5.9953 5.6136 5.7521 5.7435 5.6481 6.1645 5.6582 6.1940 5.5383 Modèle réel : x1 = 3 x2 = 4 x3 = 3 17 5.5000 5.7000 5.9000 6.1000 6.3000 6.5000 6.7000 6.9000 7.1000 0.0000 1.0000 2.0000 3.0000 4.0000 5.0000 6.0000 7.0000 Données Moindres carrés Orthogonale uploads/Litterature/ 11-moindres-carres.pdf