View
3
Download
0
Category
Preview:
Citation preview
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
QUELQUES ASPECTS DE LA PLANIFICATION D’EXPÉRIENCESPOUR MODÈLES NON PARAMÉTRIQUES
Luc Pronzato
Laboratoire I3S,CNRS/Univ. Nice Sophia Antipolis, France
CEA Cadarache, 13 décembre 2005 – p.1/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Plan
I) Planification pour l’estimation : exemple 1
CEA Cadarache, 13 décembre 2005 – p.2/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Plan
I) Planification pour l’estimation : exemple 1
II) Estimation : exemple 2
CEA Cadarache, 13 décembre 2005 – p.2/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Plan
I) Planification pour l’estimation : exemple 1
II) Estimation : exemple 2
III) Discrimination : exemple 3
CEA Cadarache, 13 décembre 2005 – p.2/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Plan
I) Planification pour l’estimation : exemple 1
II) Estimation : exemple 2
III) Discrimination : exemple 3
IV) Optimisation et planification d’expériences
CEA Cadarache, 13 décembre 2005 – p.2/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Plan
I) Planification pour l’estimation : exemple 1
II) Estimation : exemple 2
III) Discrimination : exemple 3
IV) Optimisation et planification d’expériences
V) Modèles non paramétriques
CEA Cadarache, 13 décembre 2005 – p.2/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Plan
I) Planification pour l’estimation : exemple 1
II) Estimation : exemple 2
III) Discrimination : exemple 3
IV) Optimisation et planification d’expériences
V) Modèles non paramétriques
VI) Planification en non paramétrique
CEA Cadarache, 13 décembre 2005 – p.2/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Plan
I) Planification pour l’estimation : exemple 1
II) Estimation : exemple 2
III) Discrimination : exemple 3
IV) Optimisation et planification d’expériences
V) Modèles non paramétriques
VI) Planification en non paramétrique
VII) Retour sur l’optimisation
CEA Cadarache, 13 décembre 2005 – p.2/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
I) Exemple 1 : pesée de 8 objets
.......
...........................................................
y = m1 − m2 + ǫ
m1
m2
CEA Cadarache, 13 décembre 2005 – p.3/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
I) Exemple 1 : pesée de 8 objets
.......
...........................................................
y = m1 − m2 + ǫ
m1
m2
Les objets ont des masses mi, i = 1, . . . , 8
les erreurs εi sont i.i.d. N (0, σ2)
CEA Cadarache, 13 décembre 2005 – p.3/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Méthode a: on pèse les 8 objets successivement→ y(i) = mi + εi, i = 1, . . . , 8
→ masses estimées : mi = y(i) ∼ N (mi, σ2)
On répète 8 fois, en moyennant les résultats :ˆmi = y(i) ∼ N (mi, σ
2/8) (avec 64 observations. . . )
CEA Cadarache, 13 décembre 2005 – p.4/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Méthode a: on pèse les 8 objets successivement→ y(i) = mi + εi, i = 1, . . . , 8
→ masses estimées : mi = y(i) ∼ N (mi, σ2)
On répète 8 fois, en moyennant les résultats :ˆmi = y(i) ∼ N (mi, σ
2/8) (avec 64 observations. . . )
Méthode b: plus sophistiquée. . .
CEA Cadarache, 13 décembre 2005 – p.4/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
y(1) = m1 + m2 + m3 + m4 + m5 + m6 + m7 + m8 + ε1
y(2) = m1 + m2 + m3 − m4 − m5 − m6 − m7 + m8 + ε2
y(3) = m1 − m2 − m3 + m4 + m5 − m6 − m7 + m8 + ε3
y(4) = m1 − m2 − m3 − m4 − m5 + m6 + m7 + m8 + ε4
y(5) = −m1 + m2 − m3 + m4 − m5 + m6 − m7 + m8 + ε5
y(6) = −m1 + m2 − m3 − m4 + m5 − m6 + m7 + m8 + ε6
y(7) = −m1 − m2 + m3 + m4 − m5 − m6 + m7 + m8 + ε7
y(8) = −m1 − m2 + m3 − m4 + m5 + m6 − m7 + m8 + ε8
CEA Cadarache, 13 décembre 2005 – p.5/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
y(1) = m1 + m2 + m3 + m4 + m5 + m6 + m7 + m8 + ε1
y(2) = m1 + m2 + m3 − m4 − m5 − m6 − m7 + m8 + ε2
y(3) = m1 − m2 − m3 + m4 + m5 − m6 − m7 + m8 + ε3
y(4) = m1 − m2 − m3 − m4 − m5 + m6 + m7 + m8 + ε4
y(5) = −m1 + m2 − m3 + m4 − m5 + m6 − m7 + m8 + ε5
y(6) = −m1 + m2 − m3 − m4 + m5 − m6 + m7 + m8 + ε6
y(7) = −m1 − m2 + m3 + m4 − m5 − m6 + m7 + m8 + ε7
y(8) = −m1 − m2 + m3 − m4 + m5 + m6 − m7 + m8 + ε8
→ m1 =y(1) + y(2) + y(3) + y(4) − y(5) − y(6) − y(7) − y(8)
8
= m1 +ε1 + ε2 + ε3 + ε4 − ε5 − ε6 − ε7 − ε8
8etc.
CEA Cadarache, 13 décembre 2005 – p.5/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
et mi ∼ N (mi, σ2/8) avec 8 observations seulement !
(contre 64 avec la méthode a)
CEA Cadarache, 13 décembre 2005 – p.6/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
et mi ∼ N (mi, σ2/8) avec 8 observations seulement !
(contre 64 avec la méthode a)Ici, sélection d’un bon plan = problème de combinatoire :
On a y(k) =∑8
i=1 ukimi + εk = u⊤k m + εk
par exemple pour y(2) dans la méthode b :
u2 = [1 1 1 − 1 − 1 − 1 − 1 1]⊤
CEA Cadarache, 13 décembre 2005 – p.6/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
et mi ∼ N (mi, σ2/8) avec 8 observations seulement !
(contre 64 avec la méthode a)Ici, sélection d’un bon plan = problème de combinatoire :
On a y(k) =∑8
i=1 ukimi + εk = u⊤k m + εk
par exemple pour y(2) dans la méthode b :
u2 = [1 1 1 − 1 − 1 − 1 − 1 1]⊤
estimateur des MC : m = arg minm
N∑
k=1
[y(k) − u⊤k m]2
=
(N∑
k=1
uku⊤k
)−1 N∑
k=1
y(k)uk
→ Choisir des uk tels que MN =∑N
k=1 uku⊤k est non
singulièreCEA Cadarache, 13 décembre 2005 – p.6/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
IEm = m (sans biais)
CEA Cadarache, 13 décembre 2005 – p.7/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
IEm = m (sans biais)
IE(m − m)(m − m)⊤ = σ2M−1N
→ minimiser une fonction scalaire de M−1N
CEA Cadarache, 13 décembre 2005 – p.7/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
IEm = m (sans biais)
IE(m − m)(m − m)⊤ = σ2M−1N
→ minimiser une fonction scalaire de M−1N
Problème de combinatoire puique uki ∈ −1, 0, 1[Fisher, 1925 . . . ]
CEA Cadarache, 13 décembre 2005 – p.7/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
IEm = m (sans biais)
IE(m − m)(m − m)⊤ = σ2M−1N
→ minimiser une fonction scalaire de M−1N
Problème de combinatoire puique uki ∈ −1, 0, 1[Fisher, 1925 . . . ]
Plus généralement, quand les variables (facteurs, entrées)uk sont des réels, le plan optimal pour l’estimation estobtenu par l’optimisation d’une fonction scalaire de lamatrice de covariance (asymptotique) de l’estimateur
CEA Cadarache, 13 décembre 2005 – p.7/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Exemple 2 : phamacocinétique
[D’Argenio, 1981], modèle à 2 compartimentsUn produit x est injecté par perfusion (→ entrée u(t)),xC(t) (produit dans le sang) passe dans un autre tissu →xP (t)Eq. différentielles linéaires :
dxC(t)
dt = (−KEL− KCP )xC(t) + KPCxP (t) + u(t)dxP (t)
dt = KCP xC(t) − KPCxP (t)
On observe la concentration de x dans le sang :y(t) = xC(t)/V + ε(t),
les (ǫ(ti)) sont i.i.d. N (0, σ2), σ = 0.2µg/ml
CEA Cadarache, 13 décembre 2005 – p.8/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Exemple 2 : phamacocinétique
[D’Argenio, 1981], modèle à 2 compartimentsUn produit x est injecté par perfusion (→ entrée u(t)),xC(t) (produit dans le sang) passe dans un autre tissu →xP (t)Eq. différentielles linéaires :
dxC(t)
dt = (−KEL− KCP )xC(t) + KPCxP (t) + u(t)dxP (t)
dt = KCP xC(t) − KPCxP (t)
On observe la concentration de x dans le sang :y(t) = xC(t)/V + ε(t),
les (ǫ(ti)) sont i.i.d. N (0, σ2), σ = 0.2µg/ml
4 paramètres inconnus : θ = (KCP , KPC , KEL, V )
CEA Cadarache, 13 décembre 2005 – p.8/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Le profil de l’entrée u(t) est imposé :
u(t) (in mg/min)
t (in min)
75
1.45
1→ expérience simulée avec des valeurs de paramètres
θ = (0.066 min−1, 0.038 min−1, 0.0242 min−1, 30 l)
CEA Cadarache, 13 décembre 2005 – p.9/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Variables expér. = instants de mesure ti, 1 ≤ ti ≤ 720 min
CEA Cadarache, 13 décembre 2005 – p.10/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Variables expér. = instants de mesure ti, 1 ≤ ti ≤ 720 min• Protocole «conventionnel» :
t = (5, 10, 30, 60, 120, 180, 360, 720) (en min)
CEA Cadarache, 13 décembre 2005 – p.10/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Variables expér. = instants de mesure ti, 1 ≤ ti ≤ 720 min• Protocole «conventionnel» :
t = (5, 10, 30, 60, 120, 180, 360, 720) (en min)
• Protocole «optimal» (pour θ) :
t = (1, 1, 10, 10, 74, 74, 720, 720) (en min)
(suppose possible d’obtenir des observationsindépendantes à un même instant)
CEA Cadarache, 13 décembre 2005 – p.10/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Variables expér. = instants de mesure ti, 1 ≤ ti ≤ 720 min• Protocole «conventionnel» :
t = (5, 10, 30, 60, 120, 180, 360, 720) (en min)
• Protocole «optimal» (pour θ) :
t = (1, 1, 10, 10, 74, 74, 720, 720) (en min)
(suppose possible d’obtenir des observationsindépendantes à un même instant)→ 400 simulations→ 400 fois 8 observations, pour chaque protocole→ 400 paramètres estimés (MC) pour chaque protocole. . .
histogrammes des θi
(approximation des marginales [Pázman & Pronzato 1996])
CEA Cadarache, 13 décembre 2005 – p.10/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Marginales et histogrammes pour les 2 protocoles (optimal—, conventionnel - - -)
0 0.05 0.1 0.15 0.2 0.250
5
10
15
20
25
KCP [KCP = 0.066]
0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.160
5
10
15
20
25
30
KPC [KPC = 0.038]
CEA Cadarache, 13 décembre 2005 – p.11/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Marginales et histogrammes pour les 2 protocoles (optimal—, conventionnel - - -)
0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.050
20
40
60
80
100
120
140
160
180
KEL [KEL = 0.0242]
0 5 10 15 20 25 30 35 40 45 500
0.05
0.1
0.15
0.2
0.25
V [V = 30]
CEA Cadarache, 13 décembre 2005 – p.12/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Marginales et histogrammes pour les 2 protocoles (optimal—, conventionnel - - -)
0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.050
20
40
60
80
100
120
140
160
180
KEL [KEL = 0.0242]
0 5 10 15 20 25 30 35 40 45 500
0.05
0.1
0.15
0.2
0.25
V [V = 30]
protocole «optimal» → estimation plus préciseCEA Cadarache, 13 décembre 2005 – p.12/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Exemple 3 : discrimination
[Box & Hill, 1967]: discrimination entre structures demodèles
CEA Cadarache, 13 décembre 2005 – p.13/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Exemple 3 : discrimination
[Box & Hill, 1967]: discrimination entre structures demodèlesRéaction chimique A → B2 facteurs : u = (temps t, température T )réaction du 1er, 2ème, 3ème ou 4ème ordre ?
CEA Cadarache, 13 décembre 2005 – p.13/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Exemple 3 : discrimination
[Box & Hill, 1967]: discrimination entre structures demodèlesRéaction chimique A → B2 facteurs : u = (temps t, température T )réaction du 1er, 2ème, 3ème ou 4ème ordre ?→ 4 structures de modèles sont candidates :
η(1)(θ1,u) = exp[−θ11t exp(−θ12/T )] ,
η(2)(θ2,u) =1
1 + θ21t exp(−θ22/T ),
η(3)(θ3,u) =1
[1 + 2θ31t exp(−θ32/T )]1/2,
η(4)(θ4,u) =1
[1 + 3θ41t exp(−θ42/T )]1/3.
CEA Cadarache, 13 décembre 2005 – p.13/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Expérience simulée
Observations: 2ème structure, y(uj) = η(2)(θ2,uj) + εj,
avec θ2 = (400, 5000)⊤ la vraie valeur (inconnue) des
paramètres du modèle 2, (ǫj) i.i.d. N (0, σ2), σ = 0.05
Domaine expérimental admissible : 0 ≤ t ≤ 150,450 ≤ T ≤ 600
CEA Cadarache, 13 décembre 2005 – p.14/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Expérience simulée
Observations: 2ème structure, y(uj) = η(2)(θ2,uj) + εj,
avec θ2 = (400, 5000)⊤ la vraie valeur (inconnue) des
paramètres du modèle 2, (ǫj) i.i.d. N (0, σ2), σ = 0.05
Domaine expérimental admissible : 0 ≤ t ≤ 150,450 ≤ T ≤ 600
Plan séquentiel : après observation de y(uj), j = 1, . . . , k,
• estimer θki (MC) pour i = 1, 2, 3, 4
• calculer la probabilité a posteriori πi(k) que le modèle isoit correct pour i = 1, 2, 3, 4
Initialisation : πi(0) = 1/4, i = 1, . . . , 4 et u1, . . . ,u4 donnés
CEA Cadarache, 13 décembre 2005 – p.14/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
0 2 4 6 8 10 12 140
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
π2
π3
π4
π1
→ η(2)
Probabilités πi(k)
0 20 40 60 80 100 120 140 160440
460
480
500
520
540
560
580
600
1
2 3
4
6,9,12,14 10,11,13
5,7,8
Choix des facteurs uk
CEA Cadarache, 13 décembre 2005 – p.15/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Une méthode séquentielle simple pour choisir entre deux
structures η(1)(θ1,u) et η(2)(θ2,u) [Atkinson & Fedorov 1975]
Après l’observation de y(u1), . . . , y(uk) estimer θk1 et θk
2
pour les deux modèles
placer le nouveau point uk+1 là où
[η(1)(θk1 ,u) − η(2)(θk
2 ,u)]2 est maximum
k → k + 1, répéter
CEA Cadarache, 13 décembre 2005 – p.16/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Une méthode séquentielle simple pour choisir entre deux
structures η(1)(θ1,u) et η(2)(θ2,u) [Atkinson & Fedorov 1975]
Après l’observation de y(u1), . . . , y(uk) estimer θk1 et θk
2
pour les deux modèles
placer le nouveau point uk+1 là où
[η(1)(θk1 ,u) − η(2)(θk
2 ,u)]2 est maximum
k → k + 1, répéter
Si plus de 2 modèles : estimer θki pour tous, placer le
prochain point en utilisant les deux modèles reproduisant lemieux les données (voir [Atkinson & Cox 1974; Hill 1978]pour une synthèse)
CEA Cadarache, 13 décembre 2005 – p.16/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Planification et optimisation
Observations y(i) = η(θ,ui) + ǫi, erreurs (ǫi)i i.i.d. N (0, σ2)
Objectif : maximiser IEy = η(θ,u)
déterminer u∗ = u∗(θ) = arg maxu
η(θ,u)
CEA Cadarache, 13 décembre 2005 – p.17/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Planification et optimisation
Observations y(i) = η(θ,ui) + ǫi, erreurs (ǫi)i i.i.d. N (0, σ2)
Objectif : maximiser IEy = η(θ,u)
déterminer u∗ = u∗(θ) = arg maxu
η(θ,u)
→ estimer θ = θ[y], puis utiliser u∗(θ)Quel critère pour choisir l’expérience ?
CEA Cadarache, 13 décembre 2005 – p.17/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Planification et optimisation
Observations y(i) = η(θ,ui) + ǫi, erreurs (ǫi)i i.i.d. N (0, σ2)
Objectif : maximiser IEy = η(θ,u)
déterminer u∗ = u∗(θ) = arg maxu
η(θ,u)
→ estimer θ = θ[y], puis utiliser u∗(θ)Quel critère pour choisir l’expérience ?
• a) précision sur θ ?
CEA Cadarache, 13 décembre 2005 – p.17/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Planification et optimisation
Observations y(i) = η(θ,ui) + ǫi, erreurs (ǫi)i i.i.d. N (0, σ2)
Objectif : maximiser IEy = η(θ,u)
déterminer u∗ = u∗(θ) = arg maxu
η(θ,u)
→ estimer θ = θ[y], puis utiliser u∗(θ)Quel critère pour choisir l’expérience ?
• a) précision sur θ ?
• ou b) précision sur u∗(θ) ?
CEA Cadarache, 13 décembre 2005 – p.17/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Planification et optimisation
Observations y(i) = η(θ,ui) + ǫi, erreurs (ǫi)i i.i.d. N (0, σ2)
Objectif : maximiser IEy = η(θ,u)
déterminer u∗ = u∗(θ) = arg maxu
η(θ,u)
→ estimer θ = θ[y], puis utiliser u∗(θ)Quel critère pour choisir l’expérience ?
• a) précision sur θ ?
• ou b) précision sur u∗(θ) ?
• ou c) coût C(θ|θ)
par ex., C(θ|θ) = η[θ,u∗(θ)] − η[θ,u∗(θ)] ≥ 0
→ minimiser le risque bayésien R = IEC(θ[y]|θ)(espérance sur y et θ ∼ loi a priori π(·) )
CEA Cadarache, 13 décembre 2005 – p.17/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• a,b,c = planification «standard» : en 2 étapes1) choisir des ui pour l’estimation
2) estimer θ et construire u∗(θ)
Mais chaque η(θ,ui) est loin de l’optimum u∗ !(choisis pour estimer, pas pour optimiser)
CEA Cadarache, 13 décembre 2005 – p.18/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• a,b,c = planification «standard» : en 2 étapes1) choisir des ui pour l’estimation
2) estimer θ et construire u∗(θ)
Mais chaque η(θ,ui) est loin de l’optimum u∗ !(choisis pour estimer, pas pour optimiser)
• On veut parfois les deux à la fois : η(θ,ui) aussi grand quepossible pour tous les i→ choisir ui proche de u∗(θ) . . . qui est inconnu !
→ plan séquentiel
CEA Cadarache, 13 décembre 2005 – p.18/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• a,b,c = planification «standard» : en 2 étapes1) choisir des ui pour l’estimation
2) estimer θ et construire u∗(θ)
Mais chaque η(θ,ui) est loin de l’optimum u∗ !(choisis pour estimer, pas pour optimiser)
• On veut parfois les deux à la fois : η(θ,ui) aussi grand quepossible pour tous les i→ choisir ui proche de u∗(θ) . . . qui est inconnu !
→ plan séquentiel
· · · → ui → observer y(i) → estimer θi = θ(yi1) → ui+1 → · · ·
retour d’information↔ problème de contrôle (systèmedynamique)
CEA Cadarache, 13 décembre 2005 – p.18/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Chaque ui a deux objectifs :
1) aider à estimer θ2) essayer de maximiser η(θ,u) (doit être près de
u∗(θ))→ on parle de commande duale
CEA Cadarache, 13 décembre 2005 – p.19/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Chaque ui a deux objectifs :
1) aider à estimer θ2) essayer de maximiser η(θ,u) (doit être près de
u∗(θ))→ on parle de commande duale
On peut s’intéresser aux propriétés théoriquesasymptotiques (nb. de pas N → ∞)
CEA Cadarache, 13 décembre 2005 – p.19/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Chaque ui a deux objectifs :
1) aider à estimer θ2) essayer de maximiser η(θ,u) (doit être près de
u∗(θ))→ on parle de commande duale
On peut s’intéresser aux propriétés théoriquesasymptotiques (nb. de pas N → ∞)
ou rechercher une stratégie performante pour N finiles deux sont DIFFICILES !
CEA Cadarache, 13 décembre 2005 – p.19/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Optimisation «sans modèle» (on se rapproche dunon-paramétrique. . . )[Kiefer & Wolfowitz 1952]
on observe y(uk) = f(uk) + εk,stratégie [uk+1]i = [uk]i + γk
ck[y(uk + ck[e]i) − y(uk)], i = 1, . . . , d
avec γk, ck > 0, décroisssants,∑
k γk = ∞,∑
k γkck < ∞,∑
k γ2k/c2
k < ∞
CEA Cadarache, 13 décembre 2005 – p.20/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Optimisation «sans modèle» (on se rapproche dunon-paramétrique. . . )[Kiefer & Wolfowitz 1952]
on observe y(uk) = f(uk) + εk,stratégie [uk+1]i = [uk]i + γk
ck[y(uk + ck[e]i) − y(uk)], i = 1, . . . , d
avec γk, ck > 0, décroisssants,∑
k γk = ∞,∑
k γkck < ∞,∑
k γ2k/c2
k < ∞Converge vers un maximum local, mais lentement
(il faut beaucoup d’observations yi. . . )
CEA Cadarache, 13 décembre 2005 – p.20/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Optimisation «sans modèle» (on se rapproche dunon-paramétrique. . . )[Kiefer & Wolfowitz 1952]
on observe y(uk) = f(uk) + εk,stratégie [uk+1]i = [uk]i + γk
ck[y(uk + ck[e]i) − y(uk)], i = 1, . . . , d
avec γk, ck > 0, décroisssants,∑
k γk = ∞,∑
k γkck < ∞,∑
k γ2k/c2
k < ∞Converge vers un maximum local, mais lentement
(il faut beaucoup d’observations yi. . . )Pourquoi plan d’expériences ? A chaque pas, plan avecd + 1 points:
Uk = uk et uk + ck[e]i, i = 1, . . . , d
CEA Cadarache, 13 décembre 2005 – p.20/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
≃ estimation du gradient ∇uf par différences finies≃ approximation linéaire (en u) de f
CEA Cadarache, 13 décembre 2005 – p.21/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
≃ estimation du gradient ∇uf par différences finies≃ approximation linéaire (en u) de f
Méthode de la surface de réponse : [Box & Wilson 1951]utilise des modèles linéaires et/ou quadratiques en u
CEA Cadarache, 13 décembre 2005 – p.21/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
≃ estimation du gradient ∇uf par différences finies≃ approximation linéaire (en u) de f
Méthode de la surface de réponse : [Box & Wilson 1951]utilise des modèles linéaires et/ou quadratiques en u
Remarques TRES IMPORTANTES en paramérique :• Pour un modèle paramétrique donné, un plan optimalconduit à répéter des observations toujours aux mêmespoints (conséquence du Th. de Caratheodory)
CEA Cadarache, 13 décembre 2005 – p.21/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
≃ estimation du gradient ∇uf par différences finies≃ approximation linéaire (en u) de f
Méthode de la surface de réponse : [Box & Wilson 1951]utilise des modèles linéaires et/ou quadratiques en u
Remarques TRES IMPORTANTES en paramérique :• Pour un modèle paramétrique donné, un plan optimalconduit à répéter des observations toujours aux mêmespoints (conséquence du Th. de Caratheodory)• Ce sont les points qui apportent le plus d’information surle modèle (sur ses paramètres)
CEA Cadarache, 13 décembre 2005 – p.21/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
≃ estimation du gradient ∇uf par différences finies≃ approximation linéaire (en u) de f
Méthode de la surface de réponse : [Box & Wilson 1951]utilise des modèles linéaires et/ou quadratiques en u
Remarques TRES IMPORTANTES en paramérique :• Pour un modèle paramétrique donné, un plan optimalconduit à répéter des observations toujours aux mêmespoints (conséquence du Th. de Caratheodory)• Ce sont les points qui apportent le plus d’information surle modèle (sur ses paramètres)• Ce sont les points où notre prédiction du comportementdu modèle est la plus incertaine (conséquence du Th.d’équivalence de Kiefer-Wolfowitz [1960])
CEA Cadarache, 13 décembre 2005 – p.21/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Relie l’optimalité dans l’espace des paramètres θ àl’optimalité dans l’espace des réponses y
quand N → ∞
Nvar[θN ] → M−1F (ξ, θ)
Nvar[η(θN , u)] → ∂η(θ,u)∂θ⊤ M−1
F (ξ, θ)∂η(θ,u)∂θ
CEA Cadarache, 13 décembre 2005 – p.22/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Relie l’optimalité dans l’espace des paramètres θ àl’optimalité dans l’espace des réponses y
quand N → ∞
Nvar[θN ] → M−1F (ξ, θ)
Nvar[η(θN , u)] → ∂η(θ,u)∂θ⊤ M−1
F (ξ, θ)∂η(θ,u)∂θ
Doptimalité ⇔ G-optimality
ξD minimise detM−1F (ξ, θ) et minimise le maximum de la
variance de la prédiction sur le domaine expérimental U
η(θ, u), η(θ, u)± 2σ
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2−0.2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
CEA Cadarache, 13 décembre 2005 – p.22/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
5) Modèles non-paramétriques
Plan d’expériences : apprentissage actifA partir de données «d’apprentissage»D = [u1, y(u1)], . . . , [uN , y(uN )] on souhaite prédirey(u) pour un nouveau u par un modèle non-paramétrique(beaucoup de paramètres, mais sans intérêt) :réseau de neurones, machine à vecteurs de support(SVM), estimateur de Nadaraya-Watson, splines, krigeage(Kriging) (= processus gaussien), etc.
CEA Cadarache, 13 décembre 2005 – p.23/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
5) Modèles non-paramétriques
Plan d’expériences : apprentissage actifA partir de données «d’apprentissage»D = [u1, y(u1)], . . . , [uN , y(uN )] on souhaite prédirey(u) pour un nouveau u par un modèle non-paramétrique(beaucoup de paramètres, mais sans intérêt) :réseau de neurones, machine à vecteurs de support(SVM), estimateur de Nadaraya-Watson, splines, krigeage(Kriging) (= processus gaussien), etc.
yD(u) est la prédiction en u
y = [y(u1), . . . , y(uN )]⊤ est le vecteurs des observationsdisponibles
CEA Cadarache, 13 décembre 2005 – p.23/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
1) Réseau de neurones, une couche cachée (RBF)
yD(u) =∑N
k=1 akK(u − uk), par ex. K(z) = 1h√
2πexp
(
− z2
2h2
)
→ les nœuds coincident avec les facteurs uk
Soit a = (a1, . . . , aN )⊤
a minimise γ∑N
k=1[y(uk) − yD(uk)]2 + a⊤Ga
→ (G + I/γ)a = y avec Gi,j = K(ui − uj)
CEA Cadarache, 13 décembre 2005 – p.24/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
1) Réseau de neurones, une couche cachée (RBF)
yD(u) =∑N
k=1 akK(u − uk), par ex. K(z) = 1h√
2πexp
(
− z2
2h2
)
→ les nœuds coincident avec les facteurs uk
Soit a = (a1, . . . , aN )⊤
a minimise γ∑N
k=1[y(uk) − yD(uk)]2 + a⊤Ga
→ (G + I/γ)a = y avec Gi,j = K(ui − uj)
Version paramétrique : M nœuds Ni fixés, i = 1, . . . , Mrépartis dans U
• prédire par yD(u) =∑M
i=1 aiK(u − Ni)
• estimer a par MC : a = arg mina
∑Nk=1[y(uk) − yD(uk)]
2
(modèle linéaire comme dans l’exemple 1)
CEA Cadarache, 13 décembre 2005 – p.24/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
2) Nadaraya [1964] & Watson [1964]: lissage local
yD(u) =1
G(u)
N∑
i=1
K(u − ui)y(ui)
avec G(u) =∑N
i=1 K(u − ui) et K(·) un noyau symétrique
unimodal (par ex. la densité de la loi normale)
CEA Cadarache, 13 décembre 2005 – p.25/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
3) SVM (voir par ex. [Suykens et al., 2002]
prédiction yD(u) = φ⊤(u)θ, dim(θ) = p très grande(éventuellement ∞ → modèle linéaire de dim. infinie)
CEA Cadarache, 13 décembre 2005 – p.26/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
3) SVM (voir par ex. [Suykens et al., 2002]
prédiction yD(u) = φ⊤(u)θ, dim(θ) = p très grande(éventuellement ∞ → modèle linéaire de dim. infinie)Classique : modèle non-paramétrique ⇒ beaucoup deparamètres !
CEA Cadarache, 13 décembre 2005 – p.26/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
3) SVM (voir par ex. [Suykens et al., 2002]
prédiction yD(u) = φ⊤(u)θ, dim(θ) = p très grande(éventuellement ∞ → modèle linéaire de dim. infinie)Classique : modèle non-paramétrique ⇒ beaucoup deparamètres !
Pour fθ(u) =∑∞
i=1 θiφi(u) on définit
〈fθ(·), fθ′(·)〉 = produit scalaire entre fθ(·) et fθ′(·)=∑∞
i=1 θiθ′i
→ RKHS (Reproducing Kernel Hilbert Space), avec des
noyaux K(x, z) =∑∞
i=1 φi(x)φi(z)et
〈fθ(·), K(·, z)〉 = fθ(z)
〈K(x, ·), K(·, z)〉 = K(x, z)
CEA Cadarache, 13 décembre 2005 – p.26/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Choisir θ qui minimise γ∑N
k=1 L[yk − θ⊤φ(uk)] + 12‖θ‖
2
θ satisfait −∑N
k=1 γL′[yk − θ⊤φ(uk)]︸ ︷︷ ︸
=ak
φi(uk)+ θi = 0, pour tout i
→ θi =∑N
k=1 akφi(uk), pour tout i
CEA Cadarache, 13 décembre 2005 – p.27/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Choisir θ qui minimise γ∑N
k=1 L[yk − θ⊤φ(uk)] + 12‖θ‖
2
θ satisfait −∑N
k=1 γL′[yk − θ⊤φ(uk)]︸ ︷︷ ︸
=ak
φi(uk)+ θi = 0, pour tout i
→ θi =∑N
k=1 akφi(uk), pour tout i
Prédiction en u : (Th. de représentation)
yD(u) = θ⊤φ(u) =∑∞
i=1 θiφi(u) =∑N
k=1 ak
∞∑
i=1
φi(uk)φi(u)
︸ ︷︷ ︸
=K(uk,u)
avec les ak qui satisfont
ak = γL′[
yk −∑N
i=1 aiK(ui, uk)]
CEA Cadarache, 13 décembre 2005 – p.27/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Choisir θ qui minimise γ∑N
k=1 L[yk − θ⊤φ(uk)] + 12‖θ‖
2
θ satisfait −∑N
k=1 γL′[yk − θ⊤φ(uk)]︸ ︷︷ ︸
=ak
φi(uk)+ θi = 0, pour tout i
→ θi =∑N
k=1 akφi(uk), pour tout i
Prédiction en u : (Th. de représentation)
yD(u) = θ⊤φ(u) =∑∞
i=1 θiφi(u) =∑N
k=1 ak
∞∑
i=1
φi(uk)φi(u)
︸ ︷︷ ︸
=K(uk,u)
avec les ak qui satisfont
ak = γL′[
yk −∑N
i=1 aiK(ui, uk)]
Soit a = (a1, . . . , aN )⊤
Différentes fonctions de coût L → différentes méthodes pourchoisir a
CEA Cadarache, 13 décembre 2005 – p.27/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• LS-SVM [Suykens et al., 2002]: L(u) = u2/2 et a satisfait
[Ω + I/γ]a = y, avec Ωi,j = K(ui, uj)
CEA Cadarache, 13 décembre 2005 – p.28/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• LS-SVM [Suykens et al., 2002]: L(u) = u2/2 et a satisfait
[Ω + I/γ]a = y, avec Ωi,j = K(ui, uj)
• Coût SVM classique : L(x) = ǫ + max|x| − ǫ, 0 (nondifférentiable)
0 +ǫ−ǫ
a obtenu par résolution d’unproblème convexe
⇒ de nombreux ak valent zéro dans
yD(u) =∑N
k=1 akK(uk, u)ceux 6= 0 → les «vecteurs de support» uk
CEA Cadarache, 13 décembre 2005 – p.28/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
On peut travailler directement avec K(u, z)Condition sur K ?
CEA Cadarache, 13 décembre 2005 – p.29/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
On peut travailler directement avec K(u, z)Condition sur K ?
Mercer :∫
K(u, z)g(u)g(z) du dz ≥ 0 pour tout g(·) dans L2
(pour définir un produit salaire)→ considérer K(u, z) comme la covariance d’un processusdans l’espace des u
CEA Cadarache, 13 décembre 2005 – p.29/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
On peut travailler directement avec K(u, z)Condition sur K ?
Mercer :∫
K(u, z)g(u)g(z) du dz ≥ 0 pour tout g(·) dans L2
(pour définir un produit salaire)→ considérer K(u, z) comme la covariance d’un processusdans l’espace des u
• Espace hilbertien engendré par une fonction decovariance• Processus aléatoire à trajectoires dans un RKHS
CEA Cadarache, 13 décembre 2005 – p.29/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Processus gaussien & krigeage (voir par ex. [Stein1999])
Modèle y(uk) = θ0 + P (uk, ω) + ε(uk) avec
CEA Cadarache, 13 décembre 2005 – p.30/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Processus gaussien & krigeage (voir par ex. [Stein1999])
Modèle y(uk) = θ0 + P (uk, ω) + ε(uk) avec
• P (u, ω) un processus stationnaire du second-ordre,
de covariance IEP (u, ω)P (z, ω) = K(u, z) = σ2P C(u − z)
CEA Cadarache, 13 décembre 2005 – p.30/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Processus gaussien & krigeage (voir par ex. [Stein1999])
Modèle y(uk) = θ0 + P (uk, ω) + ε(uk) avec
• P (u, ω) un processus stationnaire du second-ordre,
de covariance IEP (u, ω)P (z, ω) = K(u, z) = σ2P C(u − z)
• (εk) des erreurs i.i.d., de moyenne nulle et de variance σ2
CEA Cadarache, 13 décembre 2005 – p.30/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
4) Processus gaussien & krigeage (voir par ex. [Stein1999])
Modèle y(uk) = θ0 + P (uk, ω) + ε(uk) avec
• P (u, ω) un processus stationnaire du second-ordre,
de covariance IEP (u, ω)P (z, ω) = K(u, z) = σ2P C(u − z)
• (εk) des erreurs i.i.d., de moyenne nulle et de variance σ2
On définit la matrice CP (N × N ) par [CP ]i,j = C(ui − uj)
CEA Cadarache, 13 décembre 2005 – p.30/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Krigeage : meilleur prédicteur linéaire sans biais en u:
yD(u) = v⊤(u)y
v(u) minimise IE(v⊤y − [θ0 + P (u, ω)])2 sous la contrainte
IEv⊤y = θ0∑N
i=1 vi = IEy(u) = θ0 ⇒∑N
i=1 vi = 1
Solution explicite !
CEA Cadarache, 13 décembre 2005 – p.31/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Krigeage : meilleur prédicteur linéaire sans biais en u:
yD(u) = v⊤(u)y
v(u) minimise IE(v⊤y − [θ0 + P (u, ω)])2 sous la contrainte
IEv⊤y = θ0∑N
i=1 vi = IEy(u) = θ0 ⇒∑N
i=1 vi = 1
Solution explicite !
Posons Cy = σ2IN + σ2PCP , 1 = ( 1, . . . , 1
︸ ︷︷ ︸
N termes
)⊤
c(u) = σ2P [C(u − u1), . . . , C(u − uN )]⊤
θ0 =1⊤
C−1
y y
1⊤
C−1y 1
(estimateur des MC pondérés de θ0)
alors, yD(u) = v⊤(u)y = θ0 + c⊤(u)C−1y (y − θ01)
( = θ0 +∑N
k=1 akK(u, uk) )
CEA Cadarache, 13 décembre 2005 – p.31/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
De plus, erreur quadratique moyenne (EQM) de laprédiction yD(u) en u :
ρ2D(u) = σ2
P −[
c⊤(u) 1][
Cy 1
1⊤ 0
]−1 [
c(u)
1
]
et, si σ2 = 0 (pas d’erreur de mesure εk)
yD(ui) = y(ui) et ρ2D(ui) = 0 pour tout i
⇒ yD(u) est un interpolateur parfait !
CEA Cadarache, 13 décembre 2005 – p.32/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
De plus, erreur quadratique moyenne (EQM) de laprédiction yD(u) en u :
ρ2D(u) = σ2
P −[
c⊤(u) 1][
Cy 1
1⊤ 0
]−1 [
c(u)
1
]
et, si σ2 = 0 (pas d’erreur de mesure εk)
yD(ui) = y(ui) et ρ2D(ui) = 0 pour tout i
⇒ yD(u) est un interpolateur parfait !
Erreurs de modèle = processus aléatoire→ inférence statistique même pour un systèmepurement déterministe
aussi quand expérience = simulation (ex. éléments finis)— computer experiments — [Sacks et al., 1989]
CEA Cadarache, 13 décembre 2005 – p.32/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
0 5 10 15−2
−1.5
−1
−0.5
0
0.5
1
1.5
2
2.5
processus y(u)prédiction yD(u)et yD(u) ± 2ρD(u)
CEA Cadarache, 13 décembre 2005 – p.33/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
0 5 10 15−2
−1.5
−1
−0.5
0
0.5
1
1.5
2
2.5
processus y(u)prédiction yD(u)et yD(u) ± 2ρD(u)
Si le processus P (u, ω) et les erreurs εk appartiennent àune famille paramétrée → estimer les paramètres
Par ex., processus gaussien avec C(z) = C(β, z) + erreursnormales εk
→ estimer β, σ2P et σ2 par Maximum de Vraisemblance
CEA Cadarache, 13 décembre 2005 – p.33/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Extensions :1) Remplacer la moyenne constante θ0 par un modèle
linéaire r⊤(u)θ• meilleur prédicteur linéaire sans biais → krigeageuniversel• processus généralisé, covariances généralisées, fonctionaléatoires intrinsèques (permet d’étendre la classe desfonctions de covariance que l’on peut utiliser, équivalenceavec les splines [Vasquez, 2005])
CEA Cadarache, 13 décembre 2005 – p.34/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Extensions :1) Remplacer la moyenne constante θ0 par un modèle
linéaire r⊤(u)θ• meilleur prédicteur linéaire sans biais → krigeageuniversel• processus généralisé, covariances généralisées, fonctionaléatoires intrinsèques (permet d’étendre la classe desfonctions de covariance que l’on peut utiliser, équivalenceavec les splines [Vasquez, 2005])
2) Mettre une loi a priori sur θ (krigeage bayesien)
CEA Cadarache, 13 décembre 2005 – p.34/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Extensions :1) Remplacer la moyenne constante θ0 par un modèle
linéaire r⊤(u)θ• meilleur prédicteur linéaire sans biais → krigeageuniversel• processus généralisé, covariances généralisées, fonctionaléatoires intrinsèques (permet d’étendre la classe desfonctions de covariance que l’on peut utiliser, équivalenceavec les splines [Vasquez, 2005])
2) Mettre une loi a priori sur θ (krigeage bayesien)
3) Prédire la dérivée de y(u) (ou prédire y(u) à partird’observations de la dérivée aux points ui) [Vasquez, 2005]
CEA Cadarache, 13 décembre 2005 – p.34/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
6) Planification en non paramétrique
où placer les uk ?
CEA Cadarache, 13 décembre 2005 – p.35/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
6) Planification en non paramétrique
où placer les uk ?A) APPROCHE SANS MODÈLE : remplir l’espace• u ∈ U = espace admissible,• S ⊂ U les sites choisis uk, k = 1, . . . , N
CEA Cadarache, 13 décembre 2005 – p.35/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
6) Planification en non paramétrique
où placer les uk ?A) APPROCHE SANS MODÈLE : remplir l’espace• u ∈ U = espace admissible,• S ⊂ U les sites choisis uk, k = 1, . . . , N[Johnson et al., 1990]:• distance maximin :
maxS minu 6=u′∈S2 d(u, u′)⇒ étaler les uk autant que possible sur U(→ points sur les bords de U)
CEA Cadarache, 13 décembre 2005 – p.35/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
6) Planification en non paramétrique
où placer les uk ?A) APPROCHE SANS MODÈLE : remplir l’espace• u ∈ U = espace admissible,• S ⊂ U les sites choisis uk, k = 1, . . . , N[Johnson et al., 1990]:• distance maximin :
maxS minu 6=u′∈S2 d(u, u′)⇒ étaler les uk autant que possible sur U(→ points sur les bords de U)
• distance minimax : pour U un ensemble finiminS maxz∈U min
u∈Sd(z, u)
︸ ︷︷ ︸
=d(z,S) CEA Cadarache, 13 décembre 2005 – p.35/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Pour assurer de bonnes propriétés de projection (pourchaque coordonnée de u) : travailler dans la classe desHypercubes Latins [Morris & Mitchell 1995]
U = [0, 1]d, les [uk]i, k = 1, . . . , N , prennent les valeurs0, 1/(N − 1), 2/(N − 1), . . . , 1, pour chaque i = 1, . . . , d
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
CEA Cadarache, 13 décembre 2005 – p.36/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
B) APPROCHE AVEC MODÈLE :
Il faut une caractérisation de l’incertitude sur yD(u)
CEA Cadarache, 13 décembre 2005 – p.37/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
B) APPROCHE AVEC MODÈLE :
Il faut une caractérisation de l’incertitude sur yD(u)
Soit ρD(u) = EQM(u) = IE[yD(u) − y(u)]2 − σ2
(IE porte sur y et y(u))
Une question générale en non paramétrique :
Comment décroît EQM(u) quand N augmente ?
CEA Cadarache, 13 décembre 2005 – p.37/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
B) APPROCHE AVEC MODÈLE :
Il faut une caractérisation de l’incertitude sur yD(u)
Soit ρD(u) = EQM(u) = IE[yD(u) − y(u)]2 − σ2
(IE porte sur y et y(u))
Une question générale en non paramétrique :
Comment décroît EQM(u) quand N augmente ?
. . . pas évident ! l’effet est local : on observe en u,⇒ ρD(z) décroît pour z près de u
(krigeage sans erreur de mesure : ρD(u) devient 0)
mais peu de changement loin de u. . .
CEA Cadarache, 13 décembre 2005 – p.37/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Hypothèse classique :D forme une suite de paires i.i.d. [uk, y(uk)], voir par ex.[Cucker & Smale 2001; Bartlett 2003] → pas deplanification
CEA Cadarache, 13 décembre 2005 – p.38/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Hypothèse classique :D forme une suite de paires i.i.d. [uk, y(uk)], voir par ex.[Cucker & Smale 2001; Bartlett 2003] → pas deplanification
Planification difficile, peu de résultats précis. . .[Cheng et al., 1998] : répartir les ui ∈ IR avec une densité
de probabilité proportionnelle à |y′′(u)|2/9
CEA Cadarache, 13 décembre 2005 – p.38/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Hypothèse classique :D forme une suite de paires i.i.d. [uk, y(uk)], voir par ex.[Cucker & Smale 2001; Bartlett 2003] → pas deplanification
Planification difficile, peu de résultats précis. . .[Cheng et al., 1998] : répartir les ui ∈ IR avec une densité
de probabilité proportionnelle à |y′′(u)|2/9
. . . Pour le krigeage, on peut utiliser EQM(u) = ρ2D(u)
CEA Cadarache, 13 décembre 2005 – p.38/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• S minimise l’EQM maximale = maxu∈U ρ2D(u)
(lié à la distance minimax, [Johnson et al., 1990])
CEA Cadarache, 13 décembre 2005 – p.39/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• S minimise l’EQM maximale = maxu∈U ρ2D(u)
(lié à la distance minimax, [Johnson et al., 1990])ou• S minimise l’EQM moyenne =
∫
U ρ2D(u) π(du)
(π une mesure de probabilité pour u)
CEA Cadarache, 13 décembre 2005 – p.39/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• S minimise l’EQM maximale = maxu∈U ρ2D(u)
(lié à la distance minimax, [Johnson et al., 1990])ou• S minimise l’EQM moyenne =
∫
U ρ2D(u) π(du)
(π une mesure de probabilité pour u)ou• Maximum Entropy Sampling : [Shewry & Wynn 1987,Wynn 2004]Soit entY = −
∫log ϕ(Y )ϕ(Y )dY
YA = y(u) pour u ∈ A (et donc YS = y = vecteur desobservations)
CEA Cadarache, 13 décembre 2005 – p.39/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
• S minimise l’EQM maximale = maxu∈U ρ2D(u)
(lié à la distance minimax, [Johnson et al., 1990])ou• S minimise l’EQM moyenne =
∫
U ρ2D(u) π(du)
(π une mesure de probabilité pour u)ou• Maximum Entropy Sampling : [Shewry & Wynn 1987,Wynn 2004]Soit entY = −
∫log ϕ(Y )ϕ(Y )dY
YA = y(u) pour u ∈ A (et donc YS = y = vecteur desobservations)
Une approche bayesienne minimiserait l’espérance del’entropie a posteriori
IEent(YU\S |YS) . . . ce qui est difficile
CEA Cadarache, 13 décembre 2005 – p.39/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
On décompose l’entropie enent(YU ) = ent(YS) + IEent(YU\S |YS), puisque ent(YU ) est
fixée, choisir S qui maximise ent(YS)
CEA Cadarache, 13 décembre 2005 – p.40/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
On décompose l’entropie enent(YU ) = ent(YS) + IEent(YU\S |YS), puisque ent(YU ) est
fixée, choisir S qui maximise ent(YS)
Pour le krigeage avec processus gaussien et sans erreursde mesure («computer experiments»)
⇒ maximiser det(CP ), avec [CP ]i,j = C(ui − uj)
(lié à la distance maximin, [Johnson et al., 1990])
CEA Cadarache, 13 décembre 2005 – p.40/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
On décompose l’entropie enent(YU ) = ent(YS) + IEent(YU\S |YS), puisque ent(YU ) est
fixée, choisir S qui maximise ent(YS)
Pour le krigeage avec processus gaussien et sans erreursde mesure («computer experiments»)
⇒ maximiser det(CP ), avec [CP ]i,j = C(ui − uj)
(lié à la distance maximin, [Johnson et al., 1990])
• Application du krigeage à l’optimisation globale dans lapartie VII
CEA Cadarache, 13 décembre 2005 – p.40/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Remarque : différence avec modèle paramétrique
y(uk) = η(θ, uk) + εk
η(θ, u) est fixé (pas modifié quand d’autres uk sont utilisés)
Même problème : choisir des facteurs UN1 = (u1, . . . , uN )
assurant une «bonne prédiction» yD(u) quand u ∈ U ⊂ IRd
CEA Cadarache, 13 décembre 2005 – p.41/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Remarque : différence avec modèle paramétrique
y(uk) = η(θ, uk) + εk
η(θ, u) est fixé (pas modifié quand d’autres uk sont utilisés)
Même problème : choisir des facteurs UN1 = (u1, . . . , uN )
assurant une «bonne prédiction» yD(u) quand u ∈ U ⊂ IRd
EQM(u) = IE[yD(u) − y(u)]2 − σ2
(espérance sur y(u) et D pour UN1 fixé)
La variance domine le carré du biais, et
EQM(u) ≃ IE[yD(u) − IEyD(u)]2︸ ︷︷ ︸
V (u|UN1
)
Ici yD(u) = η(θN , u) avec θN estimé à partir de D, et
V (u|UN1 ) est relié à Var(θN ), décroît en 1/N , pour tout u!
CEA Cadarache, 13 décembre 2005 – p.41/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
Remarque : différence avec modèle paramétrique
y(uk) = η(θ, uk) + εk
η(θ, u) est fixé (pas modifié quand d’autres uk sont utilisés)
Même problème : choisir des facteurs UN1 = (u1, . . . , uN )
assurant une «bonne prédiction» yD(u) quand u ∈ U ⊂ IRd
EQM(u) = IE[yD(u) − y(u)]2 − σ2
(espérance sur y(u) et D pour UN1 fixé)
La variance domine le carré du biais, et
EQM(u) ≃ IE[yD(u) − IEyD(u)]2︸ ︷︷ ︸
V (u|UN1
)
Ici yD(u) = η(θN , u) avec θN estimé à partir de D, et
V (u|UN1 ) est relié à Var(θN ), décroît en 1/N , pour tout u!
modèle paramétrique ⇒ θN a un effet global sur yD(u)
CEA Cadarache, 13 décembre 2005 – p.41/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
7) Optimisation globale et krigeage
On veut maximiser y(u), on observe (sans erreur) en des ui
que l’on choisitComment les choisir au mieux ?
Krigeage → EQM de la prédiction en u = ρ2D(u)
CEA Cadarache, 13 décembre 2005 – p.42/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
7) Optimisation globale et krigeage
On veut maximiser y(u), on observe (sans erreur) en des ui
que l’on choisitComment les choisir au mieux ?
Krigeage → EQM de la prédiction en u = ρ2D(u)
Approche bayesienne, après observation deDk = [u1, y(u1)], . . . , [uk, y(uk)], y(u) est distribué avec la
densité ϕ(y|Dk, u) de la loi normale N (yDk(u), ρ2
Dk(u))
CEA Cadarache, 13 décembre 2005 – p.42/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
7) Optimisation globale et krigeage
On veut maximiser y(u), on observe (sans erreur) en des ui
que l’on choisitComment les choisir au mieux ?
Krigeage → EQM de la prédiction en u = ρ2D(u)
Approche bayesienne, après observation deDk = [u1, y(u1)], . . . , [uk, y(uk)], y(u) est distribué avec la
densité ϕ(y|Dk, u) de la loi normale N (yDk(u), ρ2
Dk(u))
Stratégie optimale (algorithme) → problème deProgrammation Dynamique Stochastique. . .. . . que l’on ne sait pas résoudre !
CEA Cadarache, 13 décembre 2005 – p.42/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
[Mockus et al. 1978, Mockus 1989, Schonlau et al. 1998,Jones et al. 1998] → approximation à un pas, «expectedimprovement»
uk+1 maximizes EI(u) =∫∞ymax
k[y − ymax
k ]ϕ(y|Dk, u)dy
avec ymaxk la valeur maximale des y(ui) observés
CEA Cadarache, 13 décembre 2005 – p.43/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
[Mockus et al. 1978, Mockus 1989, Schonlau et al. 1998,Jones et al. 1998] → approximation à un pas, «expectedimprovement»
uk+1 maximizes EI(u) =∫∞ymax
k[y − ymax
k ]ϕ(y|Dk, u)dy
avec ymaxk la valeur maximale des y(ui) observés
• Converge vers l’optimum global de y(u) (on va finir parobserver partout)
CEA Cadarache, 13 décembre 2005 – p.43/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
[Mockus et al. 1978, Mockus 1989, Schonlau et al. 1998,Jones et al. 1998] → approximation à un pas, «expectedimprovement»
uk+1 maximizes EI(u) =∫∞ymax
k[y − ymax
k ]ϕ(y|Dk, u)dy
avec ymaxk la valeur maximale des y(ui) observés
• Converge vers l’optimum global de y(u) (on va finir parobserver partout)
• Il faut résoudre un problème d’optimisation globale àchaque itération (mais sans calculer y en de nouveauxpoints)
CEA Cadarache, 13 décembre 2005 – p.43/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
[Mockus et al. 1978, Mockus 1989, Schonlau et al. 1998,Jones et al. 1998] → approximation à un pas, «expectedimprovement»
uk+1 maximizes EI(u) =∫∞ymax
k[y − ymax
k ]ϕ(y|Dk, u)dy
avec ymaxk la valeur maximale des y(ui) observés
• Converge vers l’optimum global de y(u) (on va finir parobserver partout)
• Il faut résoudre un problème d’optimisation globale àchaque itération (mais sans calculer y en de nouveauxpoints)
• Les points «intéressants» sont loin de ceux déjà utilisés→ initialiser la recherche au centre des simplexes d’unetriangulation de Delaunay [Bates & Pronzato 2001]
CEA Cadarache, 13 décembre 2005 – p.43/44
CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE
0 0.2 0.4 0.6 0.8 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Possibilité d’utiliser une information sur les dérivées [Learyet al., 2004]
CEA Cadarache, 13 décembre 2005 – p.44/44
44-1
References
A.C. Atkinson and D.R. Cox. Planning experiments for discriminatingbetween models (with discussion). Journal of Royal Statistical Society,B36:321–348, 1974.
A.C. Atkinson and V.V. Fedorov. The design of experiments fordiscriminating between two rival models. Biometrika, 62(1):57–70, 1975.
A.C. Atkinson and V.V. Fedorov. Optimal design: experiments fordiscriminating between several models. Biometrika, 62(2):289–303, 1975.
P.L. Bartlett. Prediction algorithms: complexity, concentration andconvexity. In Prep. 13th IFAC Symposium on System Identification,Rotterdam, pages 1507–1517, August 2003.
R. Bates and L. Pronzato. Emulator-based global optimisation usinglattices and Delaunay tesselation. In P. Prado and R. Bolado, editors,Proc. 3rd Int. Symp. on Sensitivity Analysis of Model Output, pages 189–192,Madrid, June 2001.
G.E.P. Box and W.J. Hill. Discrimination among mechanistic models.Technometrics, 9(1):57–71, 1967.
44-1
G.E.P. Box and K.B. Wilson. On the experimental attainment ofoptimum conditions (with discussion). Journal of Royal Statistical Society,B13(1):1–45, 1951.
M.-Y. Cheng, P. Hall and M. Titterington. Optimal design for curveestimation by local linear smoothing. Bernoulli, 4(1):3–14, 1998.
F. Cucker and S. Smale. On the mathematical foundations of learning.Bulletin of the AMS, 39(1):1–49, 2001.
D.Z. D’Argenio. Optimal sampling times for pharmacokineticexperiments. Journal of Pharmacokinetics and Biopharmaceutics,9(6):739–756, 1981.
R.A. Fisher. Statistical Methods for Research Workers. Oliver & Boyd,Edimbourgh, 1925.
P.D.H. Hill. A review of experimental design procedures for regressionmodel discrimination. Technometrics, 20:15–21, 1978.
M.E. Johnson, L.M. Moore, and D. Ylvisaker. Minimax and maximindistance designs. Journal of Statistical Planning and Inference, 26:131–148,1990.
44-1
D. Jones, M. Schonlau and W.J. Welch. Efficient global optimization ofexpensive black-box functions. J. Global Optimization, 13:455–492, 1998.
J. Kiefer and J. Wolfowitz. Stochastic estimation of the maximum of aregression function. Annals of Math. Stat., 23:462–466, 1952.
J. Kiefer and J. Wolfowitz. The equivalence of two extremum problems.Canadian Journal of Mathematics, 12:363–366, 1960.
S. Leary, A. Bhaskar and A.J. Keane. A derivative based surrogate modelfor approximating and optimizing the output of an expensive computersimulation. J. Global Optimization, 30:39–58, 2004.
J. Mockus. Bayesian Approach to Global Optimization, Theory andApplications. Kluwer, Dordrecht, 1989.
J. Mockus, V. Tiesis, and A. Zilinskas. The application of Bayesianmethods for seeking the extremum. In L.C.W. Dixon and G.P. Szego,editors, Towards Global Optimisation 2, pages 117–129. North Holland,Amsterdam, 1978.
M.D. Morris and T.J. Mitchell. Exploratory designs for computationalexperiments. Journal of Statistical Planning and Inference, 43:381–402, 1995.
44-1
E.A. Nadaraya. On estimating regression. Theory of Probability and itsApplications, 9:141–142, 1964.
A. Pázman and L. Pronzato. A Dirac function method for densities ofnonlinear statistics and for marginal densities in nonlinear regression.Statistics & Probability Letters, 26:159–167, 1996.
J. Sacks, W.J. Welch, T.J. Mitchell, and H.P. Wynn. Design and analysis ofcomputer experiments (with discussion). Statistical Science, 4(4):409–435,1989.
M. Schonlau, W.J. Welch, and D.R. Jones. Global versus local search inconstrained optimization of computer models. In New Developments andApplications in Experimental Design, Lecture Notes — Monograph Series, vol.34, pages 11–25. IMS, Hayward, 1998.
M.C. Shewry and H.P. Wynn. Maximum entropy sampling. AppliedStatistics, 14:165–170, 1987.
M.L. Stein. Interpolation of Spatial Data. Some Theory for Kriging. Springer,Heidelberg, 1999.
J.A.K. Suykens, T. Van Gestel, J. De Brabanter, B. De Moor, andJ. Vandewalle. Least Squares Support vector Machines. World Scientific,New Jersey, 2002.
44-1
E. Vasquez. Modélisation comportementale de systèmes non-linéairesmultivariables par méthodes à noyaux et applications. Thèse de doctorat,université Paris XI Orsay, mai 2005.
G.S. Watson. Smooth regression analysis. Sankhya, Series A, 26:359–372,1964.
H.P. Wynn. Maximum entropy sampling and general equivalencetheory. In A. Di Bucchianico, H. Läuter, and H.P. Wynn, editors, mODa’7– Advances in Model–Oriented Design and Analysis, Proceedings of the 7thInt. Workshop, Heeze (Netehrlands), pages 211–218. Physica Verlag,Heidelberg, June 2004.
44-1
Recommended