Nystrom 方法 II

本文尝试说明核函数与特征映射之间的关系，并借此介绍 Nystrom 的核函数加速方法。

本文比前文增加的地方是改进了矩阵特征分解的方法描述，现在它更简洁易懂；增补了低秩表示方法的描述，现在它在逻辑上与 Nystrom 方法的衔接更加自然。

Nystrom 方法 II^[1]
- 核函数与特征映射^[2]
- 概率密度的经验近似^[3]
- 矩阵的特征分解^[4]
- 低秩表示^[5]
- Nystrom 方法^[6]

核函数与特征映射

输入向量经过 feature map 的映射成为特征，而特征之间的内积称为核函数

其中，，这说明特征维度可以无限多；，称为特征值；，代表一种特征映射，它将输入映射成一个值。不同的特征映射彼此具有耦合关系，作为特征映射的约束，一种典型的约束称为 p-正交（p-orthogonal）

其中，代表输入向量出现的概率函数，我们要求特征之间依概率正交。正交条件虽然严格，但由于概率密度函数的存在，我们不再需要“过度”关注那些小概率事件。另外，由以上两式，我们可以立即得到下式

上式反映了核函数与特征映射之间的关系。

概率密度的经验近似

由于输入向量的概率密度函数几乎不可知，因此我们可以采取经验原则使用平均分布对它进近似，即认为所有输入向量的出现与否都是“等可能”的

反映在 p-正交约束上，它近似为

核函数与特征映射之间的关系式近似为

其中，q 代表输入向量的采样数量。

矩阵的特征分解

接下来，我将不加证明地给出矩阵分解式，再建立矩阵分解与核函数特征映射之间的关系。之所以使用这么拧巴的逻辑，是因为我实在没想明白，要怎么从正方向把这个东西给推导出来，因此我现在只能认为这是个巧合。

首先，将矩阵分解式列写如下

其中，代表变换方阵；代表列向量组成的矩阵，且；为对角实矩阵。另外，我们认为的各列满足标准正交关系

下面让我们发挥想象力地开始类比，首先是整个矩阵

之后是该矩阵的每一列都代表一个特征

这样，我们就构建了矩阵的特征分解与核函数特征映射之间的关系。为了将映射关系进行量化，我们首先计算映射函数，即特征向量。计算过程主要利用到特征向量之间的正交关系，以及矩阵的单位正交性质。

之后计算特征值。先将核函数扩展成矩阵

将其代入矩阵分解式，有

至此，我们可以认为矩阵代表有限维度的核函数，向量组合代表特征映射向量

下面考虑一般输入向量的特征映射

其中，代表第个输入向量，代表第个特征。

低秩表示

接下来我们对 Nystrom 方法的核心，即低秩表示的原理进行解释。有了矩阵分解式打底，我们可以将核函数矩阵表示为简单形式

从上式可知，此矩阵的秩完全由对角矩阵控制。所谓低秩表示，即是认为该矩阵对角线上的元素从大到小进行排列，这个有序数列呈现快速收敛到的特性。因此，我们总可以使用前若干个特征值对它进行降维表示而不影响核函数的精度。

其中，代表选择其中的低秩成分

其中，和分别代表样本数量和低秩成分的数量，而代表选择该矩阵的前行和前列。接下来考虑下式

将它进行分解可得

由特征矩阵的标准正交特征可知总有下式成立

而它与原始核函数矩阵之间的差异可以表示为

其中，是指低秩部分对应的特征值和特征向量。

Nystrom 方法

Nystrom 方法采用核函数的低秩近似,将高维核函数分解成低秩部分与剩余部分。具体来说,将核函数矩阵进行特征分解,选取前个特征向量与特征值进行重构,作为低秩近似项。剩余部分作为高秩与低秩之差,称为剩余项。因此 ,Nystrom 方法可以被表示为:

其中代表前个特征向量组成的矩阵；代表对角矩阵,包含前个特征值; 代表剩余项。由于与可以通过核函数矩阵的 SVD 分解直接获得,因此 Nystrom 方法的核心在于剩余项的估计。

通常,我们可以采用下式对剩余项进行估计:

上式中,核函数矩阵可以通过输入向量的采样获得。然而,这样的估计方法存在明显的缺陷,即忽略了特征向量与特征值之外的信息,造成了信息损失。因此,在实际应用中,我们可以通过下式获得更精确的剩余项估计:

其中，代表特征值的修正项,通常可以通过最小二乘法等方法进行估计。具体来说,我们可以构造剩余项的线性方程组,再求解以使方程组残差最小。这样一来,我们不仅利用了前个特征向量与特征值,同时还充分利用了核函数矩阵的信息,从而获得更加精确的剩余项估计。

参考资料

[1]

Nystrom 方法 II: #nystrom-方法-ii

[2]

核函数与特征映射: #核函数与特征映射

[3]

概率密度的经验近似: #概率密度的经验近似

[4]

矩阵的特征分解: #矩阵的特征分解

[5]

低秩表示: #低秩表示

[6]

Nystrom 方法: #nystrom-方法