CMSC 5724 Data Mining and Knowledge Discovery - Lecture 07
- Recall
- Motivation
- Theorem
- Kernel Function
- Polynomial Kernel
- Gaussian Kernel
- Perceptron
Recall
回想 linear classification 的核心问题：
令 P 作为 Rd 中的点，每个点有 label 1 或 label -1。linear classification 问题的目标就是确定是否有一个 d 维的分割平面
该分割平面将 P 中的点分割为两个 Labels。
如果分割平面存在，那么 P 可以说是线性可分的。
到目前为止，我们尚未对不可分离的数据集给予过多关注。 我们学到的所有技术都是针对 P 可线性分离的情况而设计的。接下来将学习一种称为内核方法的技术，该技术将数据集映射到另一个更高维度的空间。 通过适当地应用该方法，我们始终可以保证线性可分离性。
Motivation
下面这两个例子说明了如何将数据集映射以实现线性分离
Theorem
Increasing the Dimensionality Guarantees Linearly Separability
令 P 为在一维空间内任意的 n 个点的集合，它们有着 label 1 或 label 2。如果我们将每个点 x ∈ P 映射到一个在P’中 n 维的点 (1,x,x2^2,…,x^n-1)，那么，P’ 是在 P 中线性可分离的。
Proof
假设1：n 是一个奇数
假设2：label 是交叉的
因为 claim1 与 claim2 是对称的，所以只讨论 claim1
因此，如果我们将每个点 x ∈ P 转换为一个在 P‘ 中的点(1,x,x^2,…,x^n-1)，则 n 维点的结果集必然可以通过 n 维空间的原点。
Issues
证明中的转换解释了产生一个新的维数为 d’ = n 的空间。这产生两个问题：
- 如何找到一个较小的 d’ 的转换？
- 当 d’ 很大时，空间中的计算会非常高昂（即时枚举点的坐标也要话费 O(d’) 的时间）。是否有可能提高效率？
Kernel Function
Polynomial Kernel
c ≥ 1。
Example
转换后的空间的维度为 6。
一般来说，次数为 c 的多项式内核将 d w维空间转换为 C(d+c c) 维空间，也就意味着在高维空间使用的话会造成“维度灾难”。
Gaussian Kernel (RBF Kernel)
令 p 和 q 为 Rd 中的两个点。Gaussian Kernel 的形式为
对于 σ ＞ 0 称为 bandwidth，我们不讨论这个。dist(p, q) 为欧几里得距离，即
我们知道泰勒展开为
当 d = 1，
因此 φ(p) 有以下的坐标
Theorem
不管 σ 的选择如何，Gaussian Kernal 都能分离出任何有限的点集。
Perceptron
在转换后的空间 Rd’ 中，它应该被修改为
下面我们将展示如何应用到 Kernel function
对于点 p ∈ P，用 tp 表示 p 用于调整 w 的次数（如果 p 从未使用过，则 tp = 0）。当前 w 为
因此，通过为每个 p ∈ P 维持 tp，我们无需在转换的 d’ 维空间中计算任何点积。