Probabilistic classifiers and the concepts they recognize

We investigate algebraic, logical, and geomet-ric properties of concepts recognized by vari-ous classes of probabilistic classifiers. For this we introduce a natural hierarchy of probabilis-tic classifiers, the lowest level of which com-prises the naive Bayesian classifiers. We show that the expressivity of classifiers on the differ-ent levels in the hierarchy is characterized alge-braically by separability with polynomials of dif-ferent degrees. A consequence of this result is that every linearly separable concept can be rec-ognized by a naive Bayesian classifier. We con-trast 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 log-ical and geometric characterizations of linearly separable concepts, thus providing additional in-tuitive insight into what concepts are recogniz-able by naive Bayesian classifiers. 1