Author name cluster

Radu Marinescu

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.

37 papers

1 author row

AAAI Conference 2026 System Paper

AutoTuneX: Interactive Automated Fine-Tuning for Large Language Models

Daniel Karl I. Weidele
Priyanshu Rai
Frederico Araujo
Teryl Taylor
Radu Marinescu

We present AutoTuneX, a system architecture design and implementation for users to interactively fine-tune large language models (LLMs) based on automated hyperparameter optimization particularly built around Bandit Limited Discrepancy Search. Next to a classical Graphical User Interface (GUI) our system features an agentic runtime to facilitate automated fine-tuning via chat.

PDF Details DOI

TMLR Journal 2025 Journal Article

AT4TS: Autotune for Time Series Foundation Models

Shivani Tomar
Seshu Tirupathi
Radu Marinescu
Elizabeth M. Daly
Ivana Dusparic

Foundation models have been successfully adapted to the task of time series forecasting due to their ability to capture long-range dependencies, as demonstrated in the field of Natural Language Processing (NLP). However, effectiveness of applying these pre-trained time series foundation models (TSFMs) in the target domain is limited due to the need for hyperparameter optimization to match the characteristics of the target domain. To address this limitation, we propose a novel algorithm AT4TS: Autotune for Time Series Foundation Models that aims to efficiently automate the process of selective fine-tuning of pre-trained TSFMs for a given target domain. Our approach helps remove the tedious task of accurately configuring the tunable hyperparameters required to selectively update parameters to enhance predictive performance on unseen out-of-domain target datasets. AT4TS has been validated through diverse pre-trained models like Chronos and Tiny Time Mixers (TTM), fine-tuning strategies like Low Rank Adaptation (LoRA) and custom fine-tuning and state-of-the-art hyperparameter optimization (HPO) methods. Extensive experimental results on real-world benchmark datasets demonstrate that AT4TS efficiently identifies the optimal configuration of tunable hyperparameters for autotuning TSFMs. We show improvements as high as 20.55% and 45.34% for one of the out-of-domain datasets compared to zero-shot pre-trained models for Chronos and TTM respectively.

ISIPTA Conference 2025 Conference Paper

Dealing with cycles in graph-based probabilistic models: the case of Logical Credal Networks

Fabio G. Cozman
Radu Marinescu
Junkyu Lee
Alexander Gray
Denis D. Mau\'a

We examine the consequences of directed cycles in graph-based representations of joint distributions, investigating the effect of cycles on Markov conditions and on Gibbs factorizations. We focus on Logical Credal Networks, a flexible and general formalism, showing that Koster’s theory of Directed-Undirected Mixed Graphs (DUMGs) leads to an interesting Gibbs factorization. We show that inferences with DUMGs lead to multilinear programs. We also study the failure of global Markov conditions in cyclic structural equation models, connecting that failure to probabilistic imprecision under interventions.

NeurIPS Conference 2024 Conference Paper

Abductive Reasoning in Logical Credal Networks

Radu Marinescu
Junkyu Lee
Debarun Bhattacharjya
Fabio Cozman
Alexander Gray

Logical Credal Networks or LCNs were recently introduced as a powerful probabilistic logic framework for representing and reasoning with imprecise knowledge. Unlike many existing formalisms, LCNs have the ability to represent cycles and allow specifying marginal and conditional probability bounds on logic formulae which may be important in many realistic scenarios. Previous work on LCNs has focused exclusively on marginal inference, namely computing posterior lower and upper probability bounds on a query formula. In this paper, we explore abductive reasoning tasks such as solving MAP and Marginal MAP queries in LCNs given some evidence. We first formally define the MAP and Marginal MAP tasks for LCNs and subsequently show how to solve these tasks exactly using search-based approaches. We then propose several approximate schemes that allow us to scale MAP and Marginal MAP inference to larger problem instances. An extensive empirical evaluation demonstrates the effectiveness of our algorithms on both random LCN instances as well as LCNs derived from more realistic use-cases.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

WikiContradict: A Benchmark for Evaluating LLMs on Real-World Knowledge Conflicts from Wikipedia

Yufang Hou
Alessandra Pascale
Javier Carnerero-Cano
Tigran Tchrakian
Radu Marinescu
Elizabeth Daly
Inkit Padhi
Prasanna Sattigeri

Retrieval-augmented generation (RAG) has emerged as a promising solution to mitigate the limitations of large language models (LLMs), such as hallucinations and outdated information. However, it remains unclear how LLMs handle knowledge conflicts arising from different augmented retrieved passages, especially when these passages originate from the same source and have equal trustworthiness. In this work, we conduct a comprehensive evaluation of LLM-generated answers to questions that have varying answers based on contradictory passages from Wikipedia, a dataset widely regarded as a high-quality pre-training resource for most LLMs. Specifically, we introduce WikiContradict, a benchmark consisting of 253 high-quality, human-annotated instances designed to assess the performance of LLMs in providing a complete perspective on conflicts from the retrieved documents, rather than choosing one answer over another, when augmented with retrieved passages containing real-world knowledge conflicts. We benchmark a diverse range of both closed and open-source LLMs under different QA scenarios, including RAG with a single passage, and RAG with 2 contradictory passages. Through rigorous human evaluations on a subset of WikiContradict instances involving 5 LLMs and over 3, 500 judgements, we shed light on the behaviour and limitations of these models. For instance, when provided with two passages containing contradictory facts, all models struggle to generate answers that accurately reflect the conflicting nature of the context, especially for implicit conflicts requiring reasoning. Since human evaluation is costly, wealso introduce an automated model that estimates LLM performance using a strong open-source language model, achieving an F-score of 0. 8. Using this automated metric, we evaluate more than 1, 500 answers from seven LLMs across all WikiContradict instances.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

An Ensemble Approach for Automated Theorem Proving Based on Efficient Name Invariant Graph Neural Representations

Achille Fokoue
Ibrahim Abdelaziz
Maxwell Crouse
Shajith Ikbal
Akihiro Kishimoto
Guilherme Lima
Ndivhuwo Makondo
Radu Marinescu

Using reinforcement learning for automated theorem proving has recently received much attention. Current approaches use representations of logical statements that often rely on the names used in these statements and, as a result, the models are generally not transferable from one domain to another. The size of these representations and whether to include the whole theory or part of it are other important decisions that affect the performance of these approaches as well as their runtime efficiency. In this paper, we present NIAGRA; an ensemble Name InvAriant Graph RepresentAtion. NIAGRA addresses this problem by using 1) improved Graph Neural Networks for learning name-invariant formula representations that is tailored for their unique characteristics and 2) an efficient ensemble approach for automated theorem proving. Our experimental evaluation shows state-of-the-art performance on multiple datasets from different domains with improvements up to 10% compared to the best learning-based approaches. Furthermore, transfer learning experiments show that our approach significantly outperforms other learning-based approaches by up to 28%.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Approximate Inference in Logical Credal Networks

Radu Marinescu
Haifeng Qian
Alexander Gray
Debarun Bhattacharjya
Francisco Barahona
Tian Gao
Ryan Riegel

The Logical Credal Network or LCN is a recent probabilistic logic designed for effective aggregation and reasoning over multiple sources of imprecise knowledge. An LCN specifies a set of probability distributions over all interpretations of a set of logical formulas for which marginal and conditional probability bounds on their truth values are known. Inference in LCNs involves the exact solution of a non-convex non-linear program defined over an exponentially large number of non-negative real valued variables and, therefore, is limited to relatively small problems. In this paper, we present ARIEL -- a novel iterative message-passing scheme for approximate inference in LCNs. Inspired by classical belief propagation for graphical models, our method propagates messages that involve solving considerably smaller local non-linear programs. Experiments on several classes of LCNs demonstrate clearly that ARIEL yields high quality solutions compared with exact inference and scales to much larger problems than previously considered.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

Credal Marginal MAP

Radu Marinescu
Debarun Bhattacharjya
Junkyu Lee
Fabio Cozman
Alexander Gray

Credal networks extend Bayesian networks to allow for imprecision in probability values. Marginal MAP is a widely applicable mixed inference task that identifies the most likely assignment for a subset of variables (called MAP variables). However, the task is extremely difficult to solve in credal networks particularly because the evaluation of each complete MAP assignment involves exact likelihood computations (combinatorial sums) over the vertices of a complex joint credal set representing the space of all possible marginal distributions of the MAP variables. In this paper, we explore Credal Marginal MAP inference and develop new exact methods based on variable elimination and depth-first search as well as several approximation schemes based on the mini-bucket partitioning and stochastic local search. An extensive empirical evaluation demonstrates the effectiveness of our new methods on random as well as real-world benchmark problems.

AAAI Conference 2022 Conference Paper

Bandit Limited Discrepancy Search and Application to Machine Learning Pipeline Optimization

Akihiro Kishimoto
Djallel Bouneffouf
Radu Marinescu
Parikshit Ram
Ambrish Rawat
Martin Wistuba
Paulito Palmes
Adi Botea

Optimizing a machine learning (ML) pipeline has been an important topic of AI and ML. Despite recent progress, pipeline optimization remains a challenging problem, due to potentially many combinations to consider as well as slow training and validation. We present the BLDS algorithm for optimized algorithm selection in a fixed ML pipeline structure. BLDS performs multi-fidelity optimization for selecting ML algorithms trained with smaller computational overhead, while controlling its pipeline search based on multi-armed bandit and limited discrepancy search. Our experiments on classification benchmarks show that BLDS is superior to competing algorithms. We also combine BLDS with hyperparameter optimization, empirically showing the advantage of BLDS.

NeurIPS Conference 2022 Conference Paper

Hedging as Reward Augmentation in Probabilistic Graphical Models

Debarun Bhattacharjya
Radu Marinescu

Most people associate the term `hedging' exclusively with financial applications, particularly the use of financial derivatives. We argue that hedging is an activity that human and machine agents should engage in more broadly, even when the agent's value is not necessarily in monetary units. In this paper, we propose a decision-theoretic view of hedging based on augmenting a probabilistic graphical model -- specifically a Bayesian network or an influence diagram -- with a reward. Hedging is therefore posed as a particular kind of graph manipulation, and can be viewed as analogous to control/intervention and information gathering related analysis. Effective hedging occurs when a risk-averse agent finds opportunity to balance uncertain rewards in their current situation. We illustrate the concepts with examples and counter-examples, and conduct experiments to demonstrate the properties and applicability of the proposed computational tools that enable agents to proactively identify potential hedging opportunities in real-world situations.

NeurIPS Conference 2022 Conference Paper

Logical Credal Networks

Radu Marinescu
Haifeng Qian
Alexander Gray
Debarun Bhattacharjya
Francisco Barahona
Tian Gao
Ryan Riegel
Pravinda Sahu

We introduce Logical Credal Networks (or LCNs for short) -- an expressive probabilistic logic that generalizes prior formalisms that combine logic and probability. Given imprecise information represented by probability bounds and conditional probability bounds on logic formulas, an LCN specifies a set of probability distributions over all its interpretations. Our approach allows propositional and first-order logic formulas with few restrictions, e. g. , without requiring acyclicity. We also define a generalized Markov condition that allows us to identify implicit independence relations between atomic formulas. We evaluate our method on benchmark problems such as random networks, Mastermind games with uncertainty and credit card fraud detection. Our results show that the LCN outperforms existing approaches; its advantage lies in aggregating multiple sources of imprecise information.

AAAI Conference 2021 Conference Paper

A New Bounding Scheme for Influence Diagrams

Radu Marinescu
Junkyu Lee
Rina Dechter

Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. Computing the maximum expected utility (MEU) and the optimizing policy is exponential in the constrained induced width and therefore is notoriously difficult for larger models. In this paper, we develop a new bounding scheme for MEU that applies partitioning based approximations on top of the decomposition scheme called a multi-operator cluster DAG for influence diagrams that is more sensitive to the underlying structure of the model than the classical join-tree decomposition of influence diagrams. Our bounding scheme utilizes a cost-shifting mechanism to tighten the bound further. We demonstrate the effectiveness of the proposed scheme on various hard benchmarks.

AAAI Conference 2021 Conference Paper

Learning the Parameters of Bayesian Networks from Uncertain Data

Segev Wasserkrug
Radu Marinescu
Sergey Zeltyn
Evgeny Shindin
Yishai A Feldman

The creation of Bayesian networks often requires the specification of a large number of parameters, making it highly desirable to be able to learn these parameters from historical data. In many cases, such data has uncertainty associated with it, including cases in which this data comes from unstructured analysis or from sensors. When creating diagnosis networks, for example, unstructured analysis algorithms can be run on the historical text descriptions or images of previous cases so as to extract data for learning Bayesian network parameters, but such derived data has inherent uncertainty associated with it due to the nature of such algorithms. Because of the inability of current Bayesian network parameter learning algorithms to incorporate such uncertainty, common approaches either ignore this uncertainty, thus reducing the resulting accuracy, or completely disregard such data. We present an approach for learning Bayesian network parameters that explicitly incorporates such uncertainty, and which is a natural extension of the Bayesian network formalism. We present a generalization of the Expectation Maximization parameter learning algorithm that enables it to handle any historical data with likelihoodevidence-based uncertainty, as well as an empirical validation demonstrating the improved accuracy and convergence enabled by our approach. We also prove that our extended algorithm maintains the convergence and correctness properties of the original EM algorithm, while explicitly incorporating data uncertainty in the learning process.

AAAI Conference 2021 Conference Paper

Searching for Machine Learning Pipelines Using a Context-Free Grammar

Radu Marinescu
Akihiro Kishimoto
Parikshit Ram
Ambrish Rawat
Martin Wistuba
Paulito P. Palmes
Adi Botea

AutoML automatically selects, composes and parameterizes machine learning algorithms into a workflow or pipeline of operations that aims at maximizing performance on a given dataset. Although current methods for AutoML achieved impressive results they mostly concentrate on optimizing fixed linear workflows. In this paper, we take a different approach and focus on generating and optimizing pipelines of complex directed acyclic graph shapes. These complex pipeline structure may lead to discovering new synthetic features and thus boost performance considerably. We explore the power of heuristic search and context-free grammars to search and optimize these kinds of pipelines. Experiments on various benchmark datasets show that our approach is highly competitive and often outperforms existing AutoML systems.

AAAI Conference 2021 Conference Paper

Submodel Decomposition Bounds for Influence Diagrams

Junkyu Lee
Radu Marinescu
Rina Dechter

Influence diagrams (IDs) are graphical models for representing and reasoning with sequential decision-making problems under uncertainty. Limited memory influence diagrams (LIMIDs) model a decision-maker (DM) who forgets the history in the course of making a sequence of decisions. The standard inference task in IDs and LIMIDs is to compute the maximum expected utility (MEU), which is one of the most challenging tasks in graphical models. We present a model decomposition framework in both IDs and LIMIDs, which we call submodel decomposition that generates a tree of single-stage decision problems through a tree clustering scheme. We also develop a valuation algebra over the submodels that leads to a hierarchical message passing algorithm that propagates conditional expected utility functions over a submodel-tree as external messages. We show that the overall complexity is bounded by the maximum tree-width over the submodels, common in graphical model algorithms. Finally, we present a new method for computing upper bounds over a submodel-tree by first exponentiating the utility functions yielding a standard probabilistic graphical model as an upper bound and then applying standard variational upper bounds for the marginal MAP inference, yielding tighter upper bounds compared with state-of-the-art bounding schemes for the MEU task.

AAAI Conference 2020 Conference Paper

Parallel AND/OR Search for Marginal MAP

Radu Marinescu
Akihiro Kishimoto
Adi Botea

Marginal MAP is a difﬁcult mixed inference task for graphical models. Existing state-of-the-art algorithms for solving exactly this task are based on either depth-ﬁrst or best-ﬁrst sequential search over an AND/OR search space. In this paper, we explore and evaluate for the ﬁrst time the power of parallel search for exact Marginal MAP inference. We introduce a new parallel shared-memory recursive best-ﬁrst AND/OR search algorithm that explores the search space in a best-ﬁrst manner while operating with limited memory. Subsequently, we develop a complete parallel search scheme that only parallelizes the conditional likelihood computations. We also extend the proposed algorithms into depth-ﬁrst parallel search schemes. Our experiments on difﬁcult benchmarks demonstrate the effectiveness of the parallel search algorithms against current sequential methods for solving Marginal MAP exactly.

AAAI Conference 2019 Conference Paper

Anytime Recursive Best-First Search for Bounding Marginal MAP

Radu Marinescu
Akihiro Kishimoto
Adi Botea
Rina Dechter
Alexander Ihler

Marginal MAP is a difficult mixed inference task for graphical models. Existing state-of-the-art solvers for this task are based on a hybrid best-first and depth-first search scheme that allows them to compute upper and lower bounds on the optimal solution value in an anytime fashion. These methods however are memory intensive schemes (via the best-first component) and do not have an efficient memory management mechanism. For this reason, they are often less effective in practice, especially on difficult problem instances with very large search spaces. In this paper, we introduce a new recursive best-first search based bounding scheme that operates efficiently within limited memory and computes anytime upper and lower bounds that improve over time. An empirical evaluation demonstrates the effectiveness of our proposed approach against current solvers.

NeurIPS Conference 2019 Conference Paper

Counting the Optimal Solutions in Graphical Models

Radu Marinescu
Rina Dechter

We introduce #opt, a new inference task for graphical models which calls for counting the number of optimal solutions of the model. We describe a novel variable elimination based approach for solving this task, as well as a depth-first branch and bound algorithm that traverses the AND/OR search space of the model. The key feature of the proposed algorithms is that their complexity is exponential in the induced width of the model only. It does not depend on the actual number of optimal solutions. Our empirical evaluation on various benchmarks demonstrates the effectiveness of the proposed algorithms compared with existing depth-first and best-first search based approaches that enumerate explicitly the optimal solutions.

IJCAI Conference 2019 Conference Paper

Depth-First Memory-Limited AND/OR Search and Unsolvability in Cyclic Search Spaces

Akihiro Kishimoto
Adi Botea
Radu Marinescu

Computing cycle-free solutions in cyclic AND/OR search spaces is an important AI problem. Previous work on optimal depth-first search strongly assumes the use of consistent heuristics, the need to keep all examined states in a transposition table, and the existence of solutions. We give a new theoretical analysis under relaxed assumptions where previous results no longer hold. We then present a generic approachto proving unsolvability, and apply it to RBFAOO and BLDFS, two state-of-the-art algorithms. We demonstrate the performance in domain-independent nondeterministic planning

JAIR Journal 2018 Journal Article

AND/OR Search for Marginal MAP

Radu Marinescu
Junkyu Lee
Rina Dechter
Alexander Ihler

Mixed inference such as the marginal MAP query (some variables marginalized by summation and others by maximization) is key to many prediction and decision models. It is known to be extremely hard; the problem is NP PP -complete while the decision problem for MAP is only NP-complete and the summation problem is #P-complete. Consequently, approximation anytime schemes are essential. In this paper, we show that the framework of heuristic AND/OR search, which exploits conditional independence in the graphical model, coupled with variational-based mini-bucket heuristics can be extended to this task and yield powerful state-of-the-art schemes. Specifically, we explore the complementary properties of best-first search for reducing the number of conditional sums and providing time-improving upper bounds, with depth-first search for rapidly generating and improving solutions and lower bounds. We show empirically that a class of solvers that interleaves depth-first with best-first schemes emerges as the most competitive anytime scheme.

PDF Details DOI

NeurIPS Conference 2018 Conference Paper

From Stochastic Planning to Marginal MAP

Hao(Jackson) Cui
Radu Marinescu
Roni Khardon

It is well known that the problems of stochastic planning and probabilistic inference are closely related. This paper makes two contributions in this context. The first is to provide an analysis of the recently developed SOGBOFA heuristic planning algorithm that was shown to be effective for problems with large factored state and action spaces. It is shown that SOGBOFA can be seen as a specialized inference algorithm that computes its solutions through a combination of a symbolic variant of belief propagation and gradient ascent. The second contribution is a new solver for Marginal MAP (MMAP) inference. We introduce a new reduction from MMAP to maximum expected utility problems which are suitable for the symbolic computation in SOGBOFA. This yields a novel algebraic gradient-based solver (AGS) for MMAP. An experimental evaluation illustrates the potential of AGS in solving difficult MMAP problems.

IJCAI Conference 2018 Conference Paper

Stochastic Anytime Search for Bounding Marginal MAP

Radu Marinescu
Rina Dechter
Alexander Ihler

The Marginal MAP inference task is known to be extremely hard particularly because the evaluation of each complete MAP assignment involves an exact likelihood computation (a combinatorial sum). For this reason, most recent state-of-the-art solvers that focus on computing anytime upper and lower bounds on the optimal value are limited to solving instances with tractable conditioned summation subproblems. In this paper, we develop new search-based bounding schemes for Marginal MAP that produce anytime upper and lower bounds without performing exact likelihood computations. The empirical evaluation demonstrates the effectiveness of our new methods against the current best-performing search-based bounds.

AAAI Conference 2017 Conference Paper

Anytime Best+Depth-First Search for Bounding Marginal MAP

Radu Marinescu
Junkyu Lee
Alexander Ihler
Rina Dechter

We introduce new anytime search algorithms that combine best-ﬁrst with depth-ﬁrst search into hybrid schemes for Marginal MAP inference in graphical models. The main goal is to facilitate the generation of upper bounds (via the best- ﬁrst part) alongside the lower bounds of solutions (via the depth-ﬁrst part) in an anytime fashion. We compare against two of the best current state-of-the-art schemes and show that our best+depth search scheme produces higher quality solutions faster while also producing a bound on their accuracy, which can be used to measure solution quality during search. An extensive empirical evaluation demonstrates the effectiveness of our new methods which enjoy the strength of best-ﬁrst (optimality of search) and of depth-ﬁrst (memory robustness), leading to solutions for difﬁcult instances where previous solvers were unable to ﬁnd even a single solution.

IJCAI Conference 2017 Conference Paper

Efficient Optimal Search under Expensive Edge Cost Computation

Masataro Asai
Akihiro Kishimoto
Adi Botea
Radu Marinescu
Elizabeth M. Daly
Spyros Kotoulas

Optimal heuristic search has been successful in many domains, including journey planning, route planning and puzzle solving. Existing work typically assumes that the cost of each action can easily be obtained. However, in many problems, the exact edge cost is expensive to compute. Existing search algorithms face a significant performance bottleneck, due to an excessive overhead associated with dynamically calculating exact edge costs. We present DEA*, an algorithm for problems with expensive edge cost computations. DEA* combines heuristic edge cost evaluations with delayed node expansions, reducing the number of exact edge computations. We formally prove that DEA* is optimal and it is efficient with respect to the number of exact edge cost computations. We empirically evaluate DEA* on multiple-worker routing problems where the exact edge cost is calculated by invoking an external multi-modal journey planning engine. The results demonstrate the effectiveness of our ideas in reducing the computational time and improving the solving ability. In addition, we show the advantages of DEA* in domain-independent planning, where we simulate that accurate edge costs are expensive to compute.

AAAI Conference 2017 Conference Paper

Multi-Objective Influence Diagrams with Possibly Optimal Policies

Radu Marinescu
Abdul Razak
Nic Wilson

The formalism of multi-objective inﬂuence diagrams has recently been developed for modeling and solving sequential decision problems under uncertainty and multiple objectives. Since utility values representing the decision maker’s preferences are only partially ordered (e. g. , by the Pareto order) we no longer have a unique maximal value of expected utility, but a set of them. Computing the set of maximal values of expected utility and the corresponding policies can be computationally very challenging. In this paper, we consider alternative notions of optimality, one of the most important one being the notion of possibly optimal, namely optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop a variable elimination algorithm for computing the set of possibly optimal expected utility values, prove formally its correctness, and compare variants of the algorithm experimentally.

AAAI Conference 2016 Conference Paper

From Exact to Anytime Solutions for Marginal MAP

Junkyu Lee
Radu Marinescu
Rina Dechter
Alexander Ihler

This paper explores the anytime performance of search-based algorithms for solving the Marginal MAP task over graphical models. The current state-of-the-art for solving this challenging task is based on best-ﬁrst search exploring the AND/OR graph with the guidance of heuristics based on mini-bucket and variational cost-shifting principles. Yet, those schemes are uncompromising in that they solve the problem exactly, or not at all, and often suffer from memory problems. In this work, we explore the well known principle of weighted search for converting best-ﬁrst search solvers into anytime schemes. The weighted best-ﬁrst search schemes report a solution early in the process by using inadmissible heuristics, and subsequently improve the solution. While it was demonstrated recently that weighted schemes can yield effective anytime behavior for pure MAP tasks, Marginal MAP is far more challenging (e. g. , a conditional sum must be evaluated for every solution). Yet, in an extensive empirical analysis we show that weighted schemes are indeed highly effective anytime solvers for Marginal MAP yielding the most competitive schemes to date for this task.

JAIR Journal 2016 Journal Article

Searching for the M Best Solutions in Graphical Models

Natalia Flerova
Radu Marinescu
Rina Dechter

The paper focuses on finding the m best solutions to combinatorial optimization problems using best-first or depth-first branch and bound search. Specifically, we present a new algorithm m-A*, extending the well-known A* to the m-best task, and for the first time prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since best-first algorithms require extensive memory, we also extend the memory-efficient depth-first branch and bound to the m-best task. We adapt both algorithms to optimization tasks over graphical models (e.g., Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments confirm theory that the best-first approach is largely superior when memory is available, but depth-first branch and bound is more robust. We also show that our algorithms are competitive with related schemes recently developed for the m-best task.

PDF Details DOI

IJCAI Conference 2015 Conference Paper

Computing Possibly Optimal Solutions for Multi-Objective Constraint Optimisation with Tradeoffs

Nic Wilson
Abdul Razak
Radu Marinescu

Computing the set of optimal solutions for a multiobjective constraint optimisation problem can be computationally very challenging. Also, when solutions are only partially ordered, there can be a number of different natural notions of optimality, one of the most important being the notion of Possibly Optimal, i. e. , optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop an AND/OR Branch-and-Bound algorithm for computing the set of Possibly Optimal solutions, and compare variants of the algorithm experimentally.

NeurIPS Conference 2015 Conference Paper

Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models

Akihiro Kishimoto
Radu Marinescu
Adi Botea

The paper presents and evaluates the power of parallel search for exact MAP inference in graphical models. We introduce a new parallel shared-memory recursive best-first AND/OR search algorithm, called SPRBFAOO, that explores the search space in a best-first manner while operating with restricted memory. Our experiments show that SPRBFAOO is often superior to the current state-of-the-art sequential AND/OR search approaches, leading to considerable speed-ups (up to 7-fold with 12 threads), especially on hard problem instances.

IJCAI Conference 2015 Conference Paper

Pushing Forward Marginal MAP with Best-First Search

Radu Marinescu
Rina Dechter
Alexander Ihler

Marginal MAP is known to be a difficult task for graphical models, particularly because the evaluation of each MAP assignment involves a conditional likelihood computation. In order to minimize the number of likelihood evaluations, we focus in this paper on best-first search strategies for exploring the space of partial MAP assignments. We analyze the potential relative benefits of several bestfirst search algorithms and demonstrate their effectiveness against recent branch and bound schemes through extensive empirical evaluations. Our results show that best-first search improves significantly over existing depth-first approaches, in many cases by several orders of magnitude, especially when guided by relatively weak heuristics.

KR Conference 2012 Conference Paper

An Axiomatic Framework for Influence Diagram Computation with Partially Ordered Utilities

Nic Wilson
Radu Marinescu

For a standard influence diagram we have both chance and decision variables, and we eliminate chance variables with a sum operator, and decision variables with a max operator. We can compute the maximum expected utility N by applying a sequence of sum and max eliminations to Θ, eliminating all the variables. Performing combinations leads to functions involving larger sets of variables, which is expensive in terms of both computational cost and time. One therefore would like to delay performing computations where possible. Thus, P when eliminating a variable X, with, for example, the operator, one transforms Θ to a collection Θ0, which includes only functions P N N 0 that don’t involve X, and is such that X (Θ) = Θ. Crucially, the functions in Θ that don’t involve X are left unchanged, so still appear in Θ0. This paper presents an axiomatic framework for influence diagram computation, which allows reasoning with partially ordered values of utility. We show how an algorithm based on sequential variable elimination can be used to compute the set of maximal values of expected utility (up to an equivalence relation). Formalisms subsumed by the framework include decision making under uncertainty based on multi-objective utility, or on interval-valued utilities, as well as a more qualitative decision theory based on order-of-magnitude probabilities and utilities.

AAAI Conference 2012 Conference Paper

Search Algorithms for m Best Solutions for Graphical Models

Rina Dechter
Natalia Flerova
Radu Marinescu

The paper focuses on finding the m best solutions to combinatorial optimization problems using Best-First or Branchand-Bound search. Specifically, we present m-A*, extending the well-known A* to the m-best task, and prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since Best-First algorithms have memory problems, we also extend the memoryefficient Depth-First Branch-and-Bound to the m-best task. We extend both algorithms to optimization tasks over graphical models (e. g. , Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments with 5 variants of Best-First and Branch-and-Bound confirm that Best-First is largely superior when memory is available, but Branch-and-Bound is more robust, while both styles of search benefit greatly when the heuristic evaluation function has increased accuracy.

AIJ Journal 2009 Journal Article

AND/OR Branch-and-Bound search for combinatorial optimization in graphical models

Radu Marinescu
Rina Dechter

This is the first of two papers presenting and evaluating the power of a new framework for combinatorial optimization in graphical models, based on AND/OR search spaces. We introduce a new generation of depth-first Branch-and-Bound algorithms that explore the AND/OR search tree using static and dynamic variable orderings. The virtue of the AND/OR representation of the search space is that its size may be far smaller than that of a traditional OR representation, which can translate into significant time savings for search algorithms. The focus of this paper is on linear space search which explores the AND/OR search tree. In the second paper we explore memory intensive AND/OR search algorithms. In conjunction with the AND/OR search space we investigate the power of the mini-bucket heuristics in both static and dynamic setups. We focus on two most common optimization problems in graphical models: finding the Most Probable Explanation in Bayesian networks and solving Weighted CSPs. In extensive empirical evaluations we demonstrate that the new AND/OR Branch-and-Bound approach improves considerably over the traditional OR search strategy and show how various variable ordering schemes impact the performance of the AND/OR search scheme.

AIJ Journal 2009 Journal Article

Memory intensive AND/OR search for combinatorial optimization in graphical models

Radu Marinescu
Rina Dechter

In this paper we explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation (MPE) in belief networks and solving Weighted CSPs (WCSP). In an extensive empirical evaluation we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks.

AAAI Conference 2007 Conference Paper

Best-First AND/OR Search for Graphical Models

Radu Marinescu

The paper presents and evaluates the power of best-ﬁrst search over AND/OR search spaces in graphical models. The main virtue of the AND/OR representation is its sensitivity to the structure of the graphical model, which can translate into signiﬁcant time savings. Indeed, in recent years depth-ﬁrst AND/OR Branch-and-Bound algorithms were shown to be very effective when exploring such search spaces, especially when using caching. Since best-ﬁrst strategies are known to be superior to depth-ﬁrst when memory is utilized, exploring the best-ﬁrst control strategy is called for. In this paper we introduce two classes of best-ﬁrst AND/OR search algorithms: those that explore a context-minimal AND/OR search graph and use static variable orderings, and those that use dynamic variable orderings but explore an AND/OR search tree. The superiority of the best-ﬁrst search approach is demonstrated empirically on various real-world benchmarks.

AAAI Conference 2006 Conference Paper

Memory Intensive Branch-and-Bound Search for Graphical Models

Radu Marinescu

AND/OR search spaces have recently been introduced as a unifying paradigm for advanced algorithmic schemes for graphical models. The main virtue of this representation is its sensitivity to the structure of the model, which can translate into exponential time savings for search algorithms. AND/OR Branch-and-Bound (AOBB) is a new algorithm that explores the AND/OR search tree for solving optimization tasks in graphical models. In this paper we extend the algorithm to explore an AND/OR search graph by equipping it with a context-based adaptive caching scheme similar to good and no-good recording. The efficiency of the new graph search algorithm is demonstrated empirically on various benchmarks, including the very challenging ones that arise in genetic linkage analysis.

IJCAI Conference 2005 Conference Paper

AND/OR Branch-and-Bound for Graphical Models

Radu Marinescu
Rina

The paper presents and evaluates the power of a new framework for optimization in graphical models, based on AND/OR search spaces. The virtue of the AND/OR representation of the search space is that its size may be far smaller than that of a traditional OR representation. We develop our work on Constraint Optimization Problems (COP) and introduce a new generation of depth-first Branch-and-Bound algorithms that explore an AND/OR search space and use static and dynamic mini-bucket heuristics to guide the search. We focus on two optimization problems, solving Weighted CSPs (WCSP) and finding the Most Probable Explanation (MPE) in belief networks. We show that the new AND/OR approach improves considerably over the classic OR space, on a variety of benchmarks including random and real-world problems. We also demonstrate the impact of different lower bounding heuristics on Branch-and-Bound exploring AND/OR spaces.