On the optimality of Naive Bayes with dependent binary features

While Naive Bayes classifier (NB) is Bayes-optimal for independent features, we prove that it is also optimal for two equiprobable classes and two features with equal class-conditional covariances. Although strict optimality does not extend for three features, equal covariances are expected to be beneficial in higher-dimensional spaces. (c) 2005 Elsevier B.V. All rights reserved.