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 \0,1\^X we define h^(s) \0,1\^X X by h^(s)(w,x):= 1[h(w) = h(x)]. This idea can be extended to a set of functions, or hypothesis space H \0,1\^X by defining a similarity hypothesis space H^(s):= ^(s):hH\. We show that vc-dimension(H^(s)) (vc-dimension(H)).

Tasks

Reproductions