感知机：补充【统计学习方法】

点到超平面距离公式的推导过程

中学学过二维空间中点到直线的距离公式

已知点$P(x_0,y_0)$，直线$Ax+By+C=0$，求点$P$到直线$l$的距离 点$P$到直线的距离是点$P$到直线$l$的垂线段的长，设点$P$到直线的垂线垂足为$Q$，由$l$垂直$l'$可知$l'$的斜率为$\frac BA$ $\therefore l'$的方程：$y-y_0=\frac BA(x-x_0)$ 解得交点$\begin{aligned}Q(\frac{B^2x_0-ABy_0-AC}{A^2+B^2},\frac{A^2y_0-ABx_0-BC}{A^2+B^2})\end{aligned}$ $\begin{aligned}|PQ|^2=(\frac{B^2x_0-ABy_0-AC}{A^2+B^2}-x_0)^2+(\frac{A^2y_0-ABx_0-BC}{A^2+B^2}-y_0)^2=\frac{(Ax_0+By_0+C)^2}{A^2+B^2}\end{aligned}$ $\begin{aligned}\therefore|PQ|=\frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}}\end{aligned}$

类似的，推导点到超平面距离公式

已知$\boldsymbol S$为$n$维欧式空间中的$n-1$维超平面$w\cdot x+b=0$，其中$w$和$x$均为$n$维向量；另有$n$维空间中的点$x_0=(x_0^{(1)},x_0^{(2)},\cdots,x_0^{(n)})$。 求证：点$P$到超平面$\boldsymbol S$的距离$d=\frac1{||w||}|w\cdot x_0+b|$，其中$||w||$为$w$的欧式范数 证明： 由超平面$\boldsymbol S$的定义式可知$w$为超平面$\boldsymbol S$的法向量，$b$为超平面$\boldsymbol S$的截距 设点$x_0$在超平面$\boldsymbol S$的投影为$x_1=((x_1^{(1)},x_1^{(2)},\cdots,x_1^{(n)}))$，则有 $$w\cdot x_1+b=0\tag1$$ 点P到超平面$\boldsymbol S$的距离$d$即为向量$\overrightarrow{x_0x_1}$的长度 因为$\overrightarrow{x_0x_1}$与超平面$\boldsymbol S$的法向量$w$平行，所以$\overrightarrow{x_0x_1}$与法向量夹角的余弦值$\cos\theta=0$，故有 $$\begin{aligned}w\cdot\overrightarrow{x_0x_1}&=|w||\overrightarrow{x_0x_1}|\cos\theta\&=|w||\overrightarrow{x_0x_1}|\&=[(w^{(1)})^2+(w^{(2)})^2+\cdots+(w^{(n)})^2]^{\frac12}d\&=||w||d\end{aligned}\tag2$$ 又有（应用向量点积的分配律） $$\begin{aligned}w\cdot\overrightarrow{x_0x_1}&=w^{(1)}(x^{(1)}_1-x^{(1)}_0)+w^{(2)}(x^{(21)}_1-x^{(2)}_0)+\cdots+w^{(n)}(x^{(n1)}_1-x^{(n)}_0)\&=(w^{(1)}x^{(1)}_1+w^{(2)}x^{(2)}_1+\cdot+w^{(n)}x^{(n)}_1)-(w^{(1)}x^{(1)}_0+w^{(2)}x^{(2)}_0+\cdot+w^{(n)}x^{(n)}_0)\&=w\cdot x_1-w\cdot x_0\end{aligned}\tag3$$ 由式$(1)$，有$w\cdot x_1=-b$，故式$(3)$可以写成 $$\begin{aligned}w\cdot\overrightarrow{x_0x_1}&=w\cdot x_1-w\cdot x_0\&=-b-w\cdot x_0\end{aligned}\tag4$$ 由式$(2)$和式$(4)$，得 $$\begin{gathered}||w||d=|-b-w\cdot x_0|\d=\frac1{||w||}|w\cdot x_0+b|\end{gathered}$$ 证毕

梯度下降法

概念

梯度：某一函数在该点处最大的方向导数，沿着该点方向可取得最大的变化率 $$\nabla=\frac{\partial f(\theta)}{\partial\theta}$$ 若$f(\theta)$是凸函数，可通过梯度下降法进行优化 $$\theta^{(k+1)}=\theta^{(k)}-\eta\nabla f(\theta^{(k)})$$

算法

输入：目标函数$f(\theta)$，步长$\eta$，计算精度$\epsilon$ 输出：$f(\theta)$的极小值点$\theta^*$

1. 选取初始值$\theta^{(0)}\in\boldsymbol R^n$，置$k=0$
2. 计算$f(\theta^{(k)})$
3. 计算梯度$\nabla f(\theta^{(k)})$
4. 置$\theta^{(k+1)}=\theta^{(k)}-\eta\nabla f(\theta^{(k)})$，计算$f(\theta^{(k+1)})$ 当$||f(\theta^{(k+1)})- f(\theta^{(k)})||<epsilon$或者$||\theta^{(k+1)}-\theta^{(k)}||<\epsilon$时，停止迭代，令$\theta^*=\theta^{(k+1)}$
5. 否则，置$k=k+1$，转3.

原理

泰勒展开： $$f(\theta)\approx f(\theta^{(k)})+(\theta-\theta^{(k)})\nabla f(\theta^{(k)})$$

$\theta-\theta^{(k)}$的单位向量用$v$表示，$\eta'$为标量 $$\theta-\theta^{(k)}=\eta' v$$ 重新表达 $$f(\theta)\approx f(\theta^{(k)})+\eta' v\cdot\nabla f(\theta^{(k)})$$ 更新$\theta$使函数值变小 $$f(\theta)- f(\theta^{(k)})\approx\eta' v\cdot\nabla f(\theta^{(k)})<0\Rightarrow v\cdot\nabla f(\theta^{(k)})<0$$ 互为反向使下降最快，有 $$v=-\frac{\nabla f(\theta^{(k)})}{||\nabla f(\theta^{(k)})||}$$ 更新$\theta$ $$\theta^{(k+1)}=\theta^{(k)}-\eta'\frac{\nabla f(\theta^{(k)})}{||\nabla f(\theta^{(k)})||}$$ 化简 $$\theta^{(k+1)}=\theta^{(k)}-\eta\nabla f(\theta^{(k)})$$

一定存在$||\hat w_{opt}||=1$

不妨设超平面的扩充权重向量为 $$\hat w_{opt}'=(\hat w_{opt}'^T,b')^T=(w_{opt}'^{(1)},w_{opt}'^{(2)},\cdots,w_{opt}'^{(n)},b')^T$$ 有$||\hat w_{opt}'||\ne1$，于是有 $$\hat w_{opt}=(\frac{\hat w_{opt}'^{(1)}}{||\hat w_{opt}'||},\frac{\hat w_{opt}'^{(2)}}{||\hat w_{opt}'||},\cdots,\frac{\hat w_{opt}'^{(n)}}{||\hat w_{opt}'||},\frac{b'}{||\hat w_{opt}'||})^T$$ 此时，存在$\hat w_{opt}$令$||\hat w_{opt}||=1$ 证毕