A CUDA-based hill-climbing algorithm to find irreducible testors from a training matrix

Irreducible testors have been used to solve feature selection problems. All the exhaustive algorithms reported for the generation of irreducible testors have exponential complexity. However, several problems only require a portion of irreducible testors (only a subset of all). The hill-climbing algorithm is the latest approach that finds a subset of irreducible testors. So this paper introduces a parallel version of the hill-climbing algorithm which takes advantage of all the cores available in the graphics card because it has been developed on a CUDA platform. The proposed algorithm incorporates a novel mechanism that improves the exploration capability without adding any extra computation at the mutation step, thus increasing the rate of irreducible testors found. In addition, a Bloom filter is incorporated for efficient handling of duplicate irreducible testors. Several experiments with synthetic and real data, and a comparison with other state-of-the-art algorithms are presented in this work.