Author name cluster

Behrouz Babaki

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.

7 papers

2 author rows

AIJ Journal 2022 Journal Article

Exact stochastic constraint optimisation with applications in network analysis

Anna L.D. Latour
Behrouz Babaki
Daniël Fokkinga
Marie Anastacio
Holger H. Hoos
Siegfried Nijssen

We present an extensive study of methods for exactly solving stochastic constraint (optimisation) problems (SCPs) in network analysis. These problems are prevalent in science, governance and industry. The first method we study is generic and decomposes stochastic constraints into a multitude of smaller local constraints that are solved using a constraint programming (CP) or mixed-integer programming (MIP) solver. However, many SCPs are formulated on probability distributions with a monotonic property, meaning that adding a positive decision to a partial solution to the problem cannot cause a decrease in solution quality. The second method is specifically designed for solving global stochastic constraints on monotonic probability distributions (SCMDs) in CP. Both methods use knowledge compilation to obtain a decision diagram encoding of the relevant probability distributions, where we focus on ordered binary decision diagrams (OBDDs). We discuss theoretical advantages and disadvantages of these methods and evaluate them experimentally. We observed that global approaches to solving SCMDs outperform decomposition approaches from CP, and perform complementarily to MIP-based decomposition approaches, while scaling much more favourably with instance size. Both methods have many alternative design choices, as both knowledge compilation and constraint solvers are used in a single pipeline. To identify which configurations work best, we apply programming by optimisation. Specifically, we show how an automated algorithm configurator can be used to find optimised configurations of our pipeline. After configuration, our global SCMD solving pipeline outperforms its closest competitor (a MIP-based decomposition pipeline) on all test sets we considered by up to two orders of magnitude in terms of PAR10 scores.

Details DOI

AAAI Conference 2021 Conference Paper

Individual Fairness in Kidney Exchange Programs

Golnoosh Farnadi
William St-Arnaud
Behrouz Babaki
Margarida Carvalho

Kidney transplant is the preferred method of treatment for patients suffering from kidney failure. However, not all patients can find a donor that matches their physiological characteristics. Kidney exchange programs (KEPs) seek to match such incompatible patient-donor pairs together, usually with the main objective of maximizing the total number of transplants. Since selecting one optimal solution translates to a decision on who receives a transplant, it has a major effect on the lives of patients. The current practice in selecting an optimal solution does not necessarily ensure fairness in the selection process. In this paper, the existence of multiple optimal plans for a KEP is explored as a mean to achieve individual fairness. We propose the use of randomized policies for selecting an optimal solution in which patients’ equal opportunity to receive a transplant is promoted. Our approach gives rise to the problem of enumerating all optimal solutions, which we tackle using a hybrid of constraint programming and linear programming. The advantages of our proposed method over the common practice of using the optimal solution obtained by a solver are stressed through computational experiments. Our methodology enables decision makers to fully control KEP outcomes, overcoming any potential bias or vulnerability intrinsic to a deterministic solver.

PDF Details

AAAI Conference 2020 Conference Paper

Learning Fair Naive Bayes Classifiers by Discovering and Eliminating Discrimination Patterns

YooJung Choi
Golnoosh Farnadi
Behrouz Babaki
Guy Van den Broeck

As machine learning is increasingly used to make real-world decisions, recent research efforts aim to deﬁne and ensure fairness in algorithmic decision making. Existing methods often assume a ﬁxed set of observable features to deﬁne individuals, but lack a discussion of certain features not being observed at test time. In this paper, we study fairness of naive Bayes classiﬁers, which allow partial observations. In particular, we introduce the notion of a discrimination pattern, which refers to an individual receiving different classiﬁcations depending on whether some sensitive attributes were observed. Then a model is considered fair if it has no such pattern. We propose an algorithm to discover and mine for discrimination patterns in a naive Bayes classiﬁer, and show how to learn maximumlikelihood parameters subject to these fairness constraints. Our approach iteratively discovers and eliminates discrimination patterns until a fair model is learned. An empirical evaluation on three real-world datasets demonstrates that we can remove exponentially many discrimination patterns by only adding a small fraction of them as constraints.

PDF Details

SoCS Conference 2020 Conference Paper

Solving Classical AI Planning Problems Using Planning-Independent CP Modeling and Search

Behrouz Babaki
Gilles Pesant
Claude-Guy Quimper

The combinatorial problems that constraint programming typically solves belong to the class of NP-hard problems. The AI planning community focuses on even harder problems: for example, classical planning is PSPACE-hard. A natural and well-known constraint programming approach to classical planning solves a succession of fixed plan-length problems, but with limited success. We revisit this approach in light of recent progress on general-purpose branching heuristics. We conduct an empirical comparison of our proposal against state-of-the-art planners.

Details

AAAI Conference 2019 Conference Paper

Lifted Hinge-Loss Markov Random Fields

Sriram Srinivasan
Behrouz Babaki
Golnoosh Farnadi
Lise Getoor

Statistical relational learning models are powerful tools that combine ideas from first-order logic with probabilistic graphical models to represent complex dependencies. Despite their success in encoding large problems with a compact set of weighted rules, performing inference over these models is often challenging. In this paper, we show how to effectively combine two powerful ideas for scaling inference for large graphical models. The first idea, lifted inference, is a wellstudied approach to speeding up inference in graphical models by exploiting symmetries in the underlying problem. The second idea is to frame Maximum a posteriori (MAP) inference as a convex optimization problem and use alternating direction method of multipliers (ADMM) to solve the problem in parallel. A well-studied relaxation to the combinatorial optimization problem defined for logical Markov random fields gives rise to a hinge-loss Markov random field (HL- MRF) for which MAP inference is a convex optimization problem. We show how the formalism introduced for coloring weighted bipartite graphs using a color refinement algorithm can be integrated with the ADMM optimization technique to take advantage of the sparse dependency structures of HL- MRFs. Our proposed approach, lifted hinge-loss Markov random fields (LHL-MRFs), preserves the structure of the original problem after lifting and solves lifted inference as distributed convex optimization with ADMM. In our empirical evaluation on real-world problems, we observe up to a three times speed up in inference over HL-MRFs.

PDF Details

IJCAI Conference 2019 Conference Paper

Stochastic Constraint Propagation for Mining Probabilistic Networks

Anna Louise D. Latour
Behrouz Babaki
Siegfried Nijssen

A number of data mining problems on probabilistic networks can be modeled as Stochastic Constraint Optimization and Satisfaction Problems, i. e. , problems that involve objectives or constraints with a stochastic component. Earlier methods for solving these problems used Ordered Binary Decision Diagrams (OBDDs) to represent constraints on probability distributions, which were decomposed into sets of smaller constraints and solved by Constraint Programming (CP) or Mixed Integer Programming (MIP) solvers. For the specific case of monotonic distributions, we propose an alternative method: a new propagator for a global OBDD-based constraint. We show that this propagator is (sub-)linear in the size of the OBDD, and maintains domain consistency. We experimentally evaluate the effectiveness of this global constraint in comparison to existing decomposition-based approaches, and show how this propagator can be used in combination with another data mining specific constraint present in CP systems. As test cases we use problems from the data mining literature.

PDF Details

IJCAI Conference 2017 Conference Paper

Stochastic Constraint Programming with And-Or Branch-and-Bound

Behrouz Babaki
Tias Guns
Luc De Raedt

Complex multi-stage decision making problems often involve uncertainty, for example, regarding demand or processing times. Stochastic constraint programming was proposed as a way to formulate and solve such decision problems, involving arbitrary constraints over both decision and random variables. What stochastic constraint programming still lacks is support for the use of factorized probabilistic models that are popular in the graphical model community. We show how a state-of-the-art probabilistic inference engine can be integrated into standard constraint solvers. The resulting approach searches over the And-Or search tree directly, and we investigate tight bounds on the expected utility objective. This significantly improves search efficiency and outperforms scenario-based methods that ground out the possible worlds.

PDF Details