Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Conference Paper

Probabilistic Classifiers and the Concepts they Recognize


Jaeger,  Manfred
Programming Logics, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Jaeger, M. (2003). Probabilistic Classifiers and the Concepts they Recognize. In Proceedings of the Twentieth International Conference on Machine Learning (ICML-03) (pp. 266-273). Menlo Park, USA: AAAI Press.

Cite as:
We investigate algebraic, logical, and geometric properties of concepts recognized by various classes of probabilistic classifiers. For this we introduce a natural hierarchy of probabilistic classifiers, the lowest level of which comprises the naive Bayesian classifiers. We show that the expressivity of classifiers on the different levels in the hierarchy is characterized algebraically by separability with polynomials of different degrees. A consequence of this result is that every linearly separable concept can be recognized by a naive Bayesian classifier. We contrast this result with negative results about the naive Bayesian classifier previously reported in the literature, and point out that these results only pertain to specific learning scenarios for naive Bayesian classifiers. We also present some logical and geometric characterizations of linearly separable concepts, thus providing additional intuitive insight into what concepts are recognizable by naive Bayesian classifiers.