Add an option to train on bootstrap resamples of the training data.

Pros:

• Similar to the original Random Forest
• Can speed up fitting by using less samples

Cons:

• Requires either more copying of data or another indirection layer to acess data

Open questions:

Resolved questions:

• Who should do the reampling - the forest builder before passing the data to the tree builder, or the tree builder after it got passed the data? I don't think it matters for the current sequential implementation, but it may be relevant for parallelization in the future. The tree builder should do the resampling.

Along with #25 this would allow us to implement original Random Forests.

I guess an efficient implementation would sort the data along the feature, start with all samples on one side of the split, and then move one sample after the other across the split. This implementation will require some changes of to the Split-Criterion interface so that samples can be added to and removed from the accumulator.

The way the generic traits are currently organized is too convoluted. Changing something small in a trait such as Splitter leads to non-trivial modifications throughout the codebase. That is not nice :)

I think the current design is too tree-centered and has too many interdependent small traits. Now, I'm thinking about the following separation of concerns:

• Tree Predictor: take sample, find leaf, predict value
• Tree Builder: take slice of samples, recursively find splits, train leaf predictors
• Data Descriptor: takes care of everything data-specific :) This probably requires more explanation (see below).

The tree builder/predictor are quite dumb. They query the data descriptor for everything specific to data: transformation into split features, generating random features, prediction, training of the predictor, ... I think this makes sense, because the type of split feature (simply column, linear combination, superpixel, etc.) really depends on the data set. Also the type of leaf predictor (const-mean, class probabilities, regression, etc.) depends on the data and what one wants to do with the data.

Therefore, the new plan is to have a trait DataDescriptor that handles these things. This trait needs to be implemented for specific data sets. The imlementation can be very generic or highly customized, depending on the user needs. The tree builder/predictor classes delegate all relevant work to this implementation.

... to be continued...

Random forests are particularly well suitet for parallel processing. Trees are independent and could be built in separate threads. The same is true for prediction, but this is usually faster than building, so there may be less benefit.

The current implementation mutates the training data. This is not nice for threads, but copying the data once per thread may not be such a big deal. Bootstrapping (#25) will come with additional copies/references anyway.

Version 0.1.0 marks the end of the experimental development period. It will focus on functionality rather than usability.

Non-goals:

• Ease of use
  • Don't provide impls of Data traits for builtin types. This is difficult because of conflicts.(i.e. a regressor and a classifier may both want to implement SampleDescription for [X], but they can't because they require different SampleDescriptions.) This prevents usage like model.predict([5]). Instead this would need to be written as something like model.predict(Sample::new([5], ())).

To-Dos:

• README
• Basic documentation
• Structure: how to organize modules, traits, structs, ...
• Usable high-level API (simple but flexible)
  • ExtraTreesRegressor
  • ExtraTreesClassifier
  • RandomForest
    • Bootstrapping: #25
    • CART: #27
    • Regressor
    • Classifier
• More low-level components
  • Probabilistic leaf predictors
    • ConstGaussian
    • LinearRegression
  • Prototype Probabilistic/Soft Tree components