Understanding probabilistic classifiers

Ashutosh Garg, Dan Roth

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Probabilistic classifiers are developed by assuming generative models which are product distributions over the original attribute space (as in naive Bayes) or more involved spaces (as in general Bayesian networks). While this paradigm has been shown experimentally successful on real world applications, despite vastly simplified probabilistic assumptions, the question of why these approaches work is still open. This paper resolves this question. We show that almost all joint distributions with a given set of marginals (i.e., all distributions that could have given rise to the classifier learned) or, equivalently, almost all data sets that yield this set of marginals, are very close (in terms of distributional distance) to the product distribution on the marginals; the number of these distributions goes down exponentially with their distance from the product distribution. Consequently, as we show, for almost all joint distributions with this set of marginals, the penalty incurred in using the marginal distribution rather than the true one is small. In addition to resolving the puzzle surrounding the success of probabilistic classifiers our results contribute to understanding the tradeoffs in developing probabilistic classifiers and will help in developing better classifiers.

Original languageEnglish (US)
Title of host publicationMachine Learning
Subtitle of host publicationECML 2001 - 12th European Conference on Machine Learning, Proceedings
EditorsLuc de Raedt, Peter Flach
Number of pages13
ISBN (Print)3540425365, 9783540425366
StatePublished - 2001
Event12th European Conference on Machine Learning, ECML 2001 - Freiburg, Germany
Duration: Sep 5 2001Sep 7 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th European Conference on Machine Learning, ECML 2001

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Understanding probabilistic classifiers'. Together they form a unique fingerprint.

Cite this