> For the complete documentation index, see [llms.txt](https://statduck.gitbook.io/statduck/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://statduck.gitbook.io/statduck/esl/ensemble/boosting.md).

# Boosting

## Idea

* It is the method combining several classifiers in a sequential way.
* Correctly classified data doesn't need to be considered in our model, so it puts a weight on wrong classified data. 

## Notation

* Classifiers: $$H={h\_1,\cdots,h\_m}, ;s.t. ;h\_j:X\rightarrow{1,-1}$$
* Data: $$X={x\_1,\cdots,x\_n}, ;Y={y\_1,\cdots,y\_n}, ;y\_i\in{1,-1}$$
* Matrix: $$A\_{ij}=y\_ih\_j(x\_i) ;$$$$A\_{ij}=1(correct),A\_{ij}=-1(wrong)$$
* Weight for classifiers: $$w\in\mathbb{R}^m$$
* Weight f or data: $$\lambda \in \mathbb{R}^n$$

## Problem

$$
p(\lambda)=min{w^TA\lambda:w\in\Delta\_n}, ;s.t. ;\Delta\_n={w|\Sigma^n\_{i=1}=1,w\_i \geq0}
$$

$$
(A\lambda)=\begin{bmatrix}A\_1 \cdots A\_m\end{bmatrix} \begin{bmatrix} \lambda\_1 \ \vdots \ \lambda\_m\end{bmatrix}, w^TA\lambda=w^TA\_1\lambda\_1+\cdots+w^TA\_m\lambda\_m
$$

$$
\max\_{\lambda \in \Delta\_m} {p(\lambda)=\min\_{w\in \Delta\_n}w^TA\lambda} \ \min\_{w\in \Delta\_n}{f(w)=\max\_{\lambda \in \Delta\_m}w^TA\lambda}
$$

 The above optimization problem is an original problem, and the below one is the duality problem. 

In this situation, if $$A\_j\lambda\_j$$is lower than other values, it means the classifier $$A\_j$$is not good at predicting. So $$p(\lambda)$$ means the lowest value which the worst classifier has. When we make more weight on the worst classifier by making $$\lambda$$ bigger, $$p(\lambda)$$would be bigger.

To solve this problem, we can use subgradient method or mirror descent method.

## Subgradient method

The optimization problem is defined as:

$$
\max\_{\lambda \geq 0 }p(\lambda)
$$