Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 2 / d

An embedding is determined by its chosen increasing sequence of positions. Accordingly, the all-subsequence embedding kernel $K(x,y)$ counts pairs of embeddings, one in $x$ and one in $y$, that spell the same subsequence. The two embeddings are distinguished even when they spell the same word as another pair. The empty word contributes exactly one pair.

Let $n=|x|$, $p=|y|$, and define $F(i,j)=K(x_1\cdots x_i,y_1\cdots y_j)$ for prefixes. When either prefix is empty, only the empty word has an embedding in both, soTo derive a dynamic programming recurrence, count pairs that do not use position $i$ of $x$ or do not use position $j$ of $y$. Inclusion-exclusion givesThe remaining pairs use both final positions. These positions must be the final letters of the common word, so they contribute nothing if $x_i\ne y_j$. If $x_i=y_j$, deleting those two final positions is a bijection to arbitrary embedding pairs on the two shorter prefixes, including their empty pair. Their contribution is therefore $F(i-1,j-1)$. HenceEquivalently, when the final symbols agree the recurrence simplifies to $F(i,j)=F(i-1,j)+F(i,j-1)$; when they differ, subtract the diagonal term. Fill the table in increasing prefix order and return $F(n,p)$. The boundary values and the disjoint counting argument prove correctness by induction on $i+j$.

A one-row implementation of this dynamic programming uses the saved old diagonal entry:The assignment to diagonal retains the value from the previous row before F[j] was overwritten. Swapping $x$ and $y$ if necessary minimizes the row length. Thus the time complexity is $O(|x||y|)$ arithmetic operations and the extra space complexity is $O(\min (|x|,|y|))$ integer cells. Empty inputs return one immediately.

These counts include multiplicity: for $x=y=aa$, the empty word contributes $1$, the word $a$ contributes $2\cdot 2=4$, and $aa$ contributes $1$, giving $K(aa,aa)=6$, not three. More generally, each result is at most $2^{n+p}$, since it counts some pairs of position subsets. Exact integers therefore require $O(n+p)$ bits; the stated quadratic bound is an arithmetic-operation bound, with a conservative $O(np(n+p))$ bound for elementary bit arithmetic.

The proposed positive-semidefinite kernel is valid: for each finite string only finitely many coordinates ${\varphi }_u(x)$ are nonzero, so $x\mapsto ({\varphi }_u(x){)}_{u\in {\Delta }^{\ast }}$ is a well-defined feature map into the inner product space of finitely supported coordinate families, and its inner product is exactly $K$.