张春成
2023/03/02阅读:25主题:默认主题
Nystrom 方法 II
Nystrom 方法 II
本文尝试说明核函数与特征映射之间的关系,并借此介绍 Nystrom 的核函数加速方法。
本文比前文增加的地方是改进了矩阵特征分解的方法描述,现在它更简洁易懂;增补了低秩表示方法的描述,现在它在逻辑上与 Nystrom 方法的衔接更加自然。
-
Nystrom 方法 II[1] -
核函数与特征映射[2] -
概率密度的经验近似[3] -
矩阵的特征分解[4] -
低秩表示[5] -
Nystrom 方法[6]
-
核函数与特征映射
输入向量经过 feature map 的映射成为特征 ,而特征之间的内积称为核函数
其中, ,这说明特征维度可以无限多; ,称为特征值; ,代表一种特征映射,它将输入映射成一个值。 不同的特征映射彼此具有耦合关系,作为特征映射的约束,一种典型的约束称为 p-正交(p-orthogonal)
其中, 代表输入向量出现的概率函数,我们要求特征之间依概率正交。 正交条件虽然严格,但由于概率密度函数的存在,我们不再需要“过度”关注那些小概率事件。 另外,由以上两式,我们可以立即得到下式
上式反映了核函数与特征映射之间的关系。
概率密度的经验近似
由于输入向量的概率密度函数几乎不可知,因此我们可以采取经验原则使用平均分布对它进近似, 即认为所有输入向量的出现与否都是“等可能”的
反映在 p-正交约束上,它近似为
核函数与特征映射之间的关系式近似为
其中,q 代表输入向量的采样数量。
矩阵的特征分解
接下来,我将不加证明地给出矩阵分解式,再建立矩阵分解与核函数特征映射之间的关系。 之所以使用这么拧巴的逻辑,是因为我实在没想明白,要怎么从正方向把这个东西给推导出来, 因此我现在只能认为这是个巧合。
首先,将矩阵分解式列写如下
其中, 代表变换方阵; 代表列向量组成的矩阵,且 ; 为对角实矩阵。 另外,我们认为 的各列满足标准正交关系
下面让我们发挥想象力地开始类比,首先是整个矩阵
之后是该矩阵的每一列 都代表一个特征
这样,我们就构建了矩阵的特征分解与核函数特征映射之间的关系。 为了将映射关系进行量化,我们首先计算映射函数,即特征向量。 计算过程主要利用到特征向量之间的正交关系, 以及矩阵 的单位正交性质。
之后计算特征值。 先将核函数扩展成矩阵
将其代入矩阵分解式,有
至此,我们可以认为
下面考虑一般输入向量的特征映射
其中,
低秩表示
接下来我们对 Nystrom 方法的核心,即低秩表示的原理进行解释。有了矩阵分解式打底,我们可以将核函数矩阵表示为简单形式
从上式可知,此矩阵的秩完全由对角矩阵
其中,
其中,
将它进行分解可得
由特征矩阵
而它与原始核函数矩阵之间的差异可以表示为
其中,
Nystrom 方法

Nystrom 方法采用核函数的低秩近似,将高维核函数分解成低秩部分与剩余部分。 具体来说,将核函数矩阵进行特征分解,选取前
其中
通常,我们可以采用下式对剩余项进行估计:
上式中,核函数矩阵
其中,
参考资料
Nystrom 方法 II: #nystrom-方法-ii
[2]核函数与特征映射: #核函数与特征映射
[3]概率密度的经验近似: #概率密度的经验近似
[4]矩阵的特征分解: #矩阵的特征分解
[5]低秩表示: #低秩表示
[6]Nystrom 方法: #nystrom-方法
分类:
后端标签:
后端作者介绍