OpenRaiser/Intern-Atlas huggingface dataset:
Coresets for the Nearest-Neighbor Rule
Venue: arXiv cs.CG 2020
Year: 2020

Given a training set $P$ of labeled points, the nearest-neighbor rule predicts the class of an unlabeled query point as the label of its closest point in the set. To improve the time and space complexity of classification, a natural question is how to reduce the training set without significantly affecting the accuracy of the nearest-neighbor rule. Nearest-neighbor condensation deals with finding a subset $R \subseteq P$ such that for every point $p \in P$, $p$'s nearest-neighbor in $R$ has the same label as $p$. This relates to the concept of coresets, which can be broadly defined as subsets of the set, such that an exact result on the coreset corresponds to an approximate result on the original set. However, the guarantees of a coreset hold for any query point, and not only for the points of the training set. This paper introduces the concept of coresets for nearest-neighbor classification. We extend existing criteria used for condensation, and prove sufficient conditions to correctly classify any query point when using these subsets. Additionally, we prove that finding such subsets of minimum cardinality is NP-hard, and propose quadratic-time approximation algorithms with provable upper-bounds on the size of their selected subsets. Moreover, we show how to improve one of these algorithms to have subquadratic runtime, being the first of this kind for condensation.
SBERT-WK: A Sentence Embedding Method by Dissecting BERT-based Word Models
Venue: arXiv cs.CL 2020
Year: 2020

Sentence embedding is an important research topic in natural language processing (NLP) since it can transfer knowledge to downstream tasks. Meanwhile, a contextualized word representation, called BERT, achieves the state-of-the-art performance in quite a few NLP tasks. Yet, it is an open problem to generate a high quality sentence representation from BERT-based word models. It was shown in previous study that different layers of BERT capture different linguistic properties. This allows us to fusion information across layers to find better sentence representation. In this work, we study the layer-wise pattern of the word representation of deep contextualized models. Then, we propose a new sentence embedding method by dissecting BERT-based word models through geometric analysis of the space spanned by the word representation. It is called the SBERT-WK method. No further training is required in SBERT-WK. We evaluate SBERT-WK on semantic textual similarity and downstream supervised tasks. Furthermore, ten sentence-level probing tasks are presented for detailed linguistic analysis. Experiments show that SBERT-WK achieves the state-of-the-art performance. Our codes are publicly available.
Gaussian Smoothen Semantic Features (GSSF) -- Exploring the Linguistic Aspects of Visual Captioning in Indian Languages (Bengali) Using MSCOCO Framework
Venue: arXiv cs.CL 2020
Year: 2020

In this work, we have introduced Gaussian Smoothen Semantic Features (GSSF) for Better Semantic Selection for Indian regional language-based image captioning and introduced a procedure where we used the existing translation and English crowd-sourced sentences for training. We have shown that this architecture is a promising alternative source, where there is a crunch in resources. Our main contribution of this work is the development of deep learning architectures for the Bengali language (is the fifth widely spoken language in the world) with a completely different grammar and language attributes. We have shown that these are working well for complex applications like language generation from image contexts and can diversify the representation through introducing constraints, more extensive features, and unique feature spaces. We also established that we could achieve absolute precision and diversity when we use smoothened semantic tensor with the traditional LSTM and feature decomposition networks. With better learning architecture, we succeeded in establishing an automated algorithm and assessment procedure that can help in the evaluation of competent applications without the requirement for expertise and human intervention.
Multi-layer Representation Fusion for Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Neural machine translation systems require a number of stacked layers for deep models. But the prediction depends on the sentence representation of the top-most layer with no access to low-level representations. This makes it more difficult to train the model and poses a risk of information loss to prediction. In this paper, we propose a multi-layer representation fusion (MLRF) approach to fusing stacked layers. In particular, we design three fusion functions to learn a better representation from the stack. Experimental results show that our approach yields improvements of 0.92 and 0.56 BLEU points over the strong Transformer baseline on IWSLT German-English and NIST Chinese-English MT tasks respectively. The result is new state-of-the-art in German-English translation.
From Matching with Diversity Constraints to Matching with Regional Quotas
Venue: arXiv cs.GT 2020
Year: 2020

In the past few years, several new matching models have been proposed and studied that take into account complex distributional constraints. Relevant lines of work include (1) school choice with diversity constraints where students have (possibly overlapping) types and (2) hospital-doctor matching where various regional quotas are imposed. In this paper, we present a polynomial-time reduction to transform an instance of (1) to an instance of (2) and we show how the feasibility and stability of corresponding matchings are preserved under the reduction. Our reduction provides a formal connection between two important strands of work on matching with distributional constraints. We then apply the reduction in two ways. Firstly, we show that it is NP-complete to check whether a feasible and stable outcome for (1) exists. Due to our reduction, these NP-completeness results carry over to setting (2). In view of this, we help unify some of the results that have been presented in the literature. Secondly, if we have positive results for (2), then we have corresponding results for (1). One key conclusion of our results is that further developments on axiomatic and algorithmic aspects of hospital-doctor matching with regional quotas will result in corresponding results for school choice with diversity constraints.
Detecting $k$-(Sub-)Cadences and Equidistant Subsequence Occurrences
Venue: arXiv cs.DS 2020
Year: 2020

The equidistant subsequence pattern matching problem is considered. Given a pattern string $P$ and a text string $T$, we say that $P$ is an \emph{equidistant subsequence} of $T$ if $P$ is a subsequence of the text such that consecutive symbols of $P$ in the occurrence are equally spaced. We can consider the problem of equidistant subsequences as generalizations of (sub-)cadences. We give bit-parallel algorithms that yield $o(n^2)$ time algorithms for finding $k$-(sub-)cadences and equidistant subsequences. Furthermore, $O(n\log^2 n)$ and $O(n\log n)$ time algorithms, respectively for equidistant and Abelian equidistant matching for the case $|P| = 3$, are shown. The algorithms make use of a technique that was recently introduced which can efficiently compute convolutions with linear constraints.
Deep Domain Adaptive Object Detection: a Survey
Venue: arXiv cs.CV 2020
Year: 2020

Deep learning (DL) based object detection has achieved great progress. These methods typically assume that large amount of labeled training data is available, and training and test data are drawn from an identical distribution. However, the two assumptions are not always hold in practice. Deep domain adaptive object detection (DDAOD) has emerged as a new learning paradigm to address the above mentioned challenges. This paper aims to review the state-of-the-art progress on deep domain adaptive object detection approaches. Firstly, we introduce briefly the basic concepts of deep domain adaptation. Secondly, the deep domain adaptive detectors are classified into five categories and detailed descriptions of representative methods in each category are provided. Finally, insights for future research trend are presented.
HotelRec: a Novel Very Large-Scale Hotel Recommendation Dataset
Venue: arXiv cs.IR 2020
Year: 2020

Today, recommender systems are an inevitable part of everyone's daily digital routine and are present on most internet platforms. State-of-the-art deep learning-based models require a large number of data to achieve their best performance. Many datasets fulfilling this criterion have been proposed for multiple domains, such as Amazon products, restaurants, or beers. However, works and datasets in the hotel domain are limited: the largest hotel review dataset is below the million samples. Additionally, the hotel domain suffers from a higher data sparsity than traditional recommendation datasets and therefore, traditional collaborative-filtering approaches cannot be applied to such data. In this paper, we propose HotelRec, a very large-scale hotel recommendation dataset, based on TripAdvisor, containing 50 million reviews. To the best of our knowledge, HotelRec is the largest publicly available dataset in the hotel domain (50M versus 0.9M) and additionally, the largest recommendation dataset in a single domain and with textual reviews (50M versus 22M). We release HotelRec for further research: https://github.com/Diego999/HotelRec.
Enhancing Video Streaming in Vehicular Networks via Resource Slicing
Venue: arXiv cs.NI 2020
Year: 2020

Vehicle-to-everything (V2X) communication is a key enabler that connects vehicles to neighboring vehicles, infrastructure and pedestrians. In the past few years, multimedia services have seen an enormous growth and it is expected to increase as more devices will utilize infotainment services in the future i.e. vehicular devices. Therefore, it is important to focus on user centric measures i.e. quality-of-experience (QoE) such as video quality (resolution) and fluctuations therein. In this paper, a novel joint video quality selection and resource allocation technique is proposed for increasing the QoE of vehicular devices. The proposed approach exploits the queuing dynamics and channel states of vehicular devices, to maximize the QoE while ensuring seamless video playback at the end users with high probability. The network wide QoE maximization problem is decoupled into two subparts. First, a network slicing based clustering algorithm is applied to partition the vehicles into multiple logical networks. Secondly, vehicle scheduling and quality selection is formulated as a stochastic optimization problem which is solved using the Lyapunov drift plus penalty method. Numerical results show that the proposed algorithm ensures high video quality experience compared to the baseline. Simulation results also show that the proposed technique achieves low latency and high-reliability communication.
Deep Learning for Massive MIMO Channel State Acquisition and Feedback
Venue: arXiv cs.IT 2020
Year: 2020

Massive multiple-input multiple-output (MIMO) systems are a main enabler of the excessive throughput requirements in 5G and future generation wireless networks as they can serve many users simultaneously with high spectral and energy efficiency. To achieve this, massive MIMO systems require accurate and timely channel state information (CSI), which is acquired by a training process that involves pilot transmission, CSI estimation and feedback. This training process incurs a training overhead, which scales with the number of antennas, users and subcarriers. Reducing this training overhead in massive MIMO systems has been a major topic of research since the emergence of the concept. Recently, deep learning (DL)-based approaches for massive MIMO training have been proposed and showed significant improvements compared to traditional techniques. This paper provides an overview of how neural networks (NNs) can be used in the training process of massive MIMO systems to improve the performance by reducing the CSI acquisition overhead and to reduce complexity.
Finding All Global Minimum Cuts In Practice
Venue: arXiv cs.DS 2020
Year: 2020

We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.
Fractional Types: Expressive and Safe Space Management for Ancilla Bits
Venue: arXiv cs.PL 2020
Year: 2020

In reversible computing, the management of space is subject to two broad classes of constraints. First, as with general-purpose computation, every allocation must be paired with a matching de-allocation. Second, space can only be safely de-allocated if its contents are restored to their initial value from allocation time. Generally speaking, the state of the art provides limited partial solutions that address the first constraint by imposing a stack discipline and by leaving the second constraint to programmers' assertions. We propose a novel approach based on the idea of fractional types. As a simple intuitive example, allocation of a new boolean value initialized to $\texttt{false}$ also creates a value $1/{\texttt{false}}$ that can be thought of as a garbage collection (GC) process specialized to reclaim, and only reclaim, storage containing the value $\texttt{false}$. This GC process is a first-class entity that can be manipulated, decomposed into smaller processes and combined with other GC processes. We formalize this idea in the context of a reversible language founded on type isomorphisms, prove its fundamental correctness properties, and illustrate its expressiveness using a wide variety of examples. The development is backed by a fully-formalized Agda implementation.
A Case for Data Centre Traffic Management on Software Programmable Ethernet Switches
Venue: arXiv cs.NI 2020
Year: 2020

Virtualisation first and cloud computing later has led to a consolidation of workload in data centres that also comprises latency-sensitive application domains such as High Performance Computing and telecommunication. These types of applications require strict latency guarantees to maintain their Quality of Service. In virtualised environments with their churn, this demands for adaptability and flexibility to satisfy. At the same time, the mere scale of the infrastructures favours commodity (Ethernet) over specialised (Infiniband) hardware. For that purpose, this paper introduces a novel traffic management algorithm that combines Rate-limited Strict Priority and Deficit round-robin for latency-aware and fair scheduling respectively. In addition, we present an implementation of this algorithm on the bmv2 P4 software switch by evaluating it against standard priority-based and best-effort scheduling.
Fully convolutional networks for structural health monitoring through multivariate time series classification
Venue: arXiv cs.LG 2020
Year: 2020

We propose a novel approach to Structural Health Monitoring (SHM), aiming at the automatic identification of damage-sensitive features from data acquired through pervasive sensor systems. Damage detection and localization are formulated as classification problems, and tackled through Fully Convolutional Networks (FCNs). A supervised training of the proposed network architecture is performed on data extracted from numerical simulations of a physics-based model (playing the role of digital twin of the structure to be monitored) accounting for different damage scenarios. By relying on this simplified model of the structure, several load conditions are considered during the training phase of the FCN, whose architecture has been designed to deal with time series of different length. The training of the neural network is done before the monitoring system starts operating, thus enabling a real time damage classification. The numerical performances of the proposed strategy are assessed on a numerical benchmark case consisting of an eight-story shear building subjected to two load types, one of which modeling random vibrations due to low-energy seismicity. Measurement noise has been added to the responses of the structure to mimic the outputs of a real monitoring system. Extremely good classification capacities are shown: among the nine possible alternatives (represented by the healthy state and by a damage at any floor), damage is correctly classified in up to 95% of cases, thus showing the strong potential of the proposed approach in view of the application to real-life cases.
Object-based Metamorphic Testing through Image Structuring
Venue: arXiv cs.LG 2020
Year: 2020

Testing software is often costly due to the need of mass-producing test cases and providing a test oracle for it. This is often referred to as the oracle problem. One method that has been proposed in order to alleviate the oracle problem is metamorphic testing. Metamorphic testing produces new test cases by altering an existing test case, and uses the metamorphic relation between the inputs and the outputs of the System Under Test (SUT) to predict the expected outputs of the produced test cases. Metamorphic testing has often been used for image processing software, where changes are applied to the image's attributes to create new test cases with annotations that are the same as the original image. We refer to this existing method as the image-based metamorphic testing. In this research, we propose an object-based metamorphic testing and a composite metamorphic testing which combines different metamorphic testing approaches to relatively increase test coverage.
An optimal scheduling architecture for accelerating batch algorithms on Neural Network processor architectures
Venue: arXiv cs.PF 2020
Year: 2020

In neural network topologies, algorithms are running on batches of data tensors. The batches of data are typically scheduled onto the computing cores which execute in parallel. For the algorithms running on batches of data, an optimal batch scheduling architecture is very much needed by suitably utilizing hardware resources - thereby resulting in significant reduction training and inference time. In this paper, we propose to accelerate the batch algorithms for neural networks through a scheduling architecture enabling optimal compute power utilization. The proposed optimal scheduling architecture can be built into HW or can be implemented in SW alone which can be leveraged for accelerating batch algorithms. The results demonstrate that the proposed architecture speeds up the batch algorithms compared to the previous solutions. The proposed idea applies to any HPC architecture meant for neural networks.
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
Venue: arXiv cs.LG 2020
Year: 2020

We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online settings of the problems are considered. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret. For both settings, we propose an optimistic variant of the least-squares minimax value iteration algorithm. We show that our algorithm is computationally efficient and provably achieves an $\tilde O(\sqrt{d^3 H^3 T} )$ upper bound on the duality gap and regret, where $d$ is the linear dimension, $H$ the horizon and $T$ the total number of timesteps. Our results do not require additional assumptions on the sampling model. Our setting requires overcoming several new challenges that are absent in Markov decision processes or turn-based Markov games. In particular, to achieve optimism with simultaneous moves, we construct both upper and lower confidence bounds of the value function, and then compute the optimistic policy by solving a general-sum matrix game with these bounds as the payoff matrices. As finding the Nash Equilibrium of a general-sum game is computationally hard, our algorithm instead solves for a Coarse Correlated Equilibrium (CCE), which can be obtained efficiently. To our best knowledge, such a CCE-based scheme for optimism has not appeared in the literature and might be of interest in its own right.
Effective Capacity of NOMA with Finite Blocklength for Low-Latency Communications
Venue: arXiv cs.NI 2020
Year: 2020

In this paper, we investigate the link-layer rate of a two-users non-orthogonal multiple access (NOMA) network in finite blocklength (short packet communications) regime, where the two users are paired from a set of V users. The overall reliability consists of the transmission error probability and the queuing delay violation probability. The performance of the two-users NOMA network in finite blocklength is verified for achieving latency and reliability, using the effective capacity (EC) framework. Specifically, we derive closed-form expressions for the EC of the two-users NOMA network in finite blocklength regime, considering transmissions over Rayleigh fading channels. We also study a multiuser NOMA network and derive the total EC of two-users NOMA subsets, and show that the NOMA set with users having distinct channel conditions achieve maximum total EC. Focusing on a two-users NOMA network, we study the impact of the transmit signal-to-noise ratio, delay exponent, and transmission error probability, on the achievable EC of each user. The analysis shows that when the delay exponent is high, the delay violation probability does not improve below a certain value due to the dominant factor of the transmission error probability. The accuracy of the proposed closed-form expressions for the individual EC of a two-users NOMA is verified using the Monte-Carlo simulations.
On the Relationship between Software Complexity and Security
Venue: arXiv cs.SE 2020
Year: 2020

This work aims at discussing the complexity aspect of software while demonstrating its relationship with security. Complexity is an essential part of software; however, numerous studies indicate that they increase the vulnerability of the software systems and introduce bugs in the program. Many developers face difficulty when trying to understand the complex components of software. Complexity in software increases when objects in the software are used to design a more complex object while creating a hierarchical complexity in the system. However, it is necessary for the developers to strive for minimum complexity, as increased complexity introduces security risks in the software, which can cause severe monetary and reputational damage to a government or a private organization. It even causes bodily harm to human beings with various examples found in previous years where security breaches led to severe consequences. Hence it is vital to maintain low complexity and simple design of structure. Various developers tend to introduce deliberate complexities in the system so that they do not have to write the same program twice; however, it is getting problematic for the software organizations as the demands of security are continually increasing.