I detta dokument presenterar vi en algoritm för att minimera skillnaden mellan två submodulära funktioner med hjälp av en variationsram som bygger på (en förlängning av) konkav-konvex procedur [17]. Eftersom flera vanliga mått i maskininlärning, som ömsesidig information och villkorlig ömsesidig information, är submodulära, problemet med att minimera skillnaden mellan två submodulära problem uppstår naturligt i många maskininlärning applikationer. Två sådana tillämpningar är att lära sig discriminativt strukturerade grafiska modeller och funktionsval under computational komplexitet begränsningar. Ett vanligt mått för mätning av diskriminativ kapacitet är EAR-måttet som är skillnaden mellan två villkorade ömsesidiga informationstermer. Val av funktioner som tar hänsyn till komplexiteten faller också in i detta ramverk eftersom både den information som en uppsättning funktioner ger och kostnaden för beräkning och användning av funktionerna kan modelleras som submodulfunktioner. Detta problem är NPhard, och vi ger en polynom tid heuristic för det. Vi presenterar också resultat på syntetiska data för att visa att klassificeringar baserade på diskriminerande grafiska modeller med hjälp av denna algoritm avsevärt kan överträffa klassificeringar baserade på generativa grafiska modeller.
En av dessa metoder är SSP som är utformad för att minimera skillnaden mellan två submodulära funktioner REF.
A submodular-supermodular procedure with applications to discriminative structure learning
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}