第5章：线性判别函数第一部分：计算与证明1 有四个来自于两个类别的二维空间中的样本，其中第一类的两个样本为(1,4)T和(2,3)T，第二类的两个样本为(4,1)T和(3,2)T。这里，上标T表示向量转置。假设初始的权向量a=(0,1)T，且梯度更新步长hk固定为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(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以后的解区(aTyib)位于原来的解区之中(aTyi0)，且与原解区边界之间的距离为b/|yi|。证明：设a*满足aTyib,则它一定也满足aTyi0，所以引入余量后的解区位于原来的解区aTyi0之中。注意，aTyib的解区的边界为aTyi=b,而aTyi0的解区边界为aTyi=0。aTyi=b与aTyi=0两个边界之间的距离为b/|yi|。（因为aTyi=0过坐标原点，相关于坐标原点到aTyi=b的距离。）3 试证明感知器准则函数正比于被错分样本到决策面的距离之和。证明：感知器准则函数为：决策面方程为aTy=0。当y为错分样本时，有aTy0。此时，错分样本到决策面的距离为aTy/|a|。所有样本到决策面的距离之和为结论得证。4 对于多类分类情形，考虑one-vs-all技巧，即构建 c 个线性判别函数：，此时的决策规则为：对 j i, 如果 gi(x) gj(x),x 则被分类 wi 类。现有三个二维空间内的模式分类器，其判别函数为g1(x) = -x1 + x2 g2(x) = x1 + x2 -1 g3(x) = -x2试画出决策面，指出为何此时不存在分类不确定性区域。解：根据上述决策规则，属于第一类 w1的区域应满足：g1(x) g2(x) 且g1(x) g3(x)所以w1的决策界面为：g1(x) - g2(x) = -2x1 + 1 = 0。g1(x) - g3(x) = -x1 + 2x2 = 0。同样地，属于第二类 w2的区域应满足：g2(x) g1(x) 且g2(x) g3(x)所以w2的决策界面为：g2(x) - g1(x) = 2x1 - 1 = 0。g2(x) - g3(x) = x1 + 2x2 - 1 = 0。属于第三类 w3的区域应满足：g3(x) g1(x) 且g3(x) g2(x)所以w2的决策界面为：g3(x) - g1(x) = x1 - 2x2 = 0。g2(x) - g3(x) = -x1 - 2x2 + 1 = 0。g1(x) - g2(x)=-2x1 + 1 = 0下图给出了决策边界：w2类判别区域g3(x) - g1(x)=x1 - 2x2 = 0g2(x) - g3(x)=x1 + 2x2 - 1 = 01.00.5w1类判别区域1.00.5w3类判别区域由于三个决策边界交于一点，因此，不存在不确定性区域。这是因为直线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 已知模式样本集：w1 = (0,0)T, (1,1)T, w2 = (0,1)T, (1,0)T。采用误差平方准则算法（即Ho-kashyap算法）验证它是线性不可分的。（提示：迭代时hk固定取1,初始b=(1,1,1,1)T）解：首先对第二类样本，进行齐次表示，然后再进行规范化表示，得到如下规范化增广训练数据矩阵：Y的伪逆矩阵为：进行第一次迭代a=Y+b=(0,0,0)T计算误差e=Ya-b=(-1,-1,-1,-1) T 此时，不必再更新b即可知道不等式组Ya0无解。因为e中部分元素为负（此时全为负）。根据Ho-kashyap算法相关（收敛性）原理，可知原样本集线性不可分。6. Consider the hyperplane used in discrimination: (a) Show that the distance from the hyperplane g(x) = wTx + w0 = 0 to the point xa is |g(xa)|/|w| by minimizing |x-xa|2 subject 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 xa onto the hyperplane is given by (即证明点xa到超平面g(x) = 0的投影xp为如下公式)：证明注意，在以下表达中，x要换成xa(b) 根据对(a)的证明的第二个公式，结论显然成立。第二部分：计算机编程题本章所使用的数据：1Write 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 w1 and w2. Note that the number of iterations required for convergence（即记录下收敛的步数）。(b). Apply your program to the training data from w3 and w2. 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 w1 and w3. Repeat to apply it to the training data from w2 and w4. Point out the training errors, and give some analyses.3. Consider relaxation methods as described in the PPT. (See the slides for the Batch Relaxation with Margin algorithm and page 62 in PPT for the Single Sample Relaxation with Margin algorithm):(a) Implement the batch relaxation with margin, set b = 0.1 and initialize a = 0, and apply it to the data in w1 and w3. 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.