can be handled with by introducing artificial, random 'contrast variables' [29, 31, 27], which are then used as a reference.

## 1.4 Boruta

Based on those observations, we have developed an alternative heuristics algorithm for *all relevant* feature selection - Boruta [27, 17, 18]. It evaluates the relevance of variables in the information system by comparing the importance measure provided by random forest for the original attributes with that obtained for the artificially added random attributes. To this end it trains random forest classifier on the dataset extended with random contrast attributes, obtained by randomly shuffling values of original attributes between objects. Then, for each attribute, it is tested whether its importance is higher than the maximal importance achieved by any contrast attribute. In order to obtain statistically significant results this procedure is repeated several times, with contrast variables generated independently for each iteration. Boruta algorithm is implemented as an R [25] package, and is available from CRAN.

## 1.5 Artificial Contrasts With Ensembles

Another algorithm that can be used for the all-relevant feature selection is the modification of the ACE procedure proposed by Tuv and co-workers [31, 30]. The general idea of the ACE algorithm is similar to the principle used by Boruta - in order to establish absolute importance of the attribute the algorithm compares the importance of a real attribute with that of artificially constructed random features. However, in contrast to Boruta, ACE is not removing found irrelevant variables to boost quality of importance measure but removes the effects of found important variables to allow more subtle interactions to appear. Also the details of testing relevance are different. The algorithm used here is an implementation of the original ACE procedure described in [31], yet adopted to use the same source of importance measure as Brouta, namely using standard random forest tree growing procedure and larger forests (500 trees instead of 10).

## 2 Related Work

Bayesian network inference is often performed as a wrapper over Na¨ıve Bayes classifiers and could be used for all-relevant feature selection. However, since in all practical implementations the search for simple and previously postulated forms of node-node interactions [22, 23, 21], these methods are not suitable for finding the non-trivial attributes, what is a subject of this study.

The algorithm of Rogers & Gunn [26] uses internals of random forest construction for feature selection. It relies on a theoretical model giving an estimate of the information gain of a split done on a non-informative attribute, which, averaged over the forest, is used to test the relevance of original attributes. This method, while elegant, is not particularly good at discerning between relevant