OpenRaiser/Intern-Atlas huggingface dataset:
Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations
Venue: arXiv cs.CL 2022
Year: 2022

Long Short-Term Memory (LSTM) and Transformers are two popular neural architectures used for natural language processing tasks. Theoretical results show that both are Turing-complete and can represent any context-free language (CFL).In practice, it is often observed that Transformer models have better representation power than LSTM. But the reason is barely understood. We study such practical differences between LSTM and Transformer and propose an explanation based on their latent space decomposition patterns. To achieve this goal, we introduce an oracle training paradigm, which forces the decomposition of the latent representation of LSTM and the Transformer and supervises with the transitions of the Pushdown Automaton (PDA) of the corresponding CFL. With the forced decomposition, we show that the performance upper bounds of LSTM and Transformer in learning CFL are close: both of them can simulate a stack and perform stack operation along with state transitions. However, the absence of forced decomposition leads to the failure of LSTM models to capture the stack and stack operations, while having a marginal impact on the Transformer model. Lastly, we connect the experiment on the prototypical PDA to a real-world parsing task to re-verify the conclusions
Incomplete Knowledge Graph Alignment
Venue: arXiv cs.CL 2022
Year: 2022

Knowledge graph (KG) alignment - the task of recognizing entities referring to the same thing in different KGs - is recognized as one of the most important operations in the field of KG construction and completion. However, existing alignment techniques often assume that the input KGs are complete and isomorphic, which is not true due to the real-world heterogeneity in the domain, size, and sparsity. In this work, we address the problem of aligning incomplete KGs with representation learning. Our KG embedding framework exploits two feature channels: transitivity-based and proximity-based. The former captures the consistency constraints between entities via translation paths, while the latter captures the neighbourhood structure of KGs via attention guided relation-aware graph neural network. The two feature channels are jointly learned to exchange important features between the input KGs while enforcing the output representations of the input KGs in the same embedding space. Also, we develop a missing links detector that discovers and recovers the missing links in the input KGs during the training process, which helps mitigate the incompleteness issue and thus improve the compatibility of the learned representations. The embeddings then are fused to generate the alignment result, and the high-confidence matched node pairs are updated to the pre-aligned supervision data to improve the embeddings gradually. Empirical results show that our model is more accurate than the SOTA and is robust against different levels of incompleteness.
Human-vehicle Cooperative Visual Perception for Autonomous Driving under Complex Road and Traffic Scenarios
Venue: arXiv cs.CV 2022
Year: 2022

Human-vehicle cooperative driving has become the critical technology of autonomous driving, which reduces the workload of human drivers. However, the complex and uncertain road environments bring great challenges to the visual perception of cooperative systems. And the perception characteristics of autonomous driving differ from manual driving a lot. To enhance the visual perception capability of human-vehicle cooperative driving, this paper proposed a cooperative visual perception model. 506 images of complex road and traffic scenarios were collected as the data source. Then this paper improved the object detection algorithm of autonomous vehicles. The mean perception accuracy of traffic elements reached 75.52%. By the image fusion method, the gaze points of human drivers were fused with vehicles' monitoring screens. Results revealed that cooperative visual perception could reflect the riskiest zone and predict the trajectory of conflict objects more precisely. The findings can be applied in improving the visual perception algorithms and providing accurate data for planning and control.
D3PG: Dirichlet DDPG for Task Partitioning and Offloading with Constrained Hybrid Action Space in Mobile Edge Computing
Venue: arXiv cs.NI 2022
Year: 2022

Mobile Edge Computing (MEC) has been regarded as a promising paradigm to reduce service latency for data processing in the Internet of Things, by provisioning computing resources at the network edge. In this work, we jointly optimize the task partitioning and computational power allocation for computation offloading in a dynamic environment with multiple IoT devices and multiple edge servers. We formulate the problem as a Markov decision process with constrained hybrid action space, which cannot be well handled by existing deep reinforcement learning (DRL) algorithms. Therefore, we develop a novel Deep Reinforcement Learning called Dirichlet Deep Deterministic Policy Gradient (D3PG), which is built on Deep Deterministic Policy Gradient (DDPG) to solve the problem. The developed model can learn to solve multi-objective optimization, including maximizing the number of tasks processed before expiration and minimizing the energy cost and service latency.} More importantly, D3PG can effectively deal with constrained distribution-continuous hybrid action space, where the distribution variables are for the task partitioning and offloading, while the continuous variables are for computational frequency control. Moreover, the D3PG can address many similar issues in MEC and general reinforcement learning problems. Extensive simulation results show that the proposed D3PG outperforms the state-of-art methods.
WIP: Exploring DSME MAC for LoRa -- A System Integration and First Evaluation
Venue: arXiv cs.NI 2022
Year: 2022

LoRa is a popular wireless technology that enables low-throughput (bytes) long-range communication (km) at low energy consumption (mW). Its transmission, though, is on one side prone to interference during long on-air times, and on the other side subject to duty cycle restrictions. LoRaWAN defines a MAC and a vertical stack on top of LoRa. LoRaWAN circumvents the above limitations by imposing a centralized network architecture, which heavily reduces downlink capacity and prevents peer-to-peer communication. This makes it unusable for many deployments. The Deterministic and Synchronous Multichannel Extension (DSME) of IEEE 802.15.4e benefits of time-slotted communication and peer-to-peer communication and has the potential to overcome LoRaWAN limitations. In this work, we implement DSME on top of LoRa in the open source IoT OS RIOT and open the field for first evaluation experiments on real hardware. Initial results indicate that DSME-LoRa not only enables reliable peer-to-peer communication for constrained IoT devices, but also scales with an increasing number of nodes.
Weakly Supervised Semantic Segmentation via Alternative Self-Dual Teaching
Venue: arXiv cs.CV 2022
Year: 2022

Current weakly supervised semantic segmentation (WSSS) frameworks usually contain the separated mask-refinement model and the main semantic region mining model. These approaches would contain redundant feature extraction backbones and biased learning objectives, making them computational complex yet sub-optimal to addressing the WSSS task. To solve this problem, this paper establishes a compact learning framework that embeds the classification and mask-refinement components into a unified deep model. With the shared feature extraction backbone, our model is able to facilitate knowledge sharing between the two components while preserving a low computational complexity. To encourage high-quality knowledge interaction, we propose a novel alternative self-dual teaching (ASDT) mechanism. Unlike the conventional distillation strategy, the knowledge of the two teacher branches in our model is alternatively distilled to the student branch by a Pulse Width Modulation (PWM), which generates PW wave-like selection signal to guide the knowledge distillation process. In this way, the student branch can help prevent the model from falling into local minimum solutions caused by the imperfect knowledge provided of either teacher branch. Comprehensive experiments on the PASCAL VOC 2012 and COCO-Stuff 10K demonstrate the effectiveness of the proposed alternative self-dual teaching mechanism as well as the new state-of-the-art performance of our approach.
Learning from Heterogeneous Data Based on Social Interactions over Graphs
Venue: arXiv cs.LG 2022
Year: 2022

This work proposes a decentralized architecture, where individual agents aim at solving a classification problem while observing streaming features of different dimensions and arising from possibly different distributions. In the context of social learning, several useful strategies have been developed, which solve decision making problems through local cooperation across distributed agents and allow them to learn from streaming data. However, traditional social learning strategies rely on the fundamental assumption that each agent has significant prior knowledge of the underlying distribution of the observations. In this work we overcome this issue by introducing a machine learning framework that exploits social interactions over a graph, leading to a fully data-driven solution to the distributed classification problem. In the proposed social machine learning (SML) strategy, two phases are present: in the training phase, classifiers are independently trained to generate a belief over a set of hypotheses using a finite number of training samples; in the prediction phase, classifiers evaluate streaming unlabeled observations and share their instantaneous beliefs with neighboring classifiers. We show that the SML strategy enables the agents to learn consistently under this highly-heterogeneous setting and allows the network to continue learning even during the prediction phase when it is deciding on unlabeled samples. The prediction decisions are used to continually improve performance thereafter in a manner that is markedly different from most existing static classification schemes where, following training, the decisions on unlabeled data are not re-used to improve future performance.
Distill and De-bias: Mitigating Bias in Face Verification using Knowledge Distillation
Venue: arXiv cs.CV 2022
Year: 2022

Face recognition networks generally demonstrate bias with respect to sensitive attributes like gender, skintone etc. For gender and skintone, we observe that the regions of the face that a network attends to vary by the category of an attribute. This might contribute to bias. Building on this intuition, we propose a novel distillation-based approach called Distill and De-bias (D&D) to enforce a network to attend to similar face regions, irrespective of the attribute category. In D&D, we train a teacher network on images from one category of an attribute; e.g. light skintone. Then distilling information from the teacher, we train a student network on images of the remaining category; e.g., dark skintone. A feature-level distillation loss constrains the student network to generate teacher-like representations. This allows the student network to attend to similar face regions for all attribute categories and enables it to reduce bias. We also propose a second distillation step on top of D&D, called D&D++. Here, we distill the `un-biasedness' of the D&D network into a new student network, the D&D++ network, while training this new network on all attribute categories; e.g., both light and dark skintones. This helps us train a network that is less biased for an attribute, while obtaining higher face verification performance than D&D. We show that D&D++ outperforms existing baselines in reducing gender and skintone bias on the IJB-C dataset, while obtaining higher face verification performance than existing adversarial de-biasing methods. We evaluate the effectiveness of our proposed methods on two state-of-the-art face recognition networks: ArcFace and Crystalface.
Heavy-tailed denoising score matching
Venue: arXiv cs.LG 2022
Year: 2022

Score-based model research in the last few years has produced state of the art generative models by employing Gaussian denoising score-matching (DSM). However, the Gaussian noise assumption has several high-dimensional limitations, motivating a more concrete route toward even higher dimension PDF estimation in future. We outline this limitation, before extending the theory to a broader family of noising distributions -- namely, the generalised normal distribution. To theoretically ground this, we relax a key assumption in (denoising) score matching theory, demonstrating that distributions which are differentiable almost everywhere permit the same objective simplification as Gaussians. For noise vector norm distributions, we demonstrate favourable concentration of measure in the high-dimensional spaces prevalent in deep learning. In the process, we uncover a skewed noise vector norm distribution and develop an iterative noise scaling algorithm to consistently initialise the multiple levels of noise in annealed Langevin dynamics (LD). On the practical side, our use of heavy-tailed DSM leads to improved score estimation, controllable sampling convergence, and more balanced unconditional generative performance for imbalanced datasets.
Playing Against Fair Adversaries in Stochastic Games with Total Rewards
Venue: arXiv cs.LO 2022
Year: 2022

We investigate zero-sum turn-based two-player stochastic games in which the objective of one player is to maximize the amount of rewards obtained during a play, while the other aims at minimizing it. We focus on games in which the minimizer plays in a fair way. We believe that these kinds of games enjoy interesting applications in software verification, where the maximizer plays the role of a system intending to maximize the number of "milestones" achieved, and the minimizer represents the behavior of some uncooperative but yet fair environment. Normally, to study total reward properties, games are requested to be stopping (i.e., they reach a terminal state with probability 1). We relax the property to request that the game is stopping only under a fair minimizing player. We prove that these games are determined, i.e., each state of the game has a value defined. Furthermore, we show that both players have memoryless and deterministic optimal strategies, and the game value can be computed by approximating the greatest-fixed point of a set of functional equations. We implemented our approach in a prototype tool, and evaluated it on an illustrating example and an Unmanned Aerial Vehicle case study.
Android-COCO: Android Malware Detection with Graph Neural Network for Byte- and Native-Code
Venue: arXiv cs.CR 2022
Year: 2022

With the popularity of Android growing exponentially, the amount of malware has significantly exploded. It is arguably one of the most viral problems on mobile platforms. Recently, various approaches have been introduced to detect Android malware, the majority of these are either based on the Manifest File features or the structural information, such as control flow graph and API calls. Among those methods, nearly all of them only consider the Java byte-code as the target to detect malicious behaviors. However, Recent research and our own statistics show that native payloads are commonly used in both benign and malicious apps. Current state-of-the-art Android static analysis tools avoid handling native method invocation. None of those tools have the capability to capture the inter-language behaviors. In this work, we explore an ensemble mechanism, which presents how the combination of byte-code and native-code analysis of Android applications can be efficiently used to cope with the advanced sophistication of Android malware. We, therefore, present a multi-layer approach that utilizes deep learning, natural language processing (NLP), as well as graph embedding techniques to handle the threats of Android malware, both from the Java byte-code and native code. After that, we design an ensemble algorithm to get the final result of malware detection system. To be specific, the first layer of our detection approach operates on the byte-code of application and the native code level, whereas the second layer focuses on the ensemble algorithm. Large-scale experiments on 100,113 samples (35,113 malware and 65,000 benign) show that only byte-code sub-system yields 99.8% accuracy and native-code sub-system yields an accuracy of 96.6%, whereas the Android-COCO method attains an accuracy of 99.86% which outperforms various related works.
Reconfigurable Intelligent Surface for Physical Layer Key Generation: Constructive or Destructive?
Venue: arXiv cs.IT 2022
Year: 2022

Physical layer key generation (PKG) is a promising means to provide on-the-fly shared secret keys by exploiting the intrinsic randomness of the radio channel. However, the performance of PKG is highly dependent on the propagation environments. Due to its feature of controlling the wireless environment, reconfigurable intelligent surface~(RIS) is appealing to be applied in PKG. In this paper, in contrast to the existing literature, we investigate both the constructive and destructive effects of RIS on the PKG scheme. For the constructive aspect, we have identified static and wave-blockage environments as two RIS-empowered-PKG applications in future wireless systems. In particular, our experimental results in a static environment showed that RIS can enhance the entropy of the secret key, achieving a key generation rate (KGR) of 97.39 bit/s with a bit disagreement rate (BDR) of 0.083. In multi-user systems where some remote users are in worse channel conditions, the proposed RIS-assisted PKG algorithm improves the sum secret key rate by more than 2 dB, compared to the literature. Furthermore, we point out that RIS could be utilized by an attacker to perform new jamming and leakage attacks and give countermeasures, respectively. Finally, we outline future research directions for PKG systems in light of the RIS.
Balancing Adaptability and Non-exploitability in Repeated Games
Venue: arXiv cs.GT 2022
Year: 2022

We study the problem of guaranteeing low regret in repeated games against an opponent with unknown membership in one of several classes. We add the constraint that our algorithm is non-exploitable, in that the opponent lacks an incentive to use an algorithm against which we cannot achieve rewards exceeding some "fair" value. Our solution is an expert algorithm (LAFF) that searches within a set of sub-algorithms that are optimal for each opponent class and uses a punishment policy upon detecting evidence of exploitation by the opponent. With benchmarks that depend on the opponent class, we show that LAFF has sublinear regret uniformly over the possible opponents, except exploitative ones, for which we guarantee that the opponent has linear regret. To our knowledge, this work is the first to provide guarantees for both regret and non-exploitability in multi-agent learning.
CGIBNet: Bandwidth-constrained Communication with Graph Information Bottleneck in Multi-Agent Reinforcement Learning
Venue: arXiv cs.AI 2022
Year: 2022

Communication is one of the core components for cooperative multi-agent reinforcement learning (MARL). The communication bandwidth, in many real applications, is always subject to certain constraints. To improve communication efficiency, in this article, we propose to simultaneously optimize whom to communicate with and what to communicate for each agent in MARL. By initiating the communication between agents with a directed complete graph, we propose a novel communication model, named Communicative Graph Information Bottleneck Network (CGIBNet), to simultaneously compress the graph structure and the node information with the graph information bottleneck principle. The graph structure compression is designed to cut the redundant edges for determining whom to communicate with. The node information compression aims to address the problem of what to communicate via learning compact node representations. Moreover, CGIBNet is the first universal module for bandwidth-constrained communication, which can be applied to various training frameworks (i.e., policy-based and value-based MARL frameworks) and communication modes (i.e., single-round and multi-round communication). Extensive experiments are conducted in Traffic Control and StarCraft II environments. The results indicate that our method can achieve better performance in bandwidth-constrained settings compared with state-of-the-art algorithms.
Mind-proofing Your Phone: Navigating the Digital Minefield with GreaseTerminator
Venue: arXiv cs.HC 2022
Year: 2022

Digital harms are widespread in the mobile ecosystem. As these devices gain ever more prominence in our daily lives, so too increases the potential for malicious attacks against individuals. The last line of defense against a range of digital harms - including digital distraction, political polarisation through hate speech, and children being exposed to damaging material - is the user interface. This work introduces GreaseTerminator to enable researchers to develop, deploy, and test interventions against these harms with end-users. We demonstrate the ease of intervention development and deployment, as well as the broad range of harms potentially covered with GreaseTerminator in five in-depth case studies.
Minimizing Congestion for Balanced Dominators
Venue: arXiv cs.DS 2022
Year: 2022

A primary challenge in metagenomics is reconstructing individual microbial genomes from the mixture of short fragments created by sequencing. Recent work leverages the sparsity of the assembly graph to find $r$-dominating sets which enable rapid approximate queries through a dominator-centric graph partition. In this paper, we consider two problems related to reducing uncertainty and improving scalability in this setting. First, we observe that nodes with multiple closest dominators necessitate arbitrary tie-breaking in the existing pipeline. As such, we propose finding $\textit{sparse}$ dominating sets which minimize this effect via a new $\textit{congestion}$ parameter. We prove minimizing congestion is NP-hard, and give an $\mathcal{O}(\sqrt{Δ^r})$ approximation algorithm, where $Δ$ is the max degree. To improve scalability, the graph should be partitioned into uniformly sized pieces, subject to placing vertices with a closest dominator. This leads to $\textit{balanced neighborhood partitioning}$: given an $r$-dominating set, find a partition into connected subgraphs with optimal uniformity so that each vertex is co-assigned with some closest dominator. Using variance of piece sizes to measure uniformity, we show this problem is NP-hard iff $r$ is greater than $1$. We design and analyze several algorithms, including a polynomial-time approach which is exact when $r=1$ (and heuristic otherwise). We complement our theoretical results with computational experiments on a corpus of real-world networks showing sparse dominating sets lead to more balanced neighborhood partitionings. Further, on the metagenome $\textsf{HuSB1}$, our approach maintains high query containment and similarity while reducing piece size variance.