-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It would be much better to include the formulas in the question rather then expect someone to find them in the .pdf $\endgroup$ – mdewey Oct 20 '16 at 11:29
  • $\begingroup$ 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. $\endgroup$ – mokebe Oct 20 '16 at 11:37
  • $\begingroup$ 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! $\endgroup$ – Scortchi Oct 21 '16 at 14:13
  • $\begingroup$ sorry, I will improve my question soon. $\endgroup$ – mokebe Oct 21 '16 at 18:39
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.