一、(16P)泛化误差上界:对二分类问题,当假设空间是有限个函数的集合dfffF,,,21时,对任意一个函数Ff,至少以概率-1,以下不等式成立:,,NdfRfR其中,1loglog21,,dNNd即Nf的泛化能力:fRfFfNminarg.证明:在证明中要用到Hoeffding不等式,故先叙述如下:设niinxS1是独立随机变量是nXXX,,21之和,1,iiibaX;nXXnii1为这组随机变量nXXX,,21的均值,则0t,以下不等式成立:niiiabtntXEXP1222__2expniiiabtntXEXP12222exp2对任意函数Ff,fR是N个独立的随机变量XfYL,样本均值,fR是随机变量XfYL,的期望值。如果损失函数取值于区间1,0,即对所有i,1,0,iiba,那么有上述Hoeffding不等式,对0,以下不等式成立:22expNfRfRP由于dfffF,,21是一有限集合,故22exp:NdfRfRPfRfRPfRfRFfPFfFf或者等价的,对任意Ff,有22exp1NdfRfRP令22expNd则1fRfRP故至少以概率-1有fRfR.二、(28P)以损失函数推导向量最小化感知机的损失函数MxiibwibxwybwL,min,感知机学习算法是误分类驱动的,具体采用随机梯度下降法。首先,任意选取一个超平面,然后用梯度下降法不断极小化目标函数,极小化的过程不是一次使M中所有的误分类点的梯度下降,而是一次随机选取一个误分类点使其梯度下降.随机梯度下降是一种迭代求解思路,而迭代法参数寻优的基本原理:沿着(代价)函数下降的方向寻找参数,能够找到极值点.在我们已经学过的数学知识中,导数和方向导数是能找到函数变化方向的。导数表示了曲线的斜率(倾斜度),方向导数表示了曲面沿着任意方向的斜率(倾斜度)。一维时,导数就足够了。但多维时,就需要借助方向导数了,而我们更希望能找到变化率最大的方向。因此,多维下借用方向导数变化最大的情况:梯度,梯度的方向是函数某点增长最快的方向,梯度的大小是该点的最大变化率.故对于MxiiibxwybwL,损失函数bwL,的梯度是对w和b求偏导:MxiiMxiMxiiwiiixywbywwxywbwLbwL,,MxiMxiMxiibiiiybbybxwybbwLbwL,,三、(29P)如图所示的训练数据集,其正实例点是3,31x,3,42x,负实例点是1,13x,试用感知机学习算法的原始形式求感知机模型bxwsignxf.这里,21,,21,xxx.解构建最优化问题:bxwybwLMxibwi,min,按照感知机学习算法的原始形式,求解w,b.1.(1)取初值00w,00b(2)对3,31x,00101bxwy,未能被正确分类,更新w,b.3,3110xywwi,1101ybb得到线性模型1332111xxbxw(3)对1x,2x,显然,0iiibxwy,被正确分类,不修改w,b.对1,13x,01313bxwy,被误分类,更新w,b.2,23312xyww,0312ybb得到线性模型212222xxbxw1,13323xyww,1323ybb得到线性模型12133xxbxw(5)对1,13x,03333bxwy,被误分类,更新w,b0,03334xyww,2334ybb故得到线性模型244bxw(6)对331,x,04141bxwy,被误分类点,更新w,b.3,31145xyww,1145ybb故得到线性模型1332155xxbxw(7)对1,13x,05353bxwy,被误分类点,更新w,b.2,23356xyww,2356ybb故得到线性模型2222166xxbxw(8)对1,13x,03363xywy,被误分类点,更新w,b.1,13367xyww,3367ybb故得到线性模型32177xxbxw而该模型对正实例点3,31x,3,42x,负实例点1,13x,都有0iiiibxwy,则没有分类点,损失函数达到最小.故分离超平面为0321xx感知机模型为331xxsignxf迭代过程如表四、37P从统计角度考虑哪些因素影响k近邻法的准确度.我们知道K近邻法是一种应用广泛的非参数分类方法,可用于线性不可分的多类样本识别。它的优点是事先并不要求知道待分样本的分布函数。目前广泛使用的K近邻法是以待分类样本为中心做超球体,逐渐扩大超球半径直至超球内包含K个已知模式样本为止,判断这k个近邻样本中多数属于哪一类,就把待分类样本归为哪一类。分类算法描述如下:假设有c个类别,,,,21c,ci,,2,1.测试样本x和与其最近的样本之间的距离为xkikixxgmin,nk,,2,1,其中xki的下标i表示iw类,上标k表示iw类in个样本中第k个样本.在超球半径xgrimin的前提下,求iikLmaxarg,10ciki表示这k个近邻中属于iw的样本数.上述方法的弱点就是,半径r的选取十分困难.r值过大,超球体的覆盖面积广,会导致其他类样本被错误的覆盖,从而加大样本的误识率·反之若r值过小,则不能完全覆盖该类别中可能的样本点.并且近邻点具有相似的预测值,所以r的大小也会影响k近邻法的准确度.该方法易受噪声影响,尤其是样本点中孤立点的影响·而我们知道k近邻法模型由三个部分构成:距离度量,k的值,分类决策规则。所以K值的选取也会影响到分类结果.因为k值的选取是根据每类样本的数目和分散程度选取的,对不同的应用选取的k值也不同·所以我们是要在是在k值选定的情况下,对近邻点的搜索区域进行合理的定位,即选取合适的r的大小,即全局到局部,同时还要保障分类结果的准确性.具体方法:首先将样本空间的样本点进行小规模有目的性的聚类,聚类后样本空间中样本分布的区域被划分成,若干个半径一定的小超球体·如果能保证超球体内主体类样本数远远大于杂质类样本数,那么搜索时就可根据其条件将搜索范围缩小到某些超球体内,在这些超球体内寻找待分样本点的k个近邻点·定义C代表全体聚类的集合,即C中包含全部聚类中的数据·N代表确定的近邻点的集合,I为最近间隔,P为竞争点集,即可能成为近邻点的集合·聚类后计算指定点x到每个聚类中心的距离id,如图1所示依据这些距离,聚类集C被划分,离x最近的聚类为0c,下一个距离较近的聚类为1c,依次编号·然后将聚类0c中的所有点添加到P中,计算P中所有点与x的距离,将满足条件的点转移到集合N中·这样近邻点的搜索区域就可以被大致定位·求近邻点的关键是确定点x到C中聚类的搜索距离,为此需创建最近间隔I·每次近邻点的搜索范围便是以待分类点x为圆心,I值为半径的球体.在整个搜索过程中最近间隔I一直处在变化过程中,I值修改时采用使间隔I内包含尽量少的需要计算的近邻点的原则,已确保搜索的准确性·当聚类被初始划分时,由于采用局部聚类的方法,因此可能造成两个聚类存在重叠区域·为避免重叠区域的点因重搜索而影响算法效率,所以在计算最近间隔I时,还必须考虑C中的聚类是否有重叠区·当最近间隔I被初始创建时,检查0c与其他聚类是否有重叠区域,如果没有且rdrd10,则0c中所有点皆放入P中,此时rdI0.如果有重叠区域或rdd10,则rdI1·当I被确定后,P中所有点ix依据I值,将满足条件的点转移到N中·若P中的点搜索完毕,则按编号将下一个聚类中的点添加到P中,重复上述操作,直到N中包含K个元素时为止.五、根据表2计算:(1)后验概率;(2)离散属性的类条件概率;(3)连续属性的类条件概率分布的参数(样本均值和方差)Id有房婚姻状况年收入拖欠贷款1真单身125KNo2否已婚100KNo3否单身70KNo4真已婚120KNo5否离婚95KYes6否已婚60KNo7真离婚220KNo8否单身85KYes9否已婚75KNo10否单身90KYes表2从该数据集计算得到的先验概率以及每个离散属性的类条件概率、连续属性的类条件概率分布的参数(样本均值和方差)如下:先验概率:P(Yes)=3.0103;P(No)=7.010773)|(NoP是有房74|NoP否有房0|YesP是有房1|NoP否有房72|NoP单身婚姻状况71|NoP离婚婚姻状况74|NoP已婚婚姻状况32|YesP单身婚姻状况31|YesP离婚婚姻状况0|YesP已婚婚姻状况年收入:如果类=No:样本均值=1107752206012070100125;样本方差=2975;如果类=Yes:样本均值=90;样本方差=25待预测记录:X={有房=否,婚姻状况=已婚,年收入=120K}0024.00072.074747.0|120||NoKpNopNopNop年收入已婚婚姻状况否有房0102.1013.0|120||9YesKpYespYespYesp年收入已婚婚姻状况否有房由于0.0024大于0,所以该记录分类为No。从上面的例子可以看出,如果有一个属性的类条件概率等于0,则整个类的后验概率就等于0。仅仅使用记录比例来估计类条件概率的方法显得太脆弱了,尤其是当训练样例很少而属性数目又很多时。解决该问题的方法是使用m估计方法来估计条件概率mnmpnyxpcii|六、.