Abstract | Keywords | Export | Availability | Bookmark

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

This thesis presents HASSLE-GEN, a novel genetic algorithm aimed at learning weighted partial MAX-SAT models from labeled contextual examples. This problem involves jointly learning Boolean hard and soft constraints—as well as appropriate weights for the latter—from known solutions and non-solutions. The inclusion of contexts in the example set allows for learning from situational information. For instance, an example that is labeled as a solution and that comes with a particular context is possibly not a solution outside of that context. In this work, several blind and heuristic genetic operators are developed and empirically compared. The final algorithm is equipped with heuristic operators, as they are shown to realize superior performance. The algorithm also employs the deterministic crowding scheme, allowing it to learn high-quality models while maintaining a diverse population, which in turn results in better overall performance. In the experimental evaluation, HASSLE-GEN is shown to outperform the best existing approach, HASSLE-SLS, in various ways. Firstly, the novel method is able to learn high-quality models much faster than its competitor. It also learns good models more consistently (over different runs) than the existing method. Finally, it is able to simultaneously learn several distinct-looking high-quality models. This allows the user to select the model that fits best to their potential needs and preferences that are not captured in the set of examples. A second contribution made in this thesis is the development of a novel MAX-SAT model evaluation procedure. By making use of knowledge compilation techniques, a considerable speed-up in model evaluation is realized for small to medium-sized models. This is a significant result, as the evaluation of candidate models was a large bottleneck in the existing learning approach. The knowledge-compilation-based evaluation procedure can be employed regardless of what search algorithm is used. It has been implemented for both the existing and the new search approach.