bluuebunny/crossref_metadata_2025 huggingface dataset:
On Convergence of Gradient Expected Sarsa(λ)
Authors: Yang Long , Zheng Gang , Zhang Yu , Zheng Qian , Li Pengfei , Pan Gang
Published: September 2022

We study the convergence of Expected Sarsa(λ) with function approximation. We show that with off-line es- timate (multi-step bootstrapping) to ExpectedSarsa(λ) is unstable for off-policy learning. Furthermore, based on convex-concave saddle-point framework, we propose a con- vergent Gradient Expected Sarsa(λ) (GES(λ)) algorithm. The theoretical analysis shows that the proposed GES(λ) converges to the optimal solution at a linear convergence rate under true gradient setting. Furthermore, we develop a Lyapunov function technique to investigate how the step- size influences finite-time performance of GES(λ). Addition- ally, such a technique of Lyapunov function can be poten- tially generalized to other gradient temporal difference algo- rithms. Finally, our experiments verify the effectiveness of our GES(λ). For the details of proof, please refer to https: //arxiv.org/pdf/2012.07199.pdf.
Learning Interpretable Models for Coupled Networks Under Domain Constraints
Authors: You Hongyuan , Lin Sikun , Singh Ambuj
Published: September 2022

Modeling the behavior of coupled networks is challenging due to their intricate dynamics. For example in neuroscience, it is of critical importance to understand the relationship between the functional neural processes and the anatomical connectivities. Modern neuroimaging techniques allow us to separately measure functional connectivities through fMRI imaging and measure underlying white matter wirings through diffusion imaging. Previous studies have shown that structural edges in brain networks improve the inference of functional edges and vice versa. In this paper, we investigate the idea of coupled networks through an optimization framework by focusing on interactions between structural edges and functional edges of brain networks. We consider both types of edges as observed instances of random variables that represent different underlying network processes. The proposed framework does not depend on the Gaussian functional form and achieves a more robust selection on non-Gaussian data compared with existing approaches. To incorporate existing domain knowledge into such studies, we propose a novel formulation to place hard network constraints on the noise term while estimating interactions. This not only leads to a cleaner way of applying network constraints but also brings a more scalable solution when the network connectivity is sparse. We validate our method on multishell diffusion and task-evoked fMRI datasets from Human Connectome Project, leading to both important insights on structural backbones that support various types of task activities performed during the scanning sessions as well as general solutions to the study of coupled networks.
Identity-aware Graph Neural Networks
Authors: You Jiaxuan , Gomes-Selman Jonathan M , Ying Rex , Leskovec Jure
Published: September 2022

Message passing Graph Neural Networks (GNNs) provide a powerful modeling framework for relational data. However, the expressive power of existing GNNs is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test, which means GNNs that are not able to predict node clustering coefficients and shortest path distances, and cannot differentiate between different d-regular graphs. Here we develop a class of message passing GNNs, named Identity-aware Graph Neural Networks (ID-GNNs), with greater expressive power than the 1-WL test. ID-GNN offers a minimal but powerful solution to limitations of existing GNNs. ID-GNN extends existing GNN architectures by inductively considering nodes’ identities during message passing. To embed a given node, ID-GNN first extracts the ego network centered at the node, then conducts rounds of heterogeneous message passing, where different sets of parameters are applied to the center node than to other surrounding nodes in the ego network. We further propose a simplified but faster version of ID-GNN that injects node identity information as augmented node features. Alto- gether, both versions of ID-GNN represent general extensions of message passing GNNs, where experiments show that transforming existing GNNs to ID-GNNs yields on average 40% accuracy improvement on challenging node, edge, and graph property prediction tasks; 3% accuracy improvement on node and graph classification benchmarks; and 15% ROC AUC improvement on real-world link prediction tasks. Additionally, ID-GNNs demonstrate improved or comparable performance over other task-specific graph networks.
Memory-Gated Recurrent Networks
Authors: Zhang Yaquan , Wu Qi , Peng Nanbo , Dai Min , Zhang Jing , Wang Hu
Published: September 2022

The essence of multivariate sequential learning is all about how to extract dependencies in data. These data sets, such as hourly medical records in intensive care units and multi-frequency phonetic time series, often time exhibit not only strong serial dependencies in the individual components (the "marginal" memory) but also non-negligible memories in the cross-sectional dependencies (the "joint" memory). Because of the multivariate complexity in the evolution of the joint distribution that underlies the data generating process, we take a data-driven approach and construct a novel recurrent network architecture, termed Memory-Gated Recurrent Networks (mGRN), with gates explicitly regulating two distinct types of memories: the marginal memory and the joint memory. Through a combination of comprehensive simulation studies and empirical experiments on a range of public datasets, we show that our proposed mGRN architecture consistently outperforms state-of-the-art architectures targeting multivariate time series.
Efficient Classification with Adaptive KNN
Authors: Zhao Puning , Lai Lifeng
Published: September 2022

In this paper, we propose an adaptive kNN method for classification, in which different k are selected for different test samples. Our selection rule is easy to implement since it is completely adaptive and does not require any knowledge of
the underlying distribution. The convergence rate of the risk of this classifier to the Bayes risk is shown to be minimax optimal for various settings. Moreover, under some special assumptions, the convergence rate is especially fast and does
not decay with the increase of dimensionality.
Bias and Variance of Post-processing in Differential Privacy
Authors: Zhu Keyu , Van Hentenryck Pascal , Fioretto Ferdinando
Published: September 2022

Post-processing immunity is a fundamental property of differential
privacy: it enables the application of arbitrary data-independent
transformations to the results of differentially private outputs
without affecting their privacy guarantees.
When query outputs must satisfy domain constraints, post-processing
can be used to project them back onto the feasibility region.
Moreover, when the feasible region is convex, a widely adopted class of post-processing steps is also guaranteed to improve accuracy. Post-processing has
been applied successfully in many applications including census
data, energy systems, and mobility. However, its effects on the
noise distribution is poorly understood: It is often argued that
post-processing may introduce bias and increase variance. This paper
takes a first step towards understanding the properties of
post-processing. It considers the release of census data and
examines, both empirically and theoretically, the behavior of a
widely adopted class of post-processing functions.
An Efficient Algorithm for Deep Stochastic Contextual Bandits
Authors: Zhu Tan , Liang Guannan , Zhu Chunjiang , Li Haining , Bi Jinbo
Published: September 2022

In stochastic contextual bandit (SCB) problems, an agent selects an action based on certain observed context to maximize the cumulative reward over iterations. Recently there have been a few studies using a deep neural network (DNN) to predict the expected reward for an action, and the DNN is trained by a stochastic gradient based method. However, convergence analysis has been greatly ignored to examine whether and where these methods converge. In this work, we formulate the SCB that uses a DNN reward function as a non-convex stochastic optimization problem, and design a stage-wised stochastic gradient descent algorithm to optimize the problem and determine the action policy. We prove that with high probability, the action sequence chosen by our algorithm converges to a greedy action policy respecting a local optimal reward function. Extensive experiments have been performed to demonstrate the effectiveness and efficiency of the proposed algorithm on multiple real-world datasets.
Maintenance of Social Commitments in Multiagent Systems
Authors: Telang Pankaj , Singh Munindar P. , Yorke-Smith Neil
Published: September 2022

We introduce and formalize a concept of a maintenance commitment, a kind of social commitment characterized by states whose truthhood an agent commits to maintain. This concept of maintenance commitments enables us to capture a richer variety of real-world scenarios than possible using achievement commitments with a temporal condition. By developing a rule-based operational semantics, we study the relationship between agents' achievement and maintenance goals, achievement commitments, and maintenance commitments. We motivate a notion of coherence which captures alignment between an agents' achievement and maintenance cognitive and social constructs, and prove that, under specified conditions, the goals and commitments of both rational agents individually and of a multiagent system are coherent.
Is the Most Accurate AI the Best Teammate? Optimizing AI for Teamwork
Authors: Bansal Gagan , Nushi Besmira , Kamar Ece , Horvitz Eric , Weld Daniel S.
Published: September 2022

AI practitioners typically strive to develop the most accurate systems, making an implicit assumption that the AI system will function autonomously. However, in practice, AI systems often are used to provide advice to people in domains ranging from criminal justice and finance to healthcare. In such AI-advised decision making, humans and machines form a team, where the human is responsible for making final decisions. But is the most accurate AI the best teammate? We argue "not necessarily" --- predictable performance may be worth a slight sacrifice in AI accuracy. Instead, we argue that AI systems should be trained in a human-centered manner, directly optimized for team performance. We study this proposal for a specific type of human-AI teaming, where the human overseer chooses to either accept the AI recommendation or solve the task themselves. To optimize the team performance for this setting we maximize the team's expected utility, expressed in terms of the quality of the final decision, cost of verifying, and individual accuracies of people and machines. Our experiments with linear and non-linear models on real-world, high-stakes datasets show that the most accuracy AI may not lead to highest team performance and show the benefit of modeling teamwork during training through improvements in expected team utility across datasets, considering parameters such as human skill and the cost of mistakes. We discuss the shortcoming of current optimization approaches beyond well-studied loss functions such as log-loss, and encourage future work on AI optimization problems motivated by human-AI collaboration.
Beyond Class-Conditional Assumption: A Primary Attempt to Combat Instance-Dependent Label Noise
Authors: Chen Pengfei , Ye Junjie , Chen Guangyong , Zhao Jingwei , Heng Pheng-Ann
Published: September 2022

Supervised learning under label noise has seen numerous advances recently, while existing theoretical findings and empirical results broadly build up on the class-conditional noise (CCN) assumption that the noise is independent of input features given the true label. In this work, we present a theoretical hypothesis testing and prove that noise in real-world dataset is unlikely to be CCN, which confirms that label noise should depend on the instance and justifies the urgent need to go beyond the CCN assumption.The theoretical results motivate us to study the more general and practical-relevant instance-dependent noise (IDN). To stimulate the development of theory and methodology on IDN, we formalize an algorithm to generate controllable IDN and present both theoretical and empirical evidence to show that IDN is semantically meaningful and challenging. As a primary attempt to combat IDN, we present a tiny algorithm termed self-evolution average label (SEAL), which not only stands out under IDN with various noise fractions, but also improves the generalization on real-world noise benchmark Clothing1M. Our code is released. Notably, our theoretical analysis in Section 2 provides rigorous motivations for studying IDN, which is an important topic that deserves more research attention in future.
On the Verification of Neural ODEs with Stochastic Guarantees
Authors: Grunbacher Sophie , Hasani Ramin , Lechner Mathias , Cyranka Jacek , Smolka Scott A. , Grosu Radu
Published: September 2022

We show that Neural ODEs, an emerging class of time-continuous neural networks, can be verified by solving a set of global-optimization problems. For this purpose, we introduce Stochastic Lagrangian Reachability (SLR), an abstraction-based technique for constructing a tight Reachtube (an over-approximation of the set of reachable states over a given time-horizon), and provide stochastic guarantees in the form of confidence intervals for the Reachtube bounds.
SLR inherently avoids the infamous wrapping effect (accumulation of over-approximation errors) by performing local optimization steps to expand safe regions instead of repeatedly forward-propagating them as is done by deterministic reachability methods.
To enable fast local optimizations, we introduce a novel forward-mode adjoint sensitivity method to compute gradients without the need for backpropagation.
Finally, we establish asymptotic and non-asymptotic convergence rates for SLR.
PenDer: Incorporating Shape Constraints via Penalized Derivatives
Authors: Gupta Akhil , Marla Lavanya , Sun Ruoyu , Shukla Naman , Kolbeinsson Arinbjörn
Published: September 2022

When deploying machine learning models in the real-world, system designers may wish that models exhibit certain shape behavior, i.e., model outputs follow a particular shape with respect to input features. Trends such as monotonicity, convexity, diminishing or accelerating returns are some of the desired shapes. Presence of these shapes makes the model more interpretable for the system designers, and adequately fair for the customers. We notice that many such common shapes are related to derivatives, and propose a new approach, PenDer (Penalizing Derivatives), which incorporates these shape constraints by penalizing the derivatives. We further present an Augmented Lagrangian Method (ALM) to solve this constrained optimization problem. Experiments on three real-world datasets illustrate that even though both PenDer and state-of-the-art Lattice models achieve similar conformance to shape, PenDer captures better sensitivity of prediction with respect to intended features. We also demonstrate that PenDer achieves better test performance than Lattice while enforcing more desirable shape behavior.
On Generating Plausible Counterfactual and Semi-Factual Explanations for Deep Learning
Authors: Kenny Eoin M. , Keane Mark T
Published: September 2022

There is a growing concern that the recent progress made in AI, especially regarding the predictive competence of deep learning models, will be undermined by a failure to properly explain their operation and outputs. In response to this disquiet, counterfactual explanations have become very popular in eXplainable AI (XAI) due to their asserted computational, psychological, and legal benefits. In contrast however, semi-factuals (which appear to be equally useful) have surprisingly received no attention. Most counterfactual methods address tabular rather than image data, partly because the non-discrete nature of images makes good counterfactuals difficult to define; indeed, generating plausible counterfactual images which lie on the data manifold is also problematic. This paper advances a novel method for generating plausible counterfactuals and semi-factuals for black-box CNN classifiers doing computer vision. The present method, called PlausIble Exceptionality-based Contrastive Explanations (PIECE), modifies all “exceptional” features in a test image to be “normal” from the perspective of the counterfactual class, to generate plausible counterfactual images. Two controlled experiments compare this method to others in the literature, showing that PIECE generates highly plausible counterfactuals (and the best semi-factuals) on several benchmark measures.
Improving Robustness to Model Inversion Attacks via Mutual Information Regularization
Authors: Wang Tianhao , Zhang Yuheng , Jia Ruoxi
Published: September 2022

This paper studies defense mechanisms against model inversion (MI) attacks -- a type of privacy attacks aimed at inferring information about the training data distribution given the access to a target machine learning model. Existing defense mechanisms rely on model-specific heuristics or noise injection. While being able to mitigate attacks, existing methods significantly hinder model performance. There remains a question of how to design a defense mechanism that is applicable to a variety of models and achieves better utility-privacy tradeoff.

In this paper, we propose the Mutual Information Regularization based Defense (MID) against MI attacks. The key idea is to limit the information about the model input contained in the prediction, thereby limiting the ability of an adversary to infer the private training attributes from the model prediction. Our defense principle is model-agnostic and we present tractable approximations to the regularizer for linear regression, decision trees, and neural networks, which have been successfully attacked by prior work if not attached with any defenses. We present a formal study of MI attacks by devising a rigorous game-based definition and quantifying the associated information leakage. Our theoretical analysis sheds light on the inefficacy of DP in defending against MI attacks, which has been empirically observed in several prior works. Our experiments demonstrate that MID leads to state-of-the-art performance for a variety of MI attacks, target models and datasets.
Computing Plan-Length Bounds Using Lengths of Longest Paths
Authors: Abdulaziz Mohammad , Berger Dominik
Published: September 2022

We devise a method to exactly compute the length of the longest simple path in factored state spaces, like state spaces encountered in classical planning. Although the complexity of this problem is NEXP-Hard, we show that our method can be used to compute practically useful upper-bounds on lengths of plans. We show that the computed upper-bounds are significantly better than bounds produced by state-of-the-art bounding techniques and that they can be used to improve the SAT-based
planning.
Responsibility Attribution in Parameterized Markovian Models
Authors: Baier Christel , Funke Florian , Majumdar Rupak
Published: September 2022

We consider the problem of responsibility attribution in the setting of parametric Markov chains. Given a family of Markov chains over a set of parameters, and a property, responsibility attribution asks how the difference in the value of the property should be attributed to the parameters when they change from one point in the parameter space to another.

We formalize responsibility as path-based attribution schemes studied in cooperative game theory. An attribution scheme in a game determines how a value (a surplus or a cost) is distributed among a set of participants. Path-based attribution schemes include the well-studied Aumann-Shapley and the Shapley-Shubik schemes. In our context, an attribution scheme measures the responsibility of each parameter on the value function of the parametric Markov chain.

We study the decision problem for path-based attribution schemes. Our main technical result is an algorithm for deciding if a path-based attribution scheme for a rational (ratios of polynomials) cost function is over a rational threshold. In particular, it is decidable if the Aumann-Shapley value for a player is at least a given rational number. As a consequence, we show that responsibility attribution is decidable for parametric Markov chains and for a general class of properties that include expectation and variance of discounted sum and long-run average rewards, as well as specifications in temporal logic.
Revisiting Dominance Pruning in Decoupled Search
Authors: Gnad Daniel
Published: September 2022

In classical planning as search, duplicate state pruning is a standard method to avoid unnecessarily handling the same state multiple times. In decoupled search, similar to symbolic search approaches, search nodes, called decoupled states, do not correspond to individual states, but to sets of states. Therefore, duplicate state pruning is less effective in decoupled search, and dominance pruning is employed, taking into account the state sets. We observe that the time required for dominance checking dominates the overall runtime, and propose two ways to tackle this issue. Our main contribution is a stronger variant of dominance checking for optimal planning, where efficiency and pruning power are most crucial. The new variant greatly improves the latter, without incurring a computational overhead. Moreover, we develop three methods that make the dominance check more efficient: exact duplicate checking, which, albeit resulting in weaker pruning, can pay off due to the use of hashing; avoiding the dominance check in non-optimal planning if leaf state spaces are invertible; and exploiting the transitivity of the dominance relation to only check against the relevant subset of visited decoupled states. We show empirically that all our improvements are indeed beneficial in many standard benchmarks.
Endomorphisms of Classical Planning Tasks
Authors: Horčík Rostislav , Fišer Daniel
Published: September 2022

Detection of redundant operators that can be safely
removed from the planning task is an essential technique
allowing to greatly improve performance of planners.
In this paper, we employ structure-preserving maps on labeled transition
systems (LTSs), namely endomorphisms well known from model theory, in order
to detect redundancy. Computing endomorphisms of an LTS induced by a
planning task is typically infeasible, so we show how to compute some of
them on concise representations of planning tasks such as finite domain
representations and factored LTSs.
We formulate the computation of endomorphisms as a constraint satisfaction
problem (CSP) that can be solved by an off-the-shelf CSP solver.
Finally, we experimentally verify that the
proposed method can find a sizeable number of redundant operators on the
standard benchmark set.
Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processes
Authors: Rigter Marc , Lacerda Bruno , Hawes Nick
Published: September 2022

The parameters for a Markov Decision Process (MDP) often cannot be specified exactly. Uncertain MDPs (UMDPs) capture this model ambiguity by defining sets which the parameters belong to. Minimax regret has been proposed as an
objective for planning in UMDPs to find robust policies which are not overly conservative. In this work, we focus on planning for Stochastic Shortest Path (SSP) UMDPs with uncertain cost and transition functions. We introduce a Bellman equation to compute the regret for a policy. We propose a dynamic programming algorithm that utilises the regret Bellman equation, and show that it optimises minimax regret exactly for UMDPs with independent uncertainties. For coupled uncertainties, we extend our approach to use options to enable a trade off between computation and solution quality. We evaluate our approach on both synthetic and real-world domains, showing that it significantly outperforms existing baselines.
Saturated Post-hoc Optimization for Classical Planning
Authors: Seipp Jendrik , Keller Thomas , Helmert Malte
Published: September 2022

Saturated cost partitioning and post-hoc optimization are two powerful cost partitioning algorithms for optimal classical planning. The main idea of saturated cost partitioning is to give each considered heuristic only the fraction of remaining operator costs that it needs to prove its estimates. We show how to apply this idea to post-hoc optimization and obtain a heuristic that dominates the original both in theory and on the IPC benchmarks.
On the Optimal Efficiency of A* with Dominance Pruning
Authors: Torralba Álvaro
Published: September 2022

A well known result is that, given a consistent heuristic and no other source of information, A* does expand a minimal number of nodes up to tie-breaking. We extend this analysis for A* with dominance pruning, which exploits a dominance relation to eliminate some nodes during the search. We show that the expansion order of A* is not necessarily optimally efficient when considering dominance pruning with arbitrary dominance relations, but it remains optimally efficient under certain restrictions for the heuristic and dominance relation.
Dynamic Automaton-Guided Reward Shaping for Monte Carlo Tree Search
Authors: Velasquez Alvaro , Bissey Brett , Barak Lior , Beckus Andre , Alkhouri Ismail , Melcer Daniel , Atia George
Published: September 2022

Reinforcement learning and planning have been revolutionized in recent years, due in part to the mass adoption of deep convolutional neural networks and the resurgence of powerful methods to refine decision-making policies. However, the problem of sparse reward signals and their representation
remains pervasive in many domains. While various rewardshaping mechanisms and imitation learning approaches have been proposed to mitigate this problem, the use of humanaided artificial rewards introduces human error, sub-optimal behavior, and a greater propensity for reward hacking. In this
paper, we mitigate this by representing objectives as automata in order to define novel reward shaping functions over this structured representation. In doing so, we address the sparse rewards problem within a novel implementation of Monte Carlo Tree Search (MCTS) by proposing a reward shaping function which is updated dynamically to capture statistics on the utility of each automaton transition as it pertains to satisfying the goal of the agent. We further demonstrate that such automaton-guided reward shaping can be utilized to facilitate transfer learning between different environments when the objective is the same.
Competitive Analysis for Two-Level Ski-Rental Problem
Authors: Wu Binghan , Bao Wei , Yuan Dong
Published: September 2022

In this paper, we study a two-level ski-rental problem. There are multiple commodities, each one can be “rented” (paying for on-demand usage) or “purchased” (paying for life-time usage). There is also a combo purchase available so that all commodities can be purchased as a combo. Since the usages of the commodities in future are not known in advance, to minimize the overall cost, we design an online algorithm to decide if we rent a commodity, purchase a commodity, or make a combo purchase. We first propose a deterministic online algorithm. It can achieve 3 competitive ratio, which is optimal and tight. Next, we further propose a randomized online algorithm, leading to a e^σ/(e^σ-1) competitive ratio, where σ is the ratio between the price of a single commodity and the price of combo purchase. Finally, we apply simulation to verify the theoretical competitive ratios and evaluate the actual performance against benchmarks.
GO Hessian for Expectation-Based Objectives
Authors: Cong Yulai , Zhao Miaoyun , Li Jianqiao , Chen Junya , Carin Lawrence
Published: September 2022

An unbiased low-variance gradient estimator, termed GO gradient, was proposed recently for expectation-based objectives E_q_γ(y) [f(y)], where the random variable (RV) y may be drawn from a stochastic computation graph (SCG) with continuous (non-reparameterizable) internal nodes and continuous/discrete leaves. Based on the GO gradient, we present for E_q_γ(y) [f(y)] an unbiased low-variance Hessian estimator, named GO Hessian, which contains the deterministic Hessian as a special case. Considering practical implementation, we reveal that the GO Hessian in expectation obeys the chain rule and is therefore easy-to-use with auto-differentiation and Hessian-vector products, enabling efficient cheap exploitation of curvature information over deep SCGs. As representative examples, we present the GO Hessian for non-reparameterizable gamma and negative binomial RVs/nodes. Leveraging the GO Hessian, we develop a new second-order method for E_q_γ(y) [f(y)], with challenging experiments conducted to verify its effectiveness and efficiency.
Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback
Authors: D'Angelo Gianlorenzo , Poddar Debashmita , Vinci Cosimo
Published: September 2022

In the influence maximization (IM) problem, we are given a social network and a budget k, and we look for a set of k nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since his definition by Kempe, Kleinberg, and Tardos (2003). However, most of the work focuses on the non-adaptive version of the problem where all the k seed nodes must be selected before that the cascade starts. In this paper we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the i-th seed can be based on the observed cascade produced by the first i-1 seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed and on the independent cascade model where each edge is associated with an independent probability of diffusing influence.

Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only works for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by ∛n+1, where n is the number of nodes in the graph. Moreover we improve over the known upper bound for in-arborescences from 2e/(e-1)≈3.16 to 2e²/(e²-1)≈2.31. Finally, we study α-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most α, and show that the adaptivity gap is upper-bounded by √α+O(1). Moreover, we show that in 0-bounded graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3e³/(e³-1)≈3.16.

To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest.
Estimation of Spectral Risk Measures
Authors: Pandey Ajay Kumar , L.A. Prashanth , Bhat Sanjay P.
Published: September 2022

We consider the problem of estimating a spectral risk measure (SRM) from i.i.d. samples, and propose a novel method that is based on numerical integration. We show that our SRM estimate concentrates exponentially, when the underlying distribution has bounded support. Further, we also consider the case when the underlying distribution satisfies an exponential moment bound, which includes sub-Gaussian and subexponential distributions. For these distributions, we derive a concentration bound for our estimation scheme. We validate the theoretical findings on a synthetic setup, and in a vehicular traffic routing application.
Encoder-Decoder Based Unified Semantic Role Labeling with Label-Aware Syntax
Authors: Fei Hao , Li Fei , Li Bobo , Ji Donghong
Published: September 2022

Currently the unified semantic role labeling (SRL) that achieves predicate identification and argument role labeling in an end-to-end manner has received growing interests. Recent works show that leveraging the syntax knowledge significantly enhances the SRL performances. In this paper, we investigate a novel unified SRL framework based on the sequence-to-sequence architecture with double enhancement in both the encoder and decoder sides. In the encoder side, we propose a novel label-aware graph convolutional network (LA-GCN) to encode both the syntactic dependent arcs and labels into BERT-based word representations. In the decoder side, we creatively design a pointer-network-based model for detecting predicates, arguments and roles jointly. Our pointer-net decoder is able to make decisions by consulting all the input elements in a global view, and meanwhile it is syntactic-aware by incorporating the syntax information from LA-GCN. Besides, a high-order interacted attention is introduced into the decoder for leveraging previously recognized triplets to help the current decision. Empirical experiments show that our framework significantly outperforms all existing graph-based methods on the CoNLL09 and Universal Proposition Bank datasets. In-depth analysis demonstrates that our model can effectively capture the correlations between syntactic and SRL structures.
SARG: A Novel Semi Autoregressive Generator for Multi-turn Incomplete Utterance Restoration
Authors: Huang Mengzuo , Li Feng , Zou Wuhe , Zhang Weidong
Published: September 2022

Dialogue systems in open domain have achieved great success due to the easily obtained single-turn corpus and the development of deep learning, but the multi-turn scenario is still a challenge because of the frequent coreference and information omission. In this paper, we investigate the incomplete utterance restoration which has brought general improvement over multi-turn dialogue systems in recent studies. Meanwhile, inspired by the autoregression for text generation and the sequence labeling for text editing, we propose a novel semi autoregressive generator (SARG) with the high efficiency and flexibility. Moreover, experiments on Restoration-200k show that our proposed model significantly outperforms the state-of-the-art models in terms of quality and inference speed.
Adaptive Beam Search Decoding for Discrete Keyphrase Generation
Authors: Huang Xiaoli , Xu Tongge , Jiao Lvan , Zu Yueran , Zhang Youmin
Published: September 2022

Keyphrase Generation compresses a document into some highly-summative phrases, which is an important task in natural language processing. Most state-of-the-art adopt greedy search or beam search decoding methods. These two decoding methods generate a large number of duplicated keyphrases and are time-consuming. Moreover, beam search only predicts a fixed number of keyphrases for different documents. In this paper, we propose an adaptive generation model-AdaGM, which is mainly inspired by the importance of the first words in keyphrase generation. In AdaGM, a novel reset state training mechanism is proposed to maximize the difference in the predicted first words. To ensure the discreteness and get an appropriate number of keyphrases according to the content of the document adaptively, we equip beam search with a highly effective filter mechanism. Experiments on five public datasets demonstrate the proposed model can generate marginally less duplicated and more accurate keyphrases. The codes of AdaGM are available at: https://github.com/huangxiaolist/adaGM.
The Gap on Gap: Tackling the Problem of Differing Data Distributions in Bias-Measuring Datasets
Authors: Kocijan Vid , Camburu Oana-Maria , Lukasiewicz Thomas
Published: September 2022

Diagnostic datasets that can detect biased models are an important prerequisite for bias reduction within natural language processing.
However, undesired patterns in the collected data can make such tests incorrect.
For example, if the feminine subset of a gender-bias-measuring coreference resolution dataset contains sentences with a longer average distance between the pronoun and the correct candidate, an RNN-based model may perform worse on this subset due to long-term dependencies.
In this work, we introduce a theoretically grounded method for weighting test samples to cope with such patterns in the test data.
We demonstrate the method on the GAP dataset for coreference resolution.
We annotate GAP with spans of all personal names and show that examples in the female subset contain more personal names and a longer distance between pronouns and their referents, potentially affecting the bias score in an undesired way.
Using our weighting method, we find the set of weights on the test instances that should be used for coping with these correlations,
and we re-evaluate 16 recently released coreference models.
Have We Solved The Hard Problem? It’s Not Easy! Contextual Lexical Contrast as a Means to Probe Neural Coherence
Authors: Lei Wenqiang , Miao Yisong , Xie Runpeng , Webber Bonnie , Liu Meichun , Chua Tat-Seng , Chen Nancy F.
Published: September 2022

Lexical cohesion is a fundamental mechanism for text which requires a pair of words to be interpreted as a certain type of lexical relation (e.g., similarity) to understand a coherent context; we refer to such relations as the contextual lexical relation. However, work on lexical cohesion has not modeled context comprehensively in considering lexical relations due to the lack of linguistic resources. In this paper, we take initial steps to address contextual lexical relations by focusing on the contrast relation, as it is a well-known relation though it is more subtle and relatively less resourced. We present a corpus named Cont 2 Lex to make Contextual Lexical Contrast Recognition a computationally feasible task. We benchmark this task with widely-adopted semantic representations; we discover that contextual embeddings (e.g. BERT) generally outperform static embeddings (e.g. Glove), but barely go beyond 70% in accuracy performance. In addition, we ﬁnd that all embeddings perform better when CLC occurs within the same sentence, suggesting possible limitations of current computational coherence models. Another intriguing discovery is the improvement of BERT in CLC is largely attributed to its modeling of CLC word pairs co-occurring with other word repetitions. Such observations imply that the progress made in lexical coherence modeling remains relatively primitive even for semantic representations such as BERT that have been empowering numerous standard NLP tasks to approach human benchmarks. Through presenting our corpus and benchmark, we attempt to seed initial discussions and endeavors in advancing semantic representations from modeling syntactic and semantic levels to coherence and discourse levels.
Improving the Efficiency and Effectiveness for BERT-based Entity Resolution
Authors: Li Bing , Miao Yukai , Wang Yaoshu , Sun Yifang , Wang Wei
Published: September 2022

BERT has set a new state-of-the-art performance on entity resolution (ER) task, largely owed to fine-tuning pre-trained language models and the deep pair-wise interaction. Albeit being remarkably effective, it comes with a steep increase in computational cost, as the deep-interaction requires to exhaustively compute every tuple pair to search for co-references. For ER task, it is often prohibitively expensive due to the large cardinality to be matched. To tackle this, we introduce a siamese network structure that independently encodes tuples using BERT but delays the pair-wise interaction via an enhanced alignment network. This siamese structure enables a dedicated blocking module to quickly filter out obviously dissimilar tuple pairs, and thus drastically reduces the cardinality of fine-grained matching. Further, the blocking and entity matching are integrated into a multi-task learning framework for facilitating both tasks. Extensive experiments on multiple datasets demonstrate that our model significantly outperforms state-of-the-art models (including BERT) in both efficiency and effectiveness.
Towards Faithfulness in Open Domain Table-to-text Generation from an Entity-centric View
Authors: Liu Tianyu , Zheng Xin , Chang Baobao , Sui Zhifang
Published: September 2022

In open domain table-to-text generation, we notice the unfaithful generation usually contains hallucinated entities which can not be aligned to any input table record. We thus try to evaluate the generation faithfulness with two entity-centric metrics: table record coverage and the ratio of hallucinated entities in text, both of which are shown to have strong agreement with human judgements. Then based on these metrics, we quantitatively analyze the correlation between training data quality and generation fidelity which indicates the potential usage of entity information in faithful generation. Motivated by these findings, we propose two methods for faithful generation: 1) augmented training by incorporating the auxiliary entity information, including both an augmented plan-based model and an unsupervised model and 2) training instance selection based on faithfulness ranking. We show these approaches improve generation fidelity in both full dataset setting and few shot setting by both automatic and human evaluations.
Variational Inference for Learning Representations of Natural Language Edits
Authors: Marrese-Taylor Edison , Reid Machel , Matsuo Yutaka
Published: September 2022

Document editing has become a pervasive component of production of information, with version control systems enabling edits to be efficiently stored and applied. In light of this, the task of learning distributed representations of edits has been recently proposed. With this in mind, we propose a novel approach that employs variational inference to learn a continuous latent space of vector representations to capture the underlying semantic information with regard to the document editing process. We achieve this by introducing a latent variable to explicitly model the aforementioned features. This latent variable is then combined with a document representation to guide the generation of an edited-version of this document. Additionally, to facilitate standardized automatic evaluation of edit representations, which has heavily relied on direct human input thus far, we also propose a suite of downstream tasks, PEER, specifically designed to measure the quality of edit representations in the context of natural language processing.
A Student-Teacher Architecture for Dialog Domain Adaptation Under the Meta-Learning Setting
Authors: Qian Kun , Wei Wei , Yu Zhou
Published: September 2022

Numerous new dialog domains are being created every day while collecting data for these domains is extremely costly since it involves human interactions. Therefore, it is essential to develop algorithms that can adapt to different domains efficiently when building data-driven dialog models. Most recent research on domain adaption focuses on giving the model a better initialization, rather than optimizing the adaptation process. We propose an efficient domain adaptive task-oriented dialog system model, which incorporates a meta-teacher model to emphasize the different impacts between generated tokens with respect to the context. We first train our base dialog model and meta-teacher model adversarially in a meta-learning setting on rich-resource domains. The meta-teacher learns to quantify the importance of tokens under different contexts across different domains. During adaptation, the meta-teacher guides the dialog model to focus on important tokens in order to achieve better adaptation efficiency. We evaluate our model on two multi-domain datasets, MultiWOZ and Google Schema-Guided Dialogue, and achieve state-of-the-art performance.
Co-GAT: A Co-Interactive Graph Attention Network for Joint Dialog Act Recognition and Sentiment Classification
Authors: Qin Libo , Li Zhouyang , Che Wanxiang , Ni Minheng , Liu Ting
Published: September 2022

In a dialog system, dialog act recognition and sentiment classification are two correlative tasks to capture speakers’ intentions, where dialog act and sentiment can indicate the explicit and the implicit intentions separately. The dialog context information (contextual information) and the mutual interaction information are two key factors that contribute to the two related tasks. Unfortunately, none of the existing approaches consider the two important sources of information simultaneously. In this paper, we propose a Co-Interactive Graph Attention Network (Co-GAT) to jointly perform the two tasks. The core module is a proposed co-interactive graph interaction layer where a cross-utterances connection and a cross-tasks connection are constructed and iteratively updated with each other, achieving to consider the two types of information simultaneously. Experimental results on two public datasets show that our model successfully captures the two sources of information and achieve the state-of-the-art performance. In addition, we find that the contributions from the contextual and mutual interaction information do not fully overlap with contextualized word representations (BERT, Roberta, XLNet).
RpBERT: A Text-image Relation Propagation-based BERT Model for Multimodal NER
Authors: Sun Lin , Wang Jiquan , Zhang Kai , Su Yindu , Weng Fangsheng
Published: September 2022

Recently multimodal named entity recognition (MNER) has utilized images to improve the accuracy of NER in tweets. However, most of the multimodal methods use attention mechanisms to extract visual clues regardless of whether the text and image are relevant. Practically, the irrelevant text-image pairs account for a large proportion in tweets. The visual clues that are unrelated to the texts will exert uncertain or even negative effects on multimodal model learning. In this paper, we introduce a method of text-image relation propagation into the multimodal BERT model. We integrate soft or hard gates to select visual clues and propose a multitask algorithm to train and validate the effects of relation propagation on the MNER datasets. In the experiments, we deeply analyze the changes in visual attention before and after the use of relation propagation. Our model achieves state-of-the-art performance on the MNER datasets.
A Bidirectional Multi-paragraph Reading Model for Zero-shot Entity Linking
Authors: Tang Hongyin , Sun Xingwu , Jin Beihong , Zhang Fuzheng
Published: September 2022

Recently, a zero-shot entity linking task is introduced to challenge the generalization ability of entity linking models. In this task, mentions must be linked to unseen entities and only the textual information is available. In order to make full use of the documents, previous work has proposed a BERT-based model which can only take fixed length of text as input. However, the key information for entity linking may exist in nearly everywhere of the documents thus the proposed model cannot capture them all. To leverage more textual information and enhance text understanding capability, we propose a bidirectional multi-paragraph reading model for the zero-shot entity linking task. Firstly, the model treats the mention context as a query and matches it with multiple paragraphs of the entity description documents. Then, the mention-aware entity representation obtained from the first step is used as a query to match multiple paragraphs in the document containing the mention through an entity-mention attention mechanism. In particular, a new pre-training strategy is employed to strengthen the representative ability. Experimental results show that our bidirectional model can capture long-range context dependencies and outperform the baseline model by 3-4% in terms of accuracy.