OpenRaiser/Intern-Atlas huggingface dataset:
Placement and Allocation of Virtual Network Functions: Multi-dimensional Case
Venue: arXiv cs.NI 2022
Year: 2022

Network function virtualization (NFV) is an emerging design paradigm that replaces physical middlebox devices with software modules running on general purpose commodity servers. While gradually transitioning to NFV, Internet service providers face the problem of where to introduce NFV in order to make the most benefit of that; here, we measure the benefit by the amount of traffic that can be served in an NFV-enabled network. This problem is non-trivial as it is composed of two challenging subproblems: 1) placement of nodes to support virtual network functions (referred to as VNF-nodes); 2) allocation of the VNF-nodes' resources to network flows. This problem has been studied for the one-dimensional setting, where all network flows require one network function, which requires a unit of resource to process a unit of flow. In this work, we consider the multi-dimensional setting, where flows must be processed by multiple network functions, which require a different amount of each resource to process a unit of flow. The multi-dimensional setting introduces new challenges in addition to those of the one-dimensional setting (e.g., NP-hardness and non-submodularity) and also makes the resource allocation subproblem a multi-dimensional generalization of the generalized assignment problem with assignment restrictions. To address these difficulties, we propose a novel two-level relaxation method that allows us to draw a connection to the sequence submodular theory and utilize the property of sequence submodularity along with the primal-dual technique to design two approximation algorithms. We further prove that the proposed algorithms have a non-trivial approximation ratio that depends on the number of VNF-nodes, resources, and a measure of the available resource compared to flow demand. Finally, we perform trace-driven simulations to show the effectiveness of the proposed algorithms.
Intelligent Physical Attack Against Mobile Robots With Obstacle-Avoidance
Venue: arXiv cs.RO 2022
Year: 2022

The security issue of mobile robots has attracted considerable attention in recent years. In this paper, we propose an intelligent physical attack to trap mobile robots into a preset position by learning the obstacle-avoidance mechanism from external observation. The salient novelty of our work lies in revealing the possibility that physical-based attacks with intelligent and advanced design can present real threats, while without prior knowledge of the system dynamics or access to the internal system. This kind of attack cannot be handled by countermeasures in traditional cyberspace security. To practice, the cornerstone of the proposed attack is to actively explore the complex interaction characteristic of the victim robot with the environment, and learn the obstacle-avoidance knowledge exhibited in the limited observations of its behaviors. Then, we propose shortest-path and hands-off attack algorithms to find efficient attack paths from the tremendous motion space, achieving the driving-to-trap goal with low costs in terms of path length and activity period, respectively. The convergence of the algorithms is proved and the attack performance bounds are further derived. Extensive simulations and real-life experiments illustrate the effectiveness of the proposed attack, beckoning future investigation for the new physical threats and defense on robotic systems.
Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case
Venue: arXiv cs.NI 2022
Year: 2022

Deep Reinforcement Learning (DRL) has shown a dramatic improvement in decision-making and automated control problems. Consequently, DRL represents a promising technique to efficiently solve many relevant optimization problems (e.g., routing) in self-driving networks. However, existing DRL-based solutions applied to networking fail to generalize, which means that they are not able to operate properly when applied to network topologies not observed during training. This lack of generalization capability significantly hinders the deployment of DRL technologies in production networks. This is because state-of-the-art DRL-based networking solutions use standard neural networks (e.g., fully connected, convolutional), which are not suited to learn from information structured as graphs. In this paper, we integrate Graph Neural Networks (GNN) into DRL agents and we design a problem specific action space to enable generalization. GNNs are Deep Learning models inherently designed to generalize over graphs of different sizes and structures. This allows the proposed GNN-based DRL agent to learn and generalize over arbitrary network topologies. We test our DRL+GNN agent in a routing optimization use case in optical networks and evaluate it on 180 and 232 unseen synthetic and real-world network topologies respectively. The results show that the DRL+GNN agent is able to outperform state-of-the-art solutions in topologies never seen during training.
Universal Composability is Robust Compilation
Venue: arXiv cs.PL 2022
Year: 2022

This paper discusses the relationship between two frameworks: universal composability (UC) and robust compilation (RC). In cryptography, UC is a framework for the specification and analysis of cryptographic protocols with a strong compositionality guarantee: UC protocols remain secure even when composed with other protocols. In programming language security, RC is a novel framework for determining secure compilation by proving whether compiled programs are as secure as their source-level counterparts no matter what target-level code they interact with. Presently, these disciplines are studied in isolation, though we argue that there is a deep connection between them and exploring this connection will benefit both research fields. This paper formally proves the connection between UC and RC and then it explores the benefits of this connection. For this, this paper first identifies which conditions must programming languages fulfil in order to possibly attain UC-like composition. Then, it proves UC of both an existing and a new commitment protocol as a corollary of the related compilers attaining RC. Finally, it mechanises these proofs in Deepsec, obtaining symbolic guarantees that the protocol is indeed UC. Our connection lays the groundwork towards a better and deeper understanding of both UC and RC, and the benefits we showcase from this connection provide first evidence of scalable mechanised proofs for UC.
Amortized Rejection Sampling in Universal Probabilistic Programming
Venue: arXiv cs.LG 2022
Year: 2022

Naive approaches to amortized inference in probabilistic programs with unbounded loops can produce estimators with infinite variance. This is particularly true of importance sampling inference in programs that explicitly include rejection sampling as part of the user-programmed generative procedure. In this paper we develop a new and efficient amortized importance sampling estimator. We prove finite variance of our estimator and empirically demonstrate our method's correctness and efficiency compared to existing alternatives on generative programs containing rejection sampling loops and discuss how to implement our method in a generic probabilistic programming framework.
The Distribution Function of the Longest Path Length in Constant Treewidth DAGs with Random Edge Length
Venue: arXiv cs.CC 2022
Year: 2022

This paper is about the length $X_{\rm MAX}$ of the longest path in directed acyclic graph (DAG) $G=(V,E)$ with random edge lengths, where $|V|=n$ and $|E|=m$. When the edge lengths are mutually independent and uniformly distributed, the problem of computing the distribution function $\Pr[X_{\rm MAX}\le x]$ is known to be $\#$P-hard even in case $G$ is a directed path. In this case, $\Pr[X_{\rm MAX}\le x]$ is equal to the volume of the knapsack polytope, an $m$-dimensional unit hypercube truncated by a halfspace. In this paper, we show that there is a deterministic fully polynomial time approximation scheme (FPTAS) for computing $\Pr[X_{\rm MAX}\le x]$ in case the treewidth of $G$ is at most a constant $k$. The running time of our algorithm is $O(k^2 n(\frac{16(k+1)mn^2}ε)^{4k^2+6k+2})$ to achieve a multiplicative approximation ratio $1+ε$. Before our FPTAS, we present a fundamental formula that represents $\Pr[X_{\rm MAX}\le x]$ by at most $n-1$ repetitions of definite integrals. Moreover, in case the edge lengths follow the mutually independent standard exponential distribution, we show a $((4k+2)mn)^{O(k)}$ time exact algorithm. For random edge lengths satisfying certain conditions, we also show that computing $\Pr[X_{\rm MAX}\le x]$ is fixed parameter tractable if we choose treewidth $k$, the additive error $ε'$, and $x$ as the parameters.
Contrastive Representation Distillation
Venue: arXiv cs.LG 2022
Year: 2022

Often we wish to transfer representational knowledge from one neural network to another. Examples include distilling a large network into a smaller one, transferring knowledge from one sensory modality to a second, or ensembling a collection of models into a single estimator. Knowledge distillation, the standard approach to these problems, minimizes the KL divergence between the probabilistic outputs of a teacher and student network. We demonstrate that this objective ignores important structural knowledge of the teacher network. This motivates an alternative objective by which we train a student to capture significantly more information in the teacher's representation of the data. We formulate this objective as contrastive learning. Experiments demonstrate that our resulting new objective outperforms knowledge distillation and other cutting-edge distillers on a variety of knowledge transfer tasks, including single model compression, ensemble distillation, and cross-modal transfer. Our method sets a new state-of-the-art in many transfer tasks, and sometimes even outperforms the teacher network when combined with knowledge distillation. Code: http://github.com/HobbitLong/RepDistiller.
Cubic Metric Reduction for Repetitive CAZAC Sequences in frequency domain
Venue: arXiv cs.IT 2022
Year: 2022

In NR-based Access to Unlicensed Spectrum (NR-U) of 5G system, to satisfy the rules of Occupied Channel Bandwidth (OCB) of unlicensed spectrum, the channels of PRACH and PUCCH have to use some sequence repetition mechanisms in frequency domain. These repetition mechanisms will cause serious cubic metric(CM) problems for these channels, although these two types of channels are composed of Constant Amplitude Zero Auto-correlation(CAZAC) sequences.. Based on the characteristics of CAZAC sequences, which are used for PRACH and PUCCH (refer to PUCCH format 0 and format 1) in 5G NR, in this paper, we propose some new mechanisms of CM reduction for these two types of channels considering the design principles to ensure the sequence performance of the auto-correlation and cross-correlation. Then the proposed CM schemes are evaluated and the optimized parameters are further provided considering CM performance and the complexity.
A Unified MRC Framework for Named Entity Recognition
Venue: arXiv cs.CL 2022
Year: 2022

The task of named entity recognition (NER) is normally divided into nested NER and flat NER depending on whether named entities are nested or not. Models are usually separately developed for the two tasks, since sequence labeling models, the most widely used backbone for flat NER, are only able to assign a single label to a particular token, which is unsuitable for nested NER where a token may be assigned several labels. In this paper, we propose a unified framework that is capable of handling both flat and nested NER tasks. Instead of treating the task of NER as a sequence labeling problem, we propose to formulate it as a machine reading comprehension (MRC) task. For example, extracting entities with the \textsc{per} label is formalized as extracting answer spans to the question "{\it which person is mentioned in the text?}". This formulation naturally tackles the entity overlapping issue in nested NER: the extraction of two overlapping entities for different categories requires answering two independent questions. Additionally, since the query encodes informative prior knowledge, this strategy facilitates the process of entity extraction, leading to better performances for not only nested NER, but flat NER. We conduct experiments on both {\em nested} and {\em flat} NER datasets. Experimental results demonstrate the effectiveness of the proposed formulation. We are able to achieve vast amount of performance boost over current SOTA models on nested NER datasets, i.e., +1.28, +2.55, +5.44, +6.37, respectively on ACE04, ACE05, GENIA and KBP17, along with SOTA results on flat NER datasets, i.e.,+0.24, +1.95, +0.21, +1.49 respectively on English CoNLL 2003, English OntoNotes 5.0, Chinese MSRA, Chinese OntoNotes 4.0.
Residuality and Learning for Nondeterministic Nominal Automata
Venue: arXiv cs.FL 2022
Year: 2022

We are motivated by the following question: which data languages admit an active learning algorithm? This question was left open in previous work by the authors, and is particularly challenging for languages recognised by nondeterministic automata. To answer it, we develop the theory of residual nominal automata, a subclass of nondeterministic nominal automata. We prove that this class has canonical representatives, which can always be constructed via a finite number of observations. This property enables active learning algorithms, and makes up for the fact that residuality -- a semantic property -- is undecidable for nominal automata. Our construction for canonical residual automata is based on a machine-independent characterisation of residual languages, for which we develop new results in nominal lattice theory. Studying residuality in the context of nominal languages is a step towards a better understanding of learnability of automata with some sort of nondeterminism.
A framework for deep learning emulation of numerical models with a case study in satellite remote sensing
Venue: arXiv cs.LG 2022
Year: 2022

Numerical models based on physics represent the state-of-the-art in earth system modeling and comprise our best tools for generating insights and predictions. Despite rapid growth in computational power, the perceived need for higher model resolutions overwhelms the latest-generation computers, reducing the ability of modelers to generate simulations for understanding parameter sensitivities and characterizing variability and uncertainty. Thus, surrogate models are often developed to capture the essential attributes of the full-blown numerical models. Recent successes of machine learning methods, especially deep learning, across many disciplines offer the possibility that complex nonlinear connectionist representations may be able to capture the underlying complex structures and nonlinear processes in earth systems. A difficult test for deep learning-based emulation, which refers to function approximation of numerical models, is to understand whether they can be comparable to traditional forms of surrogate models in terms of computational efficiency while simultaneously reproducing model results in a credible manner. A deep learning emulation that passes this test may be expected to perform even better than simple models with respect to capturing complex processes and spatiotemporal dependencies. Here we examine, with a case study in satellite-based remote sensing, the hypothesis that deep learning approaches can credibly represent the simulations from a surrogate model with comparable computational efficiency. Our results are encouraging in that the deep learning emulation reproduces the results with acceptable accuracy and often even faster performance. We discuss the broader implications of our results in light of the pace of improvements in high-performance implementations of deep learning as well as the growing desire for higher-resolution simulations in the earth sciences.
A Relational Program Logic with Data Abstraction and Dynamic Framing
Venue: arXiv cs.LO 2022
Year: 2022

Dedicated to Tony Hoare. In a paper published in 1972 Hoare articulated the fundamental notions of hiding invariants and simulations. Hiding: invariants on encapsulated data representations need not be mentioned in specifications that comprise the API of a module. Simulation: correctness of a new data representation and implementation can be established by proving simulation between the old and new implementations using a coupling relation defined on the encapsulated state. These results were formalized semantically and for a simple model of state, though the paper claimed this could be extended to encompass dynamically allocated objects. In recent years, progress has been made towards formalizing the claim, for simulation, though mainly in semantic developments. In this article, hiding and simulation are combined with the idea in Hoare's 1969 paper: a logic of programs. For an object-based language with dynamic allocation, we introduce a relational Hoare logic with stateful frame conditions that formalizes encapsulation, hiding of invariants, and couplings that relate two implementations. Relations and other assertions are expressed in first-order logic. Specifications can express a wide range of relational properties such as conditional equivalence and noninterference with declassification. The proof rules facilitate relational reasoning by means of convenient alignments and are shown sound with respect to a conventional operational semantics. A derived proof rule for equivalence of linked programs directly embodies representation independence. Applicability to representative examples is demonstrated using an SMT-based implementation.
Toward a Better Monitoring Statistic for Profile Monitoring via Variational Autoencoders
Venue: arXiv cs.LG 2022
Year: 2022

Wide accessibility of imaging and profile sensors in modern industrial systems created an abundance of high-dimensional sensing variables. This led to a a growing interest in the research of high-dimensional process monitoring. However, most of the approaches in the literature assume the in-control population to lie on a linear manifold with a given basis (i.e., spline, wavelet, kernel, etc) or an unknown basis (i.e., principal component analysis and its variants), which cannot be used to efficiently model profiles with a nonlinear manifold which is common in many real-life cases. We propose deep probabilistic autoencoders as a viable unsupervised learning approach to model such manifolds. To do so, we formulate nonlinear and probabilistic extensions of the monitoring statistics from classical approaches as the expected reconstruction error (ERE) and the KL-divergence (KLD) based monitoring statistics. Through extensive simulation study, we provide insights on why latent-space based statistics are unreliable and why residual-space based ones typically perform much better for deep learning based approaches. Finally, we demonstrate the superiority of deep probabilistic models via both simulation study and a real-life case study involving images of defects from a hot steel rolling process.
Diffusion Improves Graph Learning
Venue: arXiv cs.SI 2022
Year: 2022

Graph convolution is the core of most Graph Neural Networks (GNNs) and usually approximated by message passing between direct (one-hop) neighbors. In this work, we remove the restriction of using only the direct neighbors by introducing a powerful, yet spatially localized graph convolution: Graph diffusion convolution (GDC). GDC leverages generalized graph diffusion, examples of which are the heat kernel and personalized PageRank. It alleviates the problem of noisy and often arbitrarily defined edges in real graphs. We show that GDC is closely related to spectral-based models and thus combines the strengths of both spatial (message passing) and spectral methods. We demonstrate that replacing message passing with graph diffusion convolution consistently leads to significant performance improvements across a wide range of models on both supervised and unsupervised tasks and a variety of datasets. Furthermore, GDC is not limited to GNNs but can trivially be combined with any graph-based model or algorithm (e.g. spectral clustering) without requiring any changes to the latter or affecting its computational complexity. Our implementation is available online.
Ocular Recognition Databases and Competitions: A Survey
Venue: arXiv cs.CV 2022
Year: 2022

The use of the iris and periocular region as biometric traits has been extensively investigated, mainly due to the singularity of the iris features and the use of the periocular region when the image resolution is not sufficient to extract iris information. In addition to providing information about an individual's identity, features extracted from these traits can also be explored to obtain other information such as the individual's gender, the influence of drug use, the use of contact lenses, spoofing, among others. This work presents a survey of the databases created for ocular recognition, detailing their protocols and how their images were acquired. We also describe and discuss the most popular ocular recognition competitions (contests), highlighting the submitted algorithms that achieved the best results using only iris trait and also fusing iris and periocular region information. Finally, we describe some relevant works applying deep learning techniques to ocular recognition and point out new challenges and future directions. Considering that there are a large number of ocular databases, and each one is usually designed for a specific problem, we believe this survey can provide a broad overview of the challenges in ocular biometrics.
GGNN: Graph-based GPU Nearest Neighbor Search
Venue: arXiv cs.CV 2022
Year: 2022

Approximate nearest neighbor (ANN) search in high dimensions is an integral part of several computer vision systems and gains importance in deep learning with explicit memory representations. Since PQT, FAISS, and SONG started to leverage the massive parallelism offered by GPUs, GPU-based implementations are a crucial resource for today's state-of-the-art ANN methods. While most of these methods allow for faster queries, less emphasis is devoted to accelerating the construction of the underlying index structures. In this paper, we propose a novel GPU-friendly search structure based on nearest neighbor graphs and information propagation on graphs. Our method is designed to take advantage of GPU architectures to accelerate the hierarchical construction of the index structure and for performing the query. Empirical evaluation shows that GGNN significantly surpasses the state-of-the-art CPU- and GPU-based systems in terms of build-time, accuracy and search speed.