The VC-Dimension of Similarity Hypotheses Spaces

Mark Herbster, Paul Rubenstein, James Townsend

Given a set $X$ and a function $h:X⟶\{0,1\}$ which labels each element of $X$ with either $0$ or $1$, we may define a function $h^{(s)}$ to measure the similarity of…