OpenRaiser/Intern-Atlas huggingface dataset:
CodeGRU: Context-aware Deep Learning with Gated Recurrent Unit for Source Code Modeling
Venue: arXiv cs.NE 2020
Year: 2020

Recently deep learning based Natural Language Processing (NLP) models have shown great potential in the modeling of source code. However, a major limitation of these approaches is that they take source code as simple tokens of text and ignore its contextual, syntactical and structural dependencies. In this work, we present CodeGRU, a gated recurrent unit based source code language model that is capable of capturing source code's contextual, syntactical and structural dependencies. We introduce a novel approach which can capture the source code context by leveraging the source code token types. Further, we adopt a novel approach which can learn variable size context by taking into account source code's syntax, and structural information. We evaluate CodeGRU with real-world data set and it shows that CodeGRU outperforms the state-of-the-art language models and help reduce the vocabulary size up to 24.93\%. Unlike previous works, we tested CodeGRU with an independent test set which suggests that our methodology does not requisite the source code comes from the same domain as training data while providing suggestions. We further evaluate CodeGRU with two software engineering applications: source code suggestion, and source code completion. Our experiment confirms that the source code's contextual information can be vital and can help improve the software language models. The extensive evaluation of CodeGRU shows that it outperforms the state-of-the-art models. The results further suggest that the proposed approach can help reduce the vocabulary size and is of practical use for software developers.
Two-phase protein folding optimization on a three-dimensional AB off-lattice model
Venue: arXiv cs.NE 2020
Year: 2020

This paper presents a two-phase protein folding optimization on a three-dimensional AB off-lattice model. The first phase is responsible for forming conformations with a good hydrophobic core or a set of compact hydrophobic amino acid positions. These conformations are forwarded to the second phase, where an accurate search is performed with the aim of locating conformations with the best energy value. The optimization process switches between these two phases until the stopping condition is satisfied. An auxiliary fitness function was designed for the first phase, while the original fitness function is used in the second phase. The auxiliary fitness function includes an expression about the quality of the hydrophobic core. This expression is crucial for leading the search process to the promising solutions that have a good hydrophobic core and, consequently, improves the efficiency of the whole optimization process. Our differential evolution algorithm was used for demonstrating the efficiency of two-phase optimization. It was analyzed on well-known amino acid sequences that are used frequently in the literature. The obtained experimental results show that the employed two-phase optimization improves the efficiency of our algorithm significantly and that the proposed algorithm is superior to other state-of-the-art algorithms.
Stabilizing the Lottery Ticket Hypothesis
Venue: arXiv cs.LG 2020
Year: 2020

Pruning is a well-established technique for removing unnecessary structure from neural networks after training to improve the performance of inference. Several recent results have explored the possibility of pruning at initialization time to provide similar benefits during training. In particular, the "lottery ticket hypothesis" conjectures that typical neural networks contain small subnetworks that can train to similar accuracy in a commensurate number of steps. The evidence for this claim is that a procedure based on iterative magnitude pruning (IMP) reliably finds such subnetworks retroactively on small vision tasks. However, IMP fails on deeper networks, and proposed methods to prune before training or train pruned networks encounter similar scaling limitations. In this paper, we argue that these efforts have struggled on deeper networks because they have focused on pruning precisely at initialization. We modify IMP to search for subnetworks that could have been obtained by pruning early in training (0.1% to 7% through) rather than at iteration 0. With this change, it finds small subnetworks of deeper networks (e.g., 80% sparsity on Resnet-50) that can complete the training process to match the accuracy of the original network on more challenging tasks (e.g., ImageNet). In situations where IMP fails at iteration 0, the accuracy benefits of delaying pruning accrue rapidly over the earliest iterations of training. To explain these behaviors, we study subnetwork "stability," finding that - as accuracy improves in this fashion - IMP subnetworks train to parameters closer to those of the full network and do so with improved consistency in the face of gradient noise. These results offer new insights into the opportunity to prune large-scale networks early in training and the behaviors underlying the lottery ticket hypothesis
Causal Discovery from Heterogeneous/Nonstationary Data with Independent Changes
Venue: arXiv cs.LG 2020
Year: 2020

It is commonplace to encounter heterogeneous or nonstationary data, of which the underlying generating process changes across domains or over time. Such a distribution shift feature presents both challenges and opportunities for causal discovery. In this paper, we develop a framework for causal discovery from such data, called Constraint-based causal Discovery from heterogeneous/NOnstationary Data (CD-NOD), to find causal skeleton and directions and estimate the properties of mechanism changes. First, we propose an enhanced constraint-based procedure to detect variables whose local mechanisms change and recover the skeleton of the causal structure over observed variables. Second, we present a method to determine causal orientations by making use of independent changes in the data distribution implied by the underlying causal model, benefiting from information carried by changing distributions. After learning the causal structure, next, we investigate how to efficiently estimate the "driving force" of the nonstationarity of a causal mechanism. That is, we aim to extract from data a low-dimensional representation of changes. The proposed methods are nonparametric, with no hard restrictions on data distributions and causal mechanisms, and do not rely on window segmentation. Furthermore, we find that data heterogeneity benefits causal structure identification even with particular types of confounders. Finally, we show the connection between heterogeneity/nonstationarity and soft intervention in causal discovery. Experimental results on various synthetic and real-world data sets (task-fMRI and stock market data) are presented to demonstrate the efficacy of the proposed methods.
Crowdsourced Behavior-Driven Development: Implementing Microservices through Microtasks
Venue: arXiv cs.SE 2020
Year: 2020

Key to the effectiveness of crowdsourcing approaches for software engineering is workflow design, describing how complex work is organized into small, relatively independent microtasks. In this paper, we introduce a Behavior-Driven Development (BDD) workflow for accomplishing programming work through self-contained microtasks, implemented as a preconfigured environment called Crowd Microservices. In our approach, a client, acting on behalf of a software team, describes a microservice as a set of endpoints with paths, requests, and responses. A crowd then implements the endpoints, identifying individual endpoint behaviors which they test, implement, and debug, creating new functions and interacting with persistence APIs as needed. To evaluate our approach, we conducted a feasibility study in which a small crowd worked to implement a small ToDo microservice. The crowd created an implementation with only four defects, completing 350 microtasks and implementing 13 functions. We discuss the implications of these findings for incorporating crowdsourced programming contributions into traditional software projects.
Revisiting the Evaluation of Uncertainty Estimation and Its Application to Explore Model Complexity-Uncertainty Trade-Off
Venue: arXiv cs.LG 2020
Year: 2020

Accurately estimating uncertainties in neural network predictions is of great importance in building trusted DNNs-based models, and there is an increasing interest in providing accurate uncertainty estimation on many tasks, such as security cameras and autonomous driving vehicles. In this paper, we focus on the two main use cases of uncertainty estimation, i.e. selective prediction and confidence calibration. We first reveal potential issues of commonly used quality metrics for uncertainty estimation in both use cases, and propose our new metrics to mitigate them. We then apply these new metrics to explore the trade-off between model complexity and uncertainty estimation quality, a critically missing work in the literature. Our empirical experiment results validate the superiority of the proposed metrics, and some interesting trends about the complexity-uncertainty trade-off are observed.
RINS-W: Robust Inertial Navigation System on Wheels
Venue: arXiv cs.RO 2020
Year: 2020

This paper proposes a real-time approach for long-term inertial navigation based only on an Inertial Measurement Unit (IMU) for self-localizing wheeled robots. The approach builds upon two components: 1) a robust detector that uses recurrent deep neural networks to dynamically detect a variety of situations of interest, such as zero velocity or no lateral slip; and 2) a state-of-the-art Kalman filter which incorporates this knowledge as pseudo-measurements for localization. Evaluations on a publicly available car dataset demonstrates that the proposed scheme may achieve a final precision of 20 m for a 21 km long trajectory of a vehicle driving for over an hour, equipped with an IMU of moderate precision (the gyro drift rate is 10 deg/h). To our knowledge, this is the first paper which combines sophisticated deep learning techniques with state-of-the-art filtering methods for pure inertial navigation on wheeled vehicles and as such opens up for novel data-driven inertial navigation techniques. Moreover, albeit taylored for IMU-only based localization, our method may be used as a component for self-localization of wheeled robots equipped with a more complete sensor suite.
Cache-Oblivious Priority Queues with Decrease-Key and Applications to Graph Algorithms
Venue: arXiv cs.DS 2020
Year: 2020

We present priority queues in the cache-oblivious external memory model with block size $B$ and main memory size $M$ that support on $N$ elements, operation \textsc{UPDATE} (combination of \textsc{INSERT} and \textsc{DECREASEKEY}) in $O \left(\frac{1}{B}\log_{\fracλ{B}} \frac{N}{B}\right)$ amortized I/Os and operations \textsc{EXTRACT-MIN} and \textsc{DELETE} in $O \left(\lceil \frac{λ^{\varepsilon}}{B} \log_{\fracλ{B}} \frac{N}{B} \rceil \log_{\fracλ{B}} \frac{N}{B}\right)$ amortized I/Os, using $O \left(\frac{N}{B}\log_{\fracλ{B}} \frac{N}{B}\right)$ blocks, for a user-defined parameter $λ\in [2, N ]$ and any real $\varepsilon \in (0,1)$. Our result improves upon previous I/O-efficient cache-oblivious and cache-aware priority queues [Chowdhury and Ramachandran, TALG 2018], [Brodal et al., SWAT 2004], [Kumar and Schwabe, SPDP 1996], [Arge et al., SICOMP 2007], [Fadel et al., TCS 1999]. We also present buffered repository trees that support on a multi-set of $N$ elements, operation \textsc{INSERT} in $O \left(\frac{1}{B}\log_{\fracλ{B}} \frac{N}{B}\right)$ I/Os and operation \textsc{EXTRACT} on $K$ extracted elements in $O \left(\frac{λ^{\varepsilon}}{B} \log_{\fracλ{B}} \frac{N}{B} + \frac{K}{B}\right)$ amortized I/Os, using $O \left(\frac{N}{B}\right)$ blocks, improving previous cache-aware and cache-oblivious results [Arge et al., SICOMP '07], [Buchsbaum et al., SODA '00]. In the cache-oblivious model, for $λ= O \left(E/V\right)$, we achieve $O \left(\frac{E}{B}\log_{\frac{E}{V B}} \frac{E}{B}\right)$ I/Os for single-source shortest paths, depth-first search and breadth-first search algorithms on massive directed dense graphs $(V,E)$. Our algorithms are I/O-optimal for $E/V = Ω(M)$ (and in the cache-aware setting for $λ= O(M)$).
Root Identification in Minirhizotron Imagery with Multiple Instance Learning
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, multiple instance learning (MIL) algorithms to automatically perform root detection and segmentation in minirhizotron imagery using only image-level labels are proposed. Root and soil characteristics vary from location to location, thus, supervised machine learning approaches that are trained with local data provide the best ability to identify and segment roots in minirhizotron imagery. However, labeling roots for training data (or otherwise) is an extremely tedious and time-consuming task. This paper aims to address this problem by labeling data at the image level (rather than the individual root or root pixel level) and train algorithms to perform individual root pixel level segmentation using MIL strategies. Three MIL methods (multiple instance adaptive cosine coherence estimator, multiple instance support vector machine, multiple instance learning with randomized trees) were applied to root detection and compared to non-MIL approches. The results show that MIL methods improve root segmentation in challenging minirhizotron imagery and reduce the labeling burden. In our results, multiple instance support vector machine outperformed other methods. The multiple instance adaptive cosine coherence estimator algorithm was a close second with an added advantage that it learned an interpretable root signature which identified the traits used to distinguish roots from soil and did not require parameter selection.
Unsupervised Domain Adaptation using Feature-Whitening and Consensus Loss
Venue: arXiv cs.CV 2020
Year: 2020

A classifier trained on a dataset seldom works on other datasets obtained under different conditions due to domain shift. This problem is commonly addressed by domain adaptation methods. In this work we introduce a novel deep learning framework which unifies different paradigms in unsupervised domain adaptation. Specifically, we propose domain alignment layers which implement feature whitening for the purpose of matching source and target feature distributions. Additionally, we leverage the unlabeled target data by proposing the Min-Entropy Consensus loss, which regularizes training while avoiding the adoption of many user-defined hyper-parameters. We report results on publicly available datasets, considering both digit classification and object recognition tasks. We show that, in most of our experiments, our approach improves upon previous methods, setting new state-of-the-art performances.
Provable Tensor Ring Completion
Venue: arXiv cs.LG 2020
Year: 2020

Tensor completion recovers a multi-dimensional array from a limited number of measurements. Using the recently proposed tensor ring (TR) decomposition, in this paper we show that a d-order tensor of dimensional size n and TR rank r can be exactly recovered with high probability by solving a convex optimization program, given n^{d/2} r^2 ln^7(n^{d/2})samples. The proposed TR incoherence condition under which the result holds is similar to the matrix incoherence condition. The experiments on synthetic data verify the recovery guarantee for TR completion. Moreover, the experiments on real-world data show that our method improves the recovery performance compared with the state-of-the-art methods.
The Homunculus Brain and Categorical Logic
Venue: arXiv cs.AI 2020
Year: 2020

The interaction between syntax (formal language) and its semantics (meanings of language) is one which has been well studied in categorical logic. The results of this particular study are employed to understand how the brain is able to create meanings. To emphasize the toy character of the proposed model, we prefer to speak of the homunculus brain rather than the brain per se. The homunculus brain consists of neurons, each of which is modeled by a category, and axons between neurons, which are modeled by functors between the corresponding neuron-categories. Each neuron (category) has its own program enabling its working, i.e. a theory of this neuron. In analogy to what is known from categorical logic, we postulate the existence of a pair of adjoint functors, called Lang and Syn, from a category, now called BRAIN, of categories, to a category, now called MIND, of theories. Our homunculus is a kind of ``mathematical robot'', the neuronal architecture of which is not important. Its only aim is to provide us with the opportunity to study how such a simple brain-like structure could ``create meanings'' and perform abstraction operations out of its purely syntactic program. The pair of adjoint functors Lang and Syn model the mutual dependencies between the syntactical structure of a given theory of MIND and the internal logic of its semantics given by a category of BRAIN. In this way, a formal language (syntax) and its meanings (semantics) are interwoven with each other in a manner corresponding to the adjointness of the functors Lang and Syn. Higher cognitive functions of abstraction and realization of concepts are also modelled by a corresponding pair of adjoint functors. The categories BRAIN and MIND interact with each other with their entire structures and, at the same time, these very structures are shaped by this interaction.
FASTER: Fast and Safe Trajectory Planner for Flights in Unknown Environments
Venue: arXiv cs.RO 2020
Year: 2020

High-speed trajectory planning through unknown environments requires algorithmic techniques that enable fast reaction times while maintaining safety as new information about the operating environment is obtained. The requirement of computational tractability typically leads to optimization problems that do not include the obstacle constraints (collision checks are done on the solutions) or use a convex decomposition of the free space and then impose an ad-hoc time allocation scheme for each interval of the trajectory. Moreover, safety guarantees are usually obtained by having a local planner that plans a trajectory with a final "stop" condition in the free-known space. However, these two decisions typically lead to slow and conservative trajectories. We propose FASTER (Fast and Safe Trajectory Planner) to overcome these issues. FASTER obtains high-speed trajectories by enabling the local planner to optimize in both the free-known and unknown spaces. Safety guarantees are ensured by always having a feasible, safe back-up trajectory in the free-known space at the start of each replanning step. Furthermore, we present a Mixed Integer Quadratic Program formulation in which the solver can choose the trajectory interval allocation, and where a time allocation heuristic is computed efficiently using the result of the previous replanning iteration. This proposed algorithm is tested extensively both in simulation and in real hardware, showing agile flights in unknown cluttered environments with velocities up to 3.6 m/s.
How far away must forced letters be so that squares are still avoidable?
Venue: arXiv cs.DM 2020
Year: 2020

We describe a new non-constructive technique to show that squares are avoidable by an infinite word even if we force some letters from the alphabet to appear at certain occurrences. We show that as long as forced positions are at distance at least 19 (resp. 3, resp. 2) from each other then we can avoid squares over 3 letters (resp. 4 letters, resp. 6 or more letters). We can also deduce exponential lower bounds on the number of solutions. For our main Theorem to be applicable, we need to check the existence of some languages and we explain how to verify that they exist with a computer. We hope that this technique could be applied to other avoidability questions where the good approach seems to be non-constructive (e.g., the Thue-list coloring number of the infinite path).
Revisiting clustering as matrix factorisation on the Stiefel manifold
Venue: arXiv cs.LG 2020
Year: 2020

This paper studies clustering for possibly high dimensional data (e.g. images, time series, gene expression data, and many other settings), and rephrase it as low rank matrix estimation in the PAC-Bayesian framework. Our approach leverages the well known Burer-Monteiro factorisation strategy from large scale optimisation, in the context of low rank estimation. Moreover, our Burer-Monteiro factors are shown to lie on a Stiefel manifold. We propose a new generalized Bayesian estimator for this problem and prove novel prediction bounds for clustering. We also devise a componentwise Langevin sampler on the Stiefel manifold to compute this estimator.
GOGGLES: Automatic Image Labeling with Affinity Coding
Venue: arXiv cs.CV 2020
Year: 2020

Generating large labeled training data is becoming the biggest bottleneck in building and deploying supervised machine learning models. Recently, the data programming paradigm has been proposed to reduce the human cost in labeling training data. However, data programming relies on designing labeling functions which still requires significant domain expertise. Also, it is prohibitively difficult to write labeling functions for image datasets as it is hard to express domain knowledge using raw features for images (pixels). We propose affinity coding, a new domain-agnostic paradigm for automated training data labeling. The core premise of affinity coding is that the affinity scores of instance pairs belonging to the same class on average should be higher than those of pairs belonging to different classes, according to some affinity functions. We build the GOGGLES system that implements affinity coding for labeling image datasets by designing a novel set of reusable affinity functions for images, and propose a novel hierarchical generative model for class inference using a small development set. We compare GOGGLES with existing data programming systems on 5 image labeling tasks from diverse domains. GOGGLES achieves labeling accuracies ranging from a minimum of 71% to a maximum of 98% without requiring any extensive human annotation. In terms of end-to-end performance, GOGGLES outperforms the state-of-the-art data programming system Snuba by 21% and a state-of-the-art few-shot learning technique by 5%, and is only 7% away from the fully supervised upper bound.
Information correlated Levy walk exploration and distributed mapping using a swarm of robots
Venue: arXiv cs.RO 2020
Year: 2020

In this work, we present a novel distributed method for constructing an occupancy grid map of an unknown environment using a swarm of robots with global localization capabilities and limited inter-robot communication. The robots explore the domain by performing Levy walks in which their headings are defined by maximizing the mutual information between the robot's estimate of its environment in the form of an occupancy grid map and the distance measurements that it is likely to obtain when it moves in that direction. Each robot is equipped with laser range sensors, and it builds its occupancy grid map by repeatedly combining its own distance measurements with map information that is broadcast by neighboring robots. Using results on average consensus over time-varying graph topologies, we prove that all robots' maps will eventually converge to the actual map of the environment. In addition, we demonstrate that a technique based on topological data analysis, developed in our previous work for generating topological maps, can be readily extended for adaptive thresholding of occupancy grid maps. We validate the effectiveness of our distributed exploration and mapping strategy through a series of 2D simulations and multi-robot experiments.