<p>Consider the task of learning to find a sequence of characters (&quot;signature&quot;) in a file that indicates whether it contains a virus or not and let <span class="math-container">$\mathcal{X}$</span> be the set of all finite strings over some alphabet set <span class="math-container">$\Sigma$</span>, and let <span class="math-container">$\mathcal{X}_d$</span> be the set of all such strings of length at most <span class="math-container">$d$</span>. The learning hypothesis class is <span class="math-container">$\mathcal{H}=\lbrace h_v: v\in\mathcal{X}_d\rbrace$</span>, where, for a string <span class="math-container">$x\in\mathcal{X}$</span>, <span class="math-container">$h_v(x)$</span> is <span class="math-container">$1$</span> iff <span class="math-container">$v$</span> is a substring of <span class="math-container">$x$</span> (and <span class="math-container">$h_v(x) = −1$</span> otherwise).</p>
<p>Let <span class="math-container">$s = |\mathcal{X}_d|$</span> and consider a mapping <span class="math-container">$\psi$</span> to a space <span class="math-container">$\mathbb{R}^s$</span>, so that each coordinate of <span class="math-container">$\psi (x)$</span> corresponds to some string <span class="math-container">$v$</span> and indicates whether <span class="math-container">$v$</span> is a substring of <span class="math-container">$x$</span> (that is, for every <span class="math-container">$x \in \mathcal{X}, \psi(x)$</span> is a vector in <span class="math-container">$\lbrace 0,1\rbrace^{|\mathcal{X}_d|}$</span>). Note that the dimension of this feature space is exponential in <span class="math-container">$d$</span>.</p>
<p>Given that information, I need to show that every member of the class <span class="math-container">$\mathcal{H}$</span> can be realized by composing a linear classifier over <span class="math-container">$\psi (x)$</span>, and, moreover, by such a halfspace whose norm is 1 and that attains a margin of 1.</p>
<p>However, I was confused over the <span class="math-container">$v$</span> in the definition of <span class="math-container">$\mathcal{H}=\lbrace h_v: v\in\mathcal{X}_d\rbrace$</span>. My understanding is that this <span class="math-container">$v$</span> denotes any string <span class="math-container">$v\in\mathcal{X}_d$</span> not just some fixed string. Suppose my understanding is correct then denote by <span class="math-container">$v_1, v_2,..., v_s$</span> all strings in <span class="math-container">$\mathcal{X}_d$</span> and then we can define <span class="math-container">$\psi$</span> by</p>
<p><span class="math-container">$$
\psi(x) =
\begin{bmatrix}
h_{v_1}(x) \\
h_{v_s}(x) \\
\vdots \\
h_{v_s}(x)
\end{bmatrix}.
$$</span></p>
<p>Thus we have <span class="math-container">$h_{v_i}(x)=\psi (x)_i$</span> (the i(th)-element of <span class="math-container">$\psi (x)$</span>). But I don't see any the linear classifiers in this equation let alone the margin and the norm constraints?</p>

CC BY-SA 4.0
2023-11-28T10:30:50.930Z
"Let $s = |\mathcal{X}_d|$ and consider a mapping to a space $R^s$." what $R$ refer to? Do you mean $\mathbb{R}$?
Saginus
CC BY-SA 4.0
2023-11-28T10:42:45.437Z
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.
Saginus
CC BY-SA 4.0
2023-11-28T10:43:58.773Z
Do you have this problem in some resources so that I can understand it? It's sp confusing the way you posed the problem.
Saginus
CC BY-SA 4.0
2023-11-28T11:17:02.917Z
@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.
Tran Khanh
CC BY-SA 4.0
2023-11-28T11:18:38.193Z
You can find it [here](https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf), in section **16.2.1** Kernels as a Way to Express Prior Knowledge.
Tran Khanh
<machine-learning><svm><kernelization>
Find the SVM kernel in detecting if a substring in a given string
Tran Khanh
# Find the SVM kernel in detecting if a substring in a given string

(Asked by: username_0 on 2023-11-28)

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?

**Tags:** machine-learning, svm, kernelization
> **Comments:**
> **username_1**: "Let $s = |\mathcal{X}_d|$ and consider a mapping to a space $R^s$." what $R$ refer to? Do you mean $\mathbb{R}$?  
> **username_1**: 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.  
> **username_1**: Do you have this problem in some resources so that I can understand it? It's sp confusing the way you posed the problem.  
> **username_0**: @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.  
> **username_0**: You can find it [here](https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf), in section **16.2.1** Kernels as a Way to Express Prior Knowledge.  

---

## 0 answers

