A short note on the efficient random sampling of the multi-dimensional pyramid between a simplex and the origin lying in the unit hypercube
Fieldsend, Jonathan E.
Date: 2005
Publisher
University of Exeter
Abstract
When estimating how much better a classifier is than random allocation in Q-class ROC analysis, we need to sample from a particular region of the unit hypercube: specifically the region, in the unit hypercube, which lies between the Q − 1 simplex in
Q(Q − 1) space and the origin.
This report introduces a fast method for randomly ...
When estimating how much better a classifier is than random allocation in Q-class ROC analysis, we need to sample from a particular region of the unit hypercube: specifically the region, in the unit hypercube, which lies between the Q − 1 simplex in
Q(Q − 1) space and the origin.
This report introduces a fast method for randomly sampling this volume, and is compared to rejection sampling of uniform draws from the unit hypercube. The new method is based on sampling from a Dirichlet distribution and shifting these samples using a draw from the Uniform distribution. We show that this method generates random samples within the volume at a probability ≈ 1/(Q(Q − 1)), as opposed to ≈ (Q − 1)Q(Q − 1) /(Q(Q − 1))! for rejection sampling from the unit hypercube.
The vast reduction in rejection rates of this method means comparing classifiers in a Q-class ROC framework is now feasible, even for large Q.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0