欢迎来到天天文库
浏览记录
ID:38196682
大小:115.85 KB
页数:5页
时间:2019-05-27
《Using Prior Knowledge with Adaptive Probing》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、UsingPriorKnowledgewithAdaptiveProbingWheelerRumlDivisionofEngineeringandAppliedSciencesHarvardUniversity33OxfordStreetCambridge,MA02138ruml@eecs.harvard.eduAbstractAdaptiveprobing(Ruml2001)isastochasticsamplingmethodthatattemptstoadjusttothetreeon-line,ratherWhensearchingatreetofindt
2、hebestleaf,completesearchthanusingaprespecifiedordering.Thealgorithmiterativelymethodssuchasdepth-firstsearchanddepth-boundeddis-crepancysearchuseafixeddeterministicorderthatmayorprobesfromtheroottoaleaf.Startingwithoutpreconcep-maynotbeappropriateforthetreeathand.Adaptiveprob-tionsabou
3、twhetherornottofollowtheheuristic,theob-ingisarecently-proposedstochasticmethodthatattemptstoservedleafcostsareusedtoincrementallybuildamodelofadjustitssamplingon-linetofocusonareasofthetreethatthetree.Inamannerreminiscentofreinforcementlearn-seemtocontaingoodsolutions.Whileeffective
4、onavarietying,theestimatesaresimultaneouslyusedduringprobingtooftrees,adaptiveprobingwastestimelearningbasicfeatureschoosewhichchildtoexpand.Thisapproachallowstheal-oftheproblemthatarebuiltintootheralgorithms,suchasthegorithmtoadjusttotheparticulartreeitfindsitselfin,learn-factthatthe
5、heuristicisoftenhelpful.Inthispaper,weinves-ingwhentotrusttheheuristicandwhennotto.tigatetwosimplemethodsforaddingsuchpriorknowledgetoRuml(2001)presentsresultsshowingthatadaptiveprob-adaptiveprobing.Thefirstsimplyreusesthemodellearnedingcansuccessfullyadapttoawidevarietyoftreesandthat
6、duringapreviousrunonasimilarproblem.Thesecondusesaheuristicallybiasedpolicyatthestartofthesearch,graduallyitiscompetitivewithsystematicalgorithmsexceptwhenthedeferringtolearnedinformationinlateriterations.Empiricalheuristicisveryaccurate.Whentheheuristicisveryoftenresultsontwodiffere
7、ntrepresentationsofnumberpartition-correct,adaptiveprobingsufferstheoverheadofhavingtoingconfirmthatthesemethodscanallowadaptiveprobingdiscoverthatfactfromscratch.Inthispaper,weinvestigatetosearchefficientlyfromtheverystartofarun.However,twomethodsforremedyingthisliability.Botharebased
8、onreusingpre
此文档下载收益归作者所有