How to minimize class weight vector of Random Forest Classifier using CV

Question

What I'd like to do is optimize the class weights of a Random Forest Classifier (using python and the sklearn library) for multiclass classification, in which different misclassification errors have different costs. In other words, I want the Decision Tree to take into account a cost matrix while it is finding the best splits in the data. My question, however, can be extended to any sort of 'Grid Search' approach in ML in which a predefined parameter space is interrogated systematically and the performance of different parameter combinations generated through X-fold CV.

As I understand it, defining different class weights will modify how the Decision Tree algorithm will recognize the best split (as measured by Gini or Entropy, for e.g.) at a given point. As was reported here, one can have a Decision Tree indirectly take into account a cost matrix when splitting the data by setting the class weights.

So I attempted to use scipy.optimize.minimize to find the weight vector which minimizes the misclassification error (as determined by a defined cost matrix).

During the minimization process, different weight vectors are generated by minimize and tested using X-fold CV, which produces a misclassification error score to be passed back to minimize.

The problem is that a RF classifier with the same parameter settings (i.e. weight vector) will produce slightly different CV scores each time it is refitted. This slight variation is enough, I believe, to throw off the minimization of misclassification error using the weight vector. This same phenomenon occurs for regular Decision Trees as well. (Importantly, the X and y data in addition to the defined train/test samples are exactly the same as well).

This is an issue which extends beyond the particular question I am asking, to any situation in which one wishes to interrogate a parameter space via a 'grid search' approach coupled with CV: if the exact same parameter space can produce different CV scores across multiple runs, how can we say that one particular parameter combination is the best?

Any comments/thoughts about the specific question I am asking or the overall question pertaining to Grid Searching are welcome.

Answer 1

First, I address why different random forest runs produce different results. The culprit is at least 1 of the following:

1. Random forest, as the name suggests, is inherently random. At each tree, RF bootstraps your data. At each split, RF is taking a sample of $m$ candidate features and selects the best feature to split on from among those $m$. Given the same data, two separate runs of RF will construct different bootstrap samples, produce different splits and hence different results with high probability.
2. Cross-validation is also random. Randomly allocating your data to $k$ different folds can have many different realizations, so there will be fluctuations in your results based purely on how the data were split.

The solution to this is to not use an optimization algorithm which assumes a deterministic function. Standard optimization methods are sub-optimal when the output is a random variable. Instead, I suggest exhaustively trying weights over a grid. Alternatives do exist, however. Optunity is a software package that advertises improvements in hyperparameter tuning for some problems; I've never used it myself, so I don't know if it is well-suited to this problem. On the other hand, it may be possible to set the random seed to a specific value and therefore make repeatable the random component of the analysis. Caveat: I'm not familiar with Python.

We can still find an optimal tuple of hyperparameters, however. In general, we first select some statistic that we're interested in optimizing, e.g. entropy. Then we compute out-of-sample entropy for your data, given a hyperparameter tuple. Record these results over several realizations of CV. Once we have these results, standard practice is to select the most regularized model within 1 standard error of the minimum entropy found for some tuple. In the case where one is simply optimizing mtry, it manifests as selecting the smallest mtry within one standard error of the minimum. In this context of weighted observations, I'm not sure what "most regularized" means for the weight component. It's possible that you will find a region of the hyperparameter surface which is relatively flat, so anything in that vacinity may be acceptable.