OpenRaiser/Intern-Atlas huggingface dataset:
Leader Election And Local Identifiers For 3D Programmable Matter
Venue: arXiv cs.DM 2020
Year: 2020

In this paper, we present two deterministic leader election algorithms for programmable matter on the face-centered cubic grid. The face-centered cubic grid is a 3-dimensional 12-regular infinite grid that represents an optimal way to pack spheres (i.e., spherical particles or modules in the context of the programmable matter) in the 3-dimensional space. While the first leader election algorithm requires a strong hypothesis about the initial configuration of the particles and no hypothesis on the system configurations that the particles are forming, the second one requires fewer hypothesis about the initial configuration of the particles but does not work for all possible particles' arrangement. We also describe a way to compute and assign-local identifiers to the particles in this grid with a memory space not dependent on the number of particles. A-local identifier is a variable assigned to each particle in such a way that particles at distance at most each have a different identifier.
Meta-learning the Learning Trends Shared Across Tasks
Venue: arXiv cs.LG 2020
Year: 2020

Meta-learning stands for 'learning to learn' such that generalization to new tasks is achieved. Among these methods, Gradient-based meta-learning algorithms are a specific sub-class that excel at quick adaptation to new tasks with limited data. This demonstrates their ability to acquire transferable knowledge, a capability that is central to human learning. However, the existing meta-learning approaches only depend on the current task information during the adaptation, and do not share the meta-knowledge of how a similar task has been adapted before. To address this gap, we propose a 'Path-aware' model-agnostic meta-learning approach. Specifically, our approach not only learns a good initialization for adaptation, it also learns an optimal way to adapt these parameters to a set of task-specific parameters, with learnable update directions, learning rates and, most importantly, the way updates evolve over different time-steps. Compared to the existing meta-learning methods, our approach offers: (a) The ability to learn gradient-preconditioning at different time-steps of the inner-loop, thereby modeling the dynamic learning behavior shared across tasks, and (b) The capability of aggregating the learning context through the provision of direct gradient-skip connections from the old time-steps, thus avoiding overfitting and improving generalization. In essence, our approach not only learns a transferable initialization, but also models the optimal update directions, learning rates, and task-specific learning trends. Specifically, in terms of learning trends, our approach determines the way update directions shape up as the task-specific learning progresses and how the previous update history helps in the current update. Our approach is simple to implement and demonstrates faster convergence. We report significant performance improvements on a number of FSL datasets.
A Two-stage Unsupervised Approach for Low light Image Enhancement
Venue: arXiv cs.CV 2020
Year: 2020

As vision based perception methods are usually built on the normal light assumption, there will be a serious safety issue when deploying them into low light environments. Recently, deep learning based methods have been proposed to enhance low light images by penalizing the pixel-wise loss of low light and normal light images. However, most of them suffer from the following problems: 1) the need of pairs of low light and normal light images for training, 2) the poor performance for dark images, 3) the amplification of noise. To alleviate these problems, in this paper, we propose a two-stage unsupervised method that decomposes the low light image enhancement into a pre-enhancement and a post-refinement problem. In the first stage, we pre-enhance a low light image with a conventional Retinex based method. In the second stage, we use a refinement network learned with adversarial training for further improvement of the image quality. The experimental results show that our method outperforms previous methods on four benchmark datasets. In addition, we show that our method can significantly improve feature points matching and simultaneous localization and mapping in low light conditions.
Bayesian Inference for Optimal Transport with Stochastic Cost
Venue: arXiv cs.LG 2020
Year: 2020

In machine learning and computer vision, optimal transport has had significant success in learning generative models and defining metric distances between structured and stochastic data objects, that can be cast as probability measures. The key element of optimal transport is the so called lifting of an \emph{exact} cost (distance) function, defined on the sample space, to a cost (distance) between probability measures over the sample space. However, in many real life applications the cost is \emph{stochastic}: e.g., the unpredictable traffic flow affects the cost of transportation between a factory and an outlet. To take this stochasticity into account, we introduce a Bayesian framework for inferring the optimal transport plan distribution induced by the stochastic cost, allowing for a principled way to include prior information and to model the induced stochasticity on the transport plans. Additionally, we tailor an HMC method to sample from the resulting transport plan posterior distribution.
The Impact of DNS Insecurity on Time
Venue: arXiv cs.CR 2020
Year: 2020

We demonstrate the first practical off-path time shifting attacks against NTP as well as against Man-in-the-Middle (MitM) secure Chronos-enhanced NTP. Our attacks exploit the insecurity of DNS allowing us to redirect the NTP clients to attacker controlled servers. We perform large scale measurements of the attack surface in NTP clients and demonstrate the threats to NTP due to vulnerable DNS.
Learning Latent Space Energy-Based Prior Model for Molecule Generation
Venue: arXiv cs.LG 2020
Year: 2020

Deep generative models have recently been applied to molecule design. If the molecules are encoded in linear SMILES strings, modeling becomes convenient. However, models relying on string representations tend to generate invalid samples and duplicates. Prior work addressed these issues by building models on chemically-valid fragments or explicitly enforcing chemical rules in the generation process. We argue that an expressive model is sufficient to implicitly and automatically learn the complicated chemical rules from the data, even if molecules are encoded in simple character-level SMILES strings. We propose to learn latent space energy-based prior model with SMILES representation for molecule modeling. Our experiments show that our method is able to generate molecules with validity and uniqueness competitive with state-of-the-art models. Interestingly, generated molecules have structural and chemical features whose distributions almost perfectly match those of the real molecules.
Unsupervised Pretraining for Neural Machine Translation Using Elastic Weight Consolidation
Venue: arXiv cs.CL 2020
Year: 2020

This work presents our ongoing research of unsupervised pretraining in neural machine translation (NMT). In our method, we initialize the weights of the encoder and decoder with two language models that are trained with monolingual data and then fine-tune the model on parallel data using Elastic Weight Consolidation (EWC) to avoid forgetting of the original language modeling tasks. We compare the regularization by EWC with the previous work that focuses on regularization by language modeling objectives. The positive result is that using EWC with the decoder achieves BLEU scores similar to the previous work. However, the model converges 2-3 times faster and does not require the original unlabeled training data during the fine-tuning stage. In contrast, the regularization using EWC is less effective if the original and new tasks are not closely related. We show that initializing the bidirectional NMT encoder with a left-to-right language model and forcing the model to remember the original left-to-right language modeling task limits the learning capacity of the encoder for the whole bidirectional context.
The Projective General Linear Group $\mathrm{PGL}_2(\mathrm{GF}(2^m))$ and Linear Codes of Length $2^m+1$
Venue: arXiv cs.IT 2020
Year: 2020

The projective general linear group $\mathrm{PGL}_2(\mathrm{GF}(2^m))$ acts as a $3$-transitive permutation group on the set of points of the projective line. The first objective of this paper is to prove that all linear codes over $\mathrm{GF}(2^h)$ that are invariant under $\mathrm{PGL}_2(\mathrm{GF}(2^m))$ are trivial codes: the repetition code, the whole space $\mathrm{GF}(2^h)^{2^m+1}$, and their dual codes. As an application of this result, the $2$-ranks of the (0,1)-incidence matrices of all $3$-$(q+1,k,λ)$ designs that are invariant under $\mathrm{PGL}_2(\mathrm{GF}(2^m))$ are determined. The second objective is to present two infinite families of cyclic codes over $\mathrm{GF}(2^m)$ such that the set of the supports of all codewords of any fixed nonzero weight is invariant under $\mathrm{PGL}_2(\mathrm{GF}(2^m))$, therefore, the codewords of any nonzero weight support a 3-design. A code from the first family has parameters $[q+1,q-3,4]_q$, where $q=2^m$, and $m\ge 4$ is even. The exact number of the codewords of minimum weight is determined, and the codewords of minimum weight support a 3-$(q+1,4,2)$ design. A code from the second family has parameters $[q+1,4,q-4]_q$, $q=2^m$, $m\ge 4$ even, and the minimum weight codewords support a 3-$(q +1,q-4,(q-4)(q-5)(q-6)/60)$ design, whose complementary 3-$(q +1, 5, 1)$ design is isomorphic to the Witt spherical geometry with these parameters. A lower bound on the dimension of a linear code over $\mathrm{GF}(q)$ that can support a 3-$(q +1,q-4,(q-4)(q-5)(q-6)/60)$ design is proved, and it is shown that the designs supported by the codewords of minimum weight in the codes from the second family of codes meet this bound.
Performance Assessment of OpenMP Compilers Targeting NVIDIA V100 GPUs
Venue: arXiv cs.PF 2020
Year: 2020

Heterogeneous systems are becoming increasingly prevalent. In order to exploit the rich compute resources of such systems, robust programming models are needed for application developers to seamlessly migrate legacy code from today's systems to tomorrow's. Over the past decade and more, directives have been established as one of the promising paths to tackle programmatic challenges on emerging systems. This work focuses on applying and demonstrating OpenMP offloading directives on five proxy applications. We observe that the performance varies widely from one compiler to the other; a crucial aspect of our work is reporting best practices to application developers who use OpenMP offloading compilers. While some issues can be worked around by the developer, there are other issues that must be reported to the compiler vendors. By restructuring OpenMP offloading directives, we gain an 18x speedup for the su3 proxy application on NERSC's Cori system when using the Clang compiler, and a 15.7x speedup by switching max reductions to add reductions in the laplace mini-app when using the Cray-llvm compiler on Cori.
Closed-Loop Neural Interfaces with Embedded Machine Learning
Venue: arXiv cs.AR 2020
Year: 2020

Neural interfaces capable of multi-site electrical recording, on-site signal classification, and closed-loop therapy are critical for the diagnosis and treatment of neurological disorders. However, deploying machine learning algorithms on low-power neural devices is challenging, given the tight constraints on computational and memory resources for such devices. In this paper, we review the recent developments in embedding machine learning in neural interfaces, with a focus on design trade-offs and hardware efficiency. We also present our optimized tree-based model for low-power and memory-efficient classification of neural signal in brain implants. Using energy-aware learning and model compression, we show that the proposed oblique trees can outperform conventional machine learning models in applications such as seizure or tremor detection and motor decoding.
Review and Comparison of Commonly Used Activation Functions for Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

The primary neural networks decision-making units are activation functions. Moreover, they evaluate the output of networks neural node; thus, they are essential for the performance of the whole network. Hence, it is critical to choose the most appropriate activation function in neural networks calculation. Acharya et al. (2018) suggest that numerous recipes have been formulated over the years, though some of them are considered deprecated these days since they are unable to operate properly under some conditions. These functions have a variety of characteristics, which are deemed essential to successfully learning. Their monotonicity, individual derivatives, and finite of their range are some of these characteristics (Bach 2017). This research paper will evaluate the commonly used additive functions, such as swish, ReLU, Sigmoid, and so forth. This will be followed by their properties, own cons and pros, and particular formula application recommendations.
Double-Linear Thompson Sampling for Context-Attentive Bandits
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we analyze and extend an online learning framework known as Context-Attentive Bandit, motivated by various practical applications, from medical diagnosis to dialog systems, where due to observation costs only a small subset of a potentially large number of context variables can be observed at each iteration;however, the agent has a freedom to choose which variables to observe. We derive a novel algorithm, called Context-Attentive Thompson Sampling (CATS), which builds upon the Linear Thompson Sampling approach, adapting it to Context-Attentive Bandit setting. We provide a theoretical regret analysis and an extensive empirical evaluation demonstrating advantages of the proposed approach over several baseline methods on a variety of real-life datasets
Multi-Armed Bandits with Dependent Arms
Venue: arXiv cs.LG 2020
Year: 2020

We study a variant of the classical multi-armed bandit problem (MABP) which we call as Multi-Armed Bandits with dependent arms. More specifically, multiple arms are grouped together to form a cluster, and the reward distributions of arms belonging to the same cluster are known functions of an unknown parameter that is a characteristic of the cluster. Thus, pulling an arm $i$ not only reveals information about its own reward distribution, but also about all those arms that share the same cluster with arm $i$. This "correlation" amongst the arms complicates the exploration-exploitation trade-off that is encountered in the MABP because the observation dependencies allow us to test simultaneously multiple hypotheses regarding the optimality of an arm. We develop learning algorithms based on the UCB principle which utilize these additional side observations appropriately while performing exploration-exploitation trade-off. We show that the regret of our algorithms grows as $O(K\log T)$, where $K$ is the number of clusters. In contrast, for an algorithm such as the vanilla UCB that is optimal for the classical MABP and does not utilize these dependencies, the regret scales as $O(M\log T)$ where $M$ is the number of arms.
Heads-up! Unsupervised Constituency Parsing via Self-Attention Heads
Venue: arXiv cs.CL 2020
Year: 2020

Transformer-based pre-trained language models (PLMs) have dramatically improved the state of the art in NLP across many tasks. This has led to substantial interest in analyzing the syntactic knowledge PLMs learn. Previous approaches to this question have been limited, mostly using test suites or probes. Here, we propose a novel fully unsupervised parsing approach that extracts constituency trees from PLM attention heads. We rank transformer attention heads based on their inherent properties, and create an ensemble of high-ranking heads to produce the final tree. Our method is adaptable to low-resource languages, as it does not rely on development sets, which can be expensive to annotate. Our experiments show that the proposed method often outperform existing approaches if there is no development set present. Our unsupervised parser can also be used as a tool to analyze the grammars PLMs learn implicitly. For this, we use the parse trees induced by our method to train a neural PCFG and compare it to a grammar derived from a human-annotated treebank.
GANs for learning from very high class conditional noisy labels
Venue: arXiv cs.LG 2020
Year: 2020

We use Generative Adversarial Networks (GANs) to design a class conditional label noise (CCN) robust scheme for binary classification. It first generates a set of correctly labelled data points from noisy labelled data and 0.1% or 1% clean labels such that the generated and true (clean) labelled data distributions are close; generated labelled data is used to learn a good classifier. The mode collapse problem while generating correct feature-label pairs and the problem of skewed feature-label dimension ratio ($\sim$ 784:1) are avoided by using Wasserstein GAN and a simple data representation change. Another WGAN with information-theoretic flavour on top of the new representation is also proposed. The major advantage of both schemes is their significant improvement over the existing ones in presence of very high CCN rates, without either estimating or cross-validating over the noise rates. We proved that KL divergence between clean and noisy distribution increases w.r.t. noise rates in symmetric label noise model; can be extended to high CCN rates. This implies that our schemes perform well due to the adversarial nature of GANs. Further, use of generative approach (learning clean joint distribution) while handling noise enables our schemes to perform better than discriminative approaches like GLC, LDMI and GCE; even when the classes are highly imbalanced. Using Friedman F test and Nemenyi posthoc test, we showed that on high dimensional binary class synthetic, MNIST and Fashion MNIST datasets, our schemes outperform the existing methods and demonstrate consistent performance across noise rates.
Cooperative Multi-Sensor Detection under Variable-Length Coding
Venue: arXiv cs.IT 2020
Year: 2020

We investigate the testing-against-independence problem \mw{over a cooperative MAC} with two sensors and a single detector under an average rate constraint on the sensors-detector links. For this setup, we design a variable-length coding scheme that maximizes the achievable type-II error exponent when the type-I error probability is limited to $ε$. Similarly to the single-link result, we show here that the optimal error exponent depends on $ε$ and that variable-length coding allows to \mw{increase the rates over the optimal} fixed-length coding \mw{scheme} by the factor $(1-ε)^{-1}$.
Multi-Stage Fusion for One-Click Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Segmenting objects of interest in an image is an essential building block of applications such as photo-editing and image analysis. Under interactive settings, one should achieve good segmentations while minimizing user input. Current deep learning-based interactive segmentation approaches use early fusion and incorporate user cues at the image input layer. Since segmentation CNNs have many layers, early fusion may weaken the influence of user interactions on the final prediction results. As such, we propose a new multi-stage guidance framework for interactive segmentation. By incorporating user cues at different stages of the network, we allow user interactions to impact the final segmentation output in a more direct way. Our proposed framework has a negligible increase in parameter count compared to early-fusion frameworks. We perform extensive experimentation on the standard interactive instance segmentation and one-click segmentation benchmarks and report state-of-the-art performance.
Subtitles to Segmentation: Improving Low-Resource Speech-to-Text Translation Pipelines
Venue: arXiv cs.CL 2020
Year: 2020

In this work, we focus on improving ASR output segmentation in the context of low-resource language speech-to-text translation. ASR output segmentation is crucial, as ASR systems segment the input audio using purely acoustic information and are not guaranteed to output sentence-like segments. Since most MT systems expect sentences as input, feeding in longer unsegmented passages can lead to sub-optimal performance. We explore the feasibility of using datasets of subtitles from TV shows and movies to train better ASR segmentation models. We further incorporate part-of-speech (POS) tag and dependency label information (derived from the unsegmented ASR outputs) into our segmentation model. We show that this noisy syntactic information can improve model accuracy. We evaluate our models intrinsically on segmentation quality and extrinsically on downstream MT performance, as well as downstream tasks including cross-lingual information retrieval (CLIR) tasks and human relevance assessments. Our model shows improved performance on downstream tasks for Lithuanian and Bulgarian.
Deriving Commonsense Inference Tasks from Interactive Fictions
Venue: arXiv cs.AI 2020
Year: 2020

Commonsense reasoning simulates the human ability to make presumptions about our physical world, and it is an indispensable cornerstone in building general AI systems. We propose a new commonsense reasoning dataset based on human's interactive fiction game playings as human players demonstrate plentiful and diverse commonsense reasoning. The new dataset mitigates several limitations of the prior art. Experiments show that our task is solvable to human experts with sufficient commonsense knowledge but poses challenges to existing machine reading models, with a big performance gap of more than 30%.
Connections between Relational Event Model and Inverse Reinforcement Learning for Characterizing Group Interaction Sequences
Venue: arXiv cs.LG 2020
Year: 2020

In this paper we explore previously unidentified connections between relational event model (REM) from the field of network science and inverse reinforcement learning (IRL) from the field of machine learning with respect to their ability to characterize sequences of directed social interaction events in group settings. REM is a conventional approach to tackle such a problem whereas the application of IRL is a largely unbeaten path. We begin by examining the mathematical components of both REM and IRL and find straightforward analogies between the two methods as well as unique characteristics of the IRL approach. We demonstrate the special utility of IRL in characterizing group social interactions with an empirical experiment, in which we use IRL to infer individual behavioral preferences based on a sequence of directed communication events from a group of virtual-reality game players interacting and cooperating to accomplish a shared goal. Our comparison and experiment introduce fresh perspectives for social behavior analytics and help inspire new research opportunities at the nexus of social network analysis and machine learning.
New Properties of the Data Distillation Method When Working With Tabular Data
Venue: arXiv cs.LG 2020
Year: 2020

Data distillation is the problem of reducing the volume oftraining data while keeping only the necessary information. With thispaper, we deeper explore the new data distillation algorithm, previouslydesigned for image data. Our experiments with tabular data show thatthe model trained on distilled samples can outperform the model trainedon the original dataset. One of the problems of the considered algorithmis that produced data has poor generalization on models with differenthyperparameters. We show that using multiple architectures during distillation can help overcome this problem.