15-781 Final Exam, Fall 2002 - Carnegie Mellon School of ...

1 15-781 FinalExam,Fall20021. :AndrewID:2. Thereshouldbe 17 pagesin thisexam(excludingthiscover sheet).3. If youneedmoreroomto workoutyouranswer to a question,usetheback of thepageandclearlymarkonthefront of thepageif we areto lookat what Youshouldattemptto answer allof Youmay useany andallnotes,as wellas Allquestionsareworthanequalamount. Youhave 3 Good luck! learningforDecisonListsA decisionlistis a listof if-thenruleswhereeach conditionis a literal(a variableor itsnegation).It canbe thought of as a example,say thatI like to gofora walkif it swarmor if it ssnowingandI have a jacket,as longas it coulddescribe thisas thefollowingdecisionlist:if rainythennoelseif warmthenyeselseif not(have-jacket)thennoelseif snowythenyeselseno.

2 (a)Describe analgorithmto learnDLsgivena dataset,forexampleabcclass100+011-111+00 0-110+Youralgorithmshouldhave thecharacteristicthatit shouldalwaysclassifyexam-plesthatit hasalreadyseencorrectly(ie,it shouldbe consistent withthedata).Ifit snotpossibleto continue to producea decisionlistthat sconsistent withthedata,youralgorithmshouldterminate andannouncethatit hasfailed.(b)Findthesizeof thehypothesisspace,|H|, fordecisionslistsof k attributes.(c)Findanexpressionforthenumb er of examplesneededto learna decisionlistof kattributeswitherrorat 90%.

3 (d)Whatif thelearneris tryingto learna decisionlist,buttherepresentationthatit isusingis a conjunctionof k literals?Findtheexpressionforthenumber of examplesneededto learnthedecisionlistwitherrorat (a)Whatis theeffectonthemeansfoundby k-means(asopposedto thetruemeans)ofoverlappingclusters?(b) theclustercentersandthedecisionboundarie sthatdefineeach many picturesas youneeduntil :Executethealgorithmsuch thatif a meanhasnopoints assignedto it, it stayswhereit is (c)Now draw (approximately)whata Gaussianmixturemodelof threegaussianswiththesameinitialcentersa s thecovariancematricesandthatEMupdatesbot hthemeansandcovariancematrices.

4 (d)Is theclassificationgiven by themixturemodelthesameas theclassificationgiven byk-means?Why or why not?43 HMMsAndrewlives a he sAngryandsomedays he sHappy. Buthehideshisemotionalstate,andso allyoucanobserve is whetherhe smiles,frowns,laughs,or startonday 1 in theHappy state,andthere sonetransitionper (smile)= (frown)= (laugh)= (yell)= (smile)= (frown)= (laugh)= (yell)= :qt= observationondayt.(a)WhatisP(q2=Happy)?( b)WhatisP(O2=f rown)?(c)WhatisP(q2=Happy|O2=f rown)?(d)WhatisP(O100=yell)?(e)Assumetha tO1=f rown,O2=f rown,O3=f rown,O4=f rown, andO5=f themostlikelysequenceof states?

5 54 BayesianInference(a)Considera datasetover 3 booleanattributes,X,Y, thesesetsof information,which aresufficient to specifythejoint distribution? ( X|Z)P( X| Z)P( Y|X Z)P( Y|X Z)P( Y| X Z)P( Y| X Z)P(Z) ( X| Z)P(X| Z)P(Y|X Z)P(Y|X Z)P(Y| X Z)P(Y| X Z)P(Z) (X|Z)P(X| Z)P(Y|X Z)P(Y|X Z)P(Y| X Z)P( Y| X Z)P( Z) (X|Z)P(X| Z)P(Y|X Z)P(Y|X Z)P( Y| X Z)P(Y| X Z)P(Z)6 Giventhisdatasetof 16 records:ABC00100100101001101101101110010 0100100100110110111(b)Writedowntheprobab ilitiesneededto make a joint density bayes classifier(c)Writedowntheprobabilitiesne ededto make a naive bayes classifier.

6 (d)Writetheclassificationthatthejoint density bayes classifierwouldmake forC givenA=0,B=1.(e)Writetheclassificationth atthenaive bayes classifierwouldmake forC given A=0,B= datasetwithtwo real-valuedinputs(x1andx2) points areshownas soliddotsandthenegative points 2 3 4 5 6123456X1x2(a)Supposeyouareusinga linearSVMwithnoprovisionfornoise( LinearSVMthatis tryingto maximizeitsmarginwhileensuringalldatapoi nts areontheircorrectsidesof themargin).Draw threelinesontheabove diagram,showingtheclassificationboundary andthetwo sidesof (s).

7 (b)UsingthefamiliarLSVM classifiernotationof class= sign( +b), calculatethevaluesofwandblearnedforpart( a)(c)Assumeyouareusinga noise-tolerant LSVM which triesto +CR k=1 k(1)usingthenotationof :is it possibletoinvent a datasetanda positive valueofCin which (a)thedatasetis linearlyseparablebut(b)theLSVM wouldneverthelessmisclassifyatleastonetr ainingpoint? If it is possibleto invent such anexample,pleasesketch theexampleandsuggesta it is notpossible,explainwhy 2 3 4 5 aboutthekernelfunctionis thatit is a monotonicallydecreasingfunctionof distancethatdecays to zeroat a distanceof 3 units(andis strictlygreaterthanzeroat a distanceof lessthan3 units).

8 (a)Whatis thepredictedvalueofywhenx= 1?(b)Whatis thepredictedvalueofywhenx= 3?(c)Whatis thepredictedvalueofywhenx= 5?(d)Whatis thepredictedvalueofywhenx= 6?9 Thefinaltwo partsof thisquestionconcern1-nearestneighbor usedas denotedby thecolorof 2 3 4 5 6123456X1x2(e)Does thereexista choiceof Euclidiandistancemetricforwhich 1-nearest-neighborwouldachieve zerotrainingseterrorontheabove dataset?Now let sconsidera different dataset:001 2 3 4 5 6123456X1x2(f) Does thereexista choiceof Euclidiandistancemetricforwhich 1-nearest-neighborwouldachieve zerotrainingseterrorontheabove dataset?

9 107 NearestNeighbor andCross-ValidationRecipe formakingtrainingsetof 10,000dat-apoints withtwo real-valuedinputsandonebinaryoutputclass :Recipe formakingtestsetof 10,000datapointswithtwo real-valuedinputsandonebinaryoutputclass :001 2 3 4 5 6123456X1x2with positionschosenrandomlyuniformlyin positionschosenrandomlyuniformlyin have + have have +ve25% have ve5000 points5000 pointsNo points ingap between rectangles001 2 3 4 5 6123456X1x2with positionschosenrandomlyuniformlyin positionschosenrandomlyuniformlyin points5000 pointsNo points ingap between rectanglesnone have +ve100% have ve100% have +venone have veUsingtheabove recipes formakingtrainingandtestsetsyouwillseeth atthetrainingsetis noisy.

10 In eitherregion,25%of thedatacomesfromtheminority each of thefollowingquestions,circletheanswer thatmostcloselydefinestheexpectederrorra te,expressedas a fraction.(a)Whatis theexpectedtrainingseterrorusingone-near est-neighbor?01/81/43/81/31/25/82/33/47/ 81(b)Whatis theexpectedleave-one-outcross-validation erroronthetrainingsetusingone-nearest-ne ighbor?01/81/43/81/31/25/82/33/47/81(c)W hatis theexpectedtestseterrorif we trainonthetrainingset,testonthetestset,a nduseone-nearest-neighbor?01/81/43/81/31 /25/82/33/47/81(d)Whatis theexpectedtrainingseterrorusing21-neare st-neighbor?