Statistical learning for system identification, estimation, and control

Abstract

Despite the recent widespread success of machine learning, we still do not fully understand its fundamental limitations. Going forward, it is crucial to better understand learning complexity, especially in critical decision making applications, where a wrong decision can lead to catastrophic consequences. In this thesis, we focus on the statistical complexity of learning unknown linear dynamical systems, with focus on the tasks of system identification, prediction, and control. We are interested in sample complexity, i.e. the minimum number of samples required to achieve satisfactory learning performance. Our goal is to provide finite-sample learning guarantees, explicitly highlighting how the learning objective depends on the number of samples. A fundamental question we are trying to answer is how system theoretic properties of the underlying process can affect sample complexity. Using recent advances in statistical learning, high-dimensional statistics, and control theoretic tools, we provide finite-sample guarantees in the following settings. i) System Identification. We provide the first finite-sample guarantees for identifying a stochastic partially-observed system; this problem is also known as the stochastic system identification problem. ii) Prediction. We provide the first end-to-end guarantees for learning the Kalman Filter, i.e. for learning to predict, in an offline learning architecture. We also provide the first logarithmic regret guarantees for the problem of learning the Kalman Filter in an online learning architecture, where the data are revealed sequentially. iii) Difficulty of System Identification and Control. Focusing on fully-observed systems, we investigate when learning linear systems is statistically easy or hard, in the finite sample regime. Statistically easy to learn linear system classes have sample complexity that is polynomial with the system dimension. Statistically hard to learn linear system classes have worst-case sample complexity that is at least exponential with the system dimension. We show that there actually exist classes of linear systems, which are hard to learn. Such classes include indirectly excited systems with large degree of indirect excitation. Similar conclusions hold for both the problem of system identification and the problem of learning to control.

Παρά την πρόσφατη ευρεία επιτυχία της μηχανικής μάθησης, εξακολουθούμε να μην κατανοούμε πλήρως τους θεμελιώδεις περιορισμούς της. Προχωρώντας προς το μέλλον, είναι κρίσιμο να κατανοήσουμε καλύτερα την πολυπλοκότητα της μάθησης, ιδιαίτερα σε εφαρμογές κρίσιμης λήψης αποφάσεων, όπου μια λανθασμένη απόφαση μπορεί να οδηγήσει σε καταστροφικές συνέπειες. Σε αυτή τη διατριβή, εστιάζουμε στην στατιστική πολυπλοκότητα της μάθησης αγνώστων γραμμικών δυναμικών συστημάτων, με έμφαση στις εργασίες της αναγνώρισης συστημάτων, της πρόβλεψης και του ελέγχου. Μας ενδιαφέρει η πολυπλοκότητα δειγματοληψίας, δηλαδή ο ελάχιστος αριθμός δειγμάτων που απαιτείται για να επιτευχθεί ικανοποιητική απόδοση μάθησης. Στόχος μας είναι να παρέχουμε εγγυήσεις μάθησης με πεπερασμένο αριθμό δειγμάτων, επισημαίνοντας ρητά πώς ο στόχος μάθησης εξαρτάται από τον αριθμό των δειγμάτων. Ένα θεμελιώδες ερώτημα που προσπαθούμε να απαντήσουμε είναι το πώς οι συστημικές θεωρητικές ιδιότητες της υποκείμενης διαδικασίας μπορούν να επηρεάσουν την πολυπλοκότητα δειγματοληψίας. Χρησιμοποιώντας πρόσφατες εξελίξεις στη στατιστική μάθηση, τη στατιστική υψηλών διαστάσεων και τα θεωρητικά εργαλεία ελέγχου, παρέχουμε εγγυήσεις με πεπερασμένο αριθμό δειγμάτων στις ακόλουθες περιπτώσεις: i) Αναγνώριση συστήματος. Παρέχουμε τις πρώτες εγγυήσεις με πεπερασμένο αριθμό δειγμάτων για την ταυτοποίηση ενός στοχαστικού μερικώς παρατηρήσιμου συστήματος· αυτό το πρόβλημα είναι επίσης γνωστό ως πρόβλημα στοχαστικής αναγνώρισης συστήματος. ii) Πρόβλεψη. Παρέχουμε τις πρώτες ολοκληρωμένες εγγυήσεις για τη μάθηση του φίλτρου Kalman, δηλαδή για τη μάθηση πρόβλεψης, σε ένα αρχιτεκτονικό πλαίσιο εκτός σύνδεσης. Παρέχουμε επίσης τις πρώτες εγγυήσεις λογαριθμικού regret για το πρόβλημα της μάθησης του φίλτρου Kalman σε ένα αρχιτεκτονικό πλαίσιο μάθησης σε πραγματικό χρόνο, όπου τα δεδομένα αποκαλύπτονται διαδοχικά. iii) Δυσκολία της αναγνώρισης συστήματος και του ελέγχου. Εστιάζοντας σε πλήρως παρατηρήσιμα συστήματα, διερευνούμε πότε η μάθηση γραμμικών συστημάτων είναι στατιστικά εύκολη ή δύσκολη, στο πεπερασμένο δειγματοληπτικό καθεστώς. Οι κλάσεις γραμμικών συστημάτων που είναι στατιστικά εύκολες στη μάθηση έχουν πολυπλοκότητα δειγματοληψίας που είναι πολυωνυμική ως προς τη διάσταση του συστήματος. Αντίθετα, οι κλάσεις γραμμικών συστημάτων που είναι στατιστικά δύσκολες στη μάθηση έχουν τη χειρότερη περίπτωση πολυπλοκότητας δειγματοληψίας τουλάχιστον εκθετική ως προς τη διάσταση του συστήματος. Δείχνουμε ότι πράγματι υπάρχουν κλάσεις γραμμικών συστημάτων που είναι δύσκολο να μάθει κανείς. Τέτοιες κλάσεις περιλαμβάνουν έμμεσα διεγερμένα συστήματα με μεγάλο βαθμό έμμεσης διέγερσης. Παρόμοια συμπεράσματα ισχύουν τόσο για το πρόβλημα της αναγνώρισης συστήματος όσο και για το πρόβλημα της μάθησης του ελέγχου.