3第三章线性判别函数

第三章线性判别函数郝红卫 1 第三章线性判别函数 3 1引言3 2线性判别函数和决策面3 3广义线性判别函数3 4两类线性可分情况3 5梯度下降算法3 6感知准则函数最小化3 7松弛算法3 8最小平方误差方法 第三章线性判别函数郝红卫 2 引言 贝叶斯公式中需要知道类条件概率密度函数和先验概率在实际中 我们通常只能得到有限数目的样本因此 分类器的设计过程可以分为两步 利用样本集估计先验概率和类条件概率密度函数将估计值代入贝叶斯公式 完成分类器设计 第三章线性判别函数郝红卫 3 引言 先验概率的估计 比较容易 比如 癌细胞识别中 可以根据细胞病理检查的统计结果得到正常与异常的大致比例 密度函数的估计 非常困难 只能根据样本进行估计 第三章线性判别函数郝红卫 4 引言 解决的思路 迎难而上参数估计 假定密度函数是种分布 即分布形式已知但参数未知 通过训练样本估计分布的参数比如 假定分布为正态 可以利用样本估计其均值和方差 非参数方法 分布的形式未知 直接通过样本估计密度函数的形式和参数另辟蹊径 第三章线性判别函数郝红卫 5 引言 在对正态分布下贝叶斯决策理论的讨论中 我们看到 在正态假设下 可以得到一些简单方便的判别函数 如 最小距离 线性判别函数 我们可以绕过对密度的估计 直接得到判别函数在所有的判别函数中 最简单的是线性判别函数 第三章线性判别函数郝红卫 6 引言 线性判别函数的优点 特定条件下为最优正态 独立 等方差 可以通过对特征的选择来达到相对简单 容易实现牺牲精度 享受简便 性能和代价的折中是复杂方法的基础线性判别函数中的基本方法可以推广到非线性判别函数中 第三章线性判别函数郝红卫 7 引言 思路 假定判别函数的形式已知 线性判别函数未知的是判别函数的参数参数由样本约束 合适的参数将使错误率最小通过训练样本确定其参数 找出使训练样本错误率最小的参数 最优化方法 第三章线性判别函数郝红卫 8 引言 设计线性分类器的主要步骤 根据需求确定准则函数 使准则函数的值反映分类器的性能 如错误率 其极值解对应最优决策用最优化技术求出准则函数的极值解将该极值解代入线性判别函数的表达式中 完成分类器的设计 第三章线性判别函数郝红卫 9 线性判别函数和决策面 线性判别函数是x各分量的线性组合 g x wtx w0其中x x1 x2 xd t是d维特征向量w w1 w2 wd t是d维权向量 weightvector w0为常数 称为偏置 bias 或阈值权 thresholdweight 第三章线性判别函数郝红卫 10 线性判别函数和决策面 通常 我们需要设计c个判别函数 分别与c个类别相对应先来看两类的情况 Decide 1ifg x 0and 2ifg x w0and 2otherwise 第三章线性判别函数郝红卫 11 线性判别函数和决策面 第三章线性判别函数郝红卫 12 线性判别函数和决策面 方程g x 0定义了一个决策面 它将分属两类的样本分开 假设x1和x2都在决策面H上 则有 wtx1 w0 wtx2 w0wt x1 x2 0这表明 w和超平面H上任一向量正交 即w是H的法向量 超平面H将特征空间分成两部分 即对 1类的决策域R1和对 2类的决策域R2 由于当x在R1中时 g x 为正 所以法向量是指向R1的 故称R1中的x在H的正侧 称R2中的x在H的负侧 第三章线性判别函数郝红卫 13 线性判别函数和决策面 判别函数g x 是特征空间中某点到超平面距离的一种代数度量 如图所示 第三章线性判别函数郝红卫 14 线性判别函数和决策面 可以将x表示成其中xp 是x在H上的投影向量r 是x到H的垂直距离w w 是w方向上的单位向量 第三章线性判别函数郝红卫 15 线性判别函数和决策面 代入g x 或写作 第三章线性判别函数郝红卫 16 线性判别函数和决策面 若x为原点 则g x w0因此原点到超平面H的距离为r0 w0 w 总之 利用线性判别函数进行分类 就是用一个超平面把特征空间分割成两个决策区域 超平面的方向由权向量w确定 超平面的位置由阈值权w0确定 判别函数正比于x到超平面的代数距离 带正负号 当x在超平面正侧时 g x 0 在负侧时 g x 0 第三章线性判别函数郝红卫 17 线性判别函数和决策面 多类情况可以把c类问题看做c个两类问题 其中第i个问题是用线性判别函数把属于 1类的点与不属于 1类的点分开可以用c c 1 2个线性判别函数 把样本分成c个类别 每个线性判别函数只对其中的两个类别分类 两种方法都会产生无法确定其类别的区域 如图所示 第三章线性判别函数郝红卫 18 线性判别函数和决策面 第三章线性判别函数郝红卫 19 线性判别函数和决策面 我们可以定义c个判别函数如果对于所有的j i有gi x gj x 则把x归为 i类 如果gi x gj x 则拒识 这样得到的分类器称为 线性机器 linearmachine 线性机器把特征空间分成c个决策区域 当x在Ri中时 gi x 具有最大值 如果Ri和Ri是相邻的 则它们的分界就是超平面H的一部分 其定义为gi x gj x 第三章线性判别函数郝红卫 20 线性判别函数和决策面 共有c个决策区域 实际中 超平面的个数往往会少于c c 1 2个 如图所示 第三章线性判别函数郝红卫 21 广义线性判别函数 线性判别函数可以写成通过增加高次项 可以得到二次判别函数 quadraticdiscriminantfunction 第三章线性判别函数郝红卫 22 广义线性判别函数 继续增加更高次的项 得到多项式判别函数 polynomialdiscriminantfunction 这可以看作对某一判别函数做级数展开 然后取其截尾逼近 由此得到广义线性判别函数 generalizedlineardiscriminantfunction 或 第三章线性判别函数郝红卫 23 广义线性判别函数 在中 yi x 可以是x的任意函数 通过选择合适的y 就可以逼近任意复杂的判别函数 得到的判别函数并不是x的线性函数 但却是y的线性函数 虽然理论上我们可以通过这种方式来解决非线性问题 但这种变换却使得维数大大增加 陷入 维数灾难 第三章线性判别函数郝红卫 24 广义线性判别函数 其中一个特例却是有用的 我们可以把线性判别函数写成如下的形式式中y称为增广样本向量 a称为增广权向量 这样做带来的好处是将两个参数w和w0合并成一个参数a 第三章线性判别函数郝红卫 25 两类线性可分情况 线性可分设有一个包含n个样本的集合 y1 y2 yn 其中某些样本为 1类 某些为 2类 如果有一个线性机器能把每个样本正确分类 即如果存在一个权向量a 使得对于任何y 1都有aty 0 而对于任何y 2都有aty 0 则称这组样本集是线性可分的 否则称为线性不可分的 反之 如果样本集线性可分 则必存在一个权向量a 能将每个样本正确分类 第三章线性判别函数郝红卫 26 两类线性可分情况 样本的规范化样本线性可分 则必存在某个权向量a 使得如果在来自 2类的样本前面加上一个负号 即对yj 2 令yj yj 则也有atyj 0 因此 如果我们令则就可以不管样本原来的类别标志 只要找一个对全部样本yn 都满足atyn 0的权向量a即可 上述过程称为样本的规范化 yn 叫规范化增广样本向量 在后面仍用yn来表示它 第三章线性判别函数郝红卫 27 两类线性可分情况 解向量和解区在线性可分的情况下 满足atyn 0的权向量称为解向量 记为a 解向量往往不止一个 而是由无穷多个解向量组成一个区域 这样的区域称为解区 第三章线性判别函数郝红卫 28 两类线性可分情况 对解区的限制对解区加以限制的目的在于使得解向量更可靠 通常认为 越靠近解区中间的解向量 似乎越能对新的样本正确分类 因此 我们可以引入余量b 0 并寻找满足atyn b的解向量a 实际上 我们主要关心的是求解权向量的算法不至于收敛到解区域的边界上 显然 余量的引入可以很好地避免这个问题 第三章线性判别函数郝红卫 29 两类线性可分情况 引入余量的解区 第三章线性判别函数郝红卫 30 梯度下降算法 求解线性不等式组atyi 0的方法 定义一个准则函数J a 使得当a是解向量时 J a 为最小 这样就将问题简化为一个标量函数的极小化问题 通常可以用梯度下降法来解决 梯度下降法的基本步骤 首先任意选择一个初始的权向量a 1 计算梯度向量 J a 1 然后自a 1 沿梯度负方向移动一段距离得到下一个值a 2 反复迭代 最终收敛到一个使J a 极小化的解上 第三章线性判别函数郝红卫 31 梯度下降算法 取初值a 1 迭代其中 是正的比例因子 是用于设定步长的 学习率 learningrate 第三章线性判别函数郝红卫 32 梯度下降算法 第三章线性判别函数郝红卫 33 感知准则函数最小化 定义感知准则函数其中是被a错分的样本集合 如果没有样本被错分 我们定义Jp a 为0 由于当atyi 0时 即样本被a错分时Jp a 是非负的 只有当a是解向量时才为0 故a 对应着Jp a 的极值解 第三章线性判别函数郝红卫 34 感知准则函数最小化 梯度迭代公式 第三章线性判别函数郝红卫 35 感知准则函数最小化 批处理感知机算法 第三章线性判别函数郝红卫 36 感知准则函数最小化 固定增量单样本感知机算法 第三章线性判别函数郝红卫 37 感知准则函数最小化 感知机算法收敛定理如果训练样本线性可分 则由固定增量单样本感知机算法给出的权向量序列必定收敛于某个解向量 第三章线性判别函数郝红卫 38 感知准则函数最小化 固定增量单样本感知机算法详细步骤样本增广样本规范化取初值迭代得到最终解 第三章线性判别函数郝红卫 39 感知准则函数最小化 例31固定增量单样本感知机算法示例 pdf32固定增量单样本感知机算法示例 doc 第三章线性判别函数郝红卫 40 感知准则函数最小化 算法推广带余量的变增量感知机算法Begininitializea marginb k 0dok k 1 modnifatyk bthena a k ykuntilatyk bforallkreturnaEnd 第三章线性判别函数郝红卫 41 感知准则函数最小化 批处理变增量感知机算法 第三章线性判别函数郝红卫 42 松弛算法 为了使搜索表面更为平滑 我们可以采用二次的准则函数其梯度是连续的 但存在两个问题有可能得到无意义的解a 0模值大的样本对其影响太大 第三章线性判别函数郝红卫 43 松弛算法 改进后 得梯度迭代公式 第三章线性判别函数郝红卫 44 松弛算法 批处理余量松弛算法 第三章线性判别函数郝红卫 45 松弛算法 单样本余量松弛算法 第三章线性判别函数郝红卫 46 最小平方误差方法 前面的准则函数依然存在两个问题只能利用被错分的样本实际上是在解线性不等式组 不如解线性方程组方便为此 我们可以引入余量bi bi是任意取定的正常数 这样就可以将一个求解线性不等式组atyi 0的问题转化为求解线性方程组atyi bi 同时 利用平方误差来定义准则函数 无论是否错分只要有误差就进行调整