1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Maybe the sets allowed to use for shattering are restricted to some geometric families, such as halfspaces. Such questions are studied in learning theory. $\endgroup$
    – domotorp
    Jan 31, 2021 at 6:22

2 Answers 2

3
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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 :)

$\endgroup$
4
  • $\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$
    – ste
    Feb 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$
    – Shaull
    Feb 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$
    – ste
    Feb 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$
    – Shaull
    Feb 2, 2021 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.