Data-Driven Reachability and Support Estimation With Christoffel Functions

• 成果类型: Article
• 署名作者: Devonport, Alex; Yang, Forest; El Ghaoui, Laurent; Arcak, Murat
• 署名单位: University of California System; University of California Berkeley; VinUniversity
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3281749
• 发表日期: 2023
• 页码: 5216-5229
• 关键词: estimation; randomized algorithms; Statistical learning; uncertain systems

摘要

In this article, we present algorithms for estimating the forward reachable set of a dynamical system using only a finite collection of independent and identically distributed samples. The produced estimate is the sublevel set of a function called an empirical inverse Christoffel function: empirical inverse Christoffel functions are known to provide good approximations to the support of probability distributions. In addition to reachability analysis, the same approach can be applied to general problems of estimating the support of a random variable, which has applications in data science toward the detection of novelties and outliers in datasets. In applications where safety is a concern, having a guarantee of accuracy that holds on finite datasets is critical. In this article, we prove such bounds for our algorithms under the probably approximately correct (PAC) framework. In addition to applying classical Vapnik-Chervonenkis dimension bound arguments, we apply the PAC-Bayes theorem by leveraging a formal connection between kernelized empirical inverse Christoffel functions and Gaussian process regression models.