LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 2 - Training versus Testing (http://book.caltech.edu/bookforum/forumdisplay.php?f=109)
-   -   Problem with understanding the proof of Sauer Lemma (http://book.caltech.edu/bookforum/showthread.php?t=4604)

yongxien 06-10-2015 11:31 PM

Problem with understanding the proof of Sauer Lemma
 
I will replicate the proof here which is from the book "Learning from Data"

Sauer Lemma:
$B(N,K) \leq \sum_{i=0}^{k-1}{n\choose i}$

Proof:
The statement is true whenever k = 1 or N = 1 by inspection. The proof is by induction on N. Assume the statement is true for all $N \leq N_o$ and for all k. We need to prove that the statement for $N = N_0 + 1$ and fpr all k. Since the statement is already true when k = 1(for all values of N) by the initial condition, we only need to worry about $k \geq 2$. By (proven in the book), $B(N_0 + 1, k) \leq B(N_0, k) + B(N_0, k-1)$ and applying induction hypothesis on each therm on the RHS, we get the result.

**My Concern** From what I see this proof only shows that if $B(N, K)$ implies $B(N+1, K)$. I can't see how it shows $B(N, K)$ implies $B(N, K+1)$. This problem arises because the $k$ in $B(N_0 + 1, K)$ and $B(N_0, K)$ are the same, so i think i need to prove the other induction too. Why the author is able to prove it this way?

yongxien 06-10-2015 11:34 PM

Re: Problem with understanding the proof of Sauer Lemma
 
OK i think i will just post it below. I can't find an edit button. I mean for 2 variable induction, shouldn't we prove B(N,k) implies B(N+1,k) and B(N, K+1)?

htlin 06-14-2015 07:26 PM

Re: Problem with understanding the proof of Sauer Lemma
 
You can imaging that the induction hypothesis to be B(N, k) satisfying the inequality for "all k", and then, B(N+1, k) satisfies the inequality for "all k" too.

Hope this helps.

yongxien 07-22-2015 11:03 PM

Re: Problem with understanding the proof of Sauer Lemma
 
That is my concern. Why "all k" when we have not proved it.


All times are GMT -7. The time now is 06:35 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.