Efficient exhaustive search for synergistic informative variables
Witold Remigiusz Rudnicki, Paweł Tabaszewski, Szymon Migacz, Andrzej Sułecki, Krzysztof Mnich, Radosław Piliszek · 2016
We present efficient GPU-based implementation of the algorithm for identification of informative variables in high-dimensional datasets. It performs an exhaustive search of all low-dimensional subspaces of the system in a reasonable time. To this end the variables are discretised using rank of object in given variable to assign the class. The models described with n-tuple of variables are built, n can be {2,3,4,5}. The exhaustive search is performed by generating all possible n-tuples. For each n-tuple several random discretisations are generated and the average information gain is collected for each variable. The variable V is deemed informative if there exist n-tuple of variables {V1,..,Vn-1} such, that adding variable V to the description of the system increases information about the decision variable in a statistically significant way. Algorithm is implemented both on CPU and on GPU. It is implemented as R module, and will be available also as a web server. It can be applied to datasets described with millions of variables containing hundreds of thousands of objects. The exhaustive search of the pairwise synergetic effects for the gene expression data for 1000 objects and 20 000 genes takes less than minute a single GPU, while the 3D search will take less than 24 hours. Even the 4D analysis can be performed within a week on a medium size computational cluster equipped with GPUs. Research was supported by the grant from the Polish NSC, grant UMO-2013/09/B/ST6/01550.