soft-tree

soft-tree copied to clipboard

Ozan Irsoy, 2013

Implementation of Soft Decision Trees (for scalar valued regression and binary classification only)

See, "Soft Decision Trees", Ozan Irsoy, Olcay Taner Yildiz, Ethem Alpaydin, 21st International Conference on Pattern Recognition (ICPR), 2012 for details.

If you use this code, please cite:

@inproceedings{irsoy2012soft, title={Soft decision trees}, author={Irsoy, Ozan and Yildiz, Olcay Taner and Alpaydin, Ethem}, booktitle={International Conference on Pattern Recognition}, year={2012}, }

The code is free for academic, non-commercial purposes. Feel free to ask questions: oirsoy [a] cs [o] cornell [o] edu https://www.cs.cornell.edu/~oirsoy/

1. GETTING STARTED VERY QUICKLY

Compile 'toy.cpp' (I suggest, with optimization flags). For this part, a decent C++ compiler should be enough:

g++ toy.cpp -O3

Then run the executable:

./a.out

That's it!
This should learn a Soft Regression Tree on a randomly generated toy dataset with a sinusoid shape. It should also output a file named 'out', in the same directory as the executable, which should have the three columns x, y (true response), y^ (predicted response), which you may plot with your favorite plotting tool.

2. FILES

Core files (important ones):

common.cpp        : Common functions & std::vector operator overloads
|-SoftTree.cpp    : Implementation of Soft Trees
| |   

Other files (not so important ones): | | | |-toy.cpp : main function to do regression on toy data | |-regress.cpp : main function to do regression on real data |-|-classify.cpp : main function to do classification on real data

3. GETTING STARTED RATHER SLOWLY

If you'd like to learn trees on real datasets, 'regress.cpp' or 'classify.cpp' might be helpful. Both files are designed to do a 5x2-CV on UCI datasets with a particular format (check UCI dataset used in the paper here: https://www.cs.cornell.edu/~oirsoy/files/softtree/data.tar.gz for the exact folder structure and file format).

'regress.cpp' is for regression and 'classify.cpp' is for classification.

Here is how to run 'regress.cpp' ('classify.cpp' is similar). Compile:

g++ regress.cpp -O3

Then run as follows:

./a.out <dataset_name> <fold_number>

It will expect a folder <executable_directory>/data/<dataset_name> having the aforementioned format. <fold_number> is in {0..9}, and denotes one of the 5x2 folds. As an example, this small bash script should run the method on 'concrete' dataset over all folds:

for i in {0..9}
do
  ./a.out concrete $i
done

Finally, if you want to replicate the paper (sort of*), you may download the data and scripts:

https://www.cs.cornell.edu/~oirsoy/files/softtree/data.tar.gz
https://www.cs.cornell.edu/~oirsoy/files/softtree/scripts.tar.gz

and extract them into the main folder. Then simply run the following for regression:

g++ regress.cpp -O3
nohup bash regress.sh &

Or the following for classification:

g++ classify.cpp -O3
nohup bash classify.sh &

These will run the algorithm over each dataset in series, over all 10 folds in parallel, as background processes.

*: There are 2 reasons that these will not yield the exact results in the paper. (1) After I refactored my code for release, there were numerical differences in the results. (2) For classification results in the paper, we used a different implementation by Olcay Taner Yildiz (http://haydut.isikun.edu.tr/), hence, there might be differences.

4. DETAILS OF USING THE 'SoftTree' CLASS

You only need 'common.cpp' and 'SoftTree.cpp' for general use.

Firstly, include "SoftTree.cpp" in your main file. There are two class implementations in that file 'SoftTree' and 'Node'. 'Node' simply implements a tree node, so you should probably not bother with it. However, it also implements update routines and recursive functions, so if you want to play with the code it is important.

Parameters:

There is a set of predefined parameters in the beginning of the file 
'SoftTree.cpp' (using the #define keyword),
such as the number of epochs in training of a parent node and their
children, or pre-pruning threshold. You should check these and modify
them according to your data/domain. Current values give reasonable results
on the datasets in the paper.

Prepare your data:

You need two datasets for training, a training set {X, Y}
and a validation set {V, R}. Validation set is used as a pre-pruning set.

X and V should be (vector<vector< double > >), and
Y and R should be (vector< double >) also the following should hold:
X.size() == Y.size() and V.size() == R.size().
This means X[i] is a feature vector with label Y[i] (similarly for V and R).

Note that even if you are doing classification Y[i] and R[i] are still
(double), not (int). This is for convenience. For binary classification,
class labels should be 0.0 or 1.0.

Normalization is important, so make sure that the data has 0 mean and
unit variance for every feature. Normalization of response values might
also be important when doing regression, if they are large or far away from 
0.

Learn the tree:

You may train the tree by simply calling the constructor (there is no
separate train function):

  SoftTree st(X, Y, V, R);
  
You may specify if it is a regression or a classification tree as:

  SoftTree st(X, Y, V, R, 'r'); // regression tree
  SoftTree st(X, Y, V ,R, 'c'); // classification tree

If you do not specify a fifth argument, it is 'r'egression by default.

Test the tree:

'evaluate()' function computes a response value for a feature vector.
If x is (vector<double>) with the appropriate size,

  double y = st.evaluate(x);
  
should return the response value 'y' for 'x'. You may compute the Mean
Squared Error (for regression) or Error Rate (for classification) over
a dataset {U, T}, instead of a single test instance. 
If U is (vector<vector< double > >) and T is (vector<double>)
with appropriate sizes,

  double mse = st.meanSqErr(U, T);
  double err = st.errRate(U, T)

should return the respective error measures. MSE is in [0, infinity) and
Error Rate is in [0, 1] (i.e. you should multiply by 100 to get a percentage
error).

5. TODO

Add save-load functionality to store a trained tree.