LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 1

Thread Tools Display Modes
Prev Previous Post   Next Post Next
Old 04-11-2013, 04:47 PM
grozhd grozhd is offline
Junior Member
Join Date: Apr 2013
Posts: 4
Default How does Hoeffding's inequality work if we have a fixed sample?

As far as I understand Hoeffding's inequality tells us about the probability of "big" differences between a random variable value (mean of N independent r.v.'s) and a number (it's expected value).

Since it is a probabilistic inequality it means that if we try to do the expirement we will get this "big" difference only with certain limited probability. And "doing the experiment" assumes that we have a probability space X with a probability function P, then some outcome x from X happens, our random variables have some value on this x.

But when we are talking about learning we have a fixed data set so it seems to me that we don't observe a new outcome x each time, but we use one fixed which corresponds to our learning data set. And as we go from first hypothesis to second we can't use Hoeffding's inequality no more unless we select another random sample. For example is sample is finite and I have big hypothesis set I will easily go from one hypothesis to another and find one which is equal to target function on that sample. But as professor said in first lecture I didn't learn anything, I just memorized the data. But in lecture 2 it seems that we do the same and we are saying that inequality should work which is obviously not true for my example.

I know that I may have stated it fuzzily but that's because I don't actually understand the formalism here: what is our probability space, what is P, what are the random variables, - so that's why I can't formulate my question precisely. But I have a feeling that using this same data set somehow violates the probabilistic picture.

So, if anyone could clarify that it would be great, thanks in advance.
Reply With Quote

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT -7. The time now is 12:18 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2021, 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.