Attribute-efficient learningof decision lists and linear threshold functions under unconcen
- 格式：pdf
- 大小：110.86 KB
- 文档页数：8
PhilipM.LongGoogleMountainView,CAplong@google.comRoccoA.ServedioDepartmentofComputerScienceColumbiaUniversityNewYork,NYrocco@cs.columbia.edu
AbstractWeconsiderthewell-studiedproblemoflearningdecisionlistsusingfewexam-pleswhenmanyirrelevantfeaturesarepresent.Weshowthatsmoothboostingal-gorithmssuchasMadaBoostcanefficientlylearndecisionlistsoflengthkovernbooleanvariablesusingpoly(k,logn)manyexamplesprovidedthatthemarginaldistributionovertherelevantvariablesis“nottooconcentrated”inanL2-normsense.UsingarecentresultofH˚astad,weextendtheanalysistoobtainasimilar(thoughquantitativelyweaker)resultforlearningarbitrarylinearthresholdfunc-tionswithknonzerocoefficients.Experimentalresultsindicatethattheuseofasmoothboostingalgorithm,whichplaysacrucialroleinouranalysis,hasanimpactontheactualperformanceofthealgorithm.
1IntroductionAdecisionlistisaBooleanfunctiondefinedovernBooleaninputsofthefollowingform:ifℓ1thenb1elseifℓ2thenb2...elseifℓkthenbkelsebk+1.Hereℓ1,...,ℓkareliteralsdefinedoverthenBooleanvariablesandb1,...,bk+1areBooleanvalues.SincetheworkofRivest[24]decisionlistshavebeenwidelystudiedinlearningtheoryandmachinelearning.
Aquestionthathasreceivedmuchattentioniswhetheritispossibletoattribute-efficientlylearndecisionlists,i.e.tolearndecisionlistsoflengthkovernvariablesusingonlypoly(k,logn)manyexamples.ThisquestionwasfirstaskedbyBlumin1990[3]andhassincebeenre-posednumeroustimes[4,5,6,29];aswenowbrieflydescribe,arangeofpartialresultshavebeenobtainedalongdifferentlines.
Severalauthors[4,29]havenotedthatLittlestone’sWinnowalgorithm[17]canlearndecisionlistsoflengthkusing2O(k)lognexamplesintime2O(k)nlogn.Valiant[29]andNevoandEl-Yaniv[21]sharpenedtheanalysisofWinnowinthespecialcasewherethedecisionlisthasonlyaboundednumberofalternationsinthesequenceofoutputbitsb1,...,bk+1.Itiswellknownthatthe“halvingalgorithm”(see[1,2,19])canlearnlength-kdecisionlistsusingonlyO(klogn)examples,buttherunningtimeofthealgorithmisnk.KlivansandServedio[16]usedpolynomialthresholdfunc-tionstogetherwithWinnowtoobtainatradeoffbetweenrunningtimeandthenumberofexamples
required,bygivinganalgorithmthatrunsintimen˜O(k1/3)anduses2˜O(k1/3)lognexamples.
Inthisworkwetakeadifferentapproachbyrelaxingtherequirementthatthealgorithmworkunderanydistributiononexamplesorinthemistake-boundmodel.Thisrelaxationinfactallowsustohan-dlenotjustdecisionlists,butarbitrarylinearthresholdfunctionswithknonzerocoefficients.(Recallthatalinearthresholdfunctionf:{−1,1}n→{−1,1}nisafunctionf(x)=sgn(ni=1wixi−θ)wherewi,θarerealnumbersandthesgnfunctionoutputsthe±1numericalsignofitsargument.)
Theapproachandresults.Wewillanalyzeasmoothboostingalgorithm(seeSection2)togetherwithaweaklearnerthatexhaustivelyconsidersall2npossibleliteralsxi,¬xiasweakhypotheses.Thealgorithm,whichwecallAlgorithmA,isdescribedinmoredetailinSection6.
Thealgorithm’sperformancecanbeboundedintermsoftheL2-normofthedistributionoverexam-ples.RecallthattheL2-normofadistributionDoverafinitesetXisD2:=(x∈XD(x)2)1/2.TheL2normcanbeusedtoevaluatethe“spread”ofaprobabilitydistribution:iftheprobabilityisconcentratedonaconstantnumberofelementsofthedomainthentheL2normisconstant,whereasiftheprobabilitymassisspreaduniformlyoveradomainofsizeNthentheL2normis1/√
ǫ,τ,log1ǫ,log1δ)examples,AlgorithmArunsinpoly(n,2˜O((τ/ǫ)2),log1LetD1,D2betwodistributions.Forκ≥1wesaythatD1isκ-smoothwithrespecttoD2ifforallx∈{−1,1}n,D1(x)/D2(x)≤κ.
Following[15],wesaythataboostingalgorithmBisκ(ǫ,γ)-smoothifforanyinitialdistributionDandanydistributionDtthatisgeneratedstartingfromDwhenBisusedtoboosttoǫ-accuracywithγ-weakhypothesesateachstage,Dtisκ(ǫ,γ)-smoothw.r.t.D.Itisknownthattherearealgorithmsthatareκ-smoothforκ=Θ(1
ǫ-smoothw.r.t.theuniformdistributionUsatisfiesD2/U2≤
2k/2onasinglepointanddistributestheremainingweightuniformlyontheother2k−1pointsisonly2k/2-smooth(i.e.verynon-smooth)butsatisfiesD2/Uk2=Θ(1).ThustheL2-normconditionweconsiderinthispaperisaweakerconditionthansmoothnesswithrespecttotheuniformdistribution.
3TotalvariationdistanceandL2-normofdistributionsThetotalvariationdistancebetweentwoprobabilitydistributionsD1,D2overafinitesetXisdTV:=maxS⊆XD1(S)−D2(S)=1
4||D||22
.
Proof:LetM=||D||2
|X|.
ByMarkov’sinequality,
Prx∼D[D(x)≥2M2U(x)]=Prx∼D[D(x)≥2M2
2M2≥14WeakhypothesesfordecisionlistsLetfbeanydecisionlistthatdependsonkvariables:ifℓ1thenoutputb1else···elseifℓkthenoutputbkelseoutputbk+1(2)whereeachℓiiseither“(xi=1)”or“(xi=−1).”Thefollowingfolklorelemmacanbeprovedbyaneasyinduction(seee.g.[12,26]forproofsofessentiallyequivalentclaims):
