Exact upper and lower bounds on the misclassification probability
Exact lower and upper bounds on the best possible misclassification probability for a finite number of classes are obtained in terms of the total variation norms of the differences between the sub-distributions over the classes. These bounds are compared with the exact bounds in terms of the conditional entropy obtained by Feder and Merhav.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Oblivious Bounds on the Probability of Boolean Functions
This paper develops upper and lower bounds for the probability of Boolean functions by treating multiple occurrences of variables as independent and assigning them new individual probabilities. We call this approach diss…
ManagementBounds on the Number of Measurements for Reliable Compressive Classification
This paper studies the classification of high-dimensional Gaussian signals from low-dimensional noisy, linear measurements. In particular, it provides upper bounds (sufficient conditions) on the number of measurements re…
ClassificationGeneral ClassificationExact Exponent in Optimal Rates for Crowdsourcing
In many machine learning applications, crowdsourcing has become the primary means for label collection. In this paper, we study the optimal error rate for aggregating labels provided by a set of non-expert workers. Under…
Exact Upper and Lower Bounds for the Output Distribution of Neural Networks with Random Inputs
We derive exact upper and lower bounds for the cumulative distribution function (cdf) of the output of a neural network (NN) over its entire support subject to noisy (stochastic) inputs. The upper and lower bounds conver…
Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport
Optimal Transport (OT) is a fundamental tool for comparing probability distributions, but its exact computation remains prohibitive for large datasets. In this work, we introduce novel families of upper and lower bounds …