Combinatorial optimization in machine learning using constraint programming

使用约束规划的机器学习组合优化

• 批准号: RGPIN-2017-04633
• 负责人: VanBeek, Peter
• 金额: $ 1.68万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=679179
• 关键词: Combinatorial; optimization; machine; learning; using

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.

机器学习中的几个重要任务可以表述为组合优化问题。例如，从数据中学习贝叶斯网络的结构可以表述为一个组合优化问题，其中定义了一个分数，衡量观察到的数据对候选结构的支持程度，任务是找到得分最低的结构。作为第二个例子，从标记数据中学习决策树可以被表述为组合优化问题，其目的是找到最能预测受正则化约束的数据的决策树。这两个问题一般来说都是NP-Hard，无法最优地解决，但在一个合理的因素范围内近似地解决也是NP-Hard。因此，需要先进的搜索技术。本研究计划是对制定和改进约束规划和其他先进的基于约束的搜索方法进行调查，以解决机器学习中出现的组合优化问题。******在约束编程方法中，通过在可接受的解决方案上指定约束来对问题进行建模，然后使用搜索来找到满足约束并优化成本函数的解决方案。约束规划的一个重要特征是，人们可以首先关注声明性约束模型，然后为该模型开发一种有效的算法，要么是基于回溯搜索的完整和最优算法，要么是基于局部搜索的不完整和近似算法。总的来说，研究将是应用驱动的，将解决实际的，重要的问题。研究将以上面提到的两个重要应用为指导：从数据中学习贝叶斯网络的结构和从受正则化约束的数据中学习决策树。科学的方法将包括：开发改进的约束模型，改进搜索过程中使用的上界和下界，研究替代搜索空间，研究以约束形式合并先验领域知识，通过生成k-best模型进行模型平均的方法，将该方法扩展到其他有向无环概率图模型（如s型信念网络），并将该方法扩展到其他决策树模型（如多变量决策树）。******研究项目的主要目标是开发更快的算法来寻找解决方案，找到最优或更高质量的解决方案的算法，以及在实践中更广泛应用的算法。对底层求解算法的任何改进都有可能改善这些机器学习方法的许多应用。这项工作的第二个目标是进一步发展约束规划技术，这种技术对类似的优化问题具有普遍的适用性。