Adaptive Random Forest vs Random Forest

[Moura]

Hi,

I'll be delving into Adaptive Random Forest (ARF) in the next few days and wondered if it can yield results similar to Random Forest (RF).

I conducted a simple simulation using an easy 2-dimensional, 2-class problem (image attached).

Data is comprised of 1,000 instances in total. 

I split into 300 test and 700 training.
I created an ARFF file with careful arrangement (300 test instances followed by 700 training instances) to use MOA correctly.

I then executed EvaluatePeriodicHeldOutTest as follows:

EvaluatePeriodicHeldOutTest -l "(meta.AdaptiveRandomForest -s 10 -x moa.classifiers.rules.core.changedetection.NoChangeDetection -p moa.classifiers.rules.core.changedetection.NoChangeDetection)" -s "(ArffFileStream -f input.arff)" -e "(BasicClassificationPerformanceEvaluator -r)" -n 300 -f 700 -d moa_result.csv -c

In summary, I trained the ARF with 700 instances and test on 300, and I did the same thing with Random Forest, also using 10 estimators for comparison.

ARF achieved 49% accuracy, while RF achieved 98% accuracy.
Actually, ARF predicts the same class for all instances, and that is why it gets around 50% right.

Am I configuring something incorrectly, or is this the expected behavior since ARF learns instance by instance?

Thanks in advance.

[Heitor Murilo Gomes]

Hi Moura, 

A few comments that might help you figure out what is happening (and some that are just related to ARF usage): 

(1) If you want to disable drift detection, use the flag option -u (which will also disable the background learners, if you just want to disable background learners, then just use -q). Then, it doesn't matter what option is set for drift detection or warning detection

-u disableDriftDetection
Should use drift detection? If disabled then bkg learner is also disabled

(2) The train and test split was stratified? 

(3) You may want to set the train size to 700 (even though it shouldn't influence the overall execution since your file has only 1000 instances)

-i trainSize (default: 0)

Number of training examples, <1 = unlimited.

(4) Given a small sample of data there is a chance that the trees do not split. 

If you can, and want, you might want to upscale the experiment by using 7000 training instances and 3000 testing instances. 

Regards, 

Heitor

[Moura]

Hi Heitor,

Thank you for your response.

I've made updates to the command line using tips (1) and (3), so thanks for those.

Regarding the other comments:

(2) Was the train and test split stratified?
   Yes.

(4) When working with a small sample of data, there's a chance that the trees may not split. If possible, you might consider scaling up the experiment by using 7000 training instances and 3000 testing instances.

I upscalled to 7000, 3000 and also to 70000, 30000.
However, I'm still experiencing the following:

• Random Forest yields 98% to 99% accuracy.
• Adaptive Random Forest consistently predicts the same class for all testing instances, resulting in 50% accuracy.

Here is the ARFF file for the 10,000-case scenario (7000 training and 3000 testing instances).
Based on my debugging, the file structure appears to be correct, and the system seems to read it accurately.

Note: I added an extra line to the ARFF file because otherwise, the test is not performed due to the following code in EvaluatePeriodicHeldOutTest.java:
After reading all training data, stream.hasMoreInstances() is equal to false, which causes the system to skip the testing part.

  for (instCount = 0; instCount < testSize; instCount++) {
      if (stream.hasMoreInstances() == false) {
break;
      }

Is there a specific test scenario configuration so I can set up everything correctly to ensure the ARF model is working as expected? 

Thank you again for your attention.

[Heitor Murilo Gomes]

Hi Moura, 

Thanks for the extra information. 

1) There are no issues with the file

2) A hoeffding tree (ARF base learner) won't split if we only have one feature available, and by default ARF will be set to use m=60% (which gives us 1 feature per tree). 

3) The following will work just fine (98.07% accuracy). 

EvaluatePeriodicHeldOutTest -l (meta.AdaptiveRandomForest -s 10 -o (Specified m (integer value)) -m 2 -x (ADWINChangeDetector -a 0.001) -p (ADWINChangeDetector -a 0.01) -w -u -q) -s (ArffFileStream -f input.arff) -e (BasicClassificationPerformanceEvaluator -r) -n 3000 -i 7000 -f 1000

Why a Hoeffidng tree won't split if we only have one feature available? 

Splits are decided by checking whether the difference between the merit of the best split and the second best split are greater than epsilon, now if there is only one feature (thus one possible split), the tree will simply never split. This gives us a forest of root nodes which in turn accumulate the observed instances statistics (i.e. class distribution) and make predictions based on that. 

Cheers, 

Heitor

[Heitor Murilo Gomes]

After thinking about it, in fact it should split even given a single feature (specially a numeric feature), so there is something odd about the base learner implementation. 

I will investigate and see what is happening. 

Regards, 

Heitor

[Heitor Murilo Gomes]

Hi Moura, 

There was an issue with the ARFHoeffdingTree implementation when the subspace size (m) = 1. 

I am going to create the PR to solve this issue, in the meantime if you want you can solve the issue by replacing the learnFromInstance(...) in the ARFHoeffdingTree.java with the following implementation. 

This should yield a ~95% accuracy in the toy dataset you provided, even when m=1. 

Finally, thanks for raising this issue, otherwise I might never have checked this edge case

Regards, 

Heitor

@Override
public void learnFromInstance(Instance inst, HoeffdingTree ht) {
this.observedClassDistribution.addToValue((int) inst.classValue(),
inst.weight());
if (this.listAttributes == null) {
int totalInstanceNumberOfAttributes = (inst.numAttributes()-1);
if(this.numAttributes >= totalInstanceNumberOfAttributes || this.numAttributes < 0) {
this.numAttributes = totalInstanceNumberOfAttributes;
this.listAttributes = new int[this.numAttributes];

for (int i = 0; i < totalInstanceNumberOfAttributes ; i++)
this.listAttributes[i] = i;
} else {
this.listAttributes = new int[this.numAttributes];
ArrayList<Integer> allFeatureIndexes = new ArrayList<>();
for (int i = 0; i < totalInstanceNumberOfAttributes ; i++)
allFeatureIndexes.add(i);
for(int i = 0 ; i < this.listAttributes.length ; ++i) {
int randIndex = ht.classifierRandom.nextInt(allFeatureIndexes.size() - 1);
this.listAttributes[i] = allFeatureIndexes.get(randIndex);
allFeatureIndexes.remove(randIndex);
}
}
}

for (int j = 0; j < this.listAttributes.length ; j++) {
int i = this.listAttributes[j];
int instAttIndex = modelAttIndexToInstanceAttIndex(i, inst);
AttributeClassObserver obs = this.attributeObservers.get(i);
if (obs == null) {
obs = inst.attribute(instAttIndex).isNominal() ? ht.newNominalClassObserver() : ht.newNumericClassObserver();
this.attributeObservers.set(i, obs);
}
obs.observeAttributeClass(inst.value(instAttIndex), (int) inst.classValue(), inst.weight());
}
}
}

[Moura]

Hi Heitor,

Thanks for carefully investigating this issue. It's good to know that now the system is working as expected.

Thank you again.