OpenRaiser/Intern-Atlas huggingface dataset:
Evaluating the Effectiveness of Efficient Neural Architecture Search for Sentence-Pair Tasks
Venue: arXiv cs.CL 2020
Year: 2020

Neural Architecture Search (NAS) methods, which automatically learn entire neural model or individual neural cell architectures, have recently achieved competitive or state-of-the-art (SOTA) performance on variety of natural language processing and computer vision tasks, including language modeling, natural language inference, and image classification. In this work, we explore the applicability of a SOTA NAS algorithm, Efficient Neural Architecture Search (ENAS) (Pham et al., 2018) to two sentence pair tasks, paraphrase detection and semantic textual similarity. We use ENAS to perform a micro-level search and learn a task-optimized RNN cell architecture as a drop-in replacement for an LSTM. We explore the effectiveness of ENAS through experiments on three datasets (MRPC, SICK, STS-B), with two different models (ESIM, BiLSTM-Max), and two sets of embeddings (Glove, BERT). In contrast to prior work applying ENAS to NLP tasks, our results are mixed -- we find that ENAS architectures sometimes, but not always, outperform LSTMs and perform similarly to random architecture search.
Performance Analysis of a Two-Tile Reconfigurable Intelligent Surface Assisted $2\times 2$ MIMO System
Venue: arXiv cs.IT 2020
Year: 2020

We consider a two--tile reconfigurable intelligent surface (RIS) assisted wireless network with a two-antenna transmitter and receiver over Rayleigh fading. We show that the average received signal-to-noise-ratio (SNR) optimal transmission and combining vectors are given by the left and right singular spaces of the RIS-receiver and transmit-RIS channel matrices, respectively. Moreover, the optimal phases at the two tiles of the RIS are determined by the phases of the elements of the latter spaces. To further study the effect of phase compensation, we statistically characterize the average SNR of all possible combinations of transmission and combining directions pertaining to the latter singular spaces by deriving novel expressions for the outage probability and throughput of each of those modes. Furthermore, for comparison, we derive the corresponding expressions in the absence of RIS. Our results show an approximate SNR improvement of $2$\,dB due to the phase compensation at the RIS.
Succinct Navigational Oracles for Families of Intersection Graphs on a Circle
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency, and neighborhood efficiently for intersection graphs on a circle, which include graph classes such as {\it circle graphs}, {\it $k$-polygon-circle graphs}, {\it circle-trapezoid graphs}, {\it trapezoid graphs}. The degree query reports the number of incident edges to a given vertex, the adjacency query asks if there is an edge between two given vertices, and the neighborhood query enumerates all the neighbors of a given vertex. We first prove a general lower bound for these intersection graph classes and then present a uniform approach that lets us obtain matching lower and upper bounds for representing each of these graph classes. More specifically, our lower bound proofs use a unified technique to produce tight bounds for all these classes, and this is followed by our data structures which are also obtained from a unified representation method to achieve succinctness for each class. In addition, we prove a lower bound of space for representing {\it trapezoid} graphs and give a succinct navigational oracle for this class of graphs.
An ensemble learning approach for software semantic clone detection
Venue: arXiv cs.SE 2020
Year: 2020

Code clone is a serious problem in software and has the potential to software defects, maintenance overhead, and licensing violations. Therefore, clone detection is important for reducing maintenance effort and improving code quality during software evolution. A variety of clone detection techniques have been proposed to identify similar code in software. However, few of them can efficiently detect semantic clones (functionally similar code without any syntactic resemblance). Recently, several deep learning based clone detectors are proposed to detect semantic clones. However, these approaches have high cost in data labelling and model training. In this paper, we propose a novel approach that leverages word embedding and ensemble learning techniques to detect semantic clones. Our evaluation on a commonly used clone benchmark, BigCloneBench, shows that our approach significantly improves the precision and recall of semantic clone detection, in comparison to a token-based clone detector, SourcererCC, and another deep learning based clone detector, CDLH.
GitEvolve: Predicting the Evolution of GitHub Repositories
Venue: arXiv cs.SI 2020
Year: 2020

Software development is becoming increasingly open and collaborative with the advent of platforms such as GitHub. Given its crucial role, there is a need to better understand and model the dynamics of GitHub as a social platform. Previous work has mostly considered the dynamics of traditional social networking sites like Twitter and Facebook. We propose GitEvolve, a system to predict the evolution of GitHub repositories and the different ways by which users interact with them. To this end, we develop an end-to-end multi-task sequential deep neural network that given some seed events, simultaneously predicts which user-group is next going to interact with a given repository, what the type of the interaction is, and when it happens. To facilitate learning, we use graph based representation learning to encode relationship between repositories. We map users to groups by modelling common interests to better predict popularity and to generalize to unseen users during inference. We introduce an artificial event type to better model varying levels of activity of repositories in the dataset. The proposed multi-task architecture is generic and can be extended to model information diffusion in other social networks. In a series of experiments, we demonstrate the effectiveness of the proposed model, using multiple metrics and baselines. Qualitative analysis of the model's ability to predict popularity and forecast trends proves its applicability.
iobes: A Library for Span-Level Processing
Venue: arXiv cs.CL 2020
Year: 2020

Many tasks in natural language processing, such as named entity recognition and slot-filling, involve identifying and labeling specific spans of text. In order to leverage common models, these tasks are often recast as sequence labeling tasks. Each token is given a label and these labels are prefixed with special tokens such as B- or I-. After a model assigns labels to each token, these prefixes are used to group the tokens into spans. Properly parsing these annotations is critical for producing fair and comparable metrics; however, despite its importance, there is not an easy-to-use, standardized, programmatically integratable library to help work with span labeling. To remedy this, we introduce our open-source library, iobes. iobes is used for parsing, converting, and processing spans represented as token level decisions.
Investigating Constraint Relationship in Evolutionary Many-Constraint Optimization
Venue: arXiv cs.AI 2020
Year: 2020

This paper contributes to the treatment of extensive constraints in evolutionary many-constraint optimization through consideration of the relationships between pair-wise constraints. In a conflicting relationship, the functional value of one constraint increases as the value in another constraint decreases. In a harmonious relationship, the improvement in one constraint is rewarded with simultaneous improvement in the other constraint. In an independent relationship, the adjustment to one constraint never affects the adjustment to the other. Based on the different features, methods for identifying constraint relationships are discussed, helping to simplify many-constraint optimization problems (MCOPs). Additionally, the transitivity of the relationships is further discussed at the aim of determining the relationship in a new pair of constraints.
On the Transmission Probabilities in Quantum Key Distribution Systems over FSO Links
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we investigate the transmission probabilities in three cases (depending only on the legitimate receiver, depending only the eavesdropper, and depending on both legitimate receiver and eavesdropper) in quantum key distribution (QKD) systems over free-space optical links. To be more realistic, we consider a generalized pointing error scenario, where the azimuth and elevation pointing error angles caused by stochastic jitters and vibrations in the legitimate receiver platform are independently distributed according to a non-identical normal distribution. Taking these assumptions into account, we derive approximate expressions of transmission probabilities by using the Gaussian quadrature method. To simplify the expressions and get some physical insights, some asymptotic analysis on the transmission probabilities is presented based on asymptotic expression for the generalized Marcum Q-function when the telescope gain at the legitimate receiver approaches to infinity. Moreover, from the asymptotic expression for the generalized Marcum Q-function, the asymptotic outage probability over Beckmann fading channels (a general channel model including Rayleigh, Rice, and Hoyt fading channels) can be also easily derived when the average signal-to-noise ratio is sufficiently large, which shows the diversity order and array gain.
Measuring What Counts: The case of Rumour Stance Classification
Venue: arXiv cs.CL 2020
Year: 2020

Stance classification can be a powerful tool for understanding whether and which users believe in online rumours. The task aims to automatically predict the stance of replies towards a given rumour, namely support, deny, question, or comment. Numerous methods have been proposed and their performance compared in the RumourEval shared tasks in 2017 and 2019. Results demonstrated that this is a challenging problem since naturally occurring rumour stance data is highly imbalanced. This paper specifically questions the evaluation metrics used in these shared tasks. We re-evaluate the systems submitted to the two RumourEval tasks and show that the two widely adopted metrics -- accuracy and macro-F1 -- are not robust for the four-class imbalanced task of rumour stance classification, as they wrongly favour systems with highly skewed accuracy towards the majority class. To overcome this problem, we propose new evaluation metrics for rumour stance detection. These are not only robust to imbalanced data but also score higher systems that are capable of recognising the two most informative minority classes (support and deny).
Incorporating planning intelligence into deep learning: A planning support tool for street network design
Venue: arXiv cs.CV 2020
Year: 2020

Deep learning applications in shaping ad hoc planning proposals are limited by the difficulty in integrating professional knowledge about cities with artificial intelligence. We propose a novel, complementary use of deep neural networks and planning guidance to automate street network generation that can be context-aware, example-based and user-guided. The model tests suggest that the incorporation of planning knowledge (e.g., road junctions and neighborhood types) in the model training leads to a more realistic prediction of street configurations. Furthermore, the new tool provides both professional and lay users an opportunity to systematically and intuitively explore benchmark proposals for comparisons and further evaluations.
Neural Random Projection: From the Initial Task To the Input Similarity Problem
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we propose a novel approach for implicit data representation to evaluate similarity of input data using a trained neural network. In contrast to the previous approach, which uses gradients for representation, we utilize only the outputs from the last hidden layer of a neural network and do not use a backward step. The proposed technique explicitly takes into account the initial task and significantly reduces the size of the vector representation, as well as the computation time. The key point is minimization of information loss between layers. Generally, a neural network discards information that is not related to the problem, which makes the last hidden layer representation useless for input similarity task. In this work, we consider two main causes of information loss: correlation between neurons and insufficient size of the last hidden layer. To reduce the correlation between neurons we use orthogonal weight initialization for each layer and modify the loss function to ensure orthogonality of the weights during training. Moreover, we show that activation functions can potentially increase correlation. To solve this problem, we apply modified Batch-Normalization with Dropout. Using orthogonal weight matrices allow us to consider such neural networks as an application of the Random Projection method and get a lower bound estimate for the size of the last hidden layer. We perform experiments on MNIST and physical examination datasets. In both experiments, initially, we split a set of labels into two disjoint subsets to train a neural network for binary classification problem, and then use this model to measure similarity between input data and define hidden classes. Our experimental results show that the proposed approach achieves competitive results on the input similarity task while reducing both computation time and the size of the input representation.
Integrating Intrinsic and Extrinsic Explainability: The Relevance of Understanding Neural Networks for Human-Robot Interaction
Venue: arXiv cs.RO 2020
Year: 2020

Explainable artificial intelligence (XAI) can help foster trust in and acceptance of intelligent and autonomous systems. Moreover, understanding the motivation for an agent's behavior results in better and more successful collaborations between robots and humans. However, not only can humans benefit from a robot's explanation but the robot itself can also benefit from explanations given to him. Currently, most attention is paid to explaining deep neural networks and black-box models. However, a lot of these approaches are not applicable to humanoid robots. Therefore, in this position paper, current problems with adapting XAI methods to explainable neurorobotics are described. Furthermore, NICO, an open-source humanoid robot platform, is introduced and how the interaction of intrinsic explanations by the robot itself and extrinsic explanations provided by the environment enable efficient robotic behavior.
Adaptive and Momentum Methods on Manifolds Through Trivializations
Venue: arXiv cs.LG 2020
Year: 2020

Adaptive methods do not have a direct generalization to manifolds as the adaptive term is not invariant. Momentum methods on manifolds suffer from efficiency problems stemming from the curvature of the manifold. We introduce a framework to generalize adaptive and momentum methods to arbitrary manifolds by noting that for every differentiable manifold, there exists a radially convex open set that covers almost all the manifold. Being radially convex, this set is diffeomorphic to $\mathbb{R}^n$. This gives a natural generalization of any adaptive and momentum-based algorithm to a set that covers almost all the manifold in an arbitrary manifolds. We also show how to extend these methods to the context of gradient descent methods with a retraction. For its implementation, we bring an approximation to the exponential of matrices that needs just of 5 matrix multiplications, making it particularly efficient on GPUs. In practice, we see that this family of algorithms closes the numerical gap created by an incorrect use of momentum and adaptive methods on manifolds. At the same time, we see that the most efficient algorithm of this family is given by simply pulling back the problem to the tangent space at the initial point via the exponential map.
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
Venue: arXiv cs.CC 2020
Year: 2020

The Promise Constraint Satisfaction Problem (PCSP) is a recently introduced vast generalization of the Constraint Satisfaction Problem (CSP). We investigate the computational complexity of a class of PCSPs beyond the most studied cases - approximation variants of satisfiability and graph coloring problems. We give an almost complete classification for the class of PCSPs of the form: given a 3-uniform hypergraph that has an admissible 2-coloring, find an admissible 3-coloring, where admissibility is given by a ternary symmetric relation. The only PCSP of this sort whose complexity is left open in this work is a natural hypergraph coloring problem, where admissibility is given by the relation "if two colors are equal, then the remaining one is higher."
Examining the Ordering of Rhetorical Strategies in Persuasive Requests
Venue: arXiv cs.CL 2020
Year: 2020

Interpreting how persuasive language influences audiences has implications across many domains like advertising, argumentation, and propaganda. Persuasion relies on more than a message's content. Arranging the order of the message itself (i.e., ordering specific rhetorical strategies) also plays an important role. To examine how strategy orderings contribute to persuasiveness, we first utilize a Variational Autoencoder model to disentangle content and rhetorical strategies in textual requests from a large-scale loan request corpus. We then visualize interplay between content and strategy through an attentional LSTM that predicts the success of textual requests. We find that specific (orderings of) strategies interact uniquely with a request's content to impact success rate, and thus the persuasiveness of a request.
Recurrent babbling: evaluating the acquisition of grammar from limited input data
Venue: arXiv cs.CL 2020
Year: 2020

Recurrent Neural Networks (RNNs) have been shown to capture various aspects of syntax from raw linguistic input. In most previous experiments, however, learning happens over unrealistic corpora, which do not reflect the type and amount of data a child would be exposed to. This paper remedies this state of affairs by training a Long Short-Term Memory network (LSTM) over a realistically sized subset of child-directed input. The behaviour of the network is analysed over time using a novel methodology which consists in quantifying the level of grammatical abstraction in the model's generated output (its "babbling"), compared to the language it has been exposed to. We show that the LSTM indeed abstracts new structuresas learning proceeds.
Recursive Top-Down Production for Sentence Generation with Latent Trees
Venue: arXiv cs.CL 2020
Year: 2020

We model the recursive production property of context-free grammars for natural and synthetic languages. To this end, we present a dynamic programming algorithm that marginalises over latent binary tree structures with $N$ leaves, allowing us to compute the likelihood of a sequence of $N$ tokens under a latent tree model, which we maximise to train a recursive neural function. We demonstrate performance on two synthetic tasks: SCAN (Lake and Baroni, 2017), where it outperforms previous models on the LENGTH split, and English question formation (McCoy et al., 2020), where it performs comparably to decoders with the ground-truth tree structure. We also present experimental results on German-English translation on the Multi30k dataset (Elliott et al., 2016), and qualitatively analyse the induced tree structures our model learns for the SCAN tasks and the German-English translation task.
Solving Historical Dictionary Codes with a Neural Language Model
Venue: arXiv cs.CL 2020
Year: 2020

We solve difficult word-based substitution codes by constructing a decoding lattice and searching that lattice with a neural language model. We apply our method to a set of enciphered letters exchanged between US Army General James Wilkinson and agents of the Spanish Crown in the late 1700s and early 1800s, obtained from the US Library of Congress. We are able to decipher 75.1% of the cipher-word tokens correctly.
Reparametrizing gradient descent
Venue: arXiv cs.LG 2020
Year: 2020

In this work, we propose an optimization algorithm which we call norm-adapted gradient descent. This algorithm is similar to other gradient-based optimization algorithms like Adam or Adagrad in that it adapts the learning rate of stochastic gradient descent at each iteration. However, rather than using statistical properties of observed gradients, norm-adapted gradient descent relies on a first-order estimate of the effect of a standard gradient descent update step, much like the Newton-Raphson method in many dimensions. Our algorithm can also be compared to quasi-Newton methods, but we seek roots rather than stationary points. Seeking roots can be justified by the fact that for models with sufficient capacity measured by nonnegative loss functions, roots coincide with global optima. This work presents several experiments where we have used our algorithm; in these results, it appears norm-adapted descent is particularly strong in regression settings but is also capable of training classifiers.
Modeling Black-Box Components with Probabilistic Synthesis
Venue: arXiv cs.PL 2020
Year: 2020

This paper is concerned with synthesizing programs based on black-box oracles: we are interested in the case where there exists an executable implementation of a component or library, but its internal structure is unknown. We are provided with just an API or function signature, and aim to synthesize a program with equivalent behavior. To attack this problem, we detail Presyn: a program synthesizer designed for flexible interoperation with existing programs and compiler toolchains. Presyn uses high-level imperative control-flow structures and a pair of cooperating predictive models to efficiently narrow the space of potential programs. These models can be trained effectively on small corpora of synthesized examples. We evaluate Presyn against five leading program synthesizers on a collection of 112 synthesis benchmarks collated from previous studies and real-world software libraries. We show that Presyn is able to synthesize a wider range of programs than each of them with less human input. We demonstrate the application of our approach to real-world code and software engineering problems with two case studies: accelerator library porting and detection of duplicated library reimplementations.
On Task-Level Dialogue Composition of Generative Transformer Model
Venue: arXiv cs.CL 2020
Year: 2020

Task-oriented dialogue systems help users accomplish tasks such as booking a movie ticket and ordering food via conversation. Generative models parameterized by a deep neural network are widely used for next turn response generation in such systems. It is natural for users of the system to want to accomplish multiple tasks within the same conversation, but the ability of generative models to compose multiple tasks is not well studied. In this work, we begin by studying the effect of training human-human task-oriented dialogues towards improving the ability to compose multiple tasks on Transformer generative models. To that end, we propose and explore two solutions: (1) creating synthetic multiple task dialogue data for training from human-human single task dialogue and (2) forcing the encoder representation to be invariant to single and multiple task dialogues using an auxiliary loss. The results from our experiments highlight the difficulty of even the sophisticated variant of transformer model in learning to compose multiple tasks from single task dialogues.