[数学]第3章判别函数及几何分类法.ppt

2. 求W(k+1) 将 代入 得： 由此可以看出，感知器算法是梯度法的特例。即：梯度法是将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题，将原来有多个解的情况，变成求最优解的情况。 上式即为固定增量算法，与感知器算法形式完全相同 。 即： 只要模式类是线性可分的，算法就会给出解。 3.7 最小平方误差算法 （least mean square error, LMSE；亦称Ho-Kashyap算法） 上述的感知器算法、梯度算法、固定增量算法或其他类 似方法，只有当模式类可分离时才收敛，在不可分的情况下， 算法会来回摆动，始终不收敛。当一次次迭代而又不见收敛 时，造成不收敛现象的原因分不清，有两种可能： a) 迭代过程本身收敛缓慢 b) 模式本身不可分 对可分模式收敛。 对于类别不可分的情况也能指出来。 LMSE算法特点： 1. 分类器的不等式方程 两类分类问题的解相当于求一组线性不等式的解。如果给 出分属于 ， 两个模式类的训练样本集 ， 应满足： 其中，Xi是规范化增广样本向量， 。 上式分开写为： 写成矩阵形式为 ： 令N× (n+1) 的长方矩阵为X，则 变为： 式中： 0为零向量 感知器算法是通过解不等式组 ，求出W。 2. LMSE算法 1) 原理 的求解。式中： ∴ 两式等价。 为各分量均为正值的矢量。 LMSE算法把对满足 XW 0 的求解，改为满足 ① 在方程组中当行数列数时，通常无解，称为矛盾方程组，一般求近似解。在模式识别中，通常训练样本数N总是大于模 式的维数n，因此方程的个数(行数)模式向量的维数(列数)， 是矛盾方程组，只能求近似解W*，即 说明： ② LMSE算法的出发点：选择一个准则函数，使得当J达到最小值时，XW=B 可得到近似解（最小二乘近似解）。 ③ LMSE算法的思路： 转化为 转化为 准则函数定义为： “最小二乘”： —— 最小：使方程组两边误差最小， 也即使J最小。 —— 二乘：次数为2，乘了两次 最小平方（误差算法） 考察向量(XW－B) 有： 可以看出： ① 当函数J达到最小值，等式XW=B有最优解。即又将问题转化为求准则函数极小值的问题。 ② 因为J有两个变量W和B，有更多的自由度供选择求解，故可望改善算法的收敛速率。 XW=B 的近似解也称“最优近似解”： —— 使方程组两边所有误差之和最小（即最优）的解。 准则函数： 使J 对W求最小，令 ，得： 2) 推导LMSE算法递推公式 与问题相关的两个梯度： (3-46) (3-47) 由(3-47)式可知：只要求出B，就可求出W。 求递推公式： (1) 求W 的递推关系 X为N×(n+1)长方阵，X#为(n+1) ×N 长方阵。 称为X的伪逆， 式中： (3-45) (2) 求B(k+1)的迭代式 (3-46)代入，得 令 ，定义 (3-49) (3-50) (3-46) 利用梯度算法公式 有： (3) 求W(k+1)的迭代式 将(3-50)代入(3-47)式W=X#B 有： =0 (3-49) (3-50) 总结：设初值B(1)，各分量均为正值，括号中数字代表迭代次数 。 …… W(k+1)、B(k+1)互相独立，先后次序无关。 …… 求出B，W后，再迭代出下一个e，从而计算出新的B， W。 或另一算法：先算B(k+1)，再算W(k+1)。 3）模式类别可分性判别 ② 如果e(k)0 ，表明XW(k)B(k) 0， 隐含有解。继续迭代， 可使e(k) →0 。 ③ 如果e(k)0（所有分量为负数或零，但不全为零），停止迭 代，无解。此时若继续迭代，数据不再发生变化。 可以证明：当模式类线性可分，且校正系数c满足 时，该算法收敛，可求得解W。 理论上不能证明该算法到底需要迭代多少步才能达到收 敛，通常在每次迭代计算后检查一下XW(k) 和误差向量e(k) ， 从而可以判断是否收敛。 ① 如果e(k)=0 ，表明XW(k)=B(k) 0，有解。 分以下几种情况： 情况③分析： e(k)0