- This event has passed.

# Applied Math Seminar – Husheng Li, University of Tennessee, Knoxville

## October 19, 2018 @ 11:00 am - 12:00 pm

Title: Data Driven Quickest Change Detection: In the Spirit of Kullback, Kolmogorov and Shannon

Abstract: Quickest change detection is to detect the unknown change of distribution of random process, which has a wide spectrum of applications in practice such as signal processing, financial data analysis and power grid operation, et al. In traditional quickest change detection algorithms, it is assumed that the distributions before and after the change are known in advance. This assumption is relaxed to unknown post-change distributions in some studies, under the assumption of i.i.d. samples. However, there have not been researches on more generic random processes, such as ergodic processes. In this talk, we will first assume i.i.d. samples and apply the Kullback-Leibler entropy to evaluate the distance between the pre-change and post-change distributions, without knowing the distributions themselves. Then, for generic ergodic random processes (not necessarily Markovian) with deterministic samples, we adopt two approaches to handle the unavailability of probabilistic structures. One approach follows the spirit of Kolmogorov; i.e., we use the Turing machine as the underlying model for generating the samples and consider the Kolmogorov complexity for measuring the model effectiveness. Then, the algorithmic probability, based on the Kolmogorov complexity, is used to turn the deterministic setup into a stochastic one, thus facilitating the application of traditional probabilistic framework. The other approach is to consider an operational representation of probability. Traditional representation of probability distribution is based on the probability on cylinder sets, which is difficult to manipulate when only deterministic samples are available. Therefore, we adopt the typical sequence, which was originally proposed by Shannon and is supported by various approaches in data mining, to represent probability distributions. In the algorithm typical sequences will be mined using a tree structure, and the change of distribution is detected by the change of typical sequence set.