Many real life problems come from uncertain and dynamic environments, where
the original problem may change during its execution. Thus, the solution
found for the problem may become invalid. For this reason, the search of
robust solutions for Constraint Satisfaction Problems (CSPs) has become an
important issue in the field of constraint programming. In some cases, there
exists knowledge about the uncertain and dynamic environment. However most
of our work is focused in problems where this information is unknown. In
addition, we consider CSPs with ordered domains. Given this context, even if
this does not cover all the possible changes, it is reasonable to assume
that the original bounds of the solution space can undergo changes. For this
reason, when the information about the possible future changes is unknown,
the main objective is to find the solution located as far as possible from
the bounds of the solution space. To this end, we propose several modeling
techniques and search algorithm. Furtheremore, we extend the concepts of
stability and robustness in this framework.
Declarative Pattern Mining using Constraint Programming
Declarative Pattern Mining using Constraint Programming
It involves the use of constraint programming to solve data mining
problems, more specifically the standard itemset mining problem and its
many 'constraint-based' variants.
The big benefit of CP in this context is that it is general and can
solve many itemset mining related problems in a single framework. This
flexibility was previously unknown to the itemset mining field, as
most of the work focused on creating highly efficient (imperative)
algorithms.
Of course generality often comes at the cost of effiency, but I will
demonstrate how the advanced propagation of CP can (and has) improved
on existing state-of-the-art mining algorithms.
I will also offer a glimpse of what declarative constraint languages can
offer to data mining.
The openness and anonymity of the Internet environment create many hazards for e-commerce. For collaborative recommender systems, it raises the possibility of that attackers will seek to bias the output recommendations through manipulation of the public inputs that the system permits. Fighting such manipulation is a constant battle for the owners and maintainers of such systems. In this talk, I will describe the known vulnerabilities of collaborative algorithms and examine a range of possible attack types that could be deployed against them. With these vulnerabilities in mind, I will discuss possible responses, including the deployment of alternate recommendation algorithms and the use of supervised and unsupervised techniques to detect attacks. Building on this research, I will examine what it might mean to build a robust collaborative recommender and consider the implications for other machine learning techniques deployed in public on-line environments.
The last 15 years have seen a steady development of methods and tools for the analysis of evolutionary algorithms. These algorithms are just one example for randomized search heuristics, a broad class of
algorithms applied for many different kind of search problems, among those optimization.
Considering evolutionary algorithms, an overview of methods and tools for obtaining rigorously proven results on the expected optimization time, the most important notion of efficiency in the context of
optimization, is presented.
Building on these methods we consider a concrete example for the transfer of these methods to another kind of randomized search heuristics, namely artificial immune systems.
Concentrating on pure static aging as one of many pertinent concepts we prove that artificial immune systems are very sensitive to the maximal age that is set in pure static aging. In this analysis we consider a new analytical tool that has the potential to prove itself
useful beyond this single concrete application.
When dealing with real-world optimization problems, we frequently
face complicated side constraints which are hard to formulate in
integer programming and constraint programming. To facilitate the
modeling process, we introduce the context-free grammar constraint
that requires that an assignment of values to an ordered set of
variables must form a word in a given context-free language. For
this constraint, we devise an efficient, complete, and incremental
filtering algorithm that has the same asymptotic complexity as the
Cocke-Younger-Kasami algorithm for parsing context-free languages.
Moreover, we show how the constraint can be linearized automatically
whereby the resulting polytope has only integer extreme points.
Joint work with Serdar Kadioglu, Louis-Martin Rousseau,
Claude-Guy Quimper, and Gilles Pesant.
