LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 1 (http://book.caltech.edu/bookforum/forumdisplay.php?f=130)
-   -   Doubt from lecture 2(Is learning feasible?) (http://book.caltech.edu/bookforum/showthread.php?t=3971)

 shirin 02-08-2013 08:13 PM

Doubt from lecture 2(Is learning feasible?)

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 02-08-2013 09:17 PM

Re: Doubt from lecture 2(Is learning feasible?)

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 02-09-2013 09:49 PM

Re: Doubt from lecture 2(Is learning feasible?)

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 02-09-2013 10:01 PM

Re: Doubt from lecture 2(Is learning feasible?)

Quote:
 Originally Posted by shirin (Post 9287) 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.

 All times are GMT -7. The time now is 07:08 AM.