I'm studying theoretical machine learning at university, and I have this problem in textbook, that I have no Idea how to start. In space $X=R^2$ are given two models $H_1$ (rectangle with sides parallel to the coordinate axes) and $H_2$ (lines). We define a model $H_3$ such that every hypothesis is a combination of one hypothesis from $H_1$ and one from $H_2$. Prove or disprove that the model $H_3$ has a bigger VC dimension (Vapnik–Chervonenkis dimension) then the VC dimensions of the models $H_1$ and $H_2$.

I need to find VC of $H_1$, $H_2$, and combined of $H_3$.

  • $\begingroup$ examples of VC computation here but I fail to understand the $H_1$ and $H_2$ sets, in yout question $\endgroup$
    – Nikos M.
    Apr 20, 2021 at 7:15
  • $\begingroup$ @NikosM. so the first is rectangle with sides parallel to the coordinate axes and second are just straight lines. In textbook I found that VC (H2)=3 and VC(H1)=4 but I don't know how to get the VC dimension of H3? $\endgroup$
    – user779537
    Apr 20, 2021 at 8:28
  • $\begingroup$ If you understand how $VC(H_1)$ and $VC(H_2)$ are derived then it can help derive the combined VC $\endgroup$
    – Nikos M.
    Apr 20, 2021 at 15:57
  • 1
    $\begingroup$ Please credit the original source of all copied material: datascience.stackexchange.com/help/referencing. The same exercise is posted here, so something has been copied from somewhere: cs.stackexchange.com/q/139171/755, datascience.stackexchange.com/q/93279/8560. $\endgroup$
    – D.W.
    Apr 20, 2021 at 17:36
  • $\begingroup$ @NikosM. I understand and found that VC(H1)=3 and VC(H2)=4. But how can I combine them ? $\endgroup$
    – user779537
    Apr 20, 2021 at 20:42


Your Answer

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