Download bonzaiboost:

1. bonzaiboost v1.6.9 binary for linux 64, for windows

1. added flag "{-}{-}info" to output information about models
2. fixed bug in error estimation for multilabels tasks
3. added "-prune" to prune tree wrt. to data in .dev for tree mode or with out of bag in bagging mode
4. corrected the "exclude_level" option with sgram mode
5. fixed some bugs (and probably add some new ones)
6. code refactoring

2. bonzaiboost v1.6.4 binary for linux 64, for linux 32, for Mac OSX.

1. fixed bug introduced in v1.6.2 using text features (no problem for AdaBoost.MH)
2. added bagging generalisation error estimation (beta)
3. flag "-draw" works in cross validation
4. fixed other minor bugs

3. bonzaiboost v1.6.3 binary

1. fixed bug when the output in test mode printed text-index instead of text himself
2. fixed a rare bug when loading model in boosting mode
3. add -fp option to format the prediction output
4. fixed the "icsi" output

4. bonzaiboost v1.6.2 binary

1. fixed a big bug in text feature extraction present in v1.6
2. added "exclude_level" option for text attribute to ignore one or several levels of information
3. added attribute based cross validation to control manually the folds
4. all gain (entropy,gini,etc.) are now expressed in percentage (so are stopping criteria with -g flag)

5. bonzaiboost v1.6 binary

1. speed and memory optimizations
2. implementation of bagging (randomForest)
3. simple k-nearest neighbor implementation
4. add option "-m" to bypass the .XXX output filenames
5. models are saved in xml format
6. add option "-format" to keep compatibility with old models
7. add option "{-}{-}discretize" to discretize numeric attributes according to MDLPC
8. reorganized the help message

6. bonzaiboost v1.4 binary for linux 64, for linux 32, for Mac OSX.

1. part of code has been rewritten with template to facilitate maintenance
2. N-Fold cross validation implemented (and parallelized)
3. cutoff is available for numeric features
4. simple features selection methods are implemented based on entropy,idf and mutual information

7. bonzaiboost v1.2 binary for linux 64, for linux 32.

1. all parallel mechanisms has been rewritten with OpenMP
2. some code has been modified to reduce significantly memory consumption
3. save boosting weights at end of boosting procedure (AdaBoost.MH only) for fast resuming
4. some file format conversion process are introduced (arff(weka) and libsvm like)
5. some bugs are fixed
1. option "-leaf" in test mode works
2. when a weight is assigned to an example in data file: now works for trees and AdaBoost.MH
3. false feature selection for no pertinent attributes

8. bonzaiboost v1.1 binary for linux 64.

1. some bugs fixed

9. bonzaiboost v1.0 binary for linux 64.

Contents

1 What is bonzaiboost ?

bonzaiboost is a general purpose machine-learning program based on decision tree for building a classifier from text and/or attribute-value data.
Currently one configuration of bonzaiboost is ranked first on http://mlcomp.org bonzaiboost can handle:

• Multiple attributes:
  1. Textual
  2. Symbolic
  3. Numeric
• Implements meta learning of decision trees
  1. Boosting: AdaBoost.MH [Schapire and Singer, 2000]
  2. Bagging: RandomForest [Breiman, 2001]
• multilabel/multiclass problems
• Fairly large datasets (up to around 1,000,000 examples or more, depending on the computer and the form of the data).
• Input data format compatible with other softwares: icsiboost,boostexter
• Produce detailed evaluation statistics (confusion matrix…)
• At least 100 times faster than weka on textual data (depending on the number of dimension)
• Implement multi-threads to speed up learning time

Note that most of existing implementations of boosting¹ use it on top of “decision stumps”, bonzaiboost can learn general decision trees and can apply boosting on top of them.

• As a decision tree learner bonzaiboost implement:
  • several tree inductions
    • entropy (CART)
    • gini (C4.5)
    • error
    • mean square error (M5) [Quinlan, 1992]
  • several stop criteria:
    • You can set the minimum number of samples in a leaf (default:1)
    • You can set the maximum tree depth (default:unlimited)
    • You can set the minimum gain for the split criterion (default:˜0)
    • You can set the minimum predictive power of a leaf (default:1)
    • MDLPC (automatic) ([Fayyad and Irani, 1993])
• As meta learner:
  1. Boosting over decision trees:
     • Implement the Boosting algorithm AdaBoost.MH (AdaBoost, AdaBoost.M1 is implemented too)
     • but Boosting algorithms are based on YOUR weak tree not only decision stumps
  2. Bagging over decision trees:
     • Choose random feature reduction among:(no,sqrt,log,fixed number)
     • simple bagging or randomForest

2 Command line and option

Usage: bonzaiboost -S stem [options]:

3 Using bonzaiboost

Here are instructions how to use the program “bonzaiboost” to build a classifier for text and/or attribute-value classification and how to classify new instances.

bonzaiboost works with data which may be of various forms. In general, each instance is broken into multiple fields. These fields may be of four types: a continuous-valued attribute (such as “age”), a discrete-valued attribute (such as “eye color”), a text string (such as “body of an email message”), or a “scored text”string (in which scores are associated with each word of the text, such as “tf-idf”scores used in information retrieval).

bonzaiboost learns decision tree and can combine them with boosting or bagging. To each node of the tree a binary feature is attached. Features are tests built from the training data and have one of the following forms depending on the type of input field associated with it:

• For discrete attributes, the test asks if the attribute has a particular value.
• For continuous attributes, the test asks if the attribute value is above or below some threshold.
• For textual input fields, the test asks whether or not a particular sequence of words is present in the given text. The form of this sequence may be a simple sequence or “ngram”if in ngram or fgram mode, or a “sparse ngram”if in sgram mode. (An example of a sparse ngram is the pattern “the * boy”which matches any three word sequence beginning with the word “the”and ending with the word “boy”.) The style of ngram that is used is determined using the “-expert_type”option, and the length is determined by the “-expert_length”option.
• For scored text, the test asks whether the score associated with a particular word is above or below some threshold.

4 Input/Output files and their formats

bonzaiboost receives several files as input and produce output files. In training mode the program gets a names files, a data file used for training. The stem of all the files is the same and given via the run-time parameter -S. For example, if bonzaiboost is called with “-S sample”, then the following files will be used or created:

1. used
   1. sample.names : names (description) file
   2. sample.data : input training file
2. created depending on the algorithm invoked
   1. sample.X.xml : model dump with X among {bagging,boost,tree} depending on the invoked algorithm
   2. sample.X.eval.html :html report of classification error statistics (in test mode when “-C”is invoked)

In classification mode (-C parameter turned on) the description file (<stem>.names) and model file (<stem>.X.xml are read depending of the selected algorithm, and the test data is read from the standard input (stdin). A detailed statistic by label of the error rate is printed to the standard error, and the per-example prediction is printed to the standard output.

4.1 “names” file (stem.names)

The names file defines the format of the data to be read in. White space is ignored throughout this file. The first line of the names file specifies the possible class labels of the data instances. It has the form:

• <label_1>, <label_2>, ... , <label_k>.

where each <label_i> is any string of letters or numbers. Certain punctuation marks, including comma and period, may be problematic. Case is significant. (Likewise for all other string names below.)
The remaining lines specify the form and type of the input fields. For continuous-valued input fields, the form is:

• <name>: continuous.

where <name> is any string naming the field.
For discrete-valued input fields, the form is:

• <name>: <value_1>, <value_2>, ... , <value_k>.
  or simply:
• <name>: discrete.

where <name> is any string naming the field, and <value_1> , ... , <value_k> are strings representing the possible values which can be assumed by this attribute. For text input fields, the form is:

• <name>: text.

where <name> is any string naming the field.
For scored-text intput fields, the form is:

• <name>: scoredtext.

where <name> is any string naming the field.

A detailed example is given below.

4.2 Data and test file (stem.data and stem.test)

These files each describe a sequence of labeled examples. Each example has the following form:
<field_1>, <field_2>, ... , <field_n>, <label_1> <label_2> ... <label_x>.
Here, <field_i> specifies the value of the i-th field, where the ordering of the fields is as specified in the names file. If this field is continuous, then a real number should appear. If this field is discrete, then the value must be one of the values (strings) specified in the names file. If the field is a text string, then any string of words may appear. If the field is a scored text string, then a real number must follow each word in the string.
Each <label_i> is one of the labels specified in the first line of the names file. These labels are the “correct”or desired labels associated with this example.

4.3 Detailed Example

Here is a toy example in which the goal is to predict if a person is rich, smart or happy. Instances describe individual people.
Here is an example “names”file (table 1, with the three classes, and a description of the fields. It is included in this distribution as the file “sample.names”, as are the other files mentioned below.

The scores appearing in the “hobbies”field would encode number of hours per week on each of a list of hobbies. The interpretation of the other fields should be obvious.
Here is an example “data”(training) file, called “sample.data”, table 2.

4.4 Particular options

for each field you may want to ask for specific option. These options must be set in the name file at the end of the field description. These options are the following:

1. Features selection:
   1. cutoff=x feature not present at least x times in the training data are not considered (default=0), for numeric fields the behavior is different: the numeric value is rounded to x digit after comma.
   2. cutentropy=x feature with entropy-gain under x is eliminated (in general set > 0)
   3. cutidf=x feature with idf over x is eliminated (in general set in [0 - 1])
   4. cutim=x feature with mutual information over x is eliminated (in general set < 0.001)
2. for text fields only:
   1. expert_type=x: type of the generated feature for learning:x=
      • sgram - all sparse word-grams up to a maximal length
      • ngram - all full word-grams up to a maximal length
      • fgram - full word-grams of maximal length only
   2. expert_length=x: x is length of the gram(default=1)
   3. expert_length_min=x: x is minimum length of the gram(default=1)
   4. expert_level=x: number of level in text field(default 1) see next:
   5. exclude_level=x: don’t consider the level x (repeat this command to exclude several level):

4.4.1 Specific ngram extraction on multiple levels text input

When working with text field you may want to give several word level information in addition to the word itself. To do so, you have to alternate word with other levels and inform the name file that the field must be read according to that. For example, word ngram pattern may not be enough general while POS pattern too less specific. You can give the two levels and all possible combinations will be evaluated by the algorithm whose select the best:
“have a big family”would be enriched by POS information “have VERB a DET big ADJ family CN”.

5 Use cases

5.1 Tree mode

5.1.1 Training

Using the example “sample”, run:

• bonzaiboost -S sample

You will see in the figure 1 the screen copy for the run result. Each node construction of the tree print informations (you can adjust verbose level with the parameter “-v”up to 5):

1. the first line give two informations: how many examples of the database are used in this current node and the depth
2. second line indicates for each field in the .names file the number of features extracted.
3. other lines print informations about individual features: gain (according to selected measure, entropy or gini), error made by the split according to this feature, and the feature name
   1. - - -: indicate current evaluated feature (only with verbose level > 4)
   2. - x -: indicate current selected feature (only with verbose level > 3)
   3. x - x: indicate best field selected feature (only with verbose level > 2)
   4. x x x: indicate best selected feature among all fields.

Several option could be fixed to control the tree construction and when to stop it:

• -cr entropy/gini/m5(beta): method used to build the tree, default:entropy
• -g minimalgain: where minimalgain is the bound from which the gain must be below to select a feature,default:0
• -leaf nbexamples: minimum number of examples in a leaf,default:1
• -p proba:: stop if prediction in a leaf >= proba,default:1
• -d depth: maximum depth of the tree,default:unlimited in tree and bagging algorithms,default:1 in boosting mode
• -mdlpc: automatic stop criterion based on the minimum description length principle

5.1.2 Testing

Using the example “sample”. Run:

• bonzaiboost -S sample -C < sample.data > tmpfile

In tmpfile you will find sample.data with the prediction made by the tree at each end of line, see figure 2. On stderr are printed detailed errors statistics about all labels like in figure 3.

When the classification mode is invoked, 2 files are build:

1. stem.tree.eval.html. This file contain evaluation statistics, see figure 4:
   1. A summary of the option used for the evaluation
   2. The per label error statistics
   3. A label confusion matrix indicating thanks to level of red the main confusions made by the classifier
2. stem.tree.dot: information to produce a graphical representation of the tree thanks to the library Graphviz http://www.graphviz.org/. You can see an example in figure 5 generated with the command line “cat sample.dot | dot -Tpng > sample.png”.

As you saw, this example is a multi-class classification problem where we want to assign several labels to an instance. Even if decision tree is not really designed to solve this kind of problem you may want to assign all labels which have a high probability (at least 0.5), you can simply change the bonzaiboost behavior in multiclass by setting the flag -c to multi and put a threshold on the probability by setting the flag -o to 0.5:

• bonzaiboost -S sample -C -o 0.5 -c multi < sample.data

Now the new output is presented in the figure 6.

Figure 6: stdout and stderr output of “bonzaiboost -S sample -C -o 0.5 -c multi < sample.data”

The same options could be fixed in classification mode than in training mode (together with the parameter “-C”), if the tree has been learned with less constrained options, the constrained are fixed for testing. This is also interesting to control the dot file produced to visualize the tree. The tree could be very big, if you want to see only the first nodes, you can invoke the command:

• bonzaiboost -S sample -C -d 2 < sample.data

Then a new sample.tree.dot file will be produced but all nodes deeper than 2 will be removed. (same effect with the other parameters).

5.2 Boosting mode

5.2.1 Training

Typical command should be invoked for training:

• bonzaiboost -S stem -boost algo [-n nbrounds -d depth -resume]
  • algo: must be in the list: ada,adam1,adamh, for AdaBoost, AdaBoost.M1 and AdaBoost.MH algorithm, note that AdaBoost works for 2 classes problems only
  • -n: parameter correspond to the number or rounds, default:2
  • -d: parameter correspond to the depth of the weak tree learner, default:1
  • -resume: to continue learning (start from the last iteration)

Typical command:

• bonzaiboost -S sample -boost adamh -n 2

Figure 7 show the stderr output.

Figure 7: stdout output of “bonzaiboost -S sample -boost adamh -n 2”

5.2.2 Testing

Testing is similar to tree algorithm, just use “-C”parameter, you can also adjust the “-n”parameters to control the number of rounds you want to use for testing.
Typical command:

• bonzaiboost -S sample -boost adamh -C < sample.data

Figure 8 show the stderr output.

5.2.3 Feedback from the model

With the following command:

• bonzaiboost -S sample -boost adamh --info

bonzaiboost will generate the file sample.boost.log.html which summarize what it has learnt

Figure 9: tables that summarize what bonzaiboost has learnt: the first table shows the selection frequency for each attribute during the boosting phase, the second table shows for each line the rule learned and the vote it does for each target class (small vote between 0.5 and -0.5 have been omitted)

5.3 Bagging mode

5.3.1 Training

Typical command should be invoked for training:

• bonzaiboost -S stem -bagging [-n nbtrees -rr featureselection -resume]
  • -n: parameter correspond to the number or trees
  • -rr: random feature reduction in each tree node (no=simple bagging(default), for random forest:sqrt,log,fixed number)
  • -bs: bag size in pourcentage: default=62%
  • -resume: to continue learning (add trees to the forest)

Typical command:

• bonzaiboost -S sample -bagging -n 100 -rr sqrt

5.3.2 Testing

Testing is similar to tree algorithm, just use “-C”parameter, you can also adjust the “-n”parameters to control the number of trees you want to use for testing.
Typical command:

• bonzaiboost -S sample -bagging -C < sample.data

5.4 Knn mode

Knn is a model-less algorithm, so you have to invoke it using the “-C”flag with test data directly:

• bonzaiboost -S stem -knn nbneighbors [-pond ponderation -dist distance] -C < sample.test
  • nbneighbors: set the number of neighbors for voting
  • -pond: kind of ponderation for textual attributes: tfidf,okapi
  • -dist: distance among scalar,euclidienne,cosinus

5.5 Output flags

In classification mode you can also use the “-o”parameter to control the kind of decision output you want, printing AND error computation is done according to this parameter:

• -o normal:is the default
  • in tree or bagging algorithm: print only the label with the highest probability
  • in boost algorithm: print all the predicted labels (whose score >0)
• -o all: equivalent to default mode but the score is reported for each label
• -o <reel>:
  • in tree or bagging algorithm: print all labels with probability >= reel
  • in boost algorithm: predict label whose score is >= reel;
• -o backoff: always take a decision
  • in tree or bagging algorithm: no effect, default behavior
  • in boost algorithm: always take a decision, if no label has been predicted (score>0) choose the best one

This summarize what is happens in default classification output mode for each algorithm: decision tree output at most one label while the boosting algorithm is multiclass and may output more than one label. You can modify this default behavior and make the boosting algorithm mono-class or the decision tree multi-class by setting the flag “-c”to “single”ot “multi”in classification mode “-C”. Table 3 summarizes the behavior of bonzaiboost according to parameters -o,-c and mode (boost or tree).

5.6 Cross-validation experiments

You can run cross-validation experiments adding the flag “-cross”followed by the number of samples wanted for the test at each fold:

• example: bonzaiboost -S stem -boost adamh -n 50 -c single -cross 500 > result.txt
  • will run 50 turns of boosting
  • -c single will only predict the best label for each sample
  • the number of fold will be the number of samples in stem.data/500
  • result.txt will contain all samples with their prediction

You may want to choose your own fold, by using an attribute encoding the fold, then run:

• example: bonzaiboost -S stem -mdlpc -cross attribute=myfold > result.txt
  • will run tree algorithm with mdlpc automatic stop criterion
  • the split will be done according to the attribute “myfold”in the .names
  • the attribute “myfold”will be ignored for the classification process.
  • there will be as many fold as different possible value in the attribute myfold

6 F.A.Q

6.1 What should I use bonzaiboost instead of boostexter/icsiboost

Using shallow trees as weak learner for boosting works quite better than decision stumps. Compare these 2 configurations:

• bonzaiboost -S sample -boost adamh → equivalent to icsiboost/boostexter

• bonzaiboost -S sample -boost adamh -d 2→ now you use depth 2 (4 leaves) decision trees as weak learner, this slight change implies often large improvement on many datasets [Laurent et al., 2014]

6.2 What can I do to increase speed when processing huge amount of data ?

bonzaiboost code has been parallelized, threads can be invoked using the “-jobs” switch. Different settings can be adjusted to match your specific conditions.

1. Extracting features: before running any algorithms, bonzaiboost extract features from data. When extracting Ngrams features with N big this first operation could be slow.
   recommended setting:
   1. if you have few attributes: option -split
      Take a look at the following command: bonzaiboost -S stem -jobs 2 -split 50000
      2 threads will be invoked and data will be splitted in packet of 50000 examples. Settings are then pertinent if you have 100000 inputs examples in your data file.
   2. if you have a lot of attributes: option -pa
      Attributes will be processed in parallel by as many threads as specified by the -jobs option
2. Tree algorithm: tree induction is parallelized use "-jobs" to control the max number of threads
3. Bagging algorithm: trees induction are not parallelized any more, but each tree is inducted in parallel: "-jobs" control the max number of simultaneous trees
4. Boosting algorithm: trees induction are not parallelized any more, since boosting is an iterative algorithm rounds can’t be parallelized however if each round is slow because a high number of features or/and attributes you can process as follow:
   1. High attributes number: when running any algorithms, bonzaiboost look for the best feature at each tree node or/and boosting round. Selection is done examining every attributes. In presence of high number of attributes or several attributes from which a lot of features have been extracted, you can ask for a parallel processing of attributes invoking the flags “-pa”.
   2. High text features: sometimes an huge amount of textual features (several millions) is extracted from textual attributes when Ngram size is high, finding the best feature among them could be slow. You can parallelize this processing setting the flag “-pt”.
      Take a look at the following command: bonzaiboost -S stem -jobs 2 -pt 10000000
      to find the best feature among features from a textual attributes, 2 threads will be invoked each times a textual attribute count more than 10000000 features
   3. High text features: another solution is the following: instead of extracting N-gram with N big from one attribute only, duplicate N times this attribute and extract fgram of 1 to N in each attribute with the -pa option. This solution is probably faster than the previous one because features extraction is parallelized too.
5. Cross validation: only folds are processed in parallel: use "-jobs" to control the max number of simultaneous folds

6.3 I have my data in a file format different from bonzaiboost format

Simple format conversion processes have been implemented. You can convert 2 well used formats:

1. arff format (used by weka)
   • assert that the attribute to predict is named "class" (and only it)
2. libsvm sparse like format

If you have a training data and testing data files you can convert them by the following command lines:

• arff: bonzaiboost -S sample -convert arff2data+ < data.file #will convert data.file in sample.data and sample.names will be created
  bonzaiboost -S sample -convert arff2data < test.file > sample.test #will convert test.file into sample.test
• libsvm: idem as previous command lines except option is ssvm2data
• libsvm: there is a "smart" conversion for textual data: if the file encode ngrams as numeric features (1 if the features is present and 0 otherwise), this "smart" conversion recover this feature as an unique text attribute instead of several numeric ones speeding up the future processing: command option is ssvm2data-auto.

Inverse conversions are possible: ask bonzaiboost -S sample -convert ? to know all possible conversions

6.4 How can I do a clean Interruption ?

1. You can stop properly the bonzaiboost execution (in mode, tree, boosting and bagging) by doing one Control-C, you will have to wait the end of the actual running node (in tree node), running weak learner (boosting mode) or running trees (bagging mode) and a model will be saved.
2. A second Control-C will stop immediately but nothing is saved.
3. If you want to continue the execution, execute the same command line as before and add the flag -resume.

This is useful if you want to change some parameters:

• Your machine is process free: increment the numbers of threads for bonzaiboost with the -jobs flag
• Increment the number of learners in meta-learning algorithms with -n flag
• etc.

7 Citing bonzaiboost

If you use bonzaiboost for a scientific work, please refer to:

• Antoine Laurent, Nathalie Camelin and Christian Raymond.
  Boosting bonsai trees for efficient features combination : application to speaker role identification
  InterSpeech, Singapor, 2014

8 Publications where bonzaiboost is applied

bonzaiboost itself:

• Antoine Laurent, Nathalie Camelin and Christian Raymond.
  Boosting bonsai trees for efficient features combination : application to speaker role identification
  InterSpeech, Singapor, 2014
• Yann Ricquebourg, Christian Raymond, Baptiste Poirriez, Aurélie Lemaitre and Bertrand Coüasnon
  Boosting bonsai trees for handwritten/printed text discrimination
  Document Recognition and Retrieval (DRR), 2014

Publications where bonzaiboost is applied

• Frédéric Béchet, Meriem Bendris, Delphine Charlet, Géraldine Damnati, Benoit Favre, Mickael Rouvier, Remi Auguste, Benjamin Bigot, Richard Dufour, Corinne Fredouille, Georges Linares, Grégory Senay, Pierre Tirilly and Jean Martinet
  Multimodal understanding for person recognition in video broadcasts
  Interspeech, 2014
• Luong N.-Q., Lecouteux B., Besacier L.
  LIG System for WMT13 QE Task: Investigating the Usefulness of Features in Word Confidence Estimation for MT
  in WSMT - Proceedings of the 8th Workshop on Statistical Machine Translation, Sofia : Bulgaria (2013)
• Julien Fayolle, Murat Saraclar, Fabienne Moreau, Christian Raymond and Guillaume Gravier
  Lexical-phonetic automata for spoken utterance indexing and retrieval
  InterSpeech, 2012

References