.. ****************************************************************************** .. * Copyright 2020-2021 Intel Corporation .. * .. * Licensed under the Apache License, Version 2.0 (the "License"); .. * you may not use this file except in compliance with the License. .. * You may obtain a copy of the License at .. * .. * http://www.apache.org/licenses/LICENSE-2.0 .. * .. * Unless required by applicable law or agreed to in writing, software .. * distributed under the License is distributed on an "AS IS" BASIS, .. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. .. * See the License for the specific language governing permissions and .. * limitations under the License. .. *******************************************************************************/ BrownBoost Classifier ===================== BrownBoost is a boosting classification algorithm. It is more robust to noisy data sets than other boosting classification algorithms [Freund99]_. BrownBoost is a binary classifier. For a multi-class case, use :ref:`svm_multi_class` framework of the library. Details ******* Given :math:`n` feature vectors :math:`x_1 = (x_{11}, \ldots, x_{1p}), \ldots, x_n = (x_{n1}, \ldots, x_{np})` of size :math:`p` and a vector of class labels :math:`y= (y_1, \ldots, y_n)`, where :math:`y_i \in K = \{-1, 1\}` describes the class to which the feature vector :math:`x_i` belongs, and a weak learner algorithm, the problem is to build a two-class BrownBoost classifier. Training Stage -------------- The model is trained using the Freund method [Freund01]_ as follows: #. Calculate :math:`c = \mathrm{erfinv}^2(1 - \varepsilon)`, where: - :math:`\mathrm{erfinv}(x)` is an inverse error function, - :math:`\varepsilon` is a target classification error of the algorithm defined as :math:`\frac {1}{n} \sum _{i=1}^{n} |p(x_i) - y_i|` - :math:`p(x) = \text{erf} \left(\frac {\sum _{i=1}^{M} \alpha_i h_i(x)}{\sqrt{c}}\right)` - :math:`\mathrm{erf}(x)` is the error function, - :math:`h_i(x)` is a hypothesis formulated by the :math:`i`-th weak learner, :math:`i = 1, \ldots, M`, - :math:`\alpha_i` is the weight of the hypothesis. #. Set initial prediction values: :math:`r_1(x, y) = 0`. #. Set "remaining timing": :math:`s_1 = c`. #. Do for :math:`i=1, 2, \ldots` until :math:`s_{i+1} \leq 0` #. With each feature vector and its label of positive weight, associate :math:`W_i(x, y) = e^{\frac {-(r_i(x, y) + s_i)^2}{c}}`. #. Call the weak learner with the distribution defined by normalizing Lmath:`W_i(x, y)` to receive a hypothesis :math:`h_i(x)`. #. Solve the differential equation .. math:: \frac {dt}{d\alpha} = \gamma = \frac {\sum _{(x,y)} \exp (-\frac{1}{c} (r_i(x, y) + \alpha h_i(x) y + s_i - t)^2)h_i(x)y} {\sum _{(x,y)} \exp (-\frac{1}{c} (r_i(x, y) + \alpha h_i(x) y + s_i - t)^2)} with given boundary conditions :math:`t = 0` and :math:`\alpha = 0` to find :math:`t_i = t^{*} > 0` and :math:`\alpha_i = \alpha^{*}` such that either :math:`\gamma \leq ν` or :math:`t^{*} = s_i`, where :math:`ν` is a given small constant needed to avoid degenerate cases. #. Update the prediction values: :math:`r_{i+1}(x, y) = r_i(x, y) + \alpha_i h_i(x) y`. #. Update "remaining time": :math:`s_{i+1} = s_i - t_i`. End do The result of the model training is the array of :math:`M` weak learners :math:`h_i`. Prediction Stage ---------------- Given the BrownBoost classifier and :math:`r` feature vectors :math:`x_1, \ldots, x_r`, the problem is to calculate the final classification confidence, a number from the interval :math:`[-1, 1]`, using the rule: .. math:: p(x) = \text{erf} \left(\frac {\sum _{i=1}^{M} \alpha_i h_i (x)}{\sqrt{c}}\right) Batch Processing **************** BrownBoost classifier follows the general workflow described in :ref:`classification_usage_model`. Training -------- For a description of the input and output, refer to :ref:`classification_usage_model`. At the training stage, a BrownBoost classifier has the following parameters: .. tabularcolumns:: |\Y{0.2}|\Y{0.2}|\Y{0.6}| .. list-table:: Training Parameters for BrownBoost Classifier (Batch Processing) :header-rows: 1 :widths: 10 20 30 :align: left :class: longtable * - Parameter - Default Value - Description * - ``algorithmFPType`` - ``float`` - The floating-point type that the algorithm uses for intermediate computations. Can be ``float`` or ``double``. * - ``method`` - ``defaultDense`` - The computation method used by the BrownBoost classifier. The only training method supported so far is the Y. Freund's method. * - ``nClasses`` - :math:`2` - The number of classes. * - ``weakLearnerTraining`` - **DEPRECATED**: Pointer to an object of the weak learner training class **USE INSTEAD**: Pointer to an object of the classification stump training class - **DEPRECATED**: Pointer to the training algorithm of the weak learner. By default, a stump weak learner is used. **USE INSTEAD**: Pointer to the classifier training algorithm. Be default, a classification stump with gini split criterion is used. * - ``weakLearnerPrediction`` - **DEPRECATED**: Pointer to an object of the weak learner prediction class **USE INSTEAD**: Pointer to an object of the classification stump prediction class - **DEPRECATED**: Pointer to the prediction algorithm of the weak learner. By default, a stump weak learner is used. **USE INSTEAD**: Pointer to the classifier prediction algorithm. Be default, a classification stump with gini split criterion is used. * - ``accuracyThreshold`` - :math:`0.01` - BrownBoost training accuracy :math:`\varepsilon`. * - ``maxIterations`` - :math:`100` - The maximal number of iterations for the BrownBoost algorithm. * - ``newtonRaphsonAccuracyThreshold`` - :math:`1.0\mathrm{e}-3` - Accuracy threshold of the Newton-Raphson method used underneath the BrownBoost algorithm. * - ``newtonRaphsonMaxIterations`` - :math:`100` - The maximal number of Newton-Raphson iterations in the algorithm. * - ``degenerateCasesThreshold`` - :math:`1.0\mathrm{e}-2` - The threshold used to avoid degenerate cases. Prediction ---------- For a description of the input and output, refer to :ref:`classification_usage_model`. At the prediction stage, a BrownBoost classifier has the following parameters: .. tabularcolumns:: |\Y{0.2}|\Y{0.2}|\Y{0.6}| .. list-table:: Prediction Parameters for BrownBoost Classifier (Batch Processing) :header-rows: 1 :widths: 10 20 30 :align: left :class: longtable * - Parameter - Default Value - Description * - ``algorithmFPType`` - ``float`` - The floating-point type that the algorithm uses for intermediate computations. Can be ``float`` or ``double``. * - ``method`` - ``defaultDense`` - Performance-oriented computation method, the only method supported by the BrownBoost classifier. * - ``nClasses`` - :math:`2` - The number of classes. * - ``weakLearnerPrediction`` - **DEPRECATED**: Pointer to an object of the weak learner prediction class **USE INSTEAD**: Pointer to an object of the classification stump prediction class - **DEPRECATED**: Pointer to the prediction algorithm of the weak learner. By default, a stump weak learner is used. **USE INSTEAD**: Pointer to the classifier prediction algorithm. Be default, a classification stump with gini split criterion is used. * - ``accuracyThreshold`` - :math:`0.01` - BrownBoost training accuracy :math:`\varepsilon`. Examples ******** .. tabs:: .. tab:: C++ (CPU) Batch Processing: - :cpp_example:`brownboost_dense_batch.cpp ` .. tab:: Java* .. note:: There is no support for Java on GPU. Batch Processing: - :java_example:`BrownBoostDenseBatch.java ` .. tab:: Python* Batch Processing: - :daal4py_example:`brownboost_batch.py`