Abstract We develop and analyze an algorithm for nonparametric estimation of divergencefunctionals and the density ratio of two probability distributions. Our method is based on a variational characterization of f-divergences, which turns the estima-tion i
Estimatingdivergencefunctionalsandthelikelihood
ratiobypenalizedconvexriskminimizationXuanLongNguyen
SAMSI&DukeUniversityMartinJ.WainwrightUCBerkeleyMichaelI.JordanUCBerkeley
Abstract
Wedevelopandanalyzeanalgorithmfornonparametricestimationofdivergencefunctionalsandthedensityratiooftwoprobabilitydistributions.Ourmethodisbasedonavariationalcharacterizationoff-divergences,whichturnstheestima-tionintoapenalizedconvexriskminimizationproblem.Wepresentaderivationofourkernel-basedestimationalgorithmandananalysisofconvergenceratesfortheestimator.Oursimulationresultsdemonstratetheconvergencebehaviorofthemethod,whichcomparesfavorablywithexistingmethodsintheliterature.
1Introduction
Animportantclassof“distances”betweenmultivariateprobabilitydistributionsPandQaretheAli-Silveyorf-divergences[1,6].Thesedivergences,tobede nedformallyinthesequel,areallofthe formDφ(P,Q)=φ(dQ/dP)dP,whereφisaconvexfunctionofthelikelihoodratio.Thisfamily,includingtheKullback-Leibler(KL)divergenceandthevariationaldistanceasspecialcases,playsanimportantroleinvariouslearningproblems,includingclassi cation,dimensionalityreduction,featureselectionandindependentcomponentanalysis.Foralloftheseproblems,iff-divergencesaretobeusedascriteriaofmerit,onehastobeabletoestimatethemef cientlyfromdata.Withthismotivation,thefocusofpaperistheproblemofestimatinganf-divergencebasedoni.i.d.samplesfromeachofthedistributionsPandQ.Ourstartingpointisavariationalcharacterizationoff-divergences,whichallowsourproblemtobetackledviaanM-estimationprocedure.Speci -cally,thelikelihoodratiofunctiondP/dQandthedivergencefunctionalDφ(P,Q)canbeestimatedbysolvingaconvexminimizationproblemoverafunctionclass.Inthispaper,weestimatethelike-lihoodratioandtheKLdivergencebyoptimizingapenalizedconvexrisk.Inparticular,werestricttheestimatetoaboundedsubsetofareproducingkernelHilbertSpace(RKHS)[17].TheRKHSissuf cientlyrichformanyapplications,andalsoallowsforcomputationallyef cientoptimizationprocedures.Theresultingestimatorisnonparametric,inthatitentailsnostrongassumptionsontheformofPandQ,exceptthatthelikelihoodratiofunctionisassumedtobelongtotheRKHS.Thebulkofthispaperisdevotedtothederivationofthealgorithm,andatheoreticalanalysisoftheperformanceofourestimator.Thekeytoouranalysisisabasicinequalityrelatingaperformancemetric(theHellingerdistance)ofourestimatortothesupremaoftwoempiricalprocesses(withrespecttoPandQ)de nedonafunctionclassofdensityratios.ConvergenceratesarethenobtainedusingtechniquesforanalyzingnonparametricM-estimatorsfromempiricalprocesstheory[20].Relatedwork.Thevariationalrepresentationofdivergenceshasbeenderivedindependentlyandexploitedbyseveralauthors[5,11,14].BroniatowskiandKeziou[5]studiedtestingandestimationproblemsbasedondualrepresentationsoff-divergences,butworkinginaparametricsettingasop-posedtothenonparametricframeworkconsideredhere.Nguyenetal.[14]establishedaone-to-onecorrespondencebetweenthefamilyoff-divergencesandthefamilyofsurrogatelossfunctions[2],throughwhichthe(optimum)“surrogaterisk”isequaltothenegativeofanassociatedf-divergence.Anotherlinkistotheproblemofestimatingintegralfunctionalsofasingledensity,withtheShan-nonentropybeingawell-knownexample,whichhasbeenstudiedextensivelydatingbacktoearly
Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization XuanLong Nguyen SAMSI & Duke University Martin J. Wainwright ...
Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization XuanLong Nguyen SAMSI & Duke University Martin J. Wainwright ...
热门文档