3.6 可训练的确定性分类器的迭代算法

3.6.1 梯度法

定义

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

$$abla f(y) = \frac{d}{dy}f(y)=\left(\frac{\partial f}{\partial y_1},\frac{\partial f}{\partial y_2},\dots,\frac{\partial f}{\partial y_n}\right)^T$$

• 梯度是一个向量，它的最重要性质就是指出了函数f在其自变量y增加时最大增长率的方向

• 负梯度指出f的最陡下降方向

利用这个性质，可以设计一个迭代方案来寻找函数的最小值

采用梯度法求解的一般思想

首先，对于感知器算法而言

$$w (k + 1) = \begin{cases} w (k) & \text{if } w^T(k) x_k > 0 \\ w (k) + C x_k & \text{if } w^T(k) x_k \leq 0 \end{cases}$$

其中$w(k)$、$x_k$随着迭代次数$k$变化

接下来，定义一个对于错误分类敏感的准则函数$J(w,x)$。先任选一个初始权向量$w(1)$，计算准则函数$J$的梯度，然后从$w(1)$出发，在最陡方向（梯度方向）上移动某一距离得到下一个权向量$w(2)$ 。

类似的，可以得到从$w(k)$导出$w(k+1)$的一般关系式：

$$\begin{align} w(k+1) &= w(k) - C\left\{\frac{\partial J(w,x)}{\partial w}\right\}_{w=w(k)}\nonumber \\ &=w(k)-C\cdot\nabla J \end{align}$$

其中C是步长，为一个正的比例因子

讨论

• 若正确地选择了准则函数$J(w,x)$，则当权向量w是一个解时，J达到极小值（此时J的梯度为零）。由于权向量是按J的梯度值减小，因此这种方法称为梯度法（最速下降法）。

• 为了使权向量能较快地收敛于一个使函数$J$极小的解，C值的选择是很重要的：

  • 若C值太小，则收敛太慢

  • 若C值太大，则搜索可能过头，引起发散