CS7641yProblemySetyFally
Instructions
Thisyproblemysetyisynotyaypartyofyyouryfinalygradeybutyratheryaymeansytoyhelpyyouywithytheyfinalyexam.yIfyallyofytheyprobl
emsyareyattemptedyandyyourygradeyisyaroundytheycutoff,yweywillyroundyupytoytheyhigheryletterygrade.yYouywillyneedytoyat
temptyeachyproblemyandysubmityyourysolutionsyonyCanvas.yWeywillyverifyyworkyisysubmittedyatytheyendyofytheyterm.yAf
terytheydeadline,yweywillyprovideysolutionsyforyyouytoycompareyyouryanswers.yWeyplanytoyholdytwoyOfficeyHours,yoneyf
oryeachypartyofytheyproblemysetybeforeytheyfinal.
PartyOne
1. Whereyweyareydoingysupervisedylearning,yweyhaveymostlyyassumedyaydeterministicyfunction.yImagineyin
steadyayworldywhereyweyareytryingytoycaptureyaynon-
deterministicyfunction.yInythisycase,yweymightyseeytrainingypairsywhereytheyxyvalueyappearsyseveralytime
s,ybutywithydifferentyyyvalues.yForyexample,yweymightyuseyattributesyofyhumansytoytheyprobabilityythatyth
eyyhaveyhadychickenypox.yInythatycase,yweymightyseeytheysameykindyofypersonymanyytimesybutyonlyysom
etimesytheyymayyhaveyhadychickenypox.yWeywouldylikeytoybuildyaylearningyalgorithmythatywillycomputey
theyprobabilityythatyaypersonyhasychickenypox.ySo,ygivenyaysetyofytrainingydataywhereyeachyinstanceyisym
appedytoy1yforytrueyory0yforyfalse:
(a) DeriveytheyproperyerroryfunctionytoyuseyforyfindingytheyMLyhypothesisyusingyBayes’yRule.yYouysho
uldygoythroughyaysimilaryprocessyasytheyoneyusedytoyderiveyleastysquaredyerroryinytheylessons.
(b) Compareyandycontrastyyouryresultytoytheyruleyweyderivedyforyaydeterministicyfunctionyperturbedybyy
zero-
meanygaussianynoise.yWhatywouldyaynormalyneuralynetworkyusingysumyofysquaredyerrorsydoywithyt
heseydata?
yWhatyifytheydatayconsistedyofyx,yyypairsywhereyyywasyanyestimateyofytheyprobabilityyinsteadyofy0sya
ndy1s?
2. Designyaytwo-inputyperceptronythatyimplementsytheybooleanyfunctionyAy∧y¬B.yDesignyaytwo-
layerynetworkyofyperceptronsythatyimplementsyAy⊕yBy(wherey⊕yisyXOR).
3. Deriveytheyperceptronytrainingyruleyandygradientydescentytrainingyruleyforyaysingleyunitywithyoutputyo,yw
hereyoy=yw0y+yw1x1y+yw1x21y+y.y.y.y+ywnxny+ywnx2 n
y.yWhatyareytheyadvantagesyofyusingygradientydescent
trainingyruleyforytrainingyneuralynetworksyoverytheyperceptronytrainingyrule?
4. ExplainyhowyoneycanyuseyDecisionyTreesytoyperformyregression?
yShowythatywhenytheyerroryfunctionyisysquaredyerrorythatytheyexpectedyvalueyatyanyyleafyisytheymean.yTak
eytheyBostonyHousingydatasety(http://lib.stat.cmu.edu/datasets/
boston)yandyuseyDecisionyTreesytoyperformyregression.
5. SuggestyaylazyyversionyofytheyeagerydecisionytreeylearningyalgorithmyID3.yWhatyareytheyadvantagesyandy
disadvantagesyofyyourylazyyalgorithmycomparedytoytheyoriginalyeageryalgorithm?
6. Imagineyyouyhadyaylearningyproblemywithyanyinstanceyspaceyofypointsyonytheyplaneyandyaytargetyfunction
ythatyyouyknewytookytheyformyofyaylineyonytheyplaneywhereyallypointsyonyoneysideyofytheylineyareypositive
yandyallythoseyonytheyotheryareynegative.yIfyyouywereyconstrainedytoyonlyyuseydecisionytreeyorynearest-
neighborylearning,ywhichywouldyyouyuse?yWhy?
7. GiveytheyVCydimensionyofytheseyhypothesisyspaces,ybrieflyyexplainingyyouryanswers:
(a) Anyorigin-centeredycircley(2D)
(b) Anyorigin-centeredyspherey(3D)
y
, 8. Youyhaveytoycommunicateyaysignalyinyaylanguageythatyhasy3ysymbolsyA,yByandyC.yTheyprobabilityyofyob
servingyAyisy50%ywhileythatyofyobservingyByandyCyisy25%yeach.yDesignyanyappropriateyencodingyforythi
sylanguage.yWhatyisytheyentropyyofythisysignalyinybits?
9. ShowythatytheyK-
meansyprocedureycanybeyviewedyasyayspecialycaseyofytheyEMyalgorithmyappliedytoyanyappropriateymixtur
eyofyGaussianydensitiesymodel.
10. PlotytheydirectionyofytheyfirstyandysecondyPCAycomponentsyinytheyfiguresygiven.
11. Whichyclusteringymethod(s)yisymostylikelyytoyproduceytheyfollowingyresultsyatyky=y2?
yChooseytheymostylikelyymethod(s)yandybrieflyyexplainywhyyit/
theyywillyworkybetterywhereyothersywillynotyinyatymosty3ysentences.
• Hierarchicalyclusteringywithysingleylink
• Hierarchicalyclusteringywithycompleteylink
• Hierarchicalyclusteringywithyaverageylink
• K-means
• EM
(a) (b) (c)
2
y
Instructions
Thisyproblemysetyisynotyaypartyofyyouryfinalygradeybutyratheryaymeansytoyhelpyyouywithytheyfinalyexam.yIfyallyofytheyprobl
emsyareyattemptedyandyyourygradeyisyaroundytheycutoff,yweywillyroundyupytoytheyhigheryletterygrade.yYouywillyneedytoyat
temptyeachyproblemyandysubmityyourysolutionsyonyCanvas.yWeywillyverifyyworkyisysubmittedyatytheyendyofytheyterm.yAf
terytheydeadline,yweywillyprovideysolutionsyforyyouytoycompareyyouryanswers.yWeyplanytoyholdytwoyOfficeyHours,yoneyf
oryeachypartyofytheyproblemysetybeforeytheyfinal.
PartyOne
1. Whereyweyareydoingysupervisedylearning,yweyhaveymostlyyassumedyaydeterministicyfunction.yImagineyin
steadyayworldywhereyweyareytryingytoycaptureyaynon-
deterministicyfunction.yInythisycase,yweymightyseeytrainingypairsywhereytheyxyvalueyappearsyseveralytime
s,ybutywithydifferentyyyvalues.yForyexample,yweymightyuseyattributesyofyhumansytoytheyprobabilityythatyth
eyyhaveyhadychickenypox.yInythatycase,yweymightyseeytheysameykindyofypersonymanyytimesybutyonlyysom
etimesytheyymayyhaveyhadychickenypox.yWeywouldylikeytoybuildyaylearningyalgorithmythatywillycomputey
theyprobabilityythatyaypersonyhasychickenypox.ySo,ygivenyaysetyofytrainingydataywhereyeachyinstanceyisym
appedytoy1yforytrueyory0yforyfalse:
(a) DeriveytheyproperyerroryfunctionytoyuseyforyfindingytheyMLyhypothesisyusingyBayes’yRule.yYouysho
uldygoythroughyaysimilaryprocessyasytheyoneyusedytoyderiveyleastysquaredyerroryinytheylessons.
(b) Compareyandycontrastyyouryresultytoytheyruleyweyderivedyforyaydeterministicyfunctionyperturbedybyy
zero-
meanygaussianynoise.yWhatywouldyaynormalyneuralynetworkyusingysumyofysquaredyerrorsydoywithyt
heseydata?
yWhatyifytheydatayconsistedyofyx,yyypairsywhereyyywasyanyestimateyofytheyprobabilityyinsteadyofy0sya
ndy1s?
2. Designyaytwo-inputyperceptronythatyimplementsytheybooleanyfunctionyAy∧y¬B.yDesignyaytwo-
layerynetworkyofyperceptronsythatyimplementsyAy⊕yBy(wherey⊕yisyXOR).
3. Deriveytheyperceptronytrainingyruleyandygradientydescentytrainingyruleyforyaysingleyunitywithyoutputyo,yw
hereyoy=yw0y+yw1x1y+yw1x21y+y.y.y.y+ywnxny+ywnx2 n
y.yWhatyareytheyadvantagesyofyusingygradientydescent
trainingyruleyforytrainingyneuralynetworksyoverytheyperceptronytrainingyrule?
4. ExplainyhowyoneycanyuseyDecisionyTreesytoyperformyregression?
yShowythatywhenytheyerroryfunctionyisysquaredyerrorythatytheyexpectedyvalueyatyanyyleafyisytheymean.yTak
eytheyBostonyHousingydatasety(http://lib.stat.cmu.edu/datasets/
boston)yandyuseyDecisionyTreesytoyperformyregression.
5. SuggestyaylazyyversionyofytheyeagerydecisionytreeylearningyalgorithmyID3.yWhatyareytheyadvantagesyandy
disadvantagesyofyyourylazyyalgorithmycomparedytoytheyoriginalyeageryalgorithm?
6. Imagineyyouyhadyaylearningyproblemywithyanyinstanceyspaceyofypointsyonytheyplaneyandyaytargetyfunction
ythatyyouyknewytookytheyformyofyaylineyonytheyplaneywhereyallypointsyonyoneysideyofytheylineyareypositive
yandyallythoseyonytheyotheryareynegative.yIfyyouywereyconstrainedytoyonlyyuseydecisionytreeyorynearest-
neighborylearning,ywhichywouldyyouyuse?yWhy?
7. GiveytheyVCydimensionyofytheseyhypothesisyspaces,ybrieflyyexplainingyyouryanswers:
(a) Anyorigin-centeredycircley(2D)
(b) Anyorigin-centeredyspherey(3D)
y
, 8. Youyhaveytoycommunicateyaysignalyinyaylanguageythatyhasy3ysymbolsyA,yByandyC.yTheyprobabilityyofyob
servingyAyisy50%ywhileythatyofyobservingyByandyCyisy25%yeach.yDesignyanyappropriateyencodingyforythi
sylanguage.yWhatyisytheyentropyyofythisysignalyinybits?
9. ShowythatytheyK-
meansyprocedureycanybeyviewedyasyayspecialycaseyofytheyEMyalgorithmyappliedytoyanyappropriateymixtur
eyofyGaussianydensitiesymodel.
10. PlotytheydirectionyofytheyfirstyandysecondyPCAycomponentsyinytheyfiguresygiven.
11. Whichyclusteringymethod(s)yisymostylikelyytoyproduceytheyfollowingyresultsyatyky=y2?
yChooseytheymostylikelyymethod(s)yandybrieflyyexplainywhyyit/
theyywillyworkybetterywhereyothersywillynotyinyatymosty3ysentences.
• Hierarchicalyclusteringywithysingleylink
• Hierarchicalyclusteringywithycompleteylink
• Hierarchicalyclusteringywithyaverageylink
• K-means
• EM
(a) (b) (c)
2
y
