Tractable average-case analysis of naive Bayesian classi

In this paper we present an average-case analysis of the naive Bayesian clas-si er, a simple induction algorithm that performs well in many domains. Our analysis assumes a monotone `M of N ' target concept and training data that consists of independent Boolean attributes. The analysis supposes a known target concept and distribution of instances, but includes parameters for the number of training cases, the number of irrelevant, relevant, and necessary at-tributes, the probability of each attribute, and the amount of class noise. Our approach diers from previous average-case analyses by introducing approxi-mations to achieve computational tractability. This lets us explore the behav-ioral implications of the model for larger training and attribute sets than the earlier exact analyses, and experimental studies show that the analysis makes very accurate predictions despite its use of approximations. In closing, we suggest promising directions for future research on the average-case analysis of induction