Sztochasztikus modellek és adaptív algoritmusok
A tantárgy angol neve: Stochastic models and adaptive algorithms
Adatlap utolsó módosítása: 2017. december 4.
PhD képzés
szabadon választható tárgy
Dr. Csáji Balázs Csanád
tudományos főmunkatárs
MTA SZTAKI
valószínűségszámítás, lineáris algebra, (többváltozós) analízis
A cél a gépi tanulásban, adatbányászatban, irányításelméletben, rendszer identifikációban, jelfeldolgozásban, pénzügyi matematikában és számos egyéb területen is használt néhány tipikus sztochasztikus modell és adaptív algoritmus elméletébe való bevezetés.
A tantárgy három fő témakört érint: (i) az első a (parametrikus és nemparametrikus) regresszió, regularizáció, és ezen módszerek statisztikai tulajdonságai (vö. felügyelt tanulás); (ii) a második a szekvenciális döntési problémák, főleg Markov folyamatokra (vö. megerősítéses tanulás); (iii) végül eljut a (rekurzív) adaptív algoritmusok (sztochasztikus approximáció) általános elméletig, amelynek néhány nevezetes algoritmusát tárgyalja.
1. Regresszió:
1.1 Legkisebb négyzetek (OLS) módszer alaptulajdonságainak átismétlése: ortogonális projekció, torzítatlanság, kovariancia mátrixa, Gauss-Markov tétel, kapcsolat a Maximum Likelihood (ML) becsléssel, erős konzisztencia, határeloszlás, aszimptotikus hatékonyság, konfidencia ellipszoidok.
1.2 LS általánosításai és kapcsolódó lineáris algebrai eredmények: Tikhonov regularizáció, legkisebb norma probléma, szinguláris érték felbontás (SVD), alacsony rangú közelítések, rekurzív legkisebb négyzetek, mátrix inverziós lemma, általánosított LS és speciális esetei: súlyozott LS, felejtési tényezők.
1.3 Kernel módszerek: nemparametrikus regresszió, reprodukáló magú Hilbert terek (RKHS), regularizáció RKHS terekben, reprezentációs tétel, Moore-Aronszain tétel, tipikus magfüggvények és indukált tanuló módszereik, fontos speciális esetek: szupport vektor klasszifikáció és regresszió.
1.4 Idősorok: erősen és gyengés stacionárius folyamatok, Wold reprezentáció, lineáris szűrők és tulajdonságaik (stabilitás, inverz szűrő, stb.), általános lineáris rendszerek, tipikus (pl., autoregresszív) modellek és becsléseik: előrejelzési hiba-, ML-, korrelációs- és instrumentális változók módszer.
2. Markov döntési problémák (MDP):
2.1 Markov láncok alapfogalmainak átismétlése (megszámlálható állapotterek): kezdeti eloszlás, átmenet függvény, stacionárius eloszlás, ergodikusság.
2.2 MDP-k alapfogalmai és főbb típusai, például, sztochasztikus legrövidebb út (SSP) problémák. Irányítási politikák és értékelő függvények (várható diszkontált és ergodikus költség). Bellman operátor és tulajdonságai, kontrakció, monotonitás, optimalitási egyenletek, közelítési lehetőségek.
2.3 MDP-k főbb megoldási irányai: iteratív értékelő függvény közelítés (érték iteráció, Q-tanulás), keresés a politikák terében (politika iteráció, politikai gradiens), lineáris programozási megközelítések, számítási bonyolultság. Általánosítások: nem korlátos költségek, részleges megfigyelhetőség.
2.4 TD-tanulás: Monte Carlo közelítések, alkalmazhatósági együtthatók, TD(0), TD(1), TD(lambda) és változatai (online, offline, first-visit, every-visit), konvergencia tételek, általánosított TD-tanulás, optimista politika iteráció.
3. Adaptív algoritmusok:
3.1 Általánosított iteratív algoritmusok és sztochasztikus approximáció, fix pont és gyökkeresési problémák, példák korábbi algoritmusok átfogalmazására.
3.2 Ljapunov függvény alapú konvergencia vizsgálat. Sztochasztikus gradiens módszer, konvergenciája és változatai: Kiefer-Wolfowitz algoritmus és a szimultán véletlen perturbáció (SPSA) módszere.
3.3 Pszeudo-kontrakció és monotonitási tulajdonságokon alapuló elemzések, és szemléltetésük a Bellman operátor példáján keresztül.
3.4 Általánosítások: időfüggő leképezések és változó paraméterek követése.
Heti 2 óra előadás.
A szorgalmi időszakban: numerikus kísérletek
A vizsgaidőszakban: szóbeli vizsga
- Jerome Friedman, Trevor Hastie, Robert Tibshirani. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer. 2009.
- Dimitri P. Bertsekas, John Tsitsiklis. Neuro-Dynamic Programming. Athena Sci. 1996.
- Albert Benveniste, Michel Métivier, Pierre Priouret. Adaptive Algorithms and Stochastic Approximations. Springer. 1990.
- Bernhard Schölkopf, Alexaner J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond. The MIT Press. 2002.
- Harold J. Kushner, G. George Yin. Stochastic Approximation and Recursive Algorithms and Applications. 2nd Edition. Springer. 2008.
- Simon Haykin. Neural Networks and Learning Machines. 3rd ed. Prentice Hall, 2008.