# Find the SVM kernel in detecting if a substring in a given string

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?

• "Let $s = |\mathcal{X}_d|$ and consider a mapping to a space $R^s$." what $R$ refer to? Do you mean $\mathbb{R}$? Commented Nov 28, 2023 at 10:30
• 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. Commented Nov 28, 2023 at 10:42
• Do you have this problem in some resources so that I can understand it? It's sp confusing the way you posed the problem. Commented Nov 28, 2023 at 10:43
• @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. Commented Nov 28, 2023 at 11:17
• You can find it here, in section 16.2.1 Kernels as a Way to Express Prior Knowledge. Commented Nov 28, 2023 at 11:18