Discrete Optimization in Machine Learning

Discrete Optimization in Machine Learning

9 Lectures · Dec 10, 2010

About

Solving optimization problems with ultimately discrete solutions is becoming increasingly important in machine learning: At the core of statistical machine learning is to infer conclusions from data, and when the variables underlying the data are discrete, both the tasks of inferring the model from data, as well as performing predictions using the estimated model are discrete optimization problems. Many of the resulting optimization problems are NPhard, and typically, as the problem size increases, standard off-the-shelf optimization procedures become intractable. 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 highdimensional 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. There are two major classes of approaches towards solving such discrete optimization problems machine learning: Combinatorial algorithms and continuous relaxations.

Workshop homepage: http://www.discml.cc/

Related categories

Uploaded videos:

video-img
34:20

Mixing sum-product and max-product type updates to tighten tree-reweighted upper...

Tamir Hazan

Jan 13, 2011

 · 

3953 Views

Invited Talk
video-img
49:39

Submodular Function Minimization

Satoru Iwata

Jan 13, 2011

 · 

9657 Views

Invited Talk
video-img
51:01

Multilinear relaxation: a tool for maximization of submodular functions

Jan Vondrak

Jan 13, 2011

 · 

4791 Views

Invited Talk
video-img
23:28

Online submodular minimization with combinatorial constraints

Stefanie Jegelka

Jan 13, 2011

 · 

6586 Views

Invited Talk
video-img
42:01

Energy Minimization with Label costs and Applications in Multi-Model Fitting

Yuri Boykov

Jan 13, 2011

 · 

8027 Views

Invited Talk
video-img
32:50

Dual decomposition for inference in natural language processing

Terry Koo

Jan 13, 2011

 · 

5664 Views

Invited Talk
video-img
34:05

Information Theoretic Model Validation by Approximate Optimization

Joachim M. Buhmann

Jan 05, 2011

 · 

4787 Views

Invited Talk
video-img
49:10

Taming Information Overload

Carlos Guestrin

Jan 13, 2011

 · 

3816 Views

Invited Talk
video-img
28:58

Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimiz...

Daniel Golovin

Jan 13, 2011

 · 

7677 Views

Invited Talk