I många naturligt förekommande optimeringsproblem måste man se till att definitionen av optimeringsproblemet lämpar sig för lösningar som går att beräkna. I de fall där exakta lösningar inte kan beräknas på ett korrekt sätt är det fördelaktigt att ha starka garantier för ungefärliga lösningar. I ordning fungerar under dessa kriterier de flesta optimeringsproblem är gjutna under paraply av konvexitet eller submodularitet. I denna rapport kommer vi att studera design och optimering över en gemensam klass av funktioner som kallas submodulära funktioner. Set funktioner, och särskilt submodulära set funktioner, karakteriserar ett brett utbud av naturligt förekommande optimeringsproblem, och egenskapen submodularitet av set funktioner har djupa teoretiska konsekvenser med omfattande tillämpningar. Informellt, egenskapen submodularitet av uppsättningar funktioner gäller den intuitiva principen om minskande avkastning. Denna egenskap säger att lägga till ett element till en mindre uppsättning har mer värde än att lägga till det till en större uppsättning. Vanliga exempel på submodulära monotona funktioner är entropier, konkava funktioner av kardinalitet, och matris rank funktioner; icke-monotona exempel inkluderar graf skärningar, nätverksflöden, och ömsesidig information. I detta dokument kommer vi att se över den formella definitionen av submodularitet; optimering av submodulära funktioner, både maximering och minimering; och slutligen diskutera vissa tillämpningar i samband med lärande och resonemang med hjälp av submodulära funktioner.
Submodularitet REF är en egenskap hos set funktioner som modellerar naturligt minskande avkastning egendom.
Learning and Optimization with Submodular Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}