10-701FinalExam,Spring2007
1.Personalinfo:
?Name:
?Andrewaccount:?E-mailaddress:
2.Thereshouldbe16numberedpagesinthisexam(includingthiscoversheet).3.Youcanuseanymaterialyoubrought:anybook,classnotes,yourprintoutsofclassmaterialsthatareontheclasswebsite,includingmyannotatedslidesandrelevantreadings,andAndrewMoore’stutorials.Youcannotusematerialsbroughtbyotherstudents.Calculatorsareallowed,butnolaptops,PDAs,phonesorInternetaccess.4.Ifyouneedmoreroomtoworkoutyouranswertoaquestion,usethebackofthepageandclearlymarkonthefrontofthepageifwearetolookatwhat’sontheback.5.Worke?ciently.Somequestionsareeasier,somemoredi?cult.Besuretogiveyourselftimetoansweralloftheeasyones,andavoidgettingboggeddowninthemoredi?cultonesbeforeyouhaveansweredtheeasierones.6.Notethereareextra-creditsub-questions.Thegradecurvewillbemadewithoutconsideringstudents’extracreditpoints.Theextracreditwillthenbeusedtotrytobumpyourgradeupwithouta?ectinganyoneelse’sgrade.7.Youhave180minutes.8.Goodluck!
Question
ShortquestionsSVMandslacksGNB
456
Learningtheory
1
Max.score
10
14+3extra
1[Points]ShortQuestions
Thefollowingshortquestionsshouldbeansweredwithatmosttwosentences,and/orapicture.Forthe(true/false)questions,answertrueorfalse.Ifyouanswertrue,provideashortjusti?cation,iffalseexplainwhyorprovideasmallcounterexample.
1.[points]Yourbillionairefriendneedsyourhelp.Sheneedstoclassifyjobapplicationsintogood/badcategories,andalsotodetectjobapplicantswholieintheirapplicationsusingdensityestimationtodetectoutliers.Tomeettheseneeds,doyourecommendusingadiscriminativeorgenerativeclassi?er?Why?
2.[points]Yourbillionairefriendalsowantstoclassifysoftwareapplicationstodetectbug-proneapplicationsusingfeaturesofthesourcecode.Thispilotprojectonlyhasafewapplicationstobeusedastrainingdata,though.Tocreatethemostaccurateclassi?er,doyourecommendusingadiscriminativeorgenerativeclassi?er?Why?
3.[points]Finally,yourbillionairefriendalsowantstoclassifycompaniestodecidewhichonetoacquire.Thisprojecthaslotsoftrainingdatabasedonseveraldecadesofresearch.Tocreatethemostaccurateclassi?er,doyourecommendusingadiscrim-inativeorgenerativeclassi?er?Why?
4.[points]Assumethatweareusingsomeclassi?erof?xedcomplexity.Drawagraphshowingtwocurves:testerrorvs.thenumberoftrainingexamplesandcross-validation
2
errorvs.thenumberoftrainingexamples.
5.[points]AssumethatweareusinganSVMclassi?erwithaGaussiankernel.Drawagraphshowingtwocurves:trainingerrorvs.kernelbandwidthandtesterrorvs.kernelbandwidth
6.[points]AssumethatwearemodelinganumberofrandomvariablesusingaBayesianNetworkwithnedges.Drawagraphshowingtwocurves:Biasoftheestimateofthejointprobabilityvs.nandvarianceoftheestimateofthejointprobabilityvs.n.
7.[points]
(a)BothPCAandlinearregressioncanbethoughtofasalgorithmsforminimizinga
sumofsquarederrors.Explainwhicherrorisbeingminimizedineachalgorithm.
8.[points]Alongtimeagotherewasavillageamidsthundredsoflakes.Twotypesof?shlivedintheregion,butonlyonetypeineachlake.Thesetypesof?shbothlookedexactlythesame,smelledexactlythesamewhencooked,andhadtheexactsamedelicioustaste-exceptonewaspoisonousandwouldkillanyvillagerwhoateit.Theonlyotherdi?erencebetweenthe?shwastheire?ectonthepH(acidity)ofthelaketheyoccupy.ThepHforlakesoccupiedbythenon-poisonoustypeof?shwas
2
distributedaccordingtoaGaussianwithunknownmean(μsafe)andvariance(σsafe)
3
andthepHforlakesoccupiedbythepoisonoustypewasdistributedaccordingtoa
2
di?erentGaussianwithunknownmean(μdeadly)andvariance(σdeadly).(Poisonous?shtendedtocauseslightlymoreacidicconditions).
Naturally,thevillagersturnedtomachinelearningforhelp.However,therewasmuchdebateabouttherightwaytoapplyEMtotheirproblem.Foreachofthefollow-ingprocedures,indicatewhetheritisanaccurateimplementationofExpectation-Maximizationandwillprovideareasonableestimateforparametersμandσ2foreachclass.
(a)Guessinitialvaluesofμandσ2foreachclass.(1)Foreachlake,?ndthemost
likelyclassof?shforthelake.(2)Updatetheμandσ2valuesusingtheirmax-imumlikelihoodestimatesbasedonthesepredictions.Iterate(1)and(2)untilconvergence.
(b)Foreachlake,guessaninitialprobabilitythatitissafe.(1)Usingtheseprob-abilities,?ndthemaximumlikelihoodestimatesfortheμandσvaluesforeachclass.(2)Usetheseestimatesofμandσtoreestimatelakesafetyprobabilities.Iterate(1)and(2)untilconvergence.
(c)ComputethemeanandvarianceofthepHlevelsacrossalllakes.Usethesevalues
fortheμandσ2valueofeachclassof?sh.(1)Usetheμandσ2valuesofeachclasstocomputethebeliefthateachlakecontainspoisonous?sh.(2)Findthemaximumlikelihoodvaluesforμandσ2.Iterate(1)and(2)untilconvergence.
4
2[points]ReinforcementLearning
ConsiderthefollowingMarkovDecisionProcess:
r=1r=1r=1r=10S1r=1S2r=1S3r=1S4r=1S5WehavestatesS1,S2,S3,S4,andS5.WehaveactionsLeftandRight,andthechosenactionhappenswithprobability1.InS1theonlyoptionistogobacktoS2,andsimilarlyinS5wecanonlygobacktoS4.Therewardfortakinganyactionisr=1,exceptfortakingactionRightfromstateS4,whichhasarewardr=10.Forallpartsofthisproblem,assumethatγ=0.8.
1.WhatistheoptimalpolicyforthisMDP?
2.WhatisV?(S5)?Itisacceptabletostateitintermsofγ,butnotintermsofstatevalues.
3.ConsiderexecutingQ-learningonthisMDP.AssumethattheQvaluesforall(state,action)pairsareinitializedto0,thatα=0.5,andthatQ-learningusesagreedyexplorationpolicy,meaningthatitalwayschoosestheactionwithmaximumQvalue.Thealgo-rithmbreakstiesbychoosingLeft.Whatarethe?rst10(state,action)pairsifour
5
机器学习考试卷 final2007s-solution
