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

Nystrom 方法采用核函数的低秩近似,将高维核函数分解成低秩部分与剩余部分。 具体来说,将核函数矩阵进行特征分解,选取前
其中
通常,我们可以采用下式对剩余项进行估计:
上式中,核函数矩阵
其中,
分类:
后端标签:
后端作者介绍