Grant: Discovery Grants Program - Individual
University of Waterloo
$23,000.00
Combinatorial optimization in machine learning using constraint programming
EF 2019-20
Résumé
Several important tasks in machine learning can be formulated as combinatorial optimization problems. For example, learning the structure of a Bayesian network from data can be formulated as a combinatorial optimization problem, where a score is defined that measures how well a candidate structure is supported by the observed data and the task is to find the structure with the lowest score. As a second example, learning a decision tree from labeled data can be formulated as a combinatorial optimization problem, where the aim is to find the decision tree that best predicts the data subject to regularization constraints. Both of these problems are NP-Hard in general to solve optimally but are also NP-Hard to solve approximately to within a reasonable factor. Thus, advanced search techniques are needed. This research proposal is an investigation into formulating and improving constraint programming and other advanced constraint-based search approaches for solving combinatorial optimization problems that arise in machine learning.******In a constraint programming approach, one models a problem by specifying constraints on acceptable solutions and search is then used to find a solution that satisfies the constraints and optimizes a cost function. An important feature of constraint programming is that one can first focus on a declarative constraint model and then develop an efficient algorithm for that model, either a complete and optimal algorithm based on backtracking search or an incomplete and approximate algorithm based on local search. In general, the research will be application-driven and will address practical, important problems. The research will be guided by the two important applications alluded to above: learning the structure of a Bayesian network from data and learning a decision tree from data subject to regularization constraints. The scientific approach will include: developing improved constraint models, improving the upper and lower bounds used during the search, investigating alternative search spaces, investigating the incorporation of prior domain knowledge in the form of constraints, methods for model averaging by generating the k-best models, extending the methods to other directed acyclic probabilistic graphical models such as sigmoid belief networks, and extending the methods to other decision tree models such as multi-variate decision trees.******The primary goals of the research projects are to develop faster algorithms for finding solutions, algorithms that find optimal or higher quality solutions, and algorithms that are more widely applicable in practice. Any improvements to the underlying solving algorithms have the potential to improve many applications of these machine learning approaches. A secondary goal of this work is to further develop constraint programming techniques that have general applicability to similar optimization problems.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2017-04633
Name nom
VanBeek, Peter
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2017
Award amount
23000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2803
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Knowledge representation
Research subject fr
Répresentation des connaissances
Installment
inst:3 - 5
Partie
3
Nb partie
5
Application title
Combinatorial optimization in machine learning using constraint programming
Keyword
NSERC
Application summary
Several important tasks in machine learning can be formulated as combinatorial optimization problems. For example, learning the structure of a Bayesian network from data can be formulated as a combinatorial optimization problem, where a score is defined that measures how well a candidate structure is supported by the observed data and the task is to find the structure with the lowest score. As a second example, learning a decision tree from labeled data can be formulated as a combinatorial optimization problem, where the aim is to find the decision tree that best predicts the data subject to regularization constraints. Both of these problems are NP-Hard in general to solve optimally but are also NP-Hard to solve approximately to within a reasonable factor. Thus, advanced search techniques are needed. This research proposal is an investigation into formulating and improving constraint programming and other advanced constraint-based search approaches for solving combinatorial optimization problems that arise in machine learning.******In a constraint programming approach, one models a problem by specifying constraints on acceptable solutions and search is then used to find a solution that satisfies the constraints and optimizes a cost function. An important feature of constraint programming is that one can first focus on a declarative constraint model and then develop an efficient algorithm for that model, either a complete and optimal algorithm based on backtracking search or an incomplete and approximate algorithm based on local search. In general, the research will be application-driven and will address practical, important problems. The research will be guided by the two important applications alluded to above: learning the structure of a Bayesian network from data and learning a decision tree from data subject to regularization constraints. The scientific approach will include: developing improved constraint models, improving the upper and lower bounds used during the search, investigating alternative search spaces, investigating the incorporation of prior domain knowledge in the form of constraints, methods for model averaging by generating the k-best models, extending the methods to other directed acyclic probabilistic graphical models such as sigmoid belief networks, and extending the methods to other decision tree models such as multi-variate decision trees.******The primary goals of the research projects are to develop faster algorithms for finding solutions, algorithms that find optimal or higher quality solutions, and algorithms that are more widely applicable in practice. Any improvements to the underlying solving algorithms have the potential to improve many applications of these machine learning approaches. A secondary goal of this work is to further develop constraint programming techniques that have general applicability to similar optimization problems.