The VC-Dimension of Similarity Hypotheses Spaces

Abstract

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 pairs of points in $X$ according to $h$. Specifically, for $h\in \{0,1{\}}^X$ we define $h^{(s)}\in \{0,1{\}}^{X\times X}$ by $h^{(s)}(w,x):=1[h(w)=h(x)]$. This idea can be extended to a set of functions, or hypothesis space $\mathcal{H}\subseteq \{0,1{\}}^X$ by defining a similarity hypothesis space ${\mathcal{H}}^{(s)}:=\{h^{(s)}:h\in \mathcal{H}\}$. We show that $vc-dimension({\mathcal{H}}^{(s)})\in \Theta (vc-dimension(\mathcal{H}))$.

6 pages

References in corpus (1)

• Online Similarity Prediction of Networked Data from Known and Unknown Graphs