bluuebunny/crossref_metadata_2025 huggingface dataset:
Nonparametric Scoring Rules
Authors: Zawadzki Erik , Lahaie Sebastien
Published: June 2022

A scoring rule is a device for eliciting and assessing probabilistic forecasts from an agent. When dealing with continuous outcome spaces, and absent any prior insights into the structure of the agent's beliefs, the rule should allow for a flexible reporting interface that can accurately represent complicated, multi-modal distributions. In this paper, we provide such a scoring rule based on a nonparametric approach of eliciting a set of samples from the agent and efficiently evaluating the score using kernel methods. We prove that sampled reports of increasing size converge rapidly to the true score, and that sampled reports are approximately optimal. We also demonstrate a connection between the scoring rule and the maximum mean discrepancy divergence. Experimental results are provided that confirm rapid convergence and that the expected score correlates well with standard notions of divergence, both important considerations for ensuring that agents are incentivized to report accurate information.
Egalitarian Collective Decision Making under Qualitative Possibilistic Uncertainty: Principles and Characterization
Authors: Ben Amor Nahla , Essghaier Fatma , Fargier Helene
Published: June 2022

This paper raises the question of collective decisionmaking under possibilistic uncertainty; We study fouregalitarian decision rules and show that in the contextof a possibilistic representation of uncertainty, the useof an egalitarian collective utility function allows toget rid of the Timing Effect. Making a step further,we prove that if both the agents’ preferences and thecollective ranking of the decisions satisfy Dubois andPrade’s axioms (1995), and particularly risk aversion,and Pareto Unanimity, then the egalitarian collectiveaggregation is compulsory. This result can be seen asan ordinal counterpart of Harsanyi’s theorem (1955).
Reward Shaping for Model-Based Bayesian Reinforcement Learning
Authors: Kim Hyeoneun , Lim Woosang , Lee Kanghoon , Noh Yung-Kyun , Kim Kee-Eung
Published: June 2022

Bayesian reinforcement learning (BRL) provides a formal framework for optimal exploration-exploitation tradeoff in reinforcement learning. Unfortunately, it is generally intractable to find the Bayes-optimal behavior except for restricted cases. As a consequence, many BRL algorithms, model-based approaches in particular, rely on approximated models or real-time search methods. In this paper, we present potential-based shaping for improving the learning performance in model-based BRL. We propose a number of potential functions that are particularly well suited for BRL, and are domain-independent in the sense that they do not require any prior knowledge about the actual environment. By incorporating the potential function into real-time heuristic search, we show that we can significantly improve the learning performance in standard benchmark domains.
Approximately Optimal Risk-Averse Routing Policies via Adaptive Discretization
Authors: Hoy Darrell , Nikolova Evdokia
Published: June 2022

Mitigating risk in decision-making has been a long-standing problem. Due to the mathematical challenge of its nonlinear nature, especially in adaptive decision-making problems, finding optimal policies is typically intractable. With a focus on efficient algorithms, we ask how well we can approximate the optimal policies for the difficult case of general utility models of risk. Little is known about efficient algorithms beyond the very special cases of linear (risk-neutral) and exponential utilities since general utilities are not separable and preclude the use of traditional dynamic programming techniques. In this paper, we consider general utility functions and investigate efficient computation of approximately optimal routing policies, where the goal is to maximize the expected utility of arriving at a destination around a given deadline. We present an adaptive discretization variant of successive approximation which gives an $\error$-optimal policy in polynomial time. The main insight is to perform discretization at the utility level space, which results in a nonuniform discretization of the domain, and applies for any monotone utility function.
Improving Cross-Domain Recommendation through Probabilistic Cluster-Level Latent Factor Model
Authors: Ren Siting , Gao Sheng , Liao Jianxin , Guo Jun
Published: June 2022

Cross-domain recommendation has been proposed to transfer user behavior pattern by pooling together the rating data from multiple domains to alleviate the sparsity problem appearing in single rating domains. However, previous models only assume that multiple domains share a latent common rating pattern based on the user-item co-clustering. To capture diversities among different domains, we propose a novel Probabilistic Cluster-level Latent Factor (PCLF) model to improve the cross-domain recommendation performance. Experiments on several real world datasets demonstrate that our proposed model outperforms the state-of-the-art methods for the cross-domain recommendation task.
Learning Word Vectors Efficiently Using Shared Representations and Document Representations
Authors: Luo Qun , Xu Weiran
Published: June 2022

We propose some better word embedding models based on vLBL model and ivLBL model by sharing representations between context and target words and using document representations. Our proposed models are much simpler which have almost half less parameters than the state-of-the-art methods. We achieve better results on word analogy task than the best ones reported before using significantly less training data and computing time.
Characterizing Performance of Consistency Algorithms by Algorithm Configuration of Random CSP Generators
Authors: Geschwender Daniel , Woodward Robert , Choueiry Berthe
Published: June 2022

In Constraint Processing, many algorithms for enforcing the same level of local consistency may exist. The performance of those algorithms varies widely. In order to understand what problem features lead to better performance of one algorithm over another, we utilize an algorithm configurator to tune the parameters of a random problem generator and maximize the performance difference of two consistency algorithms for enforcing constraint minimality. Our approach allowed us to generate instances that run 1000 times faster for one algorithm over the other.
Just-in-Time Hierarchical Constraint Decomposition
Authors: Mayer-Eichberger Valentin
Published: June 2022

Lazy Clause Generation (LCG) solvers dominate the current constraint programming competitions. These solvers successfully combine systematic propagation based search, global constraints and conflict clause learning from SAT solving into a hybrid approach. My research project extends the LCG methodology by using a mix of eager and lazy encodings and a richer set of constraint decompositions. Global Constraints exhibit a whole hierarchy of different decomposition into more basic constraints. In our work we want to take advantage of such hierarchies and identify criteria on how constraints could be decomposed before and during search.
Effect of Spatial Pooler Initialization on Column Activity in Hierarchical Temporal Memory
Authors: Leake Mackenzie , Xia Liyu , Rocki Kamil , Imaino Wayne
Published: June 2022

In the Hierarchical Temporal Memory (HTM) paradigm the effect of overlap between inputs on the activation of columns in the spatial pooler is studied. Numerical results suggest that similar inputs are represented by similar sets of columns and dissimilar inputs are represented by dissimilar sets of columns. It is shown that the spatial pooler produces these results under certain conditions for the connectivity and proximal thresholds at initialization. Qualitative arguments about the learning dynamics of the spatial pooler are then discussed.
Every Team Deserves a Second Chance: Identifying When Things Go Wrong (Student Abstract Version)
Authors: Nagarajan Vaishnavh , Soriano Marcolino Leandro , Tambe Milind
Published: June 2022

We show that without using any domain knowledge, we can predict the final performance of a team of voting agents, at any step towards solving a complex problem.
Finding Meaningful Gaps to Guide Data Acquisition for a Radiation Adjudication System
Authors: Gisolfi Nick , Fiterau Madalina , Dubrawski Artur
Published: June 2022

We consider the problem of identifying discrepancies between training and test data which are responsible for the reduced performance of a classification system. Intended for use when data acquisition is an iterative process controlled by domain experts, our method exposes insufficiencies of training data and presents them in a user-friendly manner. The system is capable of working with any classification system which admits diagnostics on test data. We illustrate the usefulness of our approach in recovering compact representations of the revealed gaps in training data and show that predictive accuracy of the resulting models is improved once the gaps are filled through collection of additional training samples.
Strong Bounds Consistencies and Their Application to Linear Constraints
Authors: Bessiere Christian , Paparrizou Anastasia , Stergiou Kostas
Published: June 2022

We propose two local consistencies that extend bounds consistency (BC) by simultaneously considering combinations of constraints as opposed to single constraints. We prove that these two local consistencies are both stronger than BC, but are NP-hard to enforce even when constraints are linear. Hence, we propose two polynomial-time techniques to enforce approximations of these two consistencies on linear constraints. One is a reformulation of the constraints on which we enforce BC whereas the other is a polynomial time algorithm. Both achieve stronger pruning than BC. Our experiments show large differences in favor of our approaches.
Intelligent Agents for Rehabilitation and Care of Disabled and Chronic Patients
Authors: Kraus Sarit
Published: June 2022

The number of people with disabilities is continuously increasing. Providing patients who have disabilities with the rehabilitation and care necessary to allow them good quality of life creates overwhelming demands for health and rehabilitation services. We suggest that advancements in intelligent agent technology provide new opportunities for improving the provided services. We will discuss the challenges of building an agent for the health care domain and present four capabilities that are required for an agent in the health care domain: planning, monitoring, intervention and encouragement. We will discuss the importance of personalizing all of them and the needto facilitate cooperation between the automated agent and the human care givers. We will review recent technology that can be used toward the development of agents that can have these capabilities and their promise in automating services such as physiotherapy, speech therapy and cognitive training.
Challenges in Resource and Cost Allocation
Authors: Walsh Toby
Published: June 2022

Many models and mechanisms in resource and cost allocation have been developed that are simple and abstract. By means of two case studies, I argue that it is now timely to consider richer models for the fair division of resources and for the allocation of costs. Such models should have features like asynchronicity which reflect more of the true complexity of many fair division and cost allocation problems met in the real world. I suggest that computation can be used in such models to increase both efficiency and fairness of the allocations. As a result, we may be able to do more with fewer resources and greater fairness.
Towards User-Adaptive Information Visualization
Authors: Conati Cristina , Carenini Giuseppe , Toker Dereck , Lallé Sébastien
Published: June 2022

This paper summarizes an ongoing multi-year project aiming to uncover knowledge and techniques for devising intelligent environments for user-adaptive visualizations. We ran three studies designed to investigate the impact of user and task characteristics on user performance and satisfaction in different visualization contexts. Eye-tracking data collected in each study was analyzed to uncover possible interactions between user/task characteristics and gaze behavior during visualization processing. Finally, we investigated user models that can assess user characteristics relevant for adaptation from eye tracking data.
Languages for Learning and Mining
Authors: De Raedt Luc
Published: June 2022

Applying machine learning and data mining to novel applications is cumbersome. This observation is the prime motivation for the interest in languages for learning and mining. This note provides a gentle introduction to three types of languages that support machine learning and data mining: inductive query languages, which extend database query languages with primitives for mining and learning, modelling languages, which allow to declaratively specify and solve mining and learning problems, and programming languages, that support the learning of functions and subroutines. It uses an example of each type of language to introduce the underlying ideas and puts them into a common perspective. This then forms the basis for a short analysis of the state-of-the-art.
Interactive Narrative Planning in The Best Laid Plans
Authors: Ware Stephen , Young R. , Stith Christian , Wright Phillip
Published: June 2022

The Best Laid Plans is an interactive narrative video game that uses cognitive-inspired fast planning techniques to generate stories with conflict during play. Players alternate between acting out a plan and seeing that plan thwarted by non-player characters. The Glaive narrative planner combines causal-link-based computational models of narrative with the speed of fast heuristic search techniques to adapt the story each time the player attempts a new plan.
Deep Representation Learning with Target Coding
Authors: Yang Shuo , Luo Ping , Loy Chen Change , Shum Kenneth W. , Tang Xiaoou
Published: June 2022

We consider the problem of learning deep representation when target labels are available. In this paper, we show that there exists intrinsic relationship between target coding and feature representation learning in deep networks. Specifically, we found that distributed binary acode with error correcting capability is more capable of encouraging discriminative features, in comparison tothe 1-of-K coding that is typically used in supervised deep learning. This new finding reveals additional benefit of using error-correcting code for deep model learning,apart from its well-known error correcting property. Extensive experiments are conducted on popular visual benchmark datasets.
Position Assignment on an Enterprise Level Using Combinatorial Optimization
Authors: Leonard Kinnaird-Heether Leonard Kinnaird-Heether , Dorman Chris
Published: June 2022

We developed a tool to solve a problem of position assignment within the IT Ford College Graduate program. This position assignment tool was first developed in 2012 and has been used successfully since then. The tool has since evolved for use with several other position assignment and related tasks with other similar programs in Ford Motor Company. This paper will describe the creation of this tool and how we have applied it, focusing on the need for developing such a tool, and how the continued development of this tool will benefit its users and the company.
Automated Problem List Generation from Electronic Medical Records in IBM Watson
Authors: Devarakonda Murthy , Tsou Ching-Huei
Published: June 2022

Identifying a patient’s important medical problems requires broad and deep medical expertise, as well as significant time to gather all the relevant facts from the patient’s medical record and assess the clinical importance of the facts in reaching the final conclusion. A patient’s medical problem list is by far the most critical information that a physician uses in treatment and care of a patient. In spite of its critical role, its curation, manual or automated, has been an unmet need in clinical practice. We developed a machine learning technique in IBM Watson to automatically generate a patient’s medical problem list. The machine learning model uses lexical and medical features extracted from a patient’s record using NLP techniques. We show that the automated method achieves 70% recall and 67% precision based on the gold standard that medical experts created on a set of deidentified patient records from a major hospital system in the US. To the best of our knowledge this is the first successful machine learning/NLP method of extracting an open-ended patient’s medical problems from an Electronic Medical Record (EMR). This paper also contributes a methodology for assessing accuracy of a medical problem list generation technique.
Design and Experiment of a Collaborative Planning Service for NetCentric International Brigade Command
Authors: Guettier Christophe , Lamal Willy , Mayk Israel , Yelloz Jacques
Published: June 2022

Complex operational environments require improved tactical mission command capabilities with a high level of interoperability among coalition control and command (C2) systems. This paper focuses on two areas of interest: decision support based on automated planning and Service Oriented Architecture (SOA) for rapid service development. Previous experiments were performed bilaterally by US, France and Germany to focus on collaborative mission planning using Web Services (WSs). The results reported herein were obtained from a unified experiment performed by US, France and Germany involving a common scenario. The operational benefit from the experimentation has been to improve mutual understanding among allied forces, to dynamically plan for assistance among ground support troops (logistics, MEDEVAC, and other areas) as well as to improve their coordination. The effort addressed system design, and integration within an experimental framework. It enabled the evolution of the CERDEC Mission Command Gateway (MCG) architecture as well as a constraint based planner ORTAC, developed by French DGA and Sagem. It takes into account near real-time multimodal Situation Awareness and readiness status from tactical edge units. The trilateral experiment, entitled From Data to Decision included Net-Centric manned and unmanned assets from all three nations (France Germany US) operating as a cohesive coalition force while preserving command and support relationships as required through their respective chains of command.
Representing Verbs as Argument Concepts
Authors: Gong Yu , Zhao Kaiqi , Zhu Kenny
Published: June 2022

Verbs play an important role in the understanding of natural language text. This paper studies the problem of abstracting the subject and object arguments of a verb into a set of noun concepts, known as the “argument concepts”. This set of concepts, whose size is parameterized, represents the fine-grained semantics of a verb. For example, the object of “enjoy” can be abstracted into time, hobby and event, etc. We present a novel framework to automatically infer human readable and machine computable action concepts with high accuracy.
Complementing Semantic Roles with Temporally Anchored Spatial Knowledge: Crowdsourced Annotations and Experiments
Authors: Vempala Alakananda , Blanco Eduardo
Published: June 2022

This paper presents a framework to infer spatial knowledge from semantic role representations. We infer whether entities are or are not located somewhere, and temporally anchor this spatial information. A large crowdsourcing effort on top of OntoNotes shows that these temporally-anchored spatial inferences are ubiquitous and intuitive to humans. Experimental results show that inferences can be performed automatically and semantic features bring significant improvement.
Text Matching as Image Recognition
Authors: Pang Liang , Lan Yanyan , Guo Jiafeng , Xu Jun , Wan Shengxian , Cheng Xueqi
Published: June 2022

Matching two texts is a fundamental problem in many natural language processing tasks. An effective way is to extract meaningful matching patterns from words, phrases, and sentences to produce the matching score. Inspired by the success of convolutional neural network in image recognition, where neurons can capture many complicated patterns based on the extracted elementary visual patterns such as oriented edges and corners, we propose to model text matching as the problem of image recognition. Firstly, a matching matrix whose entries represent the similarities between words is constructed and viewed as an image. Then a convolutional neural network is utilized to capture rich matching patterns in a layer-by-layer way. We show that by resembling the compositional hierarchies of patterns in image recognition, our model can successfully identify salient signals such as n-gram and n-term matchings. Experimental results demonstrate its superiority against the baselines.
Inferring Interpersonal Relations in Narrative Summaries
Authors: Srivastava Shashank , Chaturvedi Snigdha , Mitchell Tom
Published: June 2022

Characterizing relationships between people is fundamental for the understanding of narratives. In this work, we address the problem of inferring the polarity of relationships between people in narrative summaries. We formulate the problem as a joint structured prediction for each narrative, and present a general model that combines evidence from linguistic and semantic features, as well as features based on the structure of the social community in the text. We additionally provide a clustering-based approach that can exploit regularities in narrative types. e.g., learn an affinity for love-triangles in romantic stories. On a dataset of movie summaries from Wikipedia, our structured models provide more than 30% error-reduction over a competitive baseline that considers pairs of characters in isolation.
A Morphology-Aware Network for Morphological Disambiguation
Authors: Yildiz Eray , Tirkaz Caglar , Sahin H. , Eren Mustafa , Sonmez Omer
Published: June 2022

Agglutinative languages such as Turkish, Finnish andHungarian require morphological disambiguation beforefurther processing due to the complex morphologyof words. A morphological disambiguator is usedto select the correct morphological analysis of a word.Morphological disambiguation is important because itgenerally is one of the first steps of natural languageprocessing and its performance affects subsequent analyses.In this paper, we propose a system that uses deeplearning techniques for morphological disambiguation.Many of the state-of-the-art results in computer vision,speech recognition and natural language processinghave been obtained through deep learning models.However, applying deep learning techniques to morphologicallyrich languages is not well studied. In this work,while we focus on Turkish morphological disambiguationwe also present results for French and German inorder to show that the proposed architecture achieveshigh accuracy with no language-specific feature engineeringor additional resource. In the experiments, weachieve 84.12 , 88.35 and 93.78 morphological disambiguationaccuracy among the ambiguous words forTurkish, German and French respectively.
Listen, Attend, and Walk: Neural Mapping of Navigational Instructions to Action Sequences
Authors: Mei Hongyuan , Bansal Mohit , Walter Matthew
Published: June 2022

We propose a neural sequence-to-sequence model for direction following, a task that is essential to realizing effective autonomous agents. Our alignment-based encoder-decoder model with long short-term memory recurrent neural networks (LSTM-RNN) translates natural language instructions to action sequences based upon a representation of the observable world state. We introduce a multi-level aligner that empowers our model to focus on sentence "regions" salient to the current world state by using multiple abstractions of the input sentence. In contrast to existing methods, our model uses no specialized linguistic resources (e.g., parsers) or task-specific annotations (e.g., seed lexicons). It is therefore generalizable, yet still achieves the best results reported to-date on a benchmark single-sentence dataset and competitive results for the limited-training multi-sentence setting. We analyze our model through a series of ablations that elucidate the contributions of the primary components of our model.
Extracting Topical Phrases from Clinical Documents
Authors: He Yulan
Published: June 2022

In clinical documents, medical terms are often expressed in multi-word phrases. Traditional topic modelling approaches relying on the "bag-of-words" assumption are not effective in extracting topic themes from clinical documents. This paper proposes to first extract medical phrases using an off-the-shelf tool for medical concept mention extraction, and then train a topic model which takes a hierarchy of Pitman-Yor processes as prior for modelling the generation of phrases of arbitrary length. Experimental results on patients' discharge summaries show that the proposed approach outperforms the state-of-the-art topical phrase extraction model on both perplexity and topic coherence measure and finds more interpretable topics.
Improving Recommendation of Tail Tags for Questions in Community Question Answering
Authors: Wu Yu , Wu Wei , Li Zhoujun , Zhou Ming
Published: June 2022

We study tag recommendation for questions in community question answering (CQA). Tags represent the semantic summarization of questions are useful for navigation and expert finding in CQA and can facilitate content consumption such as searching and mining in these web sites. The task is challenging, as both questions and tags are short and a large fraction of tags are tail tags which occur very infrequently. To solve these problems, we propose matching questions and tags not only by themselves, but also by similar questions and similar tags. The idea is then formalized as a model in which we calculate question-tag similarity using a linear combination of similarity with similar questions and tags weighted by tag importance.Question similarity, tag similarity, and tag importance are learned in a supervised random walk framework by fusing multiple features. Our model thus can not only accurately identify question-tag similarity for head tags, but also improve the accuracy of recommendation of tail tags. Experimental results show that the proposed method significantly outperforms state-of-the-art methods on tag recommendation for questions. Particularly, it improves tail tag recommendation accuracy by a large margin.
Improving Twitter Sentiment Classification Using Topic-Enriched Multi-Prototype Word Embeddings
Authors: Ren Yafeng , Zhang Yue , Zhang Meishan , Ji Donghong
Published: June 2022

It has been shown that learning distributed word representations is highly useful for Twitter sentiment classification.Most existing models rely on a single distributed representation for each word.This is problematic for sentiment classification because words are often polysemous and each word can contain different sentiment polarities under different topics.We address this issue by learning topic-enriched multi-prototype word embeddings (TMWE).In particular, we develop two neural networks which 1) learn word embeddings that better capture tweet context by incorporating topic information, and 2) learn topic-enriched multiple prototype embeddings for each word.Experiments on Twitter sentiment benchmark datasets in SemEval 2013 show that TMWE outperforms the top system with hand-crafted features, and the current best neural network model.
Temporal Topic Analysis with Endogenous and Exogenous Processes
Authors: Wang Baiyang , Klabjan Diego
Published: June 2022

We consider the problem of modeling temporal textual data taking endogenous and exogenous processes into account. Such text documents arise in real world applications, including job advertisements and economic news articles, which are influenced by the fluctuations of the general economy. We propose a hierarchical Bayesian topic model which imposes a "group-correlated" hierarchical structure on the evolution of topics over time incorporating both processes, and show that this model can be estimated from Markov chain Monte Carlo sampling methods. We further demonstrate that this model captures the intrinsic relationships between the topic distribution and the time-dependent factors, and compare its performance with latent Dirichlet allocation (LDA) and two other related models. The model is applied to two collections of documents to illustrate its empirical performance: online job advertisements from DirectEmployers Association and journalists' postings on BusinessInsider.com.
Efficient Macroscopic Urban Traffic Models for Reducing Congestion: A PDDL+ Planning Approach
Authors: Vallati Mauro , Magazzeni Daniele , De Schutter Bart , Chrpa Lukas , McCluskey Thomas
Published: June 2022

The global growth in urbanisation increases the demand for services including road transport infrastructure, presenting challenges in terms of mobility. In this scenario, optimising the exploitation of urban road networks is a pivotal challenge. Existing urban traffic control approaches, based on complex mathematical models, can effectively deal with planned-ahead events, but are not able to cope with unexpected situations --such as roads blocked due to car accidents or weather-related events-- because of their huge computational requirements. Therefore, such unexpected situations are mainly dealt with manually, or by exploiting pre-computed policies. Our goal is to show the feasibility of using mixed discrete-continuous planning to deal with unexpected circumstances in urban traffic control. We present a PDDL+ formulation of urban traffic control, where continuous processes are used to model flows of cars, and show how planning can be used to efficiently reduce congestion of specified roads by controlling traffic light green phases. We present simulation results on two networks (one of them considers Manchester city centre) that demonstrate the effectiveness of the approach, compared with fixed-time and reactive techniques.
A Proactive Sampling Approach to Project Scheduling under Uncertainty
Authors: Varakantham Pradeep , Fu Na , Lau Hoong Chuin
Published: June 2022

Uncertainty in activity durations is a key characteristic of many real world scheduling problems in manufacturing, logistics and project management. RCPSP/max with durational uncertainty is a general  model that can be used to represent durational uncertainty in a wide variety of scheduling problems where there exist resource constraints. However, computing schedules or execution strategies for RCPSP/max with durational uncertainty is NP-hard and hence we focus on providing approximation methods in this paper. We provide a principled approximation approach based on Sample Average Approximation (SAA) to compute proactive schedules for RCPSP/max  with durational uncertainty. We further contribute an extension to SAA for improving scalability significantly without sacrificing on solution quality. Not only is our approach able to compute schedules at comparable runtimes as existing approaches, it also provides lower α-quantile makespan (also referred to as α-robust makespan) values than the best known approach on benchmark problems from the literature.
From Exact to Anytime Solutions for Marginal MAP
Authors: Lee Junkyu , Marinescu Radu , Dechter Rina , Ihler Alexander
Published: June 2022

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-first 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-first search solvers into anytime schemes. The weighted best-first 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 for Marginal MAP yielding the most competitive schemes to date for this task.
Exact Sampling with Integer Linear Programs and Random Perturbations
Authors: Kim Carolyn , Sabharwal Ashish , Ermon Stefano
Published: June 2022

We consider the problem of sampling from a discrete probability distribution specified by a graphical model. Exact samples can, in principle, be obtained by computing the mode of the original model perturbed with an exponentially many i.i.d. random variables. We propose a novel algorithm that views this as a combinatorial optimization problem and searches for the extreme state using a standard integer linear programming (ILP) solver, appropriately extended to account for the random perturbation. Our technique, GumbelMIP, leverages linear programming (LP) relaxations to evaluate the qualityof samples and prune large portions of the search space, and can thus scale to large tree-width models beyond the reach of current exact inference methods. Further, when the optimization problem is not solved to optimality, our method yields a novel approximate sampling technique. We empirically demonstrate that our approach parallelizes well, our exact sampler scales better than alternative approaches, and our approximate sampler yields better quality samples than a Gibbs sampler and a low-dimensional perturbation method.
Separators and Adjustment Sets in Markov Equivalent DAGs
Authors: Van der Zander Benito , Liskiewicz Maciej
Published: June 2022

In practice the vast majority of causal effect estimations from observational data are computed using adjustment sets which avoid confounding by adjusting for appropriate covariates. Recently several graphical criteria for selecting adjustment sets have been proposed. They handle causal directed acyclic graphs (DAGs) as well as more general types of graphs that represent Markov equivalence classes of DAGs, including completed partially directed acyclic graphs (CPDAGs). Though expressed in graphical language, it is not obvious how the criteria can be used to obtain effective algorithms for finding adjustment sets. In this paper we provide a new criterion which leads to an efficient algorithmic framework to find, test and enumerate covariate adjustments for chain graphs - mixed graphs representing in a compact way a broad range of Markov equivalence classes of DAGs.
On the Extraction of One Maximal Information Subset That Does Not Conflict with Multiple Contexts
Authors: Grégoire Éric , Izza Yacine , Lagniez Jean-Marie
Published: June 2022

The efficient extraction of one maximal information subset that does not conflict with multiple contxts or additional information sources is a key basic issue in many A.I. domains, especially when these contexts or sources can be mutually conflicting. In this paper, this question is addressed from a computational point of view in clausal Boolean logic. A new approach is introduced that experimentally outperforms the currently most efficient technique.
Counting-Based Search for Constraint Optimization Problems
Authors: Pesant Gilles
Published: June 2022

Branching heuristics based on counting solutions in constraints have been quite good at guiding search  to solve constraint satisfaction problems. But do they perform as well for constraint optimization problems? We propose an adaptation of counting-based search for optimization, show how to modify solution density computation for some of the most frequently-occurring constraints, and empirically evaluate its performance on several benchmark problems.
Increasing Nogoods in Restart-Based Search
Authors: Lee Jimmy , Schulte Christian , Zhu Zichen
Published: June 2022

Restarts are an important technique to make search more robust. This paper is concerned with how to maintain and propagate nogoods recorded from restarts efficiently. It builds on reduced nld-nogoods introduced for restarts and increasing nogoods introduced for symmetry breaking. The paper shows that reduced nld-nogoods extracted from a single restart are in fact increasing, which can thus benefit from the efficient propagation algorithm of the incNGs global constraint. We present a lighter weight filtering algorithm for incNGs in the context of restart-based search using dynamic event sets (dynamic subscriptions). We show formally that the lightweight version enforces GAC on each nogood while reducing the number of subscribed decisions. The paper also introduces an efficient approximation to nogood minimization such that all shortened reduced nld-nogoods from the same restart are also increasing and can be propagated with the new filtering algorithm. Experimental results confirm that our lightweight filtering algorithm and approximated nogood minimization successfully trade a slight loss in pruning for considerably better efficiency, and hence compare favorably against existing state-of-the-art techniques.
Using the Shapley Value to Analyze Algorithm Portfolios
Authors: Fréchette Alexandre , Kotthoff Lars , Michalak Tomasz , Rahwan Talal , Hoos Holger , Leyton-Brown Kevin
Published: June 2022

Algorithms for NP-complete problems often have different strengths andweaknesses, and thus algorithm portfolios often outperform individualalgorithms. It is surprisingly difficult to quantify a component algorithm's contributionto such a portfolio. Reporting a component's standalone performance wronglyrewards near-clones while penalizing algorithms that have small but distinctareas of strength. Measuring a component's marginal contribution to an existingportfolio is better, but penalizes sets of strongly correlated algorithms,thereby obscuring situations in which it is essential to have at least onealgorithm from such a set. This paper argues for analyzing component algorithmcontributions via a measure drawn from coalitional game theory---the Shapleyvalue---and yields insight into a research community's progress over time. Weconclude with an application of the analysis we advocate to SAT competitions,yielding novel insights into the behaviour of algorithm portfolios, theircomponents, and the state of SAT solving technology.
MC-HOG Correlation Tracking with Saliency Proposal
Authors: Zhu Guibo , Wang Jinqiao , Wu Yi , Zhang Xiaoyu , Lu Hanqing
Published: June 2022

Designing effective feature and handling the model drift problem are two important aspects for online visual tracking. For feature representation, gradient and color features are most widely used, but how to effectively combine them for visual tracking is still an open problem. In this paper, we propose a rich feature descriptor, MC-HOG, by leveraging rich gradient information across multiple color channels or spaces. Then MC-HOG features are embedded into the correlation tracking framework to estimate the state of the target. For handling the model drift problem caused by occlusion or distracter, we propose saliency proposals as prior information to provide candidates and reduce background interference. In addition to saliency proposals, a ranking strategy is proposed to determine the importance of these proposals by exploiting the learnt appearance filter, historical preserved object samples and the distracting proposals. In this way, the proposed approach could effectively explore the color-gradient characteristics and alleviate the model drift problem. Extensive evaluations performed on the benchmark dataset show the superiority of the proposed method.
Path Following with Adaptive Path Estimation for Graph Matching
Authors: Wang Tao , Ling Haibin
Published: June 2022

Graph matching plays an important role in many fields in computer vision. It is a well-known general NP-hard problem and has been investigated for decades. Among the large amount of algorithms for graph matching, the algorithms utilizing the path following strategy exhibited state-of-art performances. However, the main drawback of this category of algorithms lies in their high computational burden. In this paper, we propose a novel path following strategy for graph matching aiming to improve its computation efficiency. We first propose a path estimation method to reduce the computational cost at each iteration, and subsequently a method of adaptive step length to accelerate the convergence. The proposed approach is able to be integrated into all the algorithms that utilize the path following strategy. To validate our approach, we compare our approach with several recently proposed graph matching algorithms on three benchmark image datasets. Experimental results show that, our approach improves significantly the computation efficiency of the original algorithms, and offers similar or better matching results.
Zero-Shot Event Detection by Multimodal Distributional Semantic Embedding of Videos
Authors: Elhoseiny Mohamed , Liu Jingen , Cheng Hui , Sawhney Harpreet , Elgammal Ahmed
Published: June 2022

We propose a new zero-shot Event-Detection method by Multi-modal Distributional Semantic embedding of videos. Our model embeds object and action concepts as well as other available modalities from videos into a distributional semantic space. To our knowledge, this is the first Zero-Shot event detection model that is built on top of distributional semantics and extends it in the following directions: (a) semantic embedding of multimodal information in videos (with focus on the visual modalities), (b) semantic embedding of concepts definitions, and (c) retrieve videos by free text event query (e.g., "changing a vehicle tire") based on their content. We first embed the video into the multi-modal semantic space and then measure the similarity between videos with the event query in free text form. We validated our method on the large TRECVID MED (Multimedia Event Detection) challenge. Using only the event title as a query, our method outperformed the state-the-art that uses big descriptions from 12.6\% to 13.5\% with MAP metric and from 0.73 to 0.83 with ROC-AUC metric. It is also an order of magnitude faster.
A Unifying Variational Inference Framework for Hierarchical Graph-Coupled HMM with an Application to Influenza Infection
Authors: Fan Kai , Li Chunyuan , Heller Katherine
Published: June 2022

The Hierarchical Graph-Coupled Hidden Markov Model (hGCHMM) is a useful tool for tracking and predicting the spread of contagious diseases, such as influenza, by leveraging social contact data collected from individual wearable devices. However, the existing inference algorithms depend on the assumption that the infection rates are small in probability, typically close to 0. The purpose of this paper is to build a unified learning framework for latent infection state estimation for the hGCHMM, regardless of the infection rate and transition function. We derive our algorithm based on a dynamic auto-encoding variational inference scheme, thus potentially generalizing the hGCHMM to models other than those that work on highly contagious diseases. We experimentally compare our approach with previous Gibbs EM algorithms and standard variational method mean-field inference, on both semi-synthetic data and app collected epidemiological and social records.
Spatially Regularized Streaming Sensor Selection
Authors: Li Changsheng , Wei Fan , Dong Weishan , Wang Xiangfeng , Yan Junchi , Zhu Xiaobin , Liu Qingshan , Zhang Xin
Published: June 2022

Sensor selection has become an active topic aimed at energy saving, information overload prevention, and communication cost planning in sensor networks. In many real applications, often the sensors' observation regions have overlaps and thus the sensor network is inherently redundant. Therefore it is important to select proper sensors to avoid data redundancy. This paper focuses on how to incrementally select a subset of sensors in a streaming scenario to minimize information redundancy, and meanwhile meet the power consumption constraint. We propose to perform sensor selection in a multi-variate interpolation framework, such that the data sampled by the selected sensors can well predict those of the inactive sensors. Importantly, we incorporate sensors' spatial information as two regularizers, which leads to significantly better prediction performance. We also define a statistical variable to store sufficient information for incremental learning, and introduce a forgetting factor to track sensor streams' evolvement. Experiments on both synthetic and real datasets validate the effectiveness of the proposed method. Moreover, our method is over 10 times faster than the state-of-the-art sensor selection algorithm.
Preventing Illegal Logging: Simultaneous Optimization of Resource Teams and Tactics for Security
Authors: Mc Carthy Sara Marie , Tambe Milind , Kiekintveld Christopher , Gore Meredith , Killion Alex
Published: June 2022

Green security — protection of forests, fish and wildlife — is a critical problem in environmental sustainability. We focus on the problem  of  optimizing the defense of forests againstillegal logging, where often we are faced with the challenge of teaming up many different groups,  from national police to forest guards to NGOs, each with differing capabilities and costs. This paper introduces a new, yet fundamental problem: SimultaneousOptimization of Resource Teams and Tactics (SORT).  SORT contrasts with most previous game-theoretic research for green security — in particular based onsecurity games — that has solely focused on optimizing patrolling tactics, without consideration of team formation or coordination.  We develop new models and scalable algorithms to apply SORT towards illegal logging in large forest areas. We evaluate our methods on a variety of synthetic examples, as well as a real-world case study using data from our on-going collaboration in Madagascar.
Big-Data Mechanisms and Energy-Policy Design
Authors: Pat Ankit , Larson Kate , Keshav Srinivasen
Published: June 2022

A confluence of technical, economic and political forces are revolutionizing the energy sector. Policy-makers, who decide on incentives and penalties for possible courses of actions, play a critical role in determining which outcomes arise. However, designing appropriate energy policies is a complex and challenging task. Our vision is to provide tools and methodologies for policy makers so that they can leverage the power of big data to make evidence-based decisions. In this paper we present an approach we call big-data mechanism design which combines a mechanism design framework with stakeholder surveys and data to allow policy-makers to gauge the costs and benefits of potential policy decisions.We illustrate the effectiveness of this approach in a concrete application domain: the peaksaver PLUS program in Ontario, Canada.
Bagging Ensembles for the Diagnosis and Prognostication of Alzheimer's Disease
Authors: Dai Peng , Gwadry-Sridhar Femida , Bauer Michael , Borrie Michael
Published: June 2022

Alzheimer's disease (AD) is a chronic neurodegenerative disease, which involves the degeneration of various brain functions, resulting in memory loss, cognitive disorder and death. Large amounts of multivariate heterogeneous medical test data are available for the analysis of brain deterioration. How to measure the deterioration remains a challenging problem. In this study, we first investigate how different regions of the human brain change as the patient develops AD. Correlation analysis and feature ranking are performed based on the feature vectors from different stages of the pathologic process in Alzheimer disease. Then, an automatic diagnosis system is presented, which is based on a hybrid manifold learning for feature embedding and the bootstrap aggregating (Bagging) algorithm for classification.We investigate two different tasks, i.e. diagnosis and progression prediction. Extensive comparison is made against Support Vector Machines (SVM), Random Forest (RF), Decision Tree (DT) and Random Subspace (RS) methods. Experimental results show that our proposed algorithm yields superior results when compared to the other methods, suggesting promising robustness for possible clinical applications.