{"id":190301,"date":"2014-01-08T00:00:00","date_gmt":"2014-01-08T13:06:38","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/tutorials-session-a-deep-mathematical-properties-of-submodularity-with-applications-to-machine-learning\/"},"modified":"2016-07-15T15:14:17","modified_gmt":"2016-07-15T22:14:17","slug":"tutorials-session-a-deep-mathematical-properties-of-submodularity-with-applications-to-machine-learning","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/tutorials-session-a-deep-mathematical-properties-of-submodularity-with-applications-to-machine-learning\/","title":{"rendered":"Tutorials Session A &#8211; Deep Mathematical Properties of Submodularity with Applications to Machine Learning"},"content":{"rendered":"<div class=\"asset-content\">\n<p>Submodular functions have received significant attention in the  mathematics community owing to their natural and wide ranging  applicability. Submodularity has a very simple definition which belies  a treasure trove of consequent mathematical richness. This tutorial  will attempt to convey some of this richness.<\/p>\n<p>We will start by defining submodularity and polymatroidality \u2014 we  will survey a surprisingly diverse set of functions that are  submodular and operations that (sometimes remarkably) preserve  submodularity. Next, we&#8217;ll define the submodular polytope, and its  relationship to the greedy algorithm and its exact and efficient  solution to certain linear programs with an exponential number of  constraints. We will see how submodularity shares certain properties  with convexity (efficient minimization, discrete separation,  subdifferentials, lattices and sub-lattices, and the convexity of the  Lovasz extension), concavity (via its definition, submodularity via  concave functions, superdifferentials), and neither (simultaneous sub-  and super-differentials, efficient approximate maximization). The  Lovasz extension will be given particular attention due to its growing  use for structured convex norms and surrogates in relaxation methods.  We will survey both constrained and unconstrained submodular  optimization (including the minimum norm point algorithm), discussing  what is currently known about hardness (both upper and lower bounds),  and also when algorithms or instances are practical.<\/p>\n<p>As to applications, it is interesting that a submodular function  itself can often be seen as a parameter to instantiate a  machine-learning instance \u2014 this includes active\/semi-supervised  learning, structured sparsity inducing norms, combinatorial  independence and generalized entropy, and rank-order based  divergences. Other examples include feature selection, data subset (or  core set) selection, inference in graphical models with high  tree-width and global potentials in computer vision, and influence  determination in social networks.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Submodular functions have received significant attention in the mathematics community owing to their natural and wide ranging applicability. Submodularity has a very simple definition which belies a treasure trove of consequent mathematical richness. This tutorial will attempt to convey some of this richness. We will start by defining submodularity and polymatroidality \u2014 we will survey [&hellip;]<\/p>\n","protected":false},"featured_media":198069,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-190301","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/ZycBUGLD22E","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/190301","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/190301\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/198069"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=190301"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=190301"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=190301"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=190301"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=190301"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=190301"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=190301"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=190301"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=190301"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=190301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}