Described are techniques used automatic generation of classification rules used in machine learning. A single rule is formed of one or more logical expressions and an associated target. Using a set of training data, rules are formed one logical expression at a time using special data structures that require each feature to be sorted only once per rule formation. The FOIL gain metric is used in determining optimal splits for categorical features. Rule formation ceases with the production of five bad rules in which a bad rule is one in which there are more negative than positive examples in the training data set.