7. Fonctions d'optimisation▲
Objectifs du chapitre |
---|
|
Les méthodes de bissection, du point fixe, de Newton-Raphson et consorts permettent de résoudre des équations à une variable de la forme kitxmlcodeinlinelatexdvpf(x) = 0finkitxmlcodeinlinelatexdvp ou kitxmlcodeinlinelatexdvpg(x) = xfinkitxmlcodeinlinelatexdvp Il existe également des versions de ces méthodes pour les systèmes à plusieurs variables de la forme
kitxmlcodelatexdvp\begin{matrix} f_1(x_1,x_2,x_3) = 0 \\ f_2(x_1,x_2,x_3) = 0 \\ f_3(x_1,x_2,x_3) = 0 \end{matrix}finkitxmlcodelatexdvpDe tels systèmes d'équations surviennent plus souvent qu'autrement lors de l'optimisation d'une fonction. Par exemple, en recherchant le maximum ou le minimum d'une fonction kitxmlcodeinlinelatexdvpf(x,y)finkitxmlcodeinlinelatexdvp, on souhaitera résoudre le système d'équations
kitxmlcodelatexdvp\begin{matrix} \frac{\partial}{\partial x}f(x,y) = 0 \\ \frac{\partial}{\partial y}f(x,y) = 0 \end{matrix}finkitxmlcodelatexdvpEn inférence statistique, les fonctions d'optimisation sont fréquemment employées pour calculer numériquement des estimateurs du maximum de vraisemblance.
La grande majorité des suites logicielles de calcul comportent des outils d'optimisation de fonctions. Ce chapitre passe en revue les fonctions disponibles dans R. Comme pour les chapitres précédents, des exemples d'utilisation de chacune des fonctions se trouvent dans le code informatique de la section 7.4Exemples.
7-1. Fonctions d'optimisation et de calcul de racines▲
Le système R compte un certain nombre de fonctions pour trouver numériquement le minimum ou le maximum d'une fonction ainsi que pour calculer la racine d'une fonction dans un intervalle ou toutes les racines d'un polynôme. Ces fonctions diffèrent par certaines de leurs fonctionnalités et leur interface, mais aussi par les algorithmes utilisés. Consulter les rubriques d'aide pour les détails.
7-1-1. Fonction uniroot▲
La fonction uniroot recherche la racine d'une fonction dans un intervalle. C'est donc la fonction de base pour trouver la solution (unique) de l'équation kitxmlcodeinlinelatexdvpf(x) = 0finkitxmlcodeinlinelatexdvp dans un intervalle déterminé.
7-1-2. Fonction optimize▲
La fonction optimize recherche le minimum local (par défaut) ou le maximum local d'une fonction dans un intervalle donné.
7-1-3. Fonction nlm▲
La fonction nlm minimise une fonction non linéaire sur un nombre arbitraire de paramètres.
7-1-4. Fonction nlminb▲
La fonction nlminb est similaire à nlm, sauf qu'elle permet de spécifier des bornes inférieure ou supérieure pour les paramètres. Attention, toutefois : les arguments de la fonction ne sont ni les mêmes, ni dans le même ordre que ceux de nlm.
7-1-5. Fonction optim▲
La fonction optim est l'outil d'optimisation tout usage de R. À ce titre, la fonction est souvent utilisée par d'autres fonctions. Elle permet de choisir parmi plusieurs algorithmes d'optimisation différents et, selon l'algorithme choisi, de fixer des seuils minimum ou maximum aux paramètres à optimiser.
7-1-6. polyroot▲
En terminant, un mot sur polyroot(), qui n'est pas à proprement parler une fonction d'optimisation, mais qui pourrait être utilisée dans ce contexte. La fonction polyroot calcule toutes les racines (complexes) du polynôme kitxmlcodeinlinelatexdvp\sum_{i=0}^n a_ix^ifinkitxmlcodeinlinelatexdvp. Le premier argument est le vecteur des coefficients kitxmlcodeinlinelatexdvpa_0, a_1,\dots,a_nfinkitxmlcodeinlinelatexdvp dans cet ordre.
7-2. Astuce Ripley▲
Brian Ripley — un important développeur de R — a publié le truc suivant dans les forums de discussion de R. Puisqu'il est très utile, nous nous permettons de le disséminer.
Une application statistique fréquente de l'optimisation est la maximisation numérique d'une fonction de vraisemblance ou, plus communément, la minimisation de la log-vraisemblance négative
kitxmlcodelatexdvp-l(\theta) = \sum_{i=1}^n \ln f(x_i;\theta)finkitxmlcodelatexdvpLes fonctions d'optimisation sont d'ailleurs illustrées dans ce contexte dans le code informatique de la section 7.4Exemples.
Plusieurs lois de probabilité ont des paramètres strictement positifs. Or, en pratique, il n'est pas rare que les fonctions d'optimisation s'égarent dans les valeurs négatives des paramètres. La fonction de densité n'étant pas définie, la log-vraisemblance vaut alors NaN et cela peut faire complètement dérailler la procédure d'optimisation ou, à tout le moins, susciter des doutes sur la validité de la réponse.
Afin de pallier ce problème, l'Astuce Ripley™ propose d'estimer non pas les paramètres de la loi eux-mêmes, mais plutôt leur logarithme. Si l'on définit kitxmlcodeinlinelatexdvp\tilde{\theta} = \ln\thetafinkitxmlcodeinlinelatexdvp alors on peut écrire la fonction de log-vraisemblance ci-dessus sous la forme
kitxmlcodelatexdvp-l(\tilde{\theta}) = -\sum_{i=1}^n \ln f\left(x_i;e^\tilde{\theta}\right)finkitxmlcodelatexdvpDès lors, kitxmlcodeinlinelatexdvp\tilde{\theta}finkitxmlcodeinlinelatexdvp (qui peut représenter un ou plusieurs paramètres) demeure valide sur tout l'axe des réels, ce qui permet d'éviter bien des soucis de nature numérique lors de la minimisation de kitxmlcodeinlinelatexdvp-l(\tilde{\theta})finkitxmlcodeinlinelatexdvp.
Évidemment, le résultat de l'optimisation est l'estimateur du maximum de vraisemblance de kitxmlcodeinlinelatexdvp\tilde{\theta}finkitxmlcodeinlinelatexdvp. Il faudra donc veiller à faire la transformation inverse ̃ pour retrouver l'estimateur de kitxmlcodeinlinelatexdvp\thetafinkitxmlcodeinlinelatexdvp.
L'utilisation de l'astuce est illustrée à la section 7.4Exemples.
7-3. Pour en savoir plus▲
Les packages disponibles sur CRAN fournissent plusieurs autres outils d'optimisation pour R. Pour un bon résumé des options disponibles, consulter la CRAN Task View consacrée à l'optimisation : http://cran.r-project.org/web/views/Optimization.html.
7-4. Exemples▲
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
###
### FONCTION 'uniroot'
###
## La fonction 'uniroot' recherche la racine d'une fonction
## 'f' dans un intervalle spécifié soit comme une paire de
## valeurs dans un argument 'interval', soit via des arguments
## 'lower' et 'upper'.
##
## On calcule la solution de l'équation x - 2^(-x) = 0 dans
## l'intervalle [0, 1].
f <-
function
(x) x -
2
^
(-
x) # fonction
uniroot
(f, c
(0
, 1
)) # appel simple
uniroot
(f, lower =
0
, upper =
1
) # équivalent
## On peut aussi utiliser 'uniroot' avec une fonction anonyme.
uniroot
(function
(x) x -
2
^
(-
x), lower =
0
, upper =
1
)
###
### FONCTION 'optimize'
###
## On cherche le maximum local de la densité d'une loi bêta
## dans l'intervalle (0, 1), son domaine de définition. (Ce
## problème est facile à résoudre explicitement.)
##
## Les arguments de 'optimize' sont essentiellement les mêmes
## que ceux de 'uniroot'. Ici, on utilise aussi l'argument
## '... ' pour passer les paramètres de la loi bêta à 'dbeta'.
##
## Par défaut, la fonction recherche un minimum. Il faut donc
## lui indiquer de rechercher plutôt un maximum.
optimize
(dbeta
, interval =
c
(0
, 1
), maximum =
TRUE
,
shape1 =
3
, shape2 =
2
)
## On pourrait aussi avoir recours à une fonction auxiliaire.
## Moins élégant et moins flexible.
f <-
function
(x) dbeta
(x, 3
, 2
)
optimize
(f, lower =
0
, upper =
1
, maximum =
TRUE
)
###
### FONCTION 'nlm'
###
## Pour la suite, nous allons donner des exemples
## d'utilisation des fonctions d'optimisation dans un contexte
## d'estimation des paramètres d'une loi gamma par la méthode
## du maximum de vraisemblance.
##
## On commence par se donner un échantillon aléatoire de la
## loi. Évidemment, pour ce faire nous devons connaître les
## paramètres de la loi. C'est un exemple fictif.
set.seed
(1
) # toujours le même échantillon
x <-
rgamma
(10
, 5
, 2
)
## Les estimateurs du maximum de vraisemblance des paramètres
## 'shape' et 'rate' de la loi gamma sont les valeurs qui
## maximisent la fonction de vraisemblance
##
## prod(dgamma(x, shape, rate))
##
## ou, de manière équivalente, qui minimisent la fonction de
## log-vraisemblance négative
##
## -sum(log(dgamma(x, shape, rate))).
##
## On remarquera au passage que les fonctions de calcul de
## densités de lois de probabilité dans R ont un argument
## 'log' qui, lorsque TRUE, retourne la valeur du logarithme
## (naturel) de la densité de manière plus précise qu'en
## prenant le logarithme après coup. Ainsi, pour faire le
## calcul ci-dessus, on optera plutôt, pour l'expression
##
## -sum(dgamma(x, shape, rate, log = TRUE))
##
## La fonction 'nlm' suppose que la fonction à optimiser
## passée en premier argument a elle-même comme premier
## argument le vecteur 'p' des paramètres à optimiser. Le
## second argument de 'nlm' est un vecteur de valeurs de
## départ, une pour chaque paramètre.
##
## Ainsi, pour trouver les estimateurs du maximum de
## vraisemblance avec la fonction 'nlm' pour l'échantillon
## ci-dessus, on doit d'abord définir une fonction auxiliaire
## conforme aux attentes de 'nlm' pour calculer la fonction de
## log-vraisemblance (à un signe près).
f <-
function
(p, x) -
sum
(dgamma
(x, p[
1
]
, p[
2
]
, log
=
TRUE
))
## L'appel de 'nlm' est ensuite tout simple. Remarquer comment
## on passe notre échantillon aléatoire (contenu dans l'objet
## 'x') comme second argument à 'f' via l'argument '... ' de
## 'nlm'. Le fait que l'argument de 'f' et l'objet contenant
## les valeurs portent le même nom est sans importance. R sait
## faire la différence entre l'un et l'autre.
nlm
(f, c
(1
, 1
), x =
x)
## === ASTUCE RIPLEY ===
## L'optimisation ci-dessus a généré des avertissements ? C'est
## parce que la fonction d'optimisation s'est égarée dans les
## valeurs négatives, alors que les paramètres d'une gamma
## sont strictement positifs. Cela arrive souvent en pratique
## et cela peut faire complètement dérailler la procédure
## d'optimisation (c'est-à-dire : pas de convergence).
##
## L'Astuce Ripley consiste à pallier ce problème en
## estimant plutôt les logarithmes des paramètres. Pour ce
## faire, il s'agit de réécrire la log-vraisemblance comme une
## fonction du logarithme des paramètres, mais de la calculer
## avec les véritables paramètres.
f2 <-
function
(logp, x)
{
p <-
exp
(logp) # retour aux paramètres originaux
-
sum
(dgamma
(x, p[
1
]
, p[
2
]
, log
=
TRUE
))
}
nlm
(f2, c
(0
, 0
), x =
x)
## Les valeurs obtenues ci-dessus sont toutefois les
## estimateurs des logarithmes des paramètres de la loi gamma.
## On retrouve les estimateurs des paramètres en prenant
## l'exponentielle des réponses.
exp
(nlm
(f2, c
(0
, 0
), x =
x)$
estimate)
## ====================
###
### FONCTION 'nlminb'
###
## L'utilisation de la fonction 'nlminb' peut s'avérer
## intéressante dans notre contexte puisque l'on sait que les
## paramètres d'une loi gamma sont strictement positifs.
nlminb(c
(1
, 1
), f, x =
x, lower =
0
, upper =
Inf
)
###
### FONCTION 'optim'
###
## La fonction 'optim' est très puissante, mais requiert aussi
## une bonne dose de prudence. Ses principaux arguments sont :
##
## par : un vecteur contenant les valeurs initiales des
## paramètres ;
## fn : la fonction à minimiser. Le premier argument de fn
## doit être le vecteur des paramètres.
##
## Comme pour les autres fonctions étudiées ci-dessus, on peut
## passer des arguments à 'fn' (les données, par exemple) par
## le biais de l'argument '... ' de 'optim'.
optim
(c
(1
, 1
), f, x =
x)
## L'estimation par le maximum de
## vraisemblance\index{vraisemblance} est de beaucoup
## simplifiée par l'utilisation de la fonction
## \fonction{fitdistr} du package
## \texttt{MASS}\index{package! MASS@\texttt{MASS}}.
###
### FONCTION 'polyroot'
###
## Racines du polynôme x^3 + 4 x^2 - 10. Les réponses sont
## données sous forme de nombre complexe. Utiliser les
## fonctions 'Re' et 'Im' pour extraire les parties réelles et
## imaginaires des nombres, respectivement.
polyroot
(c
(-
10
, 0
, 4
, 1
)) # racines
Re
(polyroot
(c
(-
10
, 0
, 4
, 1
))) # parties réelles
Im
(polyroot
(c
(-
10
, 0
, 4
, 1
))) # parties imaginaires
7-5. Exercices▲
7.1 (solution) Trouver la solution des équations suivantes à l'aide des fonctions R appropriées.
- kitxmlcodeinlinelatexdvpx^3-2x^2-5=0finkitxmlcodeinlinelatexdvp pour kitxmlcodeinlinelatexdvp1\le x\le 4finkitxmlcodeinlinelatexdvp
- kitxmlcodeinlinelatexdvpx^3+3x^2-1=0finkitxmlcodeinlinelatexdvp pour kitxmlcodeinlinelatexdvp-4\le x\le 0finkitxmlcodeinlinelatexdvp
- kitxmlcodeinlinelatexdvpx-2^{-x} = 0finkitxmlcodeinlinelatexdvp pour kitxmlcodeinlinelatexdvp0\le x\le 1finkitxmlcodeinlinelatexdvp
- kitxmlcodeinlinelatexdvpe^x+2^{-x}+2\cos x-6=0finkitxmlcodeinlinelatexdvp pour kitxmlcodeinlinelatexdvp1\le x\le 2finkitxmlcodeinlinelatexdvp
- kitxmlcodeinlinelatexdvpe^x - x^2+3x-2=0finkitxmlcodeinlinelatexdvp pour kitxmlcodeinlinelatexdvp0\le x\le 1finkitxmlcodeinlinelatexdvp
7.2 (solution) En théorie de la crédibilité, l'estimateur d'un paramètre kitxmlcodeinlinelatexdvpafinkitxmlcodeinlinelatexdvp est donné sous forme de point fixe
kitxmlcodelatexdvp\hat{a} = \frac{1}{n-1}\sum_{i=1}^n z_i (X_i - \bar{X}_z)^2finkitxmlcodelatexdvpoù
kitxmlcodelatexdvpz_i = \frac{\hat{a}w_i}{\hat{a}w_i+s^2}finkitxmlcodelatexdvp kitxmlcodelatexdvp\bar{X}_z = \sum_{i=1}^n\frac{z_i}{z_\Sigma}X_ifinkitxmlcodelatexdvpet kitxmlcodeinlinelatexdvpX_1,\dots,X_nfinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpw_1,\dots,w_nfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvps^2finkitxmlcodeinlinelatexdvp sont des données. Calculer la valeur de kitxmlcodeinlinelatexdvp\hat{a}finkitxmlcodeinlinelatexdvp si kitxmlcodeinlinelatexdvps^2 = 140\;000\;000finkitxmlcodeinlinelatexdvp et que les valeurs de kitxmlcodeinlinelatexdvpX_ifinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpw_ifinkitxmlcodeinlinelatexdvp sont telles qu'elles apparaissent dans le tableau ci-dessous.
kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp |
1 |
2 |
3 |
4 |
5 |
kitxmlcodeinlinelatexdvpX_ifinkitxmlcodeinlinelatexdvp |
2061 |
1511 |
1806 |
1353 |
1600 |
kitxmlcodeinlinelatexdvpw_ifinkitxmlcodeinlinelatexdvp |
100 155 |
19 895 |
13 735 |
4 152 |
36 110 |
7.3 (solution) Les fonctions de densité de probabilité et de répartition de la distribution de Pareto sont données à l'exercice 6.3. Calculer les estimateurs du maximum de vraisemblance des paramètres de la Pareto à partir d'un échantillon aléatoire obtenu par simulation avec la commande
>
x <-
lambda *
(runif
(100
)^
(-
1
/
alpha) -
1
)
pour des valeurs de alpha et lambda choisies.