In Y. S. Abu-Mostafa's book "Learning from Data", he mentions on page 55 after deriving the VC generalization bound for a binary target function that "it can be extended to other types of target functions". I have looked online for quite a bit but it's really not clear to me how that should work. I'm particularly interested in continuous target functions, where hypothesis $h \in \mathcal{H}$ maps input space $\mathcal{X}$ to $\mathbb{R}^N$, rather than classifications. But I don't see how shattering could be adapted for these target functions.
2 Answers
Pseudo dimension and fat shattering dimension are (some of the) analogue of VC dimension in the regression setting. See https://ttic.uchicago.edu/~tewari/lectures/lecture15.pdf (section 3)
Daniely et al had some works on the subject back in 2012--2015.
In particular, it is referred to (there) as "multiclass learning". Here are two works on this:
Multiclass learnability and the ERM principle
Multiclass Learning Approaches: A Theoretical Comparison with Implications
Unfortunately, my knowledge of this is limited to knowing the authors personally, so I can't really give any technical details :)
-
$\begingroup$ Thanks for the answer. I looked into them but I fail to see how multiclass prediction relates to VC dimensions of continuous functions rather than classifications. $\endgroup$– steFeb 2, 2021 at 13:56
-
$\begingroup$ @ste - I may be completely off. From the conversations I had with Amit Daniely, he mentioned that what they do was essentially to extend the idea of VC dimension to multiclasses. But it's entirely possible I misunderstood. $\endgroup$– ShaullFeb 2, 2021 at 15:41
-
$\begingroup$ But as I say in the OP, I'm not looking for classification but for regression. How is multiclassing a case of regression? $\endgroup$– steFeb 2, 2021 at 16:17
-
$\begingroup$ I don't see where you mention regression in the OP. Anyway, as I mentioned: I know next to nothing about this topic. The OP mentions extending VC beyond the binary setting, and that rang a bell for me, so I wrote what little I know. If you want me to delete the answer, let me know. $\endgroup$– ShaullFeb 2, 2021 at 18:57