Online Neyman-Pearson Classification With Hierarchically Represented Models

We consider the statistical anomaly detection problem with regard to false alarm rate (or false positive rate, FPR) controllability, nonlinear modeling and computational efficiency for real-time processing. A decision theoretical solution can be formulated as Neyman-Pearson (NP) hypothesis testing (binary classification: anomaly/nominal). In this framework, we propose an ensemble NP classifier (Tree OLNP) that is based on a binary partitioning tree. Tree OLNP generates an ensemble of sample space partitions. Each partition corresponds to an online piecewise linear (hence nonlinear) expert classifier as a union of online linear NP classifiers (union of OLNPs). While maintaining a precise control over the FPR, Tree OLNP generates its overall prediction as a performance driven and time varying weighted combination of the experts. This provides a dynamical nonlinear modeling power in the sense that simpler (more powerful) experts receive larger weights early (late) in the data stream, which manages the bias-variance trade-off and mitigates overfitting/underfitting issues. We mathematically prove that, for any stream, Tree OLNP asymptotically performs at least as well as of the best expert in terms of the NP performance with a regret diminishing in the order <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(1/\sqrt{t})$</tex-math></inline-formula> (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$t:$</tex-math></inline-formula> data size). Our algorithm is computationally highly efficient since it is online and its complexity scales linearly with respect to both the data size and tree depth, and scales twice-logarithmic with respect to the number of experts. We experimentally show that Tree OLNP strongly outperforms the state-of-the-art alternative techniques.