Online minimax optimal density estimation and anomaly detection in nonstationary environments

Abstract

Çevrimiçi anomali tespiti, ağ izleme, siber güvenlik, gözetleme ve sensör arızalarındaki uygulamaları nedeniyle son yıllarda büyük ilgi gördü. Bu amaçla, zaman serilerindeki anomalileri saptamak için verileri sıralı olarak işleyen bir algoritma sunmaktayız. Algoritmamız iki aşamadan oluşmaktadır: yoğunluk tahmini ve anomali tespiti. İlk olarak, normal veriyi modellemek için bir olasılık yoğunluk fonksiyonu oluşturuyoruz. Daha sonra, anomalileri tespit etmek için yeni gözlemlerin yoğunluğunu bir eşik değeriyle karşılaştırıyoruz. Bu problemi çözerken bilişim teorisi yaklaşımı kullanıyoruz ve literatürde ilk defa, güçlü ve deterministik olarak optimal bir anomali tespit algoritması yaratmak için her iki aşamada da minimaks optimal yöntemler önermekteyiz. İlk aşamada, gözlemlenen verilerin üzerinde herhangi bir varsayımda bulunmaksızın durağan olmayan ve üstel aileye ait olan olasılıksal dağılımlar için minimaks optimal olan çevrimiçi yoğunluk tahmin algoritmasını sunuyoruz. Algoritmamızın, zaman ufkunu, temel dağılımın değişimini veya kaynak parametrelerinin değiştiği zamanları önceden bilmesine gerek yoktur. Sonuçlarımızın herhangi bir gözlem sekansı için tutulması garanti edilmektedir. Algoritmamızın ikinci aşaması için, seçilebilecek en iyi eşik değerine karşı logaritmik performans sınırlarına sahip bir çevrimiçi eşik belirleme yöntemi önermekteyiz. Algoritmamız her iki aşamada da log-lineer pişmanlıklar elde etmek için parametrelerini çevrimiçi bir şekilde günceller. Yoğunluk tahmini aşamasında evrensel tahmin perspektifi kullandığımız için, anomali tespit algoritmamız gözetimsiz, yarı gözetimli veya gözetimli şekilde kullanılabilir. Sentetik ve gerçek verilerdeki deneylerle önemli performans kazanımları gösteriyoruz.

Online anomaly detection has attracted significant attention in recent years due to its applications in network monitoring, cybersecurity, surveillance and sensor failure. To this end, we introduce an algorithm that sequentially processes data to detect anomalies in time series. Our algorithm consists of two stages: density estimation and anomaly detection. First, we construct a probability density function to model the normal data. Then, we threshold the density of the newly observed data to detect anomalies. We approach this problem from an information theoretic perspective and, for the first time in the literature, propose minimax optimal schemes for both stages to create an optimal anomaly detection algorithm in a strong deterministic sense. For the first stage, we introduce an online density estimator that is minimax optimal for general nonstationary exponential-family of distributions without any assumptions on the observation sequence. Our algorithm does not require a priori knowledge of the time horizon, the drift of the underlying distribution or the time instances the parameters of the source changes. Our results are guaranteed to hold in an individual sequence manner. For the second stage, we propose an online threshold selection scheme that has logarithmic performance bounds against the best threshold chosen in hindsight. Our complete algorithm adaptively updates its parameters in a truly sequential manner to achieve log-linear regrets in both stages. Because of its universal prediction perspective on its density estimation, our anomaly detection algorithm can be used in unsupervised, semi-supervised and supervised manner. Through synthetic and real life experiments, we demonstrate substantial performance gains with respect to the state-of-the-art.