Implementation of General Optimal Sparse Decision Tree
Project description
Fast Sparse Decision Tree Optimization via Reference Ensembles
Table of Content
Installation
Installing GOSDT Dependencies
List of external dependencies
The following dependencies need to be installed to build the program.
- Boost - Collection of portable C++ source libraries
- GMP - Collection of functions for high-precision artihmetics
- Intel TBB - Rich and complete approach to parallelism in C++
- WiredTiger - WiredTiger is an high performance, scalable, production quality, NoSQL, Open Source extensible platform for data management
- OpenCL(Optional) - A framework for execution across heterogeneous hardware accelerators.
Bundled Dependencies
The following dependencies are included as part of the repository, thus requiring no additional installation.
- nlohmann/json - JSON Parser
- ben-strasser/fast-cpp-csv-parser - CSV Parser
- OpenCL C++ Bindings 1.2 - OpenCL bindings for GPU computing
Installation
Install these using your system package manager. There are also installation scripts provided for your convenience: trainer/auto
These currently support interface with brew and apt
- Boost -
auto/boost.sh --install
- GMP -
auto/gmp.sh --install
- Intel TBB -
auto/tbb.sh --install
- WiredTiger -
auto/wiredtiger.sh --install
- OpenCL -
auto/opencl.sh --install
Installing GOSDT as a Stand-Alone Command Line Program
./autobuild --install
Installing GOSDT as a Python Library with C++ Extensions
./autobuild --install-python
For more details about GOSDT installation and examples of running pure GOSDT, please see https://github.com/Jimmy-Lin/GeneralizedOptimalSparseDecisionTrees/blob/master/README.md for more details.
Configuration
The configuration is a JSON object and has the following structure and default values:
{
"uncertainty_tolerance": 0.0,
"regularization": 0.05,
"upperbound": 0.0,
"time_limit": 0,
"worker_limit": 1,
"stack_limit": 0,
"precision_limit": 0,
"model_limit": 1,
"verbose": false,
"diagnostics": false,
"depth_budget": 0,
"reference_LB": false,
"path_to_labels": "",
"balance": false,
"look_ahead": true,
"similar_support": true,
"cancellation": true,
"continuous_feature_exchange": false,
"feature_exchange": false,
"feature_transform": true,
"rule_list": false,
"non_binary": false,
"costs": "",
"model": "",
"timing": "",
"trace": "",
"tree": "",
"profile": ""
}
Flags
balance
- Values: true or false
- Description: Enables overriding the sample importance by equalizing the importance of each present class
cancellation
- Values: true or false
- Description: Enables propagate up the dependency graph of task cancellations
look_ahead
- Values: true or false
- Description: Enables the one-step look-ahead bound implemented via scopes
similar_support
- Values: true or false
- Description: Enables the similar support bound imeplemented via the distance index
feature_exchange
- Values: true or false
- Description: Enables pruning of pairs of features using subset comparison
continuous_feature_exchange
- Values: true or false
- Description: Enables pruning of pairs continuous of feature thresholds using subset comparison
diagnostics
- Values: true or false
- Description: Enables printing of diagnostic trace when an error is encountered to standard output
verbose
- Values: true or false
- Description: Enables printing of configuration, progress, and results to standard output
reference_LB
- Values: true or false
- Description: Enables using a vector of misclassifications from another (reference) model to lower bound our own misclassifications
Tuners
regularization
- Values: Decimal within range [0,1]
- Description: Used to penalize complexity. A complexity penalty is added to the risk in the following way.
ComplexityPenalty = # Leaves x regularization
depth_budget
- Values: Integers >= 1
- Description: Used to set the maximum tree depth for solutions, counting a tree with just the root node as depth 1. 0 means unlimited.
uncertainty_tolerance
-
Values: Decimal within range [0,1]
-
Description: Used to allow early termination of the algorithm. Any models produced as a result are guaranteed to score within the lowerbound and upperbound at the time of termination. However, the algorithm does not guarantee that the optimal model is within the produced model unless the uncertainty value has reached 0.
-
Values: Decimal within range [0,1]
-
Description: Used to limit the risk of model search space. This can be used to ensure that no models are produced if even the optimal model exceeds a desired maximum risk. This also accelerates learning if the upperbound is taken from the risk of a nearly optimal model.
Limits
path_to_labels
- Values: String
- Description: If reference_LB is true, gives file path to the labels from the reference model. Otherwise, not used; if reference lb is true, configure instantiates the Reference class with the appropriate labels.
model_limit
- Values: Decimal greater than or equal to 0
- Description: The maximum number of models that will be extracted into the output.
- Special Cases: When set to 0, no output is produced.
precision_limit
- Values: Decimal greater than or equal to 0
- Description: The maximum number of significant figures considered when converting ordinal features into binary features.
- Special Cases: When set to 0, no limit is imposed.
stack_limit
- Values: Decimal greater than or equal to 0
- Description: The maximum number of bytes considered for use when allocating local buffers for worker threads.
- Special Cases: When set to 0, all local buffers will be allocated from the heap.
tile_limit
- Values: Decimal greater than or equal to 0
- Description: The maximum number of bits used for the finding tile-equivalence
- Special Cases: When set to 0, no tiling is performed.
time_limit
- Values: Decimal greater than or equal to 0
- Description: A time limit upon which the algorithm will terminate. If the time limit is reached, the algorithm will terminate with an error.
- Special Cases: When set to 0, no time limit is imposed.
worker_limit
- Values: Decimal greater than or equal to 1
- Description: The maximum number of threads allocated to executing th algorithm.
- Special Cases: When set to 0, a single thread is created for each core detected on the machine.
Files
costs
- Values: string representing a path to a file.
- Description: This file must contain a CSV representing the cost matrix for calculating loss.
- The first row is a header listing every class that is present in the training data
- Each subsequent row contains the cost incurred of predicitng class i when the true class is j, where i is the row index and j is the column index
- Example where each false negative costs 0.1 and each false positive costs 0.2 (and correct predictions costs 0.0):
negative,positive 0.0,0.1 0.2,0.0
- Example for multi-class objectives:
class-A,class-B,class-C 0.0,0.1,0.3 0.2,0.0,0.1 0.8,0.3,0.0
- Note: costs values are not normalized, so high cost values lower the relative weight of regularization
- Special Case: When set to empty string, a default cost matrix is used which represents unweighted training misclassification.
model
- Values: string representing a path to a file.
- Description: The output models will be written to this file.
- Special Case: When set to empty string, no model will be stored.
profile
- Values: string representing a path to a file.
- Description: Various analytics will be logged to this file.
- Special Case: When set to empty string, no analytics will be stored.
timing
- Values: string representing a path to a file.
- Description: The training time will be appended to this file.
- Special Case: When set to empty string, no training time will be stored.
trace
- Values: string representing a path to a directory.
- Description: snapshots used for trace visualization will be stored in this directory
- Special Case: When set to empty string, no snapshots are stored.
tree
- Values: string representing a path to a directory.
- Description: snapshots used for trace-tree visualization will be stored in this directory
- Special Case: When set to empty string, no snapshots are stored.
Example
Example code to run GOSDT with threshold guessing, lower bound guessing, and depth limit. The example python file is avaialable in python/example.py
import pandas as pd
import numpy as np
import time
import pathlib
from sklearn.ensemble import GradientBoostingClassifier
from model.threshold_guess import compute_thresholds
from model.gosdt import GOSDT
# read the dataset
df = pd.read_csv("experiments/datasets/fico.csv", sep=";")
X, y = df.iloc[:,:-1].values, df.iloc[:,-1].values
h = df.columns[:-1]
# GBDT parameters for threshold and lower bound guesses
n_est = 40
max_depth = 1
# guess thresholds
X = pd.DataFrame(X, columns=h)
print("X:", X.shape)
print("y:",y.shape)
X_train, thresholds, header, threshold_guess_time = compute_thresholds(X, y, n_est, max_depth)
y_train = pd.DataFrame(y)
# guess lower bound
start_time = time.perf_counter()
clf = GradientBoostingClassifier(n_estimators=n_est, max_depth=max_depth, random_state=42)
clf.fit(X_train, y_train.values.flatten())
warm_labels = clf.predict(X_train)
elapsed_time = time.perf_counter() - start_time
lb_time = elapsed_time
# save the labels from lower bound guesses as a tmp file and return the path to it.
labelsdir = pathlib.Path('/tmp/warm_lb_labels')
labelsdir.mkdir(exist_ok=True, parents=True)
labelpath = labelsdir / 'warm_label.tmp'
labelpath = str(labelpath)
pd.DataFrame(warm_labels).to_csv(labelpath, header="class_labels",index=None) # TODO: verify this formats correctly for gosdt (shouldn't require headers)
# train GOSDT model
config = {
"regularization": 0.001,
"similar_support": False,
"strong_indifference": False,
"time_limit": 1800,
"depth_budget": 5,
"warm_LB": True,
"path_to_labels": labelpath
}
model = GOSDT(config)
model.fit(X_train, y_train)
print("evaluate the model, extracting tree and scores", flush=True)
# get the results
train_acc = model.score(X_train, y_train)
n_leaves = model.leaves()
n_nodes = model.nodes()
time = model.utime
print("Model training time: {}".format(time))
print("Training accuracy: {}".format(train_acc))
print("# of leaves: {}".format(n_leaves))
print(model.tree)
Output
X: (10459, 23)
y: (10459,)
gosdt reported successful execution
training completed. 1.658/0.098/1.756 (user, system, wall), mem=364 MB
bounds: [0.290914..0.290914] (0.000000) loss=0.282914, iterations=13569
evaluate the model, extracting tree and scores
Model training time: 1.6584229469299316
Training accuracy: 0.7170857634573095
# of leaves: 8
if ExternalRiskEstimate<=67.5 = 1 and MSinceMostRecentInqexcl7days<=-7.5 = 1 then:
predicted class: 1
misclassification penalty: 0.027
complexity penalty: 0.001
else if ExternalRiskEstimate<=67.5 != 1 and MSinceMostRecentInqexcl7days<=-7.5 = 1 then:
predicted class: 0
misclassification penalty: 0.006
complexity penalty: 0.001
else if ExternalRiskEstimate<=74.5 = 1 and MSinceMostRecentInqexcl7days<=-7.5 != 1 and MSinceMostRecentInqexcl7days<=0.5 = 1 and PercentTradesWBalance<=80.5 = 1 then:
predicted class: 1
misclassification penalty: 0.071
complexity penalty: 0.001
else if ExternalRiskEstimate<=74.5 != 1 and MSinceMostRecentInqexcl7days<=-7.5 != 1 and MSinceMostRecentInqexcl7days<=0.5 = 1 and PercentTradesWBalance<=80.5 = 1 then:
predicted class: 0
misclassification penalty: 0.061
complexity penalty: 0.001
else if ExternalRiskEstimate<=78.5 = 1 and MSinceMostRecentInqexcl7days<=-7.5 != 1 and MSinceMostRecentInqexcl7days<=0.5 = 1 and PercentTradesWBalance<=80.5 != 1 then:
predicted class: 1
misclassification penalty: 0.033
complexity penalty: 0.001
else if ExternalRiskEstimate<=78.5 != 1 and MSinceMostRecentInqexcl7days<=-7.5 != 1 and MSinceMostRecentInqexcl7days<=0.5 = 1 and PercentTradesWBalance<=80.5 != 1 then:
predicted class: 0
misclassification penalty: 0.005
complexity penalty: 0.001
else if ExternalRiskEstimate<=67.5 = 1 and MSinceMostRecentInqexcl7days<=-7.5 != 1 and MSinceMostRecentInqexcl7days<=0.5 != 1 then:
predicted class: 1
misclassification penalty: 0.026
complexity penalty: 0.001
else if ExternalRiskEstimate<=67.5 != 1 and MSinceMostRecentInqexcl7days<=-7.5 != 1 and MSinceMostRecentInqexcl7days<=0.5 != 1 then:
predicted class: 0
misclassification penalty: 0.054
complexity penalty: 0.001
Repository_Structure
Guide for developers who want to use, modify and test the library.
Describes how to install and use the library with details on project structure.
- experiments - configurations, datasets, and models to run experiments
- doc - documentation
- python - code relating to the Python implementation and wrappers around C++ implementation
- auto - automations for checking and installing project dependencies
- dist - compiled binaries for distribution
- build - compiled binary objects and other build artifacts
- lib - headers for external libraries
- log - log files
- src - source files
- test - test files
FAQs
If you run into any issues when running GOSDT, consult the FAQs first.
License
This software is licensed under a 3-clause BSD license (see the LICENSE file for details).
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for gosdt-0.1.3-cp36-abi3-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8847e56d9f5e87fb7984f3f13484c6a5eb609d16cd4d5277957a4e024c8cc18d |
|
MD5 | f187832eb416268e488b6f4bb27c92d2 |
|
BLAKE2b-256 | 73779d10d724afed5373b7cc6364435ecbf9f6ebe914929aeddddee983741779 |
Hashes for gosdt-0.1.3-cp33-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 92c44b6a00e5fb0468475b4116d1314bad557c017aa312964c68fe1cbeb6bb6a |
|
MD5 | 4dbf8b777703db6a9e10c8d786489192 |
|
BLAKE2b-256 | 70b0905ba632a424517e3ea31f5774ff7a10a9b587063397214f32722c70555f |
Hashes for gosdt-0.1.3-cp33-abi3-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a3a8e89f30201bada4ee759ad7bae14ffc160f8a7020f7a775fb9af201c6856f |
|
MD5 | b1366192dd876b27228738ebc8a1ea6c |
|
BLAKE2b-256 | 06cdb320ec23f351040b152df89891b67f0441cdfd19c1c240bab7241174c28c |