OpenRaiser/Intern-Atlas huggingface dataset:
Coordinating Followers to Reach Better Equilibria: End-to-End Gradient Descent for Stackelberg Games
Venue: arXiv cs.GT 2021
Year: 2021

A growing body of work in game theory extends the traditional Stackelberg game to settings with one leader and multiple followers who play a Nash equilibrium. Standard approaches for computing equilibria in these games reformulate the followers' best response as constraints in the leader's optimization problem. These reformulation approaches can sometimes be effective, but often get trapped in low-quality solutions when followers' objectives are non-linear or non-quadratic. Moreover, these approaches assume a unique equilibrium or a specific equilibrium concept, e.g., optimistic or pessimistic, which is a limiting assumption in many situations. To overcome these limitations, we propose a stochastic gradient descent--based approach, where the leader's strategy is updated by differentiating through the followers' best responses. We frame the leader's optimization as a learning problem against followers' equilibrium, which allows us to decouple the followers' equilibrium constraints from the leader's problem. This approach also addresses cases with multiple equilibria and arbitrary equilibrium selection procedures by back-propagating through a sampled Nash equilibrium. To this end, this paper introduces a novel concept called equilibrium flow to formally characterize the set of equilibrium selection processes where the gradient with respect to a sampled equilibrium is an unbiased estimate of the true gradient. We evaluate our approach experimentally against existing baselines in three Stackelberg problems with multiple followers and find that in each case, our approach is able to achieve higher utility for the leader.
Video Imprint
Venue: arXiv cs.CV 2021
Year: 2021

A new unified video analytics framework (ER3) is proposed for complex event retrieval, recognition and recounting, based on the proposed video imprint representation, which exploits temporal correlations among image features across video frames. With the video imprint representation, it is convenient to reverse map back to both temporal and spatial locations in video frames, allowing for both key frame identification and key areas localization within each frame. In the proposed framework, a dedicated feature alignment module is incorporated for redundancy removal across frames to produce the tensor representation, i.e., the video imprint. Subsequently, the video imprint is individually fed into both a reasoning network and a feature aggregation module, for event recognition/recounting and event retrieval tasks, respectively. Thanks to its attention mechanism inspired by the memory networks used in language modeling, the proposed reasoning network is capable of simultaneous event category recognition and localization of the key pieces of evidence for event recounting. In addition, the latent structure in our reasoning network highlights the areas of the video imprint, which can be directly used for event recounting. With the event retrieval task, the compact video representation aggregated from the video imprint contributes to better retrieval results than existing state-of-the-art methods.
Uncertain Process Data with Probabilistic Knowledge: Problem Characterization and Challenges
Venue: arXiv cs.AI 2021
Year: 2021

Motivated by the abundance of uncertain event data from multiple sources including physical devices and sensors, this paper presents the task of relating a stochastic process observation to a process model that can be rendered from a dataset. In contrast to previous research that suggested to transform a stochastically known event log into a less informative uncertain log with upper and lower bounds on activity frequencies, we consider the challenge of accommodating the probabilistic knowledge into conformance checking techniques. Based on a taxonomy that captures the spectrum of conformance checking cases under stochastic process observations, we present three types of challenging cases. The first includes conformance checking of a stochastically known log with respect to a given process model. The second case extends the first to classify a stochastically known log into one of several process models. The third case extends the two previous ones into settings in which process models are only stochastically known. The suggested problem captures the increasingly growing number of applications in which sensors provide probabilistic process information.
Energy Aligning for Biased Models
Venue: arXiv cs.LG 2021
Year: 2021

Training on class-imbalanced data usually results in biased models that tend to predict samples into the majority classes, which is a common and notorious problem. From the perspective of energy-based model, we demonstrate that the free energies of categories are aligned with the label distribution theoretically, thus the energies of different classes are expected to be close to each other when aiming for ``balanced'' performance. However, we discover a severe energy-bias phenomenon in the models trained on class-imbalanced dataset. To eliminate the bias, we propose a simple and effective method named Energy Aligning by merely adding the calculated shift scalars onto the output logits during inference, which does not require to (i) modify the network architectures, (ii) intervene the standard learning paradigm, (iii) perform two-stage training. The proposed algorithm is evaluated on two class imbalance-related tasks under various settings: class incremental learning and long-tailed recognition. Experimental results show that energy aligning can effectively alleviate class imbalance issue and outperform state-of-the-art methods on several benchmarks.
A Joint Model for Dropped Pronoun Recovery and Conversational Discourse Parsing in Chinese Conversational Speech
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we present a neural model for joint dropped pronoun recovery (DPR) and conversational discourse parsing (CDP) in Chinese conversational speech. We show that DPR and CDP are closely related, and a joint model benefits both tasks. We refer to our model as DiscProReco, and it first encodes the tokens in each utterance in a conversation with a directed Graph Convolutional Network (GCN). The token states for an utterance are then aggregated to produce a single state for each utterance. The utterance states are then fed into a biaffine classifier to construct a conversational discourse graph. A second (multi-relational) GCN is then applied to the utterance states to produce a discourse relation-augmented representation for the utterances, which are then fused together with token states in each utterance as input to a dropped pronoun recovery layer. The joint model is trained and evaluated on a new Structure Parsing-enhanced Dropped Pronoun Recovery (SPDPR) dataset that we annotated with both two types of information. Experimental results on the SPDPR dataset and other benchmarks show that DiscProReco significantly outperforms the state-of-the-art baselines of both tasks.
QFuzz: Quantitative Fuzzing for Side Channels
Venue: arXiv cs.CR 2021
Year: 2021

Side channels pose a significant threat to the confidentiality of software systems. Such vulnerabilities are challenging to detect and evaluate because they arise from non-functional properties of software such as execution times and require reasoning on multiple execution traces. Recently, noninterference notions have been adapted in static analysis, symbolic execution, and greybox fuzzing techniques. However, noninterference is a strict notion and may reject security even if the strength of information leaks are weak. A quantitative notion of security allows for the relaxation of noninterference and tolerates small (unavoidable) leaks. Despite progress in recent years, the existing quantitative approaches have scalability limitations in practice. In this work, we present QFuzz, a greybox fuzzing technique to quantitatively evaluate the strength of side channels with a focus on min entropy. Min entropy is a measure based on the number of distinguishable observations (partitions) to assess the resulting threat from an attacker who tries to compromise secrets in one try. We develop a novel greybox fuzzing equipped with two partitioning algorithms that try to maximize the number of distinguishable observations and the cost differences between them. We evaluate QFuzz on a large set of benchmarks from existing work and real-world libraries (with a total of 70 subjects). QFuzz compares favorably to three state-of-the-art detection techniques. QFuzz provides quantitative information about leaks beyond the capabilities of all three techniques. Crucially, we compare QFuzz to a state-of-the-art quantification tool and find that QFuzz significantly outperforms the tool in scalability while maintaining similar precision. Overall, we find that our approach scales well for real-world applications and provides useful information to evaluate resulting threats. Additionally, QFuzz identifies a zero-d...
The Computational and Latency Advantage of Quantum Communication Networks
Venue: arXiv cs.IT 2021
Year: 2021

This article summarises the current status of classical communication networks and identifies some critical open research challenges that can only be solved by leveraging quantum technologies. By now, the main goal of quantum communication networks has been security. However, quantum networks can do more than just exchange secure keys or serve the needs of quantum computers. In fact, the scientific community is still investigating on the possible use cases/benefits that quantum communication networks can bring. Thus, this article aims at pointing out and clearly describing how quantum communication networks can enhance in-network distributed computing and reduce the overall end-to-end latency, beyond the intrinsic limits of classical technologies. Furthermore, we also explain how entanglement can reduce the communication complexity (overhead) that future classical virtualised networks will experience.
A generative model for molecule generation based on chemical reaction trees
Venue: arXiv cs.AI 2021
Year: 2021

Deep generative models have been shown powerful in generating novel molecules with desired chemical properties via their representations such as strings, trees or graphs. However, these models are limited in recommending synthetic routes for the generated molecules in practice. We propose a generative model to generate molecules via multi-step chemical reaction trees. Specifically, our model first propose a chemical reaction tree with predicted reaction templates and commercially available molecules (starting molecules), and then perform forward synthetic steps to obtain product molecules. Experiments show that our model can generate chemical reactions whose product molecules are with desired chemical properties. Also, the complete synthetic routes for these product molecules are provided.
Generating Relevant and Coherent Dialogue Responses using Self-separated Conditional Variational AutoEncoders
Venue: arXiv cs.CL 2021
Year: 2021

Conditional Variational AutoEncoder (CVAE) effectively increases the diversity and informativeness of responses in open-ended dialogue generation tasks through enriching the context vector with sampled latent variables. However, due to the inherent one-to-many and many-to-one phenomena in human dialogues, the sampled latent variables may not correctly reflect the contexts' semantics, leading to irrelevant and incoherent generated responses. To resolve this problem, we propose Self-separated Conditional Variational AutoEncoder (abbreviated as SepaCVAE) that introduces group information to regularize the latent variables, which enhances CVAE by improving the responses' relevance and coherence while maintaining their diversity and informativeness. SepaCVAE actively divides the input data into groups, and then widens the absolute difference between data pairs from distinct groups, while narrowing the relative distance between data pairs in the same group. Empirical results from automatic evaluation and detailed analysis demonstrate that SepaCVAE can significantly boost responses in well-established open-domain dialogue datasets.
On Healthcare Robots: Concepts, definitions, and considerations for healthcare robot governance
Venue: arXiv cs.RO 2021
Year: 2021

Although healthcare is a remarkably sensitive domain of application, and systems that exert direct control over the world can cause harm in a way that humans cannot necessarily correct or oversee, it is still unclear whether and how healthcare robots are currently regulated or should be regulated. Existing regulations are primarily unprepared to provide guidance for such a rapidly evolving field and accommodate devices that rely on machine learning and AI. Moreover, the field of healthcare robotics is very rich and extensive, but it is still very much scattered and unclear in terms of definitions, medical and technical classifications, product characteristics, purpose, and intended use. As a result, these devices often navigate between the medical device regulation or other non-medical norms, such as the ISO personal care standard. Before regulating the field of healthcare robots, it is therefore essential to map the major state-of-the-art developments in healthcare robotics, their capabilities and applications, and the challenges we face as a result of their integration within the healthcare environment. This contribution fills in this gap and lack of clarity currently experienced within healthcare robotics and its governance by providing a structured overview of and further elaboration on the main categories now established, their intended purpose, use, and main characteristics. We explicitly focus on surgical, assistive, and service robots to rightfully match the definition of healthcare as the organized provision of medical care to individuals, including efforts to maintain, treat, or restore physical, mental, or emotional well-being. We complement these findings with policy recommendations to help policymakers unravel an optimal regulatory framing for healthcare robot technologies
BERTGEN: Multi-task Generation through BERT
Venue: arXiv cs.CL 2021
Year: 2021

We present BERTGEN, a novel generative, decoder-only model which extends BERT by fusing multimodal and multilingual pretrained models VL-BERT and M-BERT, respectively. BERTGEN is auto-regressively trained for language generation tasks, namely image captioning, machine translation and multimodal machine translation, under a multitask setting. With a comprehensive set of evaluations, we show that BERTGEN outperforms many strong baselines across the tasks explored. We also show BERTGEN's ability for zero-shot language generation, where it exhibits competitive performance to supervised counterparts. Finally, we conduct ablation studies which demonstrate that BERTGEN substantially benefits from multi-tasking and effectively transfers relevant inductive biases from the pre-trained models.
An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
Venue: arXiv cs.DS 2021
Year: 2021

In this paper, we consider the task of computing an independent set of maximum weight in a given $d$-claw free graph $G=(V,E)$ equipped with a positive weight function $w:V\rightarrow\mathbb{R}^+$. In doing so, $d\geq 2$ is considered a constant. The previously best known approximation algorithm for this problem is the local improvement algorithm SquareImp proposed by Berman. It achieves a performance ratio of $\frac{d}{2}+ε$ in time $\mathcal{O}(|V(G)|^{d+1}\cdot(|V(G)|+|E(G)|)\cdot (d-1)^2\cdot \left(\frac{d}{2ε}+1\right)^2)$ for any $ε>0$, which has remained unimproved for the last twenty years. By considering a broader class of local improvements, we obtain an approximation ratio of $\frac{d}{2}-\frac{1}{63,700,992}+ε$ for any $ε>0$ at the cost of an additional factor of $\mathcal{O}(|V(G)|^{(d-1)^2})$ in the running time. In particular, our result implies a polynomial time $\frac{d}{2}$-approximation algorithm. Furthermore, the well-known reduction from the weighted $k$-Set Packing Problem to the Maximum Weight Independent Set Problem in $k+1$-claw free graphs provides a $\frac{k+1}{2}-\frac{1}{63,700,992}+ε$-approximation algorithm for the weighted $k$-Set Packing Problem for any $ε>0$. This improves on the previously best known approximation guarantee of $\frac{k+1}{2}+ε$ originating from the result of Berman.
Auction-based and Distributed Optimization Approaches for Scheduling Observations in Satellite Constellations with Exclusive Orbit Portions
Venue: arXiv cs.AI 2021
Year: 2021

We investigate the use of multi-agent allocation techniques on problems related to Earth observation scenarios with multiple users and satellites. We focus on the problem of coordinating users having reserved exclusive orbit portions and one central planner having several requests that may use some intervals of these exclusives. We define this problem as Earth Observation Satellite Constellation Scheduling Problem (EOSCSP) and map it to a Mixed Integer Linear Program. As to solve EOSCSP, we propose market-based techniques and a distributed problem solving technique based on Distributed Constraint Optimization (DCOP), where agents cooperate to allocate requests without sharing their own schedules. These contributions are experimentally evaluated on randomly generated EOSCSP instances based on real large-scale or highly conflicting observation order books.
The Limits of Local Search for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
Venue: arXiv cs.DS 2021
Year: 2021

We consider the Maximum Weight Independent Set Problem (MWIS) in $d$-claw free graphs, i.e. the task of computing an independent set of maximum weight in a given $d$-claw free graph $G=(V,E)$ equipped with a positive weight function $w:V\rightarrow\mathbb{R}_{>0}$. For $k\geq 1$, the MWIS in $k+1$-claw free graphs generalizes the weighted $k$-Set Packing Problem. Given that for $k\geq 3$, this problem does not permit a polynomial time $o(\frac{k}{\log k})$-approximation unless $P=NP$, most previous algorithms for both weighted $k$-Set Packing and the MWIS in $d$-claw free graphs rely on local search. For the last twenty years, Berman's algorithm SquareImp, which yields a $\frac{d}{2}+ε$-approximation for the MWIS in $d$-claw free graphs, has remained unchallenged for both problems. Recently, it was improved by Neuwohner, obtaining an approximation guarantee slightly below $\frac{d}{2}$, and inevitably raising the question of how far one can get by using local search. In this paper, we finally answer this question asymptotically in the following sense: By considering local improvements of logarithmic size, we obtain approximation ratios of $\frac{d-1+ε_d}{2}$ for the MWIS in $d$-claw free graphs for $d\geq 3$ in quasi-polynomial time, where $0\leq ε_d\leq 1$ and $\lim_{d\rightarrow\infty}ε_d = 0$. By employing the color coding technique, we can use the previous result to obtain a polynomial time $\frac{k+ε_{k+1}}{2}$-approximation for weighted $k$-Set Packing. On the other hand, we provide examples showing that no local improvement algorithm considering local improvements of size $\mathcal{O}(\log(|\mathcal{S}|))$ with respect to some power $w^α$ of the weight function, where $α\in\mathbb{R}$ is chosen arbitrarily, but fixed, can yield an approximation guarantee better than $\frac{k}{2}$ for the weighted $k$-Set Packing Problem with $k\geq 3$.
Arrangements of orthogonal circles with many intersections
Venue: arXiv cs.CG 2021
Year: 2021

An arrangement of circles in which circles intersect only in angles of $π/2$ is called an \emph{arrangement of orthogonal circles}. We show that in the case that no two circles are nested, the intersection graph of such an arrangement is planar. The same result holds for arrangement of circles that intersect in an angle of at most $π/2$. For the general case we prove that the maximal number of edges in an intersection graph of an arrangement of orthogonal circles lies in between $4n - O\left(\sqrt{n}\right)$ and $\left(4+\frac{5}{11}\right)n$, for $n$ being the number of circles. Based on the lower bound we can also improve the bound for the number of triangles in arrangements of orthogonal circles to $(3 + 5/9)n-O\left(\sqrt{n}\right)$.
High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learning
Venue: arXiv cs.LG 2021
Year: 2021

We introduce a method combining variational autoencoders (VAEs) and deep metric learning to perform Bayesian optimisation (BO) over high-dimensional and structured input spaces. By adapting ideas from deep metric learning, we use label guidance from the blackbox function to structure the VAE latent space, facilitating the Gaussian process fit and yielding improved BO performance. Importantly for BO problem settings, our method operates in semi-supervised regimes where only few labelled data points are available. We run experiments on three real-world tasks, achieving state-of-the-art results on the penalised logP molecule generation benchmark using just 3% of the labelled data required by previous approaches. As a theoretical contribution, we present a proof of vanishing regret for VAE BO.
RoSearch: Search for Robust Student Architectures When Distilling Pre-trained Language Models
Venue: arXiv cs.CL 2021
Year: 2021

Pre-trained language models achieve outstanding performance in NLP tasks. Various knowledge distillation methods have been proposed to reduce the heavy computation and storage requirements of pre-trained language models. However, from our observations, student models acquired by knowledge distillation suffer from adversarial attacks, which limits their usage in security sensitive scenarios. In order to overcome these security problems, RoSearch is proposed as a comprehensive framework to search the student models with better adversarial robustness when performing knowledge distillation. A directed acyclic graph based search space is built and an evolutionary search strategy is utilized to guide the searching approach. Each searched architecture is trained by knowledge distillation on pre-trained language model and then evaluated under a robustness-, accuracy- and efficiency-aware metric as environmental fitness. Experimental results show that RoSearch can improve robustness of student models from 7%~18% up to 45.8%~47.8% on different datasets with comparable weight compression ratio to existing distillation methods (4.6$\times$~6.5$\times$ improvement from teacher model BERT_BASE) and low accuracy drop. In addition, we summarize the relationship between student architecture and robustness through statistics of searched models.
Multi-modal Entity Alignment in Hyperbolic Space
Venue: arXiv cs.AI 2021
Year: 2021

Many AI-related tasks involve the interactions of data in multiple modalities. It has been a new trend to merge multi-modal information into knowledge graph(KG), resulting in multi-modal knowledge graphs (MMKG). However, MMKGs usually suffer from low coverage and incompleteness. To mitigate this problem, a viable approach is to integrate complementary knowledge from other MMKGs. To this end, although existing entity alignment approaches could be adopted, they operate in the Euclidean space, and the resulting Euclidean entity representations can lead to large distortion of KG's hierarchical structure. Besides, the visual information has yet not been well exploited. In response to these issues, in this work, we propose a novel multi-modal entity alignment approach, Hyperbolic multi-modal entity alignment(HMEA), which extends the Euclidean representation to hyperboloid manifold. We first adopt the Hyperbolic Graph Convolutional Networks (HGCNs) to learn structural representations of entities. Regarding the visual information, we generate image embeddings using the densenet model, which are also projected into the hyperbolic space using HGCNs. Finally, we combine the structure and visual representations in the hyperbolic space and use the aggregated embeddings to predict potential alignment results. Extensive experiments and ablation studies demonstrate the effectiveness of our proposed model and its components.