bluuebunny/crossref_metadata_2025 huggingface dataset:
PAnDR: Fast Adaptation to New Environments from Offline Experiences via Decoupling Policy and Environment Representations
Authors: Sang Tong , Tang Hongyao , Ma Yi , Hao Jianye , Zheng Yan , Meng Zhaopeng , Li Boyan , Wang Zhen
Published: July 2022

Deep Reinforcement Learning (DRL) has been a promising solution to many complex decision-making problems. Nevertheless, the notorious weakness in generalization among environments prevent widespread application of DRL agents in real-world scenarios. Although advances have been made recently, most prior works assume sufficient online interaction on training environments, which can be costly in practical cases.

To this end, we focus on an offline-training-online-adaptation setting,

in which the agent first learns from offline experiences collected in environments with different dynamics and then performs online policy adaptation in environments with new dynamics. In this paper, we propose Policy Adaptation with Decoupled Representations (PAnDR) for fast policy adaptation.

In offline training phase, the environment representation and policy representation are learned through contrastive learning and policy recovery, respectively. The representations are further refined by mutual information optimization to make them more decoupled and complete. With learned representations, a Policy-Dynamics Value Function (PDVF) network is trained to approximate the values for different combinations of policies and environments from offline experiences. In online adaptation phase, with the environment context inferred from few experiences collected in new environments, the policy is optimized by gradient ascent with respect to the PDVF. Our experiments show that PAnDR outperforms existing algorithms in several representative policy adaptation problems.
MMT: Multi-way Multi-modal Transformer for Multimodal Learning
Authors: Tang Jiajia , Li Kang , Hou Ming , Jin Xuanyu , Kong Wanzeng , Ding Yu , Zhao Qibin
Published: July 2022

The heart of multimodal learning research lies the challenge of effectively exploiting fusion representations among multiple modalities.However, existing two-way cross-modality unidirectional attention could only exploit the intermodal interactions from one source to one target modality. This indeed fails to unleash the complete expressive power of multimodal fusion with restricted number of modalities and fixed interactive direction.In this work, the multiway multimodal transformer (MMT) is proposed to simultaneously explore multiway multimodal intercorrelations for each modality via single block rather than multiple stacked cross-modality blocks. The core idea of MMT is the multiway multimodal attention, where the multiple modalities are leveraged to compute the multiway attention tensor. This naturally benefits us to exploit comprehensive many-to-many multimodal interactive paths. Specifically, the multiway tensor is comprised of multiple interconnected modality-aware core tensors that consist of the intramodal interactions. Additionally, the tensor contraction operation is utilized to investigate intermodal dependencies between distinct core tensors.Essentially, our tensor-based multiway structure allows for easily extending MMT to the case associated with an arbitrary number of modalities. Taking MMT as the basis, the hierarchical network is further established to recursively transmit the low-level multiway multimodal interactions to high-level ones. The experiments demonstrate that MMT can achieve state-of-the-art or comparable performance.
Recipe2Vec: Multi-modal Recipe Representation Learning with Graph Neural Networks
Authors: Tian Yijun , Zhang Chuxu , Guo Zhichun , Ma Yihong , Metoyer Ronald , Chawla Nitesh V.
Published: July 2022

Learning effective recipe representations is essential in food studies. Unlike what has been developed for image-based recipe retrieval or learning structural text embeddings, the combined effect of multi-modal information (i.e., recipe images, text, and relation data) receives less attention. In this paper, we formalize the problem of multi-modal recipe representation learning to integrate the visual, textual, and relational information into recipe embeddings. In particular, we first present Large-RG, a new recipe graph data with over half a million nodes, making it the largest recipe graph to date. We then propose Recipe2Vec, a novel graph neural network based recipe embedding model to capture multi-modal information. Additionally, we introduce an adversarial attack strategy to ensure stable learning and improve performance. Finally, we design a joint objective function of node classification and adversarial learning to optimize the model. Extensive experiments demonstrate that Recipe2Vec outperforms state-of-the-art baselines on two classic food study tasks, i.e., cuisine category classification and region prediction. Dataset and codes are available at https://github.com/meettyj/Recipe2Vec.
Approximate Exploitability: Learning a Best Response
Authors: Timbers Finbarr , Bard Nolan , Lockhart Edward , Lanctot Marc , Schmid Martin , Burch Neil , Schrittwieser Julian , Hubert Thomas , Bowling Michael
Published: July 2022

Researchers have shown that neural networks are vulnerable to adversarial examples and subtle environment changes. The resulting errors can look like blunders to humans, eroding trust in these agents. In prior games research, agent evaluation often focused on the in-practice game outcomes. Such evaluation typically fails to evaluate robustness to worst-case outcomes. Computer poker research has examined how to assess such worst-case performance. Unfortunately, exact computation is infeasible with larger domains, and existing approximations are poker-specific. We introduce ISMCTS-BR, a scalable search-based deep reinforcement learning algorithm for learning a best response to an agent, approximating worst-case performance. We demonstrate the technique in several games against a variety of agents, including several AlphaZero-based agents. Supplementary material is available at https://arxiv.org/abs/2004.09677.
Unsupervised Misaligned Infrared and Visible Image Fusion via Cross-Modality Image Generation and Registration
Authors: Wang Di , Liu Jinyuan , Fan Xin , Liu Risheng
Published: July 2022

Recent learning-based image fusion methods have marked numerous progress in pre-registered multi-modality data, but suffered serious ghosts dealing with misaligned multi-modality data, due to the spatial deformation and the difficulty narrowing cross-modality discrepancy.

To overcome the obstacles, in this paper, we present a robust cross-modality generation-registration paradigm for unsupervised misaligned infrared and visible image fusion (IVIF).

Specifically, we propose a Cross-modality Perceptual Style Transfer Network (CPSTN) to generate a pseudo infrared image taking a visible image as input.

Benefiting from the favorable geometry preservation ability of the CPSTN, the generated pseudo infrared image embraces a sharp structure, which is more conducive to transforming cross-modality image alignment into mono-modality registration coupled with the structure-sensitive of the infrared image.

In this case, we introduce a Multi-level Refinement Registration Network (MRRN) to predict the displacement vector field between distorted and pseudo infrared images and reconstruct registered infrared image under the mono-modality setting.

Moreover, to better fuse the registered infrared images and visible images, we present a feature Interaction Fusion Module (IFM) to adaptively select more meaningful features for fusion in the Dual-path Interaction Fusion Network (DIFN).

Extensive experimental results suggest that the proposed method performs superior capability on misaligned cross-modality image fusion.
On Discrete Truthful Heterogeneous Two-Facility Location
Authors: Kanellopoulos Panagiotis , Voudouris Alexandros A. , Zhang Rongsen
Published: July 2022

We revisit the discrete heterogeneous two-facility location problem, in which there is a set of agents that occupy nodes of a line graph, and have private approval preferences over two facilities. When the facilities are located at some nodes of the line, each agent derives a cost that is equal to her total distance from the facilities she approves. The goal is to decide where to locate the two facilities, so as to (a) incentivize the agents to truthfully report their preferences, and (b) achieve a good approximation of the minimum total (social) cost or the maximum cost among all agents. For both objectives, we design deterministic strategyproof mechanisms with approximation ratios that significantly outperform the state-of-the-art, and complement these results with (almost) tight lower bounds.
Estimation and Comparison of Linear Regions for ReLU Networks
Authors: Wang Yuan
Published: July 2022

We study the relationship between the arrangement of neurons and the complexity of the ReLU-activated neural networks measured by the number of linear regions. More specifically, we provide both theoretical and empirical evidence for the point of view that shallow networks tend to have higher complexity than deep ones when the total number of neurons is fixed. In the theoretical part, we prove that this is the case for networks whose neurons in the hidden layers are arranged in the forms of 1x2n, 2xn and nx2; in the empirical part, we implement an algorithm that precisely tracks (hence counts) all the linear regions, and run it on networks with various structures. Although the time complexity of the algorithm is quite high, we verify that the problem of calculating the number of linear regions of a ReLU network is itself NP-hard. So currently there is no surprisingly efficient way to solve it. Roughly speaking, in the algorithm we divide the linear regions into subregions called the "activation regions", which are convex and easy to propagate through the network. The relationship between the number of the linear regions and that of the activation regions is also discussed.
EMGC²F: Efficient Multi-view Graph Clustering with Comprehensive Fusion
Authors: Wu Danyang , Lu Jitao , Nie Feiping , Wang Rong , Yuan Yuan
Published: July 2022

This paper proposes an Efficient Multi-view Graph Clustering with Comprehensive Fusion (EMGC²F) model and a corresponding efficient optimization algorithm to address multi-view graph clustering tasks effectively and efficiently. Compared to existing works, our proposals have the following highlights: 1) EMGC²F directly finds a consistent cluster indicator matrix with a Super Nodes Similarity Minimization module from multiple views, which avoids time-consuming spectral decomposition in previous works. 2) EMGC²F comprehensively mines information from multiple views. More formally, it captures the consistency of multiple views via a Cross-view Nearest Neighbors Voting (CN²V) mechanism, meanwhile capturing the importance of multiple views via an adaptive weighted-learning mechanism. 3) EMGC²F is a parameter-free model and the time complexity of the proposed algorithm is far less than existing works, demonstrating the practicability. Empirical results on several benchmark datasets demonstrate that our proposals outperform SOTA competitors both in effectiveness and efficiency.
A Unified Meta-Learning Framework for Dynamic Transfer Learning
Authors: Wu Jun , He Jingrui
Published: July 2022

Transfer learning refers to the transfer of knowledge or information from a relevant source task to a target task. However, most existing works assume both tasks are sampled from a stationary task distribution, thereby leading to the sub-optimal performance for dynamic tasks drawn from a non-stationary task distribution in real scenarios. To bridge this gap, in this paper, we study a more realistic and challenging transfer learning setting with dynamic tasks, i.e., source and target tasks are continuously evolving over time. We theoretically show that the expected error on the dynamic target task can be tightly bounded in terms of source knowledge and consecutive distribution discrepancy across tasks. This result motivates us to propose a generic meta-learning framework L2E for modeling the knowledge transferability on dynamic tasks. It is centered around a task-guided meta-learning problem with a group of meta-pairs of tasks, based on which we are able to learn the prior model initialization for fast adaptation on the newest target task. L2E enjoys the following properties: (1) effective knowledge transferability across dynamic tasks; (2) fast adaptation to the new target task; (3) mitigation of catastrophic forgetting on historical target tasks; and (4) flexibility in incorporating any existing static transfer learning algorithms. Extensive experiments on various image data sets demonstrate the effectiveness of the proposed L2E framework.
A Simple yet Effective Method for Graph Classification
Authors: Wu Junran , Li Shangzhe , Li Jianhao , Pan Yicheng , Xu Ke
Published: July 2022

In deep neural networks, better results can often be obtained by increasing the complexity of previously developed basic models. However, it is unclear whether there is a way to boost performance by decreasing the complexity of such models. Intuitively, given a problem, a simpler data structure comes with a simpler algorithm. Here, we investigate the feasibility of improving graph classification performance while simplifying the learning process. Inspired by structural entropy on graphs, we transform the data sample from graphs to coding trees, which is a simpler but essential structure for graph data. Furthermore, we propose a novel message passing scheme, termed hierarchical reporting, in which features are transferred from leaf nodes to root nodes by following the hierarchical structure of coding trees. We then present a tree kernel and a convolutional network to implement our scheme for graph classification. With the designed message passing scheme, the tree kernel and convolutional network have a lower runtime complexity of O(n) than Weisfeiler-Lehman subtree kernel and other graph neural networks of at least O(hm). We empirically validate our methods with several graph classification benchmarks and demonstrate that they achieve better performance and lower computational consumption than competing approaches.
Automatically Gating Multi-Frequency Patterns through Rectified Continuous Bernoulli Units with Theoretical Principles
Authors: Wu Zheng-Fan , Feng Yi-Nan , Xue Hui
Published: July 2022

Different nonlinearities are only suitable for responding to different frequency signals. The locally-responding ReLU is incapable of modeling high-frequency features due to the spectral bias, whereas the globally-responding sinusoidal function is intractable to represent low-frequency concepts cheaply owing to the optimization dilemma. Moreover, nearly all the practical tasks are composed of complex multi-frequency patterns, whereas there is little prospect of designing or searching a heterogeneous network containing various types of neurons matching the frequencies, because of their exponentially-increasing combinatorial states. In this paper, our contributions are three-fold: 1) we propose a general Rectified Continuous Bernoulli (ReCB) unit paired with an efficient variational Bayesian learning paradigm, to automatically detect/gate/represent different frequency responses; 2) our numerically-tight theoretical framework proves that ReCB-based networks can achieve the optimal representation ability, which is O(m^{η/(d^2)}) times better than that of popular neural networks, for a hidden dimension of m, an input dimension of d, and a Lipschitz constant of η; 3) we provide comprehensive empirical evidence showing that ReCB-based networks can keenly learn multi-frequency patterns and push the state-of-the-art performance.
How Should We Vote? A Comparison of Voting Systems within Social Networks
Authors: Alouf-Heffetz Shiri , Armstrong Ben , Larson Kate , Talmon Nimrod
Published: July 2022

Voting is a crucial methodology for eliciting and combining agents' preferences and information across many applications. Just as there are numerous voting rules exhibiting different properties, we also see many different voting systems. In this paper we investigate how different voting systems perform as a function of the characteristics of the underlying voting population and social network. In particular, we compare direct democracy, liquid democracy, and sortition in a ground truth voting context.

Through simulations -- using both real and artificially generated social networks -- we illustrate how voter competency distributions and levels of direct participation affect group accuracy differently in each voting mechanism. Our results can be used to guide the selection of a suitable voting system based on the characteristics of a particular voting setting.
Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion
Authors: Kizilkaya Fatih Erdem , Kempe David
Published: July 2022

The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher.

A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances.

As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3.

A recent breakthrough result showed that achieving this bound of 3 is possible;

however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search.

Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3.

Each candidate starts with a score equal to his number of first-place votes.

These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins.

We give a one-paragraph proof that this voting rule achieves distortion 3.

This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead.

We also show that a straightforward extension can be used to give a constructive proof of the more general Ranking-Matching Lemma of Gkatzelis et al.

We also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality veto is run only for k < n rounds; then, a candidate is chosen with probability proportional to his residual score.

This general rule interpolates between Random Dictatorship (for k=0) and Plurality Veto (for k=n-1), and k controls the variance of the output.

We show that for all k, this rule has expected distortion at most 3.
Neuro-Symbolic Verification of Deep Neural Networks
Authors: Xie Xuan , Kersting Kristian , Neider Daniel
Published: July 2022

Formal verification has emerged as a powerful approach to ensure the safety and reliability of deep neural networks. However, current verification tools are limited to only a handful of properties that can be expressed as first-order constraints over the inputs and output of a network. While adversarial robustness and fairness fall under this category, many real-world properties (e.g., "an autonomous vehicle has to stop in front of a stop sign") remain outside the scope of existing verification technology. To mitigate this severe practical restriction, we introduce a novel framework for verifying neural networks, named neuro-symbolic verification. The key idea is to use neural networks as part of the otherwise logical specification, enabling the verification of a wide variety of complex, real-world properties, including the one above. A defining feature of our framework is that it can be implemented on top of existing verification infrastructure for neural networks, making it easily accessible to researchers and practitioners.
MultiQuant: Training Once for Multi-bit Quantization of Neural Networks
Authors: Xu Ke , Feng Qiantai , Zhang Xingyi , Wang Dong
Published: July 2022

Quantization has become a popular technique to compress deep neural networks (DNNs) and reduce computational costs, but most prior work focuses on training DNNs at each individual fixed bit-width and accuracy trade-off point. How to produce a model with flexible precision is largely unexplored. This work proposes a multi-bit quantization framework (MultiQuant) to make the learned DNNs robust for different precision configuration during inference by adopting Lowest-Random-Highest bit-width co-training method. Meanwhile, we propose an online adaptive label generation strategy to alleviate the problem of vicious competition under different precision caused by one-hot labels in the supernet training. The trained supernet model can be flexibly set to different bit widths to support dynamic speed and accuracy trade-off. Furthermore, we adopt the Monte Carlo sampling-based genetic algorithm search strategy with quantization-aware accuracy predictor as evaluation criterion to incorporate the mixed precision technology in our framework. Experiment results on ImageNet datasets demonstrate MultiQuant method can attain the quantization results under different bit-widths comparable with quantization-aware training without retraining.
Towards Safe Reinforcement Learning via Constraining Conditional Value-at-Risk
Authors: Ying ChengYang , Zhou Xinning , Su Hang , Yan Dong , Chen Ning , Zhu Jun
Published: July 2022

Though deep reinforcement learning (DRL) has obtained substantial success, it may encounter catastrophic failures due to the intrinsic uncertainty of both transition and observation. Most of the existing methods for safe reinforcement learning can only handle transition disturbance or observation disturbance since these two kinds of disturbance affect different parts of the agent; besides, the popular worst-case return may lead to overly pessimistic policies. To address these issues, we first theoretically prove that the performance degradation under transition disturbance and observation disturbance depends on a novel metric of Value Function Range (VFR), which corresponds to the gap in the value function between the best state and the worst state. Based on the analysis, we adopt conditional value-at-risk (CVaR) as an assessment of risk and propose a novel reinforcement learning algorithm of CVaR-Proximal-Policy-Optimization (CPPO) which formalizes the risk-sensitive constrained optimization problem by keeping its CVaR under a given threshold. Experimental results show that CPPO achieves a higher cumulative reward and is more robust against both observation and transition disturbances on a series of continuous control tasks in MuJoCo.
EGCN: An Ensemble-based Learning Framework for Exploring Effective Skeleton-based Rehabilitation Exercise Assessment
Authors: Yu Bruce X.B. , Liu Yan , Zhang Xiang , Chen Gong , Chan Keith C.C.
Published: July 2022

Recently, some skeleton-based physical therapy systems have been attempted to automatically evaluate the correctness or quality of an exercise performed by rehabilitation subjects. However, in terms of algorithms and evaluation criteria, the task remains not fully explored regarding making full use of different skeleton features. To advance the prior work, we propose a learning framework called Ensemble-based Graph Convolutional Network (EGCN) for skeleton-based rehabilitation exercise assessment. As far as we know, this is the first attempt that utilizes both two skeleton feature groups and investigates different ensemble strategies for the task. We also examine the properness of existing evaluation criteria and focus on evaluating the prediction ability of our proposed method. We then conduct extensive cross-validation experiments on two latest public datasets: UI-PRMD and KIMORE. Results indicate that the model-level ensemble scheme of our EGCN achieves better performance than existing methods. Code is available: https://github.com/bruceyo/EGCN.
Robust Weight Perturbation for Adversarial Training
Authors: Yu Chaojian , Han Bo , Gong Mingming , Shen Li , Ge Shiming , Bo Du , Liu Tongliang
Published: July 2022

Overfitting widely exists in adversarial robust training of deep networks. An effective remedy is adversarial weight perturbation, which injects the worst-case weight perturbation during network training by maximizing the classification loss on adversarial examples. Adversarial weight perturbation helps reduce the robust generalization gap; however, it also undermines the robustness improvement. A criterion that regulates the weight perturbation is therefore crucial for adversarial training. In this paper, we propose such a criterion, namely Loss Stationary Condition (LSC) for constrained perturbation. With LSC, we find that it is essential to conduct weight perturbation on adversarial data with small classification loss to eliminate robust overfitting. Weight perturbation on adversarial data with large classification loss is not necessary and may even lead to poor robustness. Based on these observations, we propose a robust perturbation strategy to constrain the extent of weight perturbation. The perturbation strategy prevents deep networks from overfitting while avoiding the side effect of excessive weight perturbation, significantly improving the robustness of adversarial training. Extensive experiments demonstrate the superiority of the proposed method over the state-of-the-art adversarial training methods.
Hyperbolic Knowledge Transfer with Class Hierarchy for Few-Shot Learning
Authors: Zhang Baoquan , Jiang Hao , Feng Shanshan , Li Xutao , Ye Yunming , Ye Rui
Published: July 2022

Few-shot learning (FSL) aims to recognize a novel class with very few instances, which is a challenging task since it suffers from a data scarcity issue. One way to effectively alleviate this issue is introducing explicit knowledge summarized from human past experiences to achieve knowledge transfer for FSL. Based on this idea, in this paper, we introduce the explicit knowledge of class hierarchy (i.e., the hierarchy relations between classes) as FSL priors and propose a novel hyperbolic knowledge transfer framework for FSL, namely, HyperKT. Our insight is, in the hyperbolic space, the hierarchy relation between classes can be well preserved by resorting to the exponential growth characters of hyperbolic volume, so that better knowledge transfer can be achieved for FSL. Specifically, we first regard the class hierarchy as a tree-like structure. Then, 1) a hyperbolic representation learning module and a hyperbolic prototype inference module are employed to encode/infer each image and class prototype to the hyperbolic space, respectively; and 2) a novel hierarchical classification and relation reconstruction loss are carefully designed to learn the class hierarchy. Finally, the novel class prediction is performed in a nearest-prototype manner. Extensive experiments on three datasets show our method achieves superior performance over state-of-the-art methods, especially on 1-shot tasks.
Fine-Tuning Graph Neural Networks via Graph Topology Induced Optimal Transport
Authors: Zhang Jiying , Xiao Xi , Huang Long-Kai , Rong Yu , Bian Yatao
Published: July 2022

Recently, the pretrain-finetuning paradigm has attracted tons of attention in graph learning community due to its power of alleviating the lack of labels problem in many real-world applications. Current studies use existing techniques, such as weight constraint, representation constraint, which are derived from images or text data, to transfer the invariant knowledge from the pre-train stage to fine-tuning stage. However, these methods failed to preserve invariances from graph structure and Graph Neural Network (GNN) style models. In this paper, we present a novel optimal transport-based fine-tuning framework called GTOT-Tuning, namely, Graph Topology induced Optimal Transport fine-Tuning, for GNN style backbones. GTOT-Tuning is required to utilize the property of graph data to enhance the preservation of representation produced by fine-tuned networks. Toward this goal, we formulate graph local knowledge transfer as an Optimal Transport (OT) problem with a structural prior and construct the GTOT regularizer to constrain the fine-tuned model behaviors. By using the adjacency relationship amongst nodes, the GTOT regularizer achieves node-level optimal transport procedures and reduces redundant transport procedures, resulting in efficient knowledge transfer from the pre-trained models. We evaluate GTOT-Tuning on eight downstream tasks with various GNN backbones and demonstrate that it achieves state-of-the-art fine-tuning performance for GNNs.
Next Point-of-Interest Recommendation with Inferring Multi-step Future Preferences
Authors: Zhang Lu , Sun Zhu , Wu Ziqing , Zhang Jie , Ong Yew Soon , Qu Xinghua
Published: July 2022

Existing studies on next point-of-interest (POI) recommendation mainly attempt to learn user preference from the past and current sequential behaviors. They, however, completely ignore the impact of future behaviors on the decision-making, thus hindering the quality of user preference learning. Intuitively, users' next POI visits may also be affected by their multi-step future behaviors, as users may often have activity planning in mind. To fill this gap, we propose a novel Context-aware Future Preference inference Recommender (CFPRec) to help infer user future preference in a self-ensembling manner. In particular, it delicately derives multi-step future preferences from the learned past preference thanks to the periodic property of users' daily check-ins, so as to implicitly mimic user’s activity planning before her next visit. The inferred future preferences are then seamlessly integrated with the current preference for more expressive user preference learning. Extensive experiments on three datasets demonstrate the superiority of CFPRec against state-of-the-arts.
Multi-Constraint Deep Reinforcement Learning for Smooth Action Control
Authors: Zou Guangyuan , He Ying , Yu F. Richard , Chen Longquan , Pan Weike , Ming Zhong
Published: July 2022

Deep reinforcement learning (DRL) has been studied in a variety of challenging decision-making tasks, e.g., autonomous driving. \textcolor{black}{However, DRL typically suffers from the action shaking problem, which means that agents can select actions with big difference even though states only slightly differ.} One of the crucial reasons for this issue is the inappropriate design of the reward in DRL. In this paper, to address this issue, we propose a novel way to incorporate the smoothness of actions in the reward. Specifically, we introduce sub-rewards and add multiple constraints related to these sub-rewards. In addition, we propose a multi-constraint proximal policy optimization (MCPPO) method to solve the multi-constraint DRL problem. Extensive simulation results show that the proposed MCPPO method has better action smoothness compared with the traditional proportional-integral-differential (PID) and mainstream DRL algorithms. The video is available at https://youtu.be/F2jpaSm7YOg.
Explaining Preferences by Multiple Patterns in Voters’ Behavior
Authors: Kraiczy Sonja , Elkind Edith
Published: July 2022

In some preference aggregation scenarios, voters' preferences are highly structured: e.g., the set of candidates may have one-dimensional structure (so that voters' preferences are single-peaked) or be described by a binary decision tree (so that voters' preferences are group-separable). However, sometimes a single axis or a decision tree is insufficient to capture the voters' preferences; rather, there is a small number K of axes or decision trees such that each vote in the profile is consistent with one of these axes (resp., trees). In this work, we study the complexity of deciding whether voters' preferences can be explained in this manner. For K=2, we use the technique developed by Yang [2020, https://doi.org/10.3233/FAIA200099] in the context of single-peaked preferences to obtain a polynomial-time algorithm for several domains: value-restricted preferences, group-separable preferences, and a natural subdomain of group-separable preferences, namely, caterpillar group-separable preferences. For K > 2, the problem is known to be hard for single-peaked preferences; we establish that it is also hard for value-restricted and group-separable preferences. Our positive results for K=2 make use of forbidden minor characterizations of the respective domains; in particular, we establish that the domain of caterpillar group-separable preferences admits a forbidden minor characterization.
Placing Green Bridges Optimally, with Habitats Inducing Cycles
Authors: Herkenrath Maike , Fluschnik Till , Grothe Francesco , Kellerhals Leon
Published: July 2022

Choosing the placement of wildlife crossings (i.e., green bridges) to reconnect animal species' fragmented habitats is among the 17 goals towards sustainable development by the UN. We consider the following established model: Given a graph whose vertices represent the fragmented habitat areas and whose weighted edges represent possible green bridge locations, as well as the habitable vertex set for each species, find the cheapest set of edges such that each species' habitat is connected. We study this problem from a theoretical (algorithms and complexity) and an experimental perspective, while focusing on the case where habitats induce cycles. We prove that the NP-hardness persists in this case even if the graph structure is restricted. If the habitats additionally induce faces in plane graphs however, the problem becomes efficiently solvable. In our empirical evaluation we compare this algorithm as well as ILP formulations for more general variants and an approximation algorithm with another. Our evaluation underlines that each specialization is beneficial in terms of running time, whereas the approximation provides highly competitive solutions in practice.
Learning Curricula for Humans: An Empirical Study with Puzzles from The Witness
Authors: Lelis Levi H.S. , Nova João G.G.V. , Chen Eugene , Sturtevant Nathan R. , Demmans Epp Carrie , Bowling Michael
Published: July 2022

The combination of tree search and neural networks has achieved super-human performance in challenging domains. We are interested in transferring to humans the knowledge these learning systems generate. We hypothesize the process in which neural-guided tree search algorithms learn how to solve a set of problems can be used to generate curricula for helping human learners. In this paper we show how the Bootstrap learning system can be modified to learn curricula for humans in a puzzle domain. We evaluate our system in two curriculum learning settings. First, given a small set of problem instances, our system orders the instances to ease the learning process of human learners. Second, given a large set of problem instances, our system returns a small ordered subset of the initial set that can be presented to human learners. We evaluate our curricula with a user study where participants learn how to solve a class of puzzles from the game `The Witness.' The user-study results suggest one of the curricula our system generates compares favorably with simple baselines and is competitive with the curriculum from the original `The Witness' game in terms of user retention and effort.
Transformer-based Objective-reinforced Generative Adversarial Network to Generate Desired Molecules
Authors: Li Chen , Yamanaka Chikashige , Kaitoh Kazuma , Yamanishi Yoshihiro
Published: July 2022

Deep generative models of sequence-structure data have attracted widespread attention in drug discovery. However, such models cannot fully extract the semantic features of molecules from sequential representations. Moreover, mode collapse reduces the diversity of the generated molecules. This paper proposes a transformer-based objective-reinforced generative adversarial network (TransORGAN) to generate molecules. TransORGAN leverages a transformer architecture as a generator and uses a stochastic policy gradient for reinforcement learning to generate plausible molecules with rich semantic features. The discriminator grants rewards that guide the policy update of the generator, while an objective-reinforced penalty encourages the generation of diverse molecules. Experiments were performed using the ZINC chemical dataset, and the results demonstrated the usefulness of TransORGAN in terms of uniqueness, novelty, and diversity of the generated molecules.
Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit
Authors: Sivagnanam Amutheezan , Kadir Salah Uddin , Mukhopadhyay Ayan , Pugliese Philip , Dubey Abhishek , Samaranayake Samitha , Laszka Aron
Published: July 2022

Vehicle routing problems (VRPs) can be divided into two major categories: offline VRPs, which consider a given set of trip requests to be served, and online VRPs, which consider requests as they arrive in real-time. Based on discussions with public transit agencies, we identify a real-world problem that is not addressed by existing formulations: booking trips with flexible pickup windows (e.g., 3 hours) in advance (e.g., the day before) and confirming tight pickup windows (e.g., 30 minutes) at the time of booking. Such a service model is often required in paratransit service settings, where passengers typically book trips for the next day over the phone. To address this gap between offline and online problems, we introduce a novel formulation, the offline vehicle routing problem with online bookings. This problem is very challenging computationally since it faces the complexity of considering large sets of requests—similar to offline VRPs—but must abide by strict constraints on running time—similar to online VRPs. To solve this problem, we propose a novel computational approach, which combines an anytime algorithm with a learning-based policy for real-time decisions. Based on a paratransit dataset obtained from the public transit agency of Chattanooga, TN, we demonstrate that our novel formulation and computational approach lead to significantly better outcomes in this setting than existing algorithms.
Private Stochastic Convex Optimization and Sparse Learning with Heavy-tailed Data Revisited
Authors: Tao Youming , Wu Yulian , Cheng Xiuzhen , Wang Di
Published: July 2022

In this paper, we revisit the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) with heavy-tailed data, where the gradient of the loss function has bounded moments. Instead of the case where the loss function is Lipschitz or each coordinate of the gradient has bounded second moment studied previously, we consider a relaxed scenario where each coordinate of the gradient only has bounded (1+v)-th moment with some v∈(0, 1]. Firstly, we start from the one dimensional private mean estimation for heavy-tailed distributions. We propose a novel robust and private mean estimator which is optimal. Based on its idea, we then extend to the general d-dimensional space and study DP-SCO with general convex and strongly convex loss functions. We also provide lower bounds for these two classes of loss under our setting and show that our upper bounds are optimal up to a factor of O(Poly(d)). To address the high dimensionality issue, we also study DP-SCO with heavy-tailed gradient under some sparsity constraint (DP sparse learning). We propose a new method and show it is also optimal up to a factor of O(s*), where s* is the underlying sparsity of the constraint.
Exploring the Vulnerability of Deep Reinforcement Learning-based Emergency Control for Low Carbon Power Systems
Authors: Wan Xu , Zeng Lanting , Sun Mingyang
Published: July 2022

Decarbonization of global power systems significantly increases the operational uncertainty and modeling complexity that drive the necessity of widely exploiting cutting-edge Deep Reinforcement Learning (DRL) technologies to realize adaptive and real-time emergency control, which is the last resort for system stability and resiliency. The vulnerability of the DRL-based emergency control scheme may lead to severe real-world security issues if it can not be fully explored before implementing it practically. To this end, this is the first work that comprehensively investigates adversarial attacks and defense mechanisms for DRL-based power system emergency control. In particular, recovery-targeted (RT) adversarial attacks are designed for gradient-based approaches, aiming to dramatically degrade the effectiveness of the conducted emergency control actions to prevent the system from restoring to a stable state. Furthermore, the corresponding robust defense (RD) mechanisms are proposed to actively modify the observations based on the distances of sequential states. Experiments are conducted based on the standard IEEE reliability test system, and the results show that security risks indeed exist in the state-of-the-art DRL-based power system emergency control models. The effectiveness, stealthiness, instantaneity, and transferability of the proposed attacks and defense mechanisms are demonstrated with both white-box and black-box settings.
Modelling the Dynamics of Multi-Agent Q-learning: The Stochastic Effects of Local Interaction and Incomplete Information
Authors: Leung Chin-wing , Hu Shuyue , Leung Ho-fung
Published: July 2022

The theoretical underpinnings of multiagent reinforcement learning has recently attracted much attention.

In this work, we focus on the generalized social learning (GSL) protocol --- an agent interaction protocol that is widely adopted in the literature, and aim to develop an accurate theoretical model for the Q-learning dynamics under this protocol.

Noting that previous models fail to characterize the effects of local interactions and incomplete information that arise from GSL, we model the Q-values dynamics of each individual agent as a system of stochastic differential equations (SDE).

Based on the SDE, we express the time evolution of the probability density function of Q-values in the population with a Fokker-Planck equation.

We validate the correctness of our model through extensive comparisons with agent-based simulation results across different types of symmetric games.

In addition, we show that as the interactions between agents are more limited and information is less complete, the population can converge to a outcome that is qualitatively different than that with global interactions and complete information.
ARCANE: An Efficient Architecture for Exact Machine Unlearning
Authors: Yan Haonan , Li Xiaoguang , Guo Ziyao , Li Hui , Li Fenghua , Lin Xiaodong
Published: July 2022

Recently users’ right-to-be-forgotten is stipulated by many laws and regulations. However, only removing the data from the dataset is not enough, as machine learning models would memorize the training data once the data is involved in model training, increasing the risk of exposing users’ privacy. To solve this problem, currently, the straightforward method, naive retraining, is to discard these data and retrain the model from scratch, which is reliable but brings much computational and time overhead. In this paper, we propose an exact unlearning architecture called ARCANE. Based on ensemble learning, we transform the naive retraining into multiple one-class classiﬁcation tasks to reduce retraining cost while ensuring model performance, especially in the case of a large number of unlearning requests not considered by previous works. Then we further introduce data preprocessing methods to reduce the retraining overhead and speed up the unlearning, which includes representative data selection for redundancy removal, training state saving to reuse previous calculation results, and sorting to cope with unlearning requests of different distributions. We extensively evaluate ARCANE on three typical datasets with three common model architectures. Experiment results show the effectiveness and superiority of ARCANE over both the naive retraining and the state-of-the-art method in terms of model performance and unlearning speed.
Temporality Spatialization: A Scalable and Faithful Time-Travelling Visualization for Deep Classifier Training
Authors: Yang Xianglin , Lin Yun , Liu Ruofan , Dong Jin Song
Published: July 2022

Time-travelling visualization answers how the predictions of a deep classifier are formed during the training. It visualizes in two or three dimensional space how the classification boundaries and sample embeddings are evolved during training.

In this work, we propose TimeVis, a novel time-travelling visualization solution for deep classifiers. Comparing to the state-of-the-art solution DeepVisualInsight (DVI), TimeVis can significantly (1) reduce visualization errors for rendering samples’ travel across different training epochs, and (2) improve the visualization efficiency. To this end, we design a technique called temporality spatialization, which unifies the spatial relation (e.g., neighbouring samples in single epoch) and temporal relation (e.g., one identical sample in neighbouring training epochs) into one high-dimensional topological complex. Such spatio-temporal complex can be used to efficiently train one visualization model to accurately project and inverse-project any high and low dimensional data across epochs. Our extensive experiment shows that, in comparison to DVI, TimeVis not only is more accurate to preserve the visualized time-travelling semantics, but 15X faster in visualization efficiency, achieving a new state-of-the-art in time-travelling visualization.
Enhancing Entity Representations with Prompt Learning for Biomedical Entity Linking
Authors: Zhu Tiantian , Qin Yang , Chen Qingcai , Hu Baotian , Xiang Yang
Published: July 2022

Biomedical entity linking aims to map mentions in biomedical text to standardized concepts or entities in a curated knowledge base (KB) such as Unified Medical Language System (UMLS). The latest research tends to solve this problem in a unified framework solely based on surface form matching between mentions and entities. Specifically, these methods focus on addressing the variety challenge of the heterogeneous naming of biomedical concepts. Yet, the ambiguity challenge that the same word under different contexts may refer to distinct entities is usually ignored. To address this challenge, we propose a two-stage linking algorithm to enhance the entity representations based on prompt learning. The first stage includes a coarser-grained retrieval from a representation space defined by a bi-encoder that independently embeds the mention and entity’s surface forms. Unlike previous one-model-fits-all systems, each candidate is then re-ranked with a finer-grained encoder based on prompt-tuning that utilizes the contextual information. Extensive experiments show that our model achieves promising performance improvements compared with several state-of-the-art techniques on the largest biomedical public dataset MedMentions and the NCBI disease corpus. We also observe by cases that the proposed prompt-tuning strategy is effective in solving both the variety and ambiguity challenges in the linking task.
Effective Graph Context Representation for Document-level Machine Translation
Authors: Chen Kehai , Yang Muyun , Utiyama Masao , Sumita Eiichiro , Wang Rui , Zhang Min
Published: July 2022

Document-level neural machine translation (DocNMT) universally encodes several local sentences or the entire document. Thus, DocNMT does not consider the relevance of document-level contextual information, for example, some context (i.e., content words, logical order, and co-occurrence relation) is more effective than another auxiliary context (i.e., functional and auxiliary words). To address this issue, we first utilize the word frequency information to recognize content words in the input document, and then use heuristical relations to summarize content words and sentences as a graph structure without relying on external syntactic knowledge. Furthermore, we apply graph attention networks to this graph structure to learn its feature representation, which allows DocNMT to more effectively capture the document-level context. Experimental results on several widely-used document-level benchmarks demonstrated the effectiveness of the proposed approach.