# Boosting algorithm

http://cs229.stanford.edu/extra-notes/boosting.pdf

I am currently trying to understand general basic theory of boosting. On the page 5 I came across following claim, which is consistent result of previous formulas: Thus we have that the misclassification error has upper bound: (formula in notes) and so if J(delta)<1/m then the vector delta makes no mistakes on the training data How is it possible that J(delta)<1/m? In case we have no mistakes, indicator function 1{} always equals to 0, and as a result 1/m*0=0 and 0< J(delta).

And my second question is connected with this formula on page 5: J(Delta^^t)<= (1-4a^^2)*J(Delta^^0). This formula is not compatible with Lemma 2.1. on page 4. For instance, for t=2, we have that J(Delta^^2)<=J(Delta^^1)<=1*J(Delta^^0), which is not compatible with last formula on page 5.

• It would be much better to include the formulas in the question rather then expect someone to find them in the .pdf – mdewey Oct 20 '16 at 11:29
• I would have to rewrite one page of text and formulas, I guess that linking pdf and highlitghing problems is better idea in this case. I give you precise number of pages and formulas. Such approach in this case is easier both for me and for you. – mokebe Oct 20 '16 at 11:37
• Questions should be at least intelligible without reference to external sources - symbols explained & so on - & external sources should be properly referenced. You were very lucky to get an answer! – Scortchi Oct 21 '16 at 14:13
• sorry, I will improve my question soon. – mokebe Oct 21 '16 at 18:39

Question 1

From the pdf (page 5):

$\frac{1}{M} x \leq J(\theta)$

(Since $x$ is a sum of indicatorfunctions, it can be any non-negative integer)

What is said is that if $J(\theta) < \frac{1}{M}$ then there are no mistakes, so $x=0$.

You say: "But $1/m\cdot0=0$ and $0< J(\theta)$", but that is not what is said above.

The logic here is that $x$ is an integer. So for $\frac{1}{M} x \leq J(\theta)$ and $J(\theta) < \frac{1}{M}$ to be true, $x<1 \implies x=0$.

I am not sure what this implies or how this would be used in boosting.

Question 2

I don't see how this is a problem.

Lemma 2.1 states that with each iteration $t$, $J(\theta^{(t)})$ decreases with at least a factor $\sqrt{1-4\gamma^2}$. (Decreases because $1-4\gamma^2 \leq 1$, so $J(\theta^{(t-1)})$ is multiplied with a factor lower than one, so it decreases.)

The equation at the bottom of page 5 then states that after $t$ iterations, $J(\theta)$ has decreased by $\sqrt{1-4\gamma^2}$ at least $t$ times, in other words $(1-4\gamma^2)^\frac{t}{2}$. And since $J(\theta^{(0)})$ is picked to be $1$, $J(\theta^{(t)})\leq (1-4\gamma^2)^\frac{t}{2}$.

So let's say $t=2$:

According to page 5: $J(\theta^{(2)}) \leq (1-4\gamma^2)^\frac{2}{2}\cdot J(\theta^{(0)}) = (1-4\gamma^2)$

According to theorem 2.1:

$J(\theta^{(2)}) \leq (1-4\gamma^2)^\frac{1}{2}\cdot J(\theta^{(1)})$

and

$J(\theta^{(1)}) \leq (1-4\gamma^2)^\frac{1}{2}\cdot J(\theta^{(0)})$

Then substituting $J(\theta^{(1)})$:

$J(\theta^{(2)}) \leq (1-4\gamma^2)^\frac{1}{2}(1-4\gamma^2)^\frac{1}{2}\cdot J(\theta^{(0)}) = (1-4\gamma^2)\cdot J(\theta^{(0)}) = (1-4\gamma^2)$

Again nothing wrong here. The error you make in the first post is saying $J_2 \leq J_1 \leq J_0$, while it should be $J_2 \leq c\cdot J_1 \leq c^2\cdot J_0$