Submodular functions characterize mathematically the ubiquitous ``diminishing-returns'’ property. They are widely used to describe core subjects in numerous applications, including economic utility, redundancy in information, spread of influence in social networks, and more. Optimization of submodular functions thus plays a central role in a broad range of applications in data science. However, existing works concentrate largely on optimizing a single submodular function, with a sole focus on succinct subset selection among massive data. Other circumstances have not been fully explored, for example, when there exists interplay between a submodular function and other components.

In this thesis, we study optimization beyond a single (non-decreasing) submodular function in the following three areas.

• Ranking: Ranking arises naturally in the presence of multiple submodular functions, for instance, when a list of shared resources is sequentially served to satisfy multiple submodular demands with individual budgets. One concrete example is ranking web pages to satisfy multiple user intents with different ``patience.'' We first study this ranking problem under cardinality constraints, and then we consider extensions of the basic setting, including knapsack constraints, streaming settings, and robustness requirements.
• Decision trees: A tree (or a policy) can be seen as an adaptive generalization of ranking. Popular decision trees for classification, including CART and C4.5, are constructed by recursive greedy splits, guided by some impurity function. These trees are accurate, but may not be easy to understand due to a potentially large tree size. A novel characterization of a decision tree is via adaptive intersection among multiple submodular functions, one for each object to be classified. We discover that this characterization enables one to analyze and control the tree complexity for a large family of impurity functions. As a consequence, we are able to produce accurate and interpretable decision trees with bounded complexity.
• Diversity: Multi-objective optimization is frequently encountered in reality. One specific important form is a joint optimization of utility and diversity, where utility is often modeled by a submodular function. From the theoretical side, we discuss new techniques for such joint optimization over clustered input; from the practical side, we propose one novel application in learning diverse rule sets, where diversity encourages non-overlapping rules that deliver desirable unambiguous decisions.    

For each of the three areas discussed above, we introduce novel formulations for applications in data science, and devise algorithms that are efficient, easy to implement, and have provable approximation guarantees. In addition to theory, we also highlight their practical potential by presenting empirical performance in selected applications. Our work significantly enhances the modeling capabilities of submodular optimization for novel application domains.

Submodulära funktioner karakteriserar matematiskt den allestädes närvarande egenskapen ``minskande avkastning''. De används ofta för att beskriva kärnämnen i många tillämpningar, inklusive ekonomisk nytta, redundans i information, spridning av inflytande i sociala nätverk och mer. Optimering av submodulära funktioner spelar således en central roll i ett brett spektrum av tillämpningar inom datavetenskap. Befintliga arbeten koncentrerar sig dock till stor del på att optimera en enda submodulär funktion, med enbart fokus på kortfattat urval av delmängder bland massiva data. Andra omständigheter har inte undersökts fullt ut, till exempel när det finns ett samspel mellan en submodulär funktion och andra komponenter.

I denna avhandling studerar vi optimering bortom en enda (icke-minskande) submodulär funktion inom följande tre områden.

• Ranking: Rangordning uppstår naturligt i närvaro av flera submodulära funktioner, till exempel när en lista med delade resurser serveras sekventiellt för att tillfredsställa flera submodulära krav med individuella budgetar. Ett konkret exempel är att rangordna webbsidor för att tillfredsställa flera användares avsikter med olika ``tålamod''. Vi studerar först detta rankningsproblem under kardinalitetsbegränsningar, och sedan överväger vi utökningar av den grundläggande inställningen, inklusive ryggsäcksbegränsningar, strömningsinställningar och robusthetskrav.
• Beslutsträd: Ett träd (eller en policy) kan ses som en adaptiv generalisering av rangordning. Populära beslutsträd för klassificering, inklusive CART och C4.5, är konstruerade av rekursiva giriga splittringar, styrda av någon orenhetsfunktion. Dessa träd är korrekta, men kanske inte är lätta att förstå på grund av en potentiellt stor trädstorlek. En ny karaktärisering av ett beslutsträd sker via adaptiv skärningspunkt mellan flera submodulära funktioner, en för varje objekt som ska klassificeras. Vi upptäcker att denna karakterisering gör det möjligt för en att analysera och kontrollera trädets komplexitet för en stor familj av föroreningsfunktioner.Som en konsekvens kan vi producera korrekta och tolkningsbara beslutsträd med begränsad komplexitet.
• Mångfald: Multi-objektiv optimering påträffas ofta i verkligheten. En specifik viktig form är en gemensam optimering av nytta och mångfald, där nytta ofta modelleras av en submodulär funktion. Från den teoretiska sidan diskuterar vi nya tekniker för sådan gemensam optimering över klustrad input; Från den praktiska sidan föreslår vi en ny tillämpning för att lära sig olika regeluppsättningar, där mångfald uppmuntrar icke-överlappande regler som ger önskvärda entydiga beslut.

För vart och ett av de tre områden som diskuterats ovan, vi introducerar nya formuleringar för tillämpningar inom datavetenskap och utvecklar algoritmer som är effektiva, lätta att implementera och har bevisbara approximationsgarantier. Utöver teori lyfter vi också fram deras praktiska potential genom att presentera empiriska prestationer i utvalda tillämpningar. Vårt arbete förbättrar avsevärt modelleringsmöjligheterna för submodulär optimering för nya applikationsdomäner.