资源描述：
《Maximizing submodular functions最大化子模函数 使用概率图形模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、MaximizingsubmodularfunctionsusingprobabilisticgraphicalmodelsK.S.SeshKumarFrancisBachINRIA-Sierraproject-teamINRIA-Sierraproject-teamD´epartementd’InformatiqueD´epartementd’Informatiquedel’EcoleNormaleSup´erieuredel’EcoleNormaleSup´erieureParis,FranceParis,Francesesh-kumar.karri@inria.frfranci
2、s.bach@inria.frJuly16,2018AbstractWeconsidertheproblemofmaximizingsubmodularfunctions;whilethisproblemisknowntobeNP-hard,severalnumericallyefficientlocalsearchtechniqueswithapproximationguar-anteesareavailable.Inthispaper,weproposeanovelconvexrelaxationwhichisbasedontherelationshipbetweensubmodul
3、arfunctions,entropiesandprobabilisticgraphicalmodels.Inagraphicalmodel,theentropyofthejointdistributiondecomposesasasumofmarginalentropiesofsubsetsofvariables;moreover,foranydistribution,theentropyoftheclosestdistributionfactorizinginthegraphicalmodelprovidesanboundontheentropy.Fordirectedgraph
4、icalmodels,thislastpropertyturnsouttobeadirectconsequenceofthesubmodularityoftheentropyfunction,andallowsthegeneralizationofgraphical-model-basedupperboundstoanysubmodularfunctions.Theseupperboundsmaythenbejointlymaximizedwithrespecttoaset,whileminimizedwithrespecttothegraph,leadingtoaconvexvar
5、iationalinferenceschemeformaximizingsubmodularfunctions,basedonouterapproximationsofthemarginalpolytopeandmaximumlikelihoodboundedtreewidthstructures.Byconsideringgraphsofincreasingtreewidths,wemaythenexplorethetrade-offbetweencomputationalcomplexityandtight-nessoftherelaxation.Wealsopresentexte
6、nsionstoconstrainedproblemsandmaximizingthedifferenceofsubmodularfunctions,whichincludeallpossiblesetfunctions.arXiv:1309.2593v1[cs.LG]10Sep20131IntroductionOptimizingsubmodularfunctionshasbeenanactiveareaofresearchwithapplicationsingraph-cut-basedimagesegmentation[4],sensorplacement[17],ordocum
7、entsummarization[20].AsetfunctionFisafunctiondefinedonthepowerset2VofacertainsetV.ItissubmodularifandonlyifforallA,B⊆V,F(A)+F(B)>F(A∩B)+F(A∪B).Equivalently,thesefunctionsalsoadmitthediminishingreturnsproperty,i.e.,themarginalcostof
