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 $\mathbb{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?

  • $\begingroup$ "Let $s = |\mathcal{X}_d|$ and consider a mapping to a space $R^s$." what $R$ refer to? Do you mean $\mathbb{R}$? $\endgroup$
    – ayaxxx
    Commented Nov 28, 2023 at 10:30
  • $\begingroup$ Reading the first part also lead to some confusion. The way I understand your problem an to connect with having a virus or not makes me see $\mathcal{X}_d$ as the set of viruses (strings) of length at most $d$, where $d$ is the maximal length a virus can take. $\endgroup$
    – ayaxxx
    Commented Nov 28, 2023 at 10:42
  • $\begingroup$ Do you have this problem in some resources so that I can understand it? It's sp confusing the way you posed the problem. $\endgroup$
    – ayaxxx
    Commented Nov 28, 2023 at 10:43
  • $\begingroup$ @Ayoubayjx, that's a typo, yes $\mathbb{R}$ is correct. Based on the paragraph, I can see that the $\mathcal{X}_d$ is some restricted domain space (that is it contains all strings of length $\le d$), in which some strings contain virus (i.e. those who contain a sequence characterizes the virus), but some do not. $\endgroup$
    – Tran Khanh
    Commented Nov 28, 2023 at 11:17
  • $\begingroup$ You can find it here, in section 16.2.1 Kernels as a Way to Express Prior Knowledge. $\endgroup$
    – Tran Khanh
    Commented Nov 28, 2023 at 11:18


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.