Results 1 to 3 of 3

Math Help - Probably Approximately Correct Learning

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    1

    Probably Approximately Correct Learning

    Hello, I am reading a book on machine learning and struggling through - "Introduction to Machine Learning" by Ethem Alpaydin. I hit an early sub-chapter on PAC and I don't follow the author's math and reasoning.

    The first math stumbling block I hit is when the author says "We have the inequality (1 - x) <= exp[-x]". He just drops that, doesn't explain where it comes from. Now, I can plug values into that statement and see that it's true. But where the heck did it come from? There's no context, it's just something he offers up, like saying "You need to nail this board to your house. Now, we know that pigeons eat seed ..." This is what always confuses me in math, when someone just throws out a statement that seemingly has no connection.

    He then plugs the problem into that equation, so I need to give some context:

    "In PAC learning given a class C and examples from unknown but fixed probability distribution p(x) we want to find the number of examples N such that with probability at least 1 - s the hypothesis h has error at most e for arbitrary s <= 1/2 and e > 0:"

    (I have no way to draw the delta sign so I'll use ?)

    "P{C?h <= e} >= 1 - s where C?h is the region of difference between C and h".

    He then uses a graph to illustrate that the probability that N independent draws from the distribution will 'miss' the error region between C and h will be at most 4(1 - e/4)^N which we would like to be at most s.

    I follow him to there, more or less. But then he introduces the inequality, and says:

    "If we choose N and s such that we have 4exp[-eN/4] <= s"

    Huh? Logically it seems to me that he has replaced 4(1 - e/4)^N with 4exp[-eN/4], since we stated that we want the former to be AT MOST (thus, <=) s. But I don't see how that substitution was made ... it doesn't seem that he used the formula, since he says we 'choose' this (another thing that boggles me).

    He then goes on to state that, with the above 'choice':

    "We can also write 4(1 - e/4)^N <= s".

    Okay, sure, we can use the first thing you pulled out of the blue to replace the second thing you pulled out of the blue ... got it. But ... where did the two things come from? And isn't the last thing just the basic restriction he stated in the first place, making all that substitution stuff unnecessary?

    Can anyone explain to me what those middle steps are about and why they are necessary?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    28
    Quote Originally Posted by newagelightbulb View Post
    Hello, I am reading a book on machine learning and struggling through - "Introduction to Machine Learning" by Ethem Alpaydin. I hit an early sub-chapter on PAC and I don't follow the author's math and reasoning.

    The first math stumbling block I hit is when the author says "We have the inequality (1 - x) <= exp[-x]". He just drops that, doesn't explain where it comes from. Now, I can plug values into that statement and see that it's true. But where the heck did it come from? There's no context,
    It seems like you are frustrated, but you are also assuming everyone on this forum has the book in question, what if no one does? You would then be doing the same as the author in question.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by newagelightbulb View Post
    Hello, I am reading a book on machine learning and struggling through - "Introduction to Machine Learning" by Ethem Alpaydin. I hit an early sub-chapter on PAC and I don't follow the author's math and reasoning.

    The first math stumbling block I hit is when the author says "We have the inequality (1 - x) <= exp[-x]". He just drops that, doesn't explain where it comes from. Now, I can plug values into that statement and see that it's true. But where the heck did it come from? There's no context, it's just something he offers up, like saying "You need to nail this board to your house. Now, we know that pigeons eat seed ..." This is what always confuses me in math, when someone just throws out a statement that seemingly has no connection.
    1-x is the tangent to e^{-x} at the origin, but the gradient of e^{-x} is a decreasing for positive x, so e^{-x} is always above its gradient at the origin. (draw a picture and you will see what is going on).

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: July 29th 2011, 01:39 AM
  2. Replies: 4
    Last Post: May 25th 2011, 03:59 AM
  3. Replies: 2
    Last Post: February 11th 2011, 07:08 PM
  4. Greedy Learning
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 2nd 2009, 02:51 AM
  5. Learning tables
    Posted in the Algebra Forum
    Replies: 9
    Last Post: February 20th 2008, 11:46 PM

Search Tags


/mathhelpforum @mathhelpforum