submodulær

Submodulær er en egenskap ved mengdefunksjoner f: 2^N → R. Funksjonen kalles submodulær hvis for alle A ⊆ B ⊆ N og x ∉ B er marginalnytten av x ikke større i B enn i A: f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B). En ofte brukt likhet er f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B). Hvis f også er ikke-nedadstigende, kalles den monotont submodulær.

Intuitivt betyr det at tillegget av et nytt element gir mindre eller lik nytte når mengden allerede er større.

Eksempler: Funksjoner som teller dekket antall elementer i et sett av velgte delmengder (for eksempel i et set cover-problem), samt entropi og informasjonsgevinst, er submodulære. Også graf-relaterte funksjoner som kuttfunksjonen i et nettverk viser submodularitet. Mange beslutnings- og maskinlæringsproblemer har submodulære egenskaper som gjør dem behandlelige teoretisk og praktisk.

Anvendelser: For maksimering av monotone submodulære funksjoner under en kardinalitetsbegrensning gir den gredige metoden en garanti på (1 − 1/e) nærhet til optimalet. Ikke-monotone varianter kan også tilnærmes med effektive algoritmer. Submodulær minimering kan utføres i polynomtid med spesialiserte metoder. Vanlige bruksområder inkluderer funksjonsutvelgelse (feature selection), dokumentoppsummering, sensorplassering og påvirkningsmodellering i sosiale nettverk.

Opprinnelse: Begrepet og studiet av submodularitet ble utviklet i 1970-årene og 1980-årene; viktige bidrag kom fra Nemhauser, Wolsey og Fisher i 1978, som blant annet ga gredige-tilnæringsgarantier for monotone submodulære funksjoner. Submodularitet kan ses som en disiplinell analog til convexitet i kontinuerlig optimisation.