什么是向量点乘？

在手撕 SVM 之前，首先问一个问题，向量点乘的意义是什么？

这个问题不难回答，向量点乘其实就是两个向量的长度乘以它们夹角的余弦，数学上来说就是：

$$a \cdot b = \|a\|\|b\|\cos\theta$$

那么这个结论是怎么推导出来的呢？

公式上的推导

考虑构建一个三角形，这个三角形的两个边分别是向量 $a$ 表示的边 $A$ 向量 $b$ 表示的边 $B$，另一条边 $C$ 由 $b-a$ 表示，代表从 $a$ 向量的末端指向 $b$ 向量的末端的向量。根据余弦定理（余弦定义是勾股定理在一般三角形下的推广，也是通过勾股定理来证明的，即 $c^2=a^2 + b^2-2ab\cos\theta$，此处不再证明），有

$$C^2=A^2 + B ^ 2-2AB\cos \theta$$

通过向量来表示长度，可得：

$$(b-a)^2 = a^2 + b ^2 - 2\|a\|\|b\|\cos \theta$$

因点乘对加法保有分配律，以及点乘满足交换律（数量积 - 维基百科，自由的百科全书），故：

$$(b-a)^2=(b-a)b -(b-a)a=b^2-ab-ba +a^2=a^2-2ab-b^2$$

将此式与上式结合可得：

$$a^2-2ab-b^2=a^2+b^2-2\|a\|\|b\|\cos \theta$$

即：

$$ab=\|a\|\|b\|\cos \theta$$

证毕。我们同时可以把向量的点乘看作向量 $b$ 在 向量 $a$ 方向的投影长度乘以向量 $a$ 的长度。

几何意义上的推导

事实上，点积的计算方式利用到了对称性。熟悉线性代数的都清楚，矩阵的本质是一种线性变换，矩阵的每一列都代表变换后空间的基，因此矩阵本身即表示一组基。在默认线性空间下，我们的基是由各个方向上的单位向量来表示，因此任何一个通过该组基所表示的坐标，都可以表示成向量的形式，向量的每一维表示了此向量在该维度上的分量。当将一个向量变换到新的线性空间后，我们并不期望向量本身与基的关系发生变化（即我们希望保有原向量与原线性空间下各个基的关系），因此从新线性空间的角度来看，此向量在各个新基上的分量仍然保持不变，也即不需要进行计算（取决于你怎么看待这个向量）。但是为了从默认线性空间来表示变化后向量的位置，我们需要将表示该线性变换的矩阵乘以该向量，以得出从原线性空间的角度来看，变化后的向量如何通过原线性空间下的各个单位向量来表示。

既然矩阵是一种线性变化，那么如果我们把向量 $a$ 看作只有一维的矩阵，那么一个向量也可以表示一种线性变换，只不过其把空间压缩到了一维（一条直线），向量的每一个分量表示新的基。

考虑我们想要构建一种线性变换，其把任意维度空间压缩到一维空间，压缩的方式是把该空间的向量投影到此一维空间中，那么应该如何计算呢？首先考察原空间中的基。我们以二维空间为例：

原空间中的基将被此线性变换映射到新空间所对应的基，由于新空间为一维空间，所以是一个标量，那么这个标量的值为多少呢？因为线性变换为投影，我们可以如上图取基 $i$ 方向与线性变换向量 $a$ 的中轴，根据对称性原理，我们很容易就能发现映射后的长度，也就是标量值，正是 $a$ 方向上的单位向量 $u$ 在水平轴上的坐标，由此我们可得 $u$ 为代表投影的线性变换。据此，我们有：

$$a \cdot b = (\|a\| u) \cdot b=\|a\|(ub) =\|a\|\|b\|\cos \theta$$

证毕。同时我们不难发现，当向量 $a$ 与向量 $b$ 垂直时，由于 $\cos\theta=0$，所以 $a\cdot b=0$，因此我们可以得知当两个非零向量的点积为 0 时，这两个向量垂直。

注：此部分内容参考自线性代数的本质 - 系列合集。

如何表示一个超平面？

有了以上内容作为铺垫，我们可以思考下面这个问题：如何表示一个超平面？平面的特殊性在于其平，换句话说，任何超平面都存在法向量。我们设一个超平面的法向量为 $w^\intercal$，那么不难发现，通过从原点指向该平面上任意点所表示的向量到法向量上的投影都是一个定值。由于投影可以通过点积来表示，那么这个值就为 $\frac{w^\intercal x}{|w^\intercal|}$，为一个标量，我们设这个值为 $b$，那么可得此超平面的方程为：

$$\frac{w^\intercal x}{\|w^\intercal\|}-b=0$$

通过移项可以得到：

$$w^\intercal x-{\|w^\intercal\|}b=0$$

由于 $-{|w^\intercal|}b$ 为一个标量，将其视为新的 $b$，可得最终平面的方程为：

$$w^\intercal x + b=0$$

任意一个点所表示的向量在平面法线方向投影的长度为 $\frac{w^\intercal x}{|w^\intercal|}$，通过移项我们可以得到，平面上的任意点所表示的向量在法线方向投影的长度为 $-\frac{b}{|w^\intercal|}$，结合这两个长度，可以得出任意一点到平面的距离为两个距离的差，也就是：

$$d=\frac{w^\intercal x}{\|w^\intercal\|} - \left( -\frac{b}{\|w^\intercal\|} \right)= \frac{w^\intercal x+b}{\|w^\intercal\|}$$

狭义的距离（几何间隔）为 $\frac{|w^\intercal x+b|}{|w^\intercal|}$。

支持向量机

支持向量机的规范化

支持向量机的想法很朴素，就是最大化支持向量到分类平面的距离。设支持向量机在参数为 $w,b$ 下的最小距离为 $d^{w,b}$，我们首先考察支持向量机的约束，即：

$$\left\{ \begin{aligned} \frac{w^\intercal x+b}{\|w^\intercal\|} & > d^{w,b} &, y=1 \newline \frac{w^\intercal x+b}{\|w^\intercal\|} & < -d^{w,b} &, y=-1 \newline \end{aligned} \right .$$

稍作变换可以得到：

$$y (w^\intercal x + b) > \|w^\intercal\|d^{w,b}$$

由于 $w^\intercal x+b=0$ 与 $2w^\intercal x+2b=0$ 所表示的是同一个超平面，所以理论上可能有无数组满足要求的 $w,b$ 参数对。我们可以对 $|w^\intercal|$ 约束为一个常量，来保证我们只选择一组参数对。由于在这些组参数中，$d^{w,b}$ 其实是不变的，因为其是几何距离，所以约束 $|w^\intercal|d^{w,b}$ 其实和单独约束 $|w^\intercal|$ 等价，因此，我们可以添加一个等式约束，也就是我们设 $|w^\intercal|d^{w,b}$ 恒等于 1，由此可得我们的约束变成了：

$$y (w^\intercal x + b) > 1$$

再考察我们的目标函数，其为：

$$\max_{w,b} d^{w,b}$$

由于我们加了等式约束 $|w^\intercal|d^{w,b}=1$，因此：

$$\max_{w,b} d^{w,b}= \frac{ d^{w,b}}{\|w^\intercal\|d^{w,b}}=\frac{1}{\|w^\intercal\|}$$

最后再做一个转换，可以把目标函数表达为：

$$\min_{w,b} \frac{1}{2}\|w^\intercal\|^2$$

目标函数与约束条件合起来要表达的其实就是，在保证函数间隔大于 1 的情况下，最小化参数的范数，这样才能使得几何间隔变得更大。

支持向量机的求解

先通过对偶转换为等式约束问题，然后再通过拉格朗日乘子法转化为无约束优化问题。