---

一、基于梯度的方法

梯度概念

设函数 $f(Y)$ 是向量 $Y=[y_1,y_2,\dots ,y_n{]}^T$ 的函数，则 $f(Y)$ 的梯度定义为：

$$\nabla f(Y)=\frac{d}{dY}f(Y)={\left[\begin{array}{c}\frac{\partial f}{\partial y_1},\frac{\partial f}{\partial y_2},\dots ,\frac{\partial f}{\partial y_n}\end{array}\right]}^T$$

梯度向量的重要性质之一：指出函数 $f(Y)$ 在其自变量增加时，增长最快的方向。即：

• 梯度的方向是函数 $f(Y)$ 在 $Y$ 点增长最快的方向，
• 梯度的模是 $f(Y)$ 在增长最快的方向上的增长率（增长率最大值）。

显然：负梯度指向了最快下降方向。——梯度算法的依据。
判断函数： 设两个线性可分的模式类别 ${\omega }_1$ 和 ${\omega }_2$ 的样本共有 $N$ 个，将两类样本分开的判别函数 $d(X)$ 应满足：

$$d(X_i)=W^T{X}_i>0,i=1,2,\dots ,N$$

即 $N$ 个不等式。梯度算法的目的是求一个满足上述条件的权向量，主导思想是将联立不等式求解 $W$ 的问题，转换成求准则函数极小值的问题。用负梯度方向的值对权向量 $W$ 进行修正，实现使准则函数达到极小值的目的。

基本思路：
定义一个对错误分类敏感的准则函数 $J(W,X)$，在 $J$ 的梯度方向上对权向量进行修正。一般关系表示成从 $W^{(k)}$ 导出 $W^{(k+1)}$：

$$W(k+1)=W(k)+c(-\nabla J)=W(k)-c\nabla J$$

即：

$$W(k+1)=W(k)-c{\left[\frac{\partial J(W,X)}{\partial W}\right]}_{W=W^{(k)}}$$

其中 $c$ 是正的比例因子。

---

梯度法求解步骤：

1. 将样本写成规范化增广向量形式，选择准则函数，设置初始权向量 $W(1)$，括号内为迭代次数 $k=1$。

2. 依次输入训练样本 $X$。设第 $k$ 次迭代时输入样本为 $X_i$，此时已有权向量 $W(k)$，求 $\nabla J(k)$：

$$\nabla J(k)=\frac{\partial J(W,X_i)}{\partial W}$$

权向量修正为：

$$W(k+1)=W(k)-c\nabla J(k)$$

迭代次数加 1，输入下一个训练样本，计算新的权向量，直至对全部训练样本完成一轮迭代。

3. 在一轮迭代中，如果有一个样本使 $\nabla J\ne 0$，回到步骤 2 进行下一轮迭代。否则，$W$ 不再变化，算法收敛。

---

例： 选择准则函数，$J(W,X)=|W^{T}X|-W^{T}X$，简单地考虑 $X$ 为一维增广模式的情况 $X=1$，此时 $W=w$，两者均为标量，

$$J(W,X)=|w|-w$$

错误分类时：

$$W^{T}X<0\Rightarrow w\cdot 1<0\Rightarrow w<0$$

$$\nabla J=\frac{\partial J(W,X)}{\partial W}=\frac{\partial (|w|-w)}{\partial w}=2w$$

$$W(k+1)=W(k)-c\cdot (-2)=W(k)+2c$$

正确分类时：

$$W^{T}X>0\Rightarrow w\cdot 1>0\Rightarrow w>0$$

$$\nabla J=\frac{\partial J(W,X)}{\partial W}=0$$

$$W(k+1)=W(k)$$
梯度下降法中的注意点

a) 权向量更新公式
权向量的更新公式为：

$$W(k+1)=W(k)-c\nabla J=W(k)-c{\left[\frac{\partial J(W,X)}{\partial W}\right]}_{W=W(k)}$$

随着权向量 $W$ 向理论值接近，准则函数关于 $W$ 的导数（$\nabla J$）越来越接近于零。这意味着准则函数 $J$ 越来越接近最小值。当最终 $\nabla J=0$ 时，$J$ 达到最小值，此时 $W$ 不再改变，算法收敛。

核心思想： 将感知器算法中联立不等式求解 $W$ 的问题，转换为求函数 $J$ 极小值的问题。

b) 比例因子 $c$ 的选择
比例因子 $c$ 的选取非常重要：

• 如果 $c$ 值太小，收敛速度会非常慢；
• 如果 $c$ 值太大，可能导致搜索过程震荡，甚至引起发散。

因此需要对 $c$ 进行适当的选择，确保算法稳定高效。

c) 梯度下降法的通用性
梯度算法是求解权向量的通用解法，具体计算形式取决于准则函数 $J(W,X)$ 的选择。根据 $J(W,X)$ 的形式不同，得到的具体算法也不同。

二、均方误差最小算法

回顾：收敛问题分析
在感知器算法、梯度算法、固定增量算法或其他类似方法中，仅当模式类可分离时才能收敛。在不可分的情况下，算法可能出现以下问题：

1. 算法回摆动，始终不收敛；
2. 一次次迭代后依然不见收敛。
   原因：

• a) 迭代过程本身收敛缓慢；
• b) 模式本身不可分。

LMSE 算法特点

• 对可分模式收敛。
• 对于类别不可分的情况，也能指出问题所在。

两类分类问题的线性不等式解
假设给出两类模式 ${\omega }_1$ 和 ${\omega }_2$ 的训练样本集 { X i , i = 1 , 2 , … , N } \{X_i, i = 1, 2, \dots, N\} {Xi​,i=1,2,…,N}，需要满足以下线性不等式：

$$W^T{X}_i>0,i=1,2,\dots ,N$$

其中，$X_i$ 为归一化增广样本向量，定义为：
$$X_i=[x_{i1},x_{i2},\dots ,x_{in},1{]}^T$$

展开形式
将上述不等式展开，可表示为：
$${\omega }_1\text{类:}\{\begin{array}{ll}{w}_1{x}_{11}+w_2{x}_{12}+\cdots +w_n{x}_{1n}+w_{n+1}>0& \text{对 }{X}_1\\ w_1{x}_{21}+w_2{x}_{22}+\cdots +w_n{x}_{2n}+w_{n+1}>0& \text{对 }{X}_2\\ ⋮& \\ {\omega }_2\text{类:}-w_1{x}_{N1}-w_2{x}_{N2}-\cdots -w_n{x}_{Nn}-w_{n+1}>0& \text{对 }{X}_N\end{array}$$

将线性不等式组表示为矩阵形式：令 $N\times (n+1)$ 的长方矩阵为 $X$，则 $W^T{X}_i>0$ 转化为：
$$XW>0$$
式中定义：

$$X={\left[\begin{array}{c}{X}_1^T\\ X_2^T\\ ⋮\\ X_i^T\\ -X_{N-1}^T\\ -X_N^T\end{array}\right]}_{N\times (n+1)}$$

$$W=[w_1,w_2,\cdots ,w_n,w_{n+1}{]}^T$$

感知器算法通过求解不等式组 $XW>0$ 来确定权向量 $W$。

其中：

• $X_1,X_2,\cdots ,X_i\in {\omega }_1$ 表示第一类样本，
• $X_{N-1},X_N\in {\omega }_2$ 表示第二类样本取负后包含在矩阵中，
• $0$ 为零向量。

LMSE算法把对满足 $XW>0$ 的求解，改为满足的求解。式中：

$$XW=B$$

$$B=[b_1,b_2,\cdots ,b_i,\cdots ,b_N{]}^T$$

为各分量均为正值的矢量。

说明：

1. 在方程组中当行数 $>>$ 列数时，通常无解，称为矛盾方程组，一般求近似解。在模式识别中，通常训练样本数 $N$ 总是大于模式的维数 $n$，因此方程的个数（行数） $>>$ 模式向量的维数（列数），是矛盾方程组，只能求近似解 $W^{\ast }$，即

$$\Vert X{W}^{\ast }-B\Vert =极小$$

2. LMSE算法的出发点：选择一个准则函数，使得当达到最小值时，$XW=B$ 可得到近似解（最小二乘近似解）。

准则函数定义为：

$$J(W,X,B)=\frac{1}{2}\Vert XW-B{\Vert }^2$$

3. LMSE算法的思路：

• 对 $XW>0$ 求解
  转化为
• 对 $XW=B$ 求解
  转化为
• 通过求准则函数极小值找 $W,B$

2. LMSE算法的出发点：
选择一个准则函数，使得当达到最小值时，$XW=B$ 可得到近似解（最小二乘近似解）。

准则函数定义为：
$$J(W,X,B)=\frac{1}{2}\Vert XW-B{\Vert }^2$$

---

3. LMSE算法的思路：

• 对 $XW>0$ 求解
  转化为
• 对 $XW=B$ 求解
  转化为
• 通过求准则函数极小值找 $W,B$

考察向量 $XW-B$ 有：

$$\Vert XW-B{\Vert }^2=(\text{向量各分量的平方和})=\text{向量各分量的平方和}$$
即：

$$\Vert XW-B{\Vert }^2=(W^T{X}_1-b_1{)}^2+\cdots +(W^T{X}_N-b_N{)}^2=\sum _{i=1}^N(W^T{X}_i-b_i{)}^2$$

准则函数

$$J(W,X,B)=\frac{1}{2}\Vert XW-B{\Vert }^2=\frac{1}{2}\sum _{i=1}^N{\left(W^T{X}_i-b_i\right)}^2$$

$XW=B$ 的近似解也称 “最优近似解”：
—— 使方程组两边所有误差之和最小（即最优）的解。

可以看出：

1. 当函数处到最小值，等式 $XW=B$ 有最优解。即又将问题转化为求准则函数极小值的问题。
2. 因为有两个变量 $W$ 和 $B$，有更多的自由度供选择求解，故可望改善算法的收敛速率。

---

与问题相关的两个梯度

对 $W$ 的梯度：
$$\frac{\partial J}{\partial W}=X^T(XW-B)$$

对 $B$ 的梯度：
$$\frac{\partial J}{\partial B}=-\frac{1}{2}[(XW-B)+XW-B]$$

---

(1) 求 $W$ 的递推关系

设梯度为 0，即：
$$\frac{\partial J}{\partial W}=0$$

则：
$$X^T(XW-B)=0⟹X^{T}XW=X^{T}B$$

因此：
$$W=(X^{T}X{)}^{-1}{X}^{T}B=X^{\#}B$$

其中：

• $X^{\#}=(X^{T}X{)}^{-1}{X}^T$ 称为 $X$ 的伪逆；
• $X$ 为 $N\times (n+1)$ 长方阵，$X^{\#}$ 为 $(n+1)\times N$ 长方阵。

(2) 求 $B^{(k+1)}$ 的迭代公式

根据梯度算法公式：
$$W^{(k+1)}=W^{(k)}-c{\left[\frac{\partial J(W,X)}{\partial W}\right]}_{W=W^{(k)}}$$

利用梯度算法对应到 $B$ 的公式：
$$B^{(k+1)}=B^{(k)}-c^{\prime }{\left[\frac{\partial J}{\partial B}\right]}_{B=B^{(k)}}$$

代入公式 (3-46)，得：
$$B^{(k+1)}=B^{(k)}+\frac{c^{\prime }}{2}\left[(X{W}^{(k)}-B^{(k)})+|X{W}^{(k)}-B^{(k)}|\right]$$

令 $\frac{c^{\prime }}{2}=c$，定义：
$$X{W}^{(k)}-B^{(k)}=e^{(k)}\text{\hspace{1em}(3-49)}$$

最终迭代公式为：
$$B^{(k+1)}=B^{(k)}+c\left[e^{(k)}+|e^{(k)}|\right]\text{\hspace{1em}(3-50)}$$
(3) 求 $W^{(k+1)}$ 的迭代式

由 $W^{(k+1)}=X^{\#}{B}^{(k+1)}$，代入公式 (3-50) 得：
$$W^{(k+1)}=X^{\#}\left\{B^{(k)}+c\left[e^{(k)}+e^{(k)}\right]\right\}$$

化简后：
$$W^{(k+1)}=W^{(k)}+c{X}^{\#}{e}^{(k)}$$

结合以下公式：
$$B^{(k+1)}=B^{(k)}+c\left[e^{(k)}+e^{(k)}\right]\text{\hspace{1em}(3-50)}$$

$$X{W}^{(k)}-B^{(k)}=e^{(k)}\text{\hspace{1em}(3-49)}$$

最终得出 $W^{(k+1)}$ 的迭代公式。

总结:

设初值 $B(1)$，各分量均为正值，括号中数字代表迭代次数。

$$W(1)=X^{\#}B(1)$$

$$e^{(k)}=X{W}^{(k)}-B^{(k)}$$

$$W^{(k+1)}=W^{(k)}+c{X}^{\#}{e}^{(k)}$$

$$B^{(k+1)}=B^{(k)}+c\left[e^{(k)}+e^{(k)}\right]$$

$W^{(k+1)}$、$B^{(k+1)}$ 互相独立，先后次序无关。

收敛性证明:
可以证明：当模式类线性可分，且校正系数 $c$ 满足 $0<c\le 1$ 时，该算法收敛，可求得解 $W$。
理论上不能证明该算法到底需要迭代多少步才能达到收敛，通常在每次迭代计算后检查一下 $X{W}^{(k)}$ 和误差向量 $e^{(k)}$，从而可以判断是否已收敛。

1. 如果 $e^{(k)}=0$，表明 $X{W}^{(k)}=B^{(k)}>0$，有解。

2. 如果 $e^{(k)}>0$，表明 $X{W}^{(k)}>B^{(k)}>0$，隐含有解。继续迭代，可使 $e^{(k)}\to 0$。

3. 如果 $e^{(k)}<0$（所有分量为负数或零，但不全为零），停止迭代，无解。此时若继续迭代，数据不再发生变化。

三、支持向量机 (SVM)

1. 算法原理

支持向量机（Support Vector Machine, SVM）是一种用于分类和回归的监督学习算法，其主要目标是寻找一个超平面将不同类别的数据分开，同时最大化分类间隔（margin）。

(1) 问题描述

给定一个训练数据集：

$$D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$$

其中，$x_i\in {\mathbb{R}}^n$ 是特征向量， y i ∈ { − 1 , + 1 } y_i \in \{-1, +1\} yi​∈{−1,+1} 是类别标签。

目标是找到一个超平面：
$$w^{T}x+b=0$$

使得超平面最大化分类间隔，并满足：

$$y_i(w^T{x}_i+b)\ge 1,i=1,2,\dots ,N$$

其中，$w$ 是超平面的法向量，$b$ 是偏置。

(2) 优化问题

最大化分类间隔等价于最小化 $w$ 的范数。优化问题可表示为：

原始问题：
$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2$$
约束条件：
$$y_i(w^T{x}_i+b)\ge 1,i=1,2,\dots ,N$$

对偶问题：
通过拉格朗日乘子法，将问题转化为对偶形式：
$$\underset{\alpha }{\max }\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$
约束条件：
$$\sum _{i=1}^N{\alpha }_i{y}_i=0,{\alpha }_i\ge 0,i=1,2,\dots ,N$$

(3) 核方法（非线性分类）

若数据不可线性分离，可以通过核函数将数据映射到高维空间。常用的核函数包括：

1. 线性核：$K(x_i,x_j)=x_i^T{x}_j$
2. 多项式核：$K(x_i,x_j)=(x_i^T{x}_j+c{)}^d$
3. 高斯核（RBF）：$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$

通过核函数，优化问题中的 $x_i^T{x}_j$ 替换为 $K(x_i,x_j)$。

---

示例

假设训练数据为：
$$D=\{(x_1=[2,3],y_1=1),(x_2=[1,1],y_2=-1)\}$$

(1) 构造优化问题
超平面形式：
$$w^{T}x+b=0$$

优化目标：
$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2$$
约束条件：
$$y_1(w^T{x}_1+b)\ge 1,y_2(w^T{x}_2+b)\ge 1$$

替换数据：
$$1\cdot ((w_1\cdot 2+w_2\cdot 3)+b)\ge 1$$
$$-1\cdot ((w_1\cdot 1+w_2\cdot 1)+b)\ge 1$$

约束变为：
$$2w_1+3w_2+b\ge 1$$
$$-w_1-w_2-b\ge 1$$

(2) 对偶问题

通过求解对偶问题，计算拉格朗日乘子 ${\alpha }_i$，得到解：
$$w=[0.4,0.6],b=-1.2$$

(3) 分类决策

分类决策函数：
$$f(x)=\text{sign}(w^{T}x+b)$$

对新数据点 $x=[3,4]$ 进行分类：
$$f(x)=\text{sign}([0.4,0.6{]}^T[3,4]-1.2)$$
$$f(x)=\text{sign}(0.4\cdot 3+0.6\cdot 4-1.2)=\text{sign}(3.6)=+1$$

因此，$x=[3,4]$ 的分类结果为正类。