OpenRaiser/Intern-Atlas huggingface dataset:
IntelligentCrowd: Mobile Crowdsensing via Multi-Agent Reinforcement Learning
Venue: arXiv cs.MA 2020
Year: 2020

The prosperity of smart mobile devices has made mobile crowdsensing (MCS) a promising paradigm for completing complex sensing and computation tasks. In the past, great efforts have been made on the design of incentive mechanisms and task allocation strategies from MCS platform's perspective to motivate mobile users' participation. However, in practice, MCS participants face many uncertainties coming from their sensing environment as well as other participants' strategies, and how do they interact with each other and make sensing decisions is not well understood. In this paper, we take MCS participants' perspective to derive an online sensing policy to maximize their payoffs via MCS participation. Specifically, we model the interactions of mobile users and sensing environments as a multi-agent Markov decision process. Each participant cannot observe others' decisions, but needs to decide her effort level in sensing tasks only based on local information, e.g., its own record of sensed signals' quality. To cope with the stochastic sensing environment, we develop an intelligent crowdsensing algorithm IntelligentCrowd by leveraging the power of multi-agent reinforcement learning (MARL). Our algorithm leads to the optimal sensing policy for each user to maximize the expected payoff against stochastic sensing environments, and can be implemented at individual participant's level in a distributed fashion. Numerical simulations demonstrate that IntelligentCrowd significantly improves users' payoffs in sequential MCS tasks under various sensing dynamics.
Collapsing Superstring Conjecture
Venue: arXiv cs.DS 2020
Year: 2020

In the Shortest Common Superstring (SCS) problem, one is given a collection of strings, and needs to find a shortest string containing each of them as a substring. SCS admits $2\frac{11}{23}$-approximation in polynomial time (Mucha, SODA'13). While this algorithm and its analysis are technically involved, the 30 years old Greedy Conjecture claims that the trivial and efficient Greedy Algorithm gives a 2-approximation for SCS. We develop a graph-theoretic framework for studying approximation algorithms for SCS. The framework is reminiscent of the classical 2-approximation for Traveling Salesman: take two copies of an optimal solution, apply a trivial edge-collapsing procedure, and get an approximate solution. In this framework, we observe two surprising properties of SCS solutions, and we conjecture that they hold for all input instances. The first conjecture, that we call Collapsing Superstring conjecture, claims that there is an elementary way to transform any solution repeated twice into the same graph $G$. This conjecture would give an elementary 2-approximate algorithm for SCS. The second conjecture claims that not only the resulting graph $G$ is the same for all solutions, but that $G$ can be computed by an elementary greedy procedure called Greedy Hierarchical Algorithm. While the second conjecture clearly implies the first one, perhaps surprisingly we prove their equivalence. We support these equivalent conjectures by giving a proof for the special case where all input strings have length at most 3. We prove that the standard Greedy Conjecture implies Greedy Hierarchical Conjecture, while the latter is sufficient for an efficient greedy 2-approximate approximation of SCS. Except for its (conjectured) good approximation ratio, the Greedy Hierarchical Algorithm provably finds a 3.5-approximation.
Context-Aware Attention for Understanding Twitter Abuse
Venue: arXiv cs.CL 2020
Year: 2020

The original goal of any social media platform is to facilitate users to indulge in healthy and meaningful conversations. But more often than not, it has been found that it becomes an avenue for wanton attacks. We want to alleviate this issue and hence we try to provide a detailed analysis of how abusive behavior can be monitored in Twitter. The complexity of the natural language constructs makes this task challenging. We show how applying contextual attention to Long Short Term Memory networks help us give near state of art results on multiple benchmarks abuse detection data sets from Twitter.
Language Identification with Deep Bottleneck Features
Venue: arXiv cs.CL 2020
Year: 2020

In this paper we proposed an end-to-end short utterances speech language identification(SLD) approach based on a Long Short Term Memory (LSTM) neural network which is special suitable for SLD application in intelligent vehicles. Features used for LSTM learning are generated by a transfer learning method. Bottle-neck features of a deep neural network (DNN) which are trained for mandarin acoustic-phonetic classification are used for LSTM training. In order to improve the SLD accuracy of short utterances a phase vocoder based time-scale modification(TSM) method is used to reduce and increase speech rated of the test utterance. By splicing the normal, speech rate reduced and increased utterances, we can extend length of test utterances so as to improved improved the performance of the SLD system. The experimental results on AP17-OLR database shows that the proposed methods can improve the performance of SLD, especially on short utterance with 1s and 3s durations.
Collaborative Learning for Extremely Low Bit Asymmetric Hashing
Venue: arXiv cs.IR 2020
Year: 2020

Hashing techniques are in great demand for a wide range of real-world applications such as image retrieval and network compression. Nevertheless, existing approaches could hardly guarantee a satisfactory performance with the extremely low-bit (e.g., 4-bit) hash codes due to the severe information loss and the shrink of the discrete solution space. In this paper, we propose a novel \textit{Collaborative Learning} strategy that is tailored for generating high-quality low-bit hash codes. The core idea is to jointly distill bit-specific and informative representations for a group of pre-defined code lengths. The learning of short hash codes among the group can benefit from the manifold shared with other long codes, where multiple views from different hash codes provide the supplementary guidance and regularization, making the convergence faster and more stable. To achieve that, an asymmetric hashing framework with two variants of multi-head embedding structures is derived, termed as Multi-head Asymmetric Hashing (MAH), leading to great efficiency of training and querying. Extensive experiments on three benchmark datasets have been conducted to verify the superiority of the proposed MAH, and have shown that the 8-bit hash codes generated by MAH achieve $94.3\%$ of the MAP (Mean Average Precision (MAP)) score on the CIFAR-10 dataset, which significantly surpasses the performance of the 48-bit codes by the state-of-the-arts in image retrieval tasks.
A Method to Assess and Argue for Practical Significance in Software Engineering
Venue: arXiv cs.SE 2020
Year: 2020

A key goal of empirical research in software engineering is to assess practical significance, which answers whether the observed effects of some compared treatments show a relevant difference in practice in realistic scenarios. Even though plenty of standard techniques exist to assess statistical significance, connecting it to practical significance is not straightforward or routinely done; indeed, only a few empirical studies in software engineering assess practical significance in a principled and systematic way. In this paper, we argue that Bayesian data analysis provides suitable tools to assess practical significance rigorously. We demonstrate our claims in a case study comparing different test techniques. The case study's data was previously analyzed (Afzal et al., 2015) using standard techniques focusing on statistical significance. Here, we build a multilevel model of the same data, which we fit and validate using Bayesian techniques. Our method is to apply cumulative prospect theory on top of the statistical model to quantitatively connect our statistical analysis output to a practically meaningful context. This is then the basis both for assessing and arguing for practical significance. Our study demonstrates that Bayesian analysis provides a technically rigorous yet practical framework for empirical software engineering. A substantial side effect is that any uncertainty in the underlying data will be propagated through the statistical model, and its effects on practical significance are made clear. Thus, in combination with cumulative prospect theory, Bayesian analysis supports seamlessly assessing practical significance in an empirical software engineering context, thus potentially clarifying and extending the relevance of research for practitioners.
On Rational Entailment for Propositional Typicality Logic
Venue: arXiv cs.AI 2020
Year: 2020

Propositional Typicality Logic (PTL) is a recently proposed logic, obtained by enriching classical propositional logic with a typicality operator capturing the most typical (alias normal or conventional) situations in which a given sentence holds. The semantics of PTL is in terms of ranked models as studied in the well-known KLM approach to preferential reasoning and therefore KLM-style rational consequence relations can be embedded in PTL. In spite of the non-monotonic features introduced by the semantics adopted for the typicality operator, the obvious Tarskian definition of entailment for PTL remains monotonic and is therefore not appropriate in many contexts. Our first important result is an impossibility theorem showing that a set of proposed postulates that at first all seem appropriate for a notion of entailment with regard to typicality cannot be satisfied simultaneously. Closer inspection reveals that this result is best interpreted as an argument for advocating the development of more than one type of PTL entailment. In the spirit of this interpretation, we investigate three different (semantic) versions of entailment for PTL, each one based on the definition of rational closure as introduced by Lehmann and Magidor for KLM-style conditionals, and constructed using different notions of minimality.
Performance of a Link in a Field of Vehicular Interferers with Hardcore Headway Distance
Venue: arXiv cs.NI 2020
Year: 2020

The Poisson point process (PPP) is not always a realistic model for the locations of vehicles along a road, because it does not account for the safety distance a driver maintains from the vehicle ahead. In this paper, we model the inter-vehicle distance equal to the sum of a constant hardcore distance and a random distance following the exponential distribution. Unfortunately, the probability generating functional of this point process is unknown. To approximate the Laplace transform of interference at the origin, we devise simple approximations for the variance and skewness of interference, and we select suitable probability functions to model the interference distribution. When the coefficient-of-variation and the skewness of interference distribution are high, the PPP (of equal intensity) approximation of the outage probability becomes loose in the upper tail. Relevant scenarios are associated with urban microcells and highway macrocells with a low density of vehicles. The predictions of PPP deteriorate with a multi-antenna maximum ratio combining receiver and temporal indicators related to the performance of retransmission schemes. Our approximations generate good predictions in all considered cases.
Algebraic number fields and the LLL algorithm
Venue: arXiv cs.SC 2020
Year: 2020

In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let $K$ be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in $K$ in terms of the size of the input and the parameters of $K$. We include some earlier results about these, but we go further than them, e.g. we also analyze some $\mathbb{R}$-specific operations in $K$ like less-than comparison. In the second half of the paper, we analyze two algorithms: the Bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the LLL algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from $\mathbb{Z}^n$ to $K^n$, and give a polynomial upper bound on the running time when the computations in $K$ are performed exactly (as opposed to floating-point approximations).
Brain2Object: Printing Your Mind from Brain Signals with Spatial Correlation Embedding
Venue: arXiv cs.HC 2020
Year: 2020

Electroencephalography (EEG) signals are known to manifest differential patterns when individuals visually concentrate on different objects. In this work, we present an end-to-end digital fabrication system, Brain2Object, to print the 3D object that an individual is observing by decoding visually-evoked brain signals. We propose a unified training framework that combines multi-class Common Spatial Pattern and Convolutional Neural Networks to support the backend computation. We learn the dynamical graph representations of brain signals to accurately capture the structural information among EEG channels. A user-friendly interface is developed as the system front end. Brain2Object presents a streamlined end-to-end workflow that can serve as a template for deeper integration of BCI technologies to assist with our routine activities. The proposed system is evaluated extensively using offline experiments and through an online demonstrator. The experimental results show that our approach can achieve the recognition accuracy of 92.58% on a benchmark dataset and 75.23% on a locally collected dataset. Moreover, our method consistently outperforms a wide range of baseline and state-of-the-art approaches. The proof-of-concept corroborates the practicality of our approach and illustrates the ease with which such a system could be deployed.
Control of uniflagellar soft robots at low Reynolds number using buckling instability
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we analyze the inverse dynamics and control of a bacteria-inspired uniflagellar robot in a fluid medium at low Reynolds number. Inspired by the mechanism behind the locomotion of flagellated bacteria, we consider a robot comprised of a flagellum -- a flexible helical filament -- attached to a spherical head. The flagellum rotates about the head at a controlled angular velocity and generates a propulsive force that moves the robot forward. When the angular velocity exceeds a threshold value, the hydrodynamic force exerted by the fluid can cause the soft flagellum to buckle, characterized by a dramatic change in shape. In this computational study, a fluid-structure interaction model that combines Discrete Elastic Rods (DER) algorithm with Lighthill's Slender Body Theory (LSBT) is employed to simulate the locomotion and deformation of the robot. We demonstrate that the robot can follow a prescribed path in three dimensional space by exploiting buckling of the flagellum. The control scheme involves only a single (binary) scalar input -- the angular velocity of the flagellum. By triggering the buckling instability at the right moment, the robot can follow an arbitrary path in three dimensional space. We also show that the complexity of the dynamics of the helical filament can be captured using a deep neural network, from which we identify the input-output functional relationship between the control inputs and the trajectory of the robot. Furthermore, our study underscores the potential role of buckling in the locomotion of natural bacteria.
Fast and Robust Small Infrared Target Detection Using Absolute Directional Mean Difference Algorithm
Venue: arXiv cs.CV 2020
Year: 2020

Infrared small target detection in an infrared search and track (IRST) system is a challenging task. This situation becomes more complicated when high gray-intensity structural backgrounds appear in the field of view (FoV) of the infrared seeker. While the majority of the infrared small target detection algorithms neglect directional information, in this paper, a directional approach is presented to suppress structural backgrounds and develop a more effective detection algorithm. To this end, a similar concept to the average absolute gray difference (AAGD) is utilized to construct a novel directional small target detection algorithm called absolute directional mean difference (ADMD). Also, an efficient implementation procedure is presented for the proposed algorithm. The proposed algorithm effectively enhances the target area and eliminates background clutter. Simulation results on real infrared images prove the significant effectiveness of the proposed algorithm.
Design by adaptive sampling
Venue: arXiv cs.LG 2020
Year: 2020

We present a probabilistic modeling framework and adaptive sampling algorithm wherein unsupervised generative models are combined with black box predictive models to tackle the problem of input design. In input design, one is given one or more stochastic "oracle" predictive functions, each of which maps from the input design space (e.g. DNA sequences or images) to a distribution over a property of interest (e.g. protein fluorescence or image content). Given such stochastic oracles, the problem is to find an input that is expected to maximize one or more properties, or to achieve a specified value of one or more properties, or any combination thereof. We demonstrate experimentally that our approach substantially outperforms other recently presented methods for tackling a specific version of this problem, namely, maximization when the oracle is assumed to be deterministic and unbiased. We also demonstrate that our method can tackle more general versions of the problem.
Decoupled Classification Refinement: Hard False Positive Suppression for Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we analyze failure cases of state-of-the-art detectors and observe that most hard false positives result from classification instead of localization and they have a large negative impact on the performance of object detectors. We conjecture there are three factors: (1) Shared feature representation is not optimal due to the mismatched goals of feature learning for classification and localization; (2) multi-task learning helps, yet optimization of the multi-task loss may result in sub-optimal for individual tasks; (3) large receptive field for different scales leads to redundant context information for small objects. We demonstrate the potential of detector classification power by a simple, effective, and widely-applicable Decoupled Classification Refinement (DCR) network. In particular, DCR places a separate classification network in parallel with the localization network (base detector). With ROI Pooling placed on the early stage of the classification network, we enforce an adaptive receptive field in DCR. During training, DCR samples hard false positives from the base detector and trains a strong classifier to refine classification results. During testing, DCR refines all boxes from the base detector. Experiments show competitive results on PASCAL VOC and COCO without any bells and whistles. Our codes are available at: https://github.com/bowenc0221/Decoupled-Classification-Refinement.
Hartley Spectral Pooling for Deep Learning
Venue: arXiv cs.CV 2020
Year: 2020

In most convolution neural networks (CNNs), downsampling hidden layers is adopted for increasing computation efficiency and the receptive field size. Such operation is commonly so-called pooling. Maximation and averaging over sliding windows (max/average pooling), and plain downsampling in the form of strided convolution are popular pooling methods. Since the pooling is a lossy procedure, a motivation of our work is to design a new pooling approach for less lossy in the dimensionality reduction. Inspired by the Fourier spectral pooling(FSP) proposed by Rippel et. al. [1], we present the Hartley transform based spectral pooling method in CNNs. Compared with FSP, the proposed spectral pooling avoids the use of complex arithmetic for frequency representation and reduces the computation. Spectral pooling preserves more structure features for network's discriminability than max and average pooling. We empirically show that Hartley spectral pooling gives rise to the convergence of training CNNs on MNIST and CIFAR-10 datasets.
Generic Dijkstra for optical networks
Venue: arXiv cs.NI 2020
Year: 2020

We present the generic Dijkstra shortest path algorithm: an efficient algorithm for finding a shortest path in an optical network, both in a wavelength-division multiplexed network, and an elastic optical network (EON). The proposed algorithm is an enabler of real-time softwarized control of large-scale networks, and is not limited to optical networks. The Dijkstra algorithm is a generalization of the breadth-first search, and we generalize the Dijkstra algorithm further to resolve the continuity and contiguity constraints of the frequency slot units required in EONs. Specifically, we generalize the notion of a label, change what we iterate with, and reformulate the edge relaxation so that vertices are revisited, loops avoided, and worse labels discarded. We also used the typical constriction during edge relaxation to take care of the signal modulation constraints. The algorithm can be used with various spectrum allocation policies. We motivate and discuss the algorithm design, and provide our free, reliable, and generic implementation using the Boost Graph Library. We carried out 85000 simulation runs for realistic and random networks (Gabriel graphs) of 75 vertices with about a billion shortest-path searches, and found that the proposed algorithm outperforms considerably three other competing optimal algorithms that are frequently used.
SingleGAN: Image-to-Image Translation by a Single-Generator Network using Multiple Generative Adversarial Learning
Venue: arXiv cs.CV 2020
Year: 2020

Image translation is a burgeoning field in computer vision where the goal is to learn the mapping between an input image and an output image. However, most recent methods require multiple generators for modeling different domain mappings, which are inefficient and ineffective on some multi-domain image translation tasks. In this paper, we propose a novel method, SingleGAN, to perform multi-domain image-to-image translations with a single generator. We introduce the domain code to explicitly control the different generative tasks and integrate multiple optimization goals to ensure the translation. Experimental results on several unpaired datasets show superior performance of our model in translation between two domains. Besides, we explore variants of SingleGAN for different tasks, including one-to-many domain translation, many-to-many domain translation and one-to-one domain translation with multimodality. The extended experiments show the universality and extensibility of our model.
Sound Regular Expression Semantics for Dynamic Symbolic Execution of JavaScript
Venue: arXiv cs.PL 2020
Year: 2020

Existing support for regular expressions in automated test generation or verification tools is lacking. Common aspects of regular expression engines found in mainstream programming languages, such as backreferences or greedy matching, are commonly ignored or imprecisely approximated, leading to poor test coverage or failed proofs. In this paper, we present the first complete strategy to faithfully reason about regular expressions in the context of symbolic execution, focusing on the operators found in JavaScript. We model regular expression operations using string constraints and classical regular expressions and use a refinement scheme to address the problem of matching precedence and greediness. Our survey of over 400,000 JavaScript packages from the NPM software repository shows that one fifth make use of complex regular expressions features. We implemented our model in a dynamic symbolic execution engine for JavaScript and evaluated it on over 1,000 Node.js packages containing regular expressions, demonstrating that the strategy is effective and can increase line coverage of programs by up to 30%