New MILP approach for pattern generation in LAD

Logical Analysis of Data (LAD) is a logic-based learning technique for extracting hidden patterns in data. Typically, term enumeration techniques are used in LAD for generating patterns of various degrees, which, in turn, are used to construct a discriminant to classify different types of data. The term enumeration techniques, however, can be impractical and need be extremely selective as the number of degree d patterns over n Boolean variables is 2 ^d (n d) and grows exponentially with d. In this paper, we propose a new procedure for generating patterns that sequentially solves MILPs involving n binary variables. With the advent of powerful MILP solvers, the new MILP-based procedure presents a practical and efficient way to generating patterns in LAD. In particular, the new procedure will prove useful when the dataset under study requires more complex, higher degree patterns for accurate discovery of knowledge in it. Using the proposed pattern generation procedure, we experiment with two-, three-, and four-class medical databases from the Repository of Machine Learning Databases and Domain Theories maintained by the University of California at Irvine. Experimental results demonstrate that the proposed procedure is effective - in terms of accuracy in learning - as well as efficient - in terms of CPU time required for construction of patterns and discriminant for 100% accuracy in training.