A concrete statistical realization of Kleinberg's stochastic discrimination for pattern recognition. Part I. Two-class classification

Dechang Chen*, Peng Huang, Xiuzhen Cheng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

The method of stochastic discrimination (SD) introduced by Kleinberg is a new method in statistical pattern recognition. It works by producing many weak classifiers and then combining them to form a strong classifier. However, the strict mathematical assumptions in Kleinberg [The Annals of Statistics 24 (1996) 2319-2349] are rarely met in practice. This paper provides an applicable way to realize the SD algorithm. We recast SD in a probability-space framework and present a concrete statistical realization of SD for two-class pattern recognition. We weaken Kleinberg's theoretically strict assumptions of uniformity and indiscernibility by introducing near uniformity and weak indiscernibility. Such weaker notions are easily encountered in practical applications. We present a systematic resampling method to produce weak classifiers and then establish corresponding classification rules of SD. We analyze the performance of SD theoretically and explain why SD is overtraining-resistant and why SD has a high convergence rate. Testing results on real and simulated data sets are also given.

Original languageEnglish
Pages (from-to)1393-1412
Number of pages20
JournalAnnals of Statistics
Volume31
Issue number5
DOIs
StatePublished - Oct 2003
Externally publishedYes

Keywords

  • Accuracy
  • Discriminant function
  • Test set
  • Training set

Fingerprint

Dive into the research topics of 'A concrete statistical realization of Kleinberg's stochastic discrimination for pattern recognition. Part I. Two-class classification'. Together they form a unique fingerprint.

Cite this