OpenRaiser/Intern-Atlas huggingface dataset:
Learning Adversarial Markov Decision Processes with Delayed Feedback
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning typically assumes that agents observe feedback for their actions immediately, but in many real-world applications (like recommendation systems) feedback is observed in delay. This paper studies online learning in episodic Markov decision processes (MDPs) with unknown transitions, adversarially changing costs and unrestricted delayed feedback. That is, the costs and trajectory of episode $k$ are revealed to the learner only in the end of episode $k + d^k$, where the delays $d^k$ are neither identical nor bounded, and are chosen by an oblivious adversary. We present novel algorithms based on policy optimization that achieve near-optimal high-probability regret of $\sqrt{K + D}$ under full-information feedback, where $K$ is the number of episodes and $D = \sum_{k} d^k$ is the total delay. Under bandit feedback, we prove similar $\sqrt{K + D}$ regret assuming the costs are stochastic, and $(K + D)^{2/3}$ regret in the general case. We are the first to consider regret minimization in the important setting of MDPs with delayed feedback.
Minimum Excess Risk in Bayesian Learning
Venue: arXiv cs.LG 2021
Year: 2021

We analyze the best achievable performance of Bayesian learning under generative models by defining and upper-bounding the minimum excess risk (MER): the gap between the minimum expected loss attainable by learning from data and the minimum expected loss that could be achieved if the model realization were known. The definition of MER provides a principled way to define different notions of uncertainties in Bayesian learning, including the aleatoric uncertainty and the minimum epistemic uncertainty. Two methods for deriving upper bounds for the MER are presented. The first method, generally suitable for Bayesian learning with a parametric generative model, upper-bounds the MER by the conditional mutual information between the model parameters and the quantity being predicted given the observed data. It allows us to quantify the rate at which the MER decays to zero as more data becomes available. Under realizable models, this method also relates the MER to the richness of the generative function class, notably the VC dimension in binary classification. The second method, particularly suitable for Bayesian learning with a parametric predictive model, relates the MER to the minimum estimation error of the model parameters from data. It explicitly shows how the uncertainty in model parameter estimation translates to the MER and to the final prediction uncertainty. We also extend the definition and analysis of MER to the setting with multiple model families and the setting with nonparametric models. Along the discussions we draw some comparisons between the MER in Bayesian learning and the excess risk in frequentist learning.
Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps
Venue: arXiv cs.LG 2021
Year: 2021

Modern neural network architectures use structured linear transformations, such as low-rank matrices, sparse matrices, permutations, and the Fourier transform, to improve inference speed and reduce memory usage compared to general linear maps. However, choosing which of the myriad structured transformations to use (and its associated parameterization) is a laborious task that requires trading off speed, space, and accuracy. We consider a different approach: we introduce a family of matrices called kaleidoscope matrices (K-matrices) that provably capture any structured matrix with near-optimal space (parameter) and time (arithmetic operation) complexity. We empirically validate that K-matrices can be automatically learned within end-to-end pipelines to replace hand-crafted procedures, in order to improve model quality. For example, replacing channel shuffles in ShuffleNet improves classification accuracy on ImageNet by up to 5%. K-matrices can also simplify hand-engineered pipelines -- we replace filter bank feature computation in speech data preprocessing with a learnable kaleidoscope layer, resulting in only 0.4% loss in accuracy on the TIMIT speech recognition task. In addition, K-matrices can capture latent structure in models: for a challenging permuted image classification task, a K-matrix based representation of permutations is able to learn the right latent structure and improves accuracy of a downstream convolutional model by over 9%. We provide a practically efficient implementation of our approach, and use K-matrices in a Transformer network to attain 36% faster end-to-end inference speed on a language translation task.
Reservoir Transformers
Venue: arXiv cs.CL 2021
Year: 2021

We demonstrate that transformers obtain impressive performance even when some of the layers are randomly initialized and never updated. Inspired by old and well-established ideas in machine learning, we explore a variety of non-linear "reservoir" layers interspersed with regular transformer layers, and show improvements in wall-clock compute time until convergence, as well as overall performance, on various machine translation and (masked) language modelling tasks.
Improving BERT with Syntax-aware Local Attention
Venue: arXiv cs.CL 2021
Year: 2021

Pre-trained Transformer-based neural language models, such as BERT, have achieved remarkable results on varieties of NLP tasks. Recent works have shown that attention-based models can benefit from more focused attention over local regions. Most of them restrict the attention scope within a linear span, or confine to certain tasks such as machine translation and question answering. In this paper, we propose a syntax-aware local attention, where the attention scopes are restrained based on the distances in the syntactic structure. The proposed syntax-aware local attention can be integrated with pretrained language models, such as BERT, to render the model to focus on syntactically relevant words. We conduct experiments on various single-sentence benchmarks, including sentence classification and sequence labeling tasks. Experimental results show consistent gains over BERT on all benchmark datasets. The extensive studies verify that our model achieves better performance owing to more focused attention over syntactically relevant words.
SemGloVe: Semantic Co-occurrences for GloVe from BERT
Venue: arXiv cs.CL 2021
Year: 2021

GloVe learns word embeddings by leveraging statistical information from word co-occurrence matrices. However, word pairs in the matrices are extracted from a predefined local context window, which might lead to limited word pairs and potentially semantic irrelevant word pairs. In this paper, we propose SemGloVe, which distills semantic co-occurrences from BERT into static GloVe word embeddings. Particularly, we propose two models to extract co-occurrence statistics based on either the masked language model or the multi-head attention weights of BERT. Our methods can extract word pairs without limiting by the local window assumption and can define the co-occurrence weights by directly considering the semantic distance between word pairs. Experiments on several word similarity datasets and four external tasks show that SemGloVe can outperform GloVe.
Design, Characterization, and Control of a Size Adaptable In-pipe Robot for Water Distribution Systems
Venue: arXiv cs.RO 2021
Year: 2021

Leak detection and water quality monitoring are requirements and challenging tasks in Water Distribution Systems (WDS). In-line robots are designed for this aim. In our previous work, we designed an in-pipe robot [1]. In this research, we present the design of the central processor, characterize and control the robot based on the condition of operation in a highly pressurized environment of pipelines with the presence of high-speed flow. To this aim, an extreme operation condition is simulated with computational fluid dynamics (CFD) and the spring mechanism is characterized to ensure sufficient stabilizing force during operation based on the extreme operating condition. Also, an end-to-end method is suggested for power considerations for our robot that calculates minimum battery capacity and operation duration in the extreme operating condition. Finally, we design a novel LQR-PID based controller based on the system auxiliary matrices that retain the robot stability inside the pipeline against disturbances and uncertainties during operation. The ADAMS-MATLAB co-simulation of the robot-controller shows the rotational velocity with -4 degree/sec and +3 degree/sec margin around x, y, and z axes while the system tracks different desired velocities in pipelines (i.e. 0.12m/s, 0.17m/s, and 0.35m/s). Also, experimental results for four iterations in a 14-inch diameter PVC pipe show that the controller brings initial values of stabilizing states to zero and oscillate around it with a margin of 2 degrees and the system tracks desired velocities of 0.1m/s, 0.2m/s, 0.3m/s, and 0.35m/s in which makes the robot dexterous in uncertain and highly disturbed the environment of pipelines during operation.
Blade Envelopes Part II: Multiple Objectives and Inverse Design
Venue: arXiv cs.CE 2021
Year: 2021

Blade envelopes offer a set of data-driven tolerance guidelines for manufactured components based on aerodynamic analysis. In Part I of this two-part paper, a workflow for the formulation of blade envelopes is described and demonstrated. In Part II, this workflow is extended to accommodate multiple objectives. This allows engineers to prescribe manufacturing guidelines that take into account multiple performance criteria. The quality of a manufactured blade can be correlated with features derived from the distribution of primal flow quantities over the surface. We show that these distributions can be accounted for in the blade envelope using vector-valued models derived from discrete surface flow measurements. Our methods result in a set of variables that allows flexible and independent control over multiple flow characteristics and performance metrics, similar in spirit to inverse design methods. The augmentations to the blade envelope workflow presented in this paper are demonstrated on the LS89 turbine blade, focusing on the control of loss, mass flow and the isentropic Mach number distribution. Finally, we demonstrate how blade envelopes can be used to visualize invariant designs by producing a 3D render of the envelope using 3D modelling software.
Data-driven topology optimization of spinodoid metamaterials with seamlessly tunable anisotropy
Venue: arXiv cs.CE 2021
Year: 2021

We present a two-scale topology optimization framework for the design of macroscopic bodies with an optimized elastic response, which is achieved by means of a spatially-variant cellular architecture on the microscale. The chosen spinodoid topology for the cellular network on the microscale (which is inspired by natural microstructures forming during spinodal decomposition) admits a seamless spatial grading as well as tunable elastic anisotropy, and it is parametrized by a small set of design parameters associated with the underlying Gaussian random field. The macroscale boundary value problem is discretized by finite elements, which in addition to the displacement field continuously interpolate the microscale design parameters. By assuming a separation of scales, the local constitutive behavior on the macroscale is identified as the homogenized elastic response of the microstructure based on the local design parameters. As a departure from classical FE$^2$-type approaches, we replace the costly microscale homogenization by a data-driven surrogate model, using deep neural networks, which accurately and efficiently maps design parameters onto the effective elasticity tensor. The model is trained on homogenized stiffness data obtained from numerical homogenization by finite elements. As an added benefit, the machine learning setup admits automatic differentiation, so that sensitivities (required for the optimization problem) can be computed exactly and without the need for numerical derivatives - a strategy that holds promise far beyond the elastic stiffness. Therefore, this framework presents a new opportunity for multiscale topology optimization based on data-driven surrogate models.
Am I Rare? An Intelligent Summarization Approach for Identifying Hidden Anomalies
Venue: arXiv cs.LG 2021
Year: 2021

Monitoring network traffic data to detect any hidden patterns of anomalies is a challenging and time-consuming task that requires high computing resources. To this end, an appropriate summarization technique is of great importance, where it can be a substitute for the original data. However, the summarized data is under the threat of removing anomalies. Therefore, it is vital to create a summary that can reflect the same pattern as the original data. Therefore, in this paper, we propose an INtelligent Summarization approach for IDENTifying hidden anomalies, called INSIDENT. The proposed approach guarantees to keep the original data distribution in summarized data. Our approach is a clustering-based algorithm that dynamically maps original feature space to a new feature space by locally weighting features in each cluster. Therefore, in new feature space, similar samples are closer, and consequently, outliers are more detectable. Besides, selecting representatives based on cluster size keeps the same distribution as the original data in summarized data. INSIDENT can be used both as the preprocess approach before performing anomaly detection algorithms and anomaly detection algorithm. The experimental results on benchmark datasets prove a summary of the data can be a substitute for original data in the anomaly detection task.
A CNN Approach to Simultaneously Count Plants and Detect Plantation-Rows from UAV Imagery
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we propose a novel deep learning method based on a Convolutional Neural Network (CNN) that simultaneously detects and geolocates plantation-rows while counting its plants considering highly-dense plantation configurations. The experimental setup was evaluated in a cornfield with different growth stages and in a Citrus orchard. Both datasets characterize different plant density scenarios, locations, types of crops, sensors, and dates. A two-branch architecture was implemented in our CNN method, where the information obtained within the plantation-row is updated into the plant detection branch and retro-feed to the row branch; which are then refined by a Multi-Stage Refinement method. In the corn plantation datasets (with both growth phases, young and mature), our approach returned a mean absolute error (MAE) of 6.224 plants per image patch, a mean relative error (MRE) of 0.1038, precision and recall values of 0.856, and 0.905, respectively, and an F-measure equal to 0.876. These results were superior to the results from other deep networks (HRNet, Faster R-CNN, and RetinaNet) evaluated with the same task and dataset. For the plantation-row detection, our approach returned precision, recall, and F-measure scores of 0.913, 0.941, and 0.925, respectively. To test the robustness of our model with a different type of agriculture, we performed the same task in the citrus orchard dataset. It returned an MAE equal to 1.409 citrus-trees per patch, MRE of 0.0615, precision of 0.922, recall of 0.911, and F-measure of 0.965. For citrus plantation-row detection, our approach resulted in precision, recall, and F-measure scores equal to 0.965, 0.970, and 0.964, respectively. The proposed method achieved state-of-the-art performance for counting and geolocating plants and plant-rows in UAV images from different types of crops.
MiniLMv2: Multi-Head Self-Attention Relation Distillation for Compressing Pretrained Transformers
Venue: arXiv cs.CL 2021
Year: 2021

We generalize deep self-attention distillation in MiniLM (Wang et al., 2020) by only using self-attention relation distillation for task-agnostic compression of pretrained Transformers. In particular, we define multi-head self-attention relations as scaled dot-product between the pairs of query, key, and value vectors within each self-attention module. Then we employ the above relational knowledge to train the student model. Besides its simplicity and unified principle, more favorably, there is no restriction in terms of the number of student's attention heads, while most previous work has to guarantee the same head number between teacher and student. Moreover, the fine-grained self-attention relations tend to fully exploit the interaction knowledge learned by Transformer. In addition, we thoroughly examine the layer selection strategy for teacher models, rather than just relying on the last layer as in MiniLM. We conduct extensive experiments on compressing both monolingual and multilingual pretrained models. Experimental results demonstrate that our models distilled from base-size and large-size teachers (BERT, RoBERTa and XLM-R) outperform the state-of-the-art.
Timely Communication in Federated Learning
Venue: arXiv cs.IT 2021
Year: 2021

We consider a federated learning framework in which a parameter server (PS) trains a global model by using $n$ clients without actually storing the client data centrally at a cloud server. Focusing on a setting where the client datasets are fast changing and highly temporal in nature, we investigate the timeliness of model updates and propose a novel timely communication scheme. Under the proposed scheme, at each iteration, the PS waits for $m$ available clients and sends them the current model. Then, the PS uses the local updates of the earliest $k$ out of $m$ clients to update the global model at each iteration. We find the average age of information experienced by each client and numerically characterize the age-optimal $m$ and $k$ values for a given $n$. Our results indicate that, in addition to ensuring timeliness, the proposed communication scheme results in significantly smaller average iteration times compared to random client selection without hurting the convergence of the global learning task.
Automatic-differentiated Physics-Informed Echo State Network (API-ESN)
Venue: arXiv cs.LG 2021
Year: 2021

We propose the Automatic-differentiated Physics-Informed Echo State Network (API-ESN). The network is constrained by the physical equations through the reservoir's exact time-derivative, which is computed by automatic differentiation. As compared to the original Physics-Informed Echo State Network, the accuracy of the time-derivative is increased by up to seven orders of magnitude. This increased accuracy is key in chaotic dynamical systems, where errors grows exponentially in time. The network is showcased in the reconstruction of unmeasured (hidden) states of a chaotic system. The API-ESN eliminates a source of error, which is present in existing physics-informed echo state networks, in the computation of the time-derivative. This opens up new possibilities for an accurate reconstruction of chaotic dynamical states.
UnNatural Language Inference
Venue: arXiv cs.CL 2021
Year: 2021

Recent investigations into the inner-workings of state-of-the-art large-scale pre-trained Transformer-based Natural Language Understanding (NLU) models indicate that they appear to know humanlike syntax, at least to some extent. We provide novel evidence that complicates this claim: we find that state-of-the-art Natural Language Inference (NLI) models assign the same labels to permuted examples as they do to the original, i.e. they are largely invariant to random word-order permutations. This behavior notably differs from that of humans; we struggle with ungrammatical sentences. To measure the severity of this issue, we propose a suite of metrics and investigate which properties of particular permutations lead models to be word-order invariant. In the MNLI dataset, for example, we find almost all (98.7%) examples contain at least one permutation which elicits the gold label. Models are sometimes even able to assign gold labels to permutations that they originally failed to predict correctly. We provide a comprehensive empirical evaluation of this phenomenon, and further show that this issue exists for both Transformers and pre-Transformer RNN / ConvNet based encoders, as well as across multiple languages (English and Mandarin Chinese). Our code and data are available at https://github.com/facebookresearch/unlu.
EarlyBERT: Efficient BERT Training via Early-bird Lottery Tickets
Venue: arXiv cs.CL 2021
Year: 2021

Heavily overparameterized language models such as BERT, XLNet and T5 have achieved impressive success in many NLP tasks. However, their high model complexity requires enormous computation resources and extremely long training time for both pre-training and fine-tuning. Many works have studied model compression on large NLP models, but only focusing on reducing inference time while still requiring an expensive training process. Other works use extremely large batch sizes to shorten the pre-training time, at the expense of higher computational resource demands. In this paper, inspired by the Early-Bird Lottery Tickets recently studied for computer vision tasks, we propose EarlyBERT, a general computationally-efficient training algorithm applicable to both pre-training and fine-tuning of large-scale language models. By slimming the self-attention and fully-connected sub-layers inside a transformer, we are the first to identify structured winning tickets in the early stage of BERT training. We apply those tickets towards efficient BERT training, and conduct comprehensive pre-training and fine-tuning experiments on GLUE and SQuAD downstream tasks. Our results show that EarlyBERT achieves comparable performance to standard BERT, with 35~45% less training time. Code is available at https://github.com/VITA-Group/EarlyBERT.
Towards Threshold Key Exchange Protocols
Venue: arXiv cs.CR 2021
Year: 2021

Threshold schemes exist for many cryptographic primitives like signatures, key derivation functions, and ciphers. At the same time, practical key exchange protocols based on Diffie-Hellman (DH) or ECDSA primitives are not designed or implemented in a threshold setting. In this paper, we implement popular key exchange protocols in a threshold manner and show that this approach can be used in practice. First, we introduce two basic threshold DH key agreement schemes that provide enhanced security features in comparison with the classic DH primitive: dealerless distributed key generation, threshold shared key computation, and private key shares refreshing. We implemented the proposed DH schemes within WireGuard protocol to demonstrate its effectiveness, efficiency, and usability in practice. The open question is the security of the proposed schemes and their instantiation from the elliptic curves used in key agreement protocols: NIST curves, Russian GOST curves, and Curve25519. Second, we propose an idea of implementing TLS in a threshold setting that can be used instead of Keyless SSL/TLS technology, and provide the measurements of TLS key exchanges based on threshold ECDSA. Even if we don't provide any formal definitions, security analysis, and mathematical proofs, we believe that the ideas and mechanisms suggested in this paper can be interesting and useful. The main intention of the paper is to start discussions and raise awareness of the challenges and problems arising when moving to threshold key exchange protocols.