I'm trying to do the exercise in 16.1 in the book Understanding Machine Learning, Ben-David, et al. formulated as follows:

Consider the task of learning to find a sequence of characters ("signature") in a file that indicates whether it contains a virus or not and let $\mathcal{X}$ be the set of all finite strings over some alphabet set $\Sigma$, and let $\mathcal{X}_d$ be the set of all such strings of length at most $d$. The learning hypothesis class is $\mathcal{H}=\lbrace h_v: v\in\mathcal{X}_d\rbrace$, where, for a string $x\in\mathcal{X}$, $h_v(x)$ is $1$ iff $v$ is a substring of $x$ (and $h_v(x) = −1$ otherwise).

Let $s = |\mathcal{X}_d|$ and consider a mapping $\psi$ to a space $R^s$, so that each coordinate of $\psi (x)$ corresponds to some string $v$ and indicates whether $v$ is a substring of $x$ (that is, for every $x \in \mathcal{X}, \psi(x)$ is a vector in $\lbrace > 0,1\rbrace^{|\mathcal{X}_d|}$). Note that the dimension of this feature space is exponential in $d$.

Given that information, I need to show that every member of the class $\mathcal{H}$ can be realized by composing a linear classifier over $\psi (x)$, and, moreover, by such a halfspace whose norm is 1 and that attains a margin of 1.

However, I was confused over the $v$ in the definition of $\mathcal{H}=\lbrace h_v: v\in\mathcal{X}_d\rbrace$. My understanding is that this $v$ denotes any string $v\in\mathcal{X}_d$ not just some fixed string. Suppose my understanding is correct then denote by $v_1, v_2,..., v_s$ all strings in $\mathcal{X}_d$ and then we can define $\psi$ by

$$ \psi(x) = \begin{bmatrix} h_{v_1}(x) \\ h_{v_s}(x) \\ \vdots \\ h_{v_s}(x) \end{bmatrix}. $$

Thus we have $h_{v_i}(x)=\psi (x)_i$ (the i(th)-element of $\psi (x)$). But I don't see any the linear classifiers in this equation let alone the margin and the norm constraints?



Your Answer

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

Browse other questions tagged or ask your own question.