OpenRaiser/Intern-Atlas huggingface dataset:
Shape Robust Text Detection with Progressive Scale Expansion Network
Venue: arXiv cs.CV 2018
Year: 2018

The challenges of shape robust text detection lie in two aspects: 1) most existing quadrangular bounding box based detectors are difficult to locate texts with arbitrary shapes, which are hard to be enclosed perfectly in a rectangle; 2) most pixel-wise segmentation-based detectors may not separate the text instances that are very close to each other. To address these problems, we propose a novel Progressive Scale Expansion Network (PSENet), designed as a segmentation-based detector with multiple predictions for each text instance. These predictions correspond to different `kernels' produced by shrinking the original text instance into various scales. Consequently, the final detection can be conducted through our progressive scale expansion algorithm which gradually expands the kernels with minimal scales to the text instances with maximal and complete shapes. Due to the fact that there are large geometrical margins among these minimal kernels, our method is effective to distinguish the adjacent text instances and is robust to arbitrary shapes. The state-of-the-art results on ICDAR 2015 and ICDAR 2017 MLT benchmarks further confirm the great effectiveness of PSENet. Notably, PSENet outperforms the previous best record by absolute 6.37\% on the curve text dataset SCUT-CTW1500. Code will be available in https://github.com/whai362/PSENet.
On the Effect of Inter-observer Variability for a Reliable Estimation of Uncertainty of Medical Image Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Uncertainty estimation methods are expected to improve the understanding and quality of computer-assisted methods used in medical applications (e.g., neurosurgical interventions, radiotherapy planning), where automated medical image segmentation is crucial. In supervised machine learning, a common practice to generate ground truth label data is to merge observer annotations. However, as many medical image tasks show a high inter-observer variability resulting from factors such as image quality, different levels of user expertise and domain knowledge, little is known as to how inter-observer variability and commonly used fusion methods affect the estimation of uncertainty of automated image segmentation. In this paper we analyze the effect of common image label fusion techniques on uncertainty estimation, and propose to learn the uncertainty among observers. The results highlight the negative effect of fusion methods applied in deep learning, to obtain reliable estimates of segmentation uncertainty. Additionally, we show that the learned observers' uncertainty can be combined with current standard Monte Carlo dropout Bayesian neural networks to characterize uncertainty of model's parameters.
Generative Adversarial Networks for Realistic Synthesis of Hyperspectral Samples
Venue: arXiv cs.NE 2018
Year: 2018

This work addresses the scarcity of annotated hyperspectral data required to train deep neural networks. Especially, we investigate generative adversarial networks and their application to the synthesis of consistent labeled spectra. By training such networks on public datasets, we show that these models are not only able to capture the underlying distribution, but also to generate genuine-looking and physically plausible spectra. Moreover, we experimentally validate that the synthetic samples can be used as an effective data augmentation strategy. We validate our approach on several public hyper-spectral datasets using a variety of deep classifiers.
A Simple NLP-based Approach to Support Onboarding and Retention in Open Source Communities
Venue: arXiv cs.SE 2018
Year: 2018

Successful open source communities are constantly looking for new members and helping them become active developers. A common approach for developer onboarding in open source projects is to let newcomers focus on relevant yet easy-to-solve issues to familiarize themselves with the code and the community. The goal of this research is twofold. First, we aim at automatically identifying issues that newcomers can resolve by analyzing the history of resolved issues by simply using the title and description of issues. Second, we aim at automatically identifying issues, that can be resolved by newcomers who later become active developers. We mined the issue trackers of three large open source projects and extracted natural language features from the title and description of resolved issues. In a series of experiments, we optimized and compared the accuracy of four supervised classifiers to address our research goals. Random Forest, achieved up to 91% precision (F1-score 72%) towards the first goal while for the second goal, Decision Tree achieved a precision of 92% (F1-score 91%). A qualitative evaluation gave insights on what information in the issue description is helpful for newcomers. Our approach can be used to automatically identify, label, and recommend issues for newcomers in open source software projects based only on the text of the issues.
Fast Approximate Counting and Leader Election in Populations
Venue: arXiv cs.DC 2018
Year: 2018

We study the problems of leader election and population size counting for population protocols: networks of finite-state anonymous agents that interact randomly under a uniform random scheduler. We show a protocol for leader election that terminates in $O(\log_m(n) \cdot \log_2 n)$ parallel time, where $m$ is a parameter, using $O(\max\{m,\log n\})$ states. By adjusting the parameter $m$ between a constant and $n$, we obtain a single leader election protocol whose time and space can be smoothly traded off between $O(\log^2 n)$ to $O(\log n)$ time and $O(\log n)$ to $O(n)$ states. Finally, we give a protocol which provides an upper bound $\hat{n}$ of the size $n$ of the population, where $\hat{n}$ is at most $n^a$ for some $a>1$. This protocol assumes the existence of a unique leader in the population and stabilizes in $Θ{(\log{n})}$ parallel time, using constant number of states in every node, except the unique leader which is required to use $Θ{(\log^2{n})}$ states.
Analyzing Traffic Delay at Unmanaged Intersections
Venue: arXiv cs.MA 2018
Year: 2018

At an unmanaged intersection, it is important to understand how much traffic delay may be caused as a result of microscopic vehicle interactions. Conventional traffic simulations that explicitly track these interactions are time-consuming. Prior work introduced an analytical traffic model for unmanaged intersections. The traffic delay at the intersection is modeled as an event-driven stochastic process, whose dynamics encode microscopic vehicle interactions. This paper studies the traffic delay in a two-lane intersection using the model. We perform rigorous analyses concerning the distribution of traffic delay under different scenarios. We then discuss the relationships between traffic delay and multiple factors such as traffic flow density, unevenness of traffic flows, temporal gaps between two consecutive vehicles, and the passing order.
Locally Recoverable codes from algebraic curves with separated variables
Venue: arXiv cs.IT 2018
Year: 2018

A Locally Recoverable code is an error-correcting code such that any erasure in a single coordinate of a codeword can be recovered from a small subset of other coordinates. We study Locally Recoverable Algebraic Geometry codes arising from certain curves defined by equations with separated variables. The recovery of erasures is obtained by means of Lagrangian interpolation in general, and simply by one addition in some particular cases.
Alignment-free sequence comparison using absent words
Venue: arXiv cs.DS 2018
Year: 2018

Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not occur in the sequence. An absent word is {\em minimal} if all its proper factors occur in the sequence. Here we present the first linear-time and linear-space algorithm to compare two sequences by considering {\em all} their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences. We also present an algorithm that, given a word $x$ of length $n$, computes the largest integer for which all factors of $x$ of that length occur in some minimal absent word of $x$ in time and space $\cO(n)$. Finally, we show that the known asymptotic upper bound on the number of minimal absent words of a word is tight.
Anchored in a Data Storm: How Anchoring Bias Can Affect User Strategy, Confidence, and Decisions in Visual Analytics
Venue: arXiv cs.HC 2018
Year: 2018

Cognitive biases have been shown to lead to faulty decision-making. Recent research has demonstrated that the effect of cognitive biases, anchoring bias in particular, transfers to information visualization and visual analytics. However, it is still unclear how users of visual interfaces can be anchored and the impact of anchoring on user performance and decision-making process. To investigate, we performed two rounds of between-subjects, in-laboratory experiments with 94 participants to analyze the effect of visual anchors and strategy cues in decision-making with a visual analytic system that employs coordinated multiple view design. The decision-making task is identifying misinformation from Twitter news accounts. Participants were randomly assigned one of three treatment groups (including control) in which participant training processes were modified. Our findings reveal that strategy cues and visual anchors (scenario videos) can significantly affect user activity, speed, confidence, and, under certain circumstances, accuracy. We discuss the implications of our experiment results on training users how to use a newly developed visual interface. We call for more careful consideration into how visualization designers and researchers train users to avoid unintentionally anchoring users and thus affecting the end result.
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
Venue: arXiv cs.CC 2018
Year: 2018

We develop a new framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with real-world networks) while still guaranteeing approximation ratios. The idea is to $\textit{edit}$ a given graph via vertex- or edge-deletions to put the graph into an algorithmically tractable class, apply known approximation algorithms for that class, and then $\textit{lift}$ the solution to apply to the original graph. We give a general characterization of when an optimization problem is amenable to this approach, and show that it includes many well-studied graph problems, such as Independent Set, Vertex Cover, Feedback Vertex Set, Minimum Maximal Matching, Chromatic Number, ($\ell$-)Dominating Set, Edge ($\ell$-)Dominating Set, and Connected Dominating Set. To enable this framework, we develop new editing algorithms that find the approximately-fewest edits required to bring a given graph into one of several important graph classes (in some cases, also approximating the target parameter of the family). For bounded degeneracy, we obtain a bicriteria $(4,4)$-approximation which also extends to a smoother bicriteria trade-off. For bounded treewidth, we obtain a bicriteria $(O(\log^{1.5} n), O(\sqrt{\log w}))$-approximation, and for bounded pathwidth, we obtain a bicriteria $(O(\log^{1.5} n), O(\sqrt{\log w} \cdot \log n))$-approximation. For treedepth $2$ (also related to bounded expansion), we obtain a $4$-approximation. We also prove complementary hardness-of-approximation results assuming $\mathrm{P} \neq \mathrm{NP}$: in particular, these problems are all log-factor inapproximable, except the last which is not approximable below some constant factor ($2$ assuming UGC).
Unbiased Estimation of the Value of an Optimized Policy
Venue: arXiv cs.LG 2018
Year: 2018

Randomized trials, also known as A/B tests, are used to select between two policies: a control and a treatment. Given a corresponding set of features, we can ideally learn an optimized policy P that maps the A/B test data features to action space and optimizes reward. However, although A/B testing provides an unbiased estimator for the value of deploying B (i.e., switching from policy A to B), direct application of those samples to learn the the optimized policy P generally does not provide an unbiased estimator of the value of P as the samples were observed when constructing P. In situations where the cost and risks associated of deploying a policy are high, such an unbiased estimator is highly desirable. We present a procedure for learning optimized policies and getting unbiased estimates for the value of deploying them. We wrap any policy learning procedure with a bagging process and obtain out-of-bag policy inclusion decisions for each sample. We then prove that inverse-propensity-weighting effect estimator is unbiased when applied to the optimized subset. Likewise, we apply the same idea to obtain out-of-bag unbiased per-sample value estimate of the measurement that is independent of the randomized treatment, and use these estimates to build an unbiased doubly-robust effect estimator. Lastly, we empirically shown that even when the average treatment effect is negative we can find a positive optimized policy.
Is preprocessing of text really worth your time for online comment classification?
Venue: arXiv cs.CL 2018
Year: 2018

A large proportion of online comments present on public domains are constructive, however a significant proportion are toxic in nature. The comments contain lot of typos which increases the number of features manifold, making the ML model difficult to train. Considering the fact that the data scientists spend approximately 80% of their time in collecting, cleaning and organizing their data [1], we explored how much effort should we invest in the preprocessing (transformation) of raw comments before feeding it to the state-of-the-art classification models. With the help of four models on Jigsaw toxic comment classification data, we demonstrated that the training of model without any transformation produce relatively decent model. Applying even basic transformations, in some cases, lead to worse performance and should be applied with caution.
Color Sails: Discrete-Continuous Palettes for Deep Color Exploration
Venue: arXiv cs.GR 2018
Year: 2018

We present color sails, a discrete-continuous color gamut representation that extends the color gradient analogy to three dimensions and allows interactive control of the color blending behavior. Our representation models a wide variety of color distributions in a compact manner, and lends itself to applications such as color exploration for graphic design, illustration and similar fields. We propose a Neural Network that can fit a color sail to any image. Then, the user can adjust color sail parameters to change the base colors, their blending behavior and the number of colors, exploring a wide range of options for the original design. In addition, we propose a Deep Learning model that learns to automatically segment an image into color-compatible alpha masks, each equipped with its own color sail. This allows targeted color exploration by either editing their corresponding color sails or using standard software packages. Our model is trained on a custom diverse dataset of art and design. We provide both quantitative evaluations, and a user study, demonstrating the effectiveness of color sail interaction. Interactive demos are available at www.colorsails.com.
A Deep Neural Network Surrogate for High-Dimensional Random Partial Differential Equations
Venue: arXiv cs.LG 2018
Year: 2018

Developing efficient numerical algorithms for the solution of high dimensional random Partial Differential Equations (PDEs) has been a challenging task due to the well-known curse of dimensionality. We present a new solution framework for these problems based on a deep learning approach. Specifically, the random PDE is approximated by a feed-forward fully-connected deep residual network, with either strong or weak enforcement of initial and boundary constraints. The framework is mesh-free, and can handle irregular computational domains. Parameters of the approximating deep neural network are determined iteratively using variants of the Stochastic Gradient Descent (SGD) algorithm. The satisfactory accuracy of the proposed frameworks is numerically demonstrated on diffusion and heat conduction problems, in comparison with the converged Monte Carlo-based finite element results.
Domain Adaptive Generation of Aircraft on Satellite Imagery via Simulated and Unsupervised Learning
Venue: arXiv cs.CV 2018
Year: 2018

Object detection and classification for aircraft are the most important tasks in the satellite image analysis. The success of modern detection and classification methods has been based on machine learning and deep learning. One of the key requirements for those learning processes is huge data to train. However, there is an insufficient portion of aircraft since the targets are on military action and oper- ation. Considering the characteristics of satellite imagery, this paper attempts to provide a framework of the simulated and unsupervised methodology without any additional su- pervision or physical assumptions. Finally, the qualitative and quantitative analysis revealed a potential to replenish insufficient data for machine learning platform for satellite image analysis.
Formalization of Lerch's Theorem using HOL Light
Venue: arXiv cs.LO 2018
Year: 2018

The Laplace transform is an algebraic method that is widely used for analyzing physical systems by either solving the differential equations modeling their dynamics or by evaluating their transfer function. The dynamics of the given system are firstly modeled using differential equations and then Laplace transform is applied to convert these differential equations to their equivalent algebraic equations. These equations can further be simplified to either obtain the transfer function of the system or to find out the solution of the differential equations in frequency domain. Next, the uniqueness of the Laplace transform provides the solution of these differential equations in the time domain. The traditional Laplace transform based analysis techniques, i.e., paper-and-pencil proofs and computer simulation methods are error-prone due to their inherent limitations and thus are not suitable for the analysis of the systems. Higher-order-logic theorem proving can overcome these limitations of these techniques and can ascertain accurate analysis of the systems. In this paper, we extend our higher-order logic formalization of the Laplace transform, which includes the formal definition of the Laplace transform and verification of its various classical properties. One of the main contributions of the paper is the formalization of Lerch's theorem, which describes the uniqueness of the Laplace transform and thus plays a vital role in solving linear differential equations in the frequency domain. For illustration, we present the formal analysis of a $4$-$π$ soft error crosstalk model, which is widely used in nanometer technologies, such as, Integrated Circuits (ICs).
The Saturated Subpaths Decomposition in Z 2 : a short note on generalized Tangential Cover
Venue: arXiv cs.CG 2018
Year: 2018

In this short note, we generalized the Tangential Cover used in Digital Geometry in order to use very general geometric predicates. We present the required notions of saturated $α$-paths of a digital curve as well as conservative predicates which indeed cover nearly all geometric digital primitives published so far. The goal of this note is to prove that under a very general situation, the size of the Tangential Cover is linear with the number of points of the input curve. The computation complexity of the Tangential Cover depends on the complexity of incremental recognition of geometric predicates. Moreover, in the discussion, we show that our approach does not rely on connectivity of points as it might be though first.
Compressed Communication Complexity of Longest Common Prefixes
Venue: arXiv cs.DS 2018
Year: 2018

We consider the communication complexity of fundamental longest common prefix (Lcp) problems. In the simplest version, two parties, Alice and Bob, each hold a string, $A$ and $B$, and we want to determine the length of their longest common prefix $l=\text{Lcp}(A,B)$ using as few rounds and bits of communication as possible. We show that if the longest common prefix of $A$ and $B$ is compressible, then we can significantly reduce the number of rounds compared to the optimal uncompressed protocol, while achieving the same (or fewer) bits of communication. Namely, if the longest common prefix has an LZ77 parse of $z$ phrases, only $O(\lg z)$ rounds and $O(\lg \ell)$ total communication is necessary. We extend the result to the natural case when Bob holds a set of strings $B_1, \ldots, B_k$, and the goal is to find the length of the maximal longest prefix shared by $A$ and any of $B_1, \ldots, B_k$. Here, we give a protocol with $O(\log z)$ rounds and $O(\lg z \lg k + \lg \ell)$ total communication. We present our result in the public-coin model of computation but by a standard technique our results generalize to the private-coin model. Furthermore, if we view the input strings as integers the problems are the greater-than problem and the predecessor problem.
Several recent developments in estimation and robust control of quantum systems
Venue: arXiv cs.SY 2018
Year: 2018

This paper summarizes several recent developments in the area of estimation and robust control of quantum systems and outlines several directions for future research. Quantum state tomography via linear regression estimation and adaptive quantum state estimation are introduced and a Hamiltonian identification algorithm is outlined. Two quantum robust control approaches including sliding mode control and sampling-based learning control are illustrated.
Wave-U-Net: A Multi-Scale Neural Network for End-to-End Audio Source Separation
Venue: arXiv cs.SD 2018
Year: 2018

Models for audio source separation usually operate on the magnitude spectrum, which ignores phase information and makes separation performance dependant on hyper-parameters for the spectral front-end. Therefore, we investigate end-to-end source separation in the time-domain, which allows modelling phase information and avoids fixed spectral transformations. Due to high sampling rates for audio, employing a long temporal input context on the sample level is difficult, but required for high quality separation results because of long-range temporal correlations. In this context, we propose the Wave-U-Net, an adaptation of the U-Net to the one-dimensional time domain, which repeatedly resamples feature maps to compute and combine features at different time scales. We introduce further architectural improvements, including an output layer that enforces source additivity, an upsampling technique and a context-aware prediction framework to reduce output artifacts. Experiments for singing voice separation indicate that our architecture yields a performance comparable to a state-of-the-art spectrogram-based U-Net architecture, given the same data. Finally, we reveal a problem with outliers in the currently used SDR evaluation metrics and suggest reporting rank-based statistics to alleviate this problem.