A parallel hill-climbing algorithm to generate a subset of irreducible testors

Abstract

The generation of irreducible testors from a training matrix is an expensive computational process: all the algorithms reported have exponential complexity. However, for some problems there is no need to generate the entire set of irreducible testors, but only a subset of them. Several approaches have been developed for this purpose, ranging from Univariate Marginal Distribution to Genetic Algorithms. This paper introduces a parallel version of a Hill-Climbing Algorithm useful to find a subset of irreducible testors from a training matrix. This algorithm was selected because it has been one of the fastest algorithms reported in the state-of-the-art on irreducible testors. In order to efficiently store every different irreducible testor found, the algorithm incorporates a digital-search tree. Several experiments with synthetic and real data are presented in this work.