TY - JOUR
AU - Kozdoba, Mark
AU - Marecek, Jakub
AU - Tchrakian, Tigran
AU - Mannor, Shie
PY - 2019/07/17
Y2 - 2024/07/12
TI - On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filters
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 33
IS - 01
SE - AAAI Technical Track: Machine Learning
DO - 10.1609/aaai.v33i01.33014098
UR - https://ojs.aaai.org/index.php/AAAI/article/view/4307
SP - 4098-4105
AB - <p>The Kalman filter is a key tool for time-series forecasting and analysis. We show that the dependence of a prediction of Kalman filter on the past is decaying exponentially, whenever the process noise is non-degenerate. Therefore, Kalman filter may be approximated by regression on a few recent observations. Surprisingly, we also show that having some process noise is <em>essential</em> for the exponential decay. With no process noise, it may happen that the forecast depends on all of the past uniformly, which makes forecasting more difficult.</p><p>Based on this insight, we devise an on-line algorithm for improper learning of a linear dynamical system (LDS), which considers only a few most recent observations. We use our decay results to provide the first regret bounds w.r.t. to Kalman filters within learning an LDS. That is, we compare the results of our algorithm to the best, in hindsight, Kalman filter for a given signal. Also, the algorithm is practical: its per-update run-time is linear in the regression depth.</p>
ER -