6.5 Sequence kernels

考虑拓展 \(K:\cal X\times X\to\mathbb{R}\) 到 \(\cal X\) 不是向量空间的情况，例如序列、图像等等。现在令 \(\cal X\) 为字符串的集合，对应的核称为序列核 sequence kernels；一种序列核的框架，称为 rational kernels，建立在称为加权转换器 weighted transducer 的自动机上

Weighted transducers

将序列映射到数字的普适方法，可以联想到沿着序列读入并开一个自动机；对于两个输入序列亦是类似；将两个序列视作字符串，分别来自两个有限字符集合 \(\Sigma, \Delta\)，并定义空字符 \(\epsilon\)（与字符串连接不变）便于匹配。定义加权转换器 weighted transducers：

Def. Weighted transducers
加权转换器 \(T\) 为一个 7 元组 \(T=(\Sigma, \Delta, Q, I, F, E, \rho)\)，其中：

\(\Sigma\) 为有限的输入字符集合
\(\Delta\) 为有限的输出字符集合
\(Q\) 为有限的状态集合
\(I\sube Q\) 为初始状态集合
\(F\sube Q\) 为接受状态集合
\(E\) 为状态转移 \(Q\times(\Sigma\cup\{\epsilon\})\times(\Delta\cup\{\epsilon\})\times\mathbb{R}\times Q\) 的可重集，记录每一个转移的前后状态、该转移的输入、输出字符和权值
\(\rho:F\to\mathbb{R}\) 为接收状态的权值

定义 \(T\) 的复杂度为其状态和转移的大小之和，记作 \(|T|\)

图示如下，分别用加粗、双线表示起始、接收状态，转移边用 \(\text{[input label]:[output label]/[weight]}\) 标识；接收状态用 \(\text{[state]/[weight]}\) 标识

对于一个加权转换器 \(T\) 的一条从起始状态到接收状态的路径 \(\pi\)（称为 accepting path），其输入 \(\text{input} _\pi\) 为沿途转移的输入字符的顺次连接、输出 \(\text{output} _\pi\) 为沿途转移的输出字符的顺次连接、权值 \(\text{value} _\pi\) 为沿途转移的权值的乘积再乘以接收状态的权值；
定义一个加权转换器 \(T\) 对应的映射 \(T:\Sigma ^ * \times \Delta ^ *\to\mathbb{R}\)：对于 \((x,y)\in\Sigma ^ * \times\Delta ^ *\)，\(T(x,y)\) 为所有从起始状态到接收状态的路径、满足其输入为 \(x\) 且输出为 \(y\)、的权值之和，即

\[\forall (x,y)\in\Sigma ^ * \times\Delta ^ *,\quad T(x,y)\triangleq \sum _{\begin{matrix}\text{accepting path }\pi \\ \text{ input} _{\pi}=x,\ \text{output} _{\pi}=y\end{matrix}} \text{value} _\pi \]

先考虑一个小细节：如果在某点存在 \((\epsilon:\epsilon/a),a\ne 0\) 的自环会如何呢？显然，任何经过该点的路径，都能在该自环上走任意次，且路径的输入输出不变；由于定义是对路径求和，因此有无穷多条满足 \((x,y)\) 的路径，从而 \(T(x,y)\) 无限大；因此通常我们令 \(\epsilon\) 自环的权值为 \(0\)
对于除自环外无环的 DAG，可以 \(O(|T|)\) 直接计算，后面会提供一种方法

Composition

Def. Composition 组合运算
两个加权转换器 \(T _1=(\Sigma, \Delta, Q _1, I _1, F _1, E _1, \rho _1), T _2 = (\Delta, \Omega, Q _2, I _2, F _2, E _2, \rho _2)\) 的 composition 组合运算，记为 \(T _1\circ T _2\)，为

\[\forall (x,y)\in \Sigma ^ * \times \Omega ^ *,\quad (T _1\circ T _2)(x,y)=\sum _{z\in\Delta ^ * }T _1(x,z)\cdot T _2(z,y) \]

我们有 \(O(|T _1||T _2|)\) 的算法构造一个新的 \(T _1\circ T _2\)，其实就是令 \(Q _1\times Q _2\) 为新的状态集合，并将转换 \((q _1, a,b,w _1, q _2)\in E _1,(q' _1,b,c,w _2,q' _2)\in E _2\) 合并成 \(((q _1, q' _1),a,c,w _1\cdot w _2,(q _2, q' _2))\) 加入 \(E\)
不过值得注意的是，如下图所示，这种方法构造出的转换器对于 \(z\) 用 \(\epsilon\) 匹配两边的情况，可能会存在多条 accepting path（因为 \(\epsilon\) 可以拆成任意个进行匹配，也就可能存在多种匹配方式，当然，\(\epsilon:\epsilon\) 权值都得是 \(0\)，才能保证这些路径的权值有界且都相同，这样的话其实后面讨论的多条路径，权值都是零，也无所谓几条了吧），但是由定义只有一个 \(z\)，会重复计算；
为了使得 \(\epsilon\) 路径只有一条，我们需要更具体的刻画。先考虑每一条路径，其上每一组匹配，都形如 \((a:x:x:y),(a:\epsilon:\epsilon:y),(a:\epsilon:\epsilon:\epsilon),(\epsilon:\epsilon:\epsilon:y)\) 四者之一，我们用将其重写为 \((a:x:x:y),(a:\epsilon 2:\epsilon 1:y),(a:\epsilon 2:\epsilon 2:\epsilon),(\epsilon:\epsilon 1:\epsilon 1:y)\)，也就是将 \(T _1\) 改造成 \(\widetilde{T} _1\)，使其均形如 \((x:\epsilon 2),(\epsilon:\epsilon 1)\)；对 \(T _2\) 改造成 \(\widetilde{T} _2\) 同理；
现在我们可以制造一个充当 filter 的转换器 \(F\)，插在 \(\widetilde{T} _1\circ F\circ\widetilde{T} _2\) 里，去掉一些多余的匹配；匹配的中间部分都形如 \((x:x),(\epsilon 2:\epsilon 1),(\epsilon 2:\epsilon 2),(\epsilon 1:\epsilon 1)\)，这些就是 \(F\) 的转移边
现在观察多出来的 \(\epsilon\) 路径是怎么来的，并且去重；对于该路径相邻两个 \((x:x)\) 之间的部分，如果同时存在 \((\epsilon 1:\epsilon 1),(\epsilon 2:\epsilon 2)\)，那么显然存在另一条更短的路径为 \((\epsilon 2:\epsilon 1)\)，我们总是取更短的；因此要么只有 \(\{(\epsilon 1:\epsilon 1),(\epsilon 2:\epsilon 1)\}\)，要么只有 \(\{(\epsilon 2:\epsilon 2),(\epsilon 2:\epsilon 1)\}\)；以 \(\{(\epsilon 1:\epsilon 1),(\epsilon 2:\epsilon 1)\}\) 为例，如果存在相邻两组为 \((\epsilon 1:\epsilon 1),(\epsilon 2:\epsilon 1)\)，那肯定存在另一条路径在这里为 \((\epsilon 2:\epsilon 1),(\epsilon 1:\epsilon 1)\)，我们取后者就行了；因此构造出 \(F\) 如图：

综上，求出 \(\widetilde{T} _1\circ F\circ\widetilde{T} _2\) 即可；这样的复杂度依然是 \(O(|T _1||T _2|)\)，因为 \(|F|\) 是固定的常数

Computation

接下来考虑计算 \(T(x,y)\) 的算法
首先我们假设 \(T\) 没有非零权值的 \(\epsilon:\epsilon\) 环，否则任何经过该环的权值都会变得无穷大；接下来，为 \(x\) 构造一个只有一条 accepting path、且其输入输出都为 \(x\)、其权值为 \(1\) 的转换器 \(T _x\)，显然它就是一条链，复杂度 \(O(|x|)\)；同理构造 \(T _y\)。
然后求出 \(U=T _x\circ T\circ T _y\)，复杂度为 \(O(|T||T _x||T _y|)\)。我们会发现，此时 \(U\) 是一个有向无环图，这是因为对于 \(T _x\circ T\) 的任何两个状态 \((q _1, q' _1),(q _2, q' _2)\)，状态的第一维关键字继承了原本 DAG 的偏序关系，因此 \(T _x\circ T\) 是 DAG，同理 \(U=T _x\circ T \circ T _y\) 也是 DAG
此时观察 \(U\) 的所有 accepting path，显然它们的输入都是 \(x\)、输出都是 \(y\)，因此只需要用 \(O(|U|)\) 计算做一次拓扑遍历求出所有 accepting path 的权值和，就是我们想要的 \(T(x,y)\)
由于 \(|T|\) 是一个不变的常数，因此计算 \(T(x,y)\) 的时空复杂度为 \(O(|x||y|)\)

Rational kernels

Def. Rational kernels
称映射 \(K:\Sigma ^ * \times \Sigma ^ * \to \mathbb{R}\) 为 rational kernel，若存在某个加权转换器 \(T\)，使得 \(K(x,y)=T(x,y)\)，也可以直接写成 \(K=T\)

Th. PDS rational kernels
定义加权转换器 \(T\) 的逆 \(T ^ {-1}\)，为将 \(T\) 的每一个转换的输入输出对调，从而有 \(T(x,y)=T ^{-1}(y,x)\)
则对于任意加权转换器 \(T\)，映射 \(K=T\circ T ^{-1}\) 是 PDS 核
有了这个保证，我们就能使用对 PDS 封闭的运算创造更多的序列核了

证明：
定义核序列 \((K _n) _{n\ge 0}\)，使得 \(K _n(x,y)=\sum _{|z|\le n}T(x, z) T ^{-1}(z,y)=\sum _{|z|\le n}T(x, z) T(y,z)\)
对于样本 \((x _1,\dotsb, x _m)\)，\(K _n\) 对应的核矩阵

\[\begin{aligned}{\bf K} _n &= [K _n(x _i, x _j)] _{(i,j)}=\begin{bmatrix}\Sigma _{|z|\le n}T(x _i, z)T(x _j,z)\end{bmatrix} _{(i,j)} \\ &= {\bf AA ^\top}\qquad; {\bf A}= \begin{bmatrix}T(x _i,z _j)\end{bmatrix} _{i\in[m],j\in[N]}\end{aligned} \]
从而 \({\bf c ^\top K} _n{\bf c=c ^\top AA ^\top c}\ge 0\)，\(K _n\) 为 PDS，序列极限 \(K\) 亦为 PDS

Counting transducers

一个 rational kernel 的应用，是构造计算 \((x,y)\) 同时具有某些相同模式的转换器；形式化地说，定义能被某个自动机识别的模式集合 \({\cal X}\)（可被正则表达式写出，比如 \(\Sigma ^ * (\Sigma+\epsilon) ^ * \Sigma ^ *\) 这种），记模式 \(z\in\cal X\) 在字符串 \(x\) 出现次数为 \(\text{count} _z(x)\)，则存在加权转换器 \(U\)，使得 \(U(x,y)=\sum _{z\in\cal X}\text{count} _z(x)\text{count} _z(y)w _z ^2\)，其中 \(w _z\) 为任意设定的权值
它的设计方式很简单，我们先构建如下的转换器 \(T _\text{count}\)，使得它只接受 \(\cal X\) 里的模式 \(z _1,\dotsb, z _n\)，则有

\[\forall x\in\Sigma ^ * ,z\in{\cal X},\quad T _\text{count}(x,z)=\text{count} _z(x) w _z \]

现在取 \(U=T _\text{count}\circ T ^ {-1} _\text{count}\)，有：

\[U(x,y)=\sum _{z\in\cal X} T(x,z)T(y,z)= \sum _{z\in\cal X}\text{count} _z(x)\text{count} _z(y)w _z ^2 \]

6.6 Approximate kernel feature maps

使用核方法做 SVM，求对偶问题需要 \(O(m ^2 C _K)\) 的时间复杂度，其中 \(C _K\) 是计算一次核函数的复杂度
求出问题后，做估计有两种方法，一种是 \(h(x)=\sum _{i=1} ^m\alpha _i K(x _i, x) +b\)，复杂度为 \(O(mC _K)\)；另一种方法是 \(h(x)={\bf w}\cdot\Phi(x)+b\)，复杂度为 \(O(\dim(\mathbb{H}))\)，后者不一定比前者优，但是我们可以用一种方法估计 \(\Psi\approx\Phi\)，即 \(\Psi(x)\cdot\Phi(y)\approx K(x,y)\)，使得前者的维度固定为某个 \(D\)
先给出定理：

Th. Bochner's theorem
局部紧集 \(\cal X\) 上的连续核 \(K(x,y)\)，若具有 “平移不变性”（称为平移不变核 shift-invariant kernel），即 \(K(x,y)=G(x-y)=G(y-x)\)，则 \(G\) 为正定函数（即 \(K\) 是 PDS 核），当且仅当 \(G\) 能傅里叶变换到一个 \(\cal X\) 上的非负度量 \(p\)，即：

\[p(\omega) = \int _{\cal X} G(x) e ^{-i\omega x} {\rm d}x \ge 0,\quad G(x)=\int _{\cal X} p(\omega) e ^{i\omega x}{\rm d}\omega \]

书上没有证明，按我的想法说明看看：
这个定理也就是说，\(G\) 的傅里叶变换 \(p(\omega)\ge 0\)
首先给出一个结论：实数域的正定可以等价推广到复数域，也就是说，假设 \(\bf K\) 使得 \(\forall {\bf c}\in\mathbb{R} ^{m\times 1},{\bf c ^\top Kc}\ge 0\)，等价于 \(\forall {\bf c}\in\mathbb{C} ^{m\times 1},{\bf c} ^ H {\bf Kc}\ge 0\)，其中 \({\bf c} ^ H\) 表示 \(\bf c\) 的共轭转置
它的证明很简单，若实数域成立，则 \({\bf c} ^ H {\bf Kc}=\sum _{j,k}\bar{c _j}c _k K _{jk}=\sum _{j,k}(x _j-iy _j)(x _k + iy _k)K _{jk}={\bf x ^\top K x + y ^\top K y} + i\cdot\sum _{j,k}(x _j y _k - x _k y _j) K _{jk}={\bf x ^\top K x + y ^\top K y}\ge 0\)；反过来显然成立，故两者等价
现在我们简单说明 \(K\) 满足复数域上的正定对称，等价于 \(G\) 的傅里叶变换非负
后推前，由 \(G(x)=\int p(\omega)e ^{i\omega x}{\rm d}\omega\)，可以证明每个 \(g(x)=e ^{i\omega x}\) 都是正定函数，这是因为 \(g(x)\) 的核矩阵 \({\bf K}=[e ^{i\omega (x _i-x _j)}] _{(i,j)}={\boldsymbol{\beta \beta}} ^H,{\boldsymbol{\beta}}=[e ^{i\omega x _i}] _{i}\)，于是 \(G(x)\) 作为它们的正加权和也是正定函数
前推后，固定 \(\omega\)，由 \(p(\omega)=\int G(x)e ^{-i\omega x}{\rm d}x=\int _x G(x-y _0)e ^{-i\omega (x -y _0)}{\rm d}(x - y _0)=f(y _0),\forall y _0\in\cal X\)，则 \(p(\omega)=f(y _0)\cdot 1 = f(y _0)\int _y{\rm d}y = \int _y f(y){\rm d}y=\int _y\int _x G(x-y)e ^{-i\omega (x-y)}{\rm d}x{\rm d} y\)，它的离散形式为 \(\sum _{i,j} G(x _i- x _j)e ^{-i\omega(x _i- x _j)}={\boldsymbol{\beta}} ^H{\bf K}{\boldsymbol{\beta}}\ge 0,{\boldsymbol{\beta}}\) 同上；所以粗糙地就有 \(p(\omega)\ge 0\) 啦

若 \(G(0)=\int p(\omega){\rm d}\omega=1\)，则 \(p\) 可以视作一个分布，此时可以通过采样进行估计
具体而言，由于 \(K,p\) 都是实函数，取实部分析：

\[\begin{aligned} K(x,y) &= \text{Re}[K(x,y)]=\int _{\cal X} p(\omega) \text{Re}[e ^{i\omega (x-y)}]{\rm d}\omega \\ &= \int _{\cal X} p(\omega) \cos(\omega x-\omega y){\rm d}\omega \\ &= \mathbb{E} _{\omega\sim p}\Big[ \big[\cos\omega x, \sin\omega x\big] ^\top \big[\cos\omega y, \sin\omega y\big] \Big] \\ &\approx \frac{1}{D}\sum _{i=1} ^{D}\big[\cos\omega _i x, \sin\omega _i x \big] ^\top \big[\cos\omega _i y, \sin\omega _i y \big] \\ &= \Psi(x)\cdot \Psi(y) \\ \implies \Psi(x) &= \Big[\cos\omega _1 x, \sin\omega _1 x,\dotsb,\cos\omega _D x, \sin\omega _D x \Big]'\in\mathbb{R} ^{2D} \end{aligned} \]

这就是估计方法
它具有概率上界，不过...先不写了