Naive Feature Selection: A Nearly Tight Convex Relaxation for Sparse Naive Bayes: The Sparse Multinomial Relaxation Bound Is Tight up to Four Features, ψ(k − 4) ≤ ϕ(k) ≤ ψ(k) ≤ ϕ(k + 4)Research Paper
Naive Bayes is one of the oldest and cheapest classifiers for text and count data: given word counts for documents in two classes, it fits one multinomial distribution per class by maximum likelihood and classifies by the likelihood ratio. Its cost is a single pass over the data. In high-dimensional applications (text, genomics) one also wants the…