Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
RooKeysPdf.cxx
Go to the documentation of this file.
1/*****************************************************************************
2 * Project: RooFit *
3 * Package: RooFitModels *
4 * @(#)root/roofit:$Id$
5 * Authors: *
6 * GR, Gerhard Raven, UC San Diego, raven@slac.stanford.edu *
7 * DK, David Kirkby, UC Irvine, dkirkby@uci.edu *
8 * WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu *
9 * *
10 * Copyright (c) 2000-2005, Regents of the University of California *
11 * and Stanford University. All rights reserved. *
12 * *
13 * Redistribution and use in source and binary forms, *
14 * with or without modification, are permitted according to the terms *
15 * listed in LICENSE (http://roofit.sourceforge.net/license.txt) *
16 *****************************************************************************/
17
18/** \class RooKeysPdf
19 \ingroup Roofit
20
21Class RooKeysPdf implements a one-dimensional kernel estimation p.d.f which model the distribution
22of an arbitrary input dataset as a superposition of Gaussian kernels, one for each data point,
23each contributing 1/N to the total integral of the pdf.
24It was inspired by Kyle Cranmer's KEYS package, see
25[the original web page](https://web.archive.org/web/20020705034344/https://www-wisconsin.cern.ch/~cranmer/keys.html).
26
27\note KEYS stands for Kernel Estimating Your Shapes, see
28[the KEYS write-up](https://web.archive.org/web/20010604031632/http://www-wisconsin.cern.ch/~cranmer/KEYS.pdf).
29
30If the 'adaptive mode' is enabled, the width of the Gaussian is adaptively calculated from the
31local density of events, i.e. narrow for regions with high event density to preserve details and
32wide for regions with low event density to promote smoothness. The details of the general algorithm
33are described in the following paper:
34
35Cranmer KS, Kernel Estimation in High-Energy Physics.
36 Computer Physics Communications 136:198-207,2001 - e-Print Archive: hep-ex/0011057,
37 [doi:10.1016/S0010-4655(00)00243-5](https://doi.org/10.1016/S0010-4655(00)00243-5)
38
39The `rho` parameter (default 1) is an overall scale factor for the width of the
40kernels. Values larger than 1 make the kernels wider and give a smoother
41estimate, while values smaller than 1 make them narrower and keep more detail.
42The default corresponds to the usual normal-reference ("rule of thumb")
43bandwidth.
44
45Close to the edges of the observable range the estimate is biased: the kernels
46of events near an edge have no data on the other side to balance them, so the
47density "leaks" out of the range. The `mirror` parameter selects an optional
48boundary correction that reflects the data across an edge. Symmetric mirroring
49adds the reflected events, which is appropriate when the true density is flat at
50the boundary (the estimate keeps a non-zero value there, with zero slope). Asymmetric mirroring
51subtracts the reflected events, which is appropriate when the true density is
52expected to vanish at the boundary. See the RooKeysPdf::Mirror enum for the list
53of options.
54
55For a multi-dimensional version of this pdf, see RooNDKeysPdf.
56**/
57
58#include "TMath.h"
59#include "RooKeysPdf.h"
60#include "RooRealVar.h"
61#include "RooRandom.h"
62#include "RooDataSet.h"
63
64#include "TError.h"
65
66#include <algorithm>
67#include <cmath>
68#include <cstdio>
69#include <iostream>
70#include <limits>
71
72
73const double RooKeysPdf::_nSigma = std::sqrt(-2. *
74 std::log(std::numeric_limits<double>::epsilon()));
75
76////////////////////////////////////////////////////////////////////////////////
77/// coverity[UNINIT_CTOR]
78
82
83////////////////////////////////////////////////////////////////////////////////
84/// Construct a kernel estimation pdf of the observable `xpdf` from its
85/// distribution in `data`.
86///
87/// \param[in] name Name of the pdf.
88/// \param[in] title Title of the pdf, used for plotting.
89/// \param[in] xpdf Observable the pdf is defined in. Its range sets the
90/// boundaries used for the mirror correction and for the
91/// internal binned lookup table.
92/// \param[in] data Dataset whose distribution of `xpdf` is modelled. The width
93/// of each kernel is adapted to the local event density.
94/// \param[in] mirror Optional boundary correction, see the Mirror enum.
95/// \param[in] rho Overall scale factor for the kernel width (default 1);
96/// larger values give a smoother estimate.
97
98RooKeysPdf::RooKeysPdf(const char *name, const char *title, RooAbsReal &xpdf, RooDataSet &data, Mirror mirror, double rho)
99 : RooKeysPdf(name, title, xpdf, static_cast<RooRealVar &>(xpdf), data, mirror, rho)
100{
101}
102
103////////////////////////////////////////////////////////////////////////////////
104/// As above, but reading the input values from a dataset variable `xdata` that
105/// can be different from the observable `xpdf` the pdf depends on.
106///
107/// \param[in] name Name of the pdf.
108/// \param[in] title Title of the pdf, used for plotting.
109/// \param[in] xpdf Observable the pdf is defined in.
110/// \param[in] xdata Variable in `data` whose distribution is modelled. Its
111/// range sets the boundaries used for the mirror correction
112/// and for the internal binned lookup table.
113/// \param[in] data Dataset holding the values of `xdata` to model.
114/// \param[in] mirror Optional boundary correction, see the Mirror enum.
115/// \param[in] rho Overall scale factor for the kernel width (default 1);
116/// larger values give a smoother estimate.
117
118RooKeysPdf::RooKeysPdf(const char *name, const char *title, RooAbsReal &xpdf, RooRealVar &xdata, RooDataSet &data,
119 Mirror mirror, double rho)
120 : RooAbsPdf(name, title),
121 _x("x", "Observable", this, xpdf),
122 _mirrorLeft(mirror == MirrorLeft || mirror == MirrorBoth || mirror == MirrorLeftAsymRight),
123 _mirrorRight(mirror == MirrorRight || mirror == MirrorBoth || mirror == MirrorAsymLeftRight),
124 _asymLeft(mirror == MirrorAsymLeft || mirror == MirrorAsymLeftRight || mirror == MirrorAsymBoth),
125 _asymRight(mirror == MirrorAsymRight || mirror == MirrorLeftAsymRight || mirror == MirrorAsymBoth),
126 _lo(xdata.getMin()),
127 _hi(xdata.getMax()),
128 _binWidth((_hi - _lo) / (_nPoints - 1)),
129 _rho(rho)
130{
131 snprintf(_varName, 128,"%s", xdata.GetName());
132
133 // form the lookup table
135}
136
137////////////////////////////////////////////////////////////////////////////////
138
139RooKeysPdf::RooKeysPdf(const RooKeysPdf &other, const char *name)
140 : RooAbsPdf(other, name),
141 _x("x", this, other._x),
142 _nEvents(other._nEvents),
143 _mirrorLeft(other._mirrorLeft),
144 _mirrorRight(other._mirrorRight),
145 _asymLeft(other._asymLeft),
146 _asymRight(other._asymRight),
147 _lo(other._lo),
148 _hi(other._hi),
149 _binWidth(other._binWidth),
150 _rho(other._rho)
151{
152 // cache stuff about x
153 snprintf(_varName, 128, "%s", other._varName );
154
155 // copy over data and weights... not necessary, commented out for speed
156// _dataPts = new double[_nEvents];
157// _weights = new double[_nEvents];
158// for (Int_t i= 0; i<_nEvents; i++) {
159// _dataPts[i]= other._dataPts[i];
160// _weights[i]= other._weights[i];
161// }
162
163 // copy over the lookup table
164 for (Int_t i= 0; i<_nPoints+1; i++)
165 _lookupTable[i]= other._lookupTable[i];
166
167}
168
169////////////////////////////////////////////////////////////////////////////////
170
172 delete[] _dataPts;
173 delete[] _dataWgts;
174 delete[] _weights;
175
176}
177
178////////////////////////////////////////////////////////////////////////////////
179/// small helper structure
180
181namespace {
182 struct Data {
183 double x;
184 double w;
185 };
186 // helper to order two Data structures
187 struct cmp {
188 inline bool operator()(const struct Data& a, const struct Data& b) const
189 { return a.x < b.x; }
190 };
191}
193 delete[] _dataPts;
194 delete[] _dataWgts;
195 delete[] _weights;
196
197 std::vector<Data> tmp;
198 tmp.reserve((1 + _mirrorLeft + _mirrorRight) * data.numEntries());
199 double x0 = 0.;
200 double x1 = 0.;
201 double x2 = 0.;
202 _sumWgt = 0.;
203 // read the data set into tmp and accumulate some statistics
204 RooRealVar& real = static_cast<RooRealVar&>(data.get()->operator[](_varName));
205 for (Int_t i = 0; i < data.numEntries(); ++i) {
206 data.get(i);
207 const double x = real.getVal();
208 const double w = data.weight();
209 x0 += w;
210 x1 += w * x;
211 x2 += w * x * x;
213
214 Data p;
215 p.x = x, p.w = w;
216 tmp.push_back(p);
217 if (_mirrorLeft) {
218 p.x = 2. * _lo - x;
219 tmp.push_back(p);
220 }
221 if (_mirrorRight) {
222 p.x = 2. * _hi - x;
223 tmp.push_back(p);
224 }
225 }
226 // sort the entire data set so that values of x are increasing
227 std::sort(tmp.begin(), tmp.end(), cmp());
228
229 // copy the sorted data set to its final destination
230 _nEvents = tmp.size();
231 _dataPts = new double[_nEvents];
232 _dataWgts = new double[_nEvents];
233 for (unsigned i = 0; i < tmp.size(); ++i) {
234 _dataPts[i] = tmp[i].x;
235 _dataWgts[i] = tmp[i].w;
236 }
237 {
238 // free tmp
239 std::vector<Data> tmp2;
240 tmp2.swap(tmp);
241 }
242
243 double meanv=x1/x0;
244 double sigmav=std::sqrt(x2/x0-meanv*meanv);
245 double h=std::pow(double(4)/double(3),0.2)*std::pow(_sumWgt,-0.2)*_rho;
246 double hmin=h*sigmav*std::sqrt(2.)/10;
247 // Dividing by 2*sqrt(3) = sqrt(12) turns a width into the standard deviation
248 // of a uniform distribution of that width. Per the original author, this goes
249 // back to inputs that were finely binned histograms rather than unbinned data:
250 // entries spread uniformly over a bin get aggregated into a single sample with
251 // no variance, so the bin width was taken as the spread of that sample.
252 //
253 // Beware that no bin width enters the expression below, so that rationale does
254 // not map onto the code as it stands: what remains is an extra factor of
255 // sqrt(12) with respect to hep-ex/0011057, kept for backwards compatibility.
256 // The same factor appears in RooNDKeysPdf::calculateBandWidth().
257 double norm=h*std::sqrt(sigmav * _sumWgt)/(2.0*std::sqrt(3.0));
258
259 _weights=new double[_nEvents];
260 for(Int_t j=0;j<_nEvents;++j) {
261 _weights[j] = norm / std::sqrt(_dataWgts[j] * g(_dataPts[j],h*sigmav));
262 if (_weights[j]<hmin) _weights[j]=hmin;
263 }
264
265 // The idea below is that beyond nSigma sigma, the value of the exponential
266 // in the Gaussian is well below the machine precision of a double, so it
267 // does not contribute any more. That way, we can limit how many bins of the
268 // binned approximation in _lookupTable we have to touch when filling it.
269 for (Int_t i=0;i<_nPoints+1;++i) _lookupTable[i] = 0.;
270 for(Int_t j=0;j<_nEvents;++j) {
271 const double xlo = std::min(_hi,
272 std::max(_lo, _dataPts[j] - _nSigma * _weights[j]));
273 const double xhi = std::max(_lo,
274 std::min(_hi, _dataPts[j] + _nSigma * _weights[j]));
275 if (xlo >= xhi) continue;
276 const double chi2incr = _binWidth / _weights[j] / std::sqrt(2.);
277 const double weightratio = _dataWgts[j] / _weights[j];
278 const Int_t binlo = static_cast<Int_t>(std::floor((xlo - _lo) / _binWidth));
279 const Int_t binhi = static_cast<Int_t>(_nPoints - std::floor((_hi - xhi) / _binWidth));
280 const double x = (double(_nPoints - binlo) * _lo +
281 double(binlo) * _hi) / double(_nPoints);
282 double chi = (x - _dataPts[j]) / _weights[j] / std::sqrt(2.);
283 for (Int_t k = binlo; k <= binhi; ++k, chi += chi2incr) {
284 _lookupTable[k] += weightratio * std::exp(- chi * chi);
285 }
286 }
287 if (_asymLeft) {
288 for(Int_t j=0;j<_nEvents;++j) {
289 const double xlo = std::min(_hi,
290 std::max(_lo, 2. * _lo - _dataPts[j] + _nSigma * _weights[j]));
291 const double xhi = std::max(_lo,
292 std::min(_hi, 2. * _lo - _dataPts[j] - _nSigma * _weights[j]));
293 if (xlo >= xhi) continue;
294 const double chi2incr = _binWidth / _weights[j] / std::sqrt(2.);
295 const double weightratio = _dataWgts[j] / _weights[j];
296 const Int_t binlo = static_cast<Int_t>(std::floor((xlo - _lo) / _binWidth));
297 const Int_t binhi = static_cast<Int_t>(_nPoints - std::floor((_hi - xhi) / _binWidth));
298 const double x = (double(_nPoints - binlo) * _lo +
299 double(binlo) * _hi) / double(_nPoints);
300 double chi = (x - (2. * _lo - _dataPts[j])) / _weights[j] / std::sqrt(2.);
301 for (Int_t k = binlo; k <= binhi; ++k, chi += chi2incr) {
302 _lookupTable[k] -= weightratio * std::exp(- chi * chi);
303 }
304 }
305 }
306 if (_asymRight) {
307 for(Int_t j=0;j<_nEvents;++j) {
308 const double xlo = std::min(_hi,
309 std::max(_lo, 2. * _hi - _dataPts[j] + _nSigma * _weights[j]));
310 const double xhi = std::max(_lo,
311 std::min(_hi, 2. * _hi - _dataPts[j] - _nSigma * _weights[j]));
312 if (xlo >= xhi) continue;
313 const double chi2incr = _binWidth / _weights[j] / std::sqrt(2.);
314 const double weightratio = _dataWgts[j] / _weights[j];
315 const Int_t binlo = static_cast<Int_t>(std::floor((xlo - _lo) / _binWidth));
316 const Int_t binhi = static_cast<Int_t>(_nPoints - std::floor((_hi - xhi) / _binWidth));
317 const double x = (double(_nPoints - binlo) * _lo +
318 double(binlo) * _hi) / double(_nPoints);
319 double chi = (x - (2. * _hi - _dataPts[j])) / _weights[j] / std::sqrt(2.);
320 for (Int_t k = binlo; k <= binhi; ++k, chi += chi2incr) {
321 _lookupTable[k] -= weightratio * std::exp(- chi * chi);
322 }
323 }
324 }
325 static const double sqrt2pi(std::sqrt(2*TMath::Pi()));
326 for (Int_t i=0;i<_nPoints+1;++i)
327 _lookupTable[i] /= sqrt2pi * _sumWgt;
328}
329
330////////////////////////////////////////////////////////////////////////////////
331
332double RooKeysPdf::evaluate() const {
333 Int_t i = (Int_t)floor((double(_x)-_lo)/_binWidth);
334 if (i<0) {
335// cerr << "got point below lower bound:"
336// << double(_x) << " < " << _lo
337// << " -- performing linear extrapolation..." << std::endl;
338 i=0;
339 }
340 if (i>_nPoints-1) {
341// cerr << "got point above upper bound:"
342// << double(_x) << " > " << _hi
343// << " -- performing linear extrapolation..." << std::endl;
344 i=_nPoints-1;
345 }
346 double dx = (double(_x)-(_lo+i*_binWidth))/_binWidth;
347
348 // for now do simple linear interpolation.
349 // one day replace by splines...
350 double ret = (_lookupTable[i]+dx*(_lookupTable[i+1]-_lookupTable[i]));
351 if (ret<0) ret=0 ;
352 return ret ;
353}
354
356 RooArgSet& allVars, RooArgSet& analVars, const char* /* rangeName */) const
357{
358 if (matchArgs(allVars, analVars, _x)) return 1;
359 return 0;
360}
361
362double RooKeysPdf::analyticalIntegral(Int_t code, const char* rangeName) const
363{
364 R__ASSERT(1 == code);
365 // this code is based on _lookupTable and uses linear interpolation, just as
366 // evaluate(); integration is done using the trapez rule
367 const double xmin = std::max(_lo, _x.min(rangeName));
368 const double xmax = std::min(_hi, _x.max(rangeName));
369 const Int_t imin = (Int_t)floor((xmin - _lo) / _binWidth);
370 const Int_t imax = std::min((Int_t)floor((xmax - _lo) / _binWidth),
371 _nPoints - 1);
372 double sum = 0.;
373 // sum up complete bins in middle
374 if (imin + 1 < imax)
375 sum += _lookupTable[imin + 1] + _lookupTable[imax];
376 for (Int_t i = imin + 2; i < imax; ++i)
377 sum += 2. * _lookupTable[i];
378 sum *= _binWidth * 0.5;
379 // treat incomplete bins
380 const double dxmin = (xmin - (_lo + imin * _binWidth)) / _binWidth;
381 const double dxmax = (xmax - (_lo + imax * _binWidth)) / _binWidth;
382 if (imin < imax) {
383 // first bin
384 sum += _binWidth * (1. - dxmin) * 0.5 * (_lookupTable[imin + 1] +
385 _lookupTable[imin] + dxmin *
386 (_lookupTable[imin + 1] - _lookupTable[imin]));
387 // last bin
388 sum += _binWidth * dxmax * 0.5 * (_lookupTable[imax] +
389 _lookupTable[imax] + dxmax *
390 (_lookupTable[imax + 1] - _lookupTable[imax]));
391 } else if (imin == imax) {
392 // first bin == last bin
393 sum += _binWidth * (dxmax - dxmin) * 0.5 * (
394 _lookupTable[imin] + dxmin *
395 (_lookupTable[imin + 1] - _lookupTable[imin]) +
396 _lookupTable[imax] + dxmax *
397 (_lookupTable[imax + 1] - _lookupTable[imax]));
398 }
399 return sum;
400}
401
403{
404 if (vars.contains(*_x.absArg())) return 1;
405 return 0;
406}
407
408double RooKeysPdf::maxVal(Int_t code) const
409{
410 R__ASSERT(1 == code);
411 double max = -std::numeric_limits<double>::max();
412 for (Int_t i = 0; i <= _nPoints; ++i)
413 if (max < _lookupTable[i]) max = _lookupTable[i];
414 return max;
415}
416
417////////////////////////////////////////////////////////////////////////////////
418
419double RooKeysPdf::g(double x,double sigmav) const {
420 double y=0;
421 // since data is sorted, we can be a little faster because we know which data
422 // points contribute
423 double* it = std::lower_bound(_dataPts, _dataPts + _nEvents,
424 x - _nSigma * sigmav);
425 if (it >= (_dataPts + _nEvents)) return 0.;
426 double* iend = std::upper_bound(it, _dataPts + _nEvents,
427 x + _nSigma * sigmav);
428 for ( ; it < iend; ++it) {
429 const double r = (x - *it) / sigmav;
430 y += std::exp(-0.5 * r * r);
431 }
432
433 static const double sqrt2pi(std::sqrt(2*TMath::Pi()));
434 return y/(sigmav*sqrt2pi);
435}
#define b(i)
Definition RSha256.hxx:100
#define g(i)
Definition RSha256.hxx:105
#define a(i)
Definition RSha256.hxx:99
#define h(i)
Definition RSha256.hxx:106
int Int_t
Signed integer 4 bytes (int)
Definition RtypesCore.h:60
#define R__ASSERT(e)
Checks condition e and reports a fatal error if it's false.
Definition TError.h:139
winID h TVirtualViewer3D TVirtualGLPainter p
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void data
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t hmin
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t r
Option_t Option_t TPoint TPoint const char x2
Option_t Option_t TPoint TPoint const char x1
char name[80]
Definition TGX11.cxx:142
float xmin
float xmax
bool contains(const char *name) const
Check if collection contains an argument with a specific name.
Abstract interface for all probability density functions.
Definition RooAbsPdf.h:32
Abstract base class for objects that represent a real value and implements functionality common to al...
Definition RooAbsReal.h:63
double getVal(const RooArgSet *normalisationSet=nullptr) const
Evaluate object.
Definition RooAbsReal.h:107
bool matchArgs(const RooArgSet &allDeps, RooArgSet &analDeps, const RooArgProxy &a, const Proxies &... proxies) const
Definition RooAbsReal.h:425
RooAbsArg * absArg() const
Return pointer to contained argument.
Definition RooArgProxy.h:46
RooArgSet is a container object that can hold multiple RooAbsArg objects.
Definition RooArgSet.h:24
Container class to hold unbinned data.
Definition RooDataSet.h:32
Class RooKeysPdf implements a one-dimensional kernel estimation p.d.f which model the distribution of...
Definition RooKeysPdf.h:25
double _binWidth
Definition RooKeysPdf.h:89
double _sumWgt
Definition RooKeysPdf.h:75
static constexpr int _nPoints
Definition RooKeysPdf.h:77
double * _dataWgts
Definition RooKeysPdf.h:73
RooKeysPdf()
coverity[UNINIT_CTOR]
double _lookupTable[_nPoints+1]
Definition RooKeysPdf.h:78
double maxVal(Int_t code) const override
Return maximum value for set of observables identified by code assigned in getMaxVal.
bool _mirrorRight
Definition RooKeysPdf.h:83
double _rho
Definition RooKeysPdf.h:90
double _hi
Definition RooKeysPdf.h:89
Char_t _varName[128]
Definition RooKeysPdf.h:88
double g(double x, double sigma) const
Int_t _nEvents
Definition RooKeysPdf.h:71
void LoadDataSet(RooDataSet &data)
Int_t getAnalyticalIntegral(RooArgSet &allVars, RooArgSet &analVars, const char *rangeName=nullptr) const override
Interface function getAnalyticalIntergral advertises the analytical integrals that are supported.
RooRealProxy _x
Definition RooKeysPdf.h:63
double * _weights
Definition RooKeysPdf.h:74
double analyticalIntegral(Int_t code, const char *rangeName=nullptr) const override
Implements the actual analytical integral(s) advertised by getAnalyticalIntegral.
bool _mirrorLeft
Definition RooKeysPdf.h:82
double evaluate() const override
Evaluate this PDF / function / constant. Needs to be overridden by all derived classes.
~RooKeysPdf() override
double _lo
Definition RooKeysPdf.h:89
Mirror
Boundary correction obtained by reflecting the data across the lower and/or upper edge of the observa...
Definition RooKeysPdf.h:31
double * _dataPts
Definition RooKeysPdf.h:72
bool _asymRight
Definition RooKeysPdf.h:85
static const double _nSigma
!
Definition RooKeysPdf.h:69
bool _asymLeft
Definition RooKeysPdf.h:84
Int_t getMaxVal(const RooArgSet &vars) const override
Advertise capability to determine maximum value of function for given set of observables.
Variable that can be changed from the outside.
Definition RooRealVar.h:37
double max(const char *rname=nullptr) const
Query upper limit of range. This requires the payload to be RooAbsRealLValue or derived.
double min(const char *rname=nullptr) const
Query lower limit of range. This requires the payload to be RooAbsRealLValue or derived.
const char * GetName() const override
Returns name of object.
Definition TNamed.h:49
Double_t y[n]
Definition legend1.C:17
Double_t x[n]
Definition legend1.C:17
constexpr Double_t Pi()
Definition TMath.h:40
static uint64_t sum(uint64_t i)
Definition Factory.cxx:2335