[](https://github.com/rmitsuboshi/miniboosts/actions/workflows/build.yaml) [Documentation][miniboosts] *MiniBoosts* is a library for boosting algorithm researchers. ## What is **Boosting**? Boosting is a repeated game between a *Booster* and a *Weak Learner*. For each round of the game, 1. The *Booster* chooses a distribution over training examples, 2. Then the *Weak Learner* chooses a hypothesis (function) whose accuracy w.r.t. the distribution is slightly better than random guessing. After sufficient rounds, the *Booster* outputs a hypothesis that performs significantly better on training examples. ## How to use this library Write the following in your `cargo.toml.` ```toml [dependencies] minibosts = { version = "0.3.5" } ``` All boosting algorithms are implemented without [Gurobi][gurobi]. but, if you have a [Gurobi][gurobi] license, you can use the Gurobi version of the algorithms by setting: ```toml [dependencies] minibosts = { version = "0.3.5", features = ["gurobi"] } ``` > [!CAUTION] > Since I am no longer a student, I cannot check whether the compilation succeeded with the `"gurobi"` flag. Currently, following boosting algorithms are available: |`BOOSTER` | `FEATURE FLAG` | | :--- | :--- | | [AdaBoost][adaboost]
by Freund and Schapire, 1997 | | | [MadaBoost][madaboost]
by Domingo and Watanabe, 2000 | | | [GBM][gbm] (Gradient Boosting Machine)
by Jerome H. Friedman, 2001 | | | [LPBoost][lpboost]
by Demiriz, Bennett, and Shawe-Taylor, 2002 | `gurobi` | | [SmoothBoost][smoothboost]
by Servedio, 2003 | | | [AdaBoostV][adaboostv]
by Rätsch and Warmuth, 2005 | | | [TotalBoost][totalboost]
by Warmuth, Liao, and Rätsch, 2006 | `gurobi` | | [SoftBoost][softboost]
by Warmuth, Glocer, and Rätsch, 2007 | `gurobi` | | [ERLPBoost][erlpboost]
by Warmuth and Glocer, and Vishwanathan, 2008 | `gurobi` | | [CERLPBoost][cerlpboost] (Corrective ERLPBoost)
by Shalev-Shwartz and Singer, 2010 | `gurobi` | | [MLPBoost][mlpboost]
by Mitsuboshi, Hatano, and Takimoto, 2022 | `gurobi` | | [GraphSepBoost][graphsepboost] (Graph Separation Boosting)
by Alon, Gonen, Hazan, and Moran, 2023 | | If you invent a new boosting algorithm, you can introduce it by implementing `Booster` trait. See `cargo doc -F gurobi --open` for details. |`WEAK LEARNER` | | :--- | | [Decision Tree][decisiontree] | | [Regression Tree][regressiontree] | | [A worst-case weak learner for LPBoost][badbaselearner] | | Gaussian Naive Bayes | | Neural Network (Experimental) | ## Why *MiniBoosts*? If you write a paper about boosting algorithms, you need to compare your algorithm against others. At this point, some issues arise. - Some boosting algorithms, such as [*LightGBM*][lightgbm] or [*XGBoost*][xgboost], are implemented and available for free. These are very easy to use in Python3 but hard to compare to other algorithms since they are implemented in C++ internally. Implementing your algorithm in Python3 makes the running time comparison unfair (Python3 is significantly slow compared to C++). However, implementing it in C++ is extremely hard (based on my experience). - Most boosting algorithms are designed for a decision-tree weak learner even though the boosting protocol does not demand. - There is no implementation for margin optimization boosting algorithms. Margin optimization is a better goal than empirical risk minimization in binary classification. *MiniBoosts* is a crate to address the above issues. This crate provides the followings. - Two main traits, named `Booster` and `WeakLearner.` - If you invent a new Boosting algorithm, all you need is to implement `Booster.` - If you invent a new Weak Learning algorithm, all you need is to implement `WeakLearner.` - Some famous boosting algorithms, including [*AdaBoost*][adaboost], [*LPBoost*][lpboost], [*ERLPBoost*][erlpboost], etc. - Some weak learners, including Decision-Tree, Regression-Tree, etc. ## *MiniBoosts* for reasearch Sometimes, one wants to log each step of boosting procedure. You can use `Logger` struct to output log to `.csv` file, while printing the status like this:  See [Research feature](#research-feature) section for detail. ## Examples [Documentation][miniboosts] Write the following to `Cargo.toml`. ```TOML miniboosts = { version = "0.3.5" } ``` If you want to use `gurobi` features, enable the flag: ```TOML miniboosts = { version = "0.3.5", features = ["gurobi"] } ``` Here is a sample code: ```rust use miniboosts::prelude::*; fn main() { // Set file name let file = "/path/to/input/data.csv"; // Read the CSV file // The column named `class` corresponds to the labels (targets). let sample = SampleReader::new() .file(file) .has_header(true) .target_feature("class") .read() .unwrap(); // Set tolerance parameter as `0.01`. let tol: f64 = 0.01; // Initialize Booster let mut booster = AdaBoost::init(&sample) .tolerance(tol); // Set the tolerance parameter. // Construct `DecisionTree` Weak Learner from `DecisionTreeBuilder`. let weak_learner = DecisionTreeBuilder::new(&sample) .max_depth(3) // Specify the max depth (default is 2) .criterion(Criterion::Twoing) // Choose the split rule. .build(); // Build `DecisionTree`. // Run the boosting algorithm // Each booster returns a combined hypothesis. let f = booster.run(&weak_learner); // Get the batch prediction for all examples in `data`. let predictions = f.predict_all(&sample); // You can predict the `i`th instance. let i = 0_usize; let prediction = f.predict(&sample, i); // You can convert the hypothesis `f` to `String`. let s = serde_json::to_string(&f); } ``` If you use boosting for soft margin optimization, initialize booster like this: ```rust let n_sample = sample.shape().0; // Get the number of training examples let nu = n_sample as f64 * 0.2; // Set the upper-bound of the number of outliers. let lpboost = LPBoost::init(&sample) .tolerance(tol) .nu(nu); // Set a capping parameter. ``` Note that the capping parameter must satisfies `1 <= nu && nu <= n_sample`. ## Research feature This crate can output a CSV file for such values in each step. Here is an example: ```rust use miniboosts::prelude::*; use miniboosts::{ Logger, LoggerBuilder, SoftMarginObjective, }; // Define a loss function fn zero_one_loss(sample: &Sample, f: &H) -> f64 where H: Classifier { let n_sample = sample.shape().0 as f64; let target = sample.target(); f.predict_all(sample) .into_iter() .zip(target.into_iter()) .map(|(fx, &y)| if fx != y as i64 { 1.0 } else { 0.0 }) .sum::() / n_sample } fn main() { // Read the training data let path = "/path/to/train/data.csv"; let train = SampleReader::new() .file(path) .has_header(true) .target_feature("class") .read() .unwrap(); // Set some parameters used later. let n_sample = train.shape().0 as f64; let nu = 0.01 * n_sample; // Read the test data let path = "/path/to/test/data.csv"; let test = SampleReader::new() .file(path) .has_header(true) .target_feature("class") .read() .unwrap(); let booster = LPBoost::init(&train) .tolerance(0.01) .nu(nu); let weak_learner = DecisionTreeBuilder::new(&train) .max_depth(2) .criterion(Criterion::Entropy) .build(); // Set the objective function. // One can use your own function by implementing ObjectiveFunction trait. let objective = SoftMarginObjective::new(nu); let mut logger = LoggerBuilder::new() .booster(booster) .weak_learner(tree) .train_sample(&train) .test_sample(&test) .objective_function(objective) .loss_function(zero_one_loss) .time_limit_as_secs(120) // Terminate after 120 seconds .print_every(10) // Print log every 10 rounds. .build(); // Each line of `lpboost.csv` contains the following four information: // Objective value, Train loss, Test loss, Time per iteration // The returned value `f` is the combined hypothesis. let f = logger.run("logfile.csv") .expect("Failed to logging"); } ``` ## Others - Currently, this crate mainly supports boosting algorithms for binary classification. - Some boosting algorithms use [Gurobi optimizer][gurobi], so you must acquire a license to use this library. If you have the license, you can use these boosting algorithms (boosters) by specifying `features = ["gurobi"]` in `Cargo.toml`. The compilation fails if you try to use the gurobi feature without a Gurobi license. - One can log your algorithm by implementing `Research` trait. - Run `cargo doc -F gurobi --open` to see more information. - `GraphSepBoost` only supports the aggregation rule shown in Lemma 4.2 of their paper. ## Future work - Boosters - [AnyBoost][anyboost] - [SparsiBoost][sparsiboost] - [LogitBoost][logitboost] - [AdaBoost.L][adaboostl] - [Branching Program][branching] - Weak Learners - Bag of words - TF-IDF - [RBF-Net](https://link.springer.com/content/pdf/10.1023/A:1007618119488.pdf) [adaboost]: https://www.sciencedirect.com/science/article/pii/S002200009791504X?via%3Dihub [adaboostl]: https://link.springer.com/article/10.1023/A:1013912006537 [adaboostv]: http://jmlr.org/papers/v6/ratsch05a.html [anyboost]: https://www.researchgate.net/publication/243689632_Functional_gradient_techniques_for_combining_hypotheses [badbaselearner]: https://papers.nips.cc/paper_files/paper/2007/hash/cfbce4c1d7c425baf21d6b6f2babe6be-Abstract.html [branching]: https://www.sciencedirect.com/science/article/pii/S0022000001917969 [cerlpboost]: https://link.springer.com/article/10.1007/s10994-010-5173-z [decisiontree]: https://www.amazon.co.jp/-/en/Leo-Breiman/dp/0412048418 [erlpboost]: https://www.stat.purdue.edu/~vishy/papers/WarGloVis08.pdf [gbm]: https://projecteuclid.org/journals/annals-of-statistics/volume-29/issue-5/Greedy-function-approximation-A-gradient-boostingmachine/10.1214/aos/1013203451.full [graphsepboost]: https://theoretics.episciences.org/10757 [gurobi]: https://www.gurobi.com [lightgbm]: https://github.com/microsoft/LightGBM [logitboost]: https://projecteuclid.org/journals/annals-of-statistics/volume-28/issue-2/Additive-logistic-regression--a-statistical-view-of-boosting-With/10.1214/aos/1016218223.full [lpboost]: https://link.springer.com/content/pdf/10.1023/A:1012470815092.pdf [mlpboost]: https://arxiv.org/abs/2209.10831 [madaboost]: https://www.learningtheory.org/colt2000/papers/DomingoWatanabe.pdf [regressiontree]: https://www.amazon.co.jp/-/en/Leo-Breiman/dp/0412048418 [smoothboost]: https://link.springer.com/chapter/10.1007/3-540-44581-1_31 [softboost]: https://proceedings.neurips.cc/paper/2007/file/cfbce4c1d7c425baf21d6b6f2babe6be-Paper.pdf [sparsiboost]: http://proceedings.mlr.press/v97/mathiasen19a/mathiasen19a.pdf [totalboost]: https://dl.acm.org/doi/10.1145/1143844.1143970 [xgboost]: https://github.com/dmlc/xgboost [miniboosts]: https://docs.rs/miniboosts/latest/miniboosts/