„Függvényillesztés Monte Carlo módszerrel mérésleírás” változatai közötti eltérés
42. sor: | 42. sor: | ||
A jegyzőkönyvben szerepeljen a program felépítésének leírása, valamint a probléma diszkussziója. Vizsgáljuk meg a kezdeti paraméterek, az inverz hőmérséklet, valamint a paraméterek lépésközeinek hatását az illesztés gyorsaságára és jóságára, azaz adjuk meg, hogy átlagosan hány lépés után illeszkedik a generált függvény az eredetire, valamint mekkora a jellemző minimális energia! | A jegyzőkönyvben szerepeljen a program felépítésének leírása, valamint a probléma diszkussziója. Vizsgáljuk meg a kezdeti paraméterek, az inverz hőmérséklet, valamint a paraméterek lépésközeinek hatását az illesztés gyorsaságára és jóságára, azaz adjuk meg, hogy átlagosan hány lépés után illeszkedik a generált függvény az eredetire, valamint mekkora a jellemző minimális energia! | ||
Opcionálisan próbáljuk ki, hogy lehetséges-e jobb eredményt elérni, ha $\beta$-t, illetve a lépésközöket dinamikusan változtatjuk! A dokumentációhoz csatoljuk a program forráskódját! | Opcionálisan próbáljuk ki, hogy lehetséges-e jobb eredményt elérni, ha $\beta$-t, illetve a lépésközöket dinamikusan változtatjuk! A dokumentációhoz csatoljuk a program forráskódját! | ||
+ | </wlatex> | ||
+ | |||
+ | = Syllabus in English = | ||
+ | |||
+ | The exercise sample data is available here: [[Média:Data.txt |Data.txt]]. | ||
+ | |||
+ | == Introcution == | ||
+ | Monte Carlo algorithms have a widespread use in many fields, this exercise focuses on fitting a function to a series of data (such as what would be obtained by an experimental measurement). The exercise description presents the necessary theoretical background, and provides indications for the concrete implementation. | ||
+ | |||
+ | == Theoretical background == | ||
+ | <wlatex> | ||
+ | Let the original series of points we desire to fit, be denoted as $ Y_\textrm{orig}(X_\textrm{i})$, where $i=1\ldots N$. The fitted data series is $Y_\textrm{fit}(X_\textrm{i}, \vec{A})$, where $\vec{A}=(A_1,A_2 \ldots A_\textrm{M})$ is the list of parameters that are varied to obtain the best correlation between the fitted series and the original series. The best fit is to be regarded as a minimization of the following "energy" expression: $$E(\vec{A})=\sum_{i=1}^{N} \left| Y_\textrm{orig}(X_\textrm{i}) - Y_\textrm{fit}(X_\textrm{i}, \vec{A})\right| | ||
+ | \label{MCEnergyEq} | ||
+ | $$ | ||
+ | The minimization of energy is obtained through the Monte Carlo - Metropolis algorithm: First, alter the fitting parameters with a random factor: $\vec{A}' = \vec{A}+ \vec{\delta A}$. Using the new randomly varied parameters, a new energy value is obtained: $E(\vec{A}) \rightarrow E(\vec{A}')$. The new parameters should be accepted and kept, if the new energy is closer to the energy minimum, that is, $E(\vec{A}') < E(\vec{A})$. The key to the algorithm is to avoid becoming stuck in a local minimum, thus we use an "annealing" method, where with $p=\textrm{exp}(-\beta(E(\vec{A}')-E(\vec{A})))$ probability we accept the new parameters, even if $E(\vec{A}') > E(\vec{A})$. Observe that using $\beta \rightarrow \infty$ the algorithm can only step downwards in energy, while in the limit $\beta \rightarrow 0$ the walk in the parameter space is entirely random. This gives a physical meaning to the $\beta$ value: it can be regarded as particle moving in the parameter space with $(kT)^{-1}$ inverse temperature. | ||
</wlatex> | </wlatex> |
A lap 2018. február 28., 15:49-kori változata
Az alábbi leírás pdf formátumban is letölthető. Példa adatsor: Data.txt.
Tartalomjegyzék |
Bevezetés
A Monte Carlo algoritmusok szerteágazó alkalmazási területei közül a függvényillesztés a számítógépes gyakorlat témája. A leírás áttekinti a szükséges elméleti hátteret, valamint segítséget ad a konkrét megvalósításhoz.
Elméleti háttér
Legyen az illesztendő adatsor![\setbox0\hbox{$ Y_\textrm{orig}(X_\textrm{i})$}% \message{//depth:\the\dp0//}% \box0%](/images/math/7/0/b/70b62b703fb3e0f7194338431c4d6a80.png)
![\setbox0\hbox{$i=1\ldots N$}% \message{//depth:\the\dp0//}% \box0%](/images/math/9/a/7/9a78c89210237a3fe9f8d98f0c46e74c.png)
![\setbox0\hbox{$Y_\textrm{fit}(X_\textrm{i}, \vec{A})$}% \message{//depth:\the\dp0//}% \box0%](/images/math/2/2/a/22a73081561e00a02edcd4524e6675a0.png)
![\setbox0\hbox{$\vec{A}=(A_1,A_2 \ldots A_\textrm{M})$}% \message{//depth:\the\dp0//}% \box0%](/images/math/e/0/a/e0aca2ce837c1f7e6756fc51cea5f1a2.png)
![\[E(\vec{A})=\sum_{i=1}^{N} \left| Y_\textrm{orig}(X_\textrm{i}) - Y_\textrm{fit}(X_\textrm{i}, \vec{A})\right| \label{MCEnergyEq} \]](/images/math/b/c/9/bc95522349a8e6ac1157fbcc34e08ad7.png)
A minimalizálást Monte Carlo--Metropolis algoritmussal végezzük: Változtassuk meg a paramétereket véletlenszerűen: . Ezzel a fentiek szerint kiszámolt energia is változik:
. Az új paramétereket elfogadjuk, ha közelebb kerültünk a minimumhoz, tehát
. Célunk elkerülni, hogy az algoritmus befagyjon egy lokális minimumba, ezért
valószínűséggel dolgozunk tovább az új paraméterekkel, ha
. Vegyük észre, hogy
esetben csak lefelé léphetünk, míg a
határátmenetben véletlenszerű mozgást kapunk a paramétertérben. Ez adja a fizikai jelentését az algoritmusban szereplő
értéknek: megfeleltethető egy, a paramétertérben mozgó részecske
inverz hőmérsékletének.
Implementáció
A fentiek megvalósításához a következő felépítést érdemes követni:
- Készítsünk globális tömböt az eredeti, valamint az illesztett adatsornak;
- Hasonlóan globális változókban tároljuk az inverz hőmérsékletet, az illesztési paramétereket, valamint azok lépésközét;
- Deklaráljunk két véletlenszám-generátort: egyet a paraméterek megváltoztatásához és egyet az
valószínűségű lépéshez;
- Hozzunk létre globális változókat a megváltoztatott paramétereknek, valamint egy tömböt a megváltoztatott paraméterekkel generált illesztőfüggvénynek.
Az illesztés inicializálásához hozzuk létre a szükséges változókat, és olvassuk be a kezdőértékeket a TextBoxokból.
Az illesztést az alábbiak szerint végezzük:
- Számítsuk ki a
szerinti energiát az aktuális változókkal;
- Változtassuk meg az egyik paramétert a megadott határok között egyenletes eloszlással;
- Számítsuk ki az így megváltozott energiát;
- A régi és új energia különbsége alapján döntsünk arról, hogy elfogadjuk-e a változást: ha az új érték kisebb, akkor minden esetben, ha nem, akkor sorsoljunk egy véletlenszámot, és
valószínűséggel mégis elfogadjuk a változást;
- Ha szükséges, írjuk ki az új értéket a TextBoxba, és ábrázoljuk a megváltozott illesztőfüggvényt;
- A fentiek szerint járjunk el a többi paraméter esetében.
Feladatok
Készítsünk grafikus függvényillesztő felületet a data.dat file-ban található 500 elemű adatsor illesztéséhez a![\[ y(t)=Ae^{-t/\tau}\sin(2\pi t/T)\]](/images/math/4/f/0/4f0332aa1420c838cd15b43a82ebe856.png)
![\setbox0\hbox{$A,\tau,T$}% \message{//depth:\the\dp0//}% \box0%](/images/math/2/1/f/21f45e7004a775cc8b035c06b21ae8f4.png)
- Olvassuk be és ábrázoljuk a data.dat állomány tartalmát!
- Hozzunk létre TextBoxokat, amelyekkel állíthatóak a függvényillesztés kiinduló paraméterei, azok lépésköze, valamint az inverz hőmérséklet!
- Hozzunk létre gombokat, amelyekkel elindíthatjuk a függvényillesztést: legyen lehetséges újraindítani az illesztést a TextBoxokban megadott kezdeti paraméterekkel, valamint 1, illetve 100 illesztési ciklust elindítani!
- A program jelenítse meg az aktuális paramétereket, az
szerinti energiát, valamint az illesztett függvényt!
A jegyzőkönyvben szerepeljen a program felépítésének leírása, valamint a probléma diszkussziója. Vizsgáljuk meg a kezdeti paraméterek, az inverz hőmérséklet, valamint a paraméterek lépésközeinek hatását az illesztés gyorsaságára és jóságára, azaz adjuk meg, hogy átlagosan hány lépés után illeszkedik a generált függvény az eredetire, valamint mekkora a jellemző minimális energia!
Opcionálisan próbáljuk ki, hogy lehetséges-e jobb eredményt elérni, ha -t, illetve a lépésközöket dinamikusan változtatjuk! A dokumentációhoz csatoljuk a program forráskódját!
Syllabus in English
The exercise sample data is available here: Data.txt.
Introcution
Monte Carlo algorithms have a widespread use in many fields, this exercise focuses on fitting a function to a series of data (such as what would be obtained by an experimental measurement). The exercise description presents the necessary theoretical background, and provides indications for the concrete implementation.
Theoretical background
![\setbox0\hbox{$ Y_\textrm{orig}(X_\textrm{i})$}% \message{//depth:\the\dp0//}% \box0%](/images/math/7/0/b/70b62b703fb3e0f7194338431c4d6a80.png)
![\setbox0\hbox{$i=1\ldots N$}% \message{//depth:\the\dp0//}% \box0%](/images/math/9/a/7/9a78c89210237a3fe9f8d98f0c46e74c.png)
![\setbox0\hbox{$Y_\textrm{fit}(X_\textrm{i}, \vec{A})$}% \message{//depth:\the\dp0//}% \box0%](/images/math/2/2/a/22a73081561e00a02edcd4524e6675a0.png)
![\setbox0\hbox{$\vec{A}=(A_1,A_2 \ldots A_\textrm{M})$}% \message{//depth:\the\dp0//}% \box0%](/images/math/e/0/a/e0aca2ce837c1f7e6756fc51cea5f1a2.png)
![\[E(\vec{A})=\sum_{i=1}^{N} \left| Y_\textrm{orig}(X_\textrm{i}) - Y_\textrm{fit}(X_\textrm{i}, \vec{A})\right| \label{MCEnergyEq} \]](/images/math/b/c/9/bc95522349a8e6ac1157fbcc34e08ad7.png)
The minimization of energy is obtained through the Monte Carlo - Metropolis algorithm: First, alter the fitting parameters with a random factor: . Using the new randomly varied parameters, a new energy value is obtained:
. The new parameters should be accepted and kept, if the new energy is closer to the energy minimum, that is,
. The key to the algorithm is to avoid becoming stuck in a local minimum, thus we use an "annealing" method, where with
probability we accept the new parameters, even if
. Observe that using
the algorithm can only step downwards in energy, while in the limit
the walk in the parameter space is entirely random. This gives a physical meaning to the
value: it can be regarded as particle moving in the parameter space with
inverse temperature.