The AdaBoost method#

The general boosting procedure described above requires two key operations: Adjust_Distribution and Combine_Outputs.

The cost function we aim to minimize for a classifier involves both the parameters of the classifier and the weights of each classifier used in the combination. The cost function is given by:

where $e$ is the error, $l$ is the loss function, $\theta$ represents the parameters of the classifier, and $\alpha$ denotes the weights for combining the classifiers. $G(\theta ,\alpha )$ is used for sparsification.

For a two-class classifier, the error $e$ can be represented as $e=yg(x)$, where $g(x)$ is the decision function. The cost function $J(\theta ,\alpha )$ is expressed as:

Here, $h_m(x_i)$ is the decision function at the $m$-th iteration. The decision function $H(x)$ consists of kernel functions $h(x)$ and weight combinations $\alpha$. The decision function for the $m$-th iteration is given by:

then,

This expression shows that $H_{(m)}(x)$ is incrementally updated in each boosting iteration.

The cost function can be further expanded as follows:

Substituting $h_m(x_i)$ into the expression:

This can be rewritten as:

or:

where $w_i^m=\exp (-y_i{h}_{(m-1)}(x_i))$ represents the weight of the sample $x_i$ at iteration $m$.

Given:

• For correctly classified samples: $y_i{h}_m(x_i)=1$

• For misclassified samples: $y_i{h}_m(x_i)=-1$

The cost function $J(\theta ,\alpha )$ can be split into contributions from correctly classified samples ${\mathrm{\Omega }}_1$ and misclassified samples ${\mathrm{\Omega }}_2$.

The general formula for $J(\theta ,\alpha )$ is:

For correctly classified samples ${\mathrm{\Omega }}_1$:

In this case, $y_i{h}_m(x_i)=1$. Therefore:

Thus, the contribution to $J(\theta ,\alpha )$ from correctly classified samples is:

For misclassified samples ${\mathrm{\Omega }}_2$:

In this case, $y_i{h}_m(x_i)=-1$. Therefore:

Thus, the contribution to $J(\theta ,\alpha )$ from misclassified samples is:

Combining both contributions:

Weights of combination#

Given the definitions:

• $B=F_C(m)$ (true classifications)

• $A=T_C(m)$ (false classifications)

and using the error rate definition:

we can substitute these into the derivative calculation.

Rewrite $A$ and $B$

Substitute $A$ and $B$ into the equation:

which becomes:

Express ${ϵ}_m$ in Terms of $F_C(m)$ and $T_C(m)$

From the definition of ${ϵ}_m$:

Rearrange to express $F_C(m)$ in terms of ${ϵ}_m$ and $T_C(m)$:

Solve for $F_C(m)$:

So:

Substitute into the Exponential Term

Now substitute this into the exponential term:

Solve for ${\alpha }_m$

Taking the natural logarithm of both sides:

So:

Using Taylor expansion of $e^{-y{h}_m(x)}$ the exponential loss is approximated by:

desired classifier $h_m(x)$

by noticing that $${\mathbb{E}}_{x\sim D}\left[e^{-y{H}_{m-1}(x)}\right]$$ is a constant.

Denote a distribution $${\mathcal{D}}_m(x)=\frac{\mathcal{D}(x)e^{-y{H}_{m-1}(x)}}{{\mathbb{E}}_{x\sim D}\left[e^{-y{H}_{m-1}(x)}\right]}$$

In the expression $y{h}_m(x)=1-2\mathbb{I}(y\ne h_m(x))$, where $y$ is the true label and $h_m(x)$ is the predicted label, the term $\mathbb{I}(y\ne h_m(x))$ is an indicator function that equals 1 if the true label $y$ does not match the predicted label $h_m(x)$, and 0 if they are the same.

$1-2\mathbb{I}(y\ne h_m(x))$:

• If $y=h_m(x)$: $\mathbb{I}(y\ne h_m(x))=0$, so the expression becomes $1-2\times 0=1$.

• If $y\ne h_m(x)$: $\mathbb{I}(y\ne h_m(x))=1$, so the expression becomes $1-2\times 1=-1$.

Therefore:

• When the prediction $h_m(x)$ is correct, the expression $y{h}_m(x)$ equals 1.

• When the prediction $h_m(x)$ is incorrect, the expression $y{h}_m(x)$ equals -1.

The ideal classifier is:

As can be seen, the ideal $h_m$ minimizes the classification error under the distribution $D_m$. Therefore, the weak learner is to be trained under $D_m$, and has less than 0.5 classification error according to $D_m$ (For $y{h}_m(x)>0$ that $y{h}_m(x)=1-2\mathbb{I}(y\ne h_m(x))$). Considering the relationship between $D_m$ and $D_{m+1}$ we have:

Here, $\frac{1}{Z_m}$ is a normalization factor. Therefore $D_m(x)\cdot e^{-y{\alpha }_t{h}_m(x)}$ is then calculated with,

If ${ϵ}_m>0.5$, then

Thus, ${\alpha }_m<0$. Consequently, there are a few possible scenarios:

1. ${\alpha }_m=0$

2. ${ϵ}_m=1-{ϵ}_m$, which $\alpha$ is calculated as follow,

Adaboost Algorithm#

Input:

• Dataset $D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_m,y_m)\}$

• Base learning algorithm $L$

• Number of learning rounds $T$

Process:

1. Initialize the weight distribution $D_1(x)=\frac{1}{m}$.

2. For $t=1,\dots ,T$:

   • Train a classifier $h_t$ using the base algorithm $L$ on dataset $D$ under the distribution $D_t$.

   • Calculate the error ${ϵ}_t$ of $h_t$, where ${ϵ}_t=P_{x\sim D_t}(h_t(x)\ne f(x))$.

   • If ${ϵ}_t>0.5$, then ${\alpha }_t=0$ and continue,

   • Determine the weight ${\alpha }_t=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)$ of the classifier $h_t$.

   • Update the distribution for the next round: $$D_{t+1}(x)=\frac{D_t(x)\exp (-{\alpha }_{t}f(x)h_t(x))}{Z_t}$$where$ Z_t $isanormalizationfactorthatensures$ D_{t+1} $ is a valid distribution.

3. End the loop.

Output:
The final hypothesis is given by $H(x)=\text{sign}(\sum _{t=1}^T{\alpha }_t{h}_t(x))$.

How its work Adaboost#

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt

# Generate synthetic 2D dataset
X, y = make_classification(n_samples=200, n_features=2, n_informative=2, n_redundant=0, n_clusters_per_class=1, flip_y=0, random_state=42)

# Initialize base classifier
base_classifier = DecisionTreeClassifier(max_depth=1)

# Initialize AdaBoost classifier
adaboost = AdaBoostClassifier(base_classifier, n_estimators=5, algorithm='SAMME.R', random_state=42)

# Fit AdaBoost classifier to the data
adaboost.fit(X, y)

# Predict using the fitted model
y_pred = adaboost.predict(X)

# Plot the decision boundary
def plot_decision_boundary(X, y, model):
    h = .02  # Step size in the mesh
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    plt.contourf(xx, yy, Z, alpha=0.8, cmap=plt.cm.coolwarm)
    plt.scatter(X[:, 0], X[:, 1], c=y, edgecolor='k', marker='o', cmap=plt.cm.coolwarm)
    plt.title('AdaBoost Decision Boundary')
    plt.xlabel('Feature 1')
    plt.ylabel('Feature 2')
    plt.show()

# Plot the decision boundary
plot_decision_boundary(X, y, adaboost)

e:\HadiSadoghiYazdi\.M_HomePage\Lib\site-packages\sklearn\ensemble\_weight_boosting.py:527: FutureWarning: The SAMME.R algorithm (the default) is deprecated and will be removed in 1.6. Use the SAMME algorithm to circumvent this warning.
  warnings.warn(

What we do with AdaBoost#

What we do with AdaBoost can be explained by first reviewing the following works we have mentioned:

1. Bahraini, T., Hosseini, S. M., Ghasempour, M., & Sadoghi Yazdi, H. (2022). Density-oriented linear discriminant analysis. Expert Systems with Applications, 187, 115946.

In the study “Density-oriented linear discriminant analysis,” the authors tackle big data challenges by integrating AdaBoost with a novel base learner, DLDA (Density-Oriented Linear Discriminant Analysis). This combination enhances classification accuracy and efficiency, especially in high-dimensional and imbalanced datasets. The approach is scalable and suitable for various big data applications, offering an innovative solution to improve machine learning performance in complex environments. Future work includes optimizing DLDA and exploring integrations with other advanced techniques.

Bagging algorithm#

Input:

• Dataset $D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_m,y_m)\}$

• Base learning algorithm $L$

• Number of base learners $T$

Process:

1. For $t=1,\dots ,T$:

   • Train the base learner: $h_t=L(D,D_{\text{bs}})$

   • where $D_{\text{bs}}$ is the bootstrap distribution (sampling with replacement)

2. End for

Output: $$H(x)=\arg \underset{y\in Y}{max}\sum _{t=1}^T\mathbb{I}(h_t(x)=y)$$