Replace random forest

[benjamc]

Issue: Installation of cpp difficult, replace by sth pythonic.

• possible alternative: Romain Egele, https://github.com/deephyper/deephyper/blob/develop/deephyper/skopt/learning/forest.py#L83
• what is special about our pyrfr package?
• check installation of smac for python 3.11 → does swig get installed? if not, what is missing? → check github workflows (see Eddies comment Feb 23rd in SMAC3)

H.S.:

• RF implemented as described in Algorithm runtime prediction: Methods & evaluation Frank Hutter∗, Lin Xu, Holger H. Hoos, Kevin Leyton-Brown. in Section 4.3.2. SMAC uses same implementation but different HPs
• changes related to bias/variance → F. reduces variance
• in SMAC: no compute law of total variance used. H.S. tried using it with it, leading to worse performance.
• max features is really function dependent but should not be a problem. Maybe optimizing HPs of scikit learn is enough. BBOB: extremely randomized forests(scikit learn skopt (bias/variance) works a bit better.
• Idea: Integrate skopt models into SMAC

[hadarshavit]

I investigated it a bit more. In the original SMAC (see extended version: https://www.cs.ubc.ca/labs/algorithms/Projects/SMAC/papers/10-TR-SMAC.pdf, section 4.1 "Transformations of the Cost Metric") they explain the transformation in the aggregation of the leaves samples (which happens in line 222 in the current SMAC implementation https://github.com/automl/SMAC3/blob/9d194754a5fed3ec48be06987cfc24ee99b76af5/smac/model/random_forest/random_forest.py#L222)

Note that the current implementation computes each leaf value for every sample. It can also create huge matrices (the "preds_as_array" matrix).

I check the scikit-learn implementation of random forest. There is an option to set the DecesionTreeRegressor split to "random" instead of "best" (https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html#sklearn.tree.DecisionTreeRegressor), which I think is more similar to the SMAC implementation. To have the log-transformations, a change to the criterion is required (i.e, compute the node value in a different way https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_criterion.pyx#L1032). Such change should be possible as different criteria already use different terminal values ("MSE and Poisson deviance both set the predicted value of terminal nodes to the learned mean value of the node whereas the MAE sets the predicted value of terminal nodes to the median" from https://scikit-learn.org/stable/modules/tree.html#regression-criteria)

[bbudescu]

Sorry to barge in like this. I noticed that now there's a PyPI package for swig that can be installed via pip. Perhaps that makes life a bit easier for you and for the folks at home having to install swig as a build-dep for pyrfr either from OS or from conda.

Now, if you already knew about it, I'm sorry. I just assumed that, since the installation docs list it as a prerequisite, I thought that initial step might be now, perhaps, eliminated.