Combinatorial optimization in machine learning using constraint programming

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

• 批准号: RGPIN-2017-04633
• 负责人: vanBeek, Peter
• 金额: $ 1.68万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635081
• 关键词: 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.

机器学习中的几个重要任务可以用公式表示为组合优化问题。例如，从数据中学习贝叶斯网络的结构可以被公式化为组合优化问题，其中定义了一个分数，该分数测量候选结构被观察到的数据支持的程度，并且任务是找到具有最低分数的结构。作为第二个示例，从标记数据学习决策树可以被公式化为组合优化问题，其中目标是找到最好地预测服从正则化约束的数据的决策树。这两个问题一般都是NP-难最佳解决，但也是NP-难近似解决一个合理的因素。因此，需要先进的搜索技术。这项研究计划是对制定和改进约束编程和其他先进的基于约束的搜索方法来解决机器学习中出现的组合优化问题的研究。