Reducing HoeffdingTree Time&Memory Consumption

[ZahirBilal]

Hello onlineML community,

I am evaluating an extremely imbalanced dataset using the following model:
model = compose.Pipeline(ensemble.BaggingClassifier( model=imblearn.RandomSampler(classifier=tree.HoeffdingTreeClassifier), desired_dist= {0: neg_class_dist, 1: 1 - neg_class_dist}, sampling_rate=search_space["sampling_rate"],
First, I fine-tuned the desired_dist and sampling_rate parameters to get an idea of the optimal region.
The model performs very well when I use the optimized parameters. By very well, I mean that it outperforms UOB and OOB and their improved versions when assesed using recall and gmean metrics.

However, the memory and time required for evaluation is extremely high (x100000) compared to UOB and OOB when using the same data set.

I was curious about the reasons for this. UOB uses resampling with replacement, while RandomSampling uses resampling with rejection.

Then I thought about checking the parameters of the base learner (HoeffdingTree).

My question is: which parameters affect the memory and time consumption the most?

I am now experimenting with fine tuning the following parameters:
grace_period, max_size, max_depth, with remove_poor_attrs set to True.

The choice of these parameters is based on my modest understanding of Hoeffding tree algorithms. What do you guys think? Did I choose a wrong approach?

Thanks a lot in advance,
Zahir

[smastelini]

Hi @ZahirBilal, nice strategy to compose trees, btw! I recently published a paper where random sampling is applied for regression, and the results are promising indeed :)

The choice of these parameters is based on my modest understanding of Hoeffding tree algorithms. What do you guys think? Did I choose a wrong approach?

If you want to control memory and time, your best bet is to start with max_depth. This is a straightforward way to constrain the trees and reduce memory usage, though it might lead to underfitting if the tree depth is too shallow. Next, I would try grace_period to avoid attempting to split too often. Increasing this parameter will give you some speed-ups at the cost of predictive performance.

Everything I have mentioned so far affects resource usage indirectly. Alternatively, you could change max_size and memory_estimate_period to control memory usage directly. Besides that, I suggest you check the decision trees guidelines for more details on how to tweak decision trees :)

[ZahirBilal]

Hello Saulo,

thank you so much for your reply! I thought also so, max_depth and grace_period are the key. let's see, I will give a feedback about the results very soon!

I am very interested in reading your paper, could you share the link with me?

[smastelini]

Hi Zahir, here's the paper. You can also e-mail me so I can share a pre-print copy if you want.

About the tree "regularization" strategies, setting max_depth will force the tree to stop splitting once a maximum level is defined. This ought to lead to balanced trees. On the other hand, setting the memory limit directly will force trees to disable the least promising leaves from performing split attempts to save memory. Such unpromising leaves can be at any level of the tree :)

In classification tasks, node purity is used as the heuristic to define how promising a leaf is regarding splits. In other words, leaves whose observed instances belong primarily to a single class will unlikely perform a split. These leaves enter a "deactivated" state, where only statistics related to prediction are updated, but not the split-enabling statistics. Trees reactivate leaves when the memory budget is available.