OpenRaiser/Intern-Atlas huggingface dataset:
Improving the Robustness of QA Models to Challenge Sets with Variational Question-Answer Pair Generation
Venue: arXiv cs.CL 2021
Year: 2021

Question answering (QA) models for reading comprehension have achieved human-level accuracy on in-distribution test sets. However, they have been demonstrated to lack robustness to challenge sets, whose distribution is different from that of training sets. Existing data augmentation methods mitigate this problem by simply augmenting training sets with synthetic examples sampled from the same distribution as the challenge sets. However, these methods assume that the distribution of a challenge set is known a priori, making them less applicable to unseen challenge sets. In this study, we focus on question-answer pair generation (QAG) to mitigate this problem. While most existing QAG methods aim to improve the quality of synthetic examples, we conjecture that diversity-promoting QAG can mitigate the sparsity of training sets and lead to better robustness. We present a variational QAG model that generates multiple diverse QA pairs from a paragraph. Our experiments show that our method can improve the accuracy of 12 challenge sets, as well as the in-distribution accuracy. Our code and data are available at https://github.com/KazutoshiShinoda/VQAG.
What and Where: Modeling Skeletons from Semantic and Spatial Perspectives for Action Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Skeleton data, which consists of only the 2D/3D coordinates of the human joints, has been widely studied for human action recognition. Existing methods take the semantics as prior knowledge to group human joints and draw correlations according to their spatial locations, which we call the semantic perspective for skeleton modeling. In this paper, in contrast to previous approaches, we propose to model skeletons from a novel spatial perspective, from which the model takes the spatial location as prior knowledge to group human joints and mines the discriminative patterns of local areas in a hierarchical manner. The two perspectives are orthogonal and complementary to each other; and by fusing them in a unified framework, our method achieves a more comprehensive understanding of the skeleton data. Besides, we customized two networks for the two perspectives. From the semantic perspective, we propose a Transformer-like network that is expert in modeling joint correlations, and present three effective techniques to adapt it for skeleton data. From the spatial perspective, we transform the skeleton data into the sparse format for efficient feature extraction and present two types of sparse convolutional networks for sparse skeleton modeling. Extensive experiments are conducted on three challenging datasets for skeleton-based human action/gesture recognition, namely, NTU-60, NTU-120 and SHREC, where our method achieves state-of-the-art performance.
CSMOUTE: Combined Synthetic Oversampling and Undersampling Technique for Imbalanced Data Classification
Venue: arXiv cs.LG 2021
Year: 2021

In this paper we propose a novel data-level algorithm for handling data imbalance in the classification task, Synthetic Majority Undersampling Technique (SMUTE). SMUTE leverages the concept of interpolation of nearby instances, previously introduced in the oversampling setting in SMOTE. Furthermore, we combine both in the Combined Synthetic Oversampling and Undersampling Technique (CSMOUTE), which integrates SMOTE oversampling with SMUTE undersampling. The results of the conducted experimental study demonstrate the usefulness of both the SMUTE and the CSMOUTE algorithms, especially when combined with more complex classifiers, namely MLP and SVM, and when applied on datasets consisting of a large number of outliers. This leads us to a conclusion that the proposed approach shows promise for further extensions accommodating local data characteristics, a direction discussed in more detail in the paper.
Modularis: Modular Relational Analytics over Heterogeneous Distributed Platforms
Venue: arXiv cs.DB 2021
Year: 2021

The enormous quantity of data produced every day together with advances in data analytics has led to a proliferation of data management and analysis systems. Typically, these systems are built around highly specialized monolithic operators optimized for the underlying hardware. While effective in the short term, such an approach makes the operators cumbersome to port and adapt, which is increasingly required due to the speed at which algorithms and hardware evolve. To address this limitation, we present Modularis, an execution layer for data analytics based on sub-operators, i.e.,composable building blocks resembling traditional database operators but at a finer granularity. To demonstrate the advantages of our approach, we use Modularis to build a distributed query processing system supporting relational queries running on an RDMA cluster, a serverless cloud platform, and a smart storage engine. Modularis requires minimal code changes to execute queries across these three diverse hardware platforms, showing that the sub-operator approach reduces the amount and complexity of the code. In fact, changes in the platform affect only sub-operators that depend on the underlying hardware. We show the end-to-end performance of Modularis by comparing it with a framework for SQL processing (Presto), a commercial cluster database (SingleStore), as well as Query-as-a-Service systems (Athena, BigQuery). Modularis outperforms all these systems, proving that the design and architectural advantages of a modular design can be achieved without degrading performance. We also compare Modularis with a hand-optimized implementation of a join for RDMA clusters. We show that Modularis has the advantage of being easily extensible to a wider range of join variants and group by queries, all of which are not supported in the hand-tuned join.
e-SNLI-VE: Corrected Visual-Textual Entailment with Natural Language Explanations
Venue: arXiv cs.CL 2021
Year: 2021

The recently proposed SNLI-VE corpus for recognising visual-textual entailment is a large, real-world dataset for fine-grained multimodal reasoning. However, the automatic way in which SNLI-VE has been assembled (via combining parts of two related datasets) gives rise to a large number of errors in the labels of this corpus. In this paper, we first present a data collection effort to correct the class with the highest error rate in SNLI-VE. Secondly, we re-evaluate an existing model on the corrected corpus, which we call SNLI-VE-2.0, and provide a quantitative comparison with its performance on the non-corrected corpus. Thirdly, we introduce e-SNLI-VE, which appends human-written natural language explanations to SNLI-VE-2.0. Finally, we train models that learn from these explanations at training time, and output such explanations at testing time.
A Robust Method for Image Stitching
Venue: arXiv cs.CV 2021
Year: 2021

We propose a novel method for large-scale image stitching that is robust against repetitive patterns and featureless regions in the imagery. In such cases, state-of-the-art image stitching methods easily produce image alignment artifacts, since they may produce false pairwise image registrations that are in conflict within the global connectivity graph. Our method augments the current methods by collecting all the plausible pairwise image registration candidates, among which globally consistent candidates are chosen. This enables the stitching process to determine the correct pairwise registrations by utilizing all the available information from the whole imagery, such as unambiguous registrations outside the repeating pattern and featureless regions. We formalize the method as a weighted multigraph whose nodes represent the individual image transformations from the composite image, and whose sets of multiple edges between two nodes represent all the plausible transformations between the pixel coordinates of the two images. The edge weights represent the plausibility of the transformations. The image transformations and the edge weights are solved from a non-linear minimization problem with linear constraints, for which a projection method is used. As an example, we apply the method in a large-scale scanning application where the transformations are primarily translations with only slight rotation and scaling component. Despite these simplifications, the state-of-the-art methods do not produce adequate results in such applications, since the image overlap is small, which can be featureless or repetitive, and misalignment artifacts and their concealment are unacceptable.
"Go eat a bat, Chang!": On the Emergence of Sinophobic Behavior on Web Communities in the Face of COVID-19
Venue: arXiv cs.SI 2021
Year: 2021

The outbreak of the COVID-19 pandemic has changed our lives in unprecedented ways. In the face of the projected catastrophic consequences, many countries have enacted social distancing measures in an attempt to limit the spread of the virus. Under these conditions, the Web has become an indispensable medium for information acquisition, communication, and entertainment. At the same time, unfortunately, the Web is being exploited for the dissemination of potentially harmful and disturbing content, such as the spread of conspiracy theories and hateful speech towards specific ethnic groups, in particular towards Chinese people since COVID-19 is believed to have originated from China. In this paper, we make a first attempt to study the emergence of Sinophobic behavior on the Web during the outbreak of the COVID-19 pandemic. We collect two large-scale datasets from Twitter and 4chan's Politically Incorrect board (/pol/) over a time period of approximately five months and analyze them to investigate whether there is a rise or important differences with regard to the dissemination of Sinophobic content. We find that COVID-19 indeed drives the rise of Sinophobia on the Web and that the dissemination of Sinophobic content is a cross-platform phenomenon: it exists on fringe Web communities like \dspol, and to a lesser extent on mainstream ones like Twitter. Also, using word embeddings over time, we characterize the evolution and emergence of new Sinophobic slurs on both Twitter and /pol/. Finally, we find interesting differences in the context in which words related to Chinese people are used on the Web before and after the COVID-19 outbreak: on Twitter we observe a shift towards blaming China for the situation, while on /pol/ we find a shift towards using more (and new) Sinophobic slurs.
ON-OFF Privacy in the Presence of Correlation
Venue: arXiv cs.IT 2021
Year: 2021

We formulate and study the problem of ON-OFF privacy. ON-OFF privacy algorithms enable a user to continuously switch his privacy between ON and OFF. An obvious example is the incognito mode in internet browsers. But beyond internet browsing, ON-OFF privacy can be a desired feature in most online applications. The challenge is that the statistical correlation over time of user's online behavior can lead to leakage of information. We consider the setting in which a user is interested in retrieving the latest message generated by one of N sources. The user's privacy status can change between ON and OFF over time. When privacy is ON the user wants to hide his request. Moreover, since the user's requests depend on personal attributes such as age, gender, and political views, they are typically correlated over time. As a consequence, the user cannot simply ignore privacy when privacy is OFF. We model the correlation between user's requests by an N state Markov chain. The goal is to design query schemes with optimal download rate, that preserve privacy in an ON-OFF privacy setting. In this paper, we present inner and outer bounds on the achievable download rate for N sources. We also devise an efficient algorithm to construct an ON-OFF privacy scheme achieving the inner bound and prove its optimality in the case N = 2 sources. For N > 2, finding tighter outer bounds and efficient constructions of ON-OFF privacy schemes that would achieve them remains an open question.
Massive MIMO Channels with Inter-User Angle Correlation: Open-Access Dataset, Analysis and Measurement-Based Validation
Venue: arXiv cs.IT 2021
Year: 2021

In practical propagation environments, different massive MIMO users can have correlated angles in spatial paths. In this paper, we study the effect of angle correlation on inter-user channel correlation via a combination of measurement and analysis. We show three key results. First, we collect a massive MIMO channel dataset for examining the inter-user channel correlation in a real-world propagation environment; the dataset is now open-access. We observed channel correlation higher than $0.48$ for all close-by users. Additionally, over $30$ % of far-away users, even when they are tens of wavelengths apart, have inter-user channel correlation that is at least twice higher than the correlation in the i.i.d. Rayleigh fading channel. Second, we compute the inter-user channel correlation in closed-form as a function of inter-user angle correlation, the number of base-station antennas, and base-station inter-antenna spacing. Our analysis shows that inter-user angle correlation increases the inter-user channel correlation. Inter-user channel correlation reduces with a larger base-station array aperture, i.e., more antennas and larger inter-antenna spacing. Third, we explain the measurements with numerical experiments to show that inter-user angle correlation can result in significant inter-user channel correlation in practical massive MIMO channels.
Composable Sketches for Functions of Frequencies: Beyond the Worst Case
Venue: arXiv cs.DS 2021
Year: 2021

Recently there has been increased interest in using machine learning techniques to improve classical algorithms. In this paper we study when it is possible to construct compact, composable sketches for weighted sampling and statistics estimation according to functions of data frequencies. Such structures are now central components of large-scale data analytics and machine learning pipelines. However, many common functions, such as thresholds and p-th frequency moments with p > 2, are known to require polynomial-size sketches in the worst case. We explore performance beyond the worst case under two different types of assumptions. The first is having access to noisy advice on item frequencies. This continues the line of work of Hsu et al. (ICLR 2019), who assume predictions are provided by a machine learning model. The second is providing guaranteed performance on a restricted class of input frequency distributions that are better aligned with what is observed in practice. This extends the work on heavy hitters under Zipfian distributions in a seminal paper of Charikar et al. (ICALP 2002). Surprisingly, we show analytically and empirically that "in practice" small polylogarithmic-size sketches provide accuracy for "hard" functions.
SR2CNN: Zero-Shot Learning for Signal Recognition
Venue: arXiv cs.LG 2021
Year: 2021

Signal recognition is one of significant and challenging tasks in the signal processing and communications field. It is often a common situation that there's no training data accessible for some signal classes to perform a recognition task. Hence, as widely-used in image processing field, zero-shot learning (ZSL) is also very important for signal recognition. Unfortunately, ZSL regarding this field has hardly been studied due to inexplicable signal semantics. This paper proposes a ZSL framework, signal recognition and reconstruction convolutional neural networks (SR2CNN), to address relevant problems in this situation. The key idea behind SR2CNN is to learn the representation of signal semantic feature space by introducing a proper combination of cross entropy loss, center loss and autoencoder loss, as well as adopting a suitable distance metric space such that semantic features have greater minimal inter-class distance than maximal intra-class distance. The proposed SR2CNN can discriminate signals even if no training data is available for some signal class. Moreover, SR2CNN can gradually improve itself in the aid of signal detection, because of constantly refined class center vectors in semantic feature space. These merits are all verified by extensive experiments.
Parameterized Verification of Systems with Global Synchronization and Guards
Venue: arXiv cs.FL 2021
Year: 2021

Inspired by distributed applications that use consensus or other agreement protocols for global coordination, we define a new computational model for parameterized systems that is based on a general global synchronization primitive and allows for global transition guards. Our model generalizes many existing models in the literature, including broadcast protocols and guarded protocols. We show that reachability properties are decidable for systems without guards, and give sufficient conditions under which they remain decidable in the presence of guards. Furthermore, we investigate cutoffs for reachability properties and provide sufficient conditions for small cutoffs in a number of cases that are inspired by our target applications.
A Revisit to Ordered Statistics Decoding: Distance Distribution and Decoding Rules
Venue: arXiv cs.IT 2021
Year: 2021

This paper revisits the ordered statistics decoding (OSD). It provides a comprehensive analysis of the OSD algorithm by characterizing the statistical properties, evolution and the distribution of the Hamming distance and weighted Hamming distance from codeword estimates to the received sequence in the reprocessing stages of the OSD algorithm. We prove that the Hamming distance and weighted Hamming distance distributions can be characterized as mixture models capturing the decoding error probability and code weight enumerator. Simulation and numerical results show that our proposed statistical approaches can accurately describe the distance distributions. Based on these distributions and with the aim to reduce the decoding complexity, several techniques, including stopping rules and discarding rules, are proposed, and their decoding error performance and complexity are accordingly analyzed. Simulation results for decoding various eBCH codes demonstrate that the proposed techniques can significantly reduce the decoding complexity with a negligible loss in the decoding error performance.
TIE: Time-Informed Exploration For Robot Motion Planning
Venue: arXiv cs.RO 2021
Year: 2021

Anytime sampling-based methods are an attractive technique for solving kino-dynamic motion planning problems. These algorithms scale well to higher dimensions and can efficiently handle state and control constraints. However, an intelligent exploration strategy is required to accelerate their convergence and avoid redundant computations. Using ideas from reachability analysis, this work defines a "Time-Informed Set", that focuses the search for time-optimal kino-dynamic planning after an initial solution is found. Such a Time-Informed Set (TIS) includes all trajectories that can potentially improve the current best solution and hence exploration outside this set is redundant. Benchmarking experiments show that an exploration strategy based on the TIS can accelerate the convergence of sampling-based kino-dynamic motion planners.
Computing with Continuous Objects: A Uniform Co-inductive Approach
Venue: arXiv cs.LO 2021
Year: 2021

A uniform approach to computing with infinite objects like real numbers, tuples of these, compacts sets, and uniformly continuous maps is presented. In work of Berger it was shown how to extract certified algorithms working with the signed digit representation from constructive proofs. Berger and the present author generalised this approach to complete metric spaces and showed how to deal with compact sets. Here, we unify this work and lay the foundations for doing a similar thing for the much more comprehensive class of compact Hausdorff spaces occurring in applications. The approach is of the same computational power as Weihrauch's Type-Two Theory of Effectivity.
Exponential Upper Bounds for the Runtime of Randomized Search Heuristics
Venue: arXiv cs.NE 2021
Year: 2021

We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also in heuristic search and we prove several such results. We show that any of the algorithms randomized local search, Metropolis algorithm, simulated annealing, and (1+1) evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function under a large set of noise assumptions in a runtime that is at most exponential in the problem dimension~$n$. This drastically extends a previous such result, limited to the (1+1) EA, the LeadingOnes function, and one-bit or bit-wise prior noise with noise probability at most $1/2$, and at the same time simplifies its proof. With the same general argument, among others, we also derive a sub-exponential upper bound for the runtime of the $(1,λ)$ evolutionary algorithm on the OneMax problem when the offspring population size $λ$ is logarithmic, but below the efficiency threshold. To show that our approach can also deal with non-trivial parent population sizes, we prove an exponential upper bound for the runtime of the mutation-based version of the simple genetic algorithm on the OneMax benchmark, matching a known exponential lower bound.
ProFormer: Towards On-Device LSH Projection Based Transformers
Venue: arXiv cs.CL 2021
Year: 2021

At the heart of text based neural models lay word representations, which are powerful but occupy a lot of memory making it challenging to deploy to devices with memory constraints such as mobile phones, watches and IoT. To surmount these challenges, we introduce ProFormer -- a projection based transformer architecture that is faster and lighter making it suitable to deploy to memory constraint devices and preserve user privacy. We use LSH projection layer to dynamically generate word representations on-the-fly without embedding lookup tables leading to significant memory footprint reduction from O(V.d) to O(T), where V is the vocabulary size, d is the embedding dimension size and T is the dimension of the LSH projection representation. We also propose a local projection attention (LPA) layer, which uses self-attention to transform the input sequence of N LSH word projections into a sequence of N/K representations reducing the computations quadratically by O(K^2). We evaluate ProFormer on multiple text classification tasks and observed improvements over prior state-of-the-art on-device approaches for short text classification and comparable performance for long text classification tasks. In comparison with a 2-layer BERT model, ProFormer reduced the embedding memory footprint from 92.16 MB to 1.3 KB and requires 16 times less computation overhead, which is very impressive making it the fastest and smallest on-device model.
Physics-Incorporated Convolutional Recurrent Neural Networks for Source Identification and Forecasting of Dynamical Systems
Venue: arXiv cs.LG 2021
Year: 2021

Spatio-temporal dynamics of physical processes are generally modeled using partial differential equations (PDEs). Though the core dynamics follows some principles of physics, real-world physical processes are often driven by unknown external sources. In such cases, developing a purely analytical model becomes very difficult and data-driven modeling can be of assistance. In this paper, we present a hybrid framework combining physics-based numerical models with deep learning for source identification and forecasting of spatio-temporal dynamical systems with unobservable time-varying external sources. We formulate our model PhICNet as a convolutional recurrent neural network (RNN) which is end-to-end trainable for spatio-temporal evolution prediction of dynamical systems and learns the source behavior as an internal state of the RNN. Experimental results show that the proposed model can forecast the dynamics for a relatively long time and identify the sources as well.