Doubt from lecture 2(Is learning feasible?)

[shirin]

At 31 minutes mark professor has assumed that the input samples come from a probability distribution. My question is why do we make this assumption? Because throughout the lecture we haven't make use of this assumption anywhere.

[yaser]

The assumption made it possible to invoke Hoeffding inequality. Without a probability distribution, one cannot talk about the probability of an event (the left-hand-side of the inequality). The specifics of the probability distribution don't matter here, any distribution will do.

[shirin]

Can't I start talking about hypothesis analogy without making this assumption?

I mean if i say that a hypothesis is analogous to a bin and then I say that for any hypothesis there is a probability that that it will make a wrong classification in the bin and in the sample with probability \mu & \vu.

And then go ahead with hooeffding's inequality.

In doing so do I really need that assumption?

[yaser]

Originally Posted by shirin

Can't I start talking about hypothesis analogy without making this assumption?

I mean if i say that a hypothesis is analogous to a bin and then I say that for any hypothesis there is a probability that that it will make a wrong classification in the bin and in the sample with probability \mu & \vu.

And then go ahead with hooeffding's inequality.

In doing so do I really need that assumption?

The introduction of a probability is not needed to make the analogy between a hypthesis and a bin, but it is needed to invoke Hoeffding inequality on the bin (and the hypothesis). Think of it this way. If I choose 3000 voters according to a deterministic criterion (say the richest 3000 people in the country) and poll them about who they are going to vote for, this sample will not indicate how the population as a whole will vote. If I introduce a probability distribution (say each voter in the population is as likely to be chosen for the poll as every other voter), then I can apply statistical results like Hoeffding to infer from a random sample of 3000 people how the population as a whole will vote.