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

Abstract

Irreducible testors have been used to solve feature selection problems. All the exhaustive algorithms re- ported 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 lat- est 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 com- parison with other state-of-the-art algorithms are presented in this work