OpenRaiser/Intern-Atlas huggingface dataset:
Debt-Prone Bugs: Technical Debt in Software Maintenance
Venue: arXiv cs.SE 2017
Year: 2017

Fixing bugs is an important phase in software development and maintenance. In practice, the process of bug fixing may conflict with the release schedule. Such confliction leads to a trade-off between software quality and release schedule, which is known as the technical debt metaphor. In this article, we propose the concept of debt-prone bugs to model the technical debt in software maintenance. We identify three types of debt-prone bugs, namely tag bugs, reopened bugs, and duplicate bugs. A case study on Mozilla is conducted to examine the impact of debt-prone bugs in software products. We investigate the correlation between debt-prone bugs and the product quality. For a product under development, we build prediction models based on historical products to predict the time cost of fixing bugs. The result shows that identifying debt-prone bugs can assist in monitoring and improving software quality.
Solving the Large Scale Next Release Problem with a Backbone Based Multilevel Algorithm
Venue: arXiv cs.SE 2017
Year: 2017

The Next Release Problem (NRP) aims to optimize customer profits and requirements selection for the software releases. The research on the NRP is restricted by the growing scale of requirements. In this paper, we propose a Backbone based Multilevel Algorithm (BMA) to address the large scale NRP. In contrast to direct solving approaches, BMA employs multilevel reductions to downgrade the problem scale and multilevel refinements to construct the final optimal set of customers. In both reductions and refinements, the backbone is built to fix the common part of the optimal customers. Since it is intractable to extract the backbone in practice, the approximate backbone is employed for the instance reduction while the soft backbone is proposed to augment the backbone application. In the experiments, to cope with the lack of open large requirements databases, we propose a method to extract instances from open bug repositories. Experimental results on 15 classic instances and 24 realistic instances demonstrate that BMA can achieve better solutions on the large scale NRP instances than direct solving approaches. Our work provides a reduction approach for solving large scale problems in search based requirements engineering.
Locating Power Flow Solution Space Boundaries: A Numerical Polynomial Homotopy Approach
Venue: arXiv cs.SY 2017
Year: 2017

The solution space of any set of power flow equations may contain different number of real-valued solutions. The boundaries that separate these regions are referred to as power flow solution space boundaries. Knowledge of these boundaries is important as they provide a measure for voltage stability. Traditionally, continuation based methods have been employed to compute these boundaries on the basis of initial guesses for the solution. However, with rapid growth of renewable energy sources these boundaries will be increasingly affected by variable parameters such as penetration levels, locations of the renewable sources, and voltage set-points, making it difficult to generate an initial guess that can guarantee all feasible solutions for the power flow problem. In this paper we solve this problem by applying a numerical polynomial homotopy based continuation method. The proposed method guarantees to find all solution boundaries within a given parameter space up to a chosen level of discretization, independent of any initial guess. Power system operators can use this computational tool conveniently to plan the penetration levels of renewable sources at different buses. We illustrate the proposed method through simulations on 3-bus and 10-bus power system examples with renewable generation.
Differential Evolution and Bayesian Optimisation for Hyper-Parameter Selection in Mixed-Signal Neuromorphic Circuits Applied to UAV Obstacle Avoidance
Venue: arXiv cs.NE 2017
Year: 2017

The Lobula Giant Movement Detector (LGMD) is a an identified neuron of the locust that detects looming objects and triggers its escape responses. Understanding the neural principles and networks that lead to these fast and robust responses can lead to the design of efficient facilitate obstacle avoidance strategies in robotic applications. Here we present a neuromorphic spiking neural network model of the LGMD driven by the output of a neuromorphic Dynamic Vision Sensor (DVS), which has been optimised to produce robust and reliable responses in the face of the constraints and variability of its mixed signal analogue-digital circuits. As this LGMD model has many parameters, we use the Differential Evolution (DE) algorithm to optimise its parameter space. We also investigate the use of Self-Adaptive Differential Evolution (SADE) which has been shown to ameliorate the difficulties of finding appropriate input parameters for DE. We explore the use of two biological mechanisms: synaptic plasticity and membrane adaptivity in the LGMD. We apply DE and SADE to find parameters best suited for an obstacle avoidance system on an unmanned aerial vehicle (UAV), and show how it outperforms state-of-the-art Bayesian optimisation used for comparison.
Gang of GANs: Generative Adversarial Networks with Maximum Margin Ranking
Venue: arXiv cs.CV 2017
Year: 2017

Traditional generative adversarial networks (GAN) and many of its variants are trained by minimizing the KL or JS-divergence loss that measures how close the generated data distribution is from the true data distribution. A recent advance called the WGAN based on Wasserstein distance can improve on the KL and JS-divergence based GANs, and alleviate the gradient vanishing, instability, and mode collapse issues that are common in the GAN training. In this work, we aim at improving on the WGAN by first generalizing its discriminator loss to a margin-based one, which leads to a better discriminator, and in turn a better generator, and then carrying out a progressive training paradigm involving multiple GANs to contribute to the maximum margin ranking loss so that the GAN at later stages will improve upon early stages. We call this method Gang of GANs (GoGAN). We have shown theoretically that the proposed GoGAN can reduce the gap between the true data distribution and the generated data distribution by at least half in an optimally trained WGAN. We have also proposed a new way of measuring GAN quality which is based on image completion tasks. We have evaluated our method on four visual datasets: CelebA, LSUN Bedroom, CIFAR-10, and 50K-SSFF, and have seen both visual and quantitative improvement over baseline WGAN.
A Sport Tournament Scheduling by Genetic Algorithm with Swapping Method
Venue: arXiv cs.NE 2017
Year: 2017

A sport tournament problem is considered the Traveling Tournament Problem (TTP). One interesting type is the mirrored Traveling Tournament Problem (mTTP). The objective of the problem is to minimize either the total number of traveling or the total distances of traveling or both. This research aims to find an optimized solution of the mirrored Traveling Tournament Problem with minimum total number of traveling. The solutions consisting of traveling and scheduling tables are solved by using genetic algorithm (GA) with swapping method. The number of traveling of all teams from obtained solutions are close to the lower bound theory of number of traveling. Moreover, this algorithm generates better solutions than known results for most cases.
Envy-free Matchings with Lower Quotas
Venue: arXiv cs.GT 2017
Year: 2017

While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property. In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas and not all doctor-hospital pairs are acceptable. We first show that, for an HR-LQ instance, we can efficiently decide the existence of an envy-free matching. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (2010), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.
A contract-based method to specify stimulus-response requirements
Venue: arXiv cs.SE 2017
Year: 2017

A number of formal methods exist for capturing stimulus-response requirements in a declarative form. Someone yet needs to translate the resulting declarative statements into imperative programs. The present article describes a method for specification and verification of stimulus-response requirements in the form of imperative program routines with conditionals and assertions. A program prover then checks a candidate program directly against the stated requirements. The article illustrates the approach by applying it to an ASM model of the Landing Gear System, a widely used realistic example proposed for evaluating specification and verification techniques.
Certificate Transparency with Enhancements and Short Proofs
Venue: arXiv cs.CR 2017
Year: 2017

Browsers can detect malicious websites that are provisioned with forged or fake TLS/SSL certificates. However, they are not so good at detecting malicious websites if they are provisioned with mistakenly issued certificates or certificates that have been issued by a compromised certificate authority. Google proposed certificate transparency which is an open framework to monitor and audit certificates in real time. Thereafter, a few other certificate transparency schemes have been proposed which can even handle revocation. All currently known constructions use Merkle hash trees and have proof size logarithmic in the number of certificates/domain owners. We present a new certificate transparency scheme with short (constant size) proofs. Our construction makes use of dynamic bilinear-map accumulators. The scheme has many desirable properties like efficient revocation, low verification cost and update costs comparable to the existing schemes. We provide proofs of security and evaluate the performance of our scheme.
Space-Optimal Majority in Population Protocols
Venue: arXiv cs.DC 2017
Year: 2017

Population protocols are a model of distributed computing, in which $n$ agents with limited local state interact randomly, and cooperate to collectively compute global predicates. An extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task, in which agents need to collectively reach a decision as to which one of two states $A$ or $B$ had a higher initial count. Two complexity metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires. It is known that majority requires $Ω(\log \log n)$ states per agent to allow for poly-logarithmic time stabilization, and that $O(\log^2 n)$ states are sufficient. Thus, there is an exponential gap between the upper and lower bounds. We address this question. We provide a new lower bound of $Ω(\log n)$ states for any protocol which stabilizes in $O( n^{1-c} )$ time, for any $c > 0$ constant. This result is conditional on basic monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a significant departure from previous lower bounds. Instead of relying on dense configurations, we introduce a new surgery technique to construct executions which contradict the correctness of algorithms that stabilize too fast. Subsequently, our lower bound applies to general initial configurations. We give an algorithm for majority which uses $O(\log n)$ states, and stabilizes in $O(\log^2 n)$ time. Central to the algorithm is a new leaderless phase clock, which allows nodes to synchronize in phases of $Θ(n \log{n})$ consecutive interactions using $O(\log n)$ states per node. We also employ our phase clock to build a leader election algorithm with $O(\log n )$ states, which stabilizes in $O(\log^2 n)$ time.
Adversarial and Clean Data Are Not Twins
Venue: arXiv cs.LG 2017
Year: 2017

Adversarial attack has cast a shadow on the massive success of deep neural networks. Despite being almost visually identical to the clean data, the adversarial images can fool deep neural networks into wrong predictions with very high confidence. In this paper, however, we show that we can build a simple binary classifier separating the adversarial apart from the clean data with accuracy over 99%. We also empirically show that the binary classifier is robust to a second-round adversarial attack. In other words, it is difficult to disguise adversarial samples to bypass the binary classifier. Further more, we empirically investigate the generalization limitation which lingers on all current defensive methods, including the binary classifier approach. And we hypothesize that this is the result of intrinsic property of adversarial crafting algorithms.
Fast multi-output relevance vector regression
Venue: arXiv cs.LG 2017
Year: 2017

This paper aims to decrease the time complexity of multi-output relevance vector regression from O(VM^3) to O(V^3+M^3), where V is the number of output dimensions, M is the number of basis functions, and V<M. The experimental results demonstrate that the proposed method is more competitive than the existing method, with regard to computation time. MATLAB codes are available at http://www.mathworks.com/matlabcentral/fileexchange/49131.
A Study on Performance and Power Efficiency of Dense Non-Volatile Caches in Multi-Core Systems
Venue: arXiv cs.AR 2017
Year: 2017

In this paper, we present a novel cache design based on Multi-Level Cell Spin-Transfer Torque RAM (MLC STTRAM) that can dynamically adapt the set capacity and associativity to use efficiently the full potential of MLC STTRAM. We exploit the asymmetric nature of the MLC storage scheme to build cache lines featuring heterogeneous performances, that is, half of the cache lines are read-friendly, while the other is write-friendly. Furthermore, we propose to opportunistically deactivate ways in underutilized sets to convert MLC to Single-Level Cell (SLC) mode, which features overall better performance and lifetime. Our ultimate goal is to build a cache architecture that combines the capacity advantages of MLC and performance/energy advantages of SLC. Our experiments show an improvement of 43% in total numbers of conflict misses, 27% in memory access latency, 12% in system performance, and 26% in LLC access energy, with a slight degradation in cache lifetime (about 7%) compared to an SLC cache.
FEUP at SemEval-2017 Task 5: Predicting Sentiment Polarity and Intensity with Financial Word Embeddings
Venue: arXiv cs.CL 2017
Year: 2017

This paper presents the approach developed at the Faculty of Engineering of University of Porto, to participate in SemEval 2017, Task 5: Fine-grained Sentiment Analysis on Financial Microblogs and News. The task consisted in predicting a real continuous variable from -1.0 to +1.0 representing the polarity and intensity of sentiment concerning companies/stocks mentioned in short texts. We modeled the task as a regression analysis problem and combined traditional techniques such as pre-processing short texts, bag-of-words representations and lexical-based features with enhanced financial specific bag-of-embeddings. We used an external collection of tweets and news headlines mentioning companies/stocks from S\&P 500 to create financial word embeddings which are able to capture domain-specific syntactic and semantic similarities. The resulting approach obtained a cosine similarity score of 0.69 in sub-task 5.1 - Microblogs and 0.68 in sub-task 5.2 - News Headlines.
Automatic Disambiguation of French Discourse Connectives
Venue: arXiv cs.CL 2017
Year: 2017

Discourse connectives (e.g. however, because) are terms that can explicitly convey a discourse relation within a text. While discourse connectives have been shown to be an effective clue to automatically identify discourse relations, they are not always used to convey such relations, thus they should first be disambiguated between discourse-usage non-discourse-usage. In this paper, we investigate the applicability of features proposed for the disambiguation of English discourse connectives for French. Our results with the French Discourse Treebank (FDTB) show that syntactic and lexical features developed for English texts are as effective for French and allow the disambiguation of French discourse connectives with an accuracy of 94.2%.
Video Object Segmentation using Supervoxel-Based Gerrymandering
Venue: arXiv cs.CV 2017
Year: 2017

Pixels operate locally. Superpixels have some potential to collect information across many pixels; supervoxels have more potential by implicitly operating across time. In this paper, we explore this well established notion thoroughly analyzing how supervoxels can be used in place of and in conjunction with other means of aggregating information across space-time. Focusing on the problem of strictly unsupervised video object segmentation, we devise a method called supervoxel gerrymandering that links masks of foregroundness and backgroundness via local and non-local consensus measures. We pose and answer a series of critical questions about the ability of supervoxels to adequately sway local voting; the questions regard type and scale of supervoxels as well as local versus non-local consensus, and the questions are posed in a general way so as to impact the broader knowledge of the use of supervoxels in video understanding. We work with the DAVIS dataset and find that our analysis yields an unsupervised method that outperforms all other known unsupervised methods and even many supervised ones.
"Short-Dot": Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
Venue: arXiv cs.IT 2017
Year: 2017

Faced with saturation of Moore's law and increasing dimension of data, system designers have increasingly resorted to parallel and distributed computing. However, distributed computing is often bottle necked by a small fraction of slow processors called "stragglers" that reduce the speed of computation because the fusion node has to wait for all processors to finish. To combat the effect of stragglers, recent literature introduces redundancy in computations across processors, e.g.,~using repetition-based strategies or erasure codes. The fusion node can exploit this redundancy by completing the computation using outputs from only a subset of the processors, ignoring the stragglers. In this paper, we propose a novel technique -- that we call "Short-Dot" -- to introduce redundant computations in a coding theory inspired fashion, for computing linear transforms of long vectors. Instead of computing long dot products as required in the original linear transform, we construct a larger number of redundant and short dot products that can be computed faster and more efficiently at individual processors. In reference to comparable schemes that introduce redundancy to tackle stragglers, Short-Dot reduces the cost of computation, storage and communication since shorter portions are stored and computed at each processor, and also shorter portions of the input is communicated to each processor. We demonstrate through probabilistic analysis as well as experiments that Short-Dot offers significant speed-up compared to existing techniques. We also derive trade-offs between the length of the dot-products and the resilience to stragglers (number of processors to wait for), for any such strategy and compare it to that achieved by our strategy.
Satellite Based Positioning Signal Acquisition at Higher Order Cycle Frequency
Venue: arXiv cs.IT 2017
Year: 2017

The acquisition of the signal from the satellite based positioning systems, such as GPS, Galileo, and Compass, encounters challenges in the urban streets, indoor. For improving the acquisition performance, the data accumulation is usually performed to improve the signal-to-noise ratio which is defined on the second order statistics. Different from the conventional approaches, the acquisition based on higher order cyclostatistics is proposed. Using the cyclostatistics, the estimation of the initial phase and Doppler shift of the signal is presented respectively. Afterwards, a joint estimator is introduced. The analysis in this paper is performed on GPS signal. Indeed, the proposed estimation method can be straightforwardly extended to acquire the signal from the other satellite positioning systems. The simulation and experiment results demonstrate that the proposed signal acquisition scheme achieves the detection probability of 0.9 at the CNR 28dBHz.
Mutual Information, Relative Entropy and Estimation Error in Semi-martingale Channels
Venue: arXiv cs.IT 2017
Year: 2017

Fundamental relations between information and estimation have been established in the literature for the continuous-time Gaussian and Poisson channels, in a long line of work starting from the classical representation theorems by Duncan and Kabanov respectively. In this work, we demonstrate that such relations hold for a much larger family of continuous-time channels. We introduce the family of semi-martingale channels where the channel output is a semi-martingale stochastic process, and the channel input modulates the characteristics of the semi-martingale. For these channels, which includes as a special case the continuous time Gaussian and Poisson models, we establish new representations relating the mutual information between the channel input and output to an optimal causal filtering loss, thereby unifying and considerably extending results from the Gaussian and Poisson settings. Extensions to the setting of mismatched estimation are also presented where the relative entropy between the laws governing the output of the channel under two different input distributions is equal to the cumulative difference between the estimation loss incurred by using the mismatched and optimal causal filters respectively. The main tool underlying these results is the Doob--Meyer decomposition of a class of likelihood ratio sub-martingales. The results in this work can be viewed as the continuous-time analogues of recent generalizations for relations between information and estimation for discrete-time Lévy channels.
Know Your Master: Driver Profiling-based Anti-theft Method
Venue: arXiv cs.CR 2017
Year: 2017

Although many anti-theft technologies are implemented, auto-theft is still increasing. Also, security vulnerabilities of cars can be used for auto-theft by neutralizing anti-theft system. This keyless auto-theft attack will be increased as cars adopt computerized electronic devices more. To detect auto-theft efficiently, we propose the driver verification method that analyzes driving patterns using measurements from the sensor in the vehicle. In our model, we add mechanical features of automotive parts that are excluded in previous works, but can be differentiated by drivers' driving behaviors. We design the model that uses significant features through feature selection to reduce the time cost of feature processing and improve the detection performance. Further, we enrich the feature set by deriving statistical features such as mean, median, and standard deviation. This minimizes the effect of fluctuation of feature values per driver and finally generates the reliable model. We also analyze the effect of the size of sliding window on performance to detect the time point when the detection becomes reliable and to inform owners the theft event as soon as possible. We apply our model with real driving and show the contribution of our work to the literature of driver identification.