Skip to main content

A rate-distortion framework for supervised learning

Publication ,  Conference
Nokleby, M; Beirami, A; Calderbank, R
Published in: IEEE International Workshop on Machine Learning for Signal Processing, MLSP
November 10, 2015

An information-theoretic framework is presented for bounding the number of samples needed for supervised learning in a parametric Bayesian setting. This framework is inspired by an analogy with rate-distortion theory, which characterizes tradeoffs in the lossy compression of random sources. In a parametric Bayesian environment, the maximum a posteriori classifier can be viewed as a random function of the model parameters. Labeled training data can be viewed as a finite-rate encoding of that source, and the excess loss due to using the learned classifier instead of the MAP classifier can be viewed as distortion. A strict bound on the loss-measured in terms of the expected total variation-is derived, providing a minimum number of training samples needed to drive the expected total variation to within a specified tolerance. The tightness of this bound is demonstrated on the classification of Gaus-sians, for which one can derive closed-form expressions for the bound.

Duke Scholars

Published In

IEEE International Workshop on Machine Learning for Signal Processing, MLSP

DOI

EISSN

2161-0371

ISSN

2161-0363

ISBN

9781467374545

Publication Date

November 10, 2015

Volume

2015-November
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Nokleby, M., Beirami, A., & Calderbank, R. (2015). A rate-distortion framework for supervised learning. In IEEE International Workshop on Machine Learning for Signal Processing, MLSP (Vol. 2015-November). https://doi.org/10.1109/MLSP.2015.7324319
Nokleby, M., A. Beirami, and R. Calderbank. “A rate-distortion framework for supervised learning.” In IEEE International Workshop on Machine Learning for Signal Processing, MLSP, Vol. 2015-November, 2015. https://doi.org/10.1109/MLSP.2015.7324319.
Nokleby M, Beirami A, Calderbank R. A rate-distortion framework for supervised learning. In: IEEE International Workshop on Machine Learning for Signal Processing, MLSP. 2015.
Nokleby, M., et al. “A rate-distortion framework for supervised learning.” IEEE International Workshop on Machine Learning for Signal Processing, MLSP, vol. 2015-November, 2015. Scopus, doi:10.1109/MLSP.2015.7324319.
Nokleby M, Beirami A, Calderbank R. A rate-distortion framework for supervised learning. IEEE International Workshop on Machine Learning for Signal Processing, MLSP. 2015.

Published In

IEEE International Workshop on Machine Learning for Signal Processing, MLSP

DOI

EISSN

2161-0371

ISSN

2161-0363

ISBN

9781467374545

Publication Date

November 10, 2015

Volume

2015-November