Median of Forests for Robust Density Estimation

Hongwei Wen, University of Twente, Annika Betken, University of Twente, Tao Huang, LINK-TO · 2025

Read Median of Forests for Robust Density Estimation by Hongwei Wen, University of Twente, Annika Betken, University of Twente, Tao Huang, LINK-TO (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-15157.txt.

Introduction

Outliers poison density estimates, and a 2025 arXiv paper by Hongwei Wen, Annika Betken, and Tao Huang armors the forest method against them. A single forest estimate already shrugs off far away outliers, since they never enter the local cells. Nearby ones still bite.

Their fix takes the median across many forests, each grown on a subsample of the data. Theory, using a new count of local outliers, shows the median version keeps the clean data convergence rate even when outliers grow polynomially common, a regime where kernel methods fail. Real data tests and an anomaly detection demo back the math.

Catalog record

CREATORHongwei Wen, University of Twente, Annika Betken, University of Twente, Tao Huang, LINK-TO
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-15157

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Median of Forests for Robust Density Estimation Hongwei Wen, University of Twente, Annika Betken, University of Twente, Tao Huang, LINK-TO Abstract Robust density estimation refers to the consistent estimation of the density function even when the data is contaminated by outliers. We find that existing forest density estimation at a certain point is inherently resistant to the outliers outside the cells containing the point, which we call non-local outliers , but not resistant to the rest local outliers . To achieve robustness against all outliers, we propose an ensemble learning algorithm called medians of forests for robust density estimation ( MFRDE ), which adopts a pointwise median operation on forest density estimators fitted on subsampled datasets. Compared to exsiting robust kernel-based methods, MFRDE enables us to choose larger subsampling sizes, sacrificing less accuracy for density estimation while achieving robustness. On the theoretical side, we introduce the local outlier exponent to quantify the number of local outliers. Under this exponent, we show that even if the number of outliers reaches a certain polynomial order in the sample size, MFRDE is able to achieve almost the same convergence rate as the same algorithm on uncontaminated data, whereas robust kernel-based methods fail. On the practical side, real data experiments show that MFRDE outperforms existing robust kernel-based methods. Moreover, we apply MFRDE to anomaly detection to showcase a further application. Keywords: density estimation; robust statistics; random forest; median of means 1 Introduction Robust density estimation has drawn attention across various fields in statistics and machine learning due to its wide range of applications: Lin (2010) presents a robust mixture modeling framework using the multivariate skewed t -distributions for unsupervised clustering. Hill (2015) uses robust density estimation to model financial data that exhibit heavy tails and outliers. More recently, Yoo et al. (2022) base the identification of adversarial examples in text and image classification datasets on robust density estimation. Not least, Humbert et al. (2022) apply robust density estimation to anomaly detection problems. A robust density estimator refers to a density estimator that remains consistent when the training data is contaminated by outliers. In order to construct a robust density estimator, Diggle (1975) proposes some compound estimators for the spatial patterns, which exhibit improved robustness compared with the simple estimators. Moreover, Jain and Orlitsky (2021) reduces the robust density estimation problem to robust learning of the probability of all subsets of size at most k of a larger discrete domain, but their study mainly focuses on the approximately piecewise polynomial distributions. Among other robust density estimators, it is remarkable that many studies focus on modifications of KDE Hang et al. (2018) , which is probably the most popular, commonly used and certainly mathematically the most studied density estimation method. For instance, by combining KDE with M-estimation, Kim and Scott (2012) establishes a robust kernel density estimation (RKDE) method that is insensitive to contamination of the training sample. Moreover, a different, non-parametric construction for a robust kernel density estimator, the scaled and projected KDE (SPKDE), can be found in Vandermeulen and Scott (2014) . Last but not least, Humbert et al. (2022) introduces a robust non-parametric density estimator combining KDE and the Median-of-Means principle (MoM-KDE). However, in high-dimensional datasets, samples are sparsely distributed, and the distances between them grow. This phenomenon, known as the “curse of dimensionality”, poses challenges for KDE-based methods. Additionally, selecting an appropriate kernel and bandwidth in high dimensions becomes more intricate. Choosing a bandwidth that is too small may induce sensitivity to noise, while opting for a bandwidth that is too large may yield excessively smoothed estimations, leading to a loss of detail. In contrast to KDE-based methods, partition-based density estimation methods demonstrate superior adaptability to the curse of dimensionality. For example, density estimation trees Ram and Gray (2011) and density forests Criminisi et al. (2012) ; Wen and Hang (2022) , partition the feature space into non-overlapping cells, and count the number of samples dropping in each cell to attain the density function estimation. Consequently, the forest density estimation at any specific point depends only on the number of samples in the cells containing the point. Therefore, the consistency of the forest density estimation at a certain point is not influenced by the outliers that are outside the cells containing the point, which we call non-local outliers . However, unfortunately, these methods are not commonly robust since they are sensitive to the outliers within the cells that contains the considered point, which we term local outliers . Against this background, we propose to combine random forests for density estimation with the Median-of-Means principle resulting in a locally adaptive, robust density estimator called medians of forests for robust density estimation ( MFRDE ). More precisely, the value of a corresponding density estimator in a point x corresponds to the (standardized) median of S random forest based density estimators evaluated in x . Given a dataset of size n , random forest based density estimators are each fitted on a subset of size n/S resulting from subampling from the dataset without replacement. Accordingly, a small subsampling size n/S results in a large number of subsets S . Since the number of local outliers is independent of our choice of S , based on the pigeonhole principle, a sufficiently large number of subsets ensures that more than half of all S subsets do not contain any local outliers. As a result, more than half of the S SFDEs are consistent estimators. Among these consistent SFDEs, there must exist one higher and another lower than the median of S SFDEs. Since these two consistent SFDEs can be seen as the upper and lower bound of the median of SFDEs, by the sandwich theorem, the median of the SFDEs is also consistent. Therefore, our MFRDE, being the pointwise median of S SFDEs after proper standardization, emerges asa robust density estimator. The contributions of this paper are summarized as follows. (i) We introduce the concept of local outliers and non-local outliers. We find that the existing forest density estimation methods can only resist to non-local outliers. To achieve robustness against all outliers, we develop a new forest-based algorithm called MFRDE, which is able to rule out the effects of outliers by properly choosing the subsampling size and applying a pointwise median operation to forest estimators. (ii) Theoretically, we introduce the outlier proportion exponent to quantify the number of local outliers. Under this exponent, we establish the consistency and convergence rates of MFRDE under proper parameters. Benefited from the forest method’s inherent resistence to non-local outliers, MFRDE can achieve almost identical convergence rates as the same algorithm applied to uncontaminated data, even if the number of outliers reaches a certain polynomial order in the sample size. (iii) By means of parameter analysis on synthetic datasets, we conduct real data experiments to verify the superiority of our MFRDE over robust kernel-based methods. Moreover, we evaluate the robustness of our algorithm by the anomaly detection task on real-world datasets. 1.1 Notations Let \mu denote the Lebesgue measure and let \mathcal{X}\subset\mathbb{R}^{d} be a compact set with \mu(\mathcal{X})>0 . We denote B_{r} as the centered hypercube of \mathbb{R}^{d} with side length 2r , that is B_{r}:=[-r,r]^{d}=\{x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}:x_{i}\in[-r,r],i=1,\ldots,d\} , and write B_{r}^{c}:=\mathbb{R}^{d}\setminus[-r,r]^{d} for the

Read the complete text