核函数(Kernels)
考虑我们最初在 "线性回归" 中提出的问题, 特征是房子的面积 x, 这里的 x 是实数, 结果 y 是房子的价格.
假设我们从样本点的分布中看到 x 和 y 符合 3 次曲线, 那么我们希望使用 x 的三次多项式来逼近这些样本点.
那么首先需要将特征 x 扩展到三维, 然后寻找特征和结果之间的模型. 我们将这种特征变换称作特征映射(feature mapping). 映射函数称作, 在这个例子中
我们希望将得到的特征映射后的特征应用于 SVM 分类, 而不是最初的特征. 这样, 我们需要将前面 公式中的内积从, 映射到.
至于为什么需要映射后的特征而不是最初的特征来参与计算, 上面提到的 (为了更好地拟合) 是其中一个原因, 另外的一个重要原因是样例可能存在线性不可分的情况, 而将特征映射到高维空间后, 往往就可分了.(在《数据挖掘导论》Pang-Ning Tan 等人著的《支持向量机》那一章有个很好的例子说明)
将核函数形式化定义, 如果原始特征内积是 , 映射后为 , 那么定义核函数(Kernel) 为
到这里, 我们可以得出结论, 如果要实现该节开头的效果, 只需先计算 , 然后计算 即可, 然而这种计算方式是非常低效的.
比如最初的特征是 n 维的, 我们将其映射到
维, 然后再计算, 这样需要
的时间. 那么我们能不能想办法减少计算时间呢?
先看一个例子, 假设 x 和 z 都是 n 维的,
展开后, 得
这个时候发现我们可以只计算原始特征 x 和 z 内积的平方(时间复杂度是 O(n)), 就等价与计算映射后特征的内积. 也就是说我们不需要花 时间了.
现在看一下映射函数(n=3 时), 根据上面的公式, 得到
也就是说核函数
只能在选择这样的
作为映射函数时才能够等价于映射后特征的内积.
再看一个核函数
对应的映射函数 (n=3 时) 是
更一般地, 核函数 对应的映射后特征维度为.
由于计算的是内积, 我们可以想到 IR 中的余弦相似度, 如果 x 和 z 向量夹角越小, 那么核函数值越大, 反之, 越小. 因此, 核函数值是 和 的相似度.
再看另外一个核函数
这时, 如果 x 和 z 很相近(
), 那么核函数值为 1, 如果 x 和 z 相差很大(
), 那么核函数值约等于 0.
由于这个函数类似于高斯分布, 因此称为高斯核函数, 也叫做径向基函数 (Radial Basis Function 简称 RBF). 它能够把原始特征映射到无穷维.
既然高斯核函数能够比较 x 和 z 的相似度, 并映射到 0 到 1, 回想 logistic 回归, sigmoid 函数可以, 因此还有 sigmoid 核函数等等.
下面有张图说明在低维线性不可分时, 映射到高维后就可分了, 使用高斯核函数.
来源: https://yq.aliyun.com/articles/411500