You are given a partially implemented algorithm for Extremely Randomized Trees, a decision-tree ensemble method introduced by Geurts et al. (2006).
Your task is to debug the implementation so that all unit tests pass.
The algorithm is described in the source code of trees.py. Unit tests are provided in test_trees.py. You are encouraged to read the tests and write additional tests, but do not modify the existing tests or docstrings.
You should not hack the tests by hardcoding checks for certain input data or overriding assertion methods to always pass.
Permitted resources:
- You may web search and consult documentation.
- The NumPy documentation may be useful.
You may not use or refer to:
- any other 3rd-party libraries such as scikit-learn
- existing decision tree implementations
- AI assistance (except that AI overview search results in Google are permitted)
Debugging methods:
- You may use print statements, the REPL, and terminal-based debuggers.
- Do not use the graphical debugger.
- To use breakpoints with
pdb, addbreakpoint()to your source code and run a specific test withpytest -k test_name --pdb, or run all tests withpytest --pdb. - The RUN button will hang if it hits a breakpoint.
- To use the REPL, run
ipythonin the terminal.
Hint: all test cases are of equal point value, but test_small_features and test_ensemble are the most difficult, so you may want to leave them until the end.
Time limit: 30 secondsMemory limit: 4g
This problem asks you to debug an Extremely Randomized Trees implementation, focusing on recursive tree building, random feature sampling, threshold selection, leaf prediction by majority vote, and ensemble prediction across multiple trees. The tricky parts are the boundary cases: too few samples, constant features, empty splits, and the exact traversal rule in prediction (strictly less goes left, otherwise right). It is primarily a NumPy-based recursive algorithm debugging task, with emphasis on index handling and stopping conditions rather than rewriting the model from scratch.
