机器学习-试卷-finals19

CS189Spring2019IntroductiontoMachineLearningFinalExamˆPleasedonotopentheexambeforeyouareinstructedtodoso.ˆElectronicdevicesareforbiddenonyourperson,includingcellphones,iPods,headphones,andlaptops.Turnyourcellphoneoandleaveallelectronicsatthefrontoftheroom,orriskgettingazeroontheexam.ˆWhenyoustart,thefirstthingyoushoulddoischeckthatyouhaveall12pagesandall6questions.Thesecondthingistopleasewriteyourinitialsatthetoprightofeverypageafterthisone(e.g.,write“JS”ifyouareJonathanShewchuk).ˆTheexamisclosedbook,closednotesexceptyourtwocheatsheets.ˆYouhave3hours.ˆMarkyouranswersontheexamitselfinthespaceprovided.Donotattachanyextrasheets.ˆThetotalnumberofpointsis150.Thereare26multiplechoicequestionsworth3pointseach,and5writtenquestionsworthatotalof72points.ˆFormultipleanswerquestions,fillinthebubblesforALLcorrectchoices:theremaybemorethanonecorrectchoice,butthereisalwaysatleastonecorrectchoice.NOpartialcreditonmultipleanswerquestions:thesetofallcorrectanswersmustbechecked.FirstnameLastnameSIDFirstandlastnameofstudenttoyourleftFirstandlastnameofstudenttoyourright1Q1.[78pts]MultipleAnswerFillinthebubblesforALLcorrectchoices:theremaybemorethanonecorrectchoice,butthereisalwaysatleastonecorrectchoice.NOpartialcredit:thesetofallcorrectanswersmustbechecked.(a)[3pts]Whichofthefollowingalgorithmscanlearnnonlineardecisionboundaries?Thedecisiontreesuseonlyaxis-alignedsplits.Adepth-fivedecisiontreeQuadraticdiscriminantanalysis(QDA)AdaBoostwithdepth-onedecisiontreesPerceptronThesolutionsareobviousotherthanAdaBoostwithdepth-onedecisiontrees,whereyoucanformnon-linearboundariesduetothefinalclassifiernotactuallybeingalinearcombinationofthelinearweaklearners.(b)[3pts]Whichofthefollowingclassifiersarecapableofachieving100%trainingaccuracyonthedatabelow?Thedecisiontreesuseonlyaxis-alignedsplits.LogisticregressionAneuralnetworkwithonehiddenlayerAdaBoostwithdepth-onedecisiontreesAdaBoostwithdepth-twodecisiontreestopleft:Eachweaklearnerwilleitherclassifythepointsfromeachpairindierentclasses,orclassifyeverypointinthesameclass.Sincethemetaclassifierisaweightedsumofalloftheseweakclassifiers,eachwhichhasa50%trainingaccuracy,themetaclassifiercannothave100%accuracy.topright:Aneuralnetworkwithonehiddenlayer(withenoughunits)isauniversalfunctionapproximator.lowerleft:Logisticregressionfindsalineardecisionboundary,whichcannotseparatethedata.lowerright:Adepthtwodecisiontreecanfullyseparatethedata.(c)[3pts]Whichofthefollowingaretrueofsupportvectormachines?IncreasingthehyperparameterCtendstodecreasethetrainingerrorThehard-marginSVMisaspecialcaseofthesoft-marginwiththehyperparameterCsettozeroIncreasingthehyperparameterCtendstodecreasethemarginIncreasingthehyperparameterCtendstodecreasethesensitivitytooutliersTopleft:True,fromthelecturenotes.Bottomleft:False,Hard-marginSVMiswhereCtendstowardsinfinity.Topright:false,perceptronistrainedusinggradientdescentandSVMistrainedusingaquadraticprogram.2Bottomright:True:slackbecomeslessexpensive,soyouallowdatapointstobefartheronthewrongsideofthemarginandmakethemarginbigger.Doingthiswillneverreducethenumberofdatapointsinsidethemargin.(d)[3pts]Letr(x)beadecisionrulethatminimizestheriskforathree-classclassifierwithlabelsy2f0;1;2gandanasymmetriclossfunction.Whatistrueaboutr(
)?8y2f0;1;2g;9x:r(x)=yIfwedon’thaveaccesstotheunderlyingdatadis-tributionP(X)orP(YjX),wecannotexactlycomputetheriskofr(
)8x,r(x)isaclassythatmaximizestheposteriorprobabilityP(Y=yjX=x)IfP(X=x)changesbutP(Y=yjX=x)remainsthesameforallx;y,r(X)stillminimizestherisktopleft:itispossiblethatr(X)isthesameforallX.topright:no,becausetheriskisasymmetriclowerleft:bydefinitionofriskweneedtobeabletocomputeexpectationsoverthesetwodistributions.lowerright:Giventhatr(X)hasnoconstraint,itcanpicktheythatminimizesriskforeveryX=xwithouttrade-os.Therefore,ifonlythemarginalschange,thatchoiceisnotaected.(e)[3pts]Whichofthefollowingaretrueabouttwo-classGaussiandiscriminantanalysis?AssumeyouhaveestimatedtheparametersˆC;ˆC,ˆCforclassCandˆD;ˆD,ˆDforclassD.IfˆC=ˆDandˆC=ˆD,thentheLDAandQDAclassifiersareidenticalIfˆC=I(theidentitymatrix)andˆD=5I,thentheLDAandQDAclassifiersareidenticalIfˆC=ˆD,ˆC=1=6,andˆD=5=6,thentheLDAandQDAclassifiersareidenticalIftheLDAandQDAclassifiersareidentical,thentheposteriorprobabilityP(Y=CjX=x)islinearinxTopleft:false,thecovariancematricesmightdier,makingtheQDAdecisionfunctionnonlinear.Bottomleft:false,theQDAdecisionfunctionisnonlinear.Topright:correct.Bottomright:no,theposteriorisalogisticfunction.(f)[3pts]ConsiderannddesignmatrixXwithlabelsy2Rn.Whatistrueoffittingthisdatawithdualridgeregressionwiththepolynomialkernelk(Xi;Xj)=(XTiXj+1)p=(Xi)(Xj)andregularizationparameter0?Ifthepolynomialdegreeishighenough,thepoly-nomialwillfitthedataexactlyThealgorithmcomputes(Xi)and(Xj)inO(dp)timeThealgorithmsolvesannnlinearsystemWhennisverylarge,thisdualalgorithmismorelikelytooverfitthantheprimalalgorithmwithdegree-ppolynomialfeaturesTopleft:seedefinitionofdualridgeregressionLowerleft:bothgivethesamesolution,nomattern!Topright:Thedualmethodproblemofridgeregressi