[白话解析] 深入浅出支持向量机(SVM)之核函数
[白话解析] 深入浅出支持向量机(SVM)之核函数
0x00 摘要
本文在少用数学公式的情况下，尽量仅依靠感性直觉的思考来讲解支持向量机中的核函数概念，并且给大家虚构了一个水浒传的例子来做进一步的通俗解释。
0x01 问题
在学习核函数的时候，我一直有几个很好奇的问题。
Why 为什么线性可分很重要?
Why 为什么低维数据升级到高维数据之后，就可以把低维度数据线性可分?
What 什么是核函数，其作用是什么?
How 如何能够找到核函数?
不知道大家是否和我一样有这些疑问，在后文中， 我将通过逐步的学习梳理为大家讲解这些问题。
0x02 相关概念 & 梳理过程
1. 线性分类的意义
分类器：分类器就是给定一个样本的数据，判定这个样本属于哪个类别的算法。
特征：在分类问题中，输入到分类器中的数据叫做特征。
线性分类器：线性分类器是分类器中的一种，就是判定分类结果的根据是通过特征的线性组合得到的，不能通过特征的非线性运算结果作为判定根据。比如：
- 一个点可以把一条一维直线分成两部分。
- 一条直线可以把二维平面分成两部分。
- 一个平面可以把三维空间分成两部分。
非线性分类器：就是用非线性运算结果作为判定根据。比如二维空间，一个圆可以进行非线性分割，把空间分成内部，外部两部分。
为什么需要线性分开呢？因为：
- 线性分开简单，性质很容易研究透彻；线性分开只要一条直线或一个平面之类，是曲线中最简单形式。而非线性分开的情况太多。仅就二维空间而言，就存在曲线、折线、双曲线、圆锥曲线、波浪线，以及毫无规律的各种其他曲线，没法进行统一处理。
- 线性分开推广能力强，无需建立其他模型。非线性分类很多时候都是针对具体问题来研究具体曲线模型，无法很好的推广。
这样就回答了我们第一个问题： 1. Why 为什么线性可分很重要
2. Cover定理
回忆我们的问题 2. Why：为什么低维数据升级到高维数据之后，就可以把低维度数据线性可分?
在提升维度后，原本非线性的数据点变得线性可分，这在数学上是有严格证明的，即Cover定理。我们这里就把Cover定理当公理用。
Cover定理可以定性地描述为：将复杂的模式分类问题非线性地投射到高维空间将比投射到低维空间更可能是线性可分的，当空间的维数D越大时，在该空间的N个数据点间的线性可分的概率就越大。
或者再通俗的说，这个定理描述的是 线性可分的概率，如果能把数据从低维空间映射到高维空间，我们就很可能在高维空间把数据做线性可分。对于在N维空间中线性不可分的数据，在N+1维以上的空间会有更大可能变成线性可分的。
所以人们就努力的寻找一种映射，这映射能将样本从原始空间(低维数据)转变到高维特征空间，从而把低维空间中线性不可分的两类点变成线性可分的。这种映射?(X) 又可称为“特征构建”，映射后的向量可称之为“特征向量”。比如
向量
X = [1, x1, x2]
构建映射
?(X) = ?( [1, x1, x2] ) = [1, x1, x2, x1^2， x2^2， x1.x2]
这样，Cover定理就回答了我们第二个问题，我们不去具体研究它的数学论证，就把它当作公理用。
3. 向量内积的几何意义
内积（点乘）的几何意义包括：
- 表征或计算两个向量之间的夹角
- b向量在a向量方向上的投影
所以，内积是一种在某维空间里面度量其数据相似度一种手段，就是在该空间内两个向量的关系。比如两个数据点之间的距离和角度。
分类需要内积是因为内积的正负代表了数据点是位于分类边界的正方向还是负方向，从而实现分类。
在高维空间，我们可以用向量内积来做线性分类。
4. 高维空间计算的复杂性
映射可以看作是一种拉伸，把低维数据拉伸到了高维。虽然现在我们到了高维空间号称线性可分，但是有几个困难：
- 不知道什么样的映射函数是完美的。
- 难以在各种映射函数中找到一个合适的。
- 高维空间计算量比较大。这样就会产生维灾难，计算内积是不现实的。
幸运的是，在计算中发现，我们需要的只是两个向量在新的映射空间中的内积结果，而映射函数到底是怎么样的其实并不需要知道。于是这样就引入了核函数的概念。
核函数事先在低维上计算，而将实质上的分类效果表现在了高维上，也就是
包含映射，内积，相似度的逻辑。
- 消除掉把低维向量往高维映射的过程。
避免了直接在高维空间内的复杂计算。
即核函数除了能够完成特征映射，而且还能把特征映射之后的内积结果直接返回。即把高维空间得内积运算转化为低维空间的核函数计算。
注意，核函数只是将完全不可分问题，转换为可分或达到近似可分的状态。
5. 核函数（kernel function）定义
关于我们第三个问题 What 什么是核函数，其作用是什么?，现在解答如下。
核函数是这样的一种函数：
仍然以二维空间为例，假设对于变量x和y，将其映射到新空间的映射函数为φ，则在新空间中，二者分别对应φ(x)和φ(y)，他们的内积则为<φ(x),φ(y)>。
我们令函数Kernel(x,y)=<φ(x),φ(y)>=k(x,y)，
可以看出，函数Kernel(x,y)是一个关于x和y的函数！而与φ无关！这是一个多么好的性质！我们再也不用管φ具体是什么映射关系了，只需要最后计算Kernel(x,y)就可以得到他们在高维空间中的内积。
我们则称Κ(x,y)为核函数，φ(x)为映射函数。
下面举出三个网上的好例子:
令 x = (x1, x2, x3, x4); y = (y1, y2, y3, y4)；
令 f(x) = (x1. x1, x1.x2, x1.x3, x1.x4, x2.x1, x2.x2, x2.x3, x2.x4, x3.x1, x3.x2, x3.x3, x3.x4, x4.x1, x4.x2, x4.x3, x4.x4); f(y)亦然；
这样就实现了四维到更高维度的转换。让我们带几个简单的数字进去看看是个什么效果：
x = (1, 2, 3, 4); y = (5, 6, 7, 8). 那么：
f(x) = ( 1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16) ;
f(y) = (25, 30, 35, 40, 30, 36, 42, 48, 35, 42, 49, 56, 40, 48, 56, 64) ;
<f(x), f(y)> = 25+60+105+160+60+144+252+384+105+252+441+672+160+384+672+1024
= 4900.如果我们用核函数呢？
K(x, y) = (x1.y1 + x2.y2 + x3.y3 + x4.y4) ^2= (5+12+21+32)^2 = 70^2 = 4900.
所以核函数kernel其实就是帮我们省去在高维空间里进行繁琐计算的“简便运算法”。
另外一个例子
“你在你的一生中可能会经历很多变故，可能会变成完全不同的另一个人，但是这个世界上只有一个你，我要怎样才能把不同的“你”分开呢？最直观的方法就是增加“时间”这个维度，虽然这个地球上只有一个你，这个你是不可分割的，但是“昨天在中国的你”和“今天在美国的你”在时间+空间这个维度却是可以被分割的。”
最后一个例子
假设我们的任务是要预测那些微博可以上微博热搜榜。有两个离散特征，一个代表某个微博里有 “鹿晗”，一个代表某个微博里有 “关晓彤”。
两个特征单独看热度都一般，此时我们用二阶多项式核方法：
\[K(鹿晗，关晓彤) = <鹿晗，关晓彤>^2\]
这个核函数可以把二维空间投射到三维空间，展开之后是：
\[K(鹿晗，关晓彤) = <鹿晗，关晓彤>^2 = (鹿晗^2, \sqrt{2} 鹿晗 . 关晓彤, 关晓彤^2)\]这样就把二维特征变成了三维，多了一维 ”鹿晗 x 关晓彤 “，代表着某条微博里鹿晗和关晓彤同时出现。
结果大家都知道了，鹿晗关晓彤同时出现的那条微博超级火，把新浪服务器都挤爆了。
我们大致能够得到核函数如下性质：
- 核函数给出了任意两个样本之间关系的度量，比如相似度。
- 每一个能被叫做核函数的函数，里面都藏着一个对应拉伸的函数。这些核函数的命名通常也跟如何做拉伸变换有关系。
- 核函数和映射本身没有直接关系。选哪个核函数，实际上就是在选择用哪种方法映射。通过核函数，我们就能跳过映射的过程。
- 我们只需要核函数，而不需要那个映射，也无法显式的写出那个映射。
- 选择核函数就是把原始数据集上下左右前后拉扯揉捏，直到你一刀下去正好把所有的 0 分到一边，所有的 1 分到另一边。这个上下左右前后拉扯揉捏的过程就是kernel.
6. Mercer定理
核函数使得计算一对向量的核函数等价与在变换后的空间中计算这对向量的内积。
但是接下来就是我们第四个问题 How 如何能够找到核函数?，
这个就是Mercer定理能完成的。Mercer定理也是严格证明过的数学定理，我们也把他当公理用。
Mercer定理的大致内容是：任何半正定对称函数都可以作为核函数。
正定性使得函数极限方向唯一且大于等于零，同时正定性产生的优化问题都是有良好凸优化性质，从而把原始空间的度量概念能移植到特征空间(融入了角和内积)中去。
数学家在理论指导下通过各种实验找出核函数，然后看看具体效果，如果效果好，就正式发布确认这种核函数。有点类似由果推因。
0x03 梁山好汉如何看待核函数
能够让人们理解概念最好的方式就是比喻/举例子。下面让我们用水浒传的故事来给大家举例说明核函数。
话说宋江吴用两个神棍利用石碑来忽悠梁山众好汉，搞出了英雄排座次，具体如下：
第七十一回 忠义堂石碣受天文 梁山泊英雄排座次
宋江先说要开大会，以此来作秀。
今者一百八人皆在面前聚会，端的古往今来，实为罕有。从前 兵刃到处，杀害生灵，无可禳谢。我心中欲建一罗天大醮，报答天地神明眷佑之恩
这就是要开始玩把戏了
是夜三更时候，只听得天上一声响，如裂帛相似，正是西北乾方天门上。众人 看时，直竖金盘：两头尖，中间阔，又唤做天门开，又唤做天眼开，里面毫光射人 眼目，霞彩缭绕，从中间卷出一块火来，如栲栳之形，直滚下虚皇坛来。那团火绕 坛滚了一遭，竟钻入正南地下去了。此时天眼已合，众道士下坛来，宋江随即叫人 将铁锹锄头掘开泥土，根寻火块。那地下掘不到三尺深浅，只见一个石碣，正面两 侧，各有天书文字。有诗为证： 忠义英雄迥结台，感通上帝亦奇哉! 人间善恶皆招报，天眼何时不大开!
取出事先准备好的石碑
当下宋江且教化纸满散。平明，斋众道士，各赠与金帛之物，以充衬资。方才 取过石碣看时，上面乃是龙章凤篆蝌蚪之书，人皆不识。众道士内有一人姓何，法讳玄通，对宋江说道：“小道家间祖上留下一册文书，专能辨验天书，那上面自古 都是蝌蚪文字，以此贫道善能辨认，译将出来，便知端的。”宋江听了大喜，连忙 捧过石碣，教何道士看了，良久说道：“此石都是义士大名镌在上面：侧首一边是 ‘替天行道’四字，一边是‘忠义双全’四字；顶上皆有星辰南北二斗；下面却是 尊号。若不见责，当以从头一一敷宣。”宋江道：“幸得高士指迷，缘分不浅，若 蒙见教，实感大德。唯恐上天见责之言，请勿藏匿，万望尽情剖露，休遗片言。” 宋江唤过圣手书生萧让，用黄纸誊写。何道士乃言：“前面有天书三十六行，皆是 天罡星；背后也有天书七十二行，皆是地煞星，下面注着众义士的姓名。”观看良 久，教萧让从头至后，尽数抄誊。
于是宋江假借上天来做了权利分配
宋江 与众头领道：“鄙猥小吏，原来上应星魁，众多弟兄也原来都是一会之人。上天显 应，合当聚义。今已数足，上苍分定位数，为大小二等。天罡、地煞星辰，都已分 定次序，众头领各守其位，各休争执，不可逆了天言。”众人皆道：“天地之意， 物理数定，谁敢违拗？”
众好汉中，有明白人就假装信了，有糊涂人就信以为真。但是有死心眼的比如 没面目焦挺想不通，就去找 打虎将李忠问问究竟。
焦挺：“李忠哥哥，小弟一事不明。我这身手你也知道，李逵那样的我一个人能打两个。可是为啥他就是 天杀星黑旋风李逵？我就是地恶星没面目焦挺，到底是根据啥计算出这个座次的?“。
李忠心中暗道，你个棒槌，表面上还得微笑道：
“兄弟。这个公明哥哥用的是特征映射啊。就是把每个人的信息映射到天上去，让上苍安排具体座次。你在地下是三维空间，天上可是N维空间呀。比如你在地上吧，你的低维信息就是：名称，籍贯，身手，出身等等。映射到上苍，那就是高维信息，比如：星宿具体排列顺序，星宿的形状，和黄道的位置，和太阴星的位置，加上四象八卦六壬等“，最后综合考虑得出了你的排名。
焦挺一瞪眼睛："那么多高维信息，我咋计算。能不能说人话，不然我认得哥哥，我手里的杆棒认不得哥哥"。
李忠忙陪笑到:
”兄弟，这个映射和高维计算问题太麻烦，我们在三维空间内可以用核函数直接来计算出结果，就不用映射和高维计算了。这个核函数考虑的就是：
第一条依据：根据名望来排，比如世系身份的高低/入伙梁山之前的身份高低。
第二条依据：公明哥哥的嫡系力量，公明哥哥根据个人的喜欢程度，以及与公明哥哥的亲疏程度。
第三条依据：武艺高低。
现在你明白了嘛?“
焦挺恍然大悟："李忠哥哥你是老江湖啊，来，咱俩吃酒去......"