<p>Pseudo dimension and fat shattering dimension are (some of the) analogue of VC dimension in the regression setting. See <a href="https://ttic.uchicago.edu/%7Etewari/lectures/lecture15.pdf" rel="nofollow noreferrer">https://ttic.uchicago.edu/~tewari/lectures/lecture15.pdf</a> (section 3)</p>

CC BY-SA 4.0
2021-02-03T19:37:46.270Z
2021-02-03T19:37:46.270Z
Another Grad student
<p>Daniely et al had some works on the subject back in 2012--2015.</p>
<p>In particular, it is referred to (there) as &quot;multiclass learning&quot;.
Here are two works on this:</p>
<p><a href="https://arxiv.org/abs/1308.2893" rel="nofollow noreferrer">Multiclass learnability and the ERM principle</a></p>
<p><a href="https://arxiv.org/abs/1205.6432" rel="nofollow noreferrer">Multiclass Learning Approaches: A Theoretical Comparison with Implications</a></p>
<p>Unfortunately, my knowledge of this is limited to knowing the authors personally, so I can't really give any technical details :)</p>

CC BY-SA 4.0
2021-02-02T13:56:35.737Z
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.
ste
CC BY-SA 4.0
2021-02-02T15:41:13.663Z
@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.
Shaull
CC BY-SA 4.0
2021-02-02T16:17:04.623Z
But as I say in the OP, I'm not looking for classification but for regression. How is multiclassing a case of regression?
ste
CC BY-SA 4.0
2021-02-02T18:57:41.077Z
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.
Shaull
CC BY-SA 4.0
2021-02-01T18:24:37.387Z
2021-02-01T18:41:51.840Z
2021-02-01T18:41:51.840Z
Shaull
<p>In Y. S. Abu-Mostafa's book &quot;Learning from Data&quot;, he mentions on page 55 after deriving the VC generalization bound for a binary target function that &quot;it can be extended to other types of target functions&quot;. 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 <span class="math-container">$h \in \mathcal{H}$</span> maps input space <span class="math-container">$\mathcal{X}$</span> to <span class="math-container">$\mathbb{R}^N$</span>, rather than classifications. But I don't see how shattering could be adapted for these target functions.</p>

CC BY-SA 4.0
2021-01-31T06:22:49.667Z
Maybe the sets allowed to use for shattering are restricted to some geometric families, such as halfspaces. Such questions are studied in learning theory.
domotorp
<machine-learning><vc-dimension>
VC generalization bound extended to other types of target functions
ste
# VC generalization bound extended to other types of target functions

(Asked by: username_0 on 2021-01-29)

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 intereusername_0d 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.

**Tags:** machine-learning, vc-dimension

> **Comments:**
> **username_1**: Maybe the sets allowed to use for shattering are restricted to some geometric families, such as halfspaces. Such questions are studied in learning theory.  

---

## 2 answers

### Answer by username_2 on 2021-02-03. Score: 3 | Accepted answer

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](https://ttic.uchicago.edu/%7Etewari/lectures/lecture15.pdf) (section 3)


---

### Answer by username_3 on 2021-02-01. Score: 1

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](https://arxiv.org/abs/1308.2893)

[Multiclass Learning Approaches: A Theoretical Comparison with Implications](https://arxiv.org/abs/1205.6432)

Unfortunately, my knowledge of this is limited to knowing the authors personally, so I can't really give any technical details :)

> **Comments:**
> **username_0**: 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.  
> **username_3**: @username_0 - 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.  
> **username_0**: But as I say in the OP, I'm not looking for classification but for regression. How is multiclassing a case of regression?  
> **username_3**: 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.  

---

