bluuebunny/crossref_metadata_2025 huggingface dataset:
Two-Stage Facility Location Games with Strategic Clients and Facilities
Authors: Krogmann Simon , Lenzner Pascal , Molitor Louise , Skopalik Alexander
Published: August 2021

We consider non-cooperative facility location games where both facilities and clients act strategically and heavily influence each other. This contrasts established game-theoretic facility location models with non-strategic clients that simply select the closest opened facility. In our model, every facility location has a set of attracted clients and each client has a set of shopping locations and a weight that corresponds to its spending capacity. Facility agents selfishly select a location for opening their facility to maximize the attracted total spending capacity, whereas clients strategically decide how to distribute their spending capacity among the opened facilities in their shopping range. We focus on a natural client behavior similar to classical load balancing: our selfish clients aim for a distribution that minimizes their maximum waiting time for getting serviced, where a facility’s waiting time corresponds to its total attracted client weight.

We show that subgame perfect equilibria exist and we give almost tight constant bounds on the Price of Anarchy and the Price of Stability, which even hold for a broader class of games with arbitrary client behavior. Since facilities and clients influence each other, it is crucial for the facilities to anticipate the selfish clients’ behavior when selecting their location. For this, we provide an efficient algorithm that also implies an efficient check for equilibrium. Finally, we show that computing a socially optimal facility placement is NP-hard and that this result holds for all feasible client weight distributions.
Self-supervised Network Evolution for Few-shot Classification
Authors: Tang Xuwen , Teng Zhu , Zhang Baopeng , Fan Jianping
Published: August 2021

Few-shot classification aims to recognize new classes by learning reliable models from very few available samples. It could be very challenging when there is no intersection between the alreadyknown classes (base set) and the novel set (new classes). To alleviate this problem, we propose to evolve the network (for the base set) via label propagation and self-supervision to shrink the distribution difference between the base set and the novel set. Our network evolution approach transfers the latent distribution from the already-known classes to the unknown (novel) classes by: (a) label propagation of the novel/new classes (novel set); and (b) design of dual-task to exploit a discriminative representation to effectively diminish the overfitting on the base set and enhance the generalization ability on the novel set. We conduct comprehensive experiments to examine our network evolution approach against numerous state-of-the-art ones, especially in a higher way setup and cross-dataset scenarios. Notably, our approach outperforms the second best state-of-the-art method by a large margin of 3.25% for one-shot evaluation over miniImageNet.
Stability and Generalization for Randomized Coordinate Descent
Authors: Wang Puyu , Wu Liang , Lei Yunwen
Published: August 2021

Randomized coordinate descent (RCD) is a popular optimization algorithm with wide applications in various machine learning problems, which motivates a lot of theoretical analysis on its convergence behavior. As a comparison, there is no work studying how the models trained by RCD would generalize to test examples. In this paper, we initialize the generalization analysis of RCD by leveraging the powerful tool of algorithmic stability. We establish argument stability bounds of RCD for both convex and strongly convex objectives, from which we develop optimal generalization bounds by showing how to early-stop the algorithm to tradeoff the estimation and optimization. Our analysis shows that RCD enjoys better stability as compared to stochastic gradient descent.
Unsupervised Path Representation Learning with Curriculum Negative Sampling
Authors: Yang Sean Bin , Guo Chenjuan , Hu Jilin , Tang Jian , Yang Bin
Published: August 2021

Path representations are critical in a variety of transportation applications, such as estimating path ranking in path recommendation systems and estimating path travel time in navigation systems. Existing studies often learn task-specific path representations in a supervised manner, which require a large amount of labeled training data and generalize poorly to other tasks. We propose an unsupervised learning framework Path InfoMax (PIM) to learn generic path representations that work for different downstream tasks. We first propose a curriculum negative sampling method, for each input path, to generate a small amount of negative paths, by following the principles of curriculum learning. Next, PIM employs mutual information maximization to learn path representations from both a global and a local view. In the global view, PIM distinguishes the representations of the input paths from those of the negative paths. In the local view, PIM distinguishes the input path representations from the representations of the nodes that appear only in the negative paths. This enables the learned path representations encode both global and local information at different scales. Extensive experiments on two downstream tasks, ranking score estimation and travel time estimation, using two road network datasets suggest that PIM significantly outperforms other unsupervised methods and is also able to be used as a pre-training method to enhance supervised path representation learning.
BESA: BERT-based Simulated Annealing for Adversarial Text Attacks
Authors: Yang Xinghao , Liu Weifeng , Tao Dacheng , Liu Wei
Published: August 2021

Modern Natural Language Processing (NLP) models are known immensely brittle towards text adversarial examples. Recent attack algorithms usually adopt word-level substitution strategies following a pre-computed word replacement mechanism. However, their resultant adversarial examples are still imperfect in achieving grammar correctness and semantic similarities, which is largely because of their unsuitable candidate word selections and static optimization methods. In this research, we propose BESA, a BERT-based Simulated Annealing algorithm, to address these two problems. Firstly, we leverage the BERT Masked Language Model (MLM) to generate contextual-aware candidate words to produce fluent adversarial text and avoid grammar errors. Secondly, we employ Simulated Annealing (SA) to adaptively determine the word substitution order. The SA provides sufficient word replacement options via internal simulations, with an objective to obtain both a high attack success rate and a low word substitution rate. Besides, our algorithm is able to jump out of local optima with a controlled probability, making it closer to achieve the best possible attack (i.e., the global optima). Experiments on five popular datasets manifest the superiority of BESA compared with existing methods, including TextFooler, BAE, BERT-Attack, PWWS, and PSO.
Understanding the Effect of Bias in Deep Anomaly Detection
Authors: Ye Ziyu , Chen Yuxin , Zheng Haitao
Published: August 2021

Anomaly detection presents a unique challenge in machine learning, due to the scarcity of labeled anomaly data. Recent work attempts to mitigate such problems by augmenting training of deep anomaly detection models with additional labeled anomaly samples. However, the labeled data often does not align with the target distribution and introduces harmful bias to the trained model. In this paper, we aim to understand the effect of a biased anomaly set on anomaly detection. Concretely, we view anomaly detection as a supervised learning task where the objective is to optimize the recall at a given false positive rate. We formally study the relative scoring bias of an anomaly detector, defined as the difference in performance with respect to a baseline anomaly detector. We establish the first finite sample rates for estimating the relative scoring bias for deep anomaly detection, and empirically validate our theoretical results on both synthetic and real-world datasets. We also provide an extensive empirical study on how a biased training anomaly set affects the anomaly score function and therefore the detection performance on different anomaly classes. Our study demonstrates scenarios in which the biased anomaly set can be useful or problematic, and provides a solid benchmark for future research.
Hindsight Trust Region Policy Optimization
Authors: Zhang Hanbo , Bai Site , Lan Xuguang , Hsu David , Zheng Nanning
Published: August 2021

Reinforcement Learning (RL) with sparse rewards is a major challenge. We pro-

pose Hindsight Trust Region Policy Optimization (HTRPO), a new RL algorithm

that extends the highly successful TRPO algorithm with hindsight to tackle the

challenge of sparse rewards. Hindsight refers to the algorithm’s ability to learn

from information across goals, including past goals not intended for the current

task. We derive the hindsight form of TRPO, together with QKL, a quadratic

approximation to the KL divergence constraint on the trust region. QKL reduces

variance in KL divergence estimation and improves stability in policy updates. We

show that HTRPO has similar convergence property as TRPO. We also present

Hindsight Goal Filtering (HGF), which further improves the learning performance

for suitable tasks. HTRPO has been evaluated on various sparse-reward tasks,

including Atari games and simulated robot control. Experimental results show that

HTRPO consistently outperforms TRPO, as well as HPG, a state-of-the-art policy

14 gradient algorithm for RL with sparse rewards.
Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
Authors: Manurangsi Pasin , Suksompong Warut
Published: August 2021

We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the $n$ agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to $\Theta(\sqrt{n})$ goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to $o(\sqrt{n})$ goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.
Sample Efficient Decentralized Stochastic Frank-Wolfe Methods for Continuous DR-Submodular Maximization
Authors: Gao Hongchang , Xu Hanzi , Vucetic Slobodan
Published: August 2021

Continuous DR-submodular maximization is an important machine learning problem, which covers numerous popular applications. With the emergence of large-scale distributed data, developing efficient algorithms for the continuous DR-submodular maximization, such as the decentralized Frank-Wolfe method, became an important challenge. However, existing decentralized Frank-Wolfe methods for this kind of problem have the sample complexity of $\mathcal{O}(1/\epsilon^3)$, incurring a large computational overhead. In this paper, we propose two novel sample efficient decentralized Frank-Wolfe methods to address this challenge. Our theoretical results demonstrate that the sample complexity of the two proposed methods is $\mathcal{O}(1/\epsilon^2)$, which is better than $\mathcal{O}(1/\epsilon^3)$ of the existing methods. As far as we know, this is the first published result achieving such a favorable sample complexity. Extensive experimental results confirm the effectiveness of the proposed methods.
Two-Sided Wasserstein Procrustes Analysis
Authors: Jin Kun , Liu Chaoyue , Xia Cathy
Published: August 2021

Learning correspondence between sets of objects is a key component in many machine learning tasks.Recently, optimal Transport (OT) has been successfully applied to such correspondence problems and it is appealing as a fully unsupervised approach. However, OT requires pairwise instances be directly comparable in a common metric space. This limits its applicability when feature spaces are of different dimensions or not directly comparable. In addition, OT only focuses on pairwise correspondence without sensing global transformations. To address these challenges, we propose a new method to jointly learn the optimal coupling between twosets, and the optimal transformations (e.g. rotation, projection and scaling) of each set based on a two-sided Wassertein Procrustes analysis (TWP). Since the joint problem is a non-convex optimization problem, we present a reformulation that renders the problem component-wise convex. We then propose a novel algorithm to solve the problem harnessing a Gauss–Seidel method. We further present competitive results of TWP on various applicationscompared with state-of-the-art methods.
Adaptive Residue-wise Profile Fusion for Low Homologous Protein Secondary Structure Prediction Using External Knowledge
Authors: Wang Qin , Wei Jun , Wang Boyuan , Li Zhen , Wang Sheng , Cui Shuguang
Published: August 2021

Protein secondary structure prediction (PSSP) is essential for protein function analysis. However, for low homologous proteins, the PSSP suffers from insufficient input features. In this paper, we explicitly import external self-supervised knowledge for low homologous PSSP under the guidance of residue-wise (amino acid wise) profile fusion. In practice, we firstly demonstrate the superiority of profile over Position-Specific Scoring Matrix (PSSM) for low homologous PSSP. Based on this observation, we introduce the novel self-supervised BERT features as the pseudo profile, which implicitly involves the residue distribution in all native discovered sequences as the complementary features. Furthermore, a novel residue-wise attention is specially designed to adaptively fuse different features (i.e., original low-quality profile, BERT based pseudo profile), which not only takes full advantage of each feature but also avoids noise disturbance. Besides, the feature consistency loss is proposed to accelerate the model learning from multiple semantic levels. Extensive experiments confirm that our method outperforms state-of-the-arts (i.e., 4.7% for extremely low homologous cases on BC40 dataset).
Boosting Offline Reinforcement Learning with Residual Generative Modeling
Authors: Wei Hua , Ye Deheng , Liu Zhao , Wu Hao , Yuan Bo , Fu Qiang , Yang Wei , Li Zhenhui
Published: August 2021

Offline reinforcement learning (RL) tries to learn the near-optimal policy with recorded offline experience without online exploration.Current offline RL research includes: 1) generative modeling, i.e., approximating a policy using fixed data; and 2) learning the state-action value function. While most research focuses on the state-action function part through reducing the bootstrapping error in value function approximation induced by the distribution shift of training data, the effects of error propagation in generative modeling have been neglected. In this paper, we analyze the error in generative modeling. We propose AQL (action-conditioned Q-learning), a residual generative model to reduce policy approximation error for offline RL. We show that our method can learn more accurate policy approximations in different benchmark datasets. In addition, we show that the proposed offline RL method can learn more competitive AI agents in complex control tasks under the multiplayer online battle arena (MOBA) game, Honor of Kings.
Predictive Job Scheduling under Uncertain Constraints in Cloud Computing
Authors: Dong Hang , Wang Boshi , Qiao Bo , Xing Wenqian , Luo Chuan , Qin Si , Lin Qingwei , Zhang Dongmei , Virdi Gurpreet , Moscibroda Thomas
Published: August 2021

Capacity management has always been a great challenge for cloud platforms due to massive, heterogeneous on-demand instances running at different times. To better plan the capacity for the whole platform, a class of cloud computing instances have been released to collect computing demands beforehand. To use such instances, users are allowed to submit jobs to run for a pre-specified uninterrupted duration in a flexible range of time in the future with a discount compared to the normal on-demand instances. Proactively scheduling those pre-collected job requests considering the capacity status over the platform can greatly help balance the computing workloads along time. In this work, we formulate the scheduling problem for these pre-collected job requests under uncertain available capacity as a Prediction + Optimization problem with uncertainty in constraints, and propose an effective algorithm called Controlling under Uncertain Constraints (CUC), where the predicted capacity guides the optimization of job scheduling and job scheduling results are leveraged to improve the prediction of capacity through Bayesian optimization. The proposed formulation and solution are commonly applicable for proactively scheduling problems in cloud computing. Our extensive experiments on three public, industrial datasets shows that CUC has great potential for supporting high reliability in cloud platforms.
Fine-tuning Is Not Enough: A Simple yet Effective Watermark Removal Attack for DNN Models
Authors: Guo Shangwei , Zhang Tianwei , Qiu Han , Zeng Yi , Xiang Tao , Liu Yang
Published: August 2021

Watermarking has become the tendency in protecting the intellectual property of DNN models. Recent works, from the adversary's perspective, attempted to subvert watermarking mechanisms by designing watermark removal attacks. However, these attacks mainly adopted sophisticated fine-tuning techniques, which have certain fatal drawbacks or unrealistic assumptions. In this paper, we propose a novel watermark removal attack from a different perspective. Instead of just fine-tuning the watermarked models, we design a simple yet powerful transformation algorithm by combining imperceptible pattern embedding and spatial-level transformations, which can effectively and blindly destroy the memorization of watermarked models to the watermark samples. We also introduce a lightweight fine-tuning strategy to preserve the model performance. Our solution requires much less resource or knowledge about the watermarking scheme than prior works. Extensive experimental results indicate that our attack can bypass state-of-the-art watermarking solutions with very high success rates. Based on our attack, we propose watermark augmentation techniques to enhance the robustness of existing watermarks.
Data-Driven Methods for Balancing Fairness and Efficiency in Ride-Pooling
Authors: Raman Naveen , Shah Sanket , Dickerson John
Published: August 2021

Rideshare and ride-pooling platforms use artificial intelligence-based matching algorithms to pair riders and drivers. However, these platforms can induce unfairness either through an unequal income distribution or disparate treatment of riders. We investigate two methods to reduce forms of inequality in ride-pooling platforms: by incorporating fairness constraints into the objective function and redistributing income to drivers who deserve more. To test these out, we use New York City taxi data to evaluate their performance on both the rider and driver side. For the first method, we find that optimizing for driver fairness out-performs state-of-the-art models in terms of the number of riders serviced, showing that optimizing for fairness can assist profitability in certain circumstances. For the second method, we explore income redistribution as a method to combat income inequality by having drivers keep an $r$ fraction of their income, and contribute the rest to a redistribution pool. For certain values of $r$, most drivers earn near their Shapley value, while still incentivizing drivers to maximize income, thereby avoiding the free-rider problem and reducing income variability. While the first method is useful because it improves both rider and driver-side fairness, the second method is useful because it improves fairness without affecting profitability, and both methods can be combined to improve rider and driver-side fairness.
CSGNN: Contrastive Self-Supervised Graph Neural Network for Molecular Interaction Prediction
Authors: Zhao Chengshuai , Liu Shuai , Huang Feng , Liu Shichao , Zhang Wen
Published: August 2021

Molecular interactions are significant resources for analyzing sophisticated biological systems. Identification of multifarious molecular interactions attracts increasing attention in biomedicine, bioinformatics, and human healthcare communities. Recently, a plethora of methods have been proposed to reveal molecular interactions in one specific domain. However, existing methods heavily rely on features or structures involving molecules, which limits the capacity of transferring the models to other tasks. Therefore, generalized models for the multifarious molecular interaction prediction (MIP) are in demand. In this paper, we propose a contrastive self-supervised graph neural network (CSGNN) to predict molecular interactions. CSGNN injects a mix-hop neighborhood aggregator into a graph neural network (GNN) to capture high-order dependency in the molecular interaction networks and leverages a contrastive self-supervised learning task as a regularizer within a multi-task learning paradigm to enhance the generalization ability. Experiments on seven molecular interaction networks show that CSGNN outperforms classic and state-of-the-art models. Comprehensive experiments indicate that the mix-hop aggregator and the self-supervised regularizer can effectively facilitate the link inference in multifarious molecular networks.
Automatically Paraphrasing via Sentence Reconstruction and Round-trip Translation
Authors: Guo Zilu , Huang Zhongqiang , Zhu Kenny Q. , Chen Guandan , Zhang Kaibo , Chen Boxing , Huang Fei
Published: August 2021

Paraphrase generation plays key roles in NLP tasks such as question answering, machine translation, and information retrieval. In this paper, we propose a novel framework for paraphrase generation. It simultaneously decodes the output sentence using a pretrained wordset-to-sequence model and a round-trip translation model. We evaluate this framework on Quora, WikiAnswers, MSCOCO and Twitter, and show its advantage over previous state-of-the-art unsupervised methods and distantly-supervised methods by significant margins on all datasets. For Quora and WikiAnswers, our framework even performs better than some strongly supervised methods with domain adaptation. Further, we show that the generated paraphrases can be used to augment the training data for machine translation to achieve substantial improvements.
Multi-Hop Fact Checking of Political Claims
Authors: Ostrowski Wojciech , Arora Arnav , Atanasova Pepa , Augenstein Isabelle
Published: August 2021

Recent work has proposed multi-hop models and datasets for studying complex natural language reasoning. One notable task requiring multi-hop reasoning is fact checking, where a set of connected evidence pieces leads to the final verdict of a claim. However, existing datasets either do not provide annotations for gold evidence pages, or the only dataset which does (FEVER) mostly consists of claims which can be fact-checked with simple reasoning and is constructed artificially. Here, we study more complex claim verification of naturally occurring claims with multiple hops over interconnected evidence chunks. We: 1) construct a small annotated dataset, PolitiHop, of evidence sentences for claim verification; 2) compare it to existing multi-hop datasets; and 3) study how to transfer knowledge from more extensive in- and out-of-domain resources to PolitiHop. We find that the task is complex and achieve the best performance with an architecture that specifically models reasoning over evidence pieces in combination with in-domain transfer learning.
MultiMirror: Neural Cross-lingual Word Alignment for Multilingual Word Sense Disambiguation
Authors: Procopio Luigi , Barba Edoardo , Martelli Federico , Navigli Roberto
Published: August 2021

Word Sense Disambiguation (WSD), i.e., the task of assigning senses to words in context, has seen a surge of interest with the advent of neural models and a considerable increase in performance up to 80% F1 in English. However, when considering other languages, the availability of training data is limited, which hampers scaling WSD to many languages. To address this issue, we put forward MultiMirror, a sense projection approach for multilingual WSD based on a novel neural discriminative model for word alignment: given as input a pair of parallel sentences, our model -- trained with a low number of instances -- is capable of jointly aligning, at the same time, all source and target tokens with each other, surpassing its competitors across several language combinations. We demonstrate that projecting senses from English by leveraging the alignments produced by our model leads a simple mBERT-powered classifier to achieve a new state of the art on established WSD datasets in French, German, Italian, Spanish and Japanese. We release our software and all our datasets at https://github.com/SapienzaNLP/multimirror.
Learning Class-Transductive Intent Representations for Zero-shot Intent Detection
Authors: Si Qingyi , Liu Yuanxin , Fu Peng , Lin Zheng , Li Jiangnan , Wang Weiping
Published: August 2021

Zero-shot intent detection (ZSID) aims to deal with the continuously emerging intents without annotated training data. However, existing ZSID systems suffer from two limitations: 1) They are not good at modeling the relationship between seen and unseen intents. 2) They cannot effectively recognize unseen intents under the generalized intent detection (GZSID) setting. A critical problem behind these limitations is that the representations of unseen intents cannot be learned in the training stage. To address this problem, we propose a novel framework that utilizes unseen class labels to learn Class-Transductive Intent Representations (CTIR). Specifically, we allow the model to predict unseen intents during training, with the corresponding label names serving as input utterances. On this basis, we introduce a multi-task learning objective, which encourages the model to learn the distinctions among intents, and a similarity scorer, which estimates the connections among intents more accurately. CTIR is easy to implement and can be integrated with existing ZSID and GZSID methods. Experiments on two real-world datasets show that CTIR brings considerable improvement to the baseline systems.
Document-level Relation Extraction as Semantic Segmentation
Authors: Zhang Ningyu , Chen Xiang , Xie Xin , Deng Shumin , Tan Chuanqi , Chen Mosha , Huang Fei , Si Luo , Chen Huajun
Published: August 2021

Document-level relation extraction aims to extract relations among multiple entity pairs from a document. Previously proposed graph-based or transformer-based models utilize the entities independently, regardless of global information among relational triples. This paper approaches the problem by predicting an entity-level relation matrix to capture local and global information, parallel to the semantic segmentation task in computer vision. Herein, we propose a Document U-shaped Network for document-level relation extraction. Specifically, we leverage an encoder module to capture the context information of entities and a U-shaped segmentation module over the image-style feature map to capture global interdependency among triples. Experimental results show that our approach can obtain state-of-the-art performance on three benchmark datasets DocRED, CDR, and GDA.
Drop Redundant, Shrink Irrelevant: Selective Knowledge Injection for Language Pretraining
Authors: Zhang Ningyu , Deng Shumin , Cheng Xu , Chen Xi , Zhang Yichi , Zhang Wei , Chen Huajun
Published: August 2021

Previous research has demonstrated the power of leveraging prior knowledge to improve the performance of deep models in natural language processing. However, traditional methods neglect the fact that redundant and irrelevant knowledge exists in external knowledge bases. In this study, we launched an in-depth empirical investigation into downstream tasks and found that knowledge-enhanced approaches do not always exhibit satisfactory improvements. To this end, we investigate the fundamental reasons for ineffective knowledge infusion and present selective injection for language pretraining, which constitutes a model-agnostic method and is readily pluggable into previous approaches. Experimental results on benchmark datasets demonstrate that our approach can enhance state-of-the-art knowledge injection methods.
Online Learning of Action Models for PDDL Planning
Authors: Lamanna Leonardo , Saetti Alessandro , Serafini Luciano , Gerevini Alfonso , Traverso Paolo
Published: August 2021

The automated learning of action models is widely recognised as a key and compelling challenge to address the difficulties of the manual specification of planning domains. Most state-of-the-art methods perform this learning offline from an input set of plan traces generated by the execution of (successful) plans. However, how to generate informative plan traces for learning action models is still an open issue. Moreover, plan traces might not be available for a new environment. In this paper, we propose an algorithm for learning action models online, incrementally during the execution of plans. Such plans are generated to achieve goals that the algorithm decides online in order to obtain informative plan traces and reach states from which useful information can be learned. We show some fundamental theoretical properties of the algorithm, and we experimentally evaluate the online learning of the action models over a large set of IPC domains.
Game-theoretic Analysis of Effort Allocation of Contributors to Public Projects
Authors: Soundy Jared , Wang Chenhao , Stevens Clay , Chan Hau
Published: August 2021

Public projects can succeed or fail for many reasons such as the feasibility of the original goal and coordination among contributors. One major reason for failure is that insufficient work leaves the project partially completed. For certain types of projects anything short of full completion is a failure (e.g., feature request on software projects in GitHub). Therefore, project success relies heavily on individuals allocating sufficient effort. When there are multiple public projects, each contributor needs to make decisions to best allocate his/her limited effort (e.g., time) to projects while considering the effort allocation decisions of other strategic contributors and his/her parameterized utilities based on values and costs for the projects. In this paper, we introduce a game-theoretic effort allocation model of contributors to public projects for modeling effort allocation of strategic contributors. We study the related Nash equilibrium (NE) computational problems and provide NP-hardness results for the existence of NE and polynomial-time algorithms for finding NE in restricted settings. Finally, we investigate the inefficiency of NE measured by the price of anarchy and price of stability.
Synthesizing Good-Enough Strategies for LTLf Specifications
Authors: Li Yong , Turrini Andrea , Vardi Moshe Y. , Zhang Lijun
Published: August 2021

We consider the problem of synthesizing good-enough (GE)-strategies for linear temporal logic (LTL) over finite traces or LTLf for short.

The problem of synthesizing GE-strategies for an LTL formula φ over infinite traces reduces to the problem of synthesizing winning strategies for the formula (∃Oφ)⇒φ where O is the set of propositions controlled by the system.

We first prove that this reduction does not work for LTLf formulas.

Then we show how to synthesize GE-strategies for LTLf formulas via the Good-Enough (GE)-synthesis of LTL formulas.

Unfortunately, this requires to construct deterministic parity automata on infinite words, which is computationally expensive.

We then show how to synthesize GE-strategies for LTLf formulas by a reduction to solving games played on deterministic Büchi automata, based on an easier construction of deterministic automata on finite words.

We show empirically that our specialized synthesis algorithm for GE-strategies outperforms the algorithms going through GE-synthesis of LTL formulas by orders of magnitude.
Learning Temporal Plan Preferences from Examples: An Empirical Study
Authors: Seimetz Valentin , Eifler Rebecca , Hoffmann Jörg
Published: August 2021

Temporal plan preferences are natural and important in a variety of applications. Yet users often find it difficult to formalize their preferences. Here we explore the possibility to learn preferences from example plans. Focusing on one preference at a time, the user is asked to annotate examples as good/bad. We leverage prior work on LTL formula learning to extract a preference from these examples. We conduct an empirical study of this approach in an oversubscription planning context, using hidden target formulas to emulate the user preferences. We explore four different methods for generating example plans, and evaluate performance as a function of domain and formula size. Overall, we find that reasonable-size target formulas can often be learned effectively.
Handling Overlaps When Lifting Gaussian Bayesian Networks
Authors: Hartwig Mattis , Braun Tanya , Möller Ralf
Published: August 2021

Gaussian Bayesian networks are widely used for modeling the behavior of continuous random variables. Lifting exploits symmetries when dealing with large numbers of isomorphic random variables. It provides a more compact representation for more efficient query answering by encoding the symmetries using logical variables. This paper improves on an existing lifted representation of the joint distribution represented by a Gaussian Bayesian network (lifted joint), allowing overlaps between the logical variables. Handling overlaps without grounding a model is critical for modelling real-world scenarios.

Specifically, this paper contributes (i) a lifted joint that allows overlaps in logical variables and (ii) a lifted query answering algorithm using the lifted joint. Complexity analyses and experimental results show that - despite overlaps - constructing a lifted joint and answering queries on the lifted joint outperform their grounded counterparts significantly.
Combining Fairness and Optimality when Selecting and Allocating Projects
Authors: Belahcène Khaled , Mousseau Vincent , Wilczynski Anaëlle
Published: August 2021

We consider the problem of the conjoint selection and allocation of projects to a population of agents, e.g. students are assigned papers and shall present them to their peers. The selection can be constrained either by quotas over subcategories of projects, or by the preferences of the agents themselves. We explore fairness and optimality issues and refine the analysis of the rank-maximality and popularity optimality concepts. We show that they are compatible with reasonable fairness requirements related to rank-based envy-freeness and can be adapted to select globally good projects according to the preferences of the agents.
Reducing Bus Bunching with Asynchronous Multi-Agent Reinforcement Learning
Authors: Wang Jiawei , Sun Lijun
Published: August 2021

The bus system is a critical component of sustainable urban transportation. However, due to the significant uncertainties in passenger demand and traffic conditions, bus operation is unstable in nature and bus bunching has become a common phenomenon that undermines the reliability and efficiency of bus services. Despite recent advances in multi-agent reinforcement learning (MARL) on traffic control, little research has focused on bus fleet control due to the tricky asynchronous characteristic---control actions only happen when a bus arrives at a bus stop and thus agents do not act simultaneously. In this study, we formulate route-level bus fleet control as an asynchronous multi-agent reinforcement learning (ASMR) problem and extend the classical actor-critic architecture to handle the asynchronous issue. Specifically, we design a novel critic network to effectively approximate the marginal contribution for other agents, in which graph attention neural network is used to conduct inductive learning for policy evaluation. The critic structure also helps the ego agent optimize its policy more efficiently. We evaluate the proposed framework on real-world bus services and actual passenger demand derived from smart card data. Our results show that the proposed model outperforms both traditional headway-based control methods and existing MARL methods.
Argumentative XAI: A Survey
Authors: Čyras Kristijonas , Rago Antonio , Albini Emanuele , Baroni Pietro , Toni Francesca
Published: August 2021

Explainable AI (XAI) has been investigated for decades and, together with AI itself, has witnessed unprecedented growth in recent years. Among various approaches to XAI, argumentative models have been advocated in both the AI and social science literature, as their dialectical nature appears to match some basic desirable features of the explanation activity. In this survey we overview XAI approaches built using methods from the field of computational argumentation, leveraging its wide array of reasoning abstractions and explanation delivery methods. We overview the literature focusing on different types of explanation (intrinsic and post-hoc), different models with which argumentation-based explanations are deployed, different forms of delivery, and different argumentation frameworks they use. We also lay out a roadmap for future work.
If Only We Had Better Counterfactual Explanations: Five Key Deficits to Rectify in the Evaluation of Counterfactual XAI Techniques
Authors: Keane Mark T. , Kenny Eoin M. , Delaney Eoin , Smyth Barry
Published: August 2021

In recent years, there has been an explosion of AI research on counterfactual explanations as a solution to the problem of eXplainable AI (XAI). These explanations seem to offer technical, psychological and legal benefits over other explanation techniques. We survey 100 distinct counterfactual explanation methods reported in the literature. This survey addresses the extent to which these methods have been adequately evaluated, both psychologically and computationally, and quantifies the shortfalls occurring. For instance, only 21% of these methods have been user tested. Five key deficits in the evaluation of these methods are detailed and a roadmap, with standardised benchmark evaluations, is proposed to resolve the issues arising; issues, that currently effectively block scientific progress in this field.
Person Search Challenges and Solutions: A Survey
Authors: Lin Xiangtan , Ren Pengzhen , Xiao Yun , Chang Xiaojun , Hauptmann Alex
Published: August 2021

Person search has drawn increasing attention due to its real-world applications and research significance. Person search aims to find a probe person in a gallery of scene images with a wide range of applications, such as criminals search, multicamera tracking, missing person search, etc. Early person search works focused on image-based person search, which uses person image as the search query. Text-based person search is another major person search category that uses free-form natural language as the search query. Person search is challenging, and corresponding solutions are diverse and complex. Therefore, systematic surveys on this topic are essential. This paper surveyed the recent works on image-based and text-based person search from the perspective of challenges and solutions. Specifically, we provide a brief analysis of highly influential person search methods considering the three significant challenges: the discriminative person features, the query-person gap, and the detection-identification inconsistency. We summarise and compare evaluation results. Finally, we discuss open issues and some promising future research directions.
State-Aware Value Function Approximation with Attention Mechanism for Restless Multi-armed Bandits
Authors: Wu Shuang , Zhao Jingyu , Tian Guangjian , Wang Jun
Published: August 2021

The restless multi-armed bandit (RMAB) problem is a generalization of the multi-armed bandit with non-stationary rewards. Its optimal solution is intractable due to exponentially large state and action spaces with respect to the number of arms. Existing approximation approaches, e.g., Whittle's index policy, have difficulty in capturing either temporal or spatial factors such as impacts from other arms. We propose considering both factors using the attention mechanism, which has achieved great success in deep learning. Our state-aware value function approximation solution comprises an attention-based value function approximator and a Bellman equation solver. The attention-based coordination module capture both spatial and temporal factors for arm coordination. The Bellman equation solver utilizes the decoupling structure of RMABs to acquire solutions with significantly reduced computation overheads. In particular, the time complexity of our approximation is linear in the number of arms. Finally, we illustrate the effectiveness and investigate the properties of our proposed method with numerical experiments.
Defining the Semantics of Abstract Argumentation Frameworks through Logic Programs and Partial Stable Models (Extended Abstract)
Authors: Alfano Gianvincenzo , Greco Sergio , Parisi Francesco , Trubitsyna Irina
Published: August 2021

Extensions of Dung’s Argumentation Framework (AF) include the class of Recursive Bipolar AFs (Rec-BAFs), i.e. AFs with recursive attacks and supports. We show that a Rec-BAF \Delta can be translated into a logic program P_\Delta so that the extensions of \Delta under different semantics coincide with subsets of the partial stable models of P_\Delta.
Weaving a Semantic Web of Credibility Reviews for Explainable Misinformation Detection (Extended Abstract)
Authors: Denaux Ronald , Mensio Martino , Gomez-Perez Jose Manuel , Alani Harith
Published: August 2021

This paper summarises work where we combined semantic web technologies with deep learning systems to obtain state-of-the art explainable misinformation detection. We proposed a conceptual and computational model to describe a wide range of misinformation detection systems based around the concepts of credibility and reviews. We described how Credibility Reviews (CRs) can be used to build networks of distributed bots that collaborate for misinformation detection which we evaluated by building a prototype based on publicly available datasets and deep learning models.
Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)
Authors: Grange Julien
Published: August 2021

We study the expressive power of successor-invariant first-order logic, which is an extension of first-order logic where the usage of a successor relation on the vertices of the graph is allowed, as long as the validity of formulas is independent on the choice of a particular successor.

We show that when the degree is bounded, successor-invariant first-order logic is no more expressive than first-order logic.
Budget-feasible Maximum Nash Social Welfare is Almost Envy-free
Authors: Wu Xiaowei , Li Bo , Gan Jiarui
Published: August 2021

The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.
On Sampled Metrics for Item Recommendation (Extended Abstract)
Authors: Krichene Walid , Rendle Steffen
Published: August 2021

Recommender systems personalize content by recommending items to users. Item recommendation algorithms are evaluated by metrics that compare the positions of truly relevant items among the recommended items. To speed up the computation of metrics, recent work often uses sampled metrics where only a smaller set of random items and the relevant items are ranked. This paper investigates such sampled metrics and shows that they are inconsistent with their exact counterpart, in the sense that they do not persist relative statements, e.g., recommender A is better than B, not even in expectation. We show that it is possible to improve the quality of the sampled metrics by applying a correction. We conclude with an empirical evaluation of the naive sampled metrics and their corrected variants. Our work suggests that sampling should be avoided for metric calculation, however if an experimental study needs to sample, the proposed corrections can improve the estimates.
Finding the Hardest Formulas for Resolution (Extended Abstract)
Authors: Peitl Tomáš , Szeider Stefan
Published: August 2021

A CNF formula is harder than another CNF formula with the same

number of clauses if it requires a longer resolution proof. We introduce

resolution hardness numbers; they give for m=1,2,... the length

of a shortest proof of a hardest formula on m clauses. We compute

the first ten resolution hardness numbers, along with the

corresponding hardest formulas.

To achieve this, we devise a candidate filtering and symmetry breaking

search scheme for limiting the number of potential candidates for hardest

formulas, and an efficient SAT encoding for computing a shortest

resolution proof of a given candidate formula.
Exploring the Effects of Goal Setting When Training for Complex Crowdsourcing Tasks (Extended Abstract)
Authors: Rechkemmer Amy , Yin Ming
Published: August 2021

Training is one way of enabling novice workers to work on complex crowdsourcing tasks. Based on goal setting theory in psychology, we conduct a randomized experiment to study whether and how setting different goals---including performance goal, learning goal, and behavioral goal---when training workers for a complex crowdsourcing task affects workers' learning perception, learning gain, and post-training performance. We find that setting different goals during training significantly affects workers' learning perception, but does not have an effect on learning gain or post-training performance. Further, exploratory analysis helps shed light on when and why various goals may or may not work in the crowdsourcing context.
Deep Residual Reinforcement Learning (Extended Abstract)
Authors: Zhang Shangtong , Boehmer Wendelin , Whiteson Shimon
Published: August 2021

We revisit residual algorithms in both model-free and model-based reinforcement learning settings.

We propose the bidirectional target network technique to stabilize residual algorithms, yielding a residual version of DDPG that significantly outperforms vanilla DDPG in commonly used benchmarks.

Moreover, we find the residual algorithm an effective approach to the distribution mismatch problem in model-based planning.

Compared with the existing TD(k) method, our residual-based method makes weaker assumptions about the model and yields a greater performance boost.
Greybox Algorithm Configuration
Authors: Anastacio Marie
Published: August 2021

The performance of state-of-the-art algorithms is highly dependent on their parameter values, and choosing the right configuration can make the difference between solving a problem in a few minutes or hours. Automated algorithm configurators have shown their efficiency on a wide range of applications. However, they still encounter limitations when confronted to a large number of parameters to tune or long algorithm running time.

We believe that there is untapped knowledge that can be gathered from the elements of the configuration problem, such as the default value in the configuration space, the source code of the algorithm, and the distribution of the problem instances at hand. We aim at utilising this knowledge to improve algorithm configurators.