机器统计知识学习作业任务

1、、（R6）泛化误差上界：对二分类问题，当假设空间是有限个函数的集合Ff1, f2, , fd时，对任意一个函数f F ,至少以概率1-，以下不等式成立:R f R f d, N,其中，d, N,J2N logd log-即fN的泛化能力：fN arg min R f证明：在证明中要用到Hoeffd ing不等式,故先叙述如下:n设SnXi是独立随机变量是X1, X2,i 1Xn 之和，Xi ai,bi 1 ；nXi为n这组随机变量X1, X2, Xn的均值，则t 0，以下不等式成立:expC 2. 2 2n tu2i 1 bi ai2ex p2n2t2n-2i b ai对任意函数f F , R

2、f是N个独立的随机变量L Y, f X 样本均值，R f是随机变量L Y, f X的期望值。如果损失函数取值于区间0,1 ,即对所有i ,ai ,bi0,1，那么有上述Hoeffding 不等式,0，以下不等式成立:由于Fexp2N 2fl,f2, fd是一有限集合,2d ex p 2N或者等价的,对任意f F，有21 dexD 2NXi Md exp2N 2故至少以概率1-有R f R f 二、（R8）以损失函数推导向量最小化感知机的损失函数min L w, bw,byi w x bXiM感知机学习算法是误分类驱动的,具体采用随机梯度下降法。首先，任意选取一个超平面，然后用梯度下降法不断极小

3、化目标函数， 极小化的过程不是 次使M中所有的误分类点的梯度下降，而是一次随机选取一个误分类点使其梯 度下降.随机梯度下降是一种迭代求解思路，而迭代法参数寻优的基本原理：沿着（代价）函数下降的方向寻找参数，能够找到极值点.在我们已经学过的数学知识中，导数和方向导数是能找到函数变化方向的。导数表示了曲线的斜率（倾 斜度），方向导数表示了曲面沿着任意方向的斜率（倾斜度）。一维时，导数就 足够了。但多维时，就需要借助方向导数了，而我们更希望能找到变化率最大的 方向。因此，多维下借用方向导数变化最大的情况：梯度，梯度的方向是函数某 点增长最快的方向，梯度的大小是该点的最大变化率故对于L w, byi

4、w X b损失函数L w,b的梯度是对w和b求偏导:wLw,b 3wyiXiWX Mwyibxi Mwyi XiML w, bbL w,b byiW XiXi MbyibX Mbyi刍M，X24,3 ，负实三、（P29）如图所示的训练数据集，其正实例点是 Xi3,3例点是X31,1,试用感知机学习算法的原始形式求感知机模型解 构建最优化问题:min Lw,bw,byi w x bxi M按照感知机学习算法的原始形式，求解 w ， b.1.(1) 取初值 w00 ，b0 0(2) 对 x1 3,3y1 w0 x1b00 ，未能被正确分类，更新 w， b.wiw0y1x13,3 ， b1 b0 y

5、1 1得到线性模型w1b13x1 3x 2 1(3)对 x1， x2，显然， yi wi xbi0，被正确分类，不修改w , b .对x31,1y3 w1 x3 b1，被误分类，更新得到线性模型得到线性模型(5)对 x31,1故得到线性模型6)对 x13，3故得到线性模型w2w1y3x32,2 ， b2 b1y3w2 xb22x 12x 2w3w2y3x3w3 xy3 w3 x3b3w4w3， y1 w4 x1w5 w41,1b3b2y3b3210，y3x3b4被误分类，更新0,0， b4b3w4 x b420 ，被误分类点，y1 x13,3 ， b5b4w，y3y1w， bw5 X b5 3

6、X1 3x 21(7)对 x31,1y3W5 X3b50,被误分类点，更新w6W5¥3 X32,2， b6b5¥3故得到线性模型2X1 2X22(8)对 x31,1¥3w¥3X30，被误分类点，更新W7W ¥3X31,1b7b6¥3故得到线性模型w7X b7而该模型对正实例点X13,3X24,3,负实例点x31,1,都有¥i Wi Xi bi0，则没有分类点，损失函数达到最小.故分离超平面为感知机模型为f Xsign X1X33迭代过程如表爰九1的ft代过B迭代次ft分类点h枕电H + b0000II刃1Ji叫计+l2(X2

7、f0工工+ 2d：'3T宀宀14但时-2-25a)T一13屮口 3严】T6s2jr诙#2?聲壬27(ijy-J严nS0(bif-J利+宀3四、P37从统计角度考虑哪些因素影响k近邻法的准确度.我们知道K近邻法是一种应用广泛的非参数分类方法，可用于线性不可分的多类样本识别。它的优点是事先并不要求知道待分样本的分布函数。目前广泛使用的K近邻法是以待分类样本为中心做超球体，逐渐扩大超球半径直至超球内包含K个已知模式样本为止，判断这k个近邻样本中多数属于哪一类，就把待分类样本归为哪一类。分类算法描述如下假设有C个类别W1,W2, ,Wc, , I 12 ,C.测试样本X和与其最近的样本之间的距

8、离为gixk叫n x Xi ,kk 1,2，n，其中Xi的下标i表示Wi类，上标k表示wi类ni个样本中第k个样本.在超球半径r mi n g X的前提下，求L argmaxki , KO i c 1表示这k个近邻中属于w的样本数. i上述方法的弱点就是，半径r的选取十分困难.r值过大，超球体的覆盖面积 广，会导致其他类样本被错误的覆盖,从而加大样本的误识率反之若r值过小， 则不能完全覆盖该类别中可能的样本点.并且近邻点具有相似的预测值，所以r 的大小也会影响k近邻法的准确度.该方法易受噪声影响，尤其是样本点中孤立点 的影响而我们知道k近邻法模型由三个部分构成：距离度量，k的值，分类决策 规则

9、。所以K值的选取也会影响到分类结果.因为k值的选取是根据每类样本的 数目和分散程度选取的，对不同的应用选取的k值也不同所以我们是要在是在k值选定的情况下，对近邻点的搜索区域进行合理的定位，即选取合适的r的大小，即全局到局部，同时还要保障分类结果的准确性.具体方法：首先将样本空间的样本点进行小规模有目的性的聚类，聚类后样 本空间中样本分布的区域被划分成，若干个半径一定的小超球体如果能保证超球体内主体类样本数远远大于杂质类样本数，那么搜索时就可根据其条件将搜索范围缩小到某些超球体内，在这些超球体内寻找待分样本点的k个近邻点s 1聚娄c示意ra定义C代表全体聚类的集合，即C中包含全部聚类中的数据-N

10、代表确定的近邻 点的集合，1为最近间隔，P为竞争点集，即可能成为近邻点的集合聚类后计算 指定点x到每个聚类中心的距离di,如图1所示依据这些距离，聚类集C被划 分，离X最近的聚类为C0 ,下一个距离较近的聚类为ci ,依次编号然后将聚类Co中的所有点添加到P中，计算P中所有点与X的距离，将满足条件的点转移到集 合N中这样近邻点的搜索区域就可以被大致定位求近邻点的关键是确定点 X到C中聚类的搜索距离，为此需创建最近间隔I 每次近邻点的搜索范围便是以待分类点X为圆心，I值为半径的球体.在整个搜 索过程中最近间隔I 一直处在变化过程中，1值修改时采用使间隔I内包含尽量 少的需要计算的近邻点的原则，已

11、确保搜索的准确性当聚类被初始划分时，由于 采用局部聚类的方法，因此可能造成两个聚类存在重叠区域为避免重叠区域的点 因重搜索而影响算法效率，所以在计算最近间隔I时，还必须考虑C中的聚类是 否有重叠区当最近间隔I被初始创建时检查Co与其他聚类是否有重叠区域，如 果没有且do r di r，则Co中所有点皆放入P中，此时I d。r .如果有重叠区域或do di r，则I di r 当被确定后，P中所有点Xi依据I值，将满足条件 的点转移到N中沖中的点搜索完毕，则按编号将下一个聚类中的点添加到 P中，重复上述操作，直到N中包含K个元素时为止.五、根据表2计算:(1)后验概率;(2)离散属性的类条件概率

12、;(3)连续属性的类条件概率分布的参数(样本均值和方差)Id有房婚姻状况年收入拖欠贷款1直/、单身125KNo2否已婚100KNo3否单身70KNo4直/、已婚120KNo5否离婚95KYes6否已婚60KNo7直/、离婚220KNo8否单身85KYes9否已婚75KNo10否单身90KYes表2从该数据集计算得到的先验概率以及每个离散属性的类条件概率、连续属性的类条件概率先验概率：P (Yes)=3/10P(有房是 | No)3/7P有房否1 No4/7P有房是 |Yes0P有房否1 No1分布的参数(样本均值和方差)如下:0.3 ； P(No)= 7/100.7p婚姻状况单身| No2/7

13、p婚姻状况离婚| No1/7p婚姻状况已婚| No4/7P婚姻状况单身|丫es2/3P婚姻状况离婚|Yes1/3P婚姻状况已婚|Yes0年收入：如果类=No:样本均值=125 100 70 120 60 220 75110 ；样本方差=2975;如果类=Yes:样本均值=90 ;样本方差=25待预测记录：X =有房=否，婚姻状况=已婚，年收入=120KP No p有房 否| No P婚姻状况已婚| No0.7 4/7 4/7 0.0072 0.0024P年收入 120K | NoP Yes P有房 否| Yes p婚姻状况已婚| Yes90.3 1 0 1.2 10 90P年收入 120K |Yes由于0.0024大于0 ,所以该记录分类为 No。从上面的例子可以看出，如果有一个属性的类条件概率等于0，则整个类的后验概率就等于0。仅仅使用记录比例来估计类条件概率的方法显得太脆弱了,尤其是当训练样例很少而属性数目又很多时。解决该问题的方法是使用m估计方法来估计条件概率nc mpn m其中，口是类戸中的宪例总数是类刀的训练样本中取值兀的样本数，m是称为等价样 本大水的参数，P是用户指定的参数总还是上面的例子，条件概率P（婚姻状祝二已婚|Ycs） = O, 使用m估计方袪，nk=3i p=L3 则：屮F