第三章 判别函数分类器.ppt

第三章判别函数分类器 矢量 矢量X可以看作是N维欧氏空间中的一个点 用一个列矢量表示 矩阵 矩阵可以看作是由若干个矢量构成的 矩阵的秩 矩阵所有行向量的最大无关组个数称为行秩 矩阵所有列向量的最大无关组个数称为列秩 一个矩阵的行秩等于列秩 称为矩阵的秩 转置 列矢量W的转置WT为一个行矢量 N M的矩阵A的转置AT为一个M N的矩阵 矢量与矢量的乘法 1 设W和X为N维列矢量 结果是一个数 矢量与矢量的乘法 2 设W和X为N维列矢量 结果是一个N N维的矩阵 矢量与矩阵的乘法 设W为N维列矢量 A为一个N M的矩阵 结果是一个N维列矢量 正交 设W和X为N维列矢量 如果W与X的内积等于零 则称W与X正交 也称W垂直于X 逆矩阵 A为一个N N的方阵 A的逆阵用A 1表示 满足 其中I为单位阵 一个矩阵的逆阵存在条件 1 是一个方阵 2 是一个满秩矩阵 矩阵的秩为N 矩阵的特征值和特征向量 A为一个N N的方阵 如果有 数 称为A的特征值 矢量 称为A的特征矢量 矩阵的迹和行列式值 A为一个N N的方阵 A的迹为主对角线元素之和 A为一个N N的方阵 A的迹为主对角线元素之和 矩阵的迹 行列式值与特征值之间的关系 矩阵A有N个特征值 1 2 N 则有如下关系 矩阵对数值变量微分 矩阵A t aij t M N 元素aij t 是变量t的函数 矩阵A t 对t的微分 矩阵函数对矩阵的微分 矩阵X xij M N M N元函数f X 定义f X 对矩阵X的导数 常用矢量微分的性质 X和W为N维矢量 A为M N的矩阵 3 1线性判别函数 一 两类问题二 多类问题 两类问题的线性判别函数 X0 x1 x2 xN T为待识模式的特征矢量 W0 w1 w2 wN T称为权矢量 线性判别函数的增广形式 X x1 x2 xN 1 T称为增广的特征矢量 W w1 w2 wN 1 T称为增广的权矢量 两类问题线性判别准则 多类问题 情况一 每一类模式可以用一个超平面与其它类别分开 这种情况可以把M个类别的多类问题分解为M个两类问题解决 多类问题 情况一 多类问题 情况一 判别规则 当d1 X 0 而d2 X 0且d3 X 0时 判别X属于 1 当d2 X 0 而d1 X 0且d3 X 0时 判别X属于 2 当d3 X 0 而d1 X 0且d2 X 0时 判别X属于 3 其它情况 拒识 多类问题 情况二 每两类之间可以用一个超平面分开 但是不能用来把其余类别分开 需要将M个类别的多类问题转化为M M 1 2个两类问题 第i类与第j类之间的判别函数的为 多类问题 情况二 判别准则 如果对任意j i 有dij X 0 则决策X属于 i 其它情况 则拒识 多类问题 情况二 多类问题 情况三 情况三是情况二的特例 不存在拒识区域 多类问题 情况三 判别函数 M个类别需要M个线性函数 判别准则 3 2两类别线性判别函数的学习 一 问题的表达二 感知器算法三 最小均方误差算法 LMSE 问题的表达 已知两个类别的训练样本集合 求向量W 使得d X WTX 能够区分 1类和 2类 问题的表达 矩阵形式描述 X称为增广矩阵 权矢量的解 只有当样本集线性可分的条件下 解才存在 线性不等式组的解是不唯一 感知器算法的思想 感知器算法 初始化 置W 1 中的元素为一个小的随机数 在第k步学习训练样本Xk 按照如下公式修正权值W 重复第2步 直到所有训练样本被正确识别 LMSE算法的思想 此方法也称为Ho Kashyap算法 H K算法 将线性不等式组XW 0的问题 转化为解线性方程组XW B的问题 其中 B b1 b2 bN T bi 0 问题求解 已知 增广矩阵X 可由训练样本集得到 求 W和B X一般不是方阵 所以问题实际上无解 只能求近似解 优化的准则函数 定义误差矢量e 定义准则函数J W B 梯度法求解 上面两个公式成立的W即为所求 定义伪逆矩阵X H K算法 由训练样本集计算X X XTX 1XT 初始化B 0 每个分量是一个小的正值 选常数C 置k 0 计算W k X B k e k XW k B k 若e k 0 停止迭代 输出W W k 若e k 0 停止迭代 线性不可分 其它情况 继续第5步 H K算法 迭代计算 k k 1 返回第3步 继续 3 3多类别线性判别函数的学习 情况一 M类问题转化为M个两类问题 i样本作为一类 其它样本作为另一类进行训练 情况二 M类问题问题转化为M M 1 2个两类问题 i样本作为一类 j样本作为另一类 训练Wij 多类问题情况三 采用扩展的感知器算法初始化L个权向量Wi 1 选择常数C 置步数k 1 输入增广特征矢量Xk 计算L各判别函数的输出 扩展的感知器算法 修改权矢量 规则为 若Xk属于 i 并且di Xk dj Xk 对任意的j i 则 Wi k 1 Wi k i 1 L若Xk属于 i 而dl Xk dj Xk 则 Wi k 1 Wi k CXk Wl k 1 Wl k CXkWj k 1 Wj k j I l 扩展的感知器算法 重复2 3步 当k M时 检测L个判别函数是否能够对全部训练样本正确分类 如正确分类 则结束 否则k 1 转2 继续 3 4非线性判别函数的学习 一 二次判别函数二 分段线性函数三 其它非线性判别函数方法 XOR