Author name cluster

Yahia Lebbah

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.

6 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

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 2002 Journal Article

Accelerating filtering techniques for numeric CSPs

Yahia Lebbah
Olivier Lhomme

Search algorithms for solving Numeric CSPs (Constraint Satisfaction Problems) make an extensive use of filtering techniques. In this paper 1 1 This paper is an extended version of [31]. we show how those filtering techniques can be accelerated by discovering and exploiting some regularities during the filtering process. Two kinds of regularities are discussed, cyclic phenomena in the propagation queue and numeric regularities of the domains of the variables. We also present in this paper an attempt to unify numeric CSPs solving methods from two distinct communities, that of CSP in artificial intelligence, and that of interval analysis.

Details DOI

AAAI Conference 1998 Conference Paper

Acceleration Methods for Numeric CSPs

Yahia Lebbah

This paper introduces a newwayof accelerating the convergenceof numericCSPfiltering algorithms, through the use of extrapolation methotis. Extrapolation methodsare used in numerical analysis to accelerate the convergence of real numbersequences. Wewill showhowto use them for solving numericcsPs, leading to drastic improvement in efficiency.

PDF Details