Name
Abstract | ||
|---|---|---|
We study high-dimensional asymptotic performance limits of binary supervised classification problems where the class conditional densities are Gaussian with unknown means and covariances and the number of signal dimensions scales faster than the number of labeled training samples. We show that the Bayes error, namely the minimum attainable error probability with complete distributional knowledge and equally likely classes, can be arbitrarily close to zero and yet the limiting minimax error probability of every supervised learning algorithm is no better than a random coin toss. In contrast to related studies where the classification difficulty (Bayes error) is made to vanish, we hold it constant when taking high-dimensional limits. In contrast to VC-dimension based minimax lower bounds that consider the worst case error probability over all distributions that have a fixed Bayes error, our worst case is over the family of Gaussian distributions with constant Bayes error. We also show that a nontrivial asymptotic minimax error probability can only be attained for parametric subsets of zero measure (in a suitable measure space). These results expose the fundamental importance of prior knowledge and suggest that unless we impose strong structural constraints, such as sparsity, on the parametric space, supervised learning may be ineffective in high dimensional small sample settings. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ITW.2013.6691252 | Information Theory Workshop |
Keywords | Field | DocType |
Bayes methods,Gaussian distribution,learning (artificial intelligence),pattern classification,Bayes error,Gaussian distributions,VC-dimension based minimax lower bounds,binary supervised classification problems,class conditional densities,classification difficulty,distributional knowledge,high dimensional supervised learning,high-dimensional asymptotic performance limits,impossibility result,labeled training samples,parametric space,random coin toss,signal dimensions,structural constraints,worst case error probability | Minimax,Supervised learning,Gaussian,Parametric statistics,Artificial intelligence,Coin flipping,Bayes error rate,Mathematics,Machine learning,Binary number,Bayes' theorem | Conference |
ISBN | Citations | PageRank |
978-1-4799-1321-3 | 1 | 0.39 |
References | Authors | |
1 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohammad H. Rohban | 1 | 57 | 5.28 |
| Prakash Ishwar | 2 | 85 | 11.54 |
| Burkay Orten | 3 | 98 | 6.00 |
| William Clement Karl | 4 | 79 | 13.41 |
| Venkatesh Saligrama | 5 | 1350 | 112.74 |