2
$\begingroup$

The question:

Let $\mathcal{S}$ be the set of strings of length at most $100$, drawn from a finite alphabet $A$; for any $s \in \mathcal{S}$, $s = a_1 , . . . , a_{100}$ where each $a_j \in A$. Let $\mathcal{K} : \mathcal{S} × \mathcal{S} \rightarrow \mathcal{R}$ be defined for $s_1 , s_2 \in \mathcal{S}$ by $\mathcal{K}(s_1, s_2)$ as: $\mathcal{K}(s_1, s_2)$ is the number of unique substrings that $s_1$ and $s_2$ have in common.
For example, $A = \{a, e, i, o, u\}, \ s_1 = aauuee, \ s_2 = auue$ implies that $\mathcal{K}(s_1 , s_2 ) = 9$ since the only common substrings are $a,\ u,\ e,\ uu,\ ue,\ uue,\ au,\ auu,\ auue$. I have to prove that $\mathcal{K}$ is a valid kernel.

I did the following:
We need a $\phi : \mathcal{S} → \mathcal{R}^{n}$ for some finite $n$ such that $\mathcal{K}(s_1 , s_2 ) = \phi^{T} (s_1 )\phi(s_2 )$. It is easy to suggest such a $\phi$ for $n = |S|$ $=$ number of possible substrings of size upto $100$ composed of characters from $A$. Specifically, $n= \sum_{j=1}^{100}|A|^{j}$ . We will also consider the set of these strings $\mathcal{S}$ sorted in alphabetical order so that we know what the $i^{th}$ string in it refers to.
$\phi(\mathcal{S}) \in \mathcal{R}^n$ such that the $\phi_i(s) = 1$ if an only if $i^{th}$ substring is contained in $s$ and $\phi_i (s) = 0$ otherwise.
Let $\delta(i, s) = 1$ if and only if the $i^{th}$ string of $\mathcal{S}$ is a substring of $s$ and $\delta(i, s) = 0$ otherwise. It is thereafter easy to verify that $\sum_i \phi^T (s_1 )\phi(s_2 ) = \sum_i \delta(i, s_1 )\delta(i, s_2 ) = \mathcal{K}(s_1 , s_2 )$. The existence of such a $\phi(.)$ proves that $\mathcal{K}(s_1 , s_2 )$ is a kernel.

But how to do this using Mercer's theorem and Gram matrix? How to prove for the positive-semidefinite Gram matrix, without finding the actual $\phi(.)$?

I asked the same question on Cross-Validated but I didn't get a response there.
Why isn't there a (kernel) tag on the main site of MSE? Is it not a part of mathematics? I realise that it has more to do with machine learning but ultimately it is an application of mathematics. I thought since MSE has more users, traffic and popularity, it might get answered here. But then there isn't an appropriate tag for this question.

$\endgroup$

You must log in to answer this question.

Browse other questions tagged .