Combinatorial optimization in machine learning using constraint programming

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

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.