机器学习考试卷 final2007s-solution 

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