PDE-Foam - a probability-density estimation method using self-adapting phase-space binning

Probability-Density Estimation (PDE) is a multivariate discrimination technique based on sampling signal and background densities defined by event samples from data or Monte-Carlo (MC) simulations in a multi-dimensional phase space. To efficiently use large event samples to estimate the probability density, a binary search tree (range searching) is used in the PDE-RS implementation. It is a generalisation of standard likelihood methods and a powerful classification tool for problems with highly non-linearly correlated observables. In this paper, we present an innovative improvement of the PDE method that uses a self-adapting binning method to divide the multi-dimensional phase space in a finite number of hyper-rectangles (cells). The binning algorithm adjusts the size and position of a predefined number of cells inside the multidimensional phase space, minimizing the variance of the signal and background densities inside the cells. The binned density information is stored in binary trees, allowing for a very fast and memory-efficient classification of events. The implementation of the binning algorithm (PDE-Foam) is based on the MC event-generation package Foam. It is included in the analysis package ROOT and has been developed within the framework of the Toolkit for Multivariate Data Analysis with ROOT (TMVA). We present performance results for representative examples (toy models) and discuss the dependence of the obtained res ults on the choice of parameters. The new PDE-Foam shows improved classification capability for small training samples and reduced classification time compared to the standard PDE-RS method.