Efficient nonparametric testing via dynamic trees

Modern society abounds with applications where data is constantly being recorded. As the amount of data increases, the computational efficiency of any algorithms processing this data becomes important. For many applications, it may be important to know if a process being monitored changes in some way. The area of statistics that studies these methods is known as changepoint detection, and applications for this methodology are as diverse as finance, cybersecurity, meteorology and medicine. In finance, one can use this methodology to detect changes in a collection of financial instruments. In cybersecurity, changepoint detection can be used to monitor a computer network to detect intrusions. In medicine, it can be used to monitor the condition of patients in an intensive care unit and provide alerts for when their condition changes. The goal of this work is to develop a computationally-efficient nonparametric changepoint method for use with multivariate data. A nonparametric method makes very few assumptions on the observed data and seeks to detect any type of change. This allows the methodology to be used in a variety of settings, from detecting a change in the average value of the data or detecting a change in an increase in the data's volatility or variance, or other changes in the distribution of the data. However, while nonparametric methods are more versatile, they can be more computationally intensive. Moreover, instead of monitoring a single stream of values, the goal is to monitor multiple parallel streams of data. To achieve this, the first objective will be to extend recently published work, which developed an efficient algorithm for a nonparametric two-sample test in the univariate setting, to the multivariate setting. In essence, a two-sample testing method compares two datasets and attempts to determine if there is a statistically significant difference between them. One could view two-sample testing as a simpler version of the changepoint detection problem, since in changepoint detection we are given a single dataset with the goal of partitioning it into adjacent, significantly different, datasets. We shall start with the bivariate case of two data streams since this already presents significant challenges. The second step will be to create an efficient changepoint detection algorithm in the bivariate case using this two-sample test. If possible, we would then extend this to higher dimensions. The main motivating application for this work is the medical setting. Patients in an intensive care unit can have tens of sensors monitoring their vital signs such as blood pressure, body temperature and blood oxygenation levels. Often, some of these measurements are displayed on screens for medical staff to monitor visually. Experienced staff can interpret these visualisations and determine when a patient’s condition is deteriorating, for example, if the patient is at risk of circulatory failure. The goal of this work is to create an algorithm that can provide a basis for monitoring such data and provide timely alerts for medical staff in this environment.