|
i need suggestions about the material to refer regarding the extensions of PAC(Probably Approximately Correct) learning model to real and multi-valued functions How the VC-dimension is extended to real valued functions? |
|
There are two primary ideas to redefine: generalization error (sometimes just called "error") and VC-dimension. We have the correct hypothesis h:X->R and our guess f:X->R, and there is still a probability distribution P on X. The error is defined as: error = integral[ (h(x) - f(x))^2 ] dP(x). This is basically the probability of an error, weighted by how bad the error is. Previously (when h,f were boolean) it was a probability in the interval [0,1], but now it can by any nonnegative real value. The VC dimension is defined like this: suppose you have a concept class C, which contains all the hypotheses under consideration. Then define the indicator functions I(C) as the set I(C) = { For each h in C, beta in R, {x | h(x) > beta} }. And the VCdim(C) = VCdim(I(C)), using the old definition. Specifically, the VC dimension of C is the largest set of points in X which is shattered by I(C). Basically, this definition is saying "treat the VC dim of real valued functions as being the VC dimension of all sets that can be separated by some beta." It's like transforming C into a set of sets by taking the indicator function (0,1-valued functions) based on {x : h(x) > beta} for some real number beta. One source for all this is chapter 5 in Statistical Learning Theory by Vladimir Vapnik (who is the "V" in VC dimension). |
