bluuebunny/crossref_metadata_2025 huggingface dataset:
Cross-Domain Slot Filling as Machine Reading Comprehension
Authors: Yu Mengshi , Liu Jian , Chen Yufeng , Xu Jinan , Zhang Yujie
Published: August 2021

With task-oriented dialogue systems being widely applied in everyday life, slot filling, the essential component of task-oriented dialogue systems, is required to be quickly adapted to new domains that contain domain-specific slots with few or no training data. Previous methods for slot filling usually adopt sequence labeling framework, which, however, often has limited ability when dealing with the domain-specific slots. In this paper, we take a new perspective on cross-domain slot filling by framing it as a machine reading comprehension (MRC) problem. Our approach firstly transforms slot names into well-designed queries, which contain rich informative prior knowledge and are very helpful for the detection of domain-specific slots. In addition, we utilize the large-scale MRC dataset for pre-training, which further alleviates the data scarcity problem. Experimental results on SNIPS and ATIS datasets show that our approach consistently outperforms the existing state-of-the-art methods by a large margin.
Relational Gating for ''What If'' Reasoning
Authors: Zheng Chen , Kordjamshidi Parisa
Published: August 2021

This paper addresses the challenge of learning to do procedural reasoning over text to answer "What if..." questions. We propose a novel relational gating network that learns to filter the key entities and relationships and learns contextual and cross representations of both procedure and question for finding the answer. Our relational gating network contains an entity gating module, relation gating module, and contextual interaction module. These modules help in solving the "What if..." reasoning problem. We show that modeling pairwise relationships helps to capture higher-order relations and find the line of reasoning for causes and effects in the procedural descriptions. Our proposed approach achieves the state-of-the-art results on the WIQA dataset.
Efficient Black-Box Planning Using Macro-Actions with Focused Effects
Authors: Allen Cameron , Katz Michael , Klinger Tim , Konidaris George , Riemer Matthew , Tesauro Gerald
Published: August 2021

The difficulty of deterministic planning increases exponentially with search-tree depth. Black-box planning presents an even greater challenge, since planners must operate without an explicit model of the domain. Heuristics can make search more efficient, but goal-aware heuristics for black-box planning usually rely on goal counting, which is often quite uninformative. In this work, we show how to overcome this limitation by discovering macro-actions that make the goal-count heuristic more accurate. Our approach searches for macro-actions with focused effects (i.e. macros that modify only a small number of state variables), which align well with the assumptions made by the goal-count heuristic. Focused macros dramatically improve black-box planning efficiency across a wide range of planning domains, sometimes beating even state-of-the-art planners with access to a full domain model.
Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare
Authors: Biswas Arpita , Aggarwal Gaurav , Varakantham Pradeep , Tambe Milind
Published: August 2021

In many public health settings, it is important for patients to adhere to health programs, such as taking medications and periodic health checks. Unfortunately, beneficiaries may gradually disengage from such programs, which is detrimental to their health. A concrete example of gradual disengagement has been observed by an organization that carries out a free automated call-based program for spreading preventive care information among pregnant women. Many women stop picking up calls after being enrolled for a few months. To avoid such disengagements, it is important to provide timely interventions. Such interventions are often expensive and can be provided to only a small fraction of the beneficiaries. We model this scenario as a restless multi-armed bandit (RMAB) problem, where each beneficiary is assumed to transition from one state to another depending on the intervention. Moreover, since the transition probabilities are unknown a priori, we propose a Whittle index based Q-Learning mechanism and show that it converges to the optimal solution. Our method improves over existing learning-based methods for RMABs on multiple benchmarks from literature and also on the maternal healthcare dataset.
Type-WA*: Using Exploration in Bounded Suboptimal Planning
Authors: Cohen Eldan , Valenzano Richard , McIlraith Sheila
Published: August 2021

Previous work on satisficing planning using greedy best-first search (GBFS) has shown that non-greedy, randomized exploration can help escape uninformative heuristic regions and solve hard problems faster. Despite their success when used with GBFS, such exploration techniques cannot be directly applied to bounded suboptimal algorithms like Weighted A* (WA*) without losing the solution-quality guarantees. In this work, we present Type-WA*, a novel bounded suboptimal planning algorithm that augments WA* with type-based exploration while still satisfying WA*'s theoretical solution-quality guarantee. Our empirical analysis shows that Type-WA* significantly increases the number of solved problems, when used in conjunction with each of three popular heuristics. Our analysis also provides insight into the runtime vs. solution cost trade-off.
Custom-Design of FDR Encodings: The Case of Red-Black Planning
Authors: Fišer Daniel , Gnad Daniel , Katz Michael , Hoffmann Jörg
Published: August 2021

Classical planning tasks are commonly described in PDDL, while most planning systems operate on a grounded finite-domain representation (FDR). The translation of PDDL into FDR is complex and has a lot of choice points---it involves identifying so called mutex groups---but most systems rely on the translator that comes with Fast Downward. Yet the translation choice points can strongly impact performance. Prior work has considered optimizing FDR encodings in terms of the number of variables produced. Here we go one step further by proposing to custom-design FDR encodings, optimizing the encoding to suit particular planning techniques. We develop such a custom design here for red-black planning, a partial delete relaxation technique. The FDR encoding affects the causal graph and the domain transition graph structures, which govern the tractable fragment of red-black planning and hence affects the respective heuristic function. We develop integer linear programming techniques optimizing the scope of that fragment in the resulting FDR encoding. We empirically show that the performance of red-black planning can be improved through such FDR custom design.
Interference-free Walks in Time: Temporally Disjoint Paths
Authors: Klobas Nina , Mertzios George B. , Molter Hendrik , Niedermeier Rolf , Zschoche Philipp
Published: August 2021

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never use the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks.

On the one extreme, we show that on general graphs the problem is computationally hard. The "walk version" is W[1]-hard when parameterized by the number of routes. However, it is polynomial-time solvable for any constant number of walks. The "path version" remains NP-hard even if we want to find only two temporally disjoint paths. On the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counterintuitively, we find NP-hardness in general but also identify natural tractable cases.
Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models
Authors: Lin Songtuan , Bercher Pascal
Published: August 2021

Incorporating humans into AI planning is an important feature of flexible planning technology. Such human integration allows to incorporate previously unknown constraints, and is also an integral part of automated modeling assistance. As a foundation for integrating user requests, we study the computational complexity of determining the existence of changes to an existing model, such that the resulting model allows for specific user-provided solutions. We are provided with a planning problem modeled either in the classical (non-hierarchical) or hierarchical task network (HTN) planning formalism, as well as with a supposed-to-be solution plan, which is actually not a solution for the current model. Considering changing decomposition methods as well as preconditions and effects of actions, we show that most change requests are NP-complete though some turn out to be tractable.
On Weak Stubborn Sets in Classical Planning
Authors: Sievers Silvan , Wehrle Martin
Published: August 2021

Stubborn sets are a pruning technique for state-space search which is well established in optimal classical planning. In this paper, we show that weak stubborn sets introduced in recent work in planning are actually not weak stubborn sets in Valmari's original sense. Based on this finding, we introduce weak stubborn sets in the original sense for planning by providing a generalized definition analogously to generalized strong stubborn sets in previous work. We discuss the relationship of strong, weak and the previously called weak stubborn sets, thus providing a further step in getting an overall picture of the stubborn set approach in planning.
Learning Generalized Unsolvability Heuristics for Classical Planning
Authors: Ståhlberg Simon , Francès Guillem , Seipp Jendrik
Published: August 2021

Recent work in classical planning has introduced dedicated techniques for detecting unsolvable states, i.e., states from which no goal state can be reached. We approach the problem from a generalized planning perspective and learn first-order-like formulas that characterize unsolvability for entire planning domains. We show how to cast the problem as a self-supervised classification task. Our training data is automatically generated and labeled by exhaustive exploration of small instances of each domain, and candidate features are automatically computed from the predicates used to define the domain. We investigate three learning algorithms with different properties and compare them to heuristics from the literature. Our empirical results show that our approach often captures important classes of unsolvable states with high classification accuracy. Additionally, the logical form of our heuristics makes them easy to interpret and reason about, and can be used to show that the characterizations learned in some domains capture exactly all unsolvable states of the domain.
TANGO: Commonsense Generalization in Predicting Tool Interactions for Mobile Manipulators
Authors: Tuli Shreshth , Bansal Rajas , Paul Rohan , . Mausam
Published: August 2021

Robots assisting us in factories or homes must learn to make use of objects as tools to perform tasks, e.g., a tray for carrying objects. We consider the problem of learning commonsense knowledge of when a tool may be useful and how its use may be composed with other tools to accomplish a high-level task instructed by a human. We introduce TANGO, a novel neural model for predicting task-specific tool interactions. TANGO is trained using demonstrations obtained from human teachers instructing a virtual robot in a physics simulator. TANGO encodes the world state consisting of objects and symbolic relationships between them using a graph neural network. The model learns to attend over the scene using knowledge of the goal and the action history, finally decoding the symbolic action to execute. Crucially, we address generalization to unseen environments where some known tools are missing, but alternative unseen tools are present. We show that by augmenting the representation of the environment with pre-trained embeddings derived from a knowledge-base, the model can generalize effectively to novel environments. Experimental results show a 60.5-78.9% improvement over the baseline in predicting successful symbolic plans in unseen settings for a simulated mobile manipulator.
The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound
Authors: Zhao Jingyang , Xiao Mingyu
Published: August 2021

The Traveling Tournament Problem is a well-known benchmark problem in tournament timetabling, which asks us to design a schedule of home/away games of n teams (n is even) under some feasibility requirements such that the total traveling distance of all the n teams is minimized. In this paper, we study TTP-2, the traveling tournament problem where at most two consecutive home games or away games are allowed, and give an effective algorithm for n/2 being odd. Experiments on the well-known benchmark sets show that we can beat previously known solutions for all instances with n/2 being odd by an average improvement of 2.66%. Furthermore, we improve the theoretical approximation ratio from 3/2+O(1/n) to 1+O(1/n) for n/2 being odd, answering a challenging open problem in this area.
Non-Parametric Stochastic Sequential Assignment With Random Arrival Times
Authors: Dervovic Danial , Hassanzadeh Parisa , Assefa Samuel , Reddy Prashant
Published: August 2021

We consider a problem wherein jobs arrive at random times and assume random values. Upon each job arrival, the decision-maker must decide immediately whether or not to accept the job and gain the value on offer as a reward, with the constraint that they may only accept at most n jobs over some reference time period. The decision-maker only has access to M independent realisations of the job arrival process. We propose an algorithm, Non-Parametric Sequential Allocation (NPSA), for solving this problem. Moreover, we prove that the expected reward returned by the NPSA algorithm converges in probability to optimality as M grows large. We demonstrate the effectiveness of the algorithm empirically on synthetic data and on public fraud-detection datasets, from where the motivation for this work is derived.
New Algorithms for Japanese Residency Matching
Authors: Sun Zhaohong , Todo Taiki , Yokoo Makoto
Published: August 2021

We study the Japanese Residency Matching Program (JRMP) in which hospitals are partitioned into disjoint regions and both hospitals and regions are subject to quotas. To achieve a balanced distribution of doctors across regions, hard bounds are imposed by the government to limit the number of

doctors who can be placed in each region. However, such hard bounds lead to inefficiency in terms of wasted vacant positions. In this paper, we propose

two suitable algorithms to reduce waste with minimal modification to the current system and show that they are superior to the algorithm currently

deployed in JRMP by comparing them theoretically and empirically.
Deep Bucket Elimination
Authors: Razeghi Yasaman , Kask Kalev , Lu Yadong , Baldi Pierre , Agarwal Sakshi , Dechter Rina
Published: August 2021

Bucket Elimination (BE) is a universal inference scheme that can solve most tasks over probabilistic and deterministic graphical models exactly.

However, it often requires exponentially high levels of memory (in the induced-width) preventing its execution. In the spirit of exploiting Deep Learning for inference tasks, in this paper, we will use neural networks to approximate BE.

The resulting Deep Bucket Elimination (DBE) algorithm is developed for computing the partition function.

We provide a proof-of-concept empirically using instances from several different benchmarks, showing that DBE can be a more accurate approximation than current state-of-the-art approaches for approximating BE (e.g. the mini-bucket schemes), especially when problems are sufficiently hard.
BKT-POMDP: Fast Action Selection for User Skill Modelling over Tasks with Multiple Skills
Authors: Salomons Nicole , Akdere Emir , Scassellati Brian
Published: August 2021

Creating an accurate model of a user's skills is necessary for intelligent tutoring systems. Without an accurate model, sample problems or tasks must be selected haphazardly by the tutor. Once an accurate model has been trained, the tutor can selectively focus on training essential or deficient skills. Prior work offers mechanisms for optimizing the training of a single skill or for multiple skills when individual tasks involve testing only a single skill at a time, but not for multiple skills when individual tasks can contain evidence for multiple skills. In this paper, we present a system that estimates user skill models for multiple skills by selecting tasks which maximize the information gain across the entire skill model. We compare our system's policy against several baselines and an optimal policy in both simulated and real tasks. Our system outperforms baselines and performs almost on par with the optimal policy.
Provable Guarantees on the Robustness of Decision Rules to Causal Interventions
Authors: Wang Benjie , Lyle Clare , Kwiatkowska Marta
Published: August 2021

Robustness of decision rules to shifts in the data-generating process is crucial to the successful deployment of decision-making systems. Such shifts can be viewed as interventions on a causal graph, which capture (possibly hypothetical) changes in the data-generating process, whether due to natural reasons or by the action of an adversary. We consider causal Bayesian networks and formally define the interventional robustness problem, a novel model-based notion of robustness for decision functions that measures worst-case performance with respect to a set of interventions that denote changes to parameters and/or causal influences. By relying on a tractable representation of Bayesian networks as arithmetic circuits, we provide efficient algorithms for computing guaranteed upper and lower bounds on the interventional robustness probabilities. Experimental results demonstrate that the methods yield useful and interpretable bounds for a range of practical networks, paving the way towards provably causally robust decision-making systems.
Fast Algorithms for Relational Marginal Polytopes
Authors: Wang Yuanhong , van Bremen Timothy , Pu Juhua , Wang Yuyi , Kuzelka Ondrej
Published: August 2021

We study the problem of constructing the relational marginal polytope (RMP) of a given set of first-order formulas. Past work has shown that the RMP construction problem can be reduced to weighted first-order model counting (WFOMC). However, existing reductions in the literature are intractable in practice, since they typically require an infeasibly large number of calls to a WFOMC oracle. In this paper, we propose an algorithm to construct RMPs using fewer oracle calls. As an application, we also show how to apply this new algorithm to improve an existing approximation scheme for WFOMC. We demonstrate the efficiency of the proposed approaches experimentally, and find that our method provides speed-ups over the baseline for RMP construction of a full order of magnitude.
A Survey of Machine Learning-Based Physics Event Generation
Authors: Alanazi Yasir , Sato Nobuo , Ambrozewicz Pawel , Hiller-Blin Astrid , Melnitchouk Wally , Battaglieri Marco , Liu Tianbo , Li Yaohang
Published: August 2021

Event generators in high-energy nuclear and particle physics play an important role in facilitating studies of particle reactions. We survey the state of the art of machine learning (ML) efforts at building physics event generators. We review ML generative models used in ML-based event generators and their specific challenges, and discuss various approaches of incorporating physics into the ML model designs to overcome these challenges. Finally, we explore some open questions related to super-resolution, fidelity, and extrapolation for physics event generation based on ML technology.
Recent Advances in Adversarial Training for Adversarial Robustness
Authors: Bai Tao , Luo Jinqi , Zhao Jun , Wen Bihan , Wang Qian
Published: August 2021

Adversarial training is one of the most effective approaches for deep learning models to defend against adversarial examples.

Unlike other defense strategies, adversarial training aims to enhance the robustness of models intrinsically.

During the past few years, adversarial training has been studied and discussed from various aspects, which deserves a comprehensive review.

For the first time in this survey, we systematically review the recent progress on adversarial training for adversarial robustness with a novel taxonomy.

Then we discuss the generalization problems in adversarial training from three perspectives and highlight the challenges which are not fully tackled.

Finally, we present potential future directions.
When Computational Representation Meets Neuroscience: A Survey on Brain Encoding and Decoding
Authors: Cao Lu , Huang Dandan , Zhang Yue
Published: August 2021

Real human language mechanisms and the artificial intelligent language processing methods are two independent systems. Exploring the relationship between the two can help develop human-like language models and is also beneficial to reveal the neuroscience of the reading brain. The flourishing research in this interdisciplinal research field calls for surveys to systemically study and analyze the recent successes. However, such a comprehensive review still cannot be found, which motivates our work. This article first briefly introduces the interdisciplinal research progress, then systematically discusses the task of brain decoding from the perspective of simple concepts and complete sentences, and also describes main limitations in this field and put forward with possible solutions. Finally, we conclude this survey with certain open research questions that will stimulate further studies.
Combinatorial Optimization and Reasoning with Graph Neural Networks
Authors: Cappart Quentin , Chételat Didier , Khalil Elias B. , Lodi Andrea , Morris Christopher , Veličković Petar
Published: August 2021

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have mostly focused on solving problem instances in isolation, ignoring the fact that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks, as a key building block for combinatorial tasks, either directly as solvers or by enhancing the former. This paper presents a conceptual review of recent key advancements in this emerging field, aiming at researchers in both optimization and machine learning.
Mechanism Design for Facility Location Problems: A Survey
Authors: Chan Hau , Filos-Ratsikas Aris , Li Bo , Li Minming , Wang Chenhao
Published: August 2021

The study of approximate mechanism design for facility location has been in the center of research at the intersection of artificial intelligence and economics for the last decade, largely due to its practical importance in various domains, such as social planning and clustering. At a high level, the goal is to select a number of locations on which to build a set of facilities, aiming to optimize some social objective based on the preferences of strategic agents, who might have incentives to misreport their private information. This paper presents a comprehensive survey of the significant progress that has been made since the introduction of the problem, highlighting all the different variants and methodologies, as well as the most interesting directions for future research.
Knowledge-aware Zero-Shot Learning: Survey and Perspective
Authors: Chen Jiaoyan , Geng Yuxia , Chen Zhuo , Horrocks Ian , Z. Pan Jeff , Chen Huajun
Published: August 2021

Zero-shot learning (ZSL) which aims at predicting classes that have never appeared during the training using external knowledge (a.k.a. side information) has been widely investigated. In this paper we present a literature review towards ZSL in the perspective of external knowledge, where we categorize the external knowledge, review their methods and compare different external knowledge. With the literature review, we further discuss and outlook the role of symbolic knowledge in addressing ZSL and other machine learning sample shortage issues.
A Comprehensive Survey on Image Dehazing Based on Deep Learning
Authors: Gui Jie , Cong Xiaofeng , Cao Yuan , Ren Wenqi , Zhang Jun , Zhang Jing , Tao Dacheng
Published: August 2021

The presence of haze significantly reduces the quality of images. Researchers have designed a variety of algorithms for image dehazing (ID) to restore the quality of hazy images. However, there are few studies that summarize the deep learning (DL) based dehazing technologies. In this paper, we conduct a comprehensive survey on the recent proposed dehazing methods. Firstly, we conclude the commonly used datasets, loss functions and evaluation metrics. Secondly, we group the existing researches of ID into two major categories: supervised ID and unsupervised ID. The core ideas of various influential dehazing models are introduced. Finally, the open issues for future research on ID are pointed out.
Emerging Methods of Auction Design in Social Networks
Authors: Guo Yuhang , Hao Dong
Published: August 2021

In recent years, a new branch of auction models called diffusion auction has extended the traditional auction into social network scenarios. The diffusion auction models the auction as a networked market whose nodes are potential customers and whose edges are the relations between these customers. The diffusion auction mechanism can incentivize buyers to not only submit a truthful bid, but also further invite their surrounding neighbors to participate into the auction. It can convene more participants than traditional auction mechanisms, which leads to better optimizations of different key aspects, such as social welfare, seller’s revenue, amount of redistributed money and so on. The diffusion auctions have recently attracted a discrete interest in the algorithmic game theory and market design communities. This survey summarizes the current progress of diffusion auctions.
Optimal Transport for Deep Generative Models: State of the Art and Research Challenges
Authors: Huynh Viet , Phung Dinh , Zhao He
Published: August 2021

Optimal transport has a long history in mathematics which was proposed by Gaspard Monge in the eighteenth century (Monge, 1781). However, until recently, advances in optimal transport theory pave the way for its use in the AI community, particularly for formulating deep generative models. In this paper, we provide a comprehensive overview of the literature in the field of deep generative models using optimal transport theory with an aim of providing a systematic review as well as outstanding problems and more importantly, open research opportunities to use the tools from the established optimal transport theory in the deep generative model domain.
Reasoning-Based Learning of Interpretable ML Models
Authors: Ignatiev Alexey , Marques-Silva Joao , Narodytska Nina , Stuckey Peter J.
Published: August 2021

Artificial Intelligence (AI) is widely used in decision making procedures in myriads of real-world applications across important practical areas such as finance, healthcare, education, and safety critical systems. Due to its ubiquitous use in safety and privacy critical domains, it is often vital to understand the reasoning behind the AI decisions, which motivates the need for explainable AI (XAI). One of the major approaches to XAI is represented by computing so-called interpretable machine learning (ML) models, such as decision trees (DT), decision lists (DL) and decision sets (DS). These models build on the use of if-then rules and are thus deemed to be easily understandable by humans. A number of approaches have been proposed in the recent past to devising all kinds of interpretable ML models, the most prominent of which involve encoding the problem into a logic formalism, which is then tackled by invoking a reasoning or discrete optimization procedure. This paper overviews the recent advances of the reasoning and constraints based approaches to learning interpretable ML models and discusses their advantages and limitations.
A Survey on Complex Knowledge Base Question Answering: Methods, Challenges and Solutions
Authors: Lan Yunshi , He Gaole , Jiang Jinhao , Jiang Jing , Zhao Wayne Xin , Wen Ji-Rong
Published: August 2021

Knowledge base question answering (KBQA) aims to answer a question over a knowledge base (KB). Recently, a large number of studies focus on semantically or syntactically complicated questions. In this paper, we elaborately summarize the typical challenges and solutions for complex KBQA. We begin with introducing the background about the KBQA task. Next, we present the two mainstream categories of methods for complex KBQA, namely semantic parsing-based (SP-based) methods and information retrieval-based (IR-based) methods. We then review the advanced methods comprehensively from the perspective of the two categories. Specifically, we explicate their solutions to the typical challenges. Finally, we conclude and discuss some promising directions for future research.
Pretrained Language Model for Text Generation: A Survey
Authors: Li Junyi , Tang Tianyi , Zhao Wayne Xin , Wen Ji-Rong
Published: August 2021

Text generation has become one of the most important yet challenging tasks in natural language processing (NLP). The resurgence of deep learning

has greatly advanced this field by neural generation models, especially the paradigm of pretrained language models (PLMs). In this paper, we present

an overview of the major advances achieved in the topic of PLMs for text generation. As the preliminaries, we present the general task definition

and briefly describe the mainstream architectures of PLMs for text generation. As the core content, we discuss how to adapt existing PLMs to model

different input data and satisfy special properties in the generated text. We further summarize several important fine-tuning strategies for text generation.

Finally, we present several future directions and conclude this paper. Our survey aims to provide text generation researchers a synthesis and pointer to related research.
A Survey on Goal Recognition as Planning
Authors: Meneguzzi Felipe , Fraga Pereira Ramon
Published: August 2021

Goal Recognition is the task of inferring an agent's goal, from a set of hypotheses, given a model of the environment dynamic, and a sequence of observations of such agent's behavior. While research on this problem gathered momentum as an offshoot of plan recognition, recent research has established it as a major subject of research on its own, leading to numerous new approaches that both expand the expressivity of domains in which to perform goal recognition and substantial advances to the state-of-the-art on established domain types. In this survey, we focus on the advances to goal recognition achieved in the last decade, categorizing the resulting techniques and identifying a number of opportunities for further breakthrough research.
The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs
Authors: Morris Christopher , Fey Matthias , Kriege Nils
Published: August 2021

In recent years, algorithms and neural architectures based on the Weisfeiler-Leman algorithm, a well-known heuristic for the graph isomorphism problem, emerged as a powerful tool for (supervised) machine learning with graphs and relational data. Here, we give a comprehensive overview of the algorithm's use in a machine learning setting. We discuss the theoretical background, show how to use it for supervised graph- and node classification, discuss recent extensions, and its connection to neural architectures. Moreover, we give an overview of current applications and future directions to stimulate research.
An Axiom System for Feedback Centralities
Authors: Wąs Tomasz , Skibski Oskar
Published: August 2021

In recent years, the axiomatic approach to centrality measures has attracted attention in the literature. However, most papers propose a collection of axioms dedicated to one or two considered centrality measures. In result, it is hard to capture the differences and similarities between various measures. In this paper, we propose an axiom system for four classic feedback centralities: Eigenvector centrality, Katz centrality, Katz prestige and PageRank. We prove that each of these four centrality measures can be uniquely characterized with a subset of our axioms. Our system is the first one in the literature that considers all four feedback centralities.
A Survey on Spoken Language Understanding: Recent Advances and New Frontiers
Authors: Qin Libo , Xie Tianbao , Che Wanxiang , Liu Ting
Published: August 2021

Spoken Language Understanding (SLU) aims to extract the semantics frame of user queries, which is a core component in a task-oriented dialog system. With the burst of deep neural networks and the evolution of pre-trained language models, the research of SLU has obtained signiﬁcant breakthroughs. However, there remains a lack of a comprehensive survey summarizing existing approaches and recent trends, which motivated the work presented in this article. In this paper, we survey recent advances and new frontiers in SLU. Specifically, we give a thorough review of this research ﬁeld, covering different aspects including (1) new taxonomy: we provide a new perspective for SLU ﬁled, including single model vs. joint model, implicit joint modeling vs. explicit joint modeling in joint model, non pre-trained paradigm vs. pretrained paradigm; (2) new frontiers: some emerging areas in complex SLU as well as the corresponding challenges; (3) abundant open-source resources: to help the community, we have collected, organized the related papers, baseline projects and leaderboard on a public website where SLU researchers could directly access to the recent progress. We hope that this survey can shed a light on future research in SLU ﬁeld.
Neural Temporal Point Processes: A Review
Authors: Shchur Oleksandr , Türkmen Ali Caner , Januschowski Tim , Günnemann Stephan
Published: August 2021

Temporal point processes (TPP) are probabilistic generative models for continuous-time event sequences. Neural TPPs combine the fundamental ideas from point process literature with deep learning approaches, thus enabling construction of flexible and efficient models. The topic of neural TPPs has attracted significant attention in the recent years, leading to the development of numerous new architectures and applications for this class of models. In this review paper we aim to consolidate the existing body of knowledge on neural TPPs. Specifically, we focus on important design choices and general principles for defining neural TPP models. Next, we provide an overview of application areas commonly considered in the literature. We conclude this survey with the list of open challenges and important directions for future work in the field of neural TPPs.
A Unifying Bayesian Formulation of Measures of Interpretability in Human-AI Interaction
Authors: Sreedharan Sarath , Kulkarni Anagha , Smith David , Kambhampati Subbarao
Published: August 2021

Existing approaches for generating human-aware agent behaviors have considered different measures of interpretability in isolation. Further, these measures have been studied under differing assumptions, thus precluding the possibility of designing a single framework that captures these measures under the same assumptions.

In this paper, we present a unifying Bayesian framework that models a human observer's evolving beliefs about an agent and thereby define the problem of Generalized Human-Aware Planning. We will show that the definitions of interpretability measures like explicability, legibility and predictability from the prior literature fall out as special cases of our general framework. Through this framework, we also bring a previously ignored fact to light that the human-robot interactions are in effect open-world problems, particularly as a result of modeling the human's beliefs over the agent. Since the human may not only hold beliefs unknown to the agent but may also form new hypotheses about the agent when presented with novel or unexpected behaviors.
A Survey on Low-Resource Neural Machine Translation
Authors: Wang Rui , Tan Xu , Luo Renqian , Qin Tao , Liu Tie-Yan
Published: August 2021

Neural approaches have achieved state-of-the-art accuracy on machine translation but suffer from the high cost of collecting large scale parallel data. Thus, a lot of research has been conducted for neural machine translation (NMT) with very limited parallel data, i.e., the low-resource setting. In this paper, we provide a survey for low-resource NMT and classify related works into three categories according to the auxiliary data they used: (1) exploiting monolingual data of source and/or target languages, (2) exploiting data from auxiliary languages, and (3) exploiting multi-modal data. We hope that our survey can help researchers to better understand this field and inspire them to design better algorithms, and help industry practitioners to choose appropriate algorithms for their applications.
Manipulation of k-Coalitional Games on Social Networks
Authors: Waxman Naftali , Kraus Sarit , Hazon Noam
Published: August 2021

In many coalition formation games the utility of the agents depends on a social network. In such scenarios there might be a manipulative agent that would like to manipulate his connections in the social network in order to increase his utility. We study a model of coalition formation in which a central organizer, who needs to form k coalitions, obtains information about the social network from the agents.

The central organizer has her own objective: she might want to maximize the utilitarian social welfare, maximize the egalitarian social welfare, or only guarantee that every agent will have at least one connection within her coalition.

In this paper we study the susceptibility for manipulation of these objectives, given the abilities and information that the manipulator has. Specifically, we show that if the manipulator has very limited information, namely he is only familiar with his immediate neighbours in the network, then a manipulation is almost always impossible. Moreover, if the manipulator is only able to add connections to the social network, then a manipulation is still impossible for some objectives, even if the manipulator has full information on the structure of the network. On the other hand, if the manipulator is able to hide some of his connections, then all objectives are susceptible to manipulation, even if the manipulator has limited information, i.e., when he is familiar with his immediate neighbours and with their neighbours.
Challenges and Opportunities of Building Fast GBDT Systems
Authors: Wen Zeyi , Li Qinbin , He Bingsheng , Cui Bin
Published: August 2021

In the last few years, Gradient Boosting Decision Trees (GBDTs) have been widely used in various applications such as online advertising and spam filtering. However, GBDT training is often a key performance bottleneck for such data science pipelines, especially for training a large number of deep trees on large data sets. Thus, many parallel and distributed GBDT systems have been researched and developed to accelerate the training process. In this survey paper, we review the recent GBDT systems with respect to accelerations with emerging hardware as well as cluster computing, and compare the advantages and disadvantages of the existing implementations. Finally, we present the research opportunities and challenges in designing fast next generation GBDT systems.
A Comparative Survey: Benchmarking for Pool-based Active Learning
Authors: Zhan Xueying , Liu Huan , Li Qing , Chan Antoni B.
Published: August 2021

Active learning (AL) is a subfield of machine learning (ML) in which a learning algorithm aims to achieve good accuracy with fewer training samples by interactively querying the oracles to label new data points. Pool-based AL is well-motivated in many ML tasks, where unlabeled data is abundant, but their labels are hard or costly to obtain. Although many pool-based AL methods have been developed, some important questions remain unanswered such as how to: 1) determine the current state-of-the-art technique; 2) evaluate the relative benefit of new methods for various properties of the dataset; 3) understand what specific problems merit greater attention; and 4) measure the progress of the field over time. In this paper, we survey and compare various AL strategies used in both recently proposed and classic highly-cited methods. We propose to benchmark pool-based AL methods with a variety of datasets and quantitative metric, and draw insights from the comparative empirical results.
A Survey on Universal Adversarial Attack
Authors: Zhang Chaoning , Benz Philipp , Lin Chenguo , Karjauv Adil , Wu Jing , Kweon In So
Published: August 2021

The intriguing phenomenon of adversarial examples has attracted significant attention in machine learning and what might be more surprising to the community is the existence of universal adversarial perturbations (UAPs), i.e. a single perturbation to fool the target DNN for most images. With the focus on UAP against deep classifiers, this survey summarizes the recent progress on universal adversarial attacks, discussing the challenges from both the attack and defense sides, as well as the reason for the existence of UAP. We aim to extend this work as a dynamic survey that will regularly update its content to follow new works regarding UAP or universal attack in a wide range of domains, such as image, audio, video, text, etc. Relevant updates will be discussed at: https://bit.ly/2SbQlLG. We welcome authors of future works in this field to contact us for including your new findings.
Comparing Weak Admissibility Semantics to their Dung-style Counterparts (Extended Abstract)
Authors: Baumann Ringo , Brewka Gerhard , Ulbricht Markus
Published: August 2021

Semantics based on weak admissibility were recently introduced to overcome a problem with self-defeating arguments that has not been solved for more than 25 years. The recursive definition of weak admissibility mainly relies on the notion of a reduct regarding a set E which only contains arguments which are neither in E, nor attacked by E. At first glance the reduct seems to be tailored for the weaker versions of Dung-style semantics only. In this paper we show that standard Dung semantics can be naturally reformulated using the reduct revealing that this concept is already implicit. We further identify a new abstract principle for semantics, so-called modularization describing how to obtain further extensions given an initial one. Its importance for the study of abstract argumentation semantics is shown by its ability to alternatively characterize classical and non-classical semantics.
Improved Guarantees and a Multiple-descent Curve for Column Subset Selection and the Nystrom Method (Extended Abstract)
Authors: Dereziński Michał , Khanna Rajiv , Mahoney Michael W.
Published: August 2021

The Column Subset Selection Problem (CSSP) and the Nystrom method are among the leading tools for constructing interpretable low-rank approximations of large datasets by selecting a small but representative set of features or instances. A fundamental question in this area is: what is the cost of this interpretability, i.e., how well can a data subset of size k compete with the best rank k approximation? We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees which go beyond the standard worst-case analysis. Our approach leads to significantly better bounds for datasets with known rates of singular value decay, e.g., polynomial or exponential decay. Our analysis also reveals an intriguing phenomenon: the cost of interpretability as a function of k may exhibit multiple peaks and valleys, which we call a multiple-descent curve. A lower bound we establish shows that this behavior is not an artifact of our analysis, but rather it is an inherent property of the CSSP and Nystrom tasks. Finally, using the example of a radial basis function (RBF) kernel, we show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
Mental Models of AI Agents in a Cooperative Game Setting (Extended Abstract)
Authors: Gero Katy Ilonka , Ashktorab Zahra , Dugan Casey , Pan Qian , Johnson James , Geyer Werner , Ruiz Maria , Miller Sarah , Millen David R. , Campbell Murray , Kumaravel Sadhana , Zhang Wei
Published: August 2021

As more and more forms of AI become prevalent, it becomes increasingly important to understand how people develop mental models of these systems. In this work we study people's mental models of an AI agent in a cooperative word guessing game. We run a study in which people play the game with an AI agent while ``thinking out loud''; through thematic analysis we identify features of the mental models developed by participants. In a large-scale study we have participants play the game with the AI agent online and use a post-game survey to probe their mental model. We find that those who win more often have better estimates of the AI agent's abilities. We present three components---global knowledge, local knowledge, and knowledge distribution---for modeling AI systems and propose that understanding the underlying technology is insufficient for developing appropriate conceptual models---analysis of behavior is also necessary.
Deep Drone Acrobatics (Extended Abstract)
Authors: Kaufmann Elia , Loquercio Antonio , Ranftl Rene , Müller Matthias , Koltun Vladlen , Scaramuzza Davide
Published: August 2021

Acrobatic flight with quadrotors is extremely challenging. Maneuvers such as the loop, matty flip, or barrel roll require high thrust and extreme angular accelerations that push the platform to its limits. Human drone pilots require years of practice to safely master such maneuvers. Yet, a tiny mistake could make the platform lose control, and brutally crash. This short paper describes an approach to safely train acrobatic controllers in simulation and deploy them with no fine-tuning zero-shot transfer on physical quadrotors. The approach uses only onboard sensing and computation.
The Moodoo Library: Quantitative Metrics to Model How Teachers Make Use of the Classroom Space by Analysing Indoor Positioning Traces (Extended Abstract)
Authors: Martinez-Maldonado Roberto , Echeverria Vanessa , Mangaroska Katerina , Shibani Antonette , Fernandez-Nieto Gloria , Schulte Jurgen , Shum Simon Buckingham
Published: August 2021

Teachers’ spatial behaviours in the classroom can strongly influence students’ engagement, motivation and other behaviours that shape their learning. However, classroom teaching behav-iour is ephemeral, and has largely remained opaque to computational analysis. This paper presents a library called ‘Moodoo’ that can serve to automatically model how teachers make use of the classroom space by analysing indoor positioning traces. The system automatically ex-tracts spatial metrics (e.g. teacher-student ratios, frequency of visits to students’ personal spaces, presence in classroom spaces of interest, index of dispersion and entropy), mapping from the teachers’ low-level positioning data to higher-order spatial constructs.