PLA - Need Guidance

[samirbajaj]

Greetings!

I am working on the Perceptron part of the homework, and having spent several hours on it, I'd like to know if I am proceeding in the right direction:

1) My implementation converges in 'N' iterations. This looks rather fishy. Any comments would be appreciated. (Otherwise I may have to start over :-( maybe in a different programming language)

2) I don't understand the Pr( f(x) != g(x) ) expression -- what exactly does this mean? Once the algorithm has converged, presumable f(x) matches g(x) on all data, so the difference is zero.


Thanks.

-Samir

[yaser]

Originally Posted by samirbajaj

I don't understand the Pr( f(x) != g(x) ) expression -- what exactly does this mean? Once the algorithm has converged, presumable f(x) matches g(x) on all data, so the difference is zero

On all data, yes. However, the probability is with respect to over the entire input space, not restricted to being in the finite data set used for training.

[jakvas]

If we try to evaluate Pr(f(x)!=g(x)) experimentaly how many random verification points should we use to get a significant answear?

I am tempted to believe that Hoeffding's inequality is applicable in this case to a single experiment but since we are averaging out over very many experiments I'm not sure on how to choose the amount of those verification data points (I ultimately worked with 10000 per experiment just to be sure).

[yaser]

Originally Posted by jakvas

I am tempted to believe that Hoeffding's inequality is applicable in this case to a single experiment but since we are averaging out over very many experiments I'm not sure on how to choose the amount of those verification data points (I ultimately worked with 10000 per experiment just to be sure).

Indeed, the average helps smooth out statistical fuctuations. Your choice of 10000 points is pretty safe.

[jtwang]

How would you determine f(x) == g(x) exactly - since the set of possible hypotheses is infinite (3 reals), wouldn't Pr(f(x) != g(x)) == 1? Obviously you could choose some arbitrary epsilon but then that wouldn't be "exactly."

[yaser]

Originally Posted by jtwang

How would you determine f(x) == g(x) exactly - since the set of possible hypotheses is infinite (3 reals), wouldn't Pr(f(x) != g(x)) == 1? Obviously you could choose some arbitrary epsilon but then that wouldn't be "exactly."

is per point . It may be true for some 's and false for others, hence the notion of probability that it's true (probability with respect to ). We are not saying that is identically equal to .

[dobrokot]

Originally Posted by jakvas

I'm not sure on how to choose the amount of those verification data points (I ultimately worked with 10000 per experiment just to be sure).

Hoeffding inequality given in same lesson can help to choose number of points. g(x)!=f(x) can be thinked as red marble

[nroger]

I still don't understand this Pr() function. Given two (linear) functions f and g, what is the Pr() of f and g?
Thanks...Neil

[yaser]

Originally Posted by nroger

I still don't understand this Pr() function. Given two (linear) functions f and g, what is the Pr() of f and g?
Thanks...Neil

This is the probability of an event, the event in the case discussed in this thread being that , which means you pick at random according to the probability distribution over the input space and evaluate "the fraction of time" that does not give the same value as for the you pick.

BTW, anyone who wants to refresh some of the prerequisite material for the course, here are some recommendations:

http://book.caltech.edu/bookforum/showthread.php?t=3720

[sricharan92]

Sir

If I understand correctly, we are using N = 10 training points out of a randomly generated x points according to the target function f for perceptron learning and Pr(f(x) != g(x)) should be calculated considering all x points and not just the training data. Am I right ?