PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Kernel Density Estimation

JooSeuk Kim, Clayton D. Scott

arXiv:1107.3133v2stat.MLcs.LGstat.ME

TL;DR

The paper addresses nonparametric density estimation when the training sample is contaminated, a setting in which limited understanding or improvement of KDE has been done. It proposes RKDE by robustly estimating the KDE’s RKHS sample mean via M-estimation, computes it with kernelized IRWLS, and demonstrates robustness through theory and experiments.

  • Problem

    The paper addresses nonparametric density estimation when the training sample is contaminated, where limited work has understood or improved KDE.

  • Method

    RKDE robustly estimates the KDE’s RKHS sample mean via M-estimation and computes the resulting weights with kernelized iteratively re-weighted least squares.

  • Results

    The RKDE’s robustness is demonstrated through a representer theorem, the influence function, and experiments on density estimation, anomaly detection, and benchmark datasets.

  • Takeaways & Limitations

    The method provides a robust kernel density estimator designed for contamination of the training sample.

  • Takeaways & Limitations

    Recovery of f0 requires assumptions on f0, f1, and p, and the method’s success remains contingent on certain conditions on the data-generating distributions.

Abstract

from arXiv · show

We propose a method for nonparametric density estimation that exhibits robustness to contamination of the training sample. This method achieves robustness by combining a traditional kernel density estimator (KDE) with ideas from classical $M$-estimation. We interpret the KDE based on a radial, positive semi-definite kernel as a sample mean in the associated reproducing kernel Hilbert space. Since the sample mean is sensitive to outliers, we estimate it robustly via $M$-estimation, yielding a robust kernel density estimator (RKDE). An RKDE can be computed efficiently via a kernelized iteratively re-weighted least squares (IRWLS) algorithm. Necessary and sufficient conditions are given for kernelized IRWLS to converge to the global minimizer of the $M$-estimator objective function. The robustness of the RKDE is demonstrated with a representer theorem, the influence function, and experimental results for density estimation and anomaly detection.

1 Introduction

The paper develops a robust nonparametric density estimator for contaminated, unlabeled data by replacing KDE’s RKHS sample mean with an M-estimator. The RKDE is efficiently computed and supported theoretically and experimentally for density estimation and anomaly detection.

  • Motivation: The problem is unsupervised estimation of the nominal density f0 from contaminated data without parametric assumptions.The motivating setting includes unlabeled measurements containing nominal and anomalous observations.
  • Robust kernel density estimation: The RKDE combines KDE with M-estimation, interpreting radial PSD-kernel KDE as an RKHS sample mean and robustifying that mean against outliers.This yields a robust kernel density estimator for contamination of the training sample.
  • Computation: KIRWLS computes the RKDE efficiently, with necessary and sufficient conditions for convergence to the global M-estimator minimizer.The RKDE objective generally lacks a closed-form solution, motivating an iterative algorithm.
  • Robustness analysis: A representer theorem shows that the RKDE is a weighted KDE whose weights are smaller for more outlying data points.This characterizes how the estimator reduces the contribution of outliers.
  • Robustness analysis: The influence function and numerical results show that RKDE is less sensitive to outlier contamination than KDE.Experiments on benchmark datasets report improved performance relative to competing methods for density estimation and anomaly detection.
  • Related work: The paper positions RKDE as an application of M-estimation ideas to kernel density estimation, unlike prior related kernel methods designed for other settings.The authors state that RKDE is, to their knowledge, the first such application.

2 Robust Kernel Density Estimation

The paper reframes KDE as a sample mean in an RKHS and robustifies that mean with M-estimation, producing an RKDE that down-weights contamination. Under radial, positive semi-definite kernels, the estimator remains a valid density and is less affected by contaminating points.

  • Assumptions and scope: The construction requires radial, positive semi-definite kernels, and the positive semi-definite assumption excludes some common finite-support density-estimation kernels.For radial kernels, positive semi-definiteness is equivalent to complete monotonicity of the radial function.
  • RKHS formulation: KDE is represented as the sample mean of feature-mapped observations in the RKHS associated with a positive semi-definite kernel.The canonical feature map is Φ(x) = kσ(·, x), and the reproducing property connects RKHS inner products to function evaluation.
  • Robustification: Because its least-squares formulation is sensitive to outliers, KDE is robustified by applying M-estimation to the RKHS feature vectors.The method uses robust loss functions such as Huber’s and Hampel’s losses, whose bounded derivatives limit the effect of large deviations.
  • RKDE construction: The RKDE has a weighted-kernel form with nonnegative weights summing to one, so it is a valid density.The estimator is expressed as a weighted combination of kernels centered at the observations.
  • Empirical illustration: 20 contaminating points significantly alter KDE contours in low-density regions, whereas RKDE contours are much less affected.The experiment uses 200 nominal observations and 20 contaminating points drawn from a uniform distribution.

3 Representer Theorem

The representer theorem shows that RKDE is a convexly weighted combination of kernels centered at the data, with weights that become small for observations assigned low estimated density. Under strict convexity, the stated conditions are also sufficient for global optimality.

  • Representer theorem: The RKDE can be represented as a weighted combination of kernels centered at the observed data points.This representer theorem follows from Gateaux-differential conditions for minimizing the M-estimator objective over the RKHS.
  • Density validity: The representation uses weights wi ≥ 0 whose sum is one, implying that RKDE is a density.The theorem’s weight constraints provide the normalization and nonnegativity needed for a density.
  • Robustness interpretation: When the weighting function is decreasing, observations with low RKDE values receive small weights, down-weighting outlying points.The interpretation follows by taking g equal to the RKDE in the weight formula.
  • Optimality conditions: Strict convexity of the objective makes the representer-theorem conditions sufficient for RKDE to minimize the M-estimator objective globally.Strict convexity can follow from strictly convex non-decreasing ρ, or from convexity, strict increase, n ≥ 3, and a positive-definite kernel matrix.
  • Strict convexity: The objective can be strictly convex even for Huber loss when the additional kernel-matrix condition holds.Huber loss is convex but not strictly convex, yet the stated matrix condition can still imply strict convexity of J.

4 KIRWLS Algorithm and Its Convergence

KIRWLS computes RKDE through successive weighted KDE updates using kernelized IRWLS. Under the stated assumptions, objective values approach stationary points, and strict convexity guarantees convergence to the RKDE in the H-norm.

  • Algorithm: KIRWLS generates a sequence of weighted KDEs by iteratively updating weights and solving weighted least-squares problems.The procedure seeks a fixed point of the RKDE weight equations and extends classical M-estimation through the kernel trick.
  • Computation: The computation has O(n^2) complexity per iteration, and the required number of iterations is typically below 100 in the authors’ experience.Initialization is discussed in the experimental study.
  • Convergence: Under assumptions (A1)–(A3) and nonincreasing ϕ, the KIRWLS objective sequence approaches the set of stationary points of J.The convergence theorem characterizes the sequence through the objective values J(f^(k)).
  • Global convergence: If J is strictly convex, KIRWLS converges to the RKDE in the H-norm.Strict convexity makes the stationary-point set a singleton, yielding convergence to the unique RKDE solution.

5 Influence Function for Robust KDE

The paper extends influence functions to function-valued density estimates and uses them to quantify how contamination changes KDE and RKDE outputs. Robust KDEs show smaller influence from outlying points, both analytically and experimentally.

  • Influence-function framework: The influence function measures how an estimator changes when infinitesimal probability mass is added at x′.For a function estimate, it describes the change at every evaluation point x.
  • Robust KDE influence: Theorem 4 characterizes the RKDE influence function through an implicit equation, while Huber and Hampel losses generally lack a closed-form solution.For the empirical distribution Fn, the derivative can instead be obtained explicitly using RKDE weights.
  • Robust KDE influence: For RKDEs, an outlier’s influence is reduced when its inlyingness is below the average, yielding α′ < 1.The weighting term assigns larger values to more inlying points; standard KDE instead has ϕ ≡ 1 and α′ = 1.
  • Influence-function framework: Because density-estimator influence functions remain bounded as ||x′||→∞, robustness is compared by closeness to the zero function.This comparison targets overall sensitivity rather than boundedness alone.
  • Experimental evidence: In Figure 3, robust KDE influence functions are smaller in absolute value than standard KDE influence functions for tail points x′.The reduction is especially pronounced with Hampel’s loss.
  • Experimental evidence: The paper argues that a smaller increase near an outlier is accompanied by a smaller decrease near training data, reducing overall influence-function norm.The experiments confirm this predicted reduction for outlying x′.

6 Experiments

The experimental setup is described in Section 6.1, and the results are presented in Section 6.2.

  • Section 6.1 describes the experimental setup.
  • Section 6.2 presents the experimental results.
  • The passage identifies separate setup and results subsections for the experiments.

6.1 Experimental Setup

The experimental study uses contaminated versions of 15 benchmark data sets to compare KDE, VKDE, and RKDE across robustness-oriented tasks. Performance comparisons across data sets use Wilcoxon signed-rank tests.

  • Data: The study uses 15 benchmark data sets, originally assembled for classification tasks.The data include Banana, B. Cancer, Diabetes, F. Solar, German, Heart, Image, Ringnorm, Splice, Thyroid, Twonorm, Waveform, Pima Indian, Iris, and MNIST.
  • Contamination design: Training samples combine n0 nominal observations with n1 = ϵ · n0 contaminating points for ϵ from 0 through 0.30.The corresponding anomaly proportion is p = ϵ/(1+ϵ).
  • Compared estimators: The experiments compare KDE, VKDE, and RKDE with Hampel’s loss using Gaussian kernels.The common bandwidth is the median distance from each training point to its nearest neighbor.
  • Evaluation: The evaluation covers influence-function sensitivity, density estimation, and anomaly detection, with task-specific performance measures.The study uses medians of influence measures, KL divergence, and AUC-related evaluation, respectively.
  • Statistical comparison: Across multiple data sets, method differences are assessed with the Wilcoxon signed-rank test using ranked absolute performance differences.The signed-rank statistic is T = min(R1, R2), with larger rank sums identifying the better method.

6.2 Experimental Results

RKDEs are less sensitive to outliers than KDEs and improve density-estimation and anomaly-detection performance as contamination increases. VKDEs perform poorly on KL divergence, while RKDE gains over VKDE in anomaly detection are not significant.

  • Sensitivity using influence function: VKDEs are excluded from the influence-function comparison because the authors report no formula for their influence function.This limitation applies specifically to that robustness comparison.
  • Sensitivity using influence function: RKDEs are less affected by outliers than KDEs across all evaluated data sets.The comparison uses signed-rank statistics and p-values based on influence-function performance measures.
  • Kullback-Leibler divergence: For pure nominal training data, KDEs have smaller KL divergence than RKDEs, but RKDEs estimate f0 more accurately as contamination ϵ increases.VKDEs are worst by KL divergence, while RKDE assigns weights below 1/n to outlying points.
  • Anomaly detection: RKDEs provide better detection probabilities, especially at low false-alarm rates, resulting in higher AUC.Anomaly detectors are evaluated by varying the density threshold and constructing ROC curves.
  • Kullback-Leibler divergence: RKDEs are significantly better than KDEs when ϵ ≥ 0.20 at significance level 0.05.The reported comparison is based on KL divergence across data sets.
  • Anomaly detection: RKDEs are better than VKDEs when ϵ ≥ 0.15, but the difference is not significant.The paper also reports that KSD performs worse in AUC than either RKDE or KDE.

7 Conclusions

The RKDE replaces KDE’s quadratic loss with a robust loss, downweights outlying points, and can be computed by kernelized IRWLS. Its reduced contamination sensitivity is supported by influence-function analysis and experiments, subject to distributional assumptions.

  • RKDE replaces the traditional KDE’s quadratic loss with a robust loss to handle contamination in the training sample.
  • RKDE is a weighted kernel density estimate that assigns smaller weights to more outlying data points.
  • Kernelized iteratively re-weighted least squares computes the RKDE weights efficiently.
  • Reduced sensitivity to contamination is supported by the influence function and experiments on density estimation and anomaly detection.
  • The method assumes contamination below 50%, outlying contaminants, and anomalous components that are not too concentrated; experiments examine contamination up to around 25%.
  • The methodology also applies to decision-region estimation and anomaly detection, and requires only PSD kernels, allowing polynomial and non-Euclidean-domain kernels.

8 Proofs

The proofs establish compactness and strict convexity properties for the RKDE objective, then show that IRWLS decreases the objective and supports convergence under stated conditions.

  • For three distinct points with a positive-definite kernel matrix, the relevant RKHS feature representations satisfy the required linear-independence property.
  • The constructed set D_n is compact, using compactness of A, continuity of W, and the fact that D_n is W’s image of A.
  • Under the stated conditions on the loss, the M-estimator objective J is strictly convex.
  • Kernelized IRWLS constructs each next iterate as a surrogate minimizer, causing J(f^(k)) to decrease monotonically and converge because it is bounded below by zero.
  • The convergence proof uses compactness, subsequence arguments, and uniform convergence of perturbed objectives on D_(n+1).
  • The influence-function analysis relies on strict convexity and assumes bounded Lipschitz loss derivatives, bounded kernels or related functions, and valid limit exchanges.
Loading 1107.3133v2…