OpenRaiser/Intern-Atlas huggingface dataset:
EmbedMask: Embedding Coupling for One-stage Instance Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Current instance segmentation methods can be categorized into segmentation-based methods that segment first then do clustering, and proposal-based methods that detect first then predict masks for each instance proposal using repooling. In this work, we propose a one-stage method, named EmbedMask, that unifies both methods by taking advantages of them. Like proposal-based methods, EmbedMask builds on top of detection models making it strong in detection capability. Meanwhile, EmbedMask applies extra embedding modules to generate embeddings for pixels and proposals, where pixel embeddings are guided by proposal embeddings if they belong to the same instance. Through this embedding coupling process, pixels are assigned to the mask of the proposal if their embeddings are similar. The pixel-level clustering enables EmbedMask to generate high-resolution masks without missing details from repooling, and the existence of proposal embedding simplifies and strengthens the clustering procedure to achieve high speed with higher performance than segmentation-based methods. Without any bells and whistles, EmbedMask achieves comparable performance as Mask R-CNN, which is the representative two-stage method, and can produce more detailed masks at a higher speed. Code is available at github.com/yinghdb/EmbedMask.
On Computing the Hamiltonian Index of Graphs
Venue: arXiv cs.DS 2019
Year: 2019

The $r$-th iterated line graph $L^{r}(G)$ of a graph $G$ is defined by: (i) $L^{0}(G) = G$ and (ii) $L^{r}(G) = L(L^{(r- 1)}(G))$ for $r > 0$, where $L(G)$ denotes the line graph of $G$. The Hamiltonian Index $h(G)$ of $G$ is the smallest $r$ such that $L^{r}(G)$ has a Hamiltonian cycle. Checking if $h(G) = k$ is NP-hard for any fixed integer $k \geq 0$ even for subcubic graphs $G$. We study the parameterized complexity of this problem with the parameter treewidth, $tw(G)$, and show that we can find $h(G)$ in time $O*((1 + 2^{(ω+ 3)})^{tw(G)})$ where $ω$ is the matrix multiplication exponent and the $O*$ notation hides polynomial factors in input size. The NP-hard Eulerian Steiner Subgraph problem takes as input a graph $G$ and a specified subset $K$ of terminal vertices of $G$ and asks if $G$ has an Eulerian (that is: connected, and with all vertices of even degree.) subgraph $H$ containing all the terminals. A second result (and a key ingredient of our algorithm for finding $h(G)$) in this work is an algorithm which solves Eulerian Steiner Subgraph in $O*((1 + 2^{(ω+ 3)})^{tw(G)})$ time.
On stability of users equilibria in heterogeneous routing games
Venue: arXiv cs.GT 2019
Year: 2019

The asymptotic behaviour of deterministic logit dynamics in heterogeneous routing games is analyzed. It is proved that in directed multigraphs with parallel routes, and in series composition of such multigraphs, the dynamics admits a globally asymptotically stable fixed point. Moreover, the unique fixed point of the dynamics approaches the set of Wardrop equilibria, as the noise vanishes. The result relies on the fact that the dynamics of aggregate flows is monotone, and its Jacobian is strictly diagonally dominant by columns.
Safety and Robustness in Decision Making: Deep Bayesian Recurrent Neural Networks for Somatic Variant Calling in Cancer
Venue: arXiv cs.LG 2019
Year: 2019

The genomic profile underlying an individual tumor can be highly informative in the creation of a personalized cancer treatment strategy for a given patient; a practice known as precision oncology. This involves next generation sequencing of a tumor sample and the subsequent identification of genomic aberrations, such as somatic mutations, to provide potential candidates of targeted therapy. The identification of these aberrations from sequencing noise and germline variant background poses a classic classification-style problem. This has been previously broached with many different supervised machine learning methods, including deep-learning neural networks. However, these neural networks have thus far not been tailored to give any indication of confidence in the mutation call, meaning an oncologist could be targeting a mutation with a low probability of being true. To address this, we present here a deep bayesian recurrent neural network for cancer variant calling, which shows no degradation in performance compared to standard neural networks. This approach enables greater flexibility through different priors to avoid overfitting to a single dataset. We will be incorporating this approach into software for oncologists to obtain safe, robust, and statistically confident somatic mutation calls for precision oncology treatment choices.
AlgaeDICE: Policy Gradient from Arbitrary Experience
Venue: arXiv cs.LG 2019
Year: 2019

In many real-world applications of reinforcement learning (RL), interactions with the environment are limited due to cost or feasibility. This presents a challenge to traditional RL algorithms since the max-return objective involves an expectation over on-policy samples. We introduce a new formulation of max-return optimization that allows the problem to be re-expressed by an expectation over an arbitrary behavior-agnostic and off-policy data distribution. We first derive this result by considering a regularized version of the dual max-return objective before extending our findings to unregularized objectives through the use of a Lagrangian formulation of the linear programming characterization of Q-values. We show that, if auxiliary dual variables of the objective are optimized, then the gradient of the off-policy objective is exactly the on-policy policy gradient, without any use of importance weighting. In addition to revealing the appealing theoretical properties of this approach, we also show that it delivers good practical performance.
Expressiveness and Learning of Hidden Quantum Markov Models
Venue: arXiv cs.LG 2019
Year: 2019

Extending classical probabilistic reasoning using the quantum mechanical view of probability has been of recent interest, particularly in the development of hidden quantum Markov models (HQMMs) to model stochastic processes. However, there has been little progress in characterizing the expressiveness of such models and learning them from data. We tackle these problems by showing that HQMMs are a special subclass of the general class of observable operator models (OOMs) that do not suffer from the \emph{negative probability problem} by design. We also provide a feasible retraction-based learning algorithm for HQMMs using constrained gradient descent on the Stiefel manifold of model parameters. We demonstrate that this approach is faster and scales to larger models than previous learning algorithms.
Quantifying Urban Canopy Cover with Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Urban canopy cover is important to mitigate the impact of climate change. Yet, existing quantification of urban greenery is either manual and not scalable, or use traditional computer vision methods that are inaccurate. We train deep convolutional neural networks (DCNNs) on datasets used for self-driving cars to estimate urban greenery instead, and find that our semantic segmentation and direct end-to-end estimation method are more accurate and scalable, reducing mean absolute error of estimating the Green View Index (GVI) metric from 10.1% to 4.67%. With the revised DCNN methods, the Treepedia project was able to scale and analyze canopy cover in 22 cities internationally, sparking interest and action in public policy and research fields.
Dynamic Hilbert Maps: Real-Time Occupancy Predictions in Changing Environment
Venue: arXiv cs.RO 2019
Year: 2019

This paper addresses the problem of learning instantaneous occupancy levels of dynamic environments and predicting future occupancy levels. Due to the complexity of most real-world environments, such as urban streets or crowded areas, the efficient and robust incorporation of temporal dependencies into otherwise static occupancy models remains a challenge. We propose a method to capture the spatial uncertainty of moving objects and incorporate this uncertainty information into a continuous occupancy map represented in a rich high-dimensional feature space. Experiments performed using LIDAR data verified the real-time performance of the algorithm.
A Probabilistic Approach to Satisfiability of Propositional Logic Formulae
Venue: arXiv cs.AI 2019
Year: 2019

We propose a version of WalkSAT algorithm, named as BetaWalkSAT. This method uses probabilistic reasoning for biasing the starting state of the local search algorithm. Beta distribution is used to model the belief over boolean values of the literals. Our results suggest that, the proposed BetaWalkSAT algorithm can outperform other uninformed local search approaches for complex boolean satisfiability problems.
Assessing the best edit in perturbation-based iterative refinement algorithms to compute the median string
Venue: arXiv cs.DS 2019
Year: 2019

Strings are a natural representation of biological data such as DNA, RNA and protein sequences. The problem of finding a string that summarizes a set of sequences has direct application in relative compression algorithms for genome and proteome analysis, where reference sequences need to be chosen. Median strings have been used as representatives of a set of strings in different domains. However, several formulations of those problems are NP-Complete. Alternatively, heuristic approaches that iteratively refine an initial coarse solution by applying edit operations have been proposed. Recently, we investigated the selection of the optimal edit operations to speed up convergence without spoiling the quality of the approximated median string. We propose a novel algorithm that outperforms state of the art heuristic approximations to the median string in terms of convergence speed by estimating the effect of a perturbation in the minimization of the expressions that define the median strings. We present corpus of comparative experiments to validate these results.
Natural Alpha Embeddings
Venue: arXiv cs.LG 2019
Year: 2019

Learning an embedding for a large collection of items is a popular approach to overcome the computational limitations associated to one-hot encodings. The aim of item embedding is to learn a low dimensional space for the representations, able to capture with its geometry relevant features or relationships for the data at hand. This can be achieved for example by exploiting adjacencies among items in large sets of unlabelled data. In this paper we interpret in an Information Geometric framework the item embeddings obtained from conditional models. By exploiting the $α$-geometry of the exponential family, first introduced by Amari, we introduce a family of natural $α$-embeddings represented by vectors in the tangent space of the probability simplex, which includes as a special case standard approaches available in the literature. A typical example is given by word embeddings, commonly used in natural language processing, such as Word2Vec and GloVe. In our analysis, we show how the $α$-deformation parameter can impact on standard evaluation tasks.
Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data
Venue: arXiv cs.DS 2019
Year: 2019

Kernel density estimation is a simple and effective method that lies at the heart of many important machine learning applications. Unfortunately, kernel methods scale poorly for large, high dimensional datasets. Approximate kernel density estimation has a prohibitively high memory and computation cost, especially in the streaming setting. Recent sampling algorithms for high dimensional densities can reduce the computation cost but cannot operate online, while streaming algorithms cannot handle high dimensional datasets due to the curse of dimensionality. We propose RACE, an efficient sketching algorithm for kernel density estimation on high-dimensional streaming data. RACE compresses a set of N high dimensional vectors into a small array of integer counters. This array is sufficient to estimate the kernel density for a large class of kernels. Our sketch is practical to implement and comes with strong theoretical guarantees. We evaluate our method on real-world high-dimensional datasets and show that our sketch achieves 10x better compression compared to competing methods.
RoNGBa: A Robustly Optimized Natural Gradient Boosting Training Approach with Leaf Number Clipping
Venue: arXiv cs.LG 2019
Year: 2019

Natural gradient has been recently introduced to the field of boosting to enable the generic probabilistic predication capability. Natural gradient boosting shows promising performance improvements on small datasets due to better training dynamics, but it suffers from slow training speed overhead especially for large datasets. We present a replication study of NGBoost(Duan et al., 2019) training that carefully examines the impacts of key hyper-parameters under the circumstance of best-first decision tree learning. We find that with the regularization of leaf number clipping, the performance of NGBoost can be largely improved via a better choice of hyperparameters. Experiments show that our approach significantly beats the state-of-the-art performance on various kinds of datasets from the UCI Machine Learning Repository while still has up to 4.85x speed up compared with the original approach of NGBoost.
Learning to Predict Explainable Plots for Neural Story Generation
Venue: arXiv cs.CL 2019
Year: 2019

Story generation is an important natural language processing task that aims to generate coherent stories automatically. While the use of neural networks has proven effective in improving story generation, how to learn to generate an explainable high-level plot still remains a major challenge. In this work, we propose a latent variable model for neural story generation. The model treats an outline, which is a natural language sentence explainable to humans, as a latent variable to represent a high-level plot that bridges the input and output. We adopt an external summarization model to guide the latent variable model to learn how to generate outlines from training data. Experiments show that our approach achieves significant improvements over state-of-the-art methods in both automatic and human evaluations.
Robustness of Low-Complexity Massive MIMO Architectures Against Passive Eavesdropping
Venue: arXiv cs.IT 2019
Year: 2019

Invoking large transmit antenna arrays, massive MIMO wiretap settings are capable of suppressing passive eavesdroppers via narrow beamforming towards legitimate terminals. This implies that secrecy is obtained almost for free in these settings. We show that this property holds not only for fully digital MIMO architectures, but also in massive MIMO settings whose transmitters employ architectures with reduced complexity. The investigations consider two dominant approaches for complexity reduction, namely antenna selection and hybrid analog-digital precoding. We show that using either approach, the information leakage normalized by the achievable sum-rate vanishes as the transmit array size grows large. For both approaches, the decaying speed is determined. The results demonstrate that, as the transmit array size grows large, the normalized leakages obtained by antenna selection and hybrid analog-digital precoding converge to zero double-logarithmically and logarithmically, respectively. These analytic derivations are confirmed for various benchmark architectures through numerical investigations.
Effective Data Augmentation Approaches to End-to-End Task-Oriented Dialogue
Venue: arXiv cs.CL 2019
Year: 2019

The training of task-oriented dialogue systems is often confronted with the lack of annotated data. In contrast to previous work which augments training data through expensive crowd-sourcing efforts, we propose four different automatic approaches to data augmentation at both the word and sentence level for end-to-end task-oriented dialogue and conduct an empirical study on their impact. Experimental results on the CamRest676 and KVRET datasets demonstrate that each of the four data augmentation approaches is able to obtain a significant improvement over a strong baseline in terms of Success F1 score and that the ensemble of the four approaches achieves the state-of-the-art results in the two datasets. In-depth analyses further confirm that our methods adequately increase the diversity of user utterances, which enables the end-to-end model to learn features robustly.
EviDense: a Graph-based Method for Finding Unique High-impact Events with Succinct Keyword-based Descriptions
Venue: arXiv cs.SI 2019
Year: 2019

Despite the significant efforts made by the research community in recent years, automatically acquiring valuable information about high impact-events from social media remains challenging. We present EviDense, a graph-based approach for finding high-impact events (such as disaster events) in social media. One of the challenges we address in our work is to provide for each event a succinct keyword-based description, containing the most relevant information about it, such as what happened, the location, as well as its timeframe. We evaluate our approach on a large collection of tweets posted over a period of 19 months, using a crowdsourcing platform. Our evaluation shows that our method outperforms state-of-the-art approaches for the same problem, in terms of having higher precision, lower number of duplicates, and presenting a keyword-based description that is succinct and informative. We further improve the results of our algorithm by incorporating news from mainstream media. A preliminary version of this work was presented as a 4-pages short paper at ICWSM 2018.
Is perturbation an effective restart strategy?
Venue: arXiv cs.NE 2019
Year: 2019

Premature convergence can be detrimental to the performance of search methods, which is why many search algorithms include restart strategies to deal with it. While it is common to perturb the incumbent solution with diversification steps of various sizes with the hope that the search method will find a new basin of attraction leading to a better local optimum, it is usually not clear how big the perturbation step should be. We introduce a new property of fitness landscapes termed "Neighbours with Similar Fitness" and we demonstrate that the effectiveness of a restart strategy depends on this property.
Tensor Recovery from Noisy and Multi-Level Quantized Measurements
Venue: arXiv cs.LG 2019
Year: 2019

Higher-order tensors can represent scores in a rating system, frames in a video, and images of the same subject. In practice, the measurements are often highly quantized due to the sampling strategies or the quality of devices. Existing works on tensor recovery have focused on data losses and random noises. Only a few works consider tensor recovery from quantized measurements but are restricted to binary measurements. This paper, for the first time, addresses the problem of tensor recovery from multi-level quantized measurements. Leveraging the low-rank property of the tensor, this paper proposes a nonconvex optimization problem for tensor recovery. We provide a theoretical upper bound of the recovery error, which diminishes to zero when the sizes of dimensions increase to infinity. Our error bound significantly improves over the existing results in one-bit tensor recovery and quantized matrix recovery. A tensor-based alternating proximal gradient descent algorithm with a convergence guarantee is proposed to solve the nonconvex problem. Our recovery method can handle data losses and do not need the information of the quantization rule. The method is validated on synthetic data, image datasets, and music recommender datasets.
A Novel Hybrid Scheme Using Genetic Algorithms and Deep Learning for the Reconstruction of Portuguese Tile Panels
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a novel scheme, based on a unique combination of genetic algorithms (GAs) and deep learning (DL), for the automatic reconstruction of Portuguese tile panels, a challenging real-world variant of the jigsaw puzzle problem (JPP) with important national heritage implications. Specifically, we introduce an enhanced GA-based puzzle solver, whose integration with a novel DL-based compatibility measure (DLCM) yields state-of-the-art performance, regarding the above application. Current compatibility measures consider typically (the chromatic information of) edge pixels (between adjacent tiles), and help achieve high accuracy for the synthetic JPP variant. However, such measures exhibit rather poor performance when applied to the Portuguese tile panels, which are susceptible to various real-world effects, e.g., monochromatic panels, non-squared tiles, edge degradation, etc. To overcome such difficulties, we have developed a novel DLCM to extract high-level texture/color statistics from the entire tile information. Integrating this measure with our enhanced GA-based puzzle solver, we have demonstrated, for the first time, how to deal most effectively with large-scale real-world problems, such as the Portuguese tile problem. Specifically, we have achieved 82% accuracy for the reconstruction of Portuguese tile panels with unknown piece rotation and puzzle dimension (compared to merely 3.5% average accuracy achieved by the best method known for solving this problem variant). The proposed method outperforms even human experts in several cases, correcting their mistakes in the manual tile assembly.
Insights from BB-MAS -- A Large Dataset for Typing, Gait and Swipes of the Same Person on Desktop, Tablet and Phone
Venue: arXiv cs.HC 2019
Year: 2019

Behavioral biometrics are key components in the landscape of research in continuous and active user authentication. However, there is a lack of large datasets with multiple activities, such as typing, gait and swipe performed by the same person. Furthermore, large datasets with multiple activities performed on multiple devices by the same person are non-existent. The difficulties of procuring devices, participants, designing protocol, secure storage and on-field hindrances may have contributed to this scarcity. The availability of such a dataset is crucial to forward the research in behavioral biometrics as usage of multiple devices by a person is common nowadays. Through this paper, we share our dataset, the details of its collection, features for each modality and our findings of how keystroke features vary across devices. We have collected data from 117 subjects for typing (both fixed and free text), gait (walking, upstairs and downstairs) and touch on Desktop, Tablet and Phone. The dataset consists a total of about: 3.5 million keystroke events; 57.1 million data-points for accelerometer and gyroscope each; 1.7 million data-points for swipes; and enables future research to explore previously unexplored directions in inter-device and inter-modality biometrics. Our analysis on keystrokes reveals that in most cases, keyhold times are smaller but inter-key latencies are larger, on hand-held devices when compared to desktop. We also present; detailed comparison with related datasets; possible research directions with the dataset; and lessons learnt from the data collection.