On the Storage Economy of Error-Tolerating Question-Answering Systems

Abstract

The possibility of saving various computational resources is an argument often advanced in favor of permitting question-answering systems to make occasional errors. In this paper we establish absolute bounds on the amount of memory savings that is achievable with a specified error level for certain types of question-answering systems. Question-answering systems are treated as communication channels carrying information concerning the acceptable answers to an admissible set of queries. Shannon's rate-distortion theory is used to calculate bounds on the memory required for several question-answering tasks. For data retrieval, pattern-classification, and position-matching systems it was found that only small memory gains could be materialized from error-tolerance. In pair-ordering tasks on the other hand, more significant memory savings could be accomplished if small error-rates are tolerated. Similar limitations govern the tradeoffs between error and computation time.