Finite-memory classification of Bernoulli sequences using reference samples (Corresp.)

1 May 1974

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory

Vol. 20 (3) , 384-387
https://doi.org/10.1109/tit.1974.1055213

Abstract

It is shown that in two-way Bernoulli classification problems deterministic machines can perform as well as optimal randomized machines if their memory is increased by less than one bit. This is accomplished by allowing the algorithm to observe samples from both classes, thus in effect using the data source itself to provide the necessary randomization. An application to a simple communication problem is indicated.

Keywords

This publication has 3 references indexed in Scilit:

The effects of randomization on finite-memory decision schemes
IEEE Transactions on Information Theory, 1972
On Memory Saved by Randomization
The Annals of Mathematical Statistics, 1971
Learning with Finite Memory
The Annals of Mathematical Statistics, 1970