A fast hardware software platform for computing irreducible testors

• Feature selection is an important task in pattern recognition.
• Testor theory can be used to perform feature selection.
• A testor is a subset of attributes that can discern between objects of different classes.
• We propose a fast hardware software platform for computing irreducible testors.

Among the systems involved with data and knowledge that give answers, solutions, or diagnoses, based on available information; those based on feature selection are very important since they allow us to solve important tasks into pattern recognition and decision making areas. Feature selection consists in finding a minimum subset of attributes that preserves the ability to discern between objects from different classes. Testor theory is a convenient way to solve this problem since a testor is defined as a subset of attributes that can discern between objects from different classes; and an irreducible testor is a minimal subset with this property. However, the computation of these minimal subsets is a problem whose space complexity grows exponentially regarding the number of attributes. Therefore, in the literature, several hardware implementations of algorithms for computing testors, which take advantage of the inherent parallelism in the evaluation of testor candidates, have been proposed. In this paper, a new fast hardware software platform for computing irreducible testors is introduced. Our proposal follows a pruning strategy that, in most cases, reduces the search space more than any other alternative reported in the literature. The experimental results show the runtime reduction achieved by the proposed platform in contrast to other state-of-the-art hardware and software implementations.