Author name cluster

Samir Loudni

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

IJCAI Conference 2022 Conference Paper

Threshold-free Pattern Mining Meets Multi-Objective Optimization: Application to Association Rules

Charles Vernerey
Samir Loudni
Noureddine Aribi
Yahia Lebbah

Constraint-based pattern mining is at the core of numerous data mining tasks. Unfortunately, thresholds which are involved in these constraints cannot be easily chosen. This paper investigates a Multi-objective Optimization approach where several (often conflicting) functions need to be optimized at the same time. We introduce a new model for efficiently mining Pareto optimal patterns with constraint programming. Our model exploits condensed pattern representations to reduce the mining effort. To this end, we design a new global constraint for ensuring the closeness of patterns over a set of measures. We show how our approach can be applied to derive high-quality non redundant association rules without the use of thresholds whose added-value is studied on both UCI datasets and case study related to the analysis of genes expression data integrating multiple external genes annotations.

PDF Details DOI

AIJ Journal 2020 Journal Article

Variable neighborhood search for graphical model energy minimization

Abdelkader Ouali
David Allouche
Simon de Givry
Samir Loudni
Yahia Lebbah
Lakhdar Loukil
Patrice Boizumault

Graphical models factorize a global probability distribution/energy function as the product/ sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum a posteriori probability/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i. e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS that uses (partial) tree search inside its local neighborhood exploration. The proposed approach performs several neighborhood explorations of increasing search complexity, by controlling two parameters, the discrepancy limit and the neighborhood size. Thus, optimality of the obtained solutions can be proven when the neighborhood size is maximal and with unbounded tree search. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. A solver is available at https: //github. com/toulbar2/toulbar2.

Details DOI

UAI Conference 2017 Conference Paper

Iterative Decomposition Guided Variable Neighborhood Search for Graphical Model Energy Minimization

Abdelkader Ouali
David Allouche
Simon de Givry
Samir Loudni
Yahia Lebbah
Lakhdar Loukil

range of areas such as image analysis, speech recognition, bioinformatics, and ecology. Graphical models factorize a global probability distribution/energy function as the product/sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum a posteriori probability/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i. e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS which uses (partial) tree search inside its local neighborhood exploration. The resulting hybrid method offers a good compromise between completeness and anytime behavior than existing tree search methods while still being competitive for proving optimality. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. Solver at www. inra. fr/mia/T/toulbar2 v1. 0. We focus on models with discrete variables like Markov Random Field and Bayesian Network. Our goal is to find a global assignment of all the variables with maximum a posteriori probability. This optimization task defines an NP-complete problem (Shimony, 1994). Solving methods can be categorized in two groups: exact and local search methods. Exact methods rely on tree search, variable elimination, linear programming, or a combination of them (Marinescu and Dechter, 2009; Otten and Dechter, 2012; Allouche et al. , 2015). Graph-cut and message-passing algorithms like loopy belief propagation and variational approaches (Kolmogorov, 2006; Wainwright and Jordan, 2008; Sontag et al. , 2008; 2012; Wang and Koller, 2013) are exact only in some particular cases (e. g. , Potts model or tree structure). Local search methods are stochastic algorithms like Gibbs sampling, Guided Local Search (Park, 2002; Hutter et al. , 2005), and Stochastic Greedy Search (Mengshoel et al. , 2011). Some of them have theoretical asymptotic proof of convergence, i. e. , the optimal solution is guaranteed to be found if infinite time is available. In practice, they may exhibit a better anytime behavior than exact methods on large and difficult problems (Marinescu et al. , 2003; Hutter et al. , 2005; Mengshoel et al. , 2011), i. e. , they produce better solutions in less time.

Details

AIJ Journal 2017 Journal Article

Skypattern mining: From pattern condensed representations to dynamic constraint satisfaction problems

Willy Ugarte
Patrice Boizumault
Bruno Crémilleux
Alban Lepailleur
Samir Loudni
Marc Plantevit
Chedy Raïssi
Arnaud Soulet

Data mining is the study of how to extract information from data and express it as useful knowledge. One of its most important subfields, pattern mining, involves searching and enumerating interesting patterns in data. Various aspects of pattern mining are studied in the theory of computation and statistics. In the last decade, the pattern mining community has witnessed a sharp shift from efficiency-based approaches to methods which can extract more meaningful patterns. Recently, new methods adapting results from studies of economic efficiency and multi-criteria decision analyses such as Pareto efficiency, or skylines, have been studied. Within pattern mining, this novel line of research allows the easy expression of preferences according to a dominance relation. This approach is useful from a user-preference point of view and tends to promote the use of pattern mining algorithms for non-experts. We present a significant extension of our previous work [1, 2] on the discovery of skyline patterns (or “skypatterns”) based on the theoretical relationships with condensed representations of patterns. We show how these relationships facilitate the computation of skypatterns and we exploit them to propose a flexible and efficient approach to mine skypatterns using a dynamic constraint satisfaction problems (CSP) framework. We present a unified methodology of our different approaches towards the same goal. This work is supported by an extensive experimental study allowing us to illustrate the strengths and weaknesses of each approach.

Details DOI

IJCAI Conference 2016 Conference Paper

Efficiently Finding Conceptual Clustering Models with Integer Linear Programming

Abdelkader Ouali
Samir Loudni
Yahia Lebbah
Patrice Boizumault
Albrecht Zimmermann
Lakhdar Loukil

Conceptual clustering combines two long-standing machine learning tasks: the unsupervised grouping of similar instances and their description by symbolic concepts. In this paper, we decouple the problems of finding descriptions and forming clusters by first mining formal concepts (i. e. closed itemsets), and searching for the best k clusters that can be described with those itemsets. Most existing approaches performing the two steps separately are of a heuristic nature and produce results of varying quality. Instead, we address the problem of finding an optimal constrained conceptual clustering by using integer linear programming techniques. Most other generic approaches for this problem tend to have problems scaling. Our approach takes advantageous of both techniques, the general framework of integer linear programming, and high-speed specialized approaches of data mining. Experiments performed on UCI datasets show that our approach efficiently finds clusterings of consistently high quality.

PDF Details

AIJ Journal 2016 Journal Article

Tractability-preserving transformations of global cost functions

David Allouche
Christian Bessiere
Patrice Boizumault
Simon de Givry
Patricia Gutierrez
Jimmy H.M. Lee
Ka Lun Leung
Samir Loudni

Graphical model processing is a central problem in artificial intelligence. The optimization of the combined cost of a network of local cost functions federates a variety of famous problems including CSP, SAT and Max-SAT but also optimization in stochastic variants such as Markov Random Fields and Bayesian networks. Exact solving methods for these problems typically include branch and bound and local inference-based bounds. In this paper we are interested in understanding when and how dynamic programming based optimization can be used to efficiently enforce soft local consistencies on Global Cost Functions, defined as parameterized families of cost functions of unbounded arity. Enforcing local consistencies in cost function networks is performed by applying so-called Equivalence Preserving Transformations (EPTs) to the cost functions. These EPTs may transform global cost functions and make them intractable to optimize. We identify as tractable projection-safe those global cost functions whose optimization is and remains tractable after applying the EPTs used for enforcing arc consistency. We also provide new classes of cost functions that are tractable projection-safe thanks to dynamic programming. We show that dynamic programming can either be directly used inside filtering algorithms, defining polynomially DAG-filterable cost functions, or emulated by arc consistency filtering on a Berge-acyclic network of bounded-arity cost functions, defining Berge-acyclic network-decomposable cost functions. We give examples of such cost functions and we provide a systematic way to define decompositions from existing decomposable global constraints. These two approaches to enforcing consistency in global cost functions are then embedded in a solver for extensive experiments that confirm the feasibility and efficiency of our proposal.

Details DOI

ECAI Conference 2014 Conference Paper

Computing Skypattern Cubes

Willy Ugarte
Patrice Boizumault
Samir Loudni
Bruno Crémilleux

We introduce skypattern cubes and propose an efficient bottom-up approach to compute them. Our approach relies on derivation rules collecting skypatterns of a parent node from its child nodes without any dominance test. Non-derivable skypatterns are computed on the fly thanks to Dynamic CSP. The bottom-up principle enables to provide a concise representation of the cube based on skypattern equivalence classes without any supplementary effort. Experiments show the effectiveness of our proposal.

Details

AAAI Conference 2012 Conference Paper

Filtering Decomposable Global Cost Functions

David Allouche
Christian Bessiere
Patrice Boizumault
Simon de Givry
Patricia Gutierrez
Samir Loudni
Jean-Philippe Métivier
Thomas Schiex

As (Lee and Leung 2012) have shown, weighted constraint satisfaction problems can benefit from the introduction of global cost functions, leading to a new Cost Function Programming paradigm. In this paper, we explore the possibility of decomposing global cost functions in such a way that enforcing soft local consistencies on the decomposition achieves the same level of consistency on the original global cost function. We give conditions under which directional and virtual arc consistency offer such guarantees. We conclude by experiments on decomposable cost functions showing that decompositions may be very useful to easily integrate efficient global cost functions in solvers.

PDF Details

EAAI Journal 2010 Journal Article

Advanced generic neighborhood heuristics for VNS

Samir Loudni
Patrice Boizumault
Nicolas Levasseur

Weighted CSP (Constraint Satisfaction Problems) are used to model and to solve constraint optimization problems. As most WCSP are solved by local search methods that use large neighborhoods, selecting the neighborhood to explore is crucial. However, designing efficient neighborhoods is difficult and problem dependent. The very few generic heuristics defined for CSP, as ConflictVar or H-PGLNS, are not well suited for WCSP. In this paper, we propose new generic neighborhood heuristics dedicated to WCSP. Our heuristics take advantage of both conflicted variables and the topology of the constraints graph. We define the concept of freedom degree of a variable to make a compromise between these two criteria, and introduce a diversification criterion by choosing non-conflicted variables connected to conflicted ones. Then we extend, in a systematic way, each proposed heuristic in order to take into account violation costs of constraints. Experiments have been performed on real life instances (RLFAP) as well as random instances (GRAPH and Kbtree) using VNS/LDS+CP (a particular instance of VNS we developed). Experiments show that our generic heuristics clearly outperform ConflictVar and H-PGLNS. Among all topological heuristics we proposed, ConflictVar-MaxDeg appears to be the best one.

Details DOI

IJCAI Conference 2003 Conference Paper

Solving Constraint Optimization Problems in Anytime Contexts

Samir Loudni
Patrice Boizumault

This paper presents a new hybrid method for solving constraint optimization problems in anytime contexts. Discrete optimization problems are modelled as Valued CSP. Our method (VNS/LDS+CP) combines a Variable Neighborhood Search and Limited Discrepancy Search with Constraint Propagation to efficiently guide the search. Experiments on the CELAR benchmarks demonstrate significant improvements over other competing methods. VNS/LDS+CP has been successfully applied to solve a real-life anytime resource allocation problem in computer networks.

PDF