Python · SVM（四）· SMO 算法 - 知乎专栏
{"debug":false,"apiRoot":"","paySDK":"/api/js","wechatConfigAPI":"/api/wechat/jssdkconfig","name":"production","instance":"column","tokens":{"X-XSRF-TOKEN":null,"X-UDID":null,"Authorization":"oauth c3cef7c66aa9e6a1e3160e20"}}
{"database":{"Post":{"":{"title":"Python · SVM（四）· SMO 算法","author":"carefree0910","content":"（这里是本章会用到的
地址）（这篇东西我真是觉得又臭又长 ┑(￣Д ￣)┍）SMO 算法概述SMO 是由 Platt 在 1998 年提出的、针对软间隔最大化 SVM 对偶问题求解的一个算法，其基本思想很简单：在每一步优化中，挑选出诸多参数（）中的两个参数（、）作为“真正的参数”，其余参数都视为常数，从而问题就变成了类似于二次方程求最大值的问题，从而我们就能求出解析解具体而言，SMO 要解决的是如下对偶问题：使得对、都有、其大致求解步骤则可以概括如下：选出中“最不好的”两个参数、只把、视为参数并把其余的视为常数，于是最大化就变成了以、为参数的二次规划问题，从而可以直接对其进行求解；但是，注意到、需满足和、，所以求完解后需要检查是否满足约束；如不满足，则进行调整KKT 条件先来看如何选取参数。在 SMO 算法中，我们是依次选取参数的：选出违反 KKT 条件最严重的样本点、以其对应的参数作为第一个参数第二个参数的选取有一种比较繁复且高效的方法，但对于一个朴素的实现而言、第二个参数即使随机选取也无不可这里就有了一个叫 KKT 条件的东西，其详细的陈列会放在文末，这里就仅简要的说明一下。具体而言，对于已有的模型来说，及其对应样本的 KKT 条件为：注意我们之前提过样本到超平面的函数间隔为，所以上述 KKT 条件可以直观地叙述为：样本离间隔超平面比较远样本落在间隔超平面上样本在间隔超平面以内【注意：这里的间隔超平面即为满足方程的平面；由于可以取正负一两个值，所以间隔超平面会有两个——和。而分类超平面则是满足的平面，需要将它和间隔超平面加以区分】可以以一张图来直观理解这里提到的诸多概念：（画得有点乱，见谅……）图中外面有个黑圆圈的其实就是传说中的“支持向量”，其定义会在文末给出那么我们到底应该如何刻画“违反 KKT 条件”这么个东西呢？从直观上来说，我们可以有这么一种简单有效的定义：计算三份“差异向量”，其中第份对应于三个 KKT 条件中的第个，且针对不同的 KKT 条件，将的某些位置置为 0。具体而言：对第一个 KKT 条件而言，满足以下两种情况的将应该置为 0：且且对第二个 KKT 条件而言则是：（或）且且对第三个 KKT 条件亦同理：且且最后则可以简单的将三份差异向量的平方相加来作为“损失”，从而直接选出使该损失最大的作为 SMO 的第一个参数即可。具体而言：得益于 Numpy 强大的 Fancy Indexing，上述置 0 的实现非常好写（？？？）：# 得到 alpha & 0 和 alpha & C 的 mask\ncon1 = alpha & 0\ncon2 = alpha & C\n# 算出“差异向量”并拷贝成三份\nerr1 = y * y_pred - 1\nerr2 = err1.copy()\nerr3 = err1.copy()\n# 依次根据三个 KKT 条件，将差异向量的某些位置设为 0\n# 不难看出为了直观、我做了不少重复的运算，所以这一步是可以优化的\nerr1[(con1 & (err1 &= 0)) | (~con1 & (err1 & 0))] = 0\nerr2[((~con1 | ~con2) & (err2 != 0)) | ((con1 & con2) & (err2 == 0))] = 0\nerr3[(con2 & (err3 &= 0)) | (~con2 & (err3 & 0))] = 0\n# 算出平方和并取出使得“损失”最大的 idx\nerr = err1 ** 2 + err2 ** 2 + err3 ** 2\nidx = np.argmax(err)\n第二个参数则可以简单地随机选取，虽然这不是特别好，但效果已然不错，而且不仅实现起来更简便、运行起来也更快（其实就是我太懒）（喂）。具体代码如下：idx = np.random.randint(len(self._y))\n# 这里的 idx1 是第一个参数对应的 idx\nwhile idx == idx1:\n
idx = np.random.randint(len(self._y))\nreturn idx\n至于 SMO 算法的第二步，正如前文所说，它的本质就是一个带约束的二次规划，虽然求解过程可能会比较折腾，但其实难度不大。具体步骤会放在文末，这里就暂时按下SMO 的效果仍是先看看螺旋线数据集上的训练过程：略显纠结，不过还是不错的接下来看看蘑菇数据集上的表现；单就这个数据集而言，我们实现的朴素 SVM 和 sklearn 中的 SVM 表现几乎是一致的（在使用 RBF 核时），比较具有代表性的训练曲线则如下图所示：也算是符合 SMO 这种每次只取两个参数进行更新的训练方法的直观也算是符合 SMO 这种每次只取两个参数进行更新的训练方法的直观相关数学理论1）KKT 条件的详细陈列注意到原始问题为，使得、（不妨称这两个约束为原始约束）所以其拉格朗日算子法对应的式子为于是 KKT 条件的其中四个约束即为（不妨设最优解为、、、和）：（这是拉格朗日乘子法自身的要求）、（此即原始约束）（换句话说，和中必有一个为 0）该等式有着很好的直观：设想它们同时不为 0，则必有（注意原始约束）、从而，等号当且仅当时取得。然而由于，所以若将取为 0、则上述将会变大。换句话说，将参数取为 0 将会使得目标函数比参数取时的目标函数要大，这与的最优性矛盾（换句话说，和中必有一个为 0，理由同上）从而原始问题转为；而对偶问题的实质，其实就是将原始问题转为。在求解后，可以得到如下对偶问题：，使得对、都有、（虽然这些在
中介绍过，不过为了连贯性，这里还是再介绍一遍）于是，最优解自然需要满足这么个条件：这个条件即是最后一个 KKT 条件2）何谓“支持向量”为方便说明，这里再次放出上文给出过的图：图中带黑圈的样本点即是支持向量，数学上来说的话，就是对应的样本点即是支持向量。从图中不难看出，支持向量从直观上来说，就是比较难分的样本点此外，支持向量之所以称之为“支持”向量，是因为在理想情况下，仅利用支持向量训练出来的模型和利用所有样本训练出来的模型是一致的。这从直观上是好理解的，粗略的证明则可以利用其定义来完成：非支持向量的样本对应着，亦即它对最终模型——没有丝毫贡献，所以可以直接扔掉3）带约束的二次规划求解方法不妨设我们选取出来的两个参数就是和，那么问题的关键就在于如何把和相关的东西抽取出来并把其它东西扔掉注意到我们的对偶问题为，使得对、都有、且我们在
的最后介绍过 Gram 矩阵：所以就可以改写为把和、无关的东西扔掉之后，可以化简为：约束条件则可以化简为对和，都有、，其中是某个常数而带约束的二次规划求解过程也算简单：只需先求出无约束下的最优解，然后根据约束“裁剪”该最优解即可无约束下的求解过程其实就是求偏导并令其为 0。以为例，注意到令，则亦是常数，且由于、都只能取正负 1，故不难发现，从而于是考虑到、、Gram 矩阵是对称阵、且模型在第个样本处的输出为，从而可知令，则于是注意到，从而令、，则从而接下来就要对其进行裁剪了。注意到我们的约束为、为常数所以我们需要分情况讨论的下、上界当异号（）时，可知为常数、亦即结合，可知：不应小于，否则将小于 0不应大于，否则将大于 C当同号（）时，可知为常数、亦即结合，可知：不应小于，否则将大于 C不应大于，否则将小于 0综上可知的下界为的上界为那么直接做一个 clip 即可得到更新后的：alpha1_new = np.clip(alpha1_new_raw, u, v)\n注意由于我们要保持为常数，所以（注意）综上所述，我们就完成了一次参数的更新，之后就不断地更新直至满足停机条件即可此外，我在
这篇文章中提到过，对 SVM 的对偶形式应用核方法会非常自然。表现在 SMO 上的话就是，我们可以通过简单粗暴地将核矩阵代替 Gram 矩阵来完成核方法的应用。直观地说，我们只需将上面所有出现过的都换成就行了至此，SVM 算法的介绍就大致告一段落了。我们从感知机出发，依次介绍了“极大梯度法”、MBGD（Batch 梯度下降）法、核方法和 SMO 算法；虽然都有点浅尝辄止的味道，但覆盖的东西……大概还是挺多的希望观众老爷们能够喜欢~","updated":"T04:04:01.000Z","canComment":false,"commentPermission":"anyone","commentCount":9,"collapsedCount":0,"likeCount":58,"state":"published","isLiked":false,"slug":"","lastestTipjarors":[{"isFollowed":false,"name":"符博","headline":"自由主义者，反大政府，反高福利，反文化审查，反功夫网，不喜中医，不喜小粉红。Blog: http://bofu.me 微博: @vanja 转文章不用征求我同意，给我个围观地址就好。","avatarUrl":"/2cc397f41_s.jpg","isFollowing":false,"type":"people","slug":"foolooo","bio":"Talk is cheap, show me your bra.","hash":"5dee23c560d3f1122da9","uid":68,"isOrg":false,"description":"自由主义者，反大政府，反高福利，反文化审查，反功夫网，不喜中医，不喜小粉红。Blog: http://bofu.me 微博: @vanja 转文章不用征求我同意，给我个围观地址就好。","profileUrl":"/people/foolooo","avatar":{"id":"2cc397f41","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false}],"isTitleImageFullScreen":false,"rating":"none","titleImage":"/v2-943e0b14447b63cfaa2fe5_r.png","links":{"comments":"/api/posts//comments"},"reviewers":[],"topics":[{"url":"/topic/","id":"","name":"Python"},{"url":"/topic/","id":"","name":"机器学习"},{"url":"/topic/","id":"","name":"SVM"}],"adminClosedComment":false,"titleImageSize":{"width":893,"height":328},"href":"/api/posts/","excerptTitle":"","column":{"slug":"carefree0910-pyml","name":"Python 与 机器学习"},"tipjarState":"activated","tipjarTagLine":"观众老爷们能赏个脸么 ( σ'ω')σ","sourceUrl":"","pageCommentsCount":9,"tipjarorCount":1,"annotationAction":[],"snapshotUrl":"","publishedTime":"T12:04:01+08:00","url":"/p/","lastestLikers":[{"bio":"弱鸡一枚","isFollowing":false,"hash":"e5a4775fc4df7fce34ca0","uid":76,"isOrg":false,"slug":"mo-mo-ru-chao","isFollowed":false,"description":"","name":"默默如潮","profileUrl":"/people/mo-mo-ru-chao","avatar":{"id":"4fcf246bde41b","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"看春水潺湲","isFollowing":false,"hash":"7da5cfcc826","uid":963500,"isOrg":false,"slug":"wu-jiang-gong-zi-zhang-yikuang","isFollowed":false,"description":"非职业计划通/金融数据挖掘机","name":"张无疆","profileUrl":"/people/wu-jiang-gong-zi-zhang-yikuang","avatar":{"id":"v2-cb79e5ff38e7a479d7ed1e64d5eab764","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"待业青年。","isFollowing":false,"hash":"11b96ec798b4fc558f9b","uid":365200,"isOrg":false,"slug":"cecilie","isFollowed":false,"description":"","name":"cecilie","profileUrl":"/people/cecilie","avatar":{"id":"1f3a01d1d23b0cf19b148c99d8800861","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"计算机","isFollowing":false,"hash":"c67cf20befdf","uid":72,"isOrg":false,"slug":"icycold","isFollowed":false,"description":"","name":"icycold","profileUrl":"/people/icycold","avatar":{"id":"da8e974dc","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"资产管理","isFollowing":false,"hash":"3adab5fc5dd7c","uid":046200,"isOrg":false,"slug":"wendyxie02","isFollowed":false,"description":"","name":"wendyxie02","profileUrl":"/people/wendyxie02","avatar":{"id":"da8e974dc","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false}],"summary":"（这里是本章会用到的
地址）（这篇东西我真是觉得又臭又长 ┑(￣Д ￣)┍） SMO 算法概述SMO 是由 Platt 在 1998 年提出的、针对软间隔最大化 SVM 对偶问题求解的一个算法，其基本思想很简单：在每一步优化中，挑选出诸多参数（\\alpha_k(k=1,2,...,…","reviewingCommentsCount":0,"meta":{"previous":{"isTitleImageFullScreen":false,"rating":"none","titleImage":"/v2-ce3ffef2ef4d77e8eac6ce5b9671f37b_r.png","links":{"comments":"/api/posts//comments"},"topics":[{"url":"/topic/","id":"","name":"Python"},{"url":"/topic/","id":"","name":"机器学习"},{"url":"/topic/","id":"","name":"SVM"}],"adminClosedComment":false,"href":"/api/posts/","excerptTitle":"","author":{"bio":"一个啥都想学的浮莲子","isFollowing":false,"hash":"d3031d58aeeefef54f0613","uid":547650,"isOrg":false,"slug":"carefree0910","isFollowed":false,"description":" ！沉迷东方年代记无法自拔！三倍 ICE CREEEEEEAM ！！！（╯‵□′）╯︵┴─┴","name":"射命丸咲","profileUrl":"/people/carefree0910","avatar":{"id":"0e6a3a0a84f0f9853287d","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"column":{"slug":"carefree0910-pyml","name":"Python 与 机器学习"},"content":"（这里是本章会用到的
地址）（考试周写专栏真有种忙里偷闲的感觉 _(:з」∠)_）关于核方法的比较严谨的叙述，个人建议观众老爷们可以看看下面的前几个回答；在这里的话，我们就还是只注重直观和应用层面什么是核方法？往简单里说，核方法是将一个低维的线性不可分的数据映射到一个高维的空间、并期望映射后的数据在高维空间里是线性可分的。我们以异或数据集为例：在二维空间中、异或数据集是线性不可分的；但是通过将其映射到三维空间、我们可以非常简单地让其在三维空间中变得线性可分。比如定义映射：该映射的效果如下图所示：可以看到，虽然左图的数据集线性不可分、但显然右图的数据集是线性可分的，这就是核工作原理的一个不太严谨但仍然合理的解释从直观上来说，确实容易想象、同一份数据在越高维的空间中越有可能线性可分，但从理论上是否确实如此呢？1965 年提出的 Cover 定理从理论上解决了这个问题，我们会在文末附上相应的公式，这里暂时按下不表至此，似乎问题就转化为了如何寻找合适的映射、使得数据集在被它映射到高维空间后变得线性可分。不过可以想象的是，现实任务中的数据集要比上文我们拿来举例的异或数据集要复杂得多、直接构造一个恰当的的难度甚至可能高于解决问题本身。而核方法的巧妙之处就在于，它能将构造映射这个过程再次进行转化、从而使得问题变得简易：它通过核函数来避免显式定义映射。往简单里说，核方法会通过用能够表示成的核函数替换各算式中出现的内积来完成将数据从低维映射到高维的过程。换句话说、核方法的思想如下：将算法表述成样本点内积的组合（这经常能通过算法的对偶形式实现）设法找到核函数，它能返回样本点、被作用后的内积用替换、完成低维到高维的映射（同时也完成了从线性算法到非线性算法的转换）当然了，不难想象的是，并不是所有的函数都能够对应一个映射（亦即不是所有的都能拆成；比如说，显然至少需要是一个对称函数）。幸运的是，1909 年提出的 Mercer 定理解决了这个问题，它的具体叙述会在文末给出Mercer 定理为寻找核函数带来了极大的便利。可以证明如下两族函数都是核函数：多项式核径向基（Radial Basis Function，常简称为 RBF）核：那么核方法的应用场景有哪些呢？在 2002 年由 Scholkopf 和 Smola 证明的表示定理告诉我们它的应用场景非常广泛。定理的具体内容同样会附在文末，这里就暂时按下不表核模型的表现还是用 GIF 来说明问题最为形象。当我们对感知机应用核方法后，它就能对非线性数据集（比如螺旋线数据集）进行分类了，训练过程将如下：怎么应用核方法？简单来说，就是把算法中涉及到样本（）的地方都通过某种变换、弄成样本的内积形式（）。以感知机为例，感知机的原始损失函数为为了让损失函数中的样本都变成内积形式，考虑令（也有令的）则在此之上应用核方法是平凡的：设核函数为，只需把所有的换成即可：于是优化问题变为预测步骤则变为对于 LinearSVM 而言，用同样的手法不难得出其核形式：预测步骤则仍然是（有没有发现核形式和对偶形式很像？( σ'ω')σ）如何训练核模型？【注意：为简洁，从此往后的推导和实现均以核感知机为例，核 SVM 的相关讨论会放在下一章介绍 SMO 算法时进行】简洁起见，我们还是用梯度下降法来进行训练，为此我们需要进行求导工作。假设当前模型参数为，在参数下的预测值为，则：为了加速训练，我们需要将该算式向量化，为此我们需要定义核矩阵。假设现在我们有两组样本：和，那么它们的核矩阵即为对于训练过程而言，我们关心的是训练样本之间的核矩阵利用它，不难写出相应的向量化代码：# 假设 k_mat 存储着原样本之间的核矩阵\n# 1、计算损失\nerr = -y * (k_mat.dot(alpha) + b)\n# 2、找出使得损失不小于 0 的样本\nmask = err &= 0\n# 3、进行相应梯度下降，lr 是学习速率\ndelta = lr * y[mask]\nalpha += np.sum(delta[..., None] * k_mat[mask], axis=0)\nb += np.sum(delta)\n对于预测过程，我们关心的是原样本和新样本之间的核矩阵。假设新样本为，则那么预测过程即为于是关键就在于如何定义计算核矩阵的核函数了。对于多项式核来说，核函数的实现是直观的：@staticmethod\ndef _poly(x, y, p):\n
return (x.dot(y.T) + 1) ** p\n但对于 RBF 来说就没那么直观了，用到了 Numpy 的高级实用技巧之一——升维：@staticmethod\ndef _rbf(x, y, gamma):\n
return np.exp(-gamma * np.sum((x[..., None, :] - y) ** 2, axis=2))\n当然直接用 for 来实现也是可以的，不过那将会非常非常慢……核模型的实现如果思路能够整理清楚，那么核模型相比原模型来说只有如下两点改变：需要定义核函数并计算出核矩阵计算预测值时不是，而是，其中在训练时，为原样本之间的核矩阵在测试时，为原样本和新样本的核矩阵所以实现起来的话会有许多重复代码，这里就只展现其中最核心的部分（仍以核感知机为例）：# 训练代码\ndef fit(...):\n
self._alpha = np.zeros(len(x))\n
self._b = 0.\n
self._x = x\n
# self._kernel 即为核函数，能够计算两组样本的核矩阵\n
k_mat = self._kernel(x, x)\n
for _ in range(epoch):\n
err = -y * (self._alpha.dot(k_mat) + self._b)\n
if np.max(err) & 0:\n
continue\n
mask = err &= 0\n
delta = lr * y[mask]\n
self._alpha += np.sum(delta[..., None] * k_mat[mask], axis=0)\n
self._b += np.sum(delta)\n\n# 预测代码\ndef predict(self, x, raw=False):\n
x = np.atleast_2d(x).astype(np.float32)\n
# 计算原样本与新样本的核矩阵并根据它来计算预测值\n
k_mat = self._kernel(self._x, x)\n
y_pred = self._alpha.dot(k_mat) + self._b\n
return y_pred\n
return np.sign(y_pred).astype(np.float32)\n相关数学理论1）Cover 定理若设 d 维空间中 N 个点线性可分的概率为，那么就有：其中证明从略（也就是说我不会）（喂），但是不难从中看出，它证明了当空间的维数 d 越大时、其中的 N 个点线性可分的概率就越大，这构成了核方法的理论基础之一2）Mercer 定理若是对称函数（亦即）的话，那么它具有 Hilbert 空间中内积形式的充要条件有以下两个：对任何平方可积的函数、满足对含任意 N 个样本的数据集，核矩阵：是半正定矩阵【注意：通常我们会称满足这两个充要条件之一的函数为 Mercer 核函数而把核函数定义得更宽泛。不过如果不打算在理论上深入太多的话，将 Mercer 核函数简称为核函数是可以的。此外，虽说 Mercer 核函数确实具有 Hilbert 空间中的内积形式、但此时的 Hilbert 空间并不一定具有“维度”这么好的概念（或说、可以认为此时 Hilbert 空间的维度为无穷大；比如说 RBF 核，它映射后的空间就是无穷维的）】3）表示定理设为核函数对应的映射后的空间（RKHS），表示中的范数，那么对于任意单调递增的函数和任意非负损失函数、优化问题的解总可以表述为核函数的线性组合这意味着对于任意一个损失函数和一个单调递增的正则化项组成的优化问题、我们都能够对其应用核方法下一篇文章我们则会抛开梯度下降这个有些“偷懒”的做法，并介绍一种叫序列最小最优化（SMO）的算法希望观众老爷们能够喜欢~","state":"published","sourceUrl":"","pageCommentsCount":0,"canComment":false,"snapshotUrl":"","slug":,"publishedTime":"T12:58:11+08:00","url":"/p/","title":"Python · SVM（三）· 核方法","summary":"（这里是本章会用到的
地址）（考试周写专栏真有种忙里偷闲的感觉 _(:з」∠)_）关于核方法的比较严谨的叙述，个人建议观众老爷们可以看看下面的前几个回答；在这里的话，我们就还是只注重直观和应用层面什么是核方法？往简单里说…","reviewingCommentsCount":0,"meta":{"previous":null,"next":null},"commentPermission":"anyone","commentsCount":0,"likesCount":0},"next":{"isTitleImageFullScreen":false,"rating":"none","titleImage":"/v2-c3ede4ed64f2aaf840d73_r.png","links":{"comments":"/api/posts//comments"},"topics":[{"url":"/topic/","id":"","name":"Python"},{"url":"/topic/","id":"","name":"机器学习"},{"url":"/topic/","id":"","name":"神经网络"}],"adminClosedComment":false,"href":"/api/posts/","excerptTitle":"","author":{"bio":"一个啥都想学的浮莲子","isFollowing":false,"hash":"d3031d58aeeefef54f0613","uid":547650,"isOrg":false,"slug":"carefree0910","isFollowed":false,"description":" ！沉迷东方年代记无法自拔！三倍 ICE CREEEEEEAM ！！！（╯‵□′）╯︵┴─┴","name":"射命丸咲","profileUrl":"/people/carefree0910","avatar":{"id":"0e6a3a0a84f0f9853287d","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"content":"（这里是本章会用到的
地址） （话说知乎把超链接功能删了、把公式编辑器削了【只能输单行 Tex 代码而且各种诡异 Bug】是想闹哪样……）虽然之前写过神经网络相关的文章，但彼时是本专栏刚起步的阶段，我基本是在率（瞎）性（J）地（B）写，文笔清奇逻辑混乱，所以还是重新整理一下这一部分的东西毕竟神经网络还是很重要的……等重构版弄完之后，我大概会把之前的那些玩（黑）意（历）儿（史）删掉吧…… ( σ'ω')σ将感知机应用于多分类任务我们之前在
里面介绍感知机时，用的是这么一个公式：，然后样本中的要求只能取。这在二分类任务时当然没问题，但是到多分类时就会有些问题。虽说我们是可以用各种方法让二分类模型去做多分类任务的，不过那些方法普遍都比较麻烦。为了让我们的模型天然适应于多分类任务，我们通常会将样本中的取为向量，亦即第 k 类除了第 k 位为 1 以外、其余位都是 0此时我们的感知机就会变成这样（以 N 个拥有 n 维特征的样本的 K 分类任务为例；为简洁，省略了偏置量 b）：（看在我纯鼠绘的份上原谅我画得那么丑吧 | ω?`)）此时模型的表示会变为。注意到我们原来输出的是一个数，在改造后输出的则是一个 K 维向量。也正因此，我们不能简单地沿用之前定义的损失函数（）、而应该定义一个新的损失函数由于我们的目的是让模型输出的向量和真实的（）标签向量“越近越好”，而“距离”是一个天然的衡量“远近”的东西，所以用欧氏距离来定义损失函数是比较自然的。具体而言，我们可以把损失函数定义为在有了损失之后就可以求导了。需要指出的是，虽然我接下来写的公式看上去挺显然，但由于我们进行的是矩阵求导工作，所以它们背后真正的逻辑其实没那么显然。有兴趣的观众老爷可以看看，这里就先直接给出结果，细节会附在文末：利用它，我们就能写出相应的梯度下降训练算法了：import numpy as np\n\nclass MultiPerceptron:\n
def __init__(self):\n
# 注意这里的 self._w 将来会是（n x K 的）矩阵\n
self._w = None\n
def fit(self, x, y, lr=1e-3, epoch=1000):\n
x, y = np.asarray(x, np.float32), np.asarray(y, np.float32)\n
# x.shape[1] 即为 n、y.shape[1] 即为 K\n
self._w = np.zeros([x.shape[1], y.shape[1]])\n
for _ in range(epoch):\n
# 依公式进行梯度下降\n
y_pred = x.dot(self._w)\n
dw = 2 * x.T.dot(y_pred - y)\n
self._w -= lr * dw\n
def predict(self, x):\n
# 依公式计算模型输出向量\n
y_pred = np.asarray(x, np.float32).dot(self._w)\n
# 预测类别时对输出的 K 维向量用 argmax 即可\n
return np.argmax(y_pred, axis=1).astype(np.float32)\n该模型的表现如下：此时正确率为 50% 左右。可以看到模型输出中基本没有对角线上的那一类（而这一类恰恰是最多的），这是因为将感知机拓展为多类模型并不会改变它是线性模型的本质、所以其分类效果仍然是线性的，从而它无法拟合出对角线那一类的边界从感知机到神经网络那么怎样才能把感知机变成一个非线性的模型呢？我在
中曾介绍过核方法这看上去非常高端大气的东西，这篇文章的话就主要介绍另一种思路。具体而言：现有的感知机只有两层（输入层和输出层），是否能多加一些层？核方法从直观上来说，是利用满足一定条件的核函数将样本空间映射到高维空间；如果我放宽条件、使用一些一般的比较好的函数，是否也能起到一定的效果？基于这两个想法，我们可以把上面画过的感知机模型的结构弄成下图这种结构：其中，我们通常（假设共有 N 个样本）：称为“激活函数”称和为权值矩阵称往中间加的那些层为“隐藏层”；为简洁，此后我们讨论时认为只加了一层隐藏层，多层的情况会在下一篇文章讨论称图中每个圈儿为“神经元”。以上图为例的话：输入层有 n 个神经元隐藏层有 m 个神经元输出层有 K 个神经元然后，激活函数其实就是上文所说的一般的比较好的函数；常用激活函数的相关介绍我会附在文末，这里就暂时认定激活函数为我们之前在 SVM 处就见过的 ReLU，亦即认定这个结构看上去很强大，但求导求起来却也会麻烦不少（损失函数仍取）（知乎现在这公式编辑器实在受不了了所以我就用 Word 了……仍是只给出结果并将细节附在文末）：其中，“ * ”表示乘法的 element-wise 操作（或者专业一点的话，叫 Hadamard 乘积）、ReLU'表示对 ReLU 函数进行求导。由于当为 ReLU 时我们有，所以其求导也是非常简单的：利用这两个求导公式，相应的梯度下降算法是比较好实现的：class NaiveNN:\n
def __init__(self):\n
# 这里的 self._ws 将会是一个存储着两个权值矩阵的列表\n
self._ws = None\n
@staticmethod\n
def relu(x):\n
# 利用 numpy 相应函数直接写出 ReLU 的实现\n
return np.maximum(0, x)\n
# hidden_dim 即为隐藏层神经元个数 m\n
def fit(self, x, y, hidden_dim=32, lr=1e-5, epoch=1000):\n
input_dim, output_dim = x.shape[1], y.shape[1]\n
# 随机初始化权值矩阵\n
self._ws = [\n
np.random.random([input_dim, hidden_dim]),\n
np.random.random([hidden_dim, output_dim])\n
# 定义一个列表存储训练过程中的损失\n
losses = []\n
for _ in range(epoch):\n
# 依公式算出各个值\n
h = x.dot(self._ws[0]); h_relu = NaiveNN.relu(h)\n
y_pred = h_relu.dot(self._ws[1])\n
# 利用 np.linalg.norm 算出损失\n
losses.append(np.linalg.norm(y_pred - y, ord=\"fro\"))\n
# 依公式算出各个梯度\n
d1 = 2 * (y_pred - y)\n
dw2 = h_relu.T.dot(d1)\n
dw1 = x.T.dot(d1.dot(self._ws[1].T) * (h_relu != 0))\n
# 走一步梯度下降\n
self._ws[0] -= lr * dw1; self._ws[1] -= lr * dw2\n
# 把诸模型损失返回\n
return losses\n
def predict(self, x):\n
h = x.dot(self._ws[0]); h_relu = NaiveNN.relu(h)\n
# 用 argmax 预测类别\n
return np.argmax(h_relu.dot(self._ws[1]), axis=1)\n该模型的表现如下：虽然还是比较差（准确率 70% 左右），但已经有模有样了使用 Softmax + Cross Entropy可能已经有观众老爷发现，我把上面这个模型的训练速率的默认值调到了，这是因为稍大一点的训练速率都会使模型直接爆炸。这是因为我们没有对最后一层做变换、而是直接简单粗暴地用了。这导致最终模型的输出很有可能突破天际，这当然不是我们想看到的考虑到标签是向量，换一个角度来看的话，它其实也是一个概率分布向量。那么我们是否可以将模型的输出也变成一个概率向量呢？事实上，我们耳熟能详的 Softmax 正是干这活儿的，具体而言，假设现在有一个向量，那么就有：不难看出这是个概率向量，且从直观上来看颇为合理。在真正应用 Softmax 会有一个提高数值稳定性的小技巧，细节会附在文末，这里就暂时按下于是在应用了 Softmax 之后，我们模型的输出就变成一个概率向量了。诚然此时仍然能用欧氏距离作为损失函数，不过一种普遍更优的做法是使用 Cross Entropy（交叉熵）作为损失函数。具体而言，两个随机变量（真值）、（预测值）的交叉熵为：交叉熵拥有如下两个性质：当真值为 0（）时，交叉熵其实就化为了，此时预测值越接近 0、交叉熵就越接近 0，反之若预测值趋于 1、交叉熵就会趋于无穷当真值为 1（）时，交叉熵其实就化为了，此时预测值越接近 1、交叉熵就越接近 0，反之若预测值趋于 0、交叉熵就会趋于无穷所以拿交叉熵作为损失函数是合理的。真正应用交叉熵时同样会有提高数值稳定性的小技巧——在 log 里面放一个小值以避免出现 log 0 的情况：在加了这两个东西之后，我们就要进行求导了。虽说求导过程比较繁复，但令人惊喜的是，最终结果和之前的结果是几乎一致的，区别只在于倍数（推导过程参见文末）：所以相应的实现也几乎一致：class NN:\n
def __init__(self, ws=None):\n
self._ws = ws\n
@staticmethod\n
def relu(x):\n
return np.maximum(0, x)\n
@staticmethod\n
def softmax(x):\n
exp_x = np.exp(x - np.max(x, axis=1, keepdims=True))\n
return exp_x / np.sum(exp_x, axis=1, keepdims=True)\n
@staticmethod\n
def cross_entropy(y_pred, y_true):\n
return -np.average(\n
y * np.log(np.maximum(y_pred, 1e-12)) +\n
(1 - y) * np.log(np.maximum(1 - y_pred, 1e-12))\n
def fit(self, x, y, hidden_dim=4, lr=1e-3, epoch=1000):\n
input_dim, output_dim = x.shape[1], y.shape[1]\n
if self._ws is None:\n
self._ws = [\n
np.random.random([input_dim, hidden_dim]),\n
np.random.random([hidden_dim, output_dim])\n
losses = []\n
for _ in range(epoch):\n
h = x.dot(self._ws[0]); h_relu = NN.relu(h)\n
y_pred = NN.softmax(h_relu.dot(self._ws[1]))\n
losses.append(NN.cross_entropy(y_pred, y))\n
d1 = y_pred - y\n
dw2 = h_relu.T.dot(d1)\n
dw1 = x.T.dot(d1.dot(self._ws[1].T) * (h_relu != 0))\n
self._ws[0] -= lr * dw1; self._ws[1] -= lr * dw2\n
return losses\n
def predict(self, x):\n
h = x.dot(self._ws[0]); h_relu = NaiveNN.relu(h)\n
# 由于 Softmax 不影响 argmax 的结果，所以这里直接 argmax 即可\n
return np.argmax(h_relu.dot(self._ws[1]), axis=1)\n该模型的表现如下：虽说仍不完美，但它和不使用 Softmax + Cross Entropy 的模型相比，有这么两个优势：训练速率可以调得更大（vs），这意味着该模型没那么容易爆炸（什么鬼）模型的训练更加稳定，亦即每次训练出来的结果都差不多。反观之前的模型，我所给出的模型表现其实是精挑细选出来的；在一般情况下，其表现其实是类似于这样的（这告诉我们，一个好的结果很有可能是由无数 sb 结果堆积出来的……）：相关数学理论1）常见激活函数A、Sigmoid：B、Tanh：C、ReLU：D、ELU：E、Softplus：以及最近出了一个叫 SELU 的激活函数，论文整整有 102 页……感兴趣的观众老爷们可以参见2）神经网络中导数的计算为了书写简洁，接下来我们会用矩阵求导的技巧来进行计算；不过如果觉得看着太绕的话，建议还是参照、依定义逐元素求导（事实上我也经常绕不过来……）由简入繁，我们先来看多分类感知机的求导过程。我们之前曾说过多分类感知机可以写成、其中（假设有 N 个样本）：是的矩阵是的矩阵、从而是的矩阵损失是一个的向量不少人在尝试求
时，会以为需要用向量对矩阵求导的法则，虽然不能说是错的，却可能会把问题变复杂。事实上，多分类感知机的本质是对随机向量的某个采样进行预测，只不过是一个多次采样后产生的样本矩阵而已。因此，多分类感知机的本质其实是、其中：是的向量是的权值矩阵（事实上，）、从而是的随机向量损失是一个数于是求导过程就化简为标量对矩阵的求导了：由此可知。在求出这个特殊情形之后，应该如何把它拓展到样本矩阵的情形呢？虽说严谨的数学叙述会比较麻烦（需要用到矩阵的向量化【又称“拉直”】之类的），但我们可以这样直观地理解：当样本从一个变成多个时，权值矩阵的导数理应是从一个变成多个的加总因此我们只需利用矩阵乘法完成这个加总的过程即可。注意到我们可以直观地写出：且“加总”即为，从而我们可以直观地写出注意到我们有，所以就有单隐藏层的、没有应用 Softmax + Cross Entropy 的神经网络的推导是类似的，此时：，其中、、的形状分别是、、，其中是 ReLU，、的形状分别是、于是以及3）Softmax + Cross Entropy在应用了 Softmax + Cross Entropy 之后，上面求导过程中受影响的其实只有这一项，所以只需看这一项如何变化的即可在展开讨论之前，需要先做一些符号约定（假设原模型输出向量为）：令，其中设 Softmax 后的模型输出向量为，那么依定义就有设交叉熵对应的损失函数为，则有从而可知，其中亦即本文我们主要讨论了如何将感知机应用于多分类任务，并通过直观的思想——加深感知机的层次和应用激活函数来得到更强力的模型（神经网络）。此外，我们还讨论了如何应用 Softmax + Cross Entropy 来让模型变得更加稳定。然而我们讨论的范围仍局限于单隐藏层和 ReLU 激活函数，下一篇文章我们会介绍更一般的情形，并通过一种方式来直观说明神经网络的强大希望观众老爷们能够喜欢~","state":"published","sourceUrl":"","pageCommentsCount":0,"canComment":false,"snapshotUrl":"","slug":,"publishedTime":"T17:18:18+08:00","url":"/p/","title":"Python · NN（一） · 神经网络入门","summary":"（这里是本章会用到的
地址） （话说知乎把超链接功能删了、把公式编辑器削了【只能输单行 Tex 代码而且各种诡异 Bug】是想闹哪样……）虽然之前写过神经网络相关的文章，但彼时是本专栏刚起步的阶段，我基本是在率（瞎）性（J）地（B）写…","reviewingCommentsCount":0,"meta":{"previous":null,"next":null},"commentPermission":"anyone","commentsCount":0,"likesCount":0}},"annotationDetail":null,"commentsCount":9,"likesCount":58,"FULLINFO":true}},"User":{"carefree0910":{"isFollowed":false,"name":"射命丸咲","headline":" ！沉迷东方年代记无法自拔！三倍 ICE CREEEEEEAM ！！！（╯‵□′）╯︵┴─┴","avatarUrl":"/0e6a3a0a84f0f9853287d_s.jpg","isFollowing":false,"type":"people","slug":"carefree0910","bio":"一个啥都想学的浮莲子","hash":"d3031d58aeeefef54f0613","uid":547650,"isOrg":false,"description":" ！沉迷东方年代记无法自拔！三倍 ICE CREEEEEEAM ！！！（╯‵□′）╯︵┴─┴","profileUrl":"/people/carefree0910","avatar":{"id":"0e6a3a0a84f0f9853287d","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false,"badge":{"identity":null,"bestAnswerer":null}}},"Comment":{},"favlists":{}},"me":{},"global":{},"columns":{"carefree0910-pyml":{"following":false,"canManage":false,"href":"/api/columns/carefree0910-pyml","name":"Python 与 机器学习","creator":{"slug":"carefree0910"},"url":"/carefree0910-pyml","slug":"carefree0910-pyml","avatar":{"id":"v2-a3c6fab584e","template":"/{id}_{size}.jpg"}}},"columnPosts":{},"postComments":{},"postReviewComments":{"comments":[],"newComments":[],"hasMore":true},"favlistsByUser":{},"favlistRelations":{},"promotions":{},"switches":{"couldAddVideo":false},"draft":{"titleImage":"","titleImageSize":{},"isTitleImageFullScreen":false,"canTitleImageFullScreen":false,"title":"","titleImageUploading":false,"error":"","content":"","draftLoading":false,"globalLoading":false,"pendingVideo":{"resource":null,"error":null}},"drafts":{"draftsList":[]},"config":{"userNotBindPhoneTipString":{}},"recommendPosts":{"articleRecommendations":[],"columnRecommendations":[]},"env":{"isAppView":false,"appViewConfig":{"content_padding_top":128,"content_padding_bottom":56,"content_padding_left":16,"content_padding_right":16,"title_font_size":22,"body_font_size":16,"is_dark_theme":false,"can_auto_load_image":true,"app_info":"OS=iOS"},"isApp":false},"sys":{}}