Thread: Clarification on VC bound View Single Post
#6
04-26-2012, 06:33 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Clarification on VC bound

Quote:
 Originally Posted by pventurelli@gotoibr.com I have a question regarding a statement made in the textbook. On page 51 in the second paragraph, it is said that the m_H grows logarithmically with N and so is crushed by the factor 1/N. First, igiven that (from page 50) m_H is bounded from above by N^d_vc + 1, how is it true that m_H grows logarithmically with N? Second, is the crushed part of the statement saying that a function that is of the form f1=log(N) is dominated by a function f2=1/x in the sense that f1/f2 tends to zero as N tends to infinity? Thanks for your help in clarifying this point.
The growth function grows polynomially, but the generalization bound has a logarithm in it, and the logarithm of a polynomial grows at a logarithmic rate itself, and hence gets crushed by the linear denominator. It is essentially the same as a polynomial getting crushed by a negative exponential, with the only difference being that we went into a logarithmic scale for both.
__________________
Where everyone thinks alike, no one thinks very much