Constraint Programming meets Machine Learning and Data Mining

Summary

Over the past two decades the fields of constraint programming, machine learning and data mining have become well-established research fields within computer science. They have contributed many foundational techniques that are routinely applied in real-life scientific and industrial applications. At the same time, awareness has grown that constraints can be very useful during mining and learning, and also that machine learning and data mining may allow one to automatically acquire constraints from data.

Both the data mining and machine learning communities have been interested in constraint-based mining and learning, that is, the use of constraints to formalize mining and learning problems. Examples are the specification of desirable properties of patterns to be mined, or clusters to be found. The task of the data mining or machine learning system is to generate all patterns or to compute the optimal clustering satisfying the constraints. A wide variety of constraints for local pattern mining, clustering and other machine learning problems exist and they have been implemented in an even wider range of specific data mining and machine learning systems for supporting such constraints. Some of these methods are based on mathematical programming techniques, such as linear programming or quadratic programming; other problems, however, cannot be modeled using these techniques. So far, the machine learning and data mining communities have been unable to develop general solvers that are applicable to a wide range of machine learning and data mining problems.

On the other hand, the artificial intelligence community has studied several types of constraint-satisfaction solvers. The most general systems are now gathered in the area of constraint programming. In constraint programming, the user specifies the model, that is, the set of constraints to be satisfied and constraint solvers generate solutions. Thus, the goals of constraint programming and constraint based mining and learning are similar; it is only that constraint programming targets any type of constraint satisfaction problem, whereas constraint-based mining and learning specifically targets data mining and machine learning applications. Therefore, it is surprising that despite the similarities between these two endeauvours, the two fields have evolved independently of one another, and also, that -- with a few recent exceptions -- constraint programming tools and techniques are not yet applied to data mining and machine learning, and, vice versa, that problems and challenges from data mining and machine learning have not yet been taken up by the constraint programming community. Exploring the possibilities for exploiting constraint programming in data mining and machine learning was one goal of this seminar.

The second goal was to study the use of machine learning and data mining in constraint programming. Practitioners of constraint programming have to formulate explicitly the constraints that underly their application. This is often a difficult task. Even when the right constraints are known, it can be challenging to formalize them in such a way that the constraint programming system can use them efficiently. This raises the question as to whether it is possible to (semi)- automatically learn such constraints or their formulations from data and experience. Again, some initial results in this direction exist, but we are away from a complete understanding of the potential of this approach.

In this seminar, we aimed at bridging the gap between these two fields by investigating, on the one hand, how standard constraint-programming techniques can be used in data mining and machine learning, and on the other hand, how machine learning and data mining can contribute to constraint programming. Therefore, this workshop brought together researchers in the areas of constraint programming, machine learning and data mining to discuss these issues, to identify interesting opportunities and challenges for research, and to consolidate and strengthen a promising line of research.