13

In the lecture series Learning from Data, the professor mentions that the VC dimension measures the model complexity on how many points a given model can shatter. So this works perfectly well for classification models where we could say out of N points if the classifier is able to shatter k points effectively the VC dimension measure would be K. But it was not clear to me how does one measure VC dimension for regression models?

Franck Dernoncourt
  • 42,093
  • 30
  • 155
  • 271
karthikbharadwaj
  • 274
  • 2
  • 8

2 Answers2

3

From Elements of Statistical Learning, p. 238:

So far we have discussed the VC dimension only of indicator functions, but this can be extended to real-valued functions. The VC dimension of a class of real-valued functions ${g(x, \alpha)}$ is defined to be the VC dimension of the indicator class ${\mathbb{1}(g(x, \alpha) − \beta > 0)}$, where $\beta$ takes values over the range of g.

Or, (slightly) more intuitively, to find the VC dimension of a class of real-valued functions, one can find the VC dimension of the class of indicator functions that can be formed by thresholding that class of real-valued functions.

Sean Easter
  • 8,359
  • 2
  • 29
  • 58
  • But this gives the VC dimension for threshold indicators, and at face value I don't see how getting PAC bounds for threshold indicators tells you much about the performance of your regression function. Perhaps you can come up with an argument where you binary search over the regressed value (for bounded output domains). – VF1 Jan 12 '18 at 17:55
  • @VF1 True. How to interpret VC dimension of a regression function could for a good, separate question. – Sean Easter Jan 14 '18 at 18:38
  • I'd post a separate question, but I believe the answer is simply "don't use VC dim for regression," since Rademacher would let you do just as much for arbitrary bounded losses. – VF1 Jan 14 '18 at 20:08
  • @VF1 I would read an answer that said so with interest! All I mean is to suggest that the CV norm is to limit questions to a single question per post, and that the OP didn't touch on interpretation or purpose. – Sean Easter Jan 14 '18 at 20:19
0

See section 5.2 of Statistical Learning (Vapnik) for a derivation of the thresholding indicator trick using Lebesgue-Stieltjes measures. AFAIK this is the only and definitive reference. You should already know where to found the book (and others from Vapnik, they are all superlative).

memeplex
  • 111
  • 2