# 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)
$$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://statduck.gitbook.io/statduck/esl/ensemble/boosting.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.