OpenRaiser/Intern-Atlas huggingface dataset:
Metric Spaces with Expensive Distances
Venue: arXiv cs.CG 2019
Year: 2019

In algorithms for finite metric spaces, it is common to assume that the distance between two points can be computed in constant time, and complexity bounds are expressed only in terms of the number of points of the metric space. We introduce a different model where we assume that the computation of a single distance is an expensive operation and consequently, the goal is to minimize the number of such distance queries. This model is motivated by metric spaces that appear in the context of topological data analysis. We consider two standard operations on metric spaces, namely the construction of a $1+\varepsilon$-spanner and the computation of an approximate nearest neighbor for a given query point. In both cases, we partially explore the metric space through distance queries and infer lower and upper bounds for yet unexplored distances through triangle inequality. For spanners, we evaluate several exploration strategies through extensive experimental evaluation. For approximate nearest neighbors, we prove that our strategy returns an approximate nearest neighbor after a logarithmic number of distance queries.
Deep Learning-aided Application Scheduler for Vehicular Safety Communication
Venue: arXiv cs.NI 2019
Year: 2019

802.11p based V2X communication uses stochastic medium access control, which cannot prevent broadcast packet collision, in particular during high channel load. Wireless congestion control has been designed to keep the channel load at an optimal point. However, vehicles' lack of precise and granular knowledge about true channel activity, in time and space, makes it impossible to fully avoid packet collisions. In this paper, we propose a machine learning approach using deep neural network for learning the vehicles' transmit patterns, and as such predicting future channel activity in space and time. We evaluate the performance of our proposal via simulation considering multiple safety-related V2X services involving heterogeneous transmit patterns. Our results show that predicting channel activity, and transmitting accordingly, reduces collisions and significantly improves communication performance.
Bayesian surrogate learning in dynamic simulator-based regression problems
Venue: arXiv cs.LG 2019
Year: 2019

The estimation of unknown values of parameters (or hidden variables, control variables) that characterise a physical system often relies on the comparison of measured data with synthetic data produced by some numerical simulator of the system as the parameter values are varied. This process often encounters two major difficulties: the generation of synthetic data for each considered set of parameter values can be computationally expensive if the system model is complicated; and the exploration of the parameter space can be inefficient and/or incomplete, a typical example being when the exploration becomes trapped in a local optimum of the objection function that characterises the mismatch between the measured and synthetic data. A method to address both these issues is presented, whereby: a surrogate model (or proxy), which emulates the computationally expensive system simulator, is constructed using deep recurrent networks (DRN); and a nested sampling (NS) algorithm is employed to perform efficient and robust exploration of the parameter space. The analysis is performed in a Bayesian context, in which the samples characterise the full joint posterior distribution of the parameters, from which parameter estimates and uncertainties are easily derived. The proposed approach is compared with conventional methods in some numerical examples, for which the results demonstrate that one can accelerate the parameter estimation process by at least an order of magnitude.
Bottom-up Broadcast Neural Network For Music Genre Classification
Venue: arXiv cs.SD 2019
Year: 2019

Music genre recognition based on visual representation has been successfully explored over the last years. Recently, there has been increasing interest in attempting convolutional neural networks (CNNs) to achieve the task. However, most of existing methods employ the mature CNN structures proposed in image recognition without any modification, which results in the learning features that are not adequate for music genre classification. Faced with the challenge of this issue, we fully exploit the low-level information from spectrograms of audios and develop a novel CNN architecture in this paper. The proposed CNN architecture takes the long contextual information into considerations, which transfers more suitable information for the decision-making layer. Various experiments on several benchmark datasets, including GTZAN, Ballroom, and Extended Ballroom, have verified the excellent performances of the proposed neural network. Codes and model will be available at "ttps://github.com/CaifengLiu/music-genre-classification".
Computational landscape of user behavior on social media
Venue: arXiv cs.SI 2019
Year: 2019

With the increasing abundance of 'digital footprints' left by human interactions in online environments, e.g., social media and app use, the ability to model complex human behavior has become increasingly possible. Many approaches have been proposed, however, most previous model frameworks are fairly restrictive. We introduce a new social modeling approach that enables the creation of models directly from data with minimal a priori restrictions on the model class. In particular, we infer the minimally complex, maximally predictive representation of an individual's behavior when viewed in isolation and as driven by a social input. We then apply this framework to a heterogeneous catalog of human behavior collected from fifteen thousand users on the microblogging platform Twitter. The models allow us to describe how a user processes their past behavior and their social inputs. Despite the diversity of observed user behavior, most models inferred fall into a small subclass of all possible finite-state processes. Thus, our work demonstrates that user behavior, while quite complex, belies simple underlying computational structures.
Improving Image Captioning by Leveraging Knowledge Graphs
Venue: arXiv cs.CV 2019
Year: 2019

We explore the use of a knowledge graphs, that capture general or commonsense knowledge, to augment the information extracted from images by the state-of-the-art methods for image captioning. The results of our experiments, on several benchmark data sets such as MS COCO, as measured by CIDEr-D, a performance metric for image captioning, show that the variants of the state-of-the-art methods for image captioning that make use of the information extracted from knowledge graphs can substantially outperform those that rely solely on the information extracted from images.
Perturbed Proximal Descent to Escape Saddle Points for Non-convex and Non-smooth Objective Functions
Venue: arXiv cs.LG 2019
Year: 2019

We consider the problem of finding local minimizers in non-convex and non-smooth optimization. Under the assumption of strict saddle points, positive results have been derived for first-order methods. We present the first known results for the non-smooth case, which requires different analysis and a different algorithm.
Towards Approximate Mobile Computing
Venue: arXiv cs.OH 2019
Year: 2019

Mobile computing is one of the main drivers of innovation, yet the future growth of mobile computing capabilities remains critically threatened by hardware constraints, such as the already extremely dense transistor packing and limited battery capacity. The breakdown of Dennard scaling and stagnating energy storage improvements further amplify these threats. However, the computational burden we put on our mobile devices is not always justified. In a myriad of situations the result of a computation is further manipulated, interpreted, and finally acted upon. This allows for the computation to be relaxed, so that the result is calculated with "good enough", not perfect accuracy. For example, results of a Web search may be perfectly acceptable even if the order of the last few listed items is shuffled, as an end user decides which of the available links to follow. Similarly, the quality of a voice-over-IP call may be acceptable, despite being imperfect, as long as the two involved parties can clearly understand each other. This novel way of thinking about computation is termed Approximate Computing (AC) and promises to reduce resource usage, while ensuring that satisfactory performance is delivered to end-users. AC is already experimented with on various levels of desktop computer architecture, from the hardware level where incorrect adders have been designed to sacrifice result correctness for reduced energy consumption, to compiler-level optimisations that omit certain lines of code to speed up video encoding. AC is yet to be attempted on mobile devices and in this article we examine the potential benefits of mobile AC and present an overview of AC techniques applicable in the mobile domain.
Dynamical Isometry and a Mean Field Theory of LSTMs and GRUs
Venue: arXiv cs.LG 2019
Year: 2019

Training recurrent neural networks (RNNs) on long sequence tasks is plagued with difficulties arising from the exponential explosion or vanishing of signals as they propagate forward or backward through the network. Many techniques have been proposed to ameliorate these issues, including various algorithmic and architectural modifications. Two of the most successful RNN architectures, the LSTM and the GRU, do exhibit modest improvements over vanilla RNN cells, but they still suffer from instabilities when trained on very long sequences. In this work, we develop a mean field theory of signal propagation in LSTMs and GRUs that enables us to calculate the time scales for signal propagation as well as the spectral properties of the state-to-state Jacobians. By optimizing these quantities in terms of the initialization hyperparameters, we derive a novel initialization scheme that eliminates or reduces training instabilities. We demonstrate the efficacy of our initialization scheme on multiple sequence tasks, on which it enables successful training while a standard initialization either fails completely or is orders of magnitude slower. We also observe a beneficial effect on generalization performance using this new initialization.
Diffusion Variational Autoencoders
Venue: arXiv cs.LG 2019
Year: 2019

A standard Variational Autoencoder, with a Euclidean latent space, is structurally incapable of capturing topological properties of certain datasets. To remove topological obstructions, we introduce Diffusion Variational Autoencoders with arbitrary manifolds as a latent space. A Diffusion Variational Autoencoder uses transition kernels of Brownian motion on the manifold. In particular, it uses properties of the Brownian motion to implement the reparametrization trick and fast approximations to the KL divergence. We show that the Diffusion Variational Autoencoder is capable of capturing topological properties of synthetic datasets. Additionally, we train MNIST on spheres, tori, projective spaces, SO(3), and a torus embedded in R3. Although a natural dataset like MNIST does not have latent variables with a clear-cut topological structure, training it on a manifold can still highlight topological and geometrical properties.
No-three-in-line problem on a torus: periodicity
Venue: arXiv cs.DM 2019
Year: 2019

Let $τ_{m,n}$ denote the maximal number of points on the discrete torus (discrete toric grid) of sizes $m \times n$ with no three collinear points. The value $τ_{m,n}$ is known for the case where $\gcd(m,n)$ is prime. It is also known that $τ_{m,n} \leq 2\gcd(m,n)$. In this paper we generalize some of the known tools for determining $τ_{m,n}$ and also show some new. Using these tools we prove that the sequence $(τ_{z,n})_{n \in \mathbb{N}}$ is periodic for all fixed $z > 1$. In general, we do not know the period; however, if $z = p^a$ for $p$ prime, then we can bound it. We prove that $τ_{p^a,p^{(a-1)p+2}} = 2p^a$ which implies that the period for the sequence is $p^b$ where $b$ is at most $(a-1)p+2$.
Software Architecture Metrics: a literature review
Venue: arXiv cs.SE 2019
Year: 2019

In Software Engineering, early detection of architectural issues is key. It helps mitigate the risk of poor performance, and lowers the cost of repairing these issues. Metrics give a quick overview of the project which helps designers with the detection of flaws or degradation in their architecture. Even though studies unveiled architectural metrics more than 25 years ago, they have not yet been embraced by the industry nor the open source community. In this study, we aim at conducting a review of existing metrics focused on the software architecture for evaluating quality, early in the design flow and throughout the project's lifetime. We also give guidelines of their usage and study their relevance in different contexts.
Not So Fast: Analyzing the Performance of WebAssembly vs. Native Code
Venue: arXiv cs.PL 2019
Year: 2019

All major web browsers now support WebAssembly, a low-level bytecode intended to serve as a compilation target for code written in languages like C and C++. A key goal of WebAssembly is performance parity with native code; previous work reports near parity, with many applications compiled to WebAssembly running on average 10% slower than native code. However, this evaluation was limited to a suite of scientific kernels, each consisting of roughly 100 lines of code. Running more substantial applications was not possible because compiling code to WebAssembly is only part of the puzzle: standard Unix APIs are not available in the web browser environment. To address this challenge, we build Browsix-Wasm, a significant extension to Browsix that, for the first time, makes it possible to run unmodified WebAssembly-compiled Unix applications directly inside the browser. We then use Browsix-Wasm to conduct the first large-scale evaluation of the performance of WebAssembly vs. native. Across the SPEC CPU suite of benchmarks, we find a substantial performance gap: applications compiled to WebAssembly run slower by an average of 45% (Firefox) to 55% (Chrome), with peak slowdowns of 2.08x (Firefox) and 2.5x (Chrome). We identify the causes of this performance degradation, some of which are due to missing optimizations and code generation issues, while others are inherent to the WebAssembly platform.
Learning Classifiers for Domain Adaptation, Zero and Few-Shot Recognition Based on Learning Latent Semantic Parts
Venue: arXiv cs.CV 2019
Year: 2019

In computer vision applications, such as domain adaptation (DA), few shot learning (FSL) and zero-shot learning (ZSL), we encounter new objects and environments, for which insufficient examples exist to allow for training "models from scratch," and methods that adapt existing models, trained on the presented training environment, to the new scenario are required. We propose a novel visual attribute encoding method that encodes each image as a low-dimensional probability vector composed of prototypical part-type probabilities. The prototypes are learnt to be representative of all training data. At test-time we utilize this encoding as an input to a classifier. At test-time we freeze the encoder and only learn/adapt the classifier component to limited annotated labels in FSL; new semantic attributes in ZSL. We conduct extensive experiments on benchmark datasets. Our method outperforms state-of-art methods trained for the specific contexts (ZSL, FSL, DA).
Generative Adversarial Networks for Black-Box API Attacks with Limited Training Data
Venue: arXiv cs.LG 2019
Year: 2019

As online systems based on machine learning are offered to public or paid subscribers via application programming interfaces (APIs), they become vulnerable to frequent exploits and attacks. This paper studies adversarial machine learning in the practical case when there are rate limitations on API calls. The adversary launches an exploratory (inference) attack by querying the API of an online machine learning system (in particular, a classifier) with input data samples, collecting returned labels to build up the training data, and training an adversarial classifier that is functionally equivalent and statistically close to the target classifier. The exploratory attack with limited training data is shown to fail to reliably infer the target classifier of a real text classifier API that is available online to the public. In return, a generative adversarial network (GAN) based on deep learning is built to generate synthetic training data from a limited number of real training data samples, thereby extending the training data and improving the performance of the inferred classifier. The exploratory attack provides the basis to launch the causative attack (that aims to poison the training process) and evasion attack (that aims to fool the classifier into making wrong decisions) by selecting training and test data samples, respectively, based on the confidence scores obtained from the inferred classifier. These stealth attacks with small footprint (using a small number of API calls) make adversarial machine learning practical under the realistic case with limited training data available to the adversary.
The Use of Unlabeled Data versus Labeled Data for Stopping Active Learning for Text Classification
Venue: arXiv cs.LG 2019
Year: 2019

Annotation of training data is the major bottleneck in the creation of text classification systems. Active learning is a commonly used technique to reduce the amount of training data one needs to label. A crucial aspect of active learning is determining when to stop labeling data. Three potential sources for informing when to stop active learning are an additional labeled set of data, an unlabeled set of data, and the training data that is labeled during the process of active learning. To date, no one has compared and contrasted the advantages and disadvantages of stopping methods based on these three information sources. We find that stopping methods that use unlabeled data are more effective than methods that use labeled data.
Star Routing: Between Vehicle Routing and Vertex Cover
Venue: arXiv cs.DS 2019
Year: 2019

We consider an optimization problem posed by an actual newspaper company, which consists of computing a minimum length route for a delivery truck, such that the driver only stops at street crossings, each time delivering copies to all customers adjacent to the crossing. This can be modeled as an abstract problem that takes an unweighted simple graph $G = (V, E)$ and a subset of edges $X$ and asks for a shortest cycle, not necessarily simple, such that every edge of $X$ has an endpoint in the cycle. We show that the decision version of the problem is strongly NP-complete, even if $G$ is a grid graph. Regarding approximate solutions, we show that the general case of the problem is APX-hard, and thus no PTAS is possible unless P $=$ NP. Despite the hardness of approximation, we show that given any $α$-approximation algorithm for metric TSP, we can build a $3α$-approximation algorithm for our optimization problem, yielding a concrete $9/2$-approximation algorithm. The grid case is of particular importance, because it models a city map or some part of it. A usual scenario is having some neighborhood full of customers, which translates as an instance of the abstract problem where almost every edge of $G$ is in $X$. We model this property as $|E - X| = o(|E|)$, and for these instances we give a $(3/2 + \varepsilon)$-approximation algorithm, for any $\varepsilon > 0$, provided that the grid is sufficiently big.
Discovery of Important Subsequences in Electrocardiogram Beats Using the Nearest Neighbour Algorithm
Venue: arXiv cs.LG 2019
Year: 2019

The classification of time series data is a well-studied problem with numerous practical applications, such as medical diagnosis and speech recognition. A popular and effective approach is to classify new time series in the same way as their nearest neighbours, whereby proximity is defined using Dynamic Time Warping (DTW) distance, a measure analogous to sequence alignment in bioinformatics. However, practitioners are not only interested in accurate classification, they are also interested in why a time series is classified a certain way. To this end, we introduce here the problem of finding a minimum length subsequence of a time series, the removal of which changes the outcome of the classification under the nearest neighbour algorithm with DTW distance. Informally, such a subsequence is expected to be relevant for the classification and can be helpful for practitioners in interpreting the outcome. We describe a simple but optimized implementation for detecting these subsequences and define an accompanying measure to quantify the relevance of every time point in the time series for the classification. In tests on electrocardiogram data we show that the algorithm allows discovery of important subsequences and can be helpful in detecting abnormalities in cardiac rhythms distinguishing sick from healthy patients.
Deep Convolutional Encoder-Decoders with Aggregated Multi-Resolution Skip Connections for Skin Lesion Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

The prevalence of skin melanoma is rapidly increasing as well as the recorded death cases of its patients. Automatic image segmentation tools play an important role in providing standardized computer-assisted analysis for skin melanoma patients. Current state-of-the-art segmentation methods are based on fully convolutional neural networks, which utilize an encoder-decoder approach. However, these methods produce coarse segmentation masks due to the loss of location information during the encoding layers. Inspired by Pyramid Scene Parsing Network (PSP-Net), we propose an encoder-decoder model that utilizes pyramid pooling modules in the deep skip connections which aggregate the global context and compensate for the lost spatial information. We trained and validated our approach using ISIC 2018: Skin Lesion Analysis Towards Melanoma Detection grand challenge dataset. Our approach showed a validation accuracy with a Jaccard index of 0.837, which outperforms U-Net. We believe that with this reported reliable accuracy, this method can be introduced for clinical practice.
Steiner systems $S(2, 4, \frac{3^m-1}{2})$ and $2$-designs from ternary linear codes of length $\frac{3^m-1}{2}$
Venue: arXiv cs.IT 2019
Year: 2019

Coding theory and $t$-designs have close connections and interesting interplay. In this paper, we first introduce a class of ternary linear codes and study their parameters. We then focus on their three-weight subcodes with a special weight distribution. We determine the weight distributions of some shortened codes and punctured codes of these three-weight subcodes. These shortened and punctured codes contain some codes that have the same parameters as the best ternary linear codes known in the database maintained by Markus Grassl at http://www.codetables.de/. These three-weight subcodes with a special weight distribution do not satisfy the conditions of the Assmus-Mattson theorem and do not admit $2$-transitive or $2$-homogeneous automorphism groups in general. By employing the theory of projective geometries and projective generalized Reed-Muller codes, we prove that they still hold $2$-designs. We also determine the parameters of these $2$-designs. This paper mainly confirms some recent conjectures of Ding and Li regarding Steiner systems and $2$-designs from a special type of ternary projective codes.