2.Nowdrawadatasetonthefollowing2plotssothatapoint-basedlook-aheaddecisiontreewithonelevel(4regions)willpoorlyclassifythedata,butaboundary-basedlook-aheaddecisiontreewithonelevel(4regions)willperfectlyclassifythedata.Use’+’and’-’toindicatetheclassofeachpointanddrawinthedecisionregionboundariesofeachdecisiontree.
Point-basedLook-aheadDecisionTreeBoundary-basedLook-aheadDecisionTree
3.Nowprovidetherunningtimerequiredforonelevelofthepartitioninginthevariousdecisiontreevariants.AssumethereareDpointsinthetrainingsetallwithuniqueXandYvalues.Explainyourreasoning.StandardDecisionTree
Point-BasedLook-aheadDecisionTree
Boundary-BasedLook-aheadDecisionTree
11
5NeuralNetworks
RecallthetwotypesofNeuralNetworkactivationfunctionsfromHomework2,thelinearactivationfunctionandthehardthreshold:
??
?lineary=w0+iwixi,?hardthreshold
y=
??
1ifw0+iwixi≥0,0otherwise.
??
(1)
1.Whichofthefollowingfunctionscanbeexactlyrepresentedbyaneuralnetworkwithonehiddenlayerwhichuseslinearand/orhardthresholdactivationfunctions?Foreachcase,justifyyouranswer.
(a)polynomialsofdegreeone
(b)hingeloss(h(x)=max(1-x,0))
(c)polynomialsofdegreetwo
(d)piecewiseconstantfunctions
12
6[points]VCDimentia
GivenahypothesisclassH,theVCdimension,VC(H)isde?nedtobethesizeofthelargestsetthatisshatteredbyH.IfHcanshatterarbitrarilylargesets,thenwesaythatVC(H)=∞.
1.ItissometimesusefultothinkofVCdimensionasbeingrelatedtothenumberofparametersneededtospecifyanelementofH.Forexample,whatistheVCdimensionofthesetofhypothesesofthefollowingform?
??
1ifαdxd+αd?1xd?1+···+α0>0
hα(x)=
0otherwiseJustifyyouranswer.
Hint:thinkpolynomialbasisfunctions
2.Despitetheresultfrompart(1),theVCdimensionisnotalwayssonicelyrelated
tothenumberofparameters.ForanypositiveintegerM,canyoucomeupwithahypothesisclasswhichtakesMparametersbuthasVCdimension1?Hint:Thinkofhowyoumightencodeseveralparameterswithjustoneparameter.
13
3.Considertheclassofhypothesesoftheform:
??
1ifsin(αx)>0
hα(x)=
0otherwise
Youwillshowthatthisone-parameterhypothesisclasshasin?niteVCdimension.Todothis,showthatgiventhedatapointsX={xi=10?i,i=1,...,n},anysetof
labelsyi∈{0,1}canberealizedbyhαbysetting
????n??
α=1+(1?ti)10i·π
i=1
Forexample,ifn=5andyi=(1,1,1,1,0),thenα=(100001)π.
Hint:Onintervalsoftheform(mπ,(m+1)π),thesinefunctiontakespositivevalues
ifmisevenandnegativevaluesifmisodd.
14
机器学习考试卷 final2007s-solution
