Generalized Naive Bayes

• A Generalized Naive Bayes (GNB) structure is introduced based on probabilistic graphical models. • The GNB probability distribution gives an approximation at least as good as the one given by the Naive Bayes structure, in terms of Kullback Leibler. • Algorithms introduced: GNB-A, an efficient greedy algorithm and GNB-O to find the optimal structure on the training set given a mild condition. • The new algorithms’ complexities are calculated and compared with other algorithms which exploit conditional independencies. • Feature importance score and feature selection methods were established based on the algorithms introduced. This paper introduces the Generalized Naive Bayes (GNB) structure as an extension of the Naive Bayes structure. We give two new greedy algorithms to find the possible closest GNB structure to the data in terms of minimizing Kullback-Leibler divergence between the probability distribution corresponding to the GNB structure and the data. Both algorithms focus on determining the best-fitting GNB structure based on the training data. The first algorithm adopts a greedy approach to find a good-fitting GNB probability distribution. Then, we introduce a second algorithm, which we prove finds the optimal (best-fitting) GNB probability distribution on the training set under a non-restrictive condition. Based on these algorithms, new feature importance scores and feature selection methods are introduced. The algorithms are compared from theoretical and practical points of view with other probabilistic graphical model-based algorithms.