中科院模式识别第三次(第五章)_作业_答案_更多
更新时间:2023-03-08 09:49:39 阅读量: 综合文库 文档下载
- 中科院自动化所模式识别推荐度:
- 相关推荐
第5章:线性判别函数
第一部分:计算与证明
1. 有四个来自于两个类别的二维空间中的样本,其中第一类的两个样本为(1,4)T和(2,3)T,
第二类的两个样本为(4,1)T和(3,2)T。这里,上标T表示向量转置。假设初始的权向量a=(0,1)T,且梯度更新步长?k固定为1。试利用批处理感知器算法求解线性判别函数g(y)=aTy的权向量。 解:
首先对样本进行规范化处理。将第二类样本更改为(4,1)T和(3,2)T.然后计算错分样本集: g(y1)=(0,1)(1,4)T = 4 > 0 (正确) g(y2)=(0,1)(2,3)T = 3 > 0 (正确) g(y3)=(0,1)(-4,-1)T = -1 < 0 (错分) g(y4)=(0,1)(-3,-2)T = -2 < 0 (错分) 所以错分样本集为Y={(-4,-1)T ,(-3,-2)T }.
接着,对错分样本集求和:(-4,-1)T+(-3,-2)T= (-7,-3)T
第一次修正权向量a,以完成一次梯度下降更新:a=(0,1)T+ (-7,-3)T=(-7,-2)T 再次计算错分样本集:
g(y1)=(-7,-2)(1,4)T = -15 <0 (错分) g(y2)=(-7,-2)(2,3)T = -20 < 0 (错分) g(y3)=(-7,-2)(-4,-1)T = 30 > 0 (正确) g(y4)=(-7,-2)(-3,-2)T = 25 > 0 (正确) 所以错分样本集为Y={(1,4)T ,(2,3)T }.
接着,对错分样本集求和:(1,4)T+(2,3)T= (3,7)T
第二次修正权向量a,以完成二次梯度下降更新:a=(-7,-2)T+ (3,7)T=(-4,5)T 再次计算错分样本集:
g(y1) = (-4,5)(1,4)T = 16 > 0 (正确) g(y2) =(-4,5)(2,3)T = 7 > 0 (正确) g(y3) =(-4,5)(-4,-1)T = 11 > 0 (正确) g(y4) =(-4,5)(-3,-2)T = 2 > 0 (正确)
此时,全部样本均被正确分类,算法结束,所得权向量a=(-4,5)T。
2. 在线性感知算法中,试证明引入正余量b以后的解区(aTyi?b)位于原来的解区之中(aTyi>0),
且与原解区边界之间的距离为b/||yi||。
证明:设a*满足aTyi?b,则它一定也满足aTyi>0,所以引入余量后的解区位于原来的解区aTyi>0之中。
注意,aTyi?b的解区的边界为aTyi=b,而aTyi>0的解区边界为aTyi=0。aTyi=b与aTyi=0两个边界之间的距离为b/||yi||。(因为aTyi=0过坐标原点,相关于坐标原点到aTyi=b的距离。) 3. 试证明感知器准则函数正比于被错分样本到决策面的距离之和。
证明:感知器准则函数为:
J(a)?ay??(Ty?Y ) 决策面方程为aTy=0。当y为错分样本时,有aTy?0。此时,错分样本到决策面的
距离为aTy/||a||。所有样本到决策面的距离之和为
r??(?aTy)ay?Y
结论得证。
4. 对于多类分类情形,考虑one-vs-all技巧,即构建c 个线性判别函数:
gi(x)?wTi?1,2,...,c, ix?wi0,此时的决策规则为:对j ?i, 如果gi(x) >gj(x), x 则被分类?i类。现有三个二维空间内的
模式分类器,其判别函数为
g1(x) = ?x1+ x2 g2(x) = x1+ x2?1 g3(x) = ?x2
试画出决策面,指出为何此时不存在分类不确定性区域。 解:根据上述决策规则,属于第一类?1的区域应满足:
g1(x)>g2(x)且g1(x)>g3(x) 所以?1的决策界面为: g1(x)?g2(x) = ?2x1 + 1 = 0。 g1(x)?g3(x) = ?x1 + 2x2 = 0。
同样地,属于第二类?2的区域应满足:
g2(x)>g1(x)且g2(x)>g3(x) 所以?2的决策界面为: g2(x)?g1(x) = 2x1? 1 = 0。 g2(x)?g3(x) = x1 + 2x2? 1= 0。 属于第三类?3的区域应满足:
g3(x)>g1(x)且g3(x)>g2(x) 所以?2的决策界面为: g3(x)?g1(x) = x1?2x2 = 0。 g2(x)?g3(x) = ?x1?2x2+ 1= 0。 g1(x)?g2(x) 下图给出了决策边界: =?2x1 + 1 = 0
g(x)?g(x) g3(x)?g1(x) ?2类判别区域 23
1.0 =x + 2x? 1 = 0 =x1?2x2 = 0 12
0.5 ?1类判别区域 1.0
0.5
?3类判别区域
由于三个决策边界交于一点,因此,不存在不确定性区域。这是因为直线g1(x)?g2(x)=0与直线g1(x)?g3(x)=0的交点一定位于 g1(x)?g2(x)?(g1(x)?g3(x)) = g2(x)?g3(x) =0的直线
上,即g2(x)?g3(x) =0过它们的交点。
5. 已知模式样本集:?1 = {(0,0)T, (1,1)T}, ?2 = {(0,1)T, (1,0)T}。采用误差平方准则算法(即
Ho-kashyap算法)验证它是线性不可分的。(提示:迭代时?k固定取1,初始b=(1,1,1,1)T)
解:首先对第二类样本,进行齐次表示,然后再进行规范化表示,得到如下规范化增广训练数据矩阵:
?001???111? Y???0?1?1????10?1????222?2?1???T?1TY的伪逆矩阵为:Y?(YY)Y???22?22?
4???3?1?1?1?进行第一次迭代a=Y+b=(0,0,0)T 计算误差e=Ya-b=(-1,-1,-1,-1) T
此时,不必再更新b即可知道不等式组Ya>0无解。因为e中部分元素为负(此时全为负)。根据Ho-kashyap算法相关(收敛性)原理,可知原样本集线性不可分。
6. Consider the hyperplane used in discrimination:
(a) Show that the distance from the hyperplaneg(x) = wTx + w0 = 0 to the point xais
|g(xa)|/||w|| by minimizing ||x?xa||2subject to the constraint g(x) = 0. (提示需要证明两点:其一,点xa到超平面g(x) = 0的距离为|g(xa)|/||w||;其二,该距离是位于超平面g(x) = 0上使目标函数||x?xa||2最小的点x到点xa的距离。)
(b) Show that the projection of xaonto the hyperplane is given by (即证明点xa到超平面g(x)
= 0的投影xp为如下公式):
xp?xa?证明
g(xa)w ||w||2
注意,在以下表达中,x要换成xa
(b) 根据对(a)的证明的第二个公式,结论显然成立。
第二部分:计算机编程题
本章所使用的数据:
1.Write a program to implement the “batch perception” algorithm (see page 44 or 45 in PPT).
(a). Starting with a = 0, apply your program to the training data from ?1 and ?2. Note that the number of iterations required for convergence(即记录下收敛的步数)。
(b). Apply your program to the training data from ?3 and ?2.Again, note that the number of iterations required for convergence.
(c). Explain the difference between the iterations required in the two cases.
2. Implement the Ho-Kashyap algorithm and apply it to the training data from ?1 and ?3. Repeat to apply it to the training data from ?2 and ?4. Point out the training errors, and give some analyses.
3. Consider relaxation methods as described in the PPT. (See the slides for the \Relaxation with Margin\algorithm and page 62 in PPT for the \Sample Relaxation with Margin\
(a) Implement the batch relaxation with margin, set b = 0.1 and initialize a = 0, and apply it to the data in ?1 and ?3. Plot the criterion function as a function of the number of passes through the training set.
(b) Repeat for b = 0.5 and a0 = 0 (namely, initialize a = 0). Explain qualitatively any differences you find in the convergence rates.
(c) Modify your program to use single sample learning. Again, Plot the criterion function as a function of the number of passes through the training set.
正在阅读:
2012年淮安市中考数学试卷11-24
我家的斗鱼作文400字07-09
现代诗歌欣赏:最美的的祝福11-21
7sj62或63操作说明02-02
单片机课后题答案(霍孟友主编)03-26
公务员面试真题含答案09-09
中学思想政治课采用案例教学模式探究11-06
财产保险题库03-17
部编版五年级上册语文:字词知识点归纳03-27
- 《江苏省环境水质(地表水)自动监测预警系统运行管理办法(试行)》
- 安乐死合法化辩论赛立论稿(浙大新生赛)
- 公共科目模拟试卷公务员考试资料
- 我国固定资产投资FAI对GDP的影响
- 大学生创新创业训练计划项目申请书大创项目申报表
- 完美版—单片机控制步进电机
- 2013资阳中考化学试题
- 18.两位数减一位数退位(397道)
- 工程量计算规则
- 二年级操行评语(下)
- 第3章 流程控制语句
- 浅基桥墩加固技术
- 课题研究的主要方法
- 5100软件说明书 - 图文
- 车间技术员年终总结
- 关于印发《中铁建工集团开展项目管理实验室活动方案》的通知
- 经典诵读结题报告
- 地下水动力学习题答案
- 2018年全国各地高考数学模拟试题平面解析几何试题汇编(含答案解
- 街道办事处主任2018年度述职述廉报告
- 中科院
- 识别
- 作业
- 答案
- 模式
- 更多