Combinatorial optimization in machine learning using constraint programming

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

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.