Skip to Content
Découvrez les nouveautés de cette version : Fonctionnalités, améliorations et évolutions vous attendent ! 👉 Cliquez ici pour en savoir plus

Code source wiki de Monte Carlo Methods

Modifié par Rémi Peyre le 02/05/2025 - 15:32
Afficher les derniers auteurs
1 (% class="relative-table wrapped" style="width:100.0%" %)
2 |(% class="highlight-#fff0b3" colspan="11" data-highlight-colour="#fff0b3" rowspan="3" style="text-align:left" title="Couleur d'arrière-plan : Jaune clair 100 %" %)(((
3 (% style="color:#000080" %)**Monte Carlo Methods**
4
5 (% style="color:#000080" %)**8KUAAN11**
6 )))|(% colspan="2" style="text-align:center" %)(((
7 **ECTS**
8 )))|(% class="highlight-#fff0b3" data-highlight-colour="#fff0b3" style="text-align:center" title="Couleur d'arrière-plan : Jaune clair 100 %" %)(((
9 **2**
10 )))|(% colspan="3" style="text-align:center" %)(((
11 **SEMESTER**
12 )))|(% class="highlight-#fff0b3" data-highlight-colour="#fff0b3" style="text-align:center" title="Couleur d'arrière-plan : Jaune clair 100 %" %)(((
13 **S8**
14 )))
15 |(% style="text-align:center" %)(((
16 lectures
17 )))|(% style="text-align:center" %)(((
18 classes / seminars
19 )))|(% style="text-align:center" %)(((
20 practical work
21 )))|(% style="text-align:center" %)(((
22 integrative teaching
23 )))|(% colspan="3" style="text-align:center" %)(((
24 independent work
25 )))
26 |(% style="text-align:center" %)(((
27 7 h
28 )))|(% style="text-align:center" %)(((
29 14 h
30 )))|(% style="text-align:center" %)(((
31 0 h
32 )))|(% style="text-align:center" %)(((
33 0 h
34 )))|(% colspan="3" style="text-align:center" %)(((
35 36 h
36 )))
37 |(% colspan="2" %)(((
38 **Language used**
39 )))|(% colspan="9" %)(((
40 French
41 )))|(% colspan="7" rowspan="2" %)(((
42
43 )))
44 |(((
45 **Course supervisor(s)**
46 )))|(% colspan="10" %)[[Rémi PEYRE>>mailto:remi.peyre@mines-nancy.univ-lorraine.fr]], associate professor[[~[~[image:https://play-lh.googleusercontent.com/kMofEFLjobZy_bCuaiDogzBcUT-dz3BBbOrIEjJ-hqOabjK8ieuevGe6wlTD15QzOqw~|~|width="16"~]~]>>url:https://www.linkedin.com/in/r%C3%A9mi-peyre-3120b0111/]][[~[~[image:https://wiki.univ-lorraine.fr/bin/download/interne/comp/mines-nancy/minesnancyficm/GRADUATE%20PROGRAM%20ICM%20%28English%20Version%29/SYLLABUS%203rd%20YEAR/SCIENTIFIC%20DEPARTMENTS%203rd%20YEAR/INDUSTRIAL%20ENGINEERING%20and%20APPLIED%20MATHEMATICS%203rd%20YEAR/APPLIED%20MATHEMATICS%203rd%20YEAR/Topics%20in%20Information%20Theory/WebHome/index.png?width=16&rev=1.1~|~|alt="index.png" width="16"~]~]>>url:https://www.researchgate.net/profile/Remi-Peyre]]
47 |(((
48 **Key words**
49 )))|(% colspan="17" %)(((
50 (% style="color:#003366" %)Random simulation; Monte Carlo method; Variance reduction; MCMC methods; Simulated annealing; Stochastic gradien descent
51 )))
52 |(((
53 **Prerequisites**
54 )))|(% colspan="17" %)(((
55 Probability theory (level: 1st year of master's degree); basics in //Python// programming language
56 )))
57 |(% class="highlight-#c1c7d0" colspan="18" data-highlight-colour="#c1c7d0" title="Couleur d'arrière-plan : Gris moyen 45 %" %)(((
58 **Overall objective**
59 )))
60 |(% colspan="18" %)(((
61 Learn how to use random simulation to solve complicated deterministic problems.
62 )))
63 |(% class="highlight-#c1c7d0" colspan="18" data-highlight-colour="#c1c7d0" title="Couleur d'arrière-plan : Gris moyen 45 %" %)(((
64 **Course content and organisation**
65 )))
66 |(% colspan="18" %)(((
67 **~ ** This course is made of two distinct (though closely related) parts, the core aspect shared by both parts being the use of //random// simulation procedures in order to solve problems whose statement was initially purely //deterministic//!
68
69 The first part deals with the “Monte Carlo method” to compute an integral-like quantity (so, something deterministic): the method consists in, first, writing that quantity as a probabilistic expectation; and then, estimating that expectation through the use of random simulations.  In many practical situations, the approximated result given by that method will turn out to be more precise than the computation of the quantity that one would have obtained by “classical” numerical analysis techniques!
70
71 Besides the basic question of estimating the quantity of interest, the cours will also show how to provide with a confidence interval for the estimator.  Sometimes it is important to have means to shorten the length of the interval that one will obtain for a given computational cost: such a goal may be achieved by the so-called //variance reduction// techniques.  Four such techniques are explained by the course, viz.: importance sampling; conditioning; common random numbers; and control variate.
72
73 (% style="color:#0070c0" %)** **(%%) In some situations, simulating the needed wanted variables turns out to be a more difficult challenge than applying the Monte Carlo method as such.  To tackle that issue, we will introduce the so-called //Monte Carlo Markov Chain// (or commonly “MCMC”) methods, which enable to circumvent that difficulty in many practical cases.
74
75 That Monte Carlo Markov Chains chapter will naturally lead us to the second part of the course, devoted to stochastic methods for //mathematical optimization//.  The most famous such method is //simulated annealing//, which is closely related to the //Metropolis-Hastings// MCMC algorithm, introduced in the previous chapter.  Also, the course will explain how simulated annealing can be improved into //parallel tempering//.
76
77 To finish, the last chapter of the course shall be devoted to the //stochastic gradient descent// method: this is an optimization procedure which lies at the core of the training protocols for artificial neuron networks!
78
79 (% style="color:#0070c0" %)** **(%%) A large part of the teaching will be devoted to implementing the studied concepts into computer programs.  For the computer exercise sessions, //Python// has been chosen for language.
80 )))
81 |(% class="highlight-#c1c7d0" colspan="18" data-highlight-colour="#c1c7d0" title="Couleur d'arrière-plan : Gris moyen 45 %" %)(((
82 **Skills**
83 )))
84 |(((
85 (% style="color:#0070c0" %)**Levels**
86 )))|(% colspan="17" %)(((
87 (% style="color:#0070c0" %)**Description and operational verbs**
88 )))
89 |(((
90 **Know**
91 )))|(% colspan="17" %)(((
92 How to compute the Monte Carlo estimator for an expected value, as well as the associated the confidence interval
93
94 In what the main variance reduction techniques consist
95
96 How MCMC methods work, in particular Metropolis-Hastings Markov chains
97
98 In what the following stochastic optimization algorithms consist: simulated annealing; parallel tempring; stochastic gradient descent
99 )))
100 |(((
101 **Understand**
102 )))|(% colspan="17" %)(((
103 In which situations it is relevant to use the Monte Carlo method to estimate an expectation; What are its strengths and weaknesses
104
105 Regarding the evolution algorithms introduced by the course: how the involved Markov chains do behave
106 )))
107 |(((
108 **Apply(% style="color:#0070c0" %) (%%)**
109 )))|(% colspan="17" %)(((
110 Compute theoretically the auxiliary quantities that are required in such or such method explained by the course: e.g., the quantile function of the law that one wants to simulate; the expectation of some control variate; the density ratios for a measure that one wants to sample via a Metropolis-Hastings Markov chain; the gradient of some function whose expectation one wants to minimize; etc.
111
112 Implement a Monte Carlo estimation method, resp. a variance reduction technique, into a computer program
113
114 Implement a Metropolis-Hastings algorithm, resp. a simulated annealing algorithm (possibly with parallel tempering), resp. a stochastic gradient descent algorithm.
115 )))
116 |(((
117 **Analyze(% style="color:#0070c0" %) (%%)**
118 )))|(% colspan="17" %)(((
119 Choose a reduction variance technique that will be appropriate for the problem considered
120
121 Recognize situations in which it will be better to use MCMC methods rather than “direct” simulation
122
123 Recognize situations for which such or such stochastic optimization algorithm will be suited
124
125 Tune the parameters of such or such stochastic algorithm in a clever way
126 )))
127 |(% colspan="1" %)(((
128 **Summarize**
129 )))|(% colspan="17" %)(((
130
131 )))
132 |(% colspan="1" %)(((
133 **Assess**
134 )))|(% colspan="17" %)(((
135 Look critically at the convergence behaviour of a Monte Carlo estimator
136
137 Look critically at the solution that one obtained via some stochastic optimization algorithm
138 )))
139 |(% class="highlight-#c1c7d0" colspan="18" data-highlight-colour="#c1c7d0" %)(((
140 (% class="kYiyGk sc-14kwckt-9" %)**Compliance with the United Nations Sustainable Development Goals**
141 )))
142 |(% colspan="18" %)(((
143 (% class="content-wrapper" %)
144 (((
145 (% class="wrapped" %)
146 |(((
147 (% class="content-wrapper" %)
148 (((
149 (% class="task-list" %)
150 (((
151 {{task reference="/Tasks/Task_5" status="InProgress"}}
152 [[image:attach:image2022-12-5_21-22-41.png||thumbnail="true" width="60"]]
153 {{/task}}
154 )))
155 )))
156 )))|(((
157 (% class="content-wrapper" %)
158 (((
159 (% class="task-list" %)
160 (((
161 {{task reference="/Tasks/Task_25" status="InProgress"}}
162 [[image:attach:image2022-12-5_21-23-16.png||thumbnail="true" width="60"]]
163 {{/task}}
164 )))
165 )))
166 )))|(((
167 (% class="content-wrapper" %)
168 (((
169 (% class="task-list" %)
170 (((
171 {{task reference="/Tasks/Task_26" status="InProgress"}}
172 [[image:attach:image2022-12-5_21-26-53.png||thumbnail="true" width="60"]]
173 {{/task}}
174 )))
175 )))
176 )))|(((
177 (% class="content-wrapper" %)
178 (((
179 (% class="task-list" %)
180 (((
181 {{task reference="/Tasks/Task_27" status="InProgress"}}
182 [[image:attach:image2022-12-5_21-27-10.png||thumbnail="true" width="60"]]
183 {{/task}}
184 )))
185 )))
186 )))|(((
187 (% class="content-wrapper" %)
188 (((
189 (% class="task-list" %)
190 (((
191 {{task reference="/Tasks/Task_28" status="InProgress"}}
192 [[image:attach:image2022-12-5_21-27-29.png||thumbnail="true" width="60"]]
193 {{/task}}
194 )))
195 )))
196 )))|(% colspan="1" %)(((
197 (% class="content-wrapper" %)
198 (((
199 (% class="task-list" %)
200 (((
201 {{task reference="/Tasks/Task_29" status="InProgress"}}
202 [[image:attach:image2022-12-5_21-27-47.png||thumbnail="true" width="60"]]
203 {{/task}}
204 )))
205 )))
206 )))|(% colspan="1" %)(((
207 (% class="content-wrapper" %)
208 (((
209 (% class="task-list" %)
210 (((
211 {{task reference="/Tasks/Task_30" status="InProgress"}}
212 [[image:attach:image2022-12-5_21-29-25.png||thumbnail="true" width="60"]]
213 {{/task}}
214 )))
215 )))
216 )))|(% colspan="1" %)(((
217 (% class="content-wrapper" %)
218 (((
219 (% class="task-list" %)
220 (((
221 {{task reference="/Tasks/Task_31" status="InProgress"}}
222 [[image:attach:image2022-12-5_21-29-43.png||thumbnail="true" width="60"]]
223 {{/task}}
224 )))
225 )))
226 )))|(% colspan="1" %)(((
227 (% class="content-wrapper" %)
228 (((
229 (% class="task-list" %)
230 (((
231 {{task reference="/Tasks/Task_32" status="Done"}}
232 [[image:attach:image2022-12-5_21-34-38.png||thumbnail="true" width="60"]]
233 {{/task}}
234 )))
235 )))
236 )))
237 |(((
238 (% class="content-wrapper" %)
239 (((
240 (% class="task-list" %)
241 (((
242 {{task reference="/Tasks/Task_33" status="InProgress"}}
243 [[image:attach:image2022-12-5_21-30-2.png||thumbnail="true" width="60"]]
244 {{/task}}
245 )))
246 )))
247 )))|(((
248 (% class="content-wrapper" %)
249 (((
250 (% class="task-list" %)
251 (((
252 {{task reference="/Tasks/Task_34" status="Done"}}
253 [[image:attach:image2022-12-5_21-30-25.png||thumbnail="true" width="60"]]
254 {{/task}}
255 )))
256 )))
257 )))|(((
258 (% class="content-wrapper" %)
259 (((
260 (% class="task-list" %)
261 (((
262 {{task reference="/Tasks/Task_35" status="InProgress"}}
263 [[image:attach:image2022-12-5_21-30-51.png||thumbnail="true" width="60"]]
264 {{/task}}
265 )))
266 )))
267 )))|(((
268 (% class="content-wrapper" %)
269 (((
270 (% class="task-list" %)
271 (((
272 {{task reference="/Tasks/Task_36" status="InProgress"}}
273 [[image:attach:image2022-12-5_21-31-32.png||thumbnail="true" width="60"]]
274 {{/task}}
275 )))
276 )))
277 )))|(((
278 (% class="content-wrapper" %)
279 (((
280 (% class="task-list" %)
281 (((
282 {{task reference="/Tasks/Task_37" status="InProgress"}}
283 [[image:attach:image2022-12-5_21-32-1.png||thumbnail="true" width="60"]]
284 {{/task}}
285 )))
286 )))
287 )))|(% colspan="1" %)(((
288 (% class="content-wrapper" %)
289 (((
290 (% class="task-list" %)
291 (((
292 {{task reference="/Tasks/Task_38" status="InProgress" completeDate="" createDate="02/05/2025" reporter=""}}
293
294 {{/task}}
295 )))
296 )))
297 )))|(% colspan="1" %)(((
298 (% class="content-wrapper" %)
299 (((
300 (% class="task-list" %)
301 (((
302 {{task reference="/Tasks/Task_39" status="InProgress"}}
303 [[image:attach:image2022-12-5_21-33-6.png||thumbnail="true" width="60"]]
304 {{/task}}
305 )))
306 )))
307 )))|(% colspan="1" %)(((
308 (% class="content-wrapper" %)
309 (((
310 (% class="task-list" %)
311 (((
312 {{task reference="/Tasks/Task_40" status="InProgress"}}
313 [[image:attach:image2022-12-5_21-33-33.png||thumbnail="true" width="60"]]
314 {{/task}}
315 )))
316 )))
317 )))|(% colspan="1" %)(((
318
319 )))
320
321 (% class="sc-14kwckt-9 kYiyGk" %)
322
323 )))
324 )))
325 |(% class="highlight-#c1c7d0" colspan="18" data-highlight-colour="#c1c7d0" title="Couleur d'arrière-plan : Gris moyen 45 %" %)(((
326 **Evaluation methods**
327 )))
328 |(((
329 Continuous assessment
330 )))|(% style="text-align:center" %)(((
331 (% class="task-list" %)
332 (((
333 {{task reference="/Tasks/Task_45" status="InProgress"}}
334
335 {{/task}}
336 )))
337 )))|(% colspan="4" %)(((
338 Written test
339 )))|(% colspan="2" style="text-align:center" %)(((
340 (% class="task-list" %)
341 (((
342 {{task reference="/Tasks/Task_46" status="Done"}}
343
344 {{/task}}
345 )))
346 )))|(% colspan="3" %)(((
347 Oral presentation / viva
348 )))|(% colspan="2" style="text-align:center" %)(((
349 (% class="task-list" %)
350 (((
351 {{task reference="/Tasks/Task_47" status="Done"}}
352
353 {{/task}}
354 )))
355 )))|(% colspan="3" %)(((
356 Written report / project
357 )))|(% colspan="2" style="text-align:center" %)(((
358 (% class="task-list" %)
359 (((
360 {{task reference="/Tasks/Task_48" status="Done"}}
361
362 {{/task}}
363 )))
364 )))