Subject » BMEVISZDV06
Stochastic models and adaptive algorithms
Sztochasztikus modellek és adaptív algoritmusok
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Sztochasztikus modellek és adaptív algoritmusok
Stochastic models and adaptive algorithms
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZDV06 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 3 | ||||||||||||
| Subject coordinator |
DR. Katona Gyula
position: egyetemi tanár
contact:
katona.gyula@vik.bme.hu
|
||||||||||||
| Responsible department |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Faculty | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Subject website | http://www.cs.bme.hu/smaa | ||||||||||||
| Primary curriculum type | — | ||||||||||||
| Direct prerequisites – Strong prerequisite | none | ||||||||||||
| Direct prerequisites – Weak prerequisite | none | ||||||||||||
| Direct prerequisites – Parallel prerequisite | none | ||||||||||||
| Direct prerequisites – Milestone prerequisite | none | ||||||||||||
| Direct prerequisites – Exclusion | none |
Objectives
Programme
1. Regression:
1.1 Review of the fundamental results related to the least-squares (LS) method: orthogonal projection property, unbiasedness, its covariance matrix, Gauss-Markov theorem, connection to the Maximum Likelihood (ML) estimate, strong consistency, asymptotic efficiency, and its confidence ellipsoids.
1.2 Generalizations of the LS theory and related results from linear algebra: Tikhonov regularization, least-norm problem, singular value decomposition (SVD), low rank approximations, recursive LS, matrix inversion lemma, generalized LS and its special cases: weighted LS and forgetting factors.
1.3 Kernel methods: nonparametric regression, reproducing kernel Hilbert spaces (RKHS), regularization in RKHS, representer theorem, Moore-Aronszajn theorem, typical kernels and their induced learning machines, important special cases: support vector classification and regression.
1.4 Time-series analysis: strictly and weakly stationary stochastic processes, Wold representation, linear filters and their main properties, general linear systems, typical (such as autoregressive) models and their estimates: prediction error-, correlation-, ML-, and instrumental variable methods.
2. Markov decision processes (MDPs):
2.1 Review of Markov chains (for countable state spaces), including initial distributions, transition functions, stationary distributions, and ergodicity.
2.2 Central concepts of MDPs and their main types, such as stochastic shortest path, total discounted and average (ergodic) cost problems. Control policies, value functions, Bellman operators and their core properties, monotonicity, contraction, optimality equations, and approximation possibilities.
2.3 Main solution directions of MDPs: iterative approximations of the optimal value function (value iteration, Q-learning); direct search in the space of policies (policy iteration, policy gradient); linear programming methods, complexity. Generalizations: unbounded costs, partial observability.
2.4 Temporal difference (TD) learning: Monte Carlo evaluations, eligibility traces, TD(0), TD(1), TD(lambda) and their variants (online, offline, first-visit, every-visit), convergence theorems, optimistic policy improvements.
3. Adaptive algorithms:
3.1 General iterative algorithms and stochastic approximation, fixed point and root finding problems, examples of reformulating known algorithms.
3.2 Convergence analysis based on Lyapunov functions. Famous examples: stochastic gradient descent and its variants, the Kiefer-Wolfowitz algorithm and the simultaneous perturbation stochastic approximation (SPSA) method.
3.3 Convergence analysis based on contraction and monotonicity properties, their illustration through the example of the Bellman operator in MDPs.
3.4 Generalizations: time-dependent updates and tracking changing parameters.
The course aims at providing an introduction to typical stochastic models and adaptive algorithms applied in a wide range of fields including machine learning, data mining, system identification, control theory, signal processing, and financial mathematics.
The course has three main parts: (i) the first one is (parametric and nonparametric) regression, regularization, and the statistical properties of such methods (cf. supervised learning); (ii) the second one is the theory of sequential decision making, mainly focusing on controlled Markov processes (cf. reinforcement learning); (iii) finally, the course ends with the general theory of (recursive) adaptive algorithms (also known as stochastic approximation), discussing some of the arch-typical algorithms and related theoretical results of the field.
Learning outcomes
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Knowledge
No learning outcomes recorded.
Skills
No learning outcomes recorded.
Attitudes
No learning outcomes recorded.
Autonomy and responsibility
No learning outcomes recorded.
Oktatási módszertan
2 hours of lectures per week.
Tanulástámogató anyagok
Online források
- 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.
Recommended preliminary knowledge for completing the subject
Knowledge type competencies
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
probability theory, linear algebra, (multivariable) calculus
Skill type competencies
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Recommended (non-compulsory) preliminary competencies
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
probability theory, linear algebra, (multivariable) calculus
General rules
Requirements:
Signature: numerical experiments
Final: Oral exam
Assessment methods
In-term assessments
No detailed assessments provided.
Weight of in-term assessments
No weights provided.
Exam-period assessments
No detailed assessments provided.
Weight of exam elements
No weights provided.
Grade calculation
No grade thresholds provided.
Attendance requirements
No attendance requirements provided.
Rules for retake and resubmission
Not provided.
Short description
Not provided.
Detailed description
Not provided.
Recommended courses
Not provided.
Workload to complete the subject
No workload breakdown provided.
Validity of subject requirements
Requirements valid from:
—
Requirements valid until:
—
Curriculum placement
No curriculum placements recorded for this subject version.