机器学习考试卷-final2008f

MachineLearning(10-701)Fall2008FinalExamProfessor:EricXingDate:December8,2008.Thereare9questionsinthisexam(18pagesincludingthiscoversheet).Questionsarenotequallydifficult..Thisexamisopentobookandnotes.Computers,PDAs,Cellphonesarenotallowed..Youhavethreehours..Goodluck!11AssortedQuestions[20points]1.(TrueorFalse,2pts)PCAandSpectralClustering(suchasAndrewNg’s)performeigen-decompositionontwodifferentmatrices.However,thesizeofthesetwomatricesarethesame.2.(TrueorFalse,2pts)Thedimensionalityofthefeaturemapgeneratedbypolynomialkernel(e.g.,K(x,y)=(1+x·y)d)ispolynomialwrtthepowerdofthepolynomialkernel.3.(TrueorFalse,2pts)Sinceclassificationisaspecialcaseofregression,logisticregressionisaspecialcaseoflinearregression.4.(TrueorFalse,2pts)Foranytwovariablesxandyhavingjointdistributionp(x,y),wealwayshaveH[x,y]≥H[x]+H[y]whereHisentropyfunction.5.(TrueorFalse,2pts)TheMarkovBlanketofanodexinagraphwithvertexsetXisthesmallestsetZsuchthatx⊥X/{Z∪x}|Z6.(TrueorFalse,2pts)Forsomedirectedgraphs,moralizationdecreasesthenumberofedgespresentinthegraph.7.(TrueorFalse,2pts)TheL2penaltyinaridgeregressionisequivalenttoaLaplacepriorontheweights.8.(TrueorFalse,2pts)Thereisatleastonesetof4pointsinℜ3thatcanbeshatteredbythehypothesissetofall2Dplanesinℜ3.9.(TrueorFalse,2pts)Thelog-likelihoodofthedatawillalwaysincreasethroughsuccessiveiterationsoftheexpectationmaximationalgorithm.10.(TrueorFalse,2pts)OnedisadvantageofQ-learningisthatitcanonlybeusedwhenthelearnerhaspriorknowledgeofhowitsactionsaffectitsenvironment.22SupportVectorMachine(SVM)[10pts]1.PropertiesofKernel1.1.(2pts)ProvethatthekernelK(x1,x2)issymmetric,wherexiandxjarethefeaturevectorsforithandjthexamples.hints:Yourproofwillnotbelongerthan2or3lines.1.2.(4pts)Givenntrainingexamples(xi,xj)(i,j=1,...,n),thekernelmatrixAisann×nsquarematrix,whereA(i,j)=K(xi,xj).ProvethatthekernelmatrixAissemi-positivedefinite.hints:(1)Rememberthatann×nmatrixAissemi-positivedefiniteiff.foranyndimensionalvectorf,wehavef′Af≥0.(2)Forsimplicity,youcanprovethisstatementjustforthefollowingparticularkernelfunction:K(xi,xj)=(1+xixj)2.32.Soft-MarginLinearSVM.Giventhefollowingdatasetin1-dspace(Figure1),whichconsistsof4positivedatapoints{0,1,2,3}and3negativedatapoints{−3,−2,−1}.Supposethatwewanttolearnasoft-marginlinearSVMforthisdataset.Rememberthatthesoft-marginlinearSVMcanbeformalizedasthefollowingconstrainedquadraticoptimizationproblem.Inthisformulation,Cistheregularizationparameter,whichbalancesthesizeofmargin(i.e.,smallerwtw)vs.theviolationofthemargin(i.e.,smallerPmi=1ǫi).argmin{w,b}12wtw+CmXi=1ǫiSubjectto:yi(wtxi+b)≥1−ǫiǫi≥0∀iFigure1:Dataset2.1(2pts)ifC=0,whichmeansthatweonlycarethesizeofthemargin,howmanysupportvectorsdowehave?2.2(2pts)ifC→∞,whichmeansthatweonlycaretheviolationofthemargin,howmanysupportvectorsdowehave?43PrincipleComponentAnalysis(PCA)[10pts]1.1(3pts)BasicPCAGiven3datapointsin2-dspace,(1,1),(2,2)and(3,3),(a)(1pt)whatisthefirstprinciplecomponent?(b)(1pt)Ifwewanttoprojecttheoriginaldatapointsinto1-dspacebyprinciplecompo-nentyouchoose,whatisthevarianceoftheprojecteddata?(c)(1pt)Fortheprojecteddatain(b),nowifwerepresentthemintheoriginal2-dspace,whatisthereconstructionerror?1.2(7pts)PCAandSVDGiven6datapointsin5-dspace,(1,1,1,0,0),(−3,−3,−3,0,0),(2,2,2,0,0),(0,0,0,−1,−1),(0,0,0,2,2),(0,0,0,−1,−1).Wecanrepresentthesedatapointsbya6×5matrixX,whereeachrowcorrespondstoadatapoint:X=11100−3−3−30022200000−1−100022000−1−1(a)(1pt)Whatisthesamplemeanofthedataset?5(b)(3pts)WhatisSVDofthedatamatrixXyouchoose?hints:TheSVDforthismatrixmusttakethefollowingform,wherea,b,c,d,σ1,σ2aretheparametersyouneedtodecide.X=a0−3a02a00b0−2b0b×σ100σ2×ccc00000dd(c)(1pt)Whatisfirstprinciplecomponentfortheoriginaldatapoints?(d)(1pt)Ifwewanttoprojecttheoriginaldatapointsinto1-dspacebyprinciplecompo-nentyouchoose,whatisthevarianceoftheprojecteddata?(e)(1pt)Fortheprojecteddatain(d),nowifwerepresentthemintheoriginal5-dspace,whatisthereconstructionerror?64LinearRegression[12Points]A)00.511.522.5300.511.522.53xyθ1=0.5333θ0=0.6000B)00.511.522.5300.511.522.53xyθ1=0.5000θ0=0.0000C)00.511.522.5300.511.522.53xyθ1=0.5000θ0=0.8333D)00.511.522.5300.511.522.53xyθ1=0.3944θ0=0.3521Figure2:PlotsoflinearregressionresultswithvariousregularizationBackground:Inthisproblemweareworkingonlinearregressionwithregularizationonpointsina2-Dspace.Figure2plotslinearregressionresultsonthebasisofthreedatapoints,(0,1),(1,1)and(2,2),withdifferentregularizationpenalties.Asweallknow,solvingalinearregressionproblemisabouttosolveaminimizationproblem.Thatistocomputeargminθ0,θ1nXi=1(yi−θ1xi−θ0)2+R(θ0,θ1)whereRrepresentsaregularizationpenaltywhichcouldbeL-1orL-2.Inthisproblem,n=3,(x1,y1)=(0,1),(x2,y2)=(1,1),and(x3,y3)=(2,2).R(θ0,θ1)couldeitherbeλ(|θ1|+|θ0|)orλ(θ21+θ20).However,insteadofcomputingthederivativestogetaminimumvalue,wecouldadoptageometricmethod.Inthisway,ratherthanlettingthesquareerrortermandtheregularizationpenaltytermvarysimultaneouslyasafunctionofθ0andθ1,wecanfixoneandonlylettheothervaryatatime.Havingaupper-bound,r,onthepenalty,wecanreplace