Vi utökar arbetet av Narasimhan och Bilmes [32] för att minimera uppsättning funktioner som kan representeras som en skillnad mellan submodulära funktioner. Liknar [32], våra nya algoritmer garanteras att monotont minska den objektiva funktionen i varje steg. Vi empiriskt och teoretiskt visar att periterationskostnaden för våra algoritmer är mycket lägre än [32], och våra algoritmer kan användas för att effektivt minimera en skillnad mellan submodulära funktioner under olika kombinatoriska begränsningar, ett problem som inte tidigare behandlats. Vi tillhandahåller beräkningsbegränsningar och ett hårdhetsresultat på den multiplikativa omätbarheten av att minimera skillnaden mellan submodulära funktioner. Vi visar dock att det är möjligt att ge värsta fall tillsatsgränser genom att tillhandahålla en polynom tid som kan beräknas lägre på minima. Slutligen visar vi hur ett antal maskininlärningsproblem kan modelleras som att minimera skillnaden mellan submodulära funktioner. Vi experimentellt visa giltigheten av våra algoritmer genom att testa dem på problemet med funktionsval med submodulära kostnadsfunktioner.
Iyer och Bilmes REF undersökte att optimera skillnaden mellan två submodulära funktioner.
Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
{'venue': 'UAI-2012', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}