Author name cluster

Batya Kenig

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

JAIR Journal 2025 Journal Article

Approximate Implication for Probabilistic Graphical Models

Batya Kenig

The graphical structure of Probabilistic Graphical Models (PGMs) represents the conditional independence (CI) relations that hold in the modeled distribution. Every separator in the graph represents a conditional independence relation in the distribution, making them the vehicle through which new conditional independence relations are inferred and verified. The notion of separation in graphs depends on whether the graph is directed (i.e., a Bayesian Network ), or undirected (i.e., a Markov Network ). The premise of all current systems-of-inference for deriving CIs in PGMs, is that the set of CIs used for the construction of the PGM hold exactly. In practice, algorithms for extracting the structure of PGMs from data discover approximate CIs that do not hold exactly in the distribution. In this paper, we ask how the error in this set propagates to the inferred CIs read off the graphical structure. More precisely, what guarantee can we provide on the inferred CI when the set of CIs that entailed it hold only approximately? It has recently been shown that in the general case, no such guarantee can be provided. In this work, we prove new negative and positive results concerning this problem. We prove that separators in undirected PGMs do not necessarily represent approximate CIs. In other words, no guarantee can be provided for CIs inferred from the structure of undirected graphs. We prove that such a guarantee exists for the set of CIs inferred in directed graphical models, making the d-separation algorithm a sound and complete system for inferring approximate CIs. We also establish improved approximation guarantees for independence relations derived from marginal and saturated CIs.

PDF Details DOI

UAI Conference 2025 Conference Paper

Enumerating Optimal Cost-Constrained Adjustment Sets

Batya Kenig

Estimating causal effects from observational data is a key problem in causal inference, often addressed through covariate adjustment sets that enable unbiased estimation of interventional means. This paper tackles the challenge of finding optimal covariate adjustment sets under budget constraints, a practical concern in many applications. We present algorithms for enumerating valid and minimal adjustment sets up to a specified cost, ordered by their proximity to outcome variables, which coincides with estimator variance. Our approach builds on existing graphical criteria and extends them to accommodate budgetary considerations, providing a useful tool for addressing resource limitations.

Details

UAI Conference 2021 Conference Paper

Approximate implication with d-separation

Batya Kenig

The graphical structure of Probabilistic Graphical Models (PGMs) encodes the conditional independence (CI) relations that hold in the modeled distribution. Graph algorithms, such as d-separation, use this structure to infer additional conditional independencies, and to query whether a specific CI holds in the distribution. The premise of all current systems-of-inference for deriving CIs in PGMs, is that the set of CIs used for the construction of the PGM hold exactly. In practice, algorithms for extracting the structure of PGMs from data, discover approximate CIs that do not hold exactly in the distribution. In this paper, we ask how the error in this set propagates to the inferred CIs read off the graphical structure. More precisely, what guarantee can we provide on the inferred CI when the set of CIs that entailed it hold only approximately? It has recently been shown that in the general case, no such guarantee can be provided. We prove that such a guarantee exists for the set of CIs inferred in directed graphical models, making the d-separation algorithm a sound and complete system for inferring approximate CIs. We also prove an approximation guarantee for independence relations derived from marginal CIs.

Details

AAAI Conference 2019 Conference Paper

Approximate Inference of Outcomes in Probabilistic Elections

Batya Kenig
Benny Kimelfeld

We study the complexity of estimating the probability of an outcome in an election over probabilistic votes. The focus is on voting rules expressed as positional scoring rules, and two models of probabilistic voters: the uniform distribution over the completions of a partial voting profile (consisting of a partial ordering of the candidates by each voter), and the Repeated Insertion Model (RIM) over the candidates, including the special case of the Mallows distribution. Past research has established that, while exact inference of the probability of winning is computationally hard (#P-hard), an additive polynomial-time approximation (additive FPRAS) is attained by sampling and averaging. There is often, though, a need for multiplicative approximation guarantees that are crucial for important measures such as conditional probabilities. Unfortunately, a multiplicative approximation of the probability of winning cannot be efficient (under conventional complexity assumptions) since it is already NP-complete to determine whether this probability is nonzero. Contrastingly, we devise multiplicative polynomial-time approximations (multiplicative FPRAS) for the probability of the complement event, namely, losing the election.

PDF Details

AAMAS Conference 2019 Conference Paper

The Complexity of the Possible Winner Problem with Partitioned Preferences

Batya Kenig

The Possible-Winner problem asks, given an election where the voters’ preferences over the set of candidates is partially specified, whether a distinguished candidate can become a winner. In this work, we consider the computational complexity of the Possible-Winner problem under the assumption that the voter preferences are partitioned. That is, we assume that every voter provides a complete order over sets of incomparable candidates (e. g. , candidates are ranked by their level of education). We consider elections with partitioned profiles over positional scoring rules. Our first result is a polynomial time algorithm for voting rules with two distinct values, which include the common k-approval voting rule. We then go on to prove NP-hardness for the class of voting rules that produce scoring vectors with at least four distinct values, and a large class of voting rules that produce scoring vectors with three distinct values.

PDF

AAAI Conference 2018 Conference Paper

Probabilistic Inference Over Repeated Insertion Models

Batya Kenig
Lovro Ilijasić
Haoyue Ping
Benny Kimelfeld
Julia Stoyanovich

Distributions over rankings are used to model user preferences in various settings including political elections and electronic commerce. The Repeated Insertion Model (RIM) gives rise to various known probability distributions over rankings, in particular to the popular Mallows model. However, probabilistic inference on RIM is computationally challenging, and provably intractable in the general case. In this paper we propose an algorithm for computing the marginal probability of an arbitrary partially ordered set over RIM. We analyze the complexity of the algorithm in terms of properties of the model and the partial order, captured by a novel measure termed the “cover width”. We also conduct an experimental study of the algorithm over serial and parallelized implementations. Building upon the relationship between inference with rank distributions and counting linear extensions, we investigate the inference problem when restricted to partial orders that lend themselves to efﬁcient counting of their linear extensions.

PDF Details