Discrete Optimization in Machine Learning

Discrete Optimization in Machine Learning

5 Lectures · Dec 17, 2011

About

Fortunately, most discrete optimization problems that arise in machine learning have specific structure, which can be leveraged in order to develop tractable exact or approximate optimization procedures. For example, consider the case of a discrete graphical model over a set of random variables. For the task of prediction, a key structural object is the "marginal polytope," a convex bounded set characterized by the underlying graph of the graphical model. Properties of this polytope, as well as its approximations, have been successfully used to develop efficient algorithms for inference. For the task of model selection, a key structural object is the discrete graph itself. Another problem structure is sparsity: While estimating a high-dimensional model for regression from a limited amount of data is typically an ill-posed problem, it becomes solvable if it is known that many of the coefficients are zero. Another problem structure, submodularity, a discrete analog of convexity, has been shown to arise in many machine learning problems, including structure learning of probabilistic models, variable selection and clustering. One of the primary goals of this workshop is to investigate how to leverage such structures.

The focus of this year´s workshop is on the interplay between discrete optimization and machine learning: How can we solve inference problems arising in machine learning using discrete optimization? How can one solve discrete optimization problems involving parameters that themselves are estimated from training data? How can we solve challenging sequential and adaptive discrete optimization problems where we have the opportunity to incorporate feedback (online and active learning with combinatorial decision spaces)? We will also explore applications of such approaches in computer vision, NLP, information retrieval etc.

Workshop homepage: http://discml.cc/

Related categories

Uploaded videos:

Keynote Talk

video-img
05:12

Introduction to Jack Edmonds´s talk

Jeff A. Bilmes

Jan 25, 2012

 · 

4633 Views

Introduction
video-img
01:27:21

Polymatroids and Submodularity

Jack Edmonds

Jan 25, 2012

 · 

8948 Views

Keynote

Invited Talks

video-img
49:07

Exploiting Problem Structure for Efficient Discrete Optimization

Pushmeet Kohli

Jan 25, 2012

 · 

5571 Views

Invited Talk
video-img
44:51

Learning with Submodular Functions: A Convex Optimization Perspective

Francis R. Bach

Jan 25, 2012

 · 

7616 Views

Invited Talk
video-img
50:27

Combinatorial prediction games

Nicolò Cesa-Bianchi

Jan 25, 2012

 · 

4352 Views

Invited Talk