支持向量机导论3: 核函数特征空间

Chapter 3: 核函数特征空间(Kernel-Induced Feature Spaces)

现实世界复杂的应用需要有比线性函数更富有表达能力的假设空间. 核表示(Kernel representations)方法提供了一条解决途径, 即将数据映射到高维空间来增加线性学习器的计算能力. 线性学习器对偶空间的表达方式使得这个步骤的隐式操作成为可能. 本章的目的就是展示如何映射到高维空间使得线性分类更容易.

3.1 特征空间中的学习(Learning in Feature Space)

需要学习的目标函数的复杂程度取决于它的表示方式. 因此, 在机器学习中一个普通的预处理策略包括改变数据的表达形式: \({\bf{x}} = \left( {{x_1},…,{x_n}} \right) \to \phi \left( {\bf{x}} \right) = \left( {{\phi _1}({\bf{x}}),…,{\phi _N}({\bf{x}})} \right)\). 这个步骤等价于将输入空间\(X\)映射到一个新的空间, \(F = \left( {\phi ({\bf{x}})|{\bf{x}} \in X} \right)\).

将数据简单映射到另一个空间能够很好地简化任务. 描述数据的量, 通常称为特征(features), 而原始的量有时称为属性(attributes). 选择最合适表达式的任务称为特征选择(feature selection). 空间\(X\)是指input空间, 而\(F = \left( {\phi ({\bf{x}})|{\bf{x}} \in X} \right)\)则称为feature空间.

维数简约: 寻找包含了原始属性中必要信息的最小特征集.

\({\bf{x}} = \left( {{x_1},…,{x_n}} \right) \to \phi \left( {\bf{x}} \right) = \left( {{\phi _1}({\bf{x}}),…,{\phi _d}({\bf{x}})} \right)\begin{array}{*{20}{c}}   {}  \end{array}d < n\), 这对计算和泛化性能都有益.

计算问题不是因特征空间太大而导致的唯一问题, 另一个问题是学习器的泛化能力. 使用过大的特征及会引起过拟合问题. 这就是维数简约技术受到重视的原因. 然而, 以后对泛化性的深入理解表明, 甚至可以使用无限维的特征空间. 泛化性问题可以通过使用在这个理解基础上的学习器来避免, 计算问题也可以通过下面描述的隐式映射来避免.

3.2 到特征空间的隐式映射(The Implicit Mapping into Feature Space)

建立非线性学习器分为两步: 首先使用一个非线性映射将数据变换到一个特征空间\(F\), 然后在这个特征空间使用线性学习器分类.

线性学习器的一个重要性质是可以表达为对偶形式(dual representation). 对偶表示的一个重要结果是转换后的特征空间维数不再影响计算.

核函数方法就是把上面的两步融合到一起建立一个非线性的学习器. 核是一个函数\({\bf{K}}\), 对所有\({\bf{x}},{\bf{z}} \in X\), 满足\(K\left( {{\bf{x}},{\bf{z}}} \right) = \left\langle {\phi \left( {\bf{x}} \right),\phi \left( {\bf{z}} \right)} \right\rangle \), 这里\(\phi \)是从\(X\)到(内积)特征空间\(F\)的映射. 核的使用使得数据隐式表达为特征空间, 并在其中训练一个线性学习器成为可能, 从而越过本来需要的计算特征映射的问题. 关于训练样例的唯一信息是它们在特征空间的Gram矩阵. 这个矩阵又称为核矩阵. 这里用符号\({\bf{K}}\)表示. 这个方法的关键是找到一个可以高效计算的核函数. 一旦有了这个函数, 决策规则可以通过对核的\(l\)次计算来得到:\[f({\bf{x}}) = \sum\limits_{i = 1}^l {{\alpha _i}{y_i}{\bf{K}}({{\bf{x}}_i},{\bf{x}})}  + b\]

某个矩阵\({\bf{A}}\)通过任意固定的线性变换\({\bf{x}} \to {\bf{Ax}}\)进行特征映射. 这种情况下的核函数如下:

\(K\left( {{\bf{x}},{\bf{z}}} \right) = \left\langle {{\bf{Ax}},{\bf{Az}}} \right\rangle  = {\bf{x’A'Az}} = {\bf{x’{\rm B}z}}\). 这里\({\bf{{\rm B}}} = {\bf{A’A}}\)是一个平方对称的半正定矩阵.

3.3 构造核函数(Making Kernels)

Kernels function必须是对称的: \({\bf{K}}\left( {{\bf{x}},{\bf{z}}} \right) = \left\langle {\phi \left( {\bf{x}} \right) \cdot \phi \left( {\bf{z}} \right)} \right\rangle  = \left\langle {\phi \left( {\bf{z}} \right) \cdot \phi \left( {\bf{x}} \right)} \right\rangle  = {\bf{K}}\left( {{\bf{z}},{\bf{x}}} \right)\)然而, 这些条件对于保证特征空间的存在不是充分的. 下面引出Mercer定理.

3.3.1 核函数的性质(Characterization of Kernels)

\({\bf{K}}\left( {{\bf{x}},{\bf{z}}} \right)\)是核函数的充分必要条件是矩阵\({\bf{K}}{\rm{ = (}}{\bf{K}}\left( {{{\bf{x}}_i},{{\bf{x}}_j}} \right))_{i,j = 1}^n\)是半正定(positive semi-definite), 即特征值非负.

在希尔伯特空间中进行推广, 得到Mercer定理(Mercer’s Theorem).

半正定(positive semi-definite)

注: 希尔伯特(Hilbert)空间是N维欧几里德空间的扩展.

3.3.2 从核函数中构造核函数(Making Kernels from Kernels)

确定一个对称函数是不是核函数的关键是看这个函数在任意有限点集上定义的矩阵是不是半正定. 核函数满足一定的闭性质, 它允许简单的构件块来创建复杂的核.

3.3.3 从特征中构造核函数(Making Kernels from Features)

另一个得到核的方式是从特征开始, 通过计算内积得到. 这种情况下, 不需要检查半正定性, 它自然遵循了内积的定义.

支持向量机导论3: 核函数特征空间》上有 1 条评论

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>