Online anomaly detection in the Neyman-Pearson hypothesis testing framework

Abstract

İstatistiksel anomali algılama problemini, yanlış alarm oranı (veya yanlış pozitif oran, YPO) kontrol edilebilirliğine, doğrusal olmayan modellemeye ve gerçek zamanlı işleme için hesaplama verimliliğine özellikle dikkat ederek ele alıyoruz. Bu soruna yönelik bir karar teorik çözüm, YPO'da kullanıcı tanımlı bir üst sınır kısıtlamasına bağlı olarak, algılama gücünün en üst düzeye çıkarıldığı Neyman-Pearson (NP) hipotez testi (anomaliye karşı nominal) çerçevesinde formüle edilebilir. İlk olarak, NP testini veri odaklı çevrimiçi bir şekilde elde eden, özgün bir NP sınıflandırıcısı (NP-NN) tanıtıyoruz. Tanıtılan sınıflandırıcı (i) istenen YPO ile eşleşen asimetrik bir maliyet yapısı çıkarır ve (ii) ortaya çıkan ampirik riski, yani tip I ve tip II hataların ağırlıklı ortalamasını, en aza indirir. Bu iki adım, tek bir Lagrange maks hedefiyle birlikte yürütülür. Tek bir gizli katman ileri beslemeli sinir ağını baz alan, kompakt ve hesaplama açısından verimli, doğrusal olmayan bir modelleme elde edilir. İlk katman başlangıçta sinüzoidal aktivasyonla radyal tabanlı fonksiyonunun (RTF) çekirdek alanını, yani Fourier özelliklerini, genişletir, onu izleyen ikinci katmanda sınıflandırma yapılır ve genel ağ, stokastik gradyan inişi güncellemeleri ile (NP kısıtlamasına altında) sıralı olarak optimize edilir. Algoritmamızdaki veri işleme, gerçekten çevrimiçidir ve veri boyutuna göre yalnızca doğrusal hesaplama ve sabit alan karmaşıklığına sahip olduğundan, büyük ölçekli veri uygulamaları için uygundur. Kamuya açık ve yaygın olarak kullanılan birçok kıyaslama veri setinde algoritmamızın, en son teknoloji tekniklerinden üstün olduğu deneysel olarak, hassas YPO kontrol edilebilirliğinde, karşılaştırılabilir bir hesaplama ve uzay karmaşıklığıyla NP sınıflandırma hedefi açısından daha iyi, veya önemli ölçüde daha düşük karmaşıklıkla karşılaştırılabilir bir performans elde edilerek gösterilmiştir. NP-NN'nin iki dezavantajı vardır. (i) RBF bant genişliği için kapsamlı çapraz geçerlilik sınaması gerekir, bu da bant genişliği çok küçük (büyük) seçilirse modeli aşırı uyumlamaya (yetersiz uyumlamaya) eğilimli hale getirir ve (ii) bant genişliğinin sabit tutulması da, model uyumsuzluğuna, yani bir veri akışının ilk (son) aşamalarında fazla uyumlamaya (yetersiz uyumlamaya) neden olduğu için sabit modelleme gücüne sebep olmaktadır. Aslında, artan verilerle öğrenilebilirlik giderek arttığından, çevrimiçi uygulamalarda modelleme gücü (doğrusal olmama derecesi) kademeli olarak artırılmalıdır. Modelleme gücünü dinamik olarak kontrol etmek ve uyumlama sorunlarını azaltmak için, ikili bölümleme ağacına dayalı bir topluluk NP sınıflandırıcısı (Tree OLNP) öneriyoruz. Tree OLNP, örnek uzayında, ağaç derinliğinin iki kat üslü sayıda bölüntüler topluluğu oluşturur. Her bölüntü bir çevrimiçi parçalı doğrusal (dolayısıyla doğrusal olmayan) uzman sınıflandırıcıya karşılık gelir ve her uzman esasen doğrusal NP sınıflandırıcılarının bir birleşimidir (OLNP, NP-NN'nin doğrusal versiyonudur). Farklı sayıda bölgeye sahip bölüntüler, farklı modelleme güçlerine sahip uzmanları tanımlar ve vurgulamak isteriz ki herhangi bir düzgün doğrusal olmayan sınıf ayrımı, yeterince güçlü parçalı doğrusal bir uzman tarafından (yeterli sayıda parça ile) modellenebilir. Örneğin, en basit bölüntü/uzman tek bir bölge/parça ile kök düğümdeyken, en güçlü uzman yapraklardadır. Bu ayarda ve YPO üzerinde hassas bir kontrol sağlarken, Tree OLNP, topluluktaki uzmanların performans odaklı ve zamana göre değişen ağırlıklı bir kombinasyonu olarak son tahminini oluşturur. Daha basit (daha güçlü) uzmanlar, veri akışında erken (geç) daha büyük ağırlıklar alır, yanlılık-varyans dengesini yönetir ve dolayısıyla uyum sorunlarını istenildiği gibi azaltır. Herhangi bir akış için, Tree OLNP'nin asimptotik olarak, NP performansı açısından, O(1√t) (t veri boyutudur) ile azalan pişmanlık ile, en az en iyi uzman kadar iyi performans gösterdiğini matematiksel olarak kanıtlıyoruz. Tree OLNP çevrimiçidir ve hesaplama karmaşıklığı, veri boyutuna ve ağaç derinliğine göre doğrusal, uzman sayısına göre de iki kez logaritmik olarak ölçeklenir. Deneysel olarak Tree OLNP'nin en iyi uzmandan daha iyi performans gösterdiğini ve modelleme gücü üzerinde tanıtılan dinamik kontrol ile NP-NN'yi büyük ölçüde iyileştirdiğini gösteriyoruz.Bir algoritma çevrimiçi olarak tasarlansa da, algoritmayı hacimli veri akışı için gerçek zamanlı koşturmak zor olabilir. Gerçek zamanlı işlemenin bu zorluğunu çözmek için, aktif öğrenme yoluyla seçici işlemeyi de değerlendiriyoruz. Bir örnek için yukarıda bahsedilen uzman grubundaki belirsizliği ölçmek için ikili entropiyi kullanarak, Tree OLNP'yi yalnızca belirsizlik yüksekse bir örneği işleme özelliği ile güçlendiriyoruz. Sonuç olarak, YPO kontrol edilebilirliğini korurken, deneylerimizde önemli ölçüde daha az sayıda veri örneği kullanarak, istenen bir NP performansı elde ediyoruz. Son olarak, video akışlarından anormal nesneleri/eylemleri algılamak için bir sistem sunuyoruz. Tanıtılan video işleme sistemi, canlı bir video akışından kareler alır, YoLo nesnelerini çıkarır, gürültü giderici özkodlayıcı ile boyutluluğu azaltır ve aktif Tree OLNP ile anormal faaliyetleri tespit eder. Sabancı Üniversitesi kampüsünden topladığımız set ve kamuya açık 2 veri seti üzerindeki deneysel sonuçlarımız, Tree OLNP'nin video akışlarından anormallikleri tespit etmek için uygun bir seçenek olduğunu göstermektedir.

We consider the statistical anomaly detection problem with particular attention to false alarm rate (or false positive rate, FPR) controllability, nonlinear modeling and computational efficiency for real-time processing. A decision theoretical solution to that problem can be formulated in the Neyman-Pearson (NP) hypothesis testing (anomaly vs nominal) framework in which the detection power is maximized subject to a user defined upper-bound constraint on the FPR. We first introduce a novel NP classifier (NP-NN) that obtains the NP test in a data driven online manner. The introduced classifier (i) infers an asymmetrical cost structure that matches the desired FPR and (ii) minimizes the resulting empirical risk, i.e., the weighted average of type I and type II errors. These two steps are conducted jointly with a single Lagrangian max objective. A compact and computationally efficient nonlinear modeling is achieved based on a single hidden layer feedforward neural network. The first layer initially expands the kernel space of the radial basis function (RBF) with sinusoidal activation, i.e., Fourier features, the second layer follows to classify, and the overall network is sequentially optimized (subject to the NP constraint) via stochastic gradient descent updates. The data processing in our algorithm is truly online, and appropriate for large scale data applications as it only has linear computational and constant space complexity with respect to the data size. Based on many publicly available and widely used benchmark datasets, our algorithm is experimentally shown to be superior to the state-of-the-art techniques with precise FPR controllability, either by outperforming in terms of the NP classification objective with a comparable computational as well as space complexity or by achieving a comparable performance with significantly lower complexity.NP-NN has two disadvantages. (i) It requires extensive cross validations for the RBF bandwidth, making it prone to overfitting (underfitting) if the bandwidth is chosen too small (large), and (ii) it has fixed modeling power since the bandwidth is kept constant, causing a model mismatch, i.e., overfitting (underfitting) in the earlier (later) phases of a data stream. In fact, the modeling power (i.e. the degree of nonlinearity) should be gradually increased in online applications as the learnability gradually improves with increasing data. In order to dynamically control the modeling power and mitigate fitting issues, we additionally propose an ensemble NP classifier (Tree OLNP) that is based on a binary partitioning tree. Tree OLNP creates an ensemble of doubly exponential (in the tree depth) number of partitions of the sample space. Each partition corresponds to an online piecewise linear (hence nonlinear) expert classifier and each expert is essentially a union of linear NP classifiers (OLNP, linear version of NP-NN). Partitions with different number of regions define experts with different modeling powers, and we emphasize that any smooth nonlinear class separation can be modeled by a powerful enough (with sufficient number of pieces) piecewise linear expert. For example, the simplest partition/expert is at the root node with a single region/piece whereas the most powerful one is at the leaves. In this setting, and 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 in the ensemble. Simpler (more powerful) experts receive larger weights early (late) in the data stream, managing the bias-variance trade-off and hence mitigating the fitting issues as desired. We mathematically prove that, for any stream, our 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 O(1/√t) (here, t is the data size). Tree OLNP is online and its computational 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 outperforms the best expert, and largely improves NP-NN by the introduced dynamical control over the modeling power. Even when an algorithm is designed online, running it in real time can still be challenging if the data stream is voluminous. To address this challenge of real time processing, we also consider selective processing via active learning. Using the binary entropy as a measure for the uncertainty in the aforementioned expert ensemble for a given sample, we empower our Tree OLNP with the property of processing a sample only if the uncertainty is high. As a result, while preserving the false alarm controllability, a desirable NP performance is achieved in our experiments with significantly lower number of data instances. We finally introduce a system pipeline to detect abnormal objects/actions from video streams. The introduced video processing system receives frames from a live video stream, extracts the YoLo objects, reduces dimensionality with a denoising autoencoder and detects abnormal activities with active Tree OLNP. Our experimental results, on 3 different datasets from the literature and another one from Sabanci University campus, demonstrate that Tree OLNP is a viable option for detecting abnormalities from video streams.