核方法

作者: 水之心 | 来源:发表于2018-08-23 19:36 被阅读1次

令 $\mathcal{I}$ 表示输入数据 $x$ 的数据空间, 被称为输入空间 (input space). $\phi$ 是一个映射, 令 $\mathcal{F} = \{\phi(x): x \in \mathcal{I} \}$ 表示特征空间 (feature space).

数据实例 $x$ 可以任意对象, 如文本, 序列, 图像, 字符串等;
对于给定的数据实例 $x$ , $\phi(x)$ 是一个向量, 被称为特征向量.

定义 $K: \mathcal{I \times I} → \mathbb{R}$ 是 $\mathcal{I}$ 上的核函数 为 $\mathcal{F}$ 上的内积运算, 即
$∀ x_i, x_j \in \mathcal{I}, \; K(x_i,x_j) = ⟨\phi(x_i),\phi(x_j)⟩$

令 $D= \{x_i\}_{i=1}^n \subset \mathcal{I}$ 为输入空间中包含 $n$ 个对象的数据集, 则将 $D$ 中的点对间的核函数 (亦称为相似度函数, 或核) 表示为一个 $n \times n$ 的核矩阵, 定义为
$\mathbf{K} = \begin{pmatrix} K(x_1,x_1) & K(x_1,x_2) & \cdots & K(x_1,x_n) \\ K(x_2,x_1) & K(x_2,x_2) & \cdots & K(x_2,x_n) \\ \vdots & \vdots & \ddots & \vdots\\ K(x_n,x_1) & K(x_n,x_2) & \cdots & K(x_n,x_n) \\ \end{pmatrix}$

核方法避免了显式地将输入空间中的每个点 $x$ 变换到特征空间中的映射点 $\phi(x)$ , 而是直接通过核矩阵来获取. 这样，所有的相关分析均可转移到对核矩阵的研究上来. 当然, 核矩阵也可以看作对应 $n$ 个输入点的完全图的带权邻接矩阵.

对于输入空间中的任一 $x \in \mathcal{I}$ , 都被映射到如下函数 (被称为再生核映射):
$\phi(x) = K(x,\cdot)$
其中 $\cdot$ 代表 $\mathcal{I}$ 中任一参数. 这意味着输入空间中的每一个对象 $x$ 都映射到一个特征点 $\phi(x)$ , 该特征点事实上是一个函数 $K(x,\cdot)$ , 代表了该点与输入空间 $\mathcal{I}$ 中其他点的相似度.

令
$\begin{aligned} \mathcal{F} &= \operatorname{span} \{K(x,⋅): x \in \mathcal{I}\}\\ &= \{ \mathbf{f} = f(\cdot) = \displaystyle\sum_{i=1}^m α_iK(x_i,⋅):m \in \mathbb{N}, α_i \in ℝ, \{x_1,x_2,\cdots,x_m \} ⊆ \mathcal{I} \} \end{aligned}$
代表能够由特征点的任意子集的线性组合得到的所有函数点或点的集合.

对于 $\mathbf{f,g} \in \mathcal{F}$ 为特征空间中任意两点:
$\mathbf{f} = \displaystyle\sum_{i=1}^{m_a} α_iK(x_i, ⋅), \mathbf{g} = \displaystyle\sum_{j=1}^{m_b} β_iK(x_j, ⋅)$
定义这两个点的内积为
$⟨\mathbf{f,g}⟩ = \displaystyle\sum_{i=1}^{m_a}\sum_{j=1}^{m_b}α_iβ_jK(x_i,x_j)$

易证 $\mathcal{F}$ 是希尔伯特空间, $\mathcal{F}$ 具有再生性质 (reproducing property), 即可以通过取 $\mathbf{f}$ 和 $\phi(x)$ 的内积来计算一个函数 $f(⋅)$ 在一个点 $x\in \mathcal{I}$ 上的值:
$⟨f(⋅),\phi(x)⟩ = \displaystyle\sum_{j=1}^{m_a} α_i K(x_i,x) = f(x)$
由此, $\mathcal{F}$ 也被称为再生希尔伯特空间.

再生核映射 $\phi$ 将输入空间映射到一个可能是无限维的特征空间中, 然而, 给定一个数据集 $D = \{x_i\}_{i=1}^n$ , 可以只计算 $D$ 中的点核, 从而得到一个有限维的映射, 即定义经验核映射 $\phi$ 如下:
$\phi(x) = \mathbf{K}^{-\frac{1}{2}}[K(x_1,x); K(x_2,x); \cdots; K(x_n,x)] \in \mathbb{R}^n$