机器学习中的核函数

港控/mmm° 2022-05-01 12:51 194阅读 0赞

本文参考:[blog.pluskid.org/?p=685][blog.pluskid.org_p_685]

核函数在SVM主要起到了两种作用

1.  将数据从低维映射到高维，将原本线性不可分的情况变成了线性可分
2.  降低计算级数

## 低维映射到高维 ##

其中第一点的核心思想用几何来展示如下：

比如将x1和x2的超平面 变为 ![a\_1X\_1 + a\_2X\_1^2 + a\_3 X\_2 + a\_4 X\_2^2 + a\_5 X\_1X\_2 + a\_6 = 0][a_1X_1 _ a_2X_1_2 _ a_3 X_2 _ a_4 X_2_2 _ a_5 X_1X_2 _ a_6 _ 0] 的高阶多项式函数。我们将映射函数设为 ![\\phi(\\cdot)][phi_cdot].

我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间（验算一下？），这个数目是呈爆炸性增长的，这给 ϕ(⋅) 的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了。所以就需要 Kernel 出马了。

## 降低计算复杂度 ##

**其中第一点在线性回归中使用高阶多项式就能做到，所以核函数真正最重要的是降低计算复杂度。**

所谓的核函数，其实是一种计算的技巧，所以又被称为 Kernel Trick 。

例如SVM中分类函数最终形式如下：

![f(x) = \\sum\_\{i=1\}^n\\alpha\_i y\_i \\langle x\_i, x\\rangle + b][f_x_ _ _sum_i_1_n_alpha_i y_i _langle x_i_ x_rangle _ b]

现在通过映射函数变为:

![f(x) = \\sum\_\{i=1\}^n\\alpha\_i y\_i \\langle \\phi(x\_i), \\phi(x)\\rangle + b][f_x_ _ _sum_i_1_n_alpha_i y_i _langle _phi_x_i_ _phi_x_rangle _ b]

其对偶问题：

![\\begin\{align\}  \\max\_\\alpha &\\sum\_\{i=1\}^n\\alpha\_i – \\frac\{1\}\{2\}\\sum\_\{i,j=1\}^n\\alpha\_i\\alpha\_jy\_iy\_j\\langle \\phi(x\_i),\\phi(x\_j)\\rangle \\\\  s.t., &\\alpha\_i\\geq 0, i=1,\\ldots,n \\\\  &\\sum\_\{i=1\}^n\\alpha\_iy\_i = 0  \\end\{align\}][begin_align_ _max_alpha _sum_i_1_n_alpha_i _ _frac_1_2_sum_i_j_1_n_alpha_i_alpha_jy_iy_j_langle _phi_x_i_phi_x_j_rangle _ s.t._ _alpha_i_geq 0_ i_1_ldots_n _ _sum_i_1_n_alpha_iy_i _ 0 _end_align]

如之前所提到，这是没有核函数的直接映射方式。这样的计算将会非常复杂。

设两个向量为![x\_1 = (\\eta\_1,\\eta\_2)^T][x_1 _ _eta_1_eta_2_T]和![x\_2=(\\xi\_1,\\xi\_2)^T][x_2_xi_1_xi_2_T]。

![\\left(\\langle x\_1, x\_2\\rangle + 1\\right)^2 = 2\\eta\_1\\xi\_1 + \\eta\_1^2\\xi\_1^2 + 2\\eta\_2\\xi\_2 + \\eta\_2^2\\xi\_2^2 + 2\\eta\_1\\eta\_2\\xi\_1\\xi\_2 + 1][left_langle x_1_ x_2_rangle _ 1_right_2 _ 2_eta_1_xi_1 _ _eta_1_2_xi_1_2 _ 2_eta_2_xi_2 _ _eta_2_2_xi_2_2 _ 2_eta_1_eta_2_xi_1_xi_2 _ 1]

**这个式子可以理解为先做内积再做映射。**

另外，我们又注意到：

![\\varphi(X\_1,X\_2)=(\\sqrt\{2\}X\_1,X\_1^2,\\sqrt\{2\}X\_2,X\_2^2,\\sqrt\{2\}X\_1X\_2,1)^T][varphi_X_1_X_2_sqrt_2_X_1_X_1_2_sqrt_2_X_2_X_2_2_sqrt_2_X_1X_2_1_T]

**完全等价于这个式子先做映射再作内积** ![<\\varphi(x\_1,x\_2),\\varphi(x\_2,x\_1)> = \\left(\\langle x\_1, x\_2\\rangle + 1\\right)^2][varphi_x_1_x_2_varphi_x_2_x_1_ _ _left_langle x_1_ x_2_rangle _ 1_right_2]。

所以我们可以得到新的对偶问题公式:

![\\begin\{align\}  \\max\_\\alpha &\\sum\_\{i=1\}^n\\alpha\_i – \\frac\{1\}\{2\}\\sum\_\{i,j=1\}^n\\alpha\_i\\alpha\_jy\_iy\_j \\color\{red\}\{\\kappa(x\_i, x\_j)\} \\\\  s.t., &\\alpha\_i\\geq 0, i=1,\\ldots,n \\\\  &\\sum\_\{i=1\}^n\\alpha\_iy\_i = 0  \\end\{align\}][begin_align_ _max_alpha _sum_i_1_n_alpha_i _ _frac_1_2_sum_i_j_1_n_alpha_i_alpha_jy_iy_j _color_red_kappa_x_i_ x_j_ _ s.t._ _alpha_i_geq 0_ i_1_ldots_n _ _sum_i_1_n_alpha_iy_i _ 0 _end_align]

这将会大大降低计算复杂度。同时将低位数据隐式映射到高维度。

这里还有其他简单例子如下：

我们现在考虑核函数K，即“内积平方”。

这个核函数对应着一个二维空间到三维空间的映射，它的表达式是：可以验证，

## 构造核函数 ##

当然，因为我们这里的例子非常简单，所以我可以手工构造出对应于 φ(⋅) 的核函数出来，如果对于任意一个映射，想要构造出对应的核函数就很困难了。

最理想的情况下

1.  我们希望知道数据的具体形状和分布
2.  从而得到一个刚好可以将数据映射成线性可分的 ϕ(⋅)
3.  然后通过这个 ϕ(⋅) 得出对应的 κ(⋅,⋅) 进行内积计算。

然而，第二步通常是非常困难甚至完全没法做的。不过，由于第一步也是几乎无法做到，因为对于任意的数据分析其形状找到合适的映射本身就不是什么容易的事情，所以，人们通常都是“胡乱”选择映射的，

**所以，根本没有必要精确地找出对应于映射的那个核函数，而只需要“胡乱”选择一个核函数即可。** 我们知道它对应了某个映射，虽然我们不知道这个映射具体是什么。由于我们的计算只需要核函数即可，所以我们也并不关心也没有必要求出所对应的映射的具体形式。

当然，说是“胡乱”选择，其实是夸张的说法，因为并不是任意的二元函数都可以作为核函数，所以除非某些特殊的应用中可能会构造一些特殊的核（例如用于文本分析的文本核，注意其实使用了 Kernel 进行计算之后，其实完全可以去掉原始空间是一个向量空间的假设了，只要核函数支持，原始数据可以是任意的“对象”——比如文本字符串），通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数），例如：

转载于:https://juejin.im/post/5cbc2d4c51882532ba3e98e7

[blog.pluskid.org_p_685]: https://link.juejin.im?target=http%3A%2F%2Fblog.pluskid.org%2F%3Fp%3D685
[a_1X_1 _ a_2X_1_2 _ a_3 X_2 _ a_4 X_2_2 _ a_5 X_1X_2 _ a_6 _ 0]: https://juejin.im/equation?tex=a_1X_1%20%2B%20a_2X_1%5E2%20%2B%20a_3%20X_2%20%2B%20a_4%20X_2%5E2%20%2B%20a_5%20X_1X_2%20%2B%20a_6%20%3D%200
[phi_cdot]: /images/20220119/f8c4cb562130409699f161765df8c80d.png
[f_x_ _ _sum_i_1_n_alpha_i y_i _langle x_i_ x_rangle _ b]: /images/20220119/eb72c8f26a754e388f4655f3293d0cc5.png
[f_x_ _ _sum_i_1_n_alpha_i y_i _langle _phi_x_i_ _phi_x_rangle _ b]: /images/20220119/701670d689f144a1933016e5f9a6072b.png
[begin_align_ _max_alpha _sum_i_1_n_alpha_i _ _frac_1_2_sum_i_j_1_n_alpha_i_alpha_jy_iy_j_langle _phi_x_i_phi_x_j_rangle _ s.t._ _alpha_i_geq 0_ i_1_ldots_n _ _sum_i_1_n_alpha_iy_i _ 0 _end_align]: /images/20220119/7e6aca3040044588b2b9d0e7105f244f.png
[x_1 _ _eta_1_eta_2_T]: https://juejin.im/equation?tex=x_1%20%3D%20%28%5Ceta_1%2C%5Ceta_2%29%5ET
[x_2_xi_1_xi_2_T]: /images/20220119/8a3aea206bd946e1a89ac2c5ae442e0a.png
[left_langle x_1_ x_2_rangle _ 1_right_2 _ 2_eta_1_xi_1 _ _eta_1_2_xi_1_2 _ 2_eta_2_xi_2 _ _eta_2_2_xi_2_2 _ 2_eta_1_eta_2_xi_1_xi_2 _ 1]: /images/20220119/6fdeee7e14074d18b1454c3b1b10167e.png
[varphi_X_1_X_2_sqrt_2_X_1_X_1_2_sqrt_2_X_2_X_2_2_sqrt_2_X_1X_2_1_T]: /images/20220119/69781c832ee441dab2d74a52987a13d1.png
[varphi_x_1_x_2_varphi_x_2_x_1_ _ _left_langle x_1_ x_2_rangle _ 1_right_2]: /images/20220119/9c9da1c1799049c1a763429360daf326.png
[begin_align_ _max_alpha _sum_i_1_n_alpha_i _ _frac_1_2_sum_i_j_1_n_alpha_i_alpha_jy_iy_j _color_red_kappa_x_i_ x_j_ _ s.t._ _alpha_i_geq 0_ i_1_ldots_n _ _sum_i_1_n_alpha_iy_i _ 0 _end_align]: /images/20220119/762c6f20bb3444aeb370819dee060f1c.png