An application of rate-distortion theory to pattern recognition and classification

摘要

This paper establishes absolute bounds on the amount of memory required to perform pattern-recognition tasks with a misclassification rate not exceeding a specified level. Pattern-recognition activities are viewed as communication channels with sample sets as inputs and decision rules as outputs. Shannon's rate-distortion theory gives rise to language independent bounds on the complexity of class descriptions as a function of the number of samples, the size of the data space, and the error level tolerated.