Independence in classification I recently came across this work: 
http://cvlab.epfl.ch/alumni/oezuysal/ferns.html
which is a balance between the full naive Bayes assumption (full independence between the features) and absolutely no independence assumption. This seems like a very appealing idea. Is there more work like this?
 A: So, Naive Bayes is built on the assumption of conditional independence between the attributes given the class. Violations of this assumption make NB predictions sub-optimal.
Semi-naive Bayes seeks to improve the situation by relaxing the above requirement, and thus tries to optimize the tradeoff between naivety and reliability.
There are quite a bit of papers on that:

*

*"Semi-naive bayesian classifier" (pdf) from 1991 (twenty years ago! looks like it paved the way) extends  of the NB classifier to detect dependencies between the features:


..the naivety [...] can be too drastic in certain domains with strong dependencies between attributes. There is an obvious tradeoff between the 'non-naivety' and the reliability of the approximations of probabilities. In the paper an algorithm is defined that tries to optimize this tradeoff by detecting the dependencies between attributes' values.


*

*"Subsumption Resolution: An Effient and Effective Technique for Semi-Naive Bayesian Learning" (pdf) is some new cool approach which I don't fully understand, but basically they try to identify and prune generalization relationships:


...We present Subsumption Resolution (SR), a new type of semi-naive Bayesian operation that identiﬁes pairs of attribute-values such that one is a generalization of the other and deletes the generalization. SR can be applied at either training time or classiﬁcation time...


*

*"A Comparative Study of Semi-naive Bayes Methods in Classifcation Learning" (pdf) is the best summary paper I've found: they study 8 (eight!) typical SNB algorithms, and discuss time/space complexity and bias/variance tradeoff.

