On Making Stochastic Classifiers Deterministic

Stochastic classifiers arise in a number of machine learning problems, and have
become especially prominent of late, as they often result from constrained
optimization problems, \eg for fairness, churn, or custom loss optimization.
Despite their utility, the inherent randomness of stochastic classifiers may be
problematic to use in practice for a variety of practical reasons. In this
paper, we attempt to answer the theoretical question of how well a stochastic
classifier can be approximated by a deterministic one, and compare several
possible approaches, proving lower and upper bounds. We also experimentally
investigate the pros and cons of these methods, not only in regard to how
successfully each deterministic classifier approximates the original stochastic
classifier, but also in terms of how well each addresses the other issues
that can make stochastic classifiers undesirable.

• Machine Intelligence