Reproduce “Maximum Mean Discrepancy on Exponential Windows for Online Change Detection” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Florian Kalinke, Marco Heyden, Georg Gntuni, Edouard Fouché, Klemens Böhm
An online change detection algorithm, Maximum Mean Discrepancy on Exponential Windows (MMDEW), was developed to efficiently apply the statistically powerful Maximum Mean Discrepancy (MMD) to data streams. This method achieves polylogarithmic runtime complexity and logarithmic memory usage while demonstrating superior F1-scores on four out of five real-world datasets compared to state-of-the-art competitors.
Key insights
- The exponential window data structure allows for computing MMD between any two arbitrary groups of historical data in O(log t) time and merging windows in O(log t) time.
- Strategic subsampling in the exponential windows reduces the per-insert operation runtime to O(log^2 t) and memory complexity to O(log t), making MMD scalable for online streaming.
- MMDEW's approach effectively balances the need for a comprehensive, non-parametric test like MMD with the real-time processing requirements of data streams by approximating MMD statistics on summarized data.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.