標準文檔1Givethedefinitionsoryourcomprehensionsofthefollowingterms.(12’)1.1TheinductivelearninghypothesisP171.2OverfittingP491.4ConsistentlearnerP1482Givebriefanswerstothefollowingquestions.(15’)2.2Ifthesizeofaversionspaceis|VS|,Ingeneralwhatisthesmallestnumberofqueriesmayberequiredbyaconceptlearnerusingoptimalquerystrategytoperfectlylearnthetargetconcept?P272.3Ingenaral,decisiontreesrepresentadisjunctionofconjunctionsofconstrainsontheattributevaluesofinstanse,thenwhatexpressiondoesthefollowingdecisiontreecorrespondsto?OutLookSunny Overcast RainHumidity Yes WindHigh Normal Strong WeakYes No Yes No3Givetheexplainationtoinductivebias,andlistinductivebiasofCANDIDATE-ELIMINATIONalgorithm,decisiontreelearning(ID3),BACKPROPAGATIONalgorithm.(10’)4 Howtosolveoverfittingindecisiontreeandneuralnetwork?(10 ’)Solution:Decisiontree:及早停止樹增長 (stopgrowingearlier)后修剪法(post-pruning)NeuralNetwork權值衰減(weightdecay)驗證數(shù)據(jù)集(validationset)實用大全標準文檔^5ProvethattheLMSweightupdaterule i i (Vtrain(b) V(b))xiperformsagradientdescenttominimizethesquarederror.Inparticular,definethesquarederrorEasinthetext.Now^calculatethederivativeofEwithrespecttotheweight i,assumingthatV(b)isalinearfunctionasdefinedinthetext.GradientdescentisachievedbyupdatingeachweightinproportionEto .Therefore,youmustshowthattheLMStrainingrulealtersweightsinthisproportioni^foreachtrainingexampleitencounters.( E (Vtrain(b) V(b))2) (8’)b,Vtrain(b) trainingexampleSolution：AsVtrain(b)?V(Successor(b))wecangetE=(Vtrain(b)?2V(b))?w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6V(b)E/wi2(Vtrain(b)?(b)?V(b))g(VtrainV(b))/wi=2(Vtrain(b)?V(b))gxiAsmentionedinLMS:

ii?(Vtrain(b)V(b))xiWecanget i i ( E/wi)/2Therefore,gradientdescentisachievementbyupdatingeachweightinproportionto E/ wi;LMSrulesaltersweightsinthisproportionforeachtrainingexampleitencounters.6Trueorfalse:ifdecisiontreeD2isanelaborationoftreeD1,thenD1ismore-general-thanD2.AssumeD1andD2aredecisiontreesrepresentingarbitrarybooleanfuncions,andthatD2isanelaborationofD1ifID3couldextendD1toD2.Iftruegiveaproof;iffalse,acounterexample.(Definition:Lethjandhkbeboolean-valuedfunctionsdefinedoverX.thenhjismore_general_than_or_equal_tohk(writtenhjghk)Ifandonlyif(xX)[(hk(x)1)(hj(x)1)]thenhjhk(hjghk)(hkghj))(10’)實用大全標準文檔Thehypothesisisfalse.OnecounterexampleisAXORBwhileifA!=B,trainingexamplesareallpositive,whileifA==B,trainingexamplesareallnegative,then,usingID3toextendD1,thenewtreeD2willbeequivalenttoD1,i.e.,D2isequaltoD1.7Designatwo-input perceptronthatimplements thebooleanfunction A B.Designatwo-layernetworkofperceptronsthatimplements AXORB.(10’)8Supposethatahypothesisspacecontainingthreehypotheses,h1,h2,h3,andtheposteriorprobabilitiesofthesetypothesesgiventhetrainingdataare0.4,0.3and0.3respectively.Andifanewinstancex isencountered,which isclassifiedpositiveby h1,butnegativebyh2andh3,thengivetheresultanddetailclassificationcourseofBayesoptimalclassifier.(10 ’)P1259SupposeSisacollectionoftraining-exampledaysdescribedbyattributesincludingHumidity,whichcanhavethevaluesHighorNormal.AssumeSisacollectioncontaining10examples,[7+,3-].Ofthese10examples,suppose3ofthepositiveand2ofthenegativeexampleshaveHumidity=High,andtheremainderhaveHumidity=Normal.Pleasecalculatetheinformationgainduetosortingtheoriginal10examplesbytheattributeHumidity.(log21=0,log22=1,log23=1.58,log24=2,log25=2.32,log26=2.58,log27=2.8,log28=3,log29=3.16,log210=3.32,)(5’)HumidityS:[7+,3-]High Normal[3+,2-] [4+,1-]Solution：7733(a)HerewedenoteS=[7+,3-],thenEntropy([7+,3-])=10log21010log210=0.886;(b)Gain(S,Humidity)=Entropy(S)-SvEntropy(Sv)Gain(S,a2)vvalues(Humidityi)SQValues(Humidity)={High,Normal}SHigh{sS|Humidity()}sHigh實用大全標準文檔3322Entropy(SHigh)=-5log25-5log250.972,SHigh5=4Entropy(SNormal4log2411)=--log20.72,SNormal=55555ThusGain(S,Humidity)=0.886-(50.9725*0.72)=0.04101010Finishthefollowingalgorithm.(10’)(1)GRADIENT-DESCENT(trainingexamples,)Eachtrainingexampleisapairoftheform

r rx,t ,where xisthevectorofinputvalues,andtisthetargetoutputvalue. isthelearningrate(e.g.,0.05).Initializeeach i tosomesmallrandomvalueUntiltheterminationconditionismet,DoInitializeeach

tozero.rForeach x,t intraining_examples,DorInputtheinstance xtotheunitandcomputetheoutputoForeachlinearunitweight i,DoForeachlinearunitweight i,Doi i i(2)