A GA-based Learning Algorithm for Inducing M-of-N-like Text Classifiers

This paper describes an extension of the classical M-of-N approach to text classification. The proposed hypothesis language is called M-of-N⁺. One distinguishing aspect of this language is its lattice-like structure, which defines a natural ordering in the hypothesis space useful to design effective search operators. To induce M-of-N⁺ concepts, a task-dependent Genetic Algorithm (called GAMoN), which exploits the structural properties of the hypothesis space, is proposed. In experiments on 6 standard, real-world text data sets, we compared GAMoN with one genetic rule induction method, namely, GAssist, and four classical non-evolutionary algorithms, notably, linear SVM, C4.5, Ripper and multinomial Naive Bayes. Experimental results demonstrate the effectiveness of the proposed approach.