bluuebunny/crossref_metadata_2025 huggingface dataset:
On Self-Distilling Graph Neural Network
Authors: Chen Yuzhao , Bian Yatao , Xiao Xi , Rong Yu , Xu Tingyang , Huang Junzhou
Published: August 2021

Recently, the teacher-student knowledge distillation framework has demonstrated its potential in training Graph Neural Networks (GNNs). However, due to the difficulty of training over-parameterized GNN models, one may not easily obtain a satisfactory teacher model for distillation. Furthermore, the inefficient training process of teacher-student knowledge distillation also impedes its applications in GNN models. In this paper, we propose the first teacher-free knowledge distillation method for GNNs, termed GNN Self-Distillation (GNN-SD), that serves as a drop-in replacement of the standard training process. The method is built upon the proposed neighborhood discrepancy rate (NDR), which quantifies the non-smoothness of the embedded graph in an efficient way. Based on this metric, we propose the adaptive discrepancy retaining (ADR) regularizer to empower the transferability of knowledge that maintains high neighborhood discrepancy across GNN layers. We also summarize a generic GNN-SD framework that could be exploited to induce other distillation strategies. Experiments further prove the effectiveness and generalization of our approach, as it brings: 1) state-of-the-art GNN distillation performance with less training cost, 2) consistent and considerable performance enhancement for various popular backbones.
The Successful Ingredients of Policy Gradient Algorithms
Authors: Gronauer Sven , Gottwald Martin , Diepold Klaus
Published: August 2021

Despite the sublime success in recent years, the underlying mechanisms powering the advances of reinforcement learning are yet poorly understood. In this paper, we identify these mechanisms - which we call ingredients - in on-policy policy gradient methods and empirically determine their impact on the learning. To allow an equitable assessment, we conduct our experiments based on a unified and modular implementation. Our results underline the significance of recent algorithmic advances and demonstrate that reaching state-of-the-art performance may not need sophisticated algorithms but can also be accomplished by the combination of a few simple ingredients.
Robust Regularization with Adversarial Labelling of Perturbed Samples
Authors: Guo Xiaohui , Zhang Richong , Zheng Yaowei , Mao Yongyi
Published: August 2021

Recent researches have suggested that the predictive accuracy of neural network may contend with its adversarial robustness. This presents challenges in designing effective regularization schemes that also provide strong adversarial robustness. Revisiting Vicinal Risk Minimization (VRM) as a unifying regularization principle, we propose Adversarial Labelling of Perturbed Samples (ALPS) as a regularization scheme that aims at improving the generalization ability and adversarial robustness of the trained model. ALPS trains neural networks with synthetic samples formed by perturbing each authentic input sample towards another one along with an adversarially assigned label. The ALPS regularization objective is formulated as a min-max problem, in which the outer problem is minimizing an upper-bound of the VRM loss, and the inner problem is L1-ball constrained adversarial labelling on perturbed sample. The analytic solution to the induced inner maximization problem is elegantly derived, which enables computational efficiency. Experiments on the SVHN, CIFAR-10, CIFAR-100 and Tiny-ImageNet datasets show that the ALPS has a state-of-the-art regularization performance while also serving as an effective adversarial training scheme.
DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis
Authors: Henriksen Patrick , Lomuscio Alessio
Published: August 2021

We propose a novel, complete algorithm for the verification and analysis of feed-forward, ReLU-based neural networks. The algorithm, based on symbolic interval propagation, introduces a new method for determining split-nodes which evaluates the indirect effect that splitting has on the relaxations of successor nodes. We combine this with a new efficient linear-programming encoding of the splitting constraints to further improve the algorithm’s performance. The resulting implementation, DeepSplit, achieved speedups of 1–2 orders of magnitude and 21-34% fewer timeouts when compared to the current SoA toolkits.
SURPRISE! and When to Schedule It.
Authors: Huang Zhihuan , Xu Shengwei , Shan You , Lu Yuxuan , Kong Yuqing , Liu Tracy Xiao , Schoenebeck Grant
Published: August 2021

Information flow measures, over the duration of a game, the audience’s belief of who will win, and thus can reflect the amount of surprise in a game. To quantify the relationship between information flow and audiences' perceived quality, we conduct a case study where subjects watch one of the world’s biggest esports events, LOL S10. In addition to eliciting information flow, we also ask subjects to report their rating for each game. We find that the amount of surprise in the end of the game plays a dominant role in predicting the rating. This suggests the importance of incorporating when the surprise occurs, in addition to the amount of surprise, in perceived quality models. For content providers, it implies that everything else being equal, it is better for twists to be more likely to happen toward the end of a show rather than uniformly throughout.
Epsilon Best Arm Identification in Spectral Bandits
Authors: Kocák Tomáš , Garivier Aurélien
Published: August 2021

We propose an analysis of Probably Approximately Correct (PAC) identification of an ϵ-best arm in graph bandit models with Gaussian distributions. We consider finite but potentially very large bandit models where the set of arms is endowed with a graph structure, and we assume that the arms' expectations μ are smooth with respect to this graph. Our goal is to identify an arm whose expectation is at most ϵ below the largest of all means. We focus on the fixed-confidence setting: given a risk parameter δ, we consider sequential strategies that yield an ϵ-optimal arm with probability at least 1-δ. All such strategies use at least T*(μ)log(1/δ) samples, where R is the smoothness parameter. We identify the complexity term T*(μ) as the solution of a min-max problem for which we give a game-theoretic analysis and an approximation procedure. This procedure is the key element required by the asymptotically optimal Track-and-Stop strategy.
Transfer Learning via Optimal Transportation for Integrative Cancer Patient Stratification
Authors: Liu Ziyu , Shao Wei , Zhang Jie , Zhang Min , Huang Kun
Published: August 2021

The Stratification of early-stage cancer patients for the prediction of clinical outcome is a challenging task since cancer is associated with various molecular aberrations. A single biomarker often cannot provide sufficient information to stratify early-stage patients effectively. Understanding the complex mechanism behind cancer development calls for exploiting biomarkers from multiple modalities of data such as histopathology images and genomic data. The integrative analysis of these biomarkers sheds light on cancer diagnosis, subtyping, and prognosis. Another difficulty is that labels for early-stage cancer patients are scarce and not reliable enough for predicting survival times. Given the fact that different cancer types share some commonalities, we explore if the knowledge learned from one cancer type can be utilized to improve prognosis accuracy for another cancer type. We propose a novel unsupervised multi-view transfer learning algorithm to simultaneously analyze multiple biomarkers in different cancer types. We integrate multiple views using non-negative matrix factorization and formulate the transfer learning model based on the Optimal Transport theory to align features of different cancer types. We evaluate the stratification performance on three early-stage cancers from the Cancer Genome Atlas (TCGA) project. Comparing with other benchmark methods, our framework achieves superior accuracy for patient outcome prediction.
Evaluating Relaxations of Logic for Neural Networks: A Comprehensive Study
Authors: Medina Grespan Mattia , Gupta Ashim , Srikumar Vivek
Published: August 2021

Symbolic knowledge can provide crucial inductive bias for training neural models, especially in low data regimes. A successful strategy for incorporating such knowledge involves relaxing logical statements into sub-differentiable losses for optimization. In this paper, we study the question of how best to relax logical expressions that represent labeled examples and knowledge about a problem; we focus on sub-differentiable t-norm relaxations of logic. We present theoretical and empirical criteria for characterizing which relaxation would perform best in various scenarios. In our theoretical study driven by the goal of preserving tautologies, the Lukasiewicz t-norm performs best. However, in our empirical analysis on the text chunking and digit recognition tasks, the product t-norm achieves best predictive performance. We analyze this apparent discrepancy, and conclude with a list of best practices for defining loss functions via logic.
Minimization of Limit-Average Automata
Authors: Michaliszyn Jakub , Otop Jan
Published: August 2021

LimAvg-automata are weighted automata over infinite words that aggregate weights along runs with the limit-average value function.

In this paper, we study the minimization problem for (deterministic) LimAvg-automata.

Our main contribution is an equivalence relation on words characterizing LimAvg-automata, i.e.,

the equivalence classes of this relation correspond to states of an equivalent LimAvg-automaton.

In contrast to relations characterizing DFA, our relation depends not only on the function defined by the target automaton, but also on its structure.

We show two applications of this relation.

First, we present a minimization algorithm for LimAvg-automata, which returns a minimal LimAvg-automaton among those equivalent and structurally similar to the input one.

Second, we present an extension of Angluin's L^*-algorithm with syntactic queries, which learns in polynomial time a LimAvg-automaton equivalent to the target one.
Contrastive Losses and Solution Caching for Predict-and-Optimize
Authors: Mulamba Maxime , Mandi Jayanta , Diligenti Michelangelo , Lombardi Michele , Bucarey Victor , Guns Tias
Published: August 2021

Many decision-making processes involve solving a combinatorial optimization problem with uncertain input that can be estimated from historic data. Recently, problems in this class have been successfully addressed via end-to-end learning approaches, which rely on solving one optimization problem for each training instance at every epoch. In this context, we provide two distinct contributions. First, we use a Noise Contrastive approach to motivate a family of surrogate loss functions, based on viewing non-optimal solutions as negative examples. Second, we address a major bottleneck of all predict-and-optimize approaches, i.e. the need to frequently recompute optimal solutions at training time. This is done via a solver-agnostic solution caching scheme, and by replacing optimization calls with a lookup in the solution cache. The method is formally based on an inner approximation of the feasible space and, combined with a cache lookup strategy, provides a controllable trade-off between training time and accuracy of the loss approximation. We empirically show that even a very slow growth rate is enough to match the quality of state-of-the-art methods, at a fraction of the computational cost.
TIDOT: A Teacher Imitation Learning Approach for Domain Adaptation with Optimal Transport
Authors: Nguyen Tuan , Le Trung , Dam Nhan , Tran Quan Hung , Nguyen Truyen , Phung Dinh
Published: August 2021

Using the principle of imitation learning and the theory of optimal transport we propose in this paper a novel model for unsupervised domain adaptation named Teacher Imitation Domain Adaptation with Optimal Transport (TIDOT). Our model includes two cooperative agents: a teacher and a student. The former agent is trained to be an expert on labeled data in the source domain, whilst the latter one aims to work with unlabeled data in the target domain. More specifically, optimal transport is applied to quantify the total of the distance between embedded distributions of the source and target data in the joint space, and the distance between predictive distributions of both agents, thus by minimizing this quantity TIDOT could mitigate not only the data shift but also the label shift. Comprehensive empirical studies show that TIDOT outperforms existing state-of-the-art performance on benchmark datasets.
Meta-Reinforcement Learning by Tracking Task Non-stationarity
Authors: Poiani Riccardo , Tirinzoni Andrea , Restelli Marcello
Published: August 2021

Many real-world domains are subject to a structured non-stationarity which affects the agent's goals and the environmental dynamics. Meta-reinforcement learning (RL) has been shown successful for training agents that quickly adapt to related tasks. However, most of the existing meta-RL algorithms for non-stationary domains either make strong assumptions on the task generation process or require sampling from it at training time. In this paper, we propose a novel algorithm (TRIO) that optimizes for the future by explicitly tracking the task evolution through time. At training time, TRIO learns a variational module to quickly identify latent parameters from experience samples. This module is learned jointly with an optimal exploration policy that takes task uncertainty into account. At test time, TRIO tracks the evolution of the latent parameters online, hence reducing the uncertainty over future tasks and obtaining fast adaptation through the meta-learned policy. Unlike most existing methods, TRIO does not assume Markovian task-evolution processes, it does not require information about the non-stationarity at training time, and it captures complex changes undergoing in the environment. We evaluate our algorithm on different simulated problems and show it outperforms competitive baselines.
Multi-Agent Reinforcement Learning for Automated Peer-to-Peer Energy Trading in Double-Side Auction Market
Authors: Qiu Dawei , Wang Jianhong , Wang Junkai , Strbac Goran
Published: August 2021

With increasing prosumers employed with distributed energy resources (DER), advanced energy management has become increasingly important. To this end, integrating demand-side DER into electricity market is a trend for future smart grids. The double-side auction (DA) market is viewed as a promising peer-to-peer (P2P) energy trading mechanism that enables interactions among prosumers in a distributed manner. To achieve the maximum profit in a dynamic electricity market, prosumers act as price makers to simultaneously optimize their operations and trading strategies. However, the traditional DA market is difficult to be explicitly modelled due to its complex clearing algorithm and the stochastic bidding behaviors of the participants. For this reason, in this paper we model this task as a multi-agent reinforcement learning (MARL) problem and propose an algorithm called DA-MADDPG that is modified based on MADDPG by abstracting the other agents’ observations and actions through the DA market public information for each agent’s critic. The experiments show that 1) prosumers obtain more economic benefits in P2P energy trading w.r.t. the conventional electricity market independently trading with the utility company; and 2) DA-MADDPG performs better than the traditional Zero Intelligence (ZI) strategy and the other MARL algorithms, e.g., IQL, IDDPG, IPPO and MADDPG.
Physics-aware Spatiotemporal Modules with Auxiliary Tasks for Meta-Learning
Authors: Seo Sungyong , Meng Chuizheng , Rambhatla Sirisha , Liu Yan
Published: August 2021

Modeling the dynamics of real-world physical systems is critical for spatiotemporal prediction tasks, but challenging when data is limited. The scarcity of real-world data and the difficulty in reproducing the data distribution hinder directly applying meta-learning techniques. Although the knowledge of governing partial differential equations (PDE) of the data can be helpful for the fast adaptation to few observations, it is mostly infeasible to exactly find the equation for observations in real-world physical systems. In this work, we propose a framework, physics-aware meta-learning with auxiliary tasks, whose spatial modules incorporate PDE-independent knowledge and temporal modules utilize the generalized features from the spatial modules to be adapted to the limited data, respectively. The framework is inspired by a local conservation law expressed mathematically as a continuity equation and does not require the exact form of governing equation to model the spatiotemporal observations. The proposed method mitigates the need for a large number of real-world tasks for meta-learning by leveraging spatial information in simulated data to meta-initialize the spatial modules. We apply the proposed framework to both synthetic and real-world spatiotemporal prediction tasks and demonstrate its superior performance with limited observations.
Unsupervised Progressive Learning and the STAM Architecture
Authors: Smith James , Taylor Cameron , Baer Seth , Dovrolis Constantine
Published: August 2021

We first pose the Unsupervised Progressive Learning (UPL) problem: an online

representation learning problem in which the learner observes a non-stationary

and unlabeled data stream, learning a growing number of features that persist

over time even though the data is not stored or replayed. To solve the UPL

problem we propose the Self-Taught Associative Memory (STAM) architecture.

Layered hierarchies of STAM modules learn based on a combination of online

clustering, novelty detection, forgetting outliers, and storing only prototypical

features rather than specific examples. We evaluate STAM representations using

clustering and classification tasks. While there are no existing learning scenarios

that are directly comparable to UPL, we compare the STAM architecture with two

recent continual learning models, Memory Aware Synapses (MAS) and Gradient

Episodic Memories (GEM), after adapting them in the UPL setting.
Towards Reducing Biases in Combining Multiple Experts Online
Authors: Sun Yi , Ramírez Díaz Iván , Cuesta Infante Alfredo , Veeramachaneni Kalyan
Published: August 2021

In many real life situations, including job and loan applications, gatekeepers must make justified and fair real-time decisions about a person’s fitness for a particular opportunity. In this paper, we aim to accomplish approximate group fairness in an online stochastic decision-making process, where the fairness metric we consider is equalized odds. Our work follows from the classical learning-from-experts scheme, assuming a finite set of classifiers (human experts, rules, options, etc) that cannot be modified. We run separate instances of the algorithm for each label class as well as sensitive groups, where the probability of choosing each instance is optimized for both fairness and regret. Our theoretical results show that approximately equalized odds can be achieved without sacrificing much regret. We also demonstrate the performance of the algorithm on real data sets commonly used by the fairness community.
Strategyproof Randomized Social Choice for Restricted Sets of Utility Functions
Authors: Lederer Patrick
Published: August 2021

When aggregating preferences of multiple agents, strategyproofness is a fundamental requirement. For randomized voting rules, so-called social decision schemes (SDSs), strategyproofness is usually formalized with the help of utility functions. A classic result shown by Gibbard in 1977 characterizes the set of SDSs that are strategyproof with respect to all utility functions and shows that these SDSs are either indecisive or unfair. For finding more insights into the trade-off between strategyproofness and decisiveness, we propose the notion of U-strategyproofness which requires that only voters with a utility function in the set U cannot manipulate. In particular, we show that if the utility functions in U value the best alternative much more than other alternatives, there are U-strategyproof SDSs that choose an alternative with probability 1 whenever all but k voters rank it first. We also prove for rank-based SDSs that this large gap in the utilities is required to be strategyproof and that the gap must increase in k. On the negative side, we show that U-strategyproofness is incompatible with Condorcet-consistency if U satisfies minimal symmetry conditions and there are at least four alternatives. For three alternatives, the Condorcet rule can be characterized based on U-strategyproofness for the set U containing all equi-distant utility functions.
Robust Adversarial Imitation Learning via Adaptively-Selected Demonstrations
Authors: Wang Yunke , Xu Chang , Du Bo
Published: August 2021

The agent in imitation learning (IL) is expected to mimic the behavior of the expert. Its performance relies highly on the quality of given expert demonstrations. However, the assumption that collected demonstrations are optimal cannot always hold in real-world tasks, which would seriously influence the performance of the learned agent. In this paper, we propose a robust method within the framework of Generative Adversarial Imitation Learning (GAIL) to address imperfect demonstration issue, in which good demonstrations can be adaptively selected for training while bad demonstrations are abandoned. Specifically, a binary weight is assigned to each expert demonstration to indicate whether to select it for training. The reward function in GAIL is employed to determine this weight (i.e. higher reward results in higher weight). Compared to some existing solutions that require some auxiliary information about this weight, we set up the connection between weight and model so that we can jointly optimize GAIL and learn the latent weight. Besides hard binary weighting, we also propose a soft weighting scheme. Experiments in the Mujoco demonstrate the proposed method outperforms other GAIL-based methods when dealing with imperfect demonstrations.
Reinforcement Learning Based Sparse Black-box Adversarial Attack on Video Recognition Models
Authors: Wang Zeyuan , Sha Chaofeng , Yang Su
Published: August 2021

We explore the black-box adversarial attack on video recognition models. Attacks are only performed on selected key regions and key frames to reduce the high computation cost of searching adversarial perturbations on a video due to its high dimensionality. To select key frames, one way is to use heuristic algorithms to evaluate the importance of each frame and choose the essential ones. However, it is time inefficient on sorting and searching. In order to speed up the attack process, we propose a reinforcement learning based frame selection strategy. Specifically, the agent explores the difference between the original class and the target class of videos to make selection decisions. It receives rewards from threat models which indicate the quality of the decisions. Besides, we also use saliency detection to select key regions and only estimate the sign of gradient instead of the gradient itself in zeroth order optimization to further boost the attack process. We can use the trained model directly in the untargeted attack or with little fine-tune in the targeted attack, which saves computation time. A range of empirical results on real datasets demonstrate the effectiveness and efficiency of the proposed method.
Budget-feasible Mechanisms for Representing Groups of Agents Proportionally
Authors: Liu Xiang , Chan Hau , Li Minming , Wu Weiwei
Published: August 2021

In this paper, we consider the problem of designing budget-feasible mechanisms

for selecting agents with private costs from various groups to ensure proportional representation, where the minimum proportion of the selected agents from each group is maximized. Depending on agents' membership in the groups, we consider two main models: single group setting where each agent belongs to only one group, and multiple group setting where each agent may belong to multiple groups. We propose novel budget-feasible proportion-representative mechanisms for these models, which can select representative agents from different groups. The proposed mechanisms guarantee theoretical properties of individual rationality, budget-feasibility, truthfulness, and approximation performance on proportional representation.
Clustering-Induced Adaptive Structure Enhancing Network for Incomplete Multi-View Data
Authors: Xue Zhe , Du Junping , Zheng Changwei , Song Jie , Ren Wenqi , Liang Meiyu
Published: August 2021

Incomplete multi-view clustering aims to cluster samples with missing views, which has drawn more and more research interest. Although several methods have been developed for incomplete multi-view clustering, they fail to extract and exploit the comprehensive global and local structure of multi-view data, so their clustering performance is limited. This paper proposes a Clustering-induced Adaptive Structure Enhancing Network (CASEN) for incomplete multi-view clustering, which is an end-to-end trainable framework that jointly conducts multi-view structure enhancing and data clustering. Our method adopts multi-view autoencoder to infer the missing features of the incomplete samples. Then, we perform adaptive graph learning and graph convolution on the reconstructed complete multi-view data to effectively extract data structure. Moreover, we use multiple kernel clustering to integrate the global and local structure for clustering, and the clustering results in turn are used to enhance the data structure. Extensive experiments on several benchmark datasets demonstrate that our method can comprehensively obtain the structure of incomplete multi-view data and achieve superior performance compared to the other methods.
Improving Welfare in One-Sided Matchings using Simple Threshold Queries
Authors: Ma Thomas , Menon Vijay , Larson Kate
Published: August 2021

We study one-sided matching problems where each agent must be assigned at most one object. In this classic problem it is often assumed that agents specify only ordinal preferences over objects and the goal is to return a matching that satisfies some desirable property such as Pareto optimality or rank-maximality. However, agents may have cardinal utilities describing their preference intensities and ignoring this can result in welfare loss. We investigate how to elicit additional cardinal information from agents using simple threshold queries and use it in turn to design algorithms that return a matching satisfying a desirable matching property, while also achieving a good approximation to the optimal welfare among all matchings satisfying that property. Overall, our results show how one can improve welfare by even non-adaptively asking agents for just one bit of extra information per object.
Generalized Kings and Single-Elimination Winners in Random Tournaments
Authors: Manurangsi Pasin , Suksompong Warut
Published: August 2021

Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized king: an alternative is said to be a k-king if it can reach every other alternative in the tournament via a directed path of length at most k. In this paper, we provide an almost complete characterization of the probability threshold such that all, a large number, or a small number of alternatives are k-kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the regime of constant k, with the biggest change being between k = 2 and k = 3. In addition, we establish an asymptotically tight bound on the probability threshold for which all alternatives are likely able to win a single-elimination tournament under some bracket.
Independence-aware Advantage Estimation
Authors: Zhang Pushi , Zhao Li , Liu Guoqing , Bian Jiang , Huang Minlie , Qin Tao , Liu Tie-Yan
Published: August 2021

Most of existing advantage function estimation methods in reinforcement learning suffer from the problem of high variance, which scales unfavorably with the time horizon. To address this challenge, we propose to identify the independence property between current action and future states in environments, which can be further leveraged to effectively reduce the variance of the advantage estimation. In particular, the recognized independence property can be naturally utilized to construct a novel importance sampling advantage estimator with close-to-zero variance even when the Monte-Carlo return signal yields a large variance. To further remove the risk of the high variance introduced by the new estimator, we combine it with existing Monte-Carlo estimator via a reward decomposition model learned by minimizing the estimation variance. Experiments demonstrate that our method achieves higher sample efficiency compared with existing advantage estimation methods in complex environments.
Private Stochastic Non-convex Optimization with Improved Utility Rates
Authors: Zhang Qiuchen , Ma Jing , Lou Jian , Xiong Li
Published: August 2021

We study the differentially private (DP) stochastic nonconvex optimization with a focus on its under-studied utility measures in terms of the expected excess empirical and population risks. While the excess risks are extensively studied for convex optimization, they are rarely studied for nonconvex optimization, especially the expected population risk. For the convex case, recent studies show that it is possible for private optimization to achieve the same order of excess population risk as to the nonprivate optimization under certain conditions. It still remains an open question for the nonconvex case whether such ideal excess population risk is achievable.

In this paper, we progress towards an affirmative answer to this open problem: DP nonconvex optimization is indeed capable of achieving the same excess population risk as to the nonprivate algorithm in most common parameter regimes, under certain conditions (i.e., well-conditioned nonconvexity). We achieve such improved utility rates compared to existing results by designing and analyzing the stagewise DP-SGD with early momentum algorithm. We obtain both excess empirical risk and excess population risk to achieve differential privacy. Our algorithm also features the first known results of excess and population risks for DP-SGD with momentum. Experiment results on both shallow and deep neural networks when respectively applied to simple and complex real datasets corroborate the theoretical results.
Model-based Multi-agent Policy Optimization with Adaptive Opponent-wise Rollouts
Authors: Zhang Weinan , Wang Xihuai , Shen Jian , Zhou Ming
Published: August 2021

This paper investigates the model-based methods in multi-agent reinforcement learning (MARL). We specify the dynamics sample complexity and the opponent sample complexity in MARL, and conduct a theoretic analysis of return discrepancy upper bound. To reduce the upper bound with the intention of low sample complexity during the whole learning process, we propose a novel decentralized model-based MARL method, named Adaptive Opponent-wise Rollout Policy Optimization (AORPO). In AORPO, each agent builds its multi-agent environment model, consisting of a dynamics model and multiple opponent models, and trains its policy with the adaptive opponent-wise rollout. We further prove the theoretic convergence of AORPO under reasonable assumptions. Empirical experiments on competitive and cooperative tasks demonstrate that AORPO can achieve improved sample efficiency with comparable asymptotic performance over the compared MARL methods.
Rethink the Connections among Generalization, Memorization, and the Spectral Bias of DNNs
Authors: Zhang Xiao , Xiong Haoyi , Wu Dongrui
Published: August 2021

Over-parameterized deep neural networks (DNNs) with sufficient capacity to memorize random noise can achieve excellent generalization performance, challenging the bias-variance trade-off in classical learning theory. Recent studies claimed that DNNs first learn simple patterns and then memorize noise; some other works showed a phenomenon that DNNs have a spectral bias to learn target functions from low to high frequencies during training. However, we show that the monotonicity of the learning bias does not always hold: under the experimental setup of deep double descent, the high-frequency components of DNNs diminish in the late stage of training, leading to the second descent of the test error. Besides, we find that the spectrum of DNNs can be applied to indicating the second descent of the test error, even though it is calculated from the training set only.
Uncertainty-aware Binary Neural Networks
Authors: Zhao Junhe , Yang Linlin , Zhang Baochang , Guo Guodong , Doermann David
Published: August 2021

Binary Neural Networks (BNN) are promising machine learning solutions for deployment on resource-limited devices. Recent approaches to training BNNs have produced impressive results, but minimizing the drop in accuracy from full precision networks is still challenging. One reason is that conventional BNNs ignore the uncertainty caused by weights that are near zero, resulting in the instability or frequent flip while learning. In this work, we investigate the intrinsic uncertainty of vanishing near-zero weights, making the training vulnerable to instability. We introduce an uncertainty-aware BNN (UaBNN) by leveraging a new mapping function called certainty-sign (c-sign) to reduce these weights' uncertainties. Our c-sign function is the first to train BNNs with a decreasing uncertainty for binarization. The approach leads to a controlled learning process for BNNs. We also introduce a simple but effective method to measure the uncertainty-based on a Gaussian function. Extensive experiments demonstrate that our method improves multiple BNN methods by maintaining stability of training, and achieves a higher performance over prior arts.
You Get What You Sow: High Fidelity Image Synthesis with a Single Pretrained Network
Authors: Zhu Kefeng , Tong Peilin , Kan Hongwei , Li Rengang
Published: August 2021

State-of-the-art image synthesis methods are mostly based on generative adversarial networks and require large dataset and extensive training. Although the model-inversion-oriented branch of methods eliminate the training requirement, the quality of the resulting image tends to be limited due to the lack of sufficient natural and class-specific information. In this paper, we introduce a novel strategy for high fidelity image synthesis with a single pretrained classification network. The strategy includes a class-conditional natural regularization design and a corresponding metadata collecting procedure for different scenarios. We show that our method can synthesize high quality natural images that closely follow the features of one or more given seed images. Moreover, our method achieves surprisingly decent results in the task of sketch-based image synthesis without training. Finally, our method further improves the performance in terms of accuracy and efficiency in the data-free knowledge distillation task.
SPADE: A Semi-supervised Probabilistic Approach for Detecting Errors in Tables
Authors: Pham Minh , Knoblock Craig A. , Chen Muhao , Vu Binh , Pujara Jay
Published: August 2021

Error detection is one of the most important steps in data cleaning and usually requires extensive human interaction to ensure quality. Existing supervised methods in error detection require a significant amount of training data while unsupervised methods rely on fixed inductive biases, which are usually hard to generalize, to solve the problem. In this paper, we present SPADE, a novel semi-supervised probabilistic approach for error detection. SPADE introduces a novel probabilistic active learning model, where the system suggests examples to be labeled based on the agreements between user labels and indicative signals, which are designed to capture potential errors. SPADE uses a two-phase data augmentation process to enrich a dataset before training a deep learning classifier to detect unlabeled errors. In our evaluation, SPADE achieves an average F1-score of 0.91 over five datasets and yields a 10% improvement compared with the state-of-the-art systems.
Learning Within an Instance for Designing High-Revenue Combinatorial Auctions
Authors: Balcan Maria-Florina , Prasad Siddharth , Sandholm Tuomas
Published: August 2021

We develop a new framework for designing truthful, high-revenue (combinatorial) auctions for limited supply. Our mechanism learns within an instance. It generalizes and improves over previously-studied random-sampling mechanisms. It first samples a participatory group of bidders, then samples several learning groups of bidders from the remaining pool of bidders, learns a high-revenue auction from the learning groups, and finally runs that auction on the participatory group. Previous work on random-sampling mechanisms focused primarily on unlimited supply. Limited supply poses additional significant technical challenges, since allocations of items to bidders must be feasible. We prove guarantees on the performance of our mechanism based on a market-shrinkage term and a new complexity measure we coin partition discrepancy. Partition discrepancy simultaneously measures the intrinsic complexity of the mechanism class and the uniformity of the set of bidders. We then introduce new auction classes that can be parameterized in a way that does not depend on the number of bidders participating, and prove strong guarantees for these classes. We show how our mechanism can be implemented efficiently by leveraging practically-efficient routines for solving winner determination. Finally, we show how to use structural revenue maximization to decide what auction class to use with our framework when there is a constraint on the number of learning groups.
Online Credit Payment Fraud Detection via Structure-Aware Hierarchical Recurrent Neural Network
Authors: Lin Wangli , Sun Li , Zhong Qiwei , Liu Can , Feng Jinghua , Ao Xiang , Yang Hao
Published: August 2021

Online credit payment fraud detection plays a critical role in financial institutions due to the growing volume of fraudulent transactions. Recently, researchers have shown an increased interest in capturing users’ dynamic and evolving fraudulent tendencies from their behavior sequences. However, most existing methodologies for sequential modeling overlook the intrinsic structure information of web pages. In this paper, we adopt multi-scale behavior sequence generated from different granularities of web page structures and propose a model named SAH-RNN to consume the multi-scale behavior sequence for online payment fraud detection. The SAH-RNN has stacked RNN layers in which upper layers modeling for compendious behaviors are updated less frequently and receive the summarized representations from lower layers. A dual attention is devised to capture the impacts on both sequential information within the same sequence and structural information among different granularity of web pages. Experimental results on a large-scale real-world transaction dataset from Alibaba show that our proposed model outperforms state-of-the-art models. The code is available at https://github.com/WangliLin/SAH-RNN.
Solving Large-Scale Extensive-Form Network Security Games via Neural Fictitious Self-Play
Authors: Xue Wanqi , Zhang Youzhi , Li Shuxin , Wang Xinrun , An Bo , Yeo Chai Kiat
Published: August 2021

Securing networked infrastructures is important in the real world. The problem of deploying security resources to protect against an attacker in networked domains can be modeled as Network Security Games (NSGs). Unfortunately, existing approaches, including the deep learning-based approaches, are inefficient to solve large-scale extensive-form NSGs. In this paper, we propose a novel learning paradigm, NSG-NFSP, to solve large-scale extensive-form NSGs based on Neural Fictitious Self-Play (NFSP). Our main contributions include: i) reforming the best response (BR) policy network in NFSP to be a mapping from action-state pair to action-value, to make the calculation of BR possible in NSGs; ii) converting the average policy network of an NFSP agent into a metric-based classifier, helping the agent to assign distributions only on legal actions rather than all actions; iii) enabling NFSP with high-level actions, which can benefit training efficiency and stability in NSGs; and iv) leveraging information contained in graphs of NSGs by learning efficient graph node embeddings. Our algorithm significantly outperforms state-of-the-art algorithms in both scalability and solution quality.
Long-term, Short-term and Sudden Event: Trading Volume Movement Prediction with Graph-based Multi-view Modeling
Authors: Zhao Liang , Li Wei , Bao Ruihan , Harimoto Keiko , Wu Yunfang , Sun Xu
Published: August 2021

Trading volume movement prediction is the key in a variety of financial applications. Despite its importance, there is few research on this topic because of its requirement for comprehensive understanding of information from different sources. For instance, the relation between multiple stocks, recent transaction data and suddenly released events are all essential for understanding trading market. However, most of the previous methods only take the fluctuation information of the past few weeks into consideration, thus yielding poor performance. To handle this issue, we propose a graph-based approach that can incorporate multi-view information, i.e., long-term stock trend, short-term fluctuation and sudden events information jointly into a temporal heterogeneous graph. Besides, our method is equipped with deep canonical analysis to highlight the correlations between different perspectives of fluctuation for better prediction. Experiment results show that our method outperforms strong baselines by a large margin.
Shortlisting Rules and Incentives in an End-to-End Model for Participatory Budgeting
Authors: Rey Simon , Endriss Ulle , de Haan Ronald
Published: August 2021

We introduce an end-to-end model for participatory

budgeting grounded in social choice theory. Our

model accounts for the interplay between the two

stages commonly encountered in real-life partici-

patory budgeting. In the first stage participants pro-

pose projects to be shortlisted, while in the second

stage they vote on which of the shortlisted projects

should be funded. Prior work of a formal nature has

focused on analysing the second stage only. We in-

troduce several shortlisting rules for the first stage

and analyse them in both normative and algorith-

mic terms. Our main focus is on the incentives of

participants to engage in strategic behaviour during

the first stage, in which they need to reason about

how their proposals will impact the range of strate-

gies available to everyone in the second stage.
Generating Senses and RoLes: An End-to-End Model for Dependency- and Span-based Semantic Role Labeling
Authors: Blloshmi Rexhina , Conia Simone , Tripodi Rocco , Navigli Roberto
Published: August 2021

Despite the recent great success of the sequence-to-sequence paradigm in Natural Language Processing, the majority of current studies in Semantic Role Labeling (SRL) still frame the problem as a sequence labeling task.

In this paper we go against the flow and propose GSRL (Generating Senses and RoLes), the first sequence-to-sequence model for end-to-end SRL.

Our approach benefits from recently-proposed decoder-side pretraining techniques to generate both sense and role labels for all the predicates in an input sentence at once, in an end-to-end fashion.

Evaluated on standard gold benchmarks, GSRL achieves state-of-the-art results in both dependency- and span-based English SRL, proving empirically that our simple generation-based model can learn to produce complex predicate-argument structures.

Finally, we propose a framework for evaluating the robustness of an SRL model in a variety of synthetic low-resource scenarios which can aid human annotators in the creation of better, more diverse, and more challenging gold datasets.

We release GSRL at github.com/SapienzaNLP/gsrl.
Improving Context-Aware Neural Machine Translation with Source-side Monolingual Documents
Authors: Chen Linqing , Li Junhui , Gong Zhengxian , Duan Xiangyu , Chen Boxing , Luo Weihua , Zhang Min , Zhou Guodong
Published: August 2021

Document context-aware machine translation remains challenging due to the lack of large-scale document parallel corpora. To make full use of source-side monolingual documents for context-aware NMT, we propose a Pre-training approach with Global Context (PGC). In particular, we first propose a novel self-supervised pre-training task, which contains two training objectives: (1) reconstructing the original sentence from a corrupted version; (2) generating a gap sentence from its left and right neighbouring sentences. Then we design a universal model for PGC which consists of a global context encoder, a sentence encoder and a decoder, with similar architecture to typical context-aware NMT models. We evaluate the effectiveness and generality of our pre-trained PGC model by adapting it to various downstream context-aware NMT models. Detailed experimentation on four different translation tasks demonstrates that our PGC approach significantly improves the translation performance of context-aware NMT. For example, based on the state-of-the-art SAN model, we achieve an averaged improvement of 1.85 BLEU scores and 1.59 Meteor scores on the four translation tasks.
Modelling General Properties of Nouns by Selectively Averaging Contextualised Embeddings
Authors: Li Na , Bouraoui Zied , Camacho-Collados Jose , Espinosa-Anke Luis , Gu Qing , Schockaert Steven
Published: August 2021

While the success of pre-trained language models has largely eliminated the need for high-quality static word vectors in many NLP applications, static word vectors continue to play an important role in tasks where word meaning needs to be modelled in the absence of linguistic context. In this paper, we explore how the contextualised embeddings predicted by BERT can be used to produce high-quality word vectors for such domains, in particular related to knowledge base completion, where our focus is on capturing the semantic properties of nouns. We find that a simple strategy of averaging the contextualised embeddings of masked word mentions leads to vectors that outperform the static word vectors learned by BERT, as well as those from standard word embedding models, in property induction tasks. We notice in particular that masking target words is critical to achieve this strong performance, as the resulting vectors focus less on idiosyncratic properties and more on general semantic properties. Inspired by this view, we propose a filtering strategy which is aimed at removing the most idiosyncratic mention vectors, allowing us to obtain further performance gains in property induction.