Repository: emlearn/emlearn (language: python)

Issue:
Overflow warnings when converting RandomForestsClassifier
Hi,

Apologies if I'm just missing something obvious but when trying to convert a RandomForestsClassifier (trained on all-integer data) I keep getting tons of these warnings:
```
In file included from tmp/myinlinetree.c:2:
tmp/myinlinetree.h:62312:23: warning: overflow in conversion from ‘int’ to ‘short int’ changes value from ‘66413’ to ‘877’ [-Woverflow]
62312 |   { 6, 1736.5, 62303, 66413 },
      |                       ^~~~~
tmp/myinlinetree.h:65535:23: warning: overflow in conversion from ‘int’ to ‘short int’ changes value from ‘66017’ to ‘481’ [-Woverflow]
65535 |   { 4, 6592.5, 65526, 66017 },
      |                       ^~~~~
tmp/myinlinetree.h:65536:23: warning: overflow in conversion from ‘int’ to ‘short int’ changes value from ‘65809’ to ‘273’ [-Woverflow]
65536 |   { 3, 4978.5, 65527, 65809 },
      |                       ^~~~~
```
Any idea how I could fix that?
I was using this line to convert it, both with and without the dtype argument - same effect.
```
cmodel = emlearn.convert(forest, method='inline', dtype='int32')
```


Discussion / hints:
Hi @mrkajetanp - thank you for reporting. Which platform and compiler is this?
How large is your RandomForest? I believe you might be running out of space to store the leaves - only 16 bits are used, giving max 32767 nodes total (around 282 kB). Try reducing the number of trees and/or limit the depth of the trees?

Running out of nodes should probably be an error (or at the very least a warning) in Python when doing the conversion. Instead of it happening only at compile time.
It was pointed out to me by @mastensg that the leaf values could probably be relative jumps instead of absolute as they are now. That would enable much larger models for the same model size.
> Which platform and compiler is this?

This was on Gentoo Linux with whichever compiler is used by default so presumably gcc?

>  I believe you might be running out of space to store the leaves

Ah yes that'll most likely be it then. Is there any way I could check the exact number of nodes I have in the tree? I know the joblib serialization files for it are much bigger than 282 kB but those two wouldn't exactly be comparable.

> the leaf values could probably be relative jumps

It sounds like that could work and it would be great to support these larger model sizes.  Do you think you'd be able to implement that in the near future? I'd love to use the functionality for some academic research I'm doing at the moment but probably wouldn't have time to dig in and do it myself :/

Gentoo, then I am assuming it is x86_64. But yeah on further thought, it probably is not relevant here.

The number of nodes can be returned using [emlearn.evaluate.trees.model_size_nodes](https://emlearn.readthedocs.io/en/latest/evaluate.html#emlearn.evaluate.trees.model_size_nodes). It takes as input a scikit-learn model.

I cannot promise that I will be able to implement support for larger models in the short term. But I might get a bit more time towards the end of January. A quick hack that might be acceptable for you, being on a not-so-constrained platform, would be to increase the size of datatype used for the leaf nodes.

I quickly checked if relative jumps could be implemented easily. It would require more work unfortunately, as documented in #81

So for now we are limited to max 32768 nodes in a decision tree ensemble.
A model with 32768 will currently take nearly 400 kB (12 bytes per node), which is quite a lot for microcontrollers (our primary target).  A fully grown tree with max_depth=10 takes 2048 nodes, so with such depth n_ensembles would be maximum of 15.
If using max_depth=8 is 512 nodes, it coudl to support 60 fully grown trees.
When using trees that are not fully grown, the number of trees / maximum depth can be somewhat larger than this.

So one should limit n_ensembles and tree depth somehow to constrain model size. There are examples of this in: 
https://emlearn.readthedocs.io/en/latest/auto_examples/trees_hyperparameters.html

Might be possible to give this another chance now, with #62 being merged

Fix patch:
diff --git a/emlearn/eml_trees.h b/emlearn/eml_trees.h
index dadd089..8be01b2 100644
--- a/emlearn/eml_trees.h
+++ b/emlearn/eml_trees.h
@@ -78,7 +78,12 @@ eml_trees_predict_tree(const EmlTrees *forest, int32_t tree_root,
         const float value = features[feature];
         const float point = forest->nodes[node_idx].value;
         //printf("node %d feature %d. %d < %d\n", node_idx, feature, value, point);
-        node_idx = (value < point) ? forest->nodes[node_idx].left : forest->nodes[node_idx].right;
+        const int16_t child = (value < point) ? forest->nodes[node_idx].left : forest->nodes[node_idx].right;
+        if (child >= 0) {
+            node_idx += child;
+        } else {
+            node_idx = child;
+        }
     }
 
     const int16_t leaf = -node_idx-1;
diff --git a/emlearn/evaluate/trees.py b/emlearn/evaluate/trees.py
index c174a0c..20d0e2f 100644
--- a/emlearn/evaluate/trees.py
+++ b/emlearn/evaluate/trees.py
@@ -25,7 +25,7 @@ def model_size_nodes(model, a=None, b=None):
     """
     em = convert_model(model)
     
-    nodes, roots = em.forest_
+    nodes, roots, leaves = em.forest_
     return len(nodes)
 
 def model_size_bytes(model, a=None, b=None, node_size=None):
diff --git a/emlearn/trees.py b/emlearn/trees.py
index f6007dd..e556b78 100644
--- a/emlearn/trees.py
+++ b/emlearn/trees.py
@@ -331,16 +331,25 @@ def assert_valid_child(value):
         assert value >= child_value_min, value
         assert value <= child_value_max, value
 
-    def make_node(index, node):
-        feature, value, left_index, right_index = node
-
-        # XXX: consider using relative jumps?
-        left = left_index
-        right = right_index
+    def encode_child(index, child):
+        if child >= 0:
+            # decision node, use relative jump
+            assert child >= index
+            encoded = child - index
+            # must not become negative, would be confused with a leaf
+            assert encoded >= 0
+        else:
+            # leaf node, leave as-as
+            encoded = child
     
-        assert_valid_child(left)
-        assert_valid_child(right)
+        assert_valid_child(encoded)
+        return encoded
 
+    def make_node(index, node):
+        feature, value, left_child, right_child = node
+
+        left = encode_child(index, left_child)
+        right = encode_child(index, right_child)
         value = cgen.constant(value, dtype=dtype)
 
         return "{{ {}, {}, {}, {} }}".format(feature, value, left, right)
@@ -561,11 +570,6 @@ def __init__(self, estimator, classifier, dtype='float', leaf_bits=None):
         if self.is_classifier:
             self.n_classes = estimators[0].n_classes_
 
-        n_nodes = len(self.forest_[0])
-        max_nodes = 2**15 # limited by int16_t for children in EmlTreeNode structure
-        if n_nodes > max_nodes:
-            raise ValueError(f"Model has {n_nodes} nodes. Max supported is {max_nodes} nodes.")
-
 
         if classifier == 'pymodule':
             # FIXME: use Nodes,Roots directly, as Numpy Array


Test patch:
diff --git a/test/test_trees.py b/test/test_trees.py
index a14c5af..83524d9 100644
--- a/test/test_trees.py
+++ b/test/test_trees.py
@@ -1,8 +1,10 @@
 
+import os
+
 import sklearn
 import numpy
 import numpy.testing
-
+import joblib
 from sklearn import datasets
 from sklearn.ensemble import RandomForestClassifier, RandomForestRegressor
 from sklearn.ensemble import ExtraTreesClassifier, ExtraTreesRegressor
@@ -12,6 +14,8 @@
 from emlearn.evaluate.trees import model_size_nodes
 import pytest
 
+here = os.path.dirname(__file__)
+
 random = numpy.random.randint(0, 1000)
 print('random_state={}'.format(random))
 
@@ -42,7 +46,7 @@
     '1out': datasets.make_regression(n_targets=1, n_samples=100, random_state=random),
 }
 
-METHODS = ['pymodule', 'loadable', 'inline']
+METHODS = ['loadable', 'inline']
 
 @pytest.mark.parametrize("data", CLASSIFICATION_DATASETS.keys())
 @pytest.mark.parametrize("model", CLASSIFICATION_MODELS.keys())
@@ -77,19 +81,28 @@ def test_trees_sklearn_regressor_predict(data, model, method):
 
     numpy.testing.assert_allclose(pred_c, pred_original, rtol=1e-3, atol=2)
 
-def test_trees_too_many_nodes():
-    """should give nice error"""
+@pytest.fixture(scope='module')
+def huge_trees_model():
+    store_classifier_path = os.path.join(here, 'out/test_trees_huge.model.pickle')
     X, Y = datasets.make_classification(n_classes=2, n_samples=1000, random_state=1)
-    estimator = RandomForestClassifier(n_estimators=1000, max_depth=20, random_state=1)
-    estimator.fit(X, Y)
+    est = RandomForestClassifier(n_estimators=1000, max_depth=20, random_state=1)
+    est.fit(X, Y)
+
+    n_nodes = model_size_nodes(est)
+    assert n_nodes >= 90*1000
 
-    with pytest.raises(ValueError) as ex:
-        cmodel = emlearn.convert(estimator, method='loadable')
+    return X, Y, est
 
-    error = str(ex.value).lower()
-    assert 'nodes' in error
-    assert 'model has ' in error
-    assert 'max supported ' in error
+@pytest.mark.parametrize("method", ['loadable', 'inline'])
+@pytest.mark.skipif(not bool(int(os.environ.get('EMLEARN_TESTS_SLOW', '0'))), reason='EMLEARN_TESTS_SLOW not enabled')
+def test_trees_huge(method, huge_trees_model):
+    """Should work just the same as a smaller model"""
+    X, Y, estimator = huge_trees_model
+
+    cmodel = emlearn.convert(estimator, method=method)
+    pred_original = estimator.predict(X)
+    pred_c = cmodel.predict(X)
+    numpy.testing.assert_equal(pred_c, pred_original)
 
 def test_trees_to_dot():
     X, Y = datasets.make_classification(n_classes=2, n_samples=10, random_state=1)