Support Vector Machines Explained支持向量机讲解

To make the task concrete, suppose the filter measures only two numbers for each email: how many links and how many exclamation marks it contains per thousand words. Counting per thousand words makes long and short emails comparable, and it is also why the numbers need not be whole. Each email then becomes a point on a plane, and the emails that people have already labelled form two groups of points. Deciding about a new email amounts to deciding which group its point belongs to, and the simplest rule is a straight line drawn between the groups, with one side meaning spam and the other meaning normal mail.

In the figure below the line can be moved by dragging its two ends. Many different lines separate the labelled emails without a single mistake, yet they disagree about new emails that land between the two groups. The first question this guide answers is therefore which of these lines to choose; the later chapters turn to the case in which no straight line can separate the groups at all.

为了把任务说具体，假设过滤器对每封邮件只量两个数：每千字里有几个链接、几个感叹号。按每千字计数，长短不同的邮件才能放在一起比较，这也是这些数不一定是整数的原因。这样每封邮件都成了平面上的一个点，人工标注过的邮件构成两群点。判断一封新邮件，就是判断它的点属于哪一群；最简单的规则是在两群点之间画一条直线，一侧算作垃圾邮件，另一侧算作正常邮件。

下图中的直线可以拖动两端来移动。能把已标注邮件完全分开、一封都不错的直线有许多条，它们对落在两群点之间的新邮件却给出不同的判断。因此本文首先回答的问题是应该选哪一条直线；后面的章节再讨论两群点根本无法用直线分开时该怎么办。

Before a computer can search for a line, the line has to be written as numbers. The figure below builds the decision rule in four steps:

• Point: the two measurements of an email form a vector $x=(x_1,x_2)$, a point in the plane.
• Line: every straight line can be written as $w_1x_1+w_2x_2+b=0$, or $w\cdot x+b=0$ with the dot product. The numbers $w=(w_1,w_2)$ and $b$ are not decided yet; $w$ is perpendicular to the line and sets its direction, and $b$ shifts it.
• Score: for any point, $f(x)=w\cdot x+b$ is positive on one side of the line and negative on the other.
• Rule: the rule predicts $+1$ (spam) when $f(x)>0$ and $-1$ (normal mail) otherwise.

The emails used for learning also carry a second number, the label $y$, which is the answer given by people: $y=+1$ for spam and $y=-1$ for normal mail. The label is not the score. The score $f(x)$ is computed from the line and changes whenever the line moves, while the label comes with the data and never changes. Learning adjusts the line until the sign of $f(x)$ agrees with $y$ for the labelled emails; a new email has no label, and only $f(x)$ is available to judge it.

要让计算机去寻找直线，先得把直线写成数字。下图分四步搭出判断规则：

• 点：一封邮件的两个测量值组成向量 $x=(x_1,x_2)$，也就是平面上的一个点。
• 直线：任何一条直线都可以写成 $w_1x_1+w_2x_2+b=0$，用点积简写为 $w\cdot x+b=0$。其中 $w=(w_1,w_2)$ 和 $b$ 还没有确定；$w$ 与直线垂直，决定直线的方向，$b$ 让直线平移。
• 打分：对任意一个点，$f(x)=w\cdot x+b$ 在直线一侧为正，另一侧为负。
• 规则：$f(x)>0$ 时判为 $+1$（垃圾邮件），否则判为 $-1$（正常邮件）。

用来学习的邮件还带有另一个数，即标签 $y$，它是人工给出的正确答案：垃圾邮件 $y=+1$，正常邮件 $y=-1$。标签不是分数。分数 $f(x)$ 由直线算出，直线一动它就跟着变；标签则随数据一起给定，始终不变。学习就是调整直线，使已标注邮件上 $f(x)$ 的正负号与 $y$ 一致；新邮件没有标签，只能靠 $f(x)$ 来判断。

A rule of this kind is called a linear classifier, and learning it means choosing the numbers $w$ and $b$. With more than two measurements the line becomes a flat surface called a hyperplane, but the formula stays exactly the same; appendix A1 explains the dot product and why $w$ is perpendicular to the line.

这样的规则称为线性分类器，学习它就是选出 $w$ 和 $b$ 这几个数。测量值多于两个时，直线变成一个称为超平面的平直曲面，公式却完全不变；附录 A1 讲解了点积，以及 $w$ 为什么与直线垂直。

The oldest method for finding $w$ and $b$ from labelled data is the perceptron^[1]. It starts from an arbitrary line and goes through the emails one at a time. Whenever an email lies on the wrong side, the perceptron corrects the line for that email by adding $y_ix_i$ to $w$ and $y_i$ to $b$. For a spam email ($y_i=+1$) this turns $w$ towards the email and raises its score $f(x_i)$; for a normal email it does the opposite. The perceptron stops once a full pass finds no mistakes, and when the two groups can be separated it is guaranteed to stop after a finite number of corrections^[2].

Where it stops, however, depends on the starting line and on the order in which it happens to see the emails. Different starts lead to different lines, often ones that pass very close to some email. The perceptron therefore answers the question of whether a line without mistakes exists, but not the question of the previous chapter, namely which such line to choose.

根据已标注数据求 $w$ 和 $b$，最早的方法是感知机^[1]。它从一条随意的直线出发，逐封查看邮件。每遇到一封落在错误一侧的邮件，就针对这封邮件修正直线：给 $w$ 加上 $y_ix_i$，给 $b$ 加上 $y_i$。对垃圾邮件（$y_i=+1$），这会让 $w$ 转向这封邮件，使它的得分 $f(x_i)$ 变大；对正常邮件则正好相反。完整看一遍都没有错误时，感知机停止；只要两群点能被直线分开，它一定会在有限次修正后停下来^[2]。

然而它停在哪里，取决于起始直线和它碰巧以什么顺序看到这些邮件。起点不同，得到的直线也不同，而且常常紧贴着某封邮件经过。因此，感知机回答了“是否存在一条不出错的直线”，却没有回答上一章的问题：在这些直线中应该选哪一条。

Measurements are never exact, and a new email is rarely a copy of an old one; it tends to land somewhere near the emails it resembles. If the line passes very close to a training email, a new email similar to it can easily fall on the wrong side. A line that keeps as far as possible from both groups leaves the most room for such variation. This suggests scoring each candidate line by its distance to the nearest training point, called the margin, and choosing the line with the largest margin.

A helpful picture is a street running between the two groups: the line is the centre of the street, and the goal is to make the street as wide as possible while no point stands on it. Since the distance from a point $x$ to the line is $|w\cdot x+b|/\|w\|$ (derived in appendix A1), the margin of a line is the smallest of these distances over all training points.

Once the widest street has been found, only a few points touch its edges, and these points alone determine where it lies. They are called support vectors, because they hold the street in place the way posts hold up a fence; any other point can be moved, or removed, without changing anything, as long as it stays off the street. The classifier that chooses the maximum-margin line is accordingly called the support vector machine, or SVM^[3]. In the experiment below the line starts with a narrow street and can again be moved by hand.

测量总有误差，新邮件也很少是旧邮件的翻版，它往往落在与它相似的那些邮件附近。如果直线紧贴着某封训练邮件经过，一封与之相似的新邮件就很容易落到错误一侧。离两群点都尽量远的直线，给这种变化留出了最大的余地。于是可以这样给每条候选直线打分：看它到最近的训练点有多远，这个距离称为间隔；然后选间隔最大的那条直线。

不妨想象两群点之间有一条街道，直线是街道的中线，目标是在没有任何点站在街上的前提下，让街道尽量宽。点 $x$ 到直线的距离是 $|w\cdot x+b|/\|w\|$（推导见附录 A1），因此一条直线的间隔就是所有训练点到它的距离中最小的那个。

找到最宽的街道之后，只有少数几个点贴着街道的边缘，街道的位置完全由这几个点决定。它们称为支持向量，因为它们像篱笆的桩子一样把街道撑在原处；其余的点只要不走到街上，移动甚至删除都不会改变任何结果。选择最大间隔直线的分类器因此称为支持向量机，简称 SVM^[3]。下面的实验中，直线一开始的街道很窄，仍然可以手动移动。

To let a computer find the widest street, “as wide as possible” has to become a formula, and the first step is to say where the two edges of a street lie. For the centre line of a street, the nearest emails on the two sides are equally far away, so their scores $f(x)=w\cdot x+b$ are equal in size and opposite in sign, say $+c$ and $-c$, and the edges are the lines $f(x)=+c$ and $f(x)=-c$.

The number $c$, however, is not fixed by the line. Multiplying $w$ and $b$ by the same positive number $k$ leaves the line where it is but multiplies every score by $k$, so $c$ can be made any positive number. Since this choice is free, it is made in the simplest way, $c=1$: the nearest emails then score exactly $+1$ and $-1$, and the edges are the lines $f(x)=+1$ and $f(x)=-1$. By the distance formula of appendix A1, each edge lies at distance $1/\|w\|$ from the centre, so the street is $2/\|w\|$ wide.

要让计算机找出最宽的街道，得先把“尽量宽”写成公式，第一步是说清街道的两条边缘在哪里。对一条街道的中线来说，两侧最近的邮件离它一样远，因此它们的分数 $f(x)=w\cdot x+b$ 大小相等、符号相反，不妨记作 $+c$ 和 $-c$；街道的两条边缘就是直线 $f(x)=+c$ 和 $f(x)=-c$。

然而 $c$ 并不由直线决定。把 $w$ 和 $b$ 同时乘以同一个正数 $k$，直线不动，所有分数却都乘以 $k$，所以 $c$ 可以变成任何正数。既然可以随意选，就选最简单的 $c=1$：这时最近的邮件分数恰好是 $+1$ 和 $-1$，街道边缘就是直线 $f(x)=+1$ 和 $f(x)=-1$。根据附录 A1 的距离公式，每条边缘到中线的距离是 $1/\|w\|$，因此街道宽度为 $2/\|w\|$。

A wider street is therefore the same as a smaller $\|w\|$, under the condition that every training point lies on its own side and off the street. For spam the condition reads $f(x_i)\ge 1$ and for normal mail $f(x_i)\le -1$; multiplying by the label $y_i$ folds the two into the single condition $y_i(w\cdot x_i+b)\ge 1$. A condition of this kind is called a constraint, and a point that stands on the street or lies on the wrong side is said to violate its constraint. Minimizing $\tfrac12\|w\|^2$ instead of $\|w\|$ leads to the same line and a smoother formula, which gives the problem below, known as the hard-margin SVM.

于是，让街道更宽就等于让 $\|w\|$ 更小，条件是每个训练点都在自己那一侧、且不站在街上。对垃圾邮件，条件是 $f(x_i)\ge 1$；对正常邮件，条件是 $f(x_i)\le -1$。两边同乘标签 $y_i$，就把这两个条件合并成一个：$y_i(w\cdot x_i+b)\ge 1$。这样的条件称为约束；站在街上或落在错误一侧的点，就违反了它的约束。用 $\tfrac12\|w\|^2$ 代替 $\|w\|$ 求最小，得到的直线相同，公式却更光滑，这就是下面的问题，称为硬间隔 SVM。

The objective is a quadratic function and every constraint is linear, so the problem belongs to a well-studied class called quadratic programming. Such a problem has a single lowest point and no false local minima^[4], which means that, unlike the perceptron, it always returns the same line. The experiment below shows the trade-off inside the formula. The direction slider turns $w$, and for each direction $b$ is placed in the middle of the gap between the groups; the size slider sets $\|w\|$. A large $\|w\|$ gives a narrow street that every point stays off, while shrinking $\|w\|$ widens the street until it runs into points, which then violate their constraints.

目标函数是二次函数，每个约束都是线性的，因此这个问题属于一类研究得很透彻的问题，称为二次规划。这类问题只有一个最低点，不存在虚假的局部极小值^[4]，所以它与感知机不同，每次都给出同一条直线。下面的实验展示了公式内部的取舍。“方向”滑块转动 $w$，对每个方向，$b$ 都取在两群点之间空隙的正中；“大小”滑块设定 $\|w\|$。$\|w\|$ 大时街道窄，所有点都在街外；把 $\|w\|$ 调小，街道随之变宽，直到撞上一些点，这些点随即违反了约束。

Real data are rarely as tidy as the emails so far. Some spam is written to look like normal mail, and a single such email landing among the normal ones makes the hard-margin problem impossible, since no line satisfies every constraint. Even when a line still exists, one unusual point can force the street to become narrow and tilted. The remedy is to let each point violate its constraint by some amount $\xi_i\ge 0$, called a slack variable, and to charge for it in the objective^[5]:

真实数据很少像前面的邮件那样整齐。有些垃圾邮件刻意写得像正常邮件，只要有一封这样的邮件落进正常邮件之中，硬间隔问题就无解了，因为没有任何直线能满足全部约束。即使直线仍然存在，一个异常的点也可能迫使街道变窄、变斜。解决办法是允许每个点以一定的量 $\xi_i\ge 0$ 违反约束，这个量称为松弛变量，同时在目标函数中为它付出代价^[5]：

The constant $C$ is the cost of a violation. A large $C$ makes violations expensive, so the street narrows to keep as many points off it as possible; a small $C$ accepts violations in exchange for a wider street that is not dragged around by a few unusual points. This version is called the soft-margin SVM, and the hard margin is its limit as $C$ grows without bound. After training, the points fall into three kinds:

• Points outside the street on the correct side: $\xi_i=0$, and they have no influence on the result.
• Points exactly on an edge of the street: $\xi_i=0$, and they are support vectors.
• Points inside the street or on the wrong side: $\xi_i>0$, and they are support vectors as well.

The objective above contains the slack variables $\xi_i$, which were invented only to allow violations. What is actually at hand is the line, that is, $w$ and $b$, and the data, so it is natural to try to express each $\xi_i$ through these. For a given line, each point needs just enough slack to make its constraint $y_if(x_i)\ge 1-\xi_i$ hold. Here $y_if(x_i)$ is the score of point $i$, counted as positive on its own side, in the units of Chapter 3, where the edges of the street lie at 1 and the centre line at 0. The slack a point needs is how far its score falls short of 1, as the figure below shows.

常数 $C$ 就是违反约束的代价。$C$ 大时违反约束代价高，街道会收窄，尽量让更多的点留在街外；$C$ 小时可以容忍违反约束，换来一条更宽、不被少数异常点牵着走的街道。这种形式称为软间隔 SVM，硬间隔则是 $C$ 无限增大时的极限。训练完成后，所有点分为三种：

• 位于街道之外、且在正确一侧的点：$\xi_i=0$，对结果没有任何影响。
• 恰好位于街道边缘上的点：$\xi_i=0$，它们是支持向量。
• 位于街道之内或错误一侧的点：$\xi_i>0$，它们同样是支持向量。

上面的目标函数里有松弛变量 $\xi_i$，它们只是为了允许违反约束而额外引入的。我们手里真正有的是直线（即 $w$ 和 $b$）和数据点，因此自然想用这些已有的量把每个 $\xi_i$ 表示出来。对给定的直线，每个点需要的松弛，恰好够让它的约束 $y_if(x_i)\ge 1-\xi_i$ 成立即可。这里 $y_if(x_i)$ 是第 $i$ 个点的分数，在它自己一侧记为正，单位沿用第 3 章：街道边缘位于 1，中线位于 0。一个点需要的松弛，就是它的分数比 1 差了多少，见下图。

All three zones of the figure are covered by $\xi_i=\max\big(0,\,1-y_if(x_i)\big)$; taking the larger of the number and 0 says that a point beyond the edge needs nothing and earns no credit for being far. The slacks of all points are added up, not averaged, and $C$ sets their weight; averaging would only divide $C$ by the number of points. Substituting gives an objective in $w$ and $b$ alone:

The second term is called the hinge loss after the shape of its graph, shown on the right below with the three zones shaded.

图中的三个区域可以合写成 $\xi_i=\max\big(0,\,1-y_if(x_i)\big)$；与 0 取较大者，表示边缘之外的点不需要松弛，离得再远也不会得到额外的奖励。所有点的松弛是相加，而不是取平均，由 $C$ 决定它们的分量；取平均只相当于把 $C$ 除以点的个数。代入后，目标函数就只含 $w$ 和 $b$：

第二项因函数图像形似合页而称为合页损失，图像见下图右侧，三个区域用底色标出。

The hinge loss alone does not pick out one line. In fact it rewards a narrow street. Doubling $w$ and $b$ leaves the line where it is, as in Chapter 3, but halves the width of the street, because its edges are always the lines where the score is $\pm1$. Points that stood on the street now lie beyond its edges, and their hinge loss drops to 0. Left to itself, the hinge loss would therefore make the street ever narrower and $w$ ever larger. The term $\tfrac12\|w\|^2$ pulls the other way and keeps $w$ small, so the result balances a small loss against a small $w$. Adding such a term to the objective, so that the parameters are kept small, is called regularization. It is common throughout machine learning; neural networks, for example, are often trained with a similar penalty on their weights, which reduces overfitting.

This does not conflict with the earlier description of the same term. The street is $2/\|w\|$ wide, so a smaller $w$ means a wider street, and “make the street as wide as possible” and “regularization” refer to the same term $\tfrac12\|w\|^2$, seen once from geometry and once from the loss.

仅凭合页损失，选不出唯一的一条直线；事实上，它偏爱窄街道。把 $w$ 和 $b$ 同时乘以 2，与第 3 章一样，直线不动，街道却窄了一半，因为街道边缘始终是分数等于 $\pm1$ 的地方。原本站在街上的点，现在落到了边缘之外，合页损失降为 0。所以，只看合页损失，街道会越变越窄，$w$ 会越变越大。$\tfrac12\|w\|^2$ 这一项朝相反的方向拉，让 $w$ 保持较小，于是结果在“损失小”和“$w$ 小”之间取得平衡。这种在目标函数中额外加一项、使参数保持较小的做法，称为正则化。它在机器学习中十分常见，例如训练神经网络时也常对权重加类似的惩罚，以减少过拟合。

这与前面对这一项的说法并不矛盾。街道宽度是 $2/\|w\|$，$w$ 越小，街道越宽，所以“让街道尽量宽”和“正则化”说的是同一项 $\tfrac12\|w\|^2$，只是一个从几何的角度看，一个从损失的角度看。

The problem so far searches for the street directly, through its direction and width, that is, through $w$ and $b$. The same problem can also be looked at from the side of the training points, which are what is actually known. The constraints require that no point stand on the street, or, in the soft-margin version, that a point stand on it only at a price. The street can therefore widen only until points stop it, and it is these points that decide where its edges lie.

To describe how much each point decides, point $i$ is given a number $\alpha_i\ge 0$, which can be pictured as the force with which it pushes back against the street. This number is called a Lagrange multiplier; appendix A2 explains the idea on a small example. Its values follow from the picture:

• Points away from the street: the street never reaches them, so they do not push, and $\alpha_i=0$. This property is called complementary slackness.
• Points on an edge of the street or on the street, the support vectors: $\alpha_i>0$, and in the soft-margin version no point pushes harder than $C$.

到目前为止，问题都是直接寻找街道本身，即它的方向和宽度，也就是 $w$ 和 $b$。同一个问题也可以换一种方式来看：从已知的训练点出发。约束要求所有点都不能站上街道；在软间隔版本中，则是点要付出代价才能站上去。因此，街道只能一直加宽到被某些点挡住为止，街道的边缘在哪里，是由这些点决定的。

为了描述每个点在多大程度上决定了街道，给第 $i$ 个点配一个数 $\alpha_i\ge 0$，可以把它想象成这个点顶住街道的力。这个数称为拉格朗日乘子，附录 A2 用一个小例子讲解了这个想法。它的取值可以直接从这幅图景中看出来：

• 离街道较远的点：街道碰不到它，它不用出力，因此 $\alpha_i=0$。这一性质称为互补松弛。
• 贴着街道边缘或站上街道的点，即支持向量：$\alpha_i>0$；在软间隔版本中，任何一个点的力都不会超过 $C$。

When the pushes are in balance, $w$ turns out to be a weighted sum of the training points, $w=\sum_i\alpha_iy_ix_i$, so the classifier can be written entirely in terms of the training points:

这些力相互平衡时，$w$ 恰好是训练点的加权和 $w=\sum_i\alpha_iy_ix_i$，因此分类器可以完全用训练点写出来：

Training therefore amounts to finding the weights $\alpha_i$ instead of $w$ and $b$. The weights are the solution of the problem below, called the dual problem; the original problem, which searches for $w$ and $b$, is then called the primal problem^[4]. In practice it is solved by algorithms such as SMO, which repeatedly picks two weights and adjusts them together until no further improvement is possible^[6].

因此，训练不再直接求 $w$ 和 $b$，而是求这些权重 $\alpha_i$。它们是下面这个问题的解，这个问题称为对偶问题；原来那个求 $w$ 和 $b$ 的问题，则称为原问题^[4]。实际中常用 SMO 之类的算法求解：每次挑出两个权重一起调整，直到无法再改进为止^[6]。

Both formulas share a detail that becomes the key to the second part of this guide. The training points never appear on their own, only in pairs inside dot products, as $x_i\cdot x_j$ during training and $x_i\cdot x$ during prediction.

两个公式有一个共同的细节，它将成为本文第二部分的关键：训练点从不单独出现，总是成对地出现在点积里，训练时是 $x_i\cdot x_j$，预测时是 $x_i\cdot x$。

Some groups cannot be split by any straight line. In the figure below one class forms a disc in the middle and the other a ring around it, and every line through the plane leaves part of the ring on the wrong side. A circle would separate them easily, so the question becomes how a method that only knows how to draw straight lines can be made to draw a circle. The answer is to change the data rather than the method. Each point receives a third coordinate, its squared distance from the centre, $x_1^2+x_2^2$. In three dimensions the inner disc stays low while the ring rises high, so a flat plane at a suitable height separates them, and seen from above, the place where the plane cuts the bowl is exactly a circle.

有些点群无论用哪条直线都分不开。下图中，一类点在中间组成圆盘，另一类点在外面围成圆环，平面上的任何直线都会把圆环的一部分划到错误一侧。用一个圆就能轻松分开它们，于是问题变成：一个只会画直线的方法，怎样才能画出圆来？答案是改变数据，而不是改变方法。给每个点添上第三个坐标，即它到中心距离的平方 $x_1^2+x_2^2$。在三维空间中，内圈的圆盘留在低处，外圈的圆环升到高处，于是一个高度合适的平面就能把它们分开；从上往下看，平面与碗面相交的地方恰好是一个圆。

In general, a function $\varphi$ that turns each original point into a list of new coordinates is called a feature map, and the space of the new coordinates is called the feature space. A straight boundary in the feature space corresponds to a curved boundary in the original space.

The coordinate added above, $x_1^2+x_2^2$, is built from products of coordinates, $x_1\cdot x_1$ and $x_2\cdot x_2$. Other curves need other products: a flattened ellipse needs $x_1^2$ and $x_2^2$ with different weights, and a tilted one also needs the cross product $x_1x_2$. In fact, once the five features $x_1,\ x_2,\ x_1^2,\ x_1x_2,\ x_2^2$ are all available, every circle, ellipse, parabola and hyperbola in the plane becomes a straight boundary in the feature space, and which curve it is depends only on the weights $w$ that the SVM gives to the features. There is then no need to guess the right feature in advance: it is enough to include all products of two coordinates and let the SVM find the combination. Products of three coordinates allow still more winding curves, and so on.

一般地，把每个原始点变成一组新坐标的函数 $\varphi$ 称为特征映射，新坐标所在的空间称为特征空间。特征空间里平直的边界，对应原始空间里弯曲的边界。

上面添加的坐标 $x_1^2+x_2^2$ 是由坐标的乘积 $x_1\cdot x_1$ 和 $x_2\cdot x_2$ 构成的。别的曲线需要别的乘积：压扁的椭圆需要权重不同的 $x_1^2$ 和 $x_2^2$，倾斜的椭圆还需要交叉乘积 $x_1x_2$。事实上，只要 $x_1,\ x_2,\ x_1^2,\ x_1x_2,\ x_2^2$ 这五个特征都齐备，平面上的任何圆、椭圆、抛物线和双曲线，在特征空间里都变成平直的边界；具体是哪一条曲线，只取决于 SVM 给各个特征的权重 $w$。于是不必事先猜出哪个特征有用，只要把两个坐标的所有乘积都放进去，让 SVM 去找合适的组合即可。三个坐标的乘积能画出更曲折的曲线，依此类推。

The price is the number of features, which grows quickly with both the number of coordinates and the number of factors in each product. Two coordinates with products of at most two factors give the five features above, but a 28×28 grayscale image has 784 coordinates, and the products of at most three of them already number about 81 million. Storing such vectors and computing their dot products becomes the bottleneck. The next chapter shows that this cost can be avoided entirely.

代价是特征的数量，它随坐标数和每个乘积的因子数迅速增长。两个坐标、乘积不超过两个因子时，只有上面这五个特征；但一张 28×28 的灰度图片有 784 个坐标，其中不超过三个坐标的乘积就已经约有 8100 万个。存储这样的向量、计算它们的点积都成了瓶颈。下一章说明这笔开销其实可以完全省去。

Chapter 5 showed that the SVM never needs the points themselves, only the dot product $x\cdot z$ of pairs of points. This invites an experiment: replace the dot product with another quantity that is just as easy to compute, for example its square $(x\cdot z)^2$. For two-dimensional points, expanding the square gives

The right-hand side is an ordinary dot product of two three-dimensional vectors, and their coordinates are exactly the products of two coordinates from the previous chapter; the factor $\sqrt2$ appears only because the cross term occurs twice in the expansion. Squaring the dot product is therefore the same as moving every point into a feature space in which a circle like the one in the previous chapter becomes a straight line, and taking the dot product there. Yet the computation needs only one dot product in two dimensions followed by squaring, and $\varphi(x)$ is never built.

A function $K(x,z)$ that equals $\varphi(x)\cdot\varphi(z)$ for some feature map $\varphi$ is called a kernel, and replacing every dot product in the SVM with a kernel gives the kernel SVM:

第 5 章说明，SVM 从不需要点本身，只需要两点之间的点积 $x\cdot z$。这就引出一个尝试：把点积换成另一个同样容易计算的量，比如它的平方 $(x\cdot z)^2$。对二维的点，把平方展开得到

右边是两个三维向量的普通点积，而这些向量的坐标正是上一章所说的两个坐标的乘积；系数 $\sqrt2$ 只是因为交叉项在展开式中出现了两次。因此，把点积平方，就等于先把每个点搬进一个特征空间（在那里，像上一章那样的圆变成了直线），再在那里做点积。然而计算时只需在二维中做一次点积再平方，$\varphi(x)$ 根本不必构造出来。

如果函数 $K(x,z)$ 对某个特征映射 $\varphi$ 满足 $K(x,z)=\varphi(x)\cdot\varphi(z)$，就称它为核函数。把 SVM 中所有的点积都换成核函数，就得到核 SVM：

This replacement is called the kernel trick^[7]. It lets the SVM draw a straight boundary in the feature space while every computation stays in the original space. Adding 1 before squaring brings in the products of fewer coordinates as well, and raising to the power $d$ instead of 2 covers all products of up to $d$ coordinates. The kernel $(x\cdot z+1)^3$ therefore stands for the 81 million features of the image example while costing one 784-dimensional dot product, and the feature space may even have infinitely many dimensions, as Chapter 9 shows.

A space with so many dimensions would normally invite overfitting, that is, a boundary that follows the accidents of the training data so closely that new data are classified badly. Here the maximum margin helps: the ability of a large-margin classifier to fit arbitrary labels is limited by the width of its margin, relative to the spread of the data, rather than by the number of dimensions^[8].

这种替换称为核技巧^[7]。它让 SVM 在特征空间中画出平直的边界，而所有计算都留在原始空间里完成。平方之前先加 1，就把因子更少的乘积也包括进来；把 2 次方换成 $d$ 次方，就涵盖了不超过 $d$ 个坐标的全部乘积。因此，核函数 $(x\cdot z+1)^3$ 代表了图片例子中的 8100 万个特征，计算它却只需要一次 784 维的点积；特征空间甚至可以有无穷多维，第 9 章会看到这样的例子。

维数这么高的空间通常容易导致过拟合，也就是边界把训练数据中的偶然情况也学了进去，以致新数据被判错。这里最大间隔起了作用：一个大间隔分类器能拟合任意标签的能力，受间隔宽度（相对于数据的分布范围）的限制，而不受维数的限制^[8]。

In the previous chapter, the feature map behind $(x\cdot z)^2$ was found by expanding the square. This is how kernels are used in practice: one writes down a function $K(x,z)$ that measures how similar two points are, and only needs to know that some feature map lies behind it. For most such functions, however, no expansion is at hand that would reveal the feature map, and not every similarity function has one. A test is therefore needed.

Because $K(x,z)=\varphi(x)\cdot\varphi(z)$, a kernel must be symmetric, $K(x,z)=K(z,x)$. A less obvious requirement comes from the fact that a squared length is never negative: for any points $x_1,\dots,x_m$ and any numbers $c_1,\dots,c_m$,

The table of values $K(x_i,x_j)$ is called the Gram matrix, and a symmetric matrix that satisfies this inequality for every choice of $c$ is called positive semidefinite, which is the same as having no negative eigenvalues (appendix A3 explains both terms with pictures). The requirement turns out to be sufficient as well as necessary. If a symmetric function produces a positive semidefinite Gram matrix for every finite set of points, then a feature map with $K(x,z)=\varphi(x)\cdot\varphi(z)$ exists, possibly with infinitely many dimensions; this is the content of Mercer’s theorem^[9].

The theorem supplies the precise definition of a kernel: a symmetric function all of whose Gram matrices are positive semidefinite. It also explains what goes wrong otherwise, since with an invalid kernel the dual problem can lose its single lowest point and the solver may return different answers.

上一章把 $(x\cdot z)^2$ 展开，找到了它背后的特征映射。实际中核函数正是这样用的：先写出一个衡量两个点有多相似的函数 $K(x,z)$，只需确认它背后存在某个特征映射即可。然而，对大多数这样的函数，并没有现成的展开式能揭示它的特征映射，而且并非每个相似度函数背后都有特征映射，因此需要一种检验办法。

由于 $K(x,z)=\varphi(x)\cdot\varphi(z)$，核函数必须对称，即 $K(x,z)=K(z,x)$。另一个不那么显然的要求来自“长度的平方不会是负数”：对任意一组点 $x_1,\dots,x_m$ 和任意一组数 $c_1,\dots,c_m$，

由 $K(x_i,x_j)$ 组成的数表称为 Gram 矩阵；一个对称矩阵若对任意一组 $c$ 都满足这个不等式，就称为半正定矩阵，这等价于它没有负的特征值（附录 A3 用图解释了这两个概念）。这个要求不仅必要，而且充分：如果一个对称函数对任意有限个点构成的 Gram 矩阵都是半正定的，那么一定存在满足 $K(x,z)=\varphi(x)\cdot\varphi(z)$ 的特征映射，维数可能是无穷，这就是 Mercer 定理^[9]。

这个定理给出了核函数的精确定义：所有 Gram 矩阵都半正定的对称函数。它也说明了不满足条件时会出什么问题：用了不合格的核函数，对偶问题可能不再只有一个最低点，求解器可能给出不同的答案。

Checking the condition directly is hard, because it has to hold for every set of points. New kernels are therefore usually assembled from known ones by operations that are guaranteed to preserve it^[10]. If $K_1$ and $K_2$ are kernels, so are the following:

• Sum: $K_1(x,z)+K_2(x,z)$.
• Positive multiple: $c\,K_1(x,z)$ for any $c>0$.
• Product: $K_1(x,z)\,K_2(x,z)$.
• Rescaling: $g(x)\,K_1(x,z)\,g(z)$ for any function $g$.
• Exponential: $\exp\big(K_1(x,z)\big)$.

For instance, $(x\cdot z+1)^d$ is obtained from the dot product by adding the constant kernel 1 and multiplying the result by itself $d$ times, and the Gaussian kernel of the next chapter follows from $\exp(-\|x-z\|^2)=e^{-\|x\|^2}\,\exp(2\,x\cdot z)\,e^{-\|z\|^2}$, which is an exponential followed by a rescaling.

直接检验这个条件很困难，因为它必须对任意一组点都成立。因此，新的核函数通常是用保证不破坏这一条件的运算，由已知的核函数组合出来的^[10]。若 $K_1$、$K_2$ 是核函数，下面这些也都是核函数：

• 和：$K_1(x,z)+K_2(x,z)$。
• 正数倍：$c\,K_1(x,z)$，其中 $c>0$。
• 乘积：$K_1(x,z)\,K_2(x,z)$。
• 两端缩放：$g(x)\,K_1(x,z)\,g(z)$，其中 $g$ 是任意函数。
• 指数：$\exp\big(K_1(x,z)\big)$。

例如，$(x\cdot z+1)^d$ 是在点积上加常数核 1，再自乘 $d$ 次得到的；下一章的高斯核则来自 $\exp(-\|x-z\|^2)=e^{-\|x\|^2}\,\exp(2\,x\cdot z)\,e^{-\|z\|^2}$，即先取指数、再做两端缩放。

With these rules, a handful of kernels covers most practical needs. Each expresses a different idea of what makes two points similar:

• Linear kernel, $K(x,z)=x\cdot z$: no feature map at all. It suits data that already have very many coordinates, such as text described by word counts, where a hyperplane is usually enough.
• Polynomial kernel, $K(x,z)=(x\cdot z+c)^d$: the feature space holds all products of up to $d$ coordinates, so it captures interactions, such as two words that matter only when they appear together.
• Gaussian kernel, also called the RBF kernel, $K(x,z)=\exp(-\gamma\|x-z\|^2)$: similarity is 1 for identical points and fades to 0 with distance, and $\gamma$ sets how fast it fades. It is the most common default.
• Sigmoid kernel, $K(x,z)=\tanh(\kappa\,x\cdot z+c)$: borrowed from neural networks, but it is positive semidefinite only for some values of $\kappa$ and $c$, as the previous experiment showed, so it is used with care^[12].

Kernels also exist for data that are not lists of numbers at all. String kernels compare two texts by the substrings they share^[11], and graph kernels compare molecules by their structure. Since the SVM only ever asks for $K$, it can classify any kind of object for which a valid similarity can be written down.

The popularity of the Gaussian kernel is easiest to see in one dimension. With it, the classifier $f(x)=\sum_i\alpha_iy_iK(x_i,x)+b$ is a sum of bumps, one centred on each support vector, pointing up for one class and down for the other, and the boundary lies where the sum crosses zero. Because bumps can be placed anywhere, the sum can follow a boundary of any shape, which is the practical meaning of an infinite-dimensional feature space. The value of $\gamma$ sets the width of each bump: a large $\gamma$ gives narrow bumps that wrap each training point separately and overfit, while a small $\gamma$ gives wide bumps that blur into an almost straight boundary.

借助这些规则，少数几种核函数就能满足大多数实际需要。每一种都体现了对“两个点有多相似”的不同理解：

• 线性核，$K(x,z)=x\cdot z$：完全不做特征映射。适合本身就有大量坐标的数据，例如用词频描述的文本，这时一个超平面通常就够了。
• 多项式核，$K(x,z)=(x\cdot z+c)^d$：特征空间包含不超过 $d$ 个坐标的全部乘积，因此能刻画特征之间的相互作用，例如两个词只有同时出现才有意义。
• 高斯核，又称 RBF 核，$K(x,z)=\exp(-\gamma\|x-z\|^2)$：两个点重合时相似度为 1，随距离增大逐渐降到 0，$\gamma$ 决定下降的快慢。它是最常用的默认选择。
• Sigmoid 核，$K(x,z)=\tanh(\kappa\,x\cdot z+c)$：借自神经网络，但正如上一个实验所示，它只在部分 $\kappa$、$c$ 取值下半正定，因此使用时要谨慎^[12]。

对于根本不是一列数字的数据，也有相应的核函数。字符串核按两段文本共有的子串来比较它们^[11]，图核则按分子的结构来比较两个分子。由于 SVM 只需要 $K$，任何能写出合格相似度的对象，它都能分类。

高斯核为什么如此常用，在一维中最容易看清。用高斯核时，分类器 $f(x)=\sum_i\alpha_iy_iK(x_i,x)+b$ 是一串鼓包之和，每个支持向量上各有一个，一类向上、另一类向下，边界就在总和穿过 0 的地方。鼓包可以放在任何位置，因此总和能贴合任何形状的边界，这就是“特征空间有无穷多维”在实际中的含义。$\gamma$ 决定每个鼓包的宽度：$\gamma$ 大时鼓包窄，把每个训练点单独包起来，造成过拟合；$\gamma$ 小时鼓包宽，彼此融成一条几乎平直的边界。

The playground below brings these ideas together on two-dimensional data. The settings interact: $C$ decides how much a violation costs, and $\gamma$ decides how flexible the boundary can be, so a flexible boundary with a high price for violations bends around every point, while a stiff boundary with a low price may ignore real structure. In practice both values are chosen by trying a grid of combinations and measuring accuracy on data held back from training, a procedure called cross-validation^[13].

下面的实验场在二维数据上把这些想法放到一起。几个设置相互影响：$C$ 决定违反约束的代价，$\gamma$ 决定边界有多灵活；边界很灵活、违反约束代价又高时，边界会绕着每个点打弯，边界僵硬、违反约束代价又低时，则可能忽略数据中真实存在的结构。实际中这两个值通常这样选定：在一张网格上尝试各种组合，用训练时预留出来的数据衡量准确率，这一做法称为交叉验证^[13]。

The ideas in this guide did not appear in the order in which they were presented. The maximum-margin line was proposed in the early 1960s under the name “generalized portrait”^[14], and at about the same time the potential function method already computed dot products in a feature space through a function of the original points^[15]; the mathematics of valid kernels goes back to Mercer in 1909^[9]. Over the following decades Vapnik and Chervonenkis developed a theory that bounds how far the error on new data can exceed the error on the training data^[16], and it explained why a wide margin should help. The pieces were combined only in 1992, when the kernel trick was applied to the maximum-margin classifier^[7], and the soft margin of 1995 made the method usable on noisy real data^[5].

From the mid-1990s until around 2010 the SVM was among the most widely used classifiers. Fast solvers such as SMO^[6] and libraries such as LIBSVM^[17] made it practical, and it matched the best methods of its time on handwritten digits^[18] and text categorization^[19]. The kernel idea spread to other methods as well, including regression^[20] and principal component analysis^[21].

Its limits also became clear. Training on $N$ points involves an $N\times N$ Gram matrix, so time and memory grow at least as fast as $N^2$, and the kernel still has to be chosen by hand. Deep neural networks, which learn their features from data and scale to millions of examples, overtook kernel methods on images from 2012^[22]. The kernel view did not disappear, however: random features approximate kernels at large scale^[23], and very wide neural networks trained by gradient descent behave like kernel machines with a particular kernel, the neural tangent kernel^[24].

本文中的各个想法，并不是按照本文介绍的顺序出现的。最大间隔的直线早在 20 世纪 60 年代初就以“广义肖像”之名被提出^[14]；差不多同一时期，势函数方法已经在用原始点的某个函数来计算特征空间中的点积^[15]；而合格核函数背后的数学，可以追溯到 Mercer 1909 年的工作^[9]。此后几十年间，Vapnik 与 Chervonenkis 发展出一套理论，给出新数据上的错误率最多比训练数据上的错误率高出多少的界^[16]，这解释了为什么宽间隔有帮助。直到 1992 年，这些部件才被组合起来，核技巧被用到最大间隔分类器上^[7]；1995 年的软间隔使这一方法能够用于带噪声的真实数据^[5]。

从 20 世纪 90 年代中期到 2010 年前后，SVM 一直是最常用的分类器之一。SMO 等快速求解算法^[6] 和 LIBSVM 等程序库^[17] 让它变得实用，它在手写数字识别^[18] 和文本分类^[19] 上与当时最好的方法不相上下。核函数的思想也扩展到其他方法，包括回归^[20] 和主成分分析^[21]。

它的局限也逐渐显现：在 $N$ 个点上训练要用到 $N\times N$ 的 Gram 矩阵，时间和内存至少按 $N^2$ 增长，而且核函数仍需人工选择。深度神经网络能从数据中自己学出特征，又能扩展到数百万个样本，从 2012 年起在图像任务上超越了核方法^[22]。不过，核方法的视角并没有消失：随机特征方法在大规模数据上近似核函数^[23]；而用梯度下降训练的极宽神经网络，表现得就像一台使用特定核函数的核机器，这个核函数称为神经正切核^[24]。

In the last link of this story, kernels were connected with today’s neural networks. The neural tangent kernel looks obscure, and although it is no longer widely used today, this guide still introduces it. Its name has three parts, explained one by one below.

A neural network is a function built from many simple units, loosely modelled on nerve cells, which is where the word “neural” comes from. In the simplest network the input $x$ goes to one layer of $m$ units. Unit $j$ computes $\max(0,\,w_jx+b_j)$ with its own numbers $w_j$ and $b_j$, and the output $f(x)$ adds up the units with weights $a_j$ and divides the sum by $\sqrt m$, which keeps it at a moderate size however many units there are. The output $f(x)$ is the network’s prediction for the input $x$; the loss is a separate number that compares predictions with the labels and measures the error. All the adjustable numbers are called the parameters of the network, and training adjusts them by gradient descent, nudging each parameter a little at a time in the direction that reduces the loss. The number of units in a layer is called the width. A wide network has a very large number of units in a layer, as opposed to a deep network, which has many layers.

在这段历史的最后一环，人们把核函数与今天的神经网络联系了起来。“神经正切核”看起来很晦涩，虽然在今天已经并不常用，但本文还是对其进行介绍。这个名字由三部分组成，下面逐一解释。

神经网络是由许多简单单元搭成的函数，这些单元粗略地模仿神经细胞，“神经”一词由此而来。在最简单的网络中，输入 $x$ 进入一层共 $m$ 个单元。第 $j$ 个单元用自己的数 $w_j$ 和 $b_j$ 计算 $\max(0,\,w_jx+b_j)$，输出 $f(x)$ 再用权重 $a_j$ 把各个单元加起来，并把总和除以 $\sqrt m$，使它无论有多少单元都保持适中的大小。输出 $f(x)$ 是网络对输入 $x$ 的预测；损失则是另一个数，它把预测与标签作比较，衡量误差有多大。这些可调的数统称为网络的参数，训练用梯度下降调整它们，也就是每次把每个参数朝减小损失的方向稍微挪动一点。一层中单元的个数称为宽度。宽网络的一层里有非常多的单元；与之相对，深网络有很多层。

Training such a network is hard to analyse. The parameters are searched over a vast landscape of hills and valleys, and in general it cannot be said in advance where the search will end, whether it will reach the lowest point, or how well the result will do on new data. For very wide networks, however, the question can be handed over to something already well understood, because such a network turns out to be a kernel machine in disguise. The translation takes four steps:

• The network: it takes a number $x$ and returns a number $f(x)$, computed with its parameters $\theta$. Each unit has three parameters, $w_j$, $b_j$ and $a_j$, so a layer of $m$ units has $3m$ of them.
• Gradient as feature map: for an input $x$, list for every parameter how much $f(x)$ would change if that parameter were nudged slightly. This list of $3m$ numbers, the gradient, is written $\varphi(x)$. It turns the single number $x$ into a point with $3m$ coordinates, so it is a feature map.
• Training as a linear model: when training moves the parameters by $\Delta\theta$, the output changes by about each slope times the corresponding move, added up, that is, by $\varphi(x)\cdot\Delta\theta$. Hence $f(x)\approx f_0(x)+\varphi(x)\cdot\Delta\theta$, where $f_0$ is the network before training: a linear model on the features $\varphi(x)$, with $\Delta\theta$ playing the role of $w$. This straight-line approximation of how the output responds to the parameters is what the word “tangent” refers to.
• Gradient descent as weights on training points: every step of gradient descent moves $\theta$ by a multiple of $\varphi(x_i)$ for each training point $x_i$, so the total move is $\Delta\theta=\sum_ic_i\,\varphi(x_i)$ for some numbers $c_i$. Substituting gives

This has the same form as the kernel SVM of Chapter 7: one weight per training point, multiplied by a kernel that compares the training point with the new input. The kernel $K$ is the neural tangent kernel^[24]. It helps to be precise about what each piece takes in and gives out:

• The kernel $K(x,z)$: it takes two inputs and returns one number, computed from the untrained network alone. The number says how much a training step aimed at the input $z$ moves the prediction at the input $x$.
• The kernel machine $f_0(x)+\sum_ic_iK(x_i,x)$: it takes a new input $x$ and returns a prediction, the same one the trained network would give. It stands for the trained network, not for the training process.
• The weights $c_i$: they are found from the training data and the kernel, and finding them corresponds to running gradient descent on the network.

Put together, the untrained network and the training data determine the predictions of the trained network, without the network ever being trained.

The translation uses the gradient of the untrained network, so it is accurate only if the slopes $\varphi(x)$ hardly change during training. This seems to contradict experience, since training turns a random network into one that fits the data. The way out is to tell apart the predictions and the individual parameters:

• The predictions do change a lot: the untrained network’s output has nothing to do with the data, while the trained one passes through the training points.
• Each individual parameter, however, changes only a little in a wide network. The output adds up $m$ units, so it is moved by all of them together, much as a heavy cart pushed by a crowd: the more people push, the less each one has to do. Because the sum is divided by $\sqrt m$, moving the output by a given amount needs each parameter to move by only about $1/\sqrt m$ of that amount; with $m=10\,000$ this is a hundredth.
• The slopes of unit $j$ depend only on its own parameters $w_j$, $b_j$ and $a_j$. When these hardly move, its slopes hardly change, and so the features $\varphi(x)$ stay as they were.

A wide network can therefore be treated as a kernel machine because width spreads the change that the output has to make, from the wrong predictions before training to the right ones after it, over so many parameters that each parameter, and with it each slope, barely moves. The experiment below shows the two quantities side by side.

训练这样的网络很难分析。参数要在一片高低起伏的广阔地形中搜索，一般无法事先说出搜索会停在哪里、能否到达最低点、结果在新数据上表现如何。然而对非常宽的网络，这个问题可以交给已经研究透彻的对象来回答，因为这样的网络其实是一台改头换面的核机器。转换要经过四步：

• 网络：输入一个数 $x$，返回一个数 $f(x)$，计算时用到它的参数 $\theta$。每个单元有 $w_j$、$b_j$、$a_j$ 三个参数，因此 $m$ 个单元共有 $3m$ 个参数。
• 梯度即特征映射：对输入 $x$，逐个列出每个参数稍微挪动一点时 $f(x)$ 会变化多少。这串 $3m$ 个数就是梯度，记作 $\varphi(x)$。它把单个数 $x$ 变成一个有 $3m$ 个坐标的点，因此是一个特征映射。
• 训练即线性模型：训练把参数挪动 $\Delta\theta$ 时，输出的变化约等于每个斜率乘以相应的挪动量再相加，也就是 $\varphi(x)\cdot\Delta\theta$。于是 $f(x)\approx f_0(x)+\varphi(x)\cdot\Delta\theta$，其中 $f_0$ 是训练前的网络。这是特征 $\varphi(x)$ 上的线性模型，$\Delta\theta$ 扮演了 $w$ 的角色。用直线近似输出对参数的反应，正是“正切”一词的含义。
• 梯度下降即训练点上的权重：梯度下降的每一步，都把 $\theta$ 沿每个训练点 $x_i$ 的 $\varphi(x_i)$ 挪动一个倍数，因此总的挪动量是 $\Delta\theta=\sum_ic_i\,\varphi(x_i)$，其中 $c_i$ 是一些数。代入后得到

这与第 7 章的核 SVM 形式相同：每个训练点一个权重，乘以一个把训练点与新输入作比较的核函数。这里的核函数 $K$ 就是神经正切核^[24]。各个部分输入什么、输出什么，需要分清：

• 核函数 $K(x,z)$：输入两个数，输出一个数，只用未训练的网络就能算出。这个数表示：针对输入 $z$ 做一步训练，会让输入 $x$ 处的预测移动多少。
• 核机器 $f_0(x)+\sum_ic_iK(x_i,x)$：输入一个新的 $x$，输出一个预测，与训练后的网络给出的预测相同。它代表的是训练后的网络，而不是训练过程。
• 权重 $c_i$：由训练数据和核函数求出；求出它们，相当于对网络做梯度下降。

合起来看，只凭未训练的网络和训练数据，就能确定训练后网络的预测，而无须真的训练网络。

这一转换用的是未训练网络的梯度，因此只有当斜率 $\varphi(x)$ 在训练中几乎不变时才准确。这似乎与经验相矛盾：训练把一个随机的网络变成了能拟合数据的网络，变化应该很大才对。解开矛盾的关键，是把预测和单个参数区分开：

• 预测确实变化很大：未训练网络的输出与数据毫无关系，训练后的网络则穿过了训练点。
• 但在宽网络中，每个单独的参数只改变一点点。输出是 $m$ 个单元之和，因此它是由所有单元一起推动的，就像一群人推一辆重车：推的人越多，每个人需要出的力就越小。由于总和除以了 $\sqrt m$，要让输出移动一定的量，每个参数只需移动这个量的大约 $1/\sqrt m$。$m=10\,000$ 时，这只是百分之一。
• 第 $j$ 个单元的斜率只取决于它自己的参数 $w_j$、$b_j$、$a_j$。这些参数几乎不动，它的斜率也就几乎不变，于是特征 $\varphi(x)$ 保持原样。

因此，宽网络之所以能等价为核机器，是因为宽度把输出所需的变化（从训练前错误的预测变成训练后正确的预测）分摊到极多的参数上，使每个参数以及每个斜率都几乎不动。下面的实验把这两个量并排显示出来。

Seen as a kernel machine, a wide network becomes predictable. Its trained output can be computed in advance from the kernel, without training; training is guaranteed to drive the error on the training points to zero, provided the table of kernel values between them has no zero eigenvalue; and the tools for kernel machines, such as the margin of Chapter 7, can be used to judge how well it will do on new data. This was among the first solid explanations of why a network with far more parameters than training points still trains successfully. The kernel can also be computed and used on its own, in an SVM or a similar method.

The view also marks a limit. A network that behaves like a kernel machine keeps the features it started with, so it can do no better than a kernel method with that kernel. The networks used in practice are not in this regime: their features change substantially during training, which means they learn features from the data. What makes them stronger than kernel methods is precisely this departure from the kernel regime.

看作核机器之后，宽网络就变得可以预测。训练后的输出可以直接由核函数算出来，不必真的训练；只要训练点之间的核函数值表没有为 0 的特征值，训练就一定能把训练点上的误差降到 0；核机器的分析工具，例如第 7 章的间隔，也可以用来判断它在新数据上表现如何。这是最早能够扎实解释“参数远多于训练点的网络为什么仍能训练成功”的理论之一。这个核函数本身也可以单独算出来，放进 SVM 或类似的方法中使用。

这一视角也划出了一条界线。表现得像核机器的网络，始终保留着它一开始的特征，因此它最多只能做到使用这个核函数的核方法那么好。实际使用的网络并不处在这种状态：它们的特征在训练中会大幅改变，也就是说，它们从数据中学到了特征。神经网络之所以比核方法更强，恰恰是因为它离开了这种核机器的状态。