Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    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.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    PhD képzés

    szabadon választható tárgy 

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZDV06   2/0/0/V 3  
    3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula, Számítástudományi és Információelméleti Tanszék
    A tantárgy tanszéki weboldala http://www.cs.bme.hu/smaa
    4. A tantárgy előadója

    Dr. Csáji Balázs Csanád

    tudományos főmunkatárs

    MTA SZTAKI

    5. A tantárgy az alábbi témakörök ismeretére épít

    valószínűségszámítás, lineáris algebra, (többváltozós) analízis

    7. A tantárgy célkitűzése

    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.

    8. A tantárgy részletes tematikája

    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.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    Heti 2 óra előadás.

    10. Követelmények

    A szorgalmi időszakban: numerikus kísérletek

    A vizsgaidőszakban: szóbeli vizsga

    Elővizsga: lehetséges
    11. Pótlási lehetőségek Személyes egyeztetés alapján
    12. Konzultációs lehetőségek Fogadóórákon, illetve személyes egyeztetés alapján
    13. Jegyzet, tankönyv, felhasználható irodalom

    - 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.

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra28
    Félévközi készülés órákra14
    Felkészülés zárthelyire
    Házi feladat elkészítése14
    Kijelölt írásos tananyag elsajátítása10
    Vizsgafelkészülés24
    Összesen90
    15. A tantárgy tematikáját kidolgozta

    Dr. Csáji Balázs Csanád

    tudományos főmunkatárs

    MTA SZTAKI