eduzhai > Applied Sciences > Engineering >

Submodularity in Action From Machine Learning to Signal Processing Applications

  • Save

... pages left unread,continue reading

Document pages: 12 pages

Abstract: Submodularity is a discrete domain functional property that can beinterpreted as mimicking the role of the well-known convexity concavityproperties in the continuous domain. Submodular functions exhibit strongstructure that lead to efficient optimization algorithms with provablenear-optimality guarantees. These characteristics, namely, efficiency andprovable performance bounds, are of particular interest for signal processing(SP) and machine learning (ML) practitioners as a variety of discreteoptimization problems are encountered in a wide range of applications.Conventionally, two general approaches exist to solve discrete problems: $(i)$relaxation into the continuous domain to obtain an approximate solution, or$(ii)$ development of a tailored algorithm that applies directly in thediscrete domain. In both approaches, worst-case performance guarantees areoften hard to establish. Furthermore, they are often complex, thus notpractical for large-scale problems. In this paper, we show how certainscenarios lend themselves to exploiting submodularity so as to constructscalable solutions with provable worst-case performance guarantees. Weintroduce a variety of submodular-friendly applications, and elucidate therelation of submodularity to convexity and concavity which enables efficientoptimization. With a mixture of theory and practice, we present differentflavors of submodularity accompanying illustrative real-world case studies frommodern SP and ML. In all cases, optimization algorithms are presented, alongwith hints on how optimality guarantees can be established.

Please select stars to rate!

         

0 comments Sign in to leave a comment.

    Data loading, please wait...
×