A Paradigm for Class Identification Problems

Sanjeev R. Kulkarni, David N C Tse

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

The following problem arises in many applications involving classification, identification, and inference. There is a set of objects X, and a particular x є X is chosen (unknown to us). Based on information obtained about x in a sequential manner, we wish to decide whether x belongs to one class of objects A0 or a different class of objects A1. We study a general paradigm applicable to a broad range of problems of this type, which we refer to as problems of class identification or discernibility. We consider various types of information sequences, and various success criteria including discernibility in the limit, discernibility with a stopping criterion, uniform discernibility, and discernibility in the Cesaro sense. We consider decision rules both with and without memory. Necessary and sufficient conditions for discernibility are provided for each case in terms of separability conditions on the sets A0 and A1. We then show that for any sets A0and A1, various types of separability can be achieved by allowing failure on appropriate sets of small measure. Applications to problems in language identification, system identification, and discrete geometry are discussed.

Original languageEnglish (US)
Pages (from-to)696-705
Number of pages10
JournalIEEE Transactions on Information Theory
Volume40
Issue number3
DOIs
StatePublished - May 1994

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Cesaro sense
  • Classification
  • discernibility
  • identification
  • in the limit
  • learning
  • memory
  • memoryless
  • stopping rule
  • uniform

Fingerprint Dive into the research topics of 'A Paradigm for Class Identification Problems'. Together they form a unique fingerprint.

Cite this