北京交通大学机器学习于剑课后习题答案

1第二章1充分性由样本可分性公理有,IXIKK，即对任意对象总有唯一一个类与其最相似。所以1,MAXARGIKXIXXSIMK。必要性由1,MAXARGIKXIXXSIMK，有对任意一个对象与其最相似的类有且仅有一个。所以有,IXIKK。2满足归类公理有样本可分性公理,IXIKK（1）类可分性公理,IXKIK（2）归类等价公理XX（3）由1式有,JKXIKXXXSIMIJJXXSIMIK，即,JKXIKXXXSIMXXSIMIJJIK。由3式归类等价公理有认知表示和外延表示归类能力等价，即JKIKJKXIKXUUXXSIMXXSIM,所以有,JKIKUUIJJIK。由2式有,JKXIKXXXSIMIJJXXSIMKI，即,JKXIKXXXSIMXXSIMIJJKI。由3式归类等价公理有认知表示和外延表示归类能力等价，即JKIKJKXIKXUUXXSIMXXSIM,，所以有,JKIKUUIJJKI。3归类等价公理XX，U为硬划分，即由1,0IKU，有对于一个样本而言只有属于与不属于某类且CIIKU11，所以每个样本对于C类而言有且仅有属于一类由归类等价公理XX，即样本的认知表示和外延表示归类能力等价，所以有对任意对象总有唯一一个类与其最相似。所以样本可分性公理成立。1,1,0,111NKIKIKCIIKUUU2且11NKIKU，有对于每一类总有至少有一个对象属于该类。由归类等价公理XX，即样本的认知表示和外延表示归类能力等价，所以有对任意一类至少有一个样本与其最相似。所以类可分性公理成立。4由非正则划分，有JKIKUUIJJKI又一般情况下归类等价公理总是满足的，所以XX所以,JKXIKXXXSIMXXSIMIJJKI。5样本可分性公理有类可分性公理有由指派算子和相似算子有MAXARGXIUKIKI,MAXARGXIXXSIMKIKXI由归类等价公理有XX，所以,MAXARGMAXARGIKXIIKIXXSIMUK。6样本可分性公理类可分性公理由指派算子和相似算子,JKXIKXJKXIKXKXXSIMXXSIMIJJIKXXSIMIJJXXSIMIKIXIK,JKXIKXJKXIKXKXXSIMXXSIMIJJKIXXSIMIJJXXSIMKIIXKI,MINARG,JKXIKXJKXIKXIKXIKXXDSXXDSIJJIKXXDSIJJXXDSIKIXXDSIKIXIK,MINARG,JKXIKXJKXIKXIKXIKXXDSXXDSIJJKIXXDSIJJXXDSKIIXXDSKIIXKI3MAXARGXIUKIKI,MINARGXIXXDSKIKXI由归类等价公理有XX，所以,MINARGMAXARGIKXIIKIXXDSUK7,JKYIKYYYSIMYYSIMIJJIK即对任意一个对象，该对象与任意两类的相似度都不同，则必然存在最大的一个。即,JKYIKYYYSIMYYSIMIJJIK所以有,MAXARG,IYYSIMIKIKI即,IYIKK所以样本可分性公理成立。8由归类等价公理有XXYY所以，若YX，则YX若YX，则YX所以归类等价公理成立的条件下，YXYX。即YX等价于YX。9由指派算子MAXARGXIUKIKI有3,2,1,1,2,3,1,2654321XXXXXX10第三章12PXXXKPPK,/1221EXP21|XXP4第四章1如下数据集只有两个样本2211,YXYXX其中在该数据集上有多个回归函数达到目标函数的最小值，如211XXXF，1212XXF都使回归函数到达目标函数的最小值。2由岭回归推导的最后表示式有ABIAAWT1，在上述数据集上其中所以代入上式有7,4,33,2,12211YXYX423111A73B73423111201410141046421WNKKNKKUXNXNU122111NKNKKNKKXX112222120110122221LN212LN21|LNKKXXP021211|LN22222KKKXXXP5当0时，矩阵IAAT不可逆，无法求出显示解当MM,时，则3LASSO回归如在广告推广问题上，一种算法FFM把广告推广中每一类的输入特征的属性的取值看作输出特征，多个输入特征的属性值进行笛卡尔积，将输出特征维度拉的很高，这样导致了在样本数据不多情况下会出现过拟合现象，常用逻辑回归加L1范的形式，即LASSO回归防止过拟合。第五章1推导过程由W是一组正交向量基，所以01,IJIJIJJTIJIJIWWJI由拉格朗日乘子法有，拉格朗日函数为00XLDIITKTKTIKDITJKIJKTIDIITKTKTIKDITJKTJDJTIKTIDIITKTKTIKDIJJTKDJTIITKDIITKTKTIKDIIITKDIIITKDIITKTKTIKDIIITKDIIITKTKKDIIITKKKXKKXXWXXXXWXXWXXXXWWXXXXWXXWXXWWXXWWXXXXWXXWWXXWWXXWXXXXWXXWWXXWWXXWXXXXWXXWWXXWWXXXXXXWWXXXXXXDSXXDS1002010010020101010020101010020101010020210100202210022222,MIN6求导有由后式代入上式，且DII1等于协方差矩阵的迹，所以有所以的通解为2非负矩阵分解相异性度量采用如下则有采用拉格朗日乘子法，有拉格朗日函数为HBWAWHXHWL,EXP,2其中A，B是拉格朗日乘子。对W，H求偏导有DIJTIIKDIITKTKTIKKWWWXXXXWXXL1100201KKDITIIPXXWWIXL2010IIKITKKIWWXXXXWL2200KKNXX0IIKITKKWWXXXX0000XLJJDITIIPKJJDITIIPKJWWIWWINXXJJJJ110任意2EXP,WHXXXDSKX0,0EXP2,HWTSWHXMINKHWBWWHXWHXBWWHXWHXHL2EXP02EXP22AHWHXWHXAHWHXWHXWL2EXP02EXP227由KTT条件有0,0IJIJIJIJWAHB3图像稀疏编码第六章1聚类分析例子如在商业上，采用聚类分析来来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征。23如PAKHIRA等人提出的一个能同时评价硬聚类和模糊聚类结果的有效性指标这里其中V是数据集的聚类中心，JM是FCM或者HCM算法中的目标函数值，DC是所有不同聚类原型之间的距离总和，最优的聚类数通过求解PBV的最大值获得。可以看出PBV满足聚类有效性指标，其中JM表示类内距离尽可能的小则最优，即满足类紧致性准则，DC则表示类间距离总和越大越优，同时聚类效果不能无限扩大类别数C，所以1/C来限制聚类类数，而E只与数据整体上的分布有关。可以看出PBV满足聚类有效性指标。第七章P64N1假设02EXP2IJIJWHWHXWHX02EXP2IJIJHWWHXWHX211CMPBDJECCVNJJVXE118由拉格朗日乘子法有拉格朗日函数为（1）对（1求导）由代入（1）式NKKCIINKKNKKXPXPXSIM1111|LOGMAX|MAX,MAX11CIICIIKIIKIIKXPXP1|0|11NKCIIKIIKIXPXPL0|12112NKIIKIKNKCIIKIIIKIKIIXXPXXPL01,|211131ITIINKIKNKCIIKIIITIIKIIXXXPXXXPLNKIKIN1122/2EXP21|ITPIPKXXXP22/2EXP21|IITIPIPKXXXP1|LOG111CIINKKCIIXPL9所以所以在第一个假设下基于混合高斯分布的聚类算法如下第一步初始化参数,E步根据参数更新隶属度IKM步根据更新的隶属度IK，采用最大似然估计更新参数II,重复迭代EM步直到收敛。2假设同上有NKIKNKTIKIKIKNKIKNKKIKIXXXI11211CIIKIIKIIKXPXP1|NKIKNKTIKIKIKINKIKNKKIKINKIKIXXXN11111122/2EXP21|XXXPTPPKNKIKIN11NKIKNKTIKIKIKNKIKNKKIKIXXX1121110所以在第一个假设下基于混合高斯分布的聚类算法如下第一步初始化参数,E步根据参数更新隶属度IKM步根据更新的隶属度IK，采用最大似然估计更新参数,重复迭代EM步直到收敛。3假设1,CII那么有CIIKIIKIIKXPXP1|NKIKNKTIKIKIKNKIKNKKIKINKIKIXXXN11111122/2EXP21|XXXPTPPKNKIKNKTIKIKIKNKIKNKKIKIIXXXC1111111所以在第该假设下基于混合高斯分布的聚类算法如下第一步初始化参数,1CE步根据参数更新隶属度IKM步根据更新的隶属度IK，采用最大似然估计更新参数,重复迭代EM步直到收敛。4由最小化J推导出CIIKIIKIIKXPXP1|NKIKNKTIKIKIKNKIKNKKIKIIXXXC11111211MINCINKIKIKXXJ12第八章1在PAC理论中，满足PAC辨识的话，则表示学习算法可以在置信度为1下学到目标空间中某类标函数X的近似，且误差在范围内。而在类表示唯一公理中，如果类表示唯一公理成立，那么目标函数与学到的函数之间在不存在误差，即0。所以说PAC理论是类表示唯一公理的一个近似版。2在统计机器学习理论中，学习的过程使用训练集的平均损失来代替泛化能力。即采用经验风险或经验损失来代替泛化能力作为设计分类算法的判据。根据类一致性准则的方法使得类标函数与类预测函数误差最小，也就是期望经验风险最小化。所以统计机器学习理论服从类一致性准则。理想情况下，经验风险最小化能够保证有和好的学习效果，即学到的类标预测函数在测试集上也会有良好的泛化能力。但在实际设计分类算法过程中，如果采用过分复杂的类标预测函数来进行学习，可能会导致在训练集上效果非常好，而在测试集上效果很差，导致过拟合。为了防止过拟合现象的出现，在经验风险最小化的同时考虑奥卡姆剃刀准则，即在性能相同的时候类标预测函数最简最佳。所以统计机器学习理论服从奥卡姆剃刀准则。所以统计机器学习模型上一般采用经验风险最小化加正则项的形式。第九章131径向基神经网络，通过一个径向基函数将输入特征映射到输出特征上，然后在输出特征上进行线性回归。常见的一种径向基神经网络表达式如下（1）在基于回归的分类模型中，一般输入表示为,SIMXXUX，输出表示为,SIMYYVY，如果那么（1）式就可以看做是对输入特征Y的一个线性回归表示，且每个样本都是一个独立的线性函数，即,21KNKKKYHYHYHYHK。所以说径向基神经网络属于基于回归的分类模型。2ELMAN网络通常是一个两层网络，其隐藏层神经元到输出层神经元之间还存在一个反馈通道，这种反馈连接使得ELMAN网络具有检测和产生时变的能力。输入，隐藏，输出层之间关系如下输入层到隐藏层隐藏层到输出层同样可以把ELMAN网络从输入层到隐藏层看作是输入表示到输出表示的一个映射而输出表示到最后的输出层则是一个线性回归模型。所以ELMAN网络也可以看作是一个基于回归的分类模型。3径向基网络学习的函数如下PJCXWYHIIPIJJ2,1,21EXP12221EXP22ICXY11100IIINIJIYWXSFYXWXSIIJ112NIJYWYHJPJCXWYHIIPJIJJ2,1,21EXP12214由类一致性准则最小化如下目标函数记JJJYXFE对上式求导有由上式导数有迭代更新如下4由ELMAN网络如下由类一致准则最小化目标函数如下NJHIIPJIJJNJJJNJJJCXWXFYXFLYXFD1212212121EXP2121,NJJIJNJHIJJJIJJJNJHIJJJIJJJGEWLCXGWELCXGWECL1112311221EXP22IPJCXGIJTIJTIJJTTJTTWLWWLCLCCJJJJ11111100IIINIJIYWXSFYXWXSIIJ112NIJYWYHJ15采用BP算法对参数进行求导如下记JJJYHXFE由此迭代更新如下第十章由特征X1（3,6,8,5,4,9）的方差大于特征2（5,3,76,2,4）所以第一次分类根据特征X1的中位数（56）/255（特征1）（特征2）NJJJNJJJYHXFLYHXFD12121,其中110201111212XWXXSFWYXXEXWWLXPWYXSFWYXPXEXPWWLXEYWLTJITTJIIIIIJJJIJJIJIJIJIJJJJ200111222111IIIIIIIIIWLTWTWWLTWTWWLTWTW（3,5）（6,3）（8,7）162采用曼哈顿距离1建立KD树的过程同书上一直2查询S的最近邻过程中，与书上采用的欧式距离不同的地方在于，当查询到叶子节点A为当前最近邻时，以S为中心，SA的距离为画P维的“斜45度正方体”，记当前节点的父节点为Q，判断当前节点的兄弟节点所在的区域是否在“正方形”内，如果在，对兄弟节点所在的子树进行临近搜索，记当前所找到的最近邻节点为A，上移一层至Q节点，判断Q节点是否比A点更近，若近则更新距离，若Q为根节点，算法结束。3第十一章1假设线性判别函数以0KXF为两类的判别界限。假设1X和2X都有01XF02XF，即IRX1，IRX2，现有1,0,121XXX，那么有121XXFXF由KXF为线性函数有由01XF，02XF且1,0，有0XF所以IRX。所以线性判别函数的判定区是凸的。2假设这个分类向量的P维分量均在100,1之间且为整数，那么可以采用穷举法（5,6）（4,2）（9,4）112121XFXFXXFXF17从P维向量试到那么需要穷尽100P次，即算法的复杂度为100P。3假设BXWIT1和BXWIT2，那么BXWXWITIT221由线性性有BXWWITT221，即所以BXWIT1的解集TW构成一个凸集，所以必然存在极小值，即最小长度的向量是唯一的。4如图显然X1，X2，X3两两之间是线性可分的但是X1，X2，X3整个样本不是线性可分的。5由点到平面的距离可以表示为点AX到平面上任意一点BX的向量在平面的法向量上的投影。所以有距离由BX在平面上，所以P11P100100100100BXWWITT221X1X3X2WWWXWWXWWXXABAB00WXFWWWXAA/018而AX在平面上投影的点必然有0XF，且满足点AX到X的距离2XXA最小。6当采用松弛变量如下则有软间隔支持向量机形式如下781支持向量机的超平面构建依赖于支持向量，非支持向量的点对超平面的构建重要性不大，可以选择性的剔除非支持向量上的点。29如图支持向量为（0,1），（1,0）（1,1）三个点11MIPI0121MIN12,PIPIKTKMIPIBWBXWUTSCW19超平面易得为02/3YXXF，间隔为10过滤掉不是支持向量的点由支持向量的性质可以看出，超平面大致位于样本点的中心附近，所以提出一种不精确的方法，统计样本的中心点，剔除掉离中心点较远的样例点。第十二章1对,LOG00IJJIWWWLLF由LF为光滑凸函数，所以二阶导存在上限2/P，即所以在进行二阶泰勒展开有所以对LF上限进行最大化，同时在求解过程中加上和减去一些常数项所以由FIST算法思想有41114/2NKCIIJNKCICJKTJJKTIIIKWXWWXWWUWL1111100EXPLOGLOGPJCIWLTTIJ0,1,222,TTTTLLPLLLFLFLFLLPLFLFCIPJIJTTCIPJIJTTCIPJIJTTTTWLLFPLWLFPLLPWLLPLLLFLFWL10221022102221MAXARG1记12MAXARG2,MAXARG2MAXLOGARG其他,0,IIIIS20所以迭代SL，其中2LOGISTIC回归的稀疏版算法同上可以采用FIST算法思想3如果将SOFTMAX和LOGISTIC回归的类标看作是C维的向量，把C维向量映射到一维坐标轴1XH上，那么就可以把SOFTMAX和LOGISTIC回归的认知表示看作是回归模型中的回归值，即有输入表示为那么就有SOFTMAX和LOGISTIC回归存在单类回归模型的解释。第十三章1由类紧致准则有最大化类内相似性可以看出最大化目标函数即为最大似然估计。2假设对于X有一个先验估计而输入类认知表示为Y，根据类一致性准则最大化其相似性，假设其中LRLIISLPRCI1,1,1,1TTLFPL坐标上的值类维的向量映射到一维为其中,12211CXHXHXXHXXHXY