OpenRaiser/Intern-Atlas huggingface dataset:
What Causes My Test Alarm? Automatic Cause Analysis for Test Alarms in System and Integration Testing
Venue: arXiv cs.SE 2017
Year: 2017

Driven by new software development processes and testing in clouds, system and integration testing nowadays tends to produce enormous number of alarms. Such test alarms lay an almost unbearable burden on software testing engineers who have to manually analyze the causes of these alarms. The causes are critical because they decide which stakeholders are responsible to fix the bugs detected during the testing. In this paper, we present a novel approach that aims to relieve the burden by automating the procedure. Our approach, called Cause Analysis Model, exploits information retrieval techniques to efficiently infer test alarm causes based on test logs. We have developed a prototype and evaluated our tool on two industrial datasets with more than 14,000 test alarms. Experiments on the two datasets show that our tool achieves an accuracy of 58.3% and 65.8%, respectively, which outperforms the baseline algorithms by up to 13.3%. Our algorithm is also extremely efficient, spending about 0.1s per cause analysis. Due to the attractive experimental results, our industrial partner, a leading information and communication technology company in the world, has deployed the tool and it achieves an average accuracy of 72% after two months of running, nearly three times more accurate than a previous strategy based on regular expressions.
Creative Community Demystified: A Statistical Overview of Behance
Venue: arXiv cs.SI 2017
Year: 2017

Online communities are changing the ways that creative professionals such as artists and designers share ideas, receive feedback, and find inspiration. While they became increasingly popular, there have been few studies so far. In this paper, we investigate Behance, an online community site for creatives to maintain relationships with others and showcase their works from various fields such as graphic design, illustration, photography, and fashion. We take a quantitative approach to study three research questions about the site. What attract followers and appreciation of artworks on Behance? what patterns of activity exist around topics? And, lastly, does color play a role in attracting appreciation? In summary, being male suggests more followers and appreciations, most users focus on a few topics, and grayscale colors mean fewer appreciations. This work serves as a preliminary overview of a creative community that later studies can build on.
Privacy Management and Optimal Pricing in People-Centric Sensing
Venue: arXiv cs.GT 2017
Year: 2017

With the emerging sensing technologies such as mobile crowdsensing and Internet of Things (IoT), people-centric data can be efficiently collected and used for analytics and optimization purposes. This data is typically required to develop and render people-centric services. In this paper, we address the privacy implication, optimal pricing, and bundling of people-centric services. We first define the inverse correlation between the service quality and privacy level from data analytics perspectives. We then present the profit maximization models of selling standalone, complementary, and substitute services. Specifically, the closed-form solutions of the optimal privacy level and subscription fee are derived to maximize the gross profit of service providers. For interrelated people-centric services, we show that cooperation by service bundling of complementary services is profitable compared to the separate sales but detrimental for substitutes. We also show that the market value of a service bundle is correlated with the degree of contingency between the interrelated services. Finally, we incorporate the profit sharing models from game theory for dividing the bundling profit among the cooperative service providers.
Meta Networks
Venue: arXiv cs.LG 2017
Year: 2017

Neural networks have been successfully applied in applications with a large amount of labeled data. However, the task of rapid generalization on new concepts with small training data while preserving performances on previously learned ones still presents a significant challenge to neural network models. In this work, we introduce a novel meta learning method, Meta Networks (MetaNet), that learns a meta-level knowledge across tasks and shifts its inductive biases via fast parameterization for rapid generalization. When evaluated on Omniglot and Mini-ImageNet benchmarks, our MetaNet models achieve a near human-level performance and outperform the baseline approaches by up to 6% accuracy. We demonstrate several appealing properties of MetaNet relating to generalization and continual learning.
Towards CNN Map Compression for camera relocalisation
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a study on the use of Convolutional Neural Networks for camera relocalisation and its application to map compression. We follow state of the art visual relocalisation results and evaluate response to different data inputs -- namely, depth, grayscale, RGB, spatial position and combinations of these. We use a CNN map representation and introduce the notion of CNN map compression by using a smaller CNN architecture. We evaluate our proposal in a series of publicly available datasets. This formulation allows us to improve relocalisation accuracy by increasing the number of training trajectories while maintaining a constant-size CNN.
Improved Deterministic Distributed Matching via Rounding
Venue: arXiv cs.DS 2017
Year: 2017

We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method, to our knowledge. A sampling of our end results is as follows. -- An $O(\log^2 Δ\cdot \log n)$-round deterministic distributed algorithm for computing a maximal matching, in $n$-node graphs with maximum degree $Δ$. This is the first improvement in about 20 years over the celebrated $O(\log^4 n)$-round algorithm of Hańćkowiak, Karoński, and Panconesi [SODA'98, PODC'99]. -- A deterministic distributed algorithm for computing a $(2+\varepsilon)$-approximation of maximum matching in $O(\log^2 Δ\cdot \log \frac{1}{\varepsilon} + \log^ * n)$ rounds. This is exponentially faster than the classic $O(Δ+\log^* n)$-round $2$-approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an $\varepsilon$-maximal matching which leaves only an $\varepsilon$-fraction of the edges on unmatched nodes. -- An $O(\log^2 Δ\cdot \log \frac{1}{\varepsilon} + \log^ * n)$-round deterministic distributed algorithm for computing a $(2+\varepsilon)$-approximation of a maximum weighted matching, and also for the more general problem of maximum weighted $b$-matching. These improve over the $O(\log^4 n \cdot \log_{1+\varepsilon} W)$-round $(6+\varepsilon)$-approximation algorithm of Panconesi and Sozio [DIST'10], where $W$ denotes the maximum normalized weight.
Skin Lesion Classification using Class Activation Map
Venue: arXiv cs.CV 2017
Year: 2017

We proposed a two stage framework with only one network to analyze skin lesion images, we firstly trained a convolutional network to classify these images, and cropped the import regions which the network has the maximum activation value. In the second stage, we retrained this CNN with the image regions extracted from stage one and output the final probabilities. The two stage framework achieved a mean AUC of 0.857 in ISIC-2017 skin lesion validation set and is 0.04 higher than that of the original inputs, 0.821.
Dynamic State Warping
Venue: arXiv cs.LG 2017
Year: 2017

The ubiquity of sequences in many domains enhances significant recent interest in sequence learning, for which a basic problem is how to measure the distance between sequences. Dynamic time warping (DTW) aligns two sequences by nonlinear local warping and returns a distance value. DTW shows superior ability in many applications, e.g. video, image, etc. However, in DTW, two points are paired essentially based on point-to-point Euclidean distance (ED) without considering the autocorrelation of sequences. Thus, points with different semantic meanings, e.g. peaks and valleys, may be matched providing their coordinate values are similar. As a result, DTW is sensitive to noise and poorly interpretable. This paper proposes an efficient and flexible sequence alignment algorithm, dynamic state warping (DSW). DSW converts each time point into a latent state, which endows point-wise autocorrelation information. Alignment is performed by using the state sequences. Thus DSW is able to yield alignment that is semantically more interpretable than that of DTW. Using one nearest neighbor classifier, DSW shows significant improvement on classification accuracy in comparison to ED (70/85 wins) and DTW (74/85 wins). We also empirically demonstrate that DSW is more robust and scales better to long sequences than ED and DTW.
Why is it hard to beat $O(n^2)$ for Longest Common Weakly Increasing Subsequence?
Venue: arXiv cs.CC 2017
Year: 2017

The Longest Common Weakly Increasing Subsequence problem (LCWIS) is a variant of the classic Longest Common Subsequence problem (LCS). Both problems can be solved with simple quadratic time algorithms. A recent line of research led to a number of matching conditional lower bounds for LCS and other related problems. However, the status of LCWIS remained open. In this paper we show that LCWIS cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis (SETH) is false. The ideas which we developed can also be used to obtain a lower bound based on a safer assumption of NC-SETH, i.e. a version of SETH which talks about NC circuits instead of less expressive CNF formulas.
Runtime Optimization of Join Location in Parallel Data Management Systems
Venue: arXiv cs.DB 2017
Year: 2017

Applications running on parallel systems often need to join a streaming relation or a stored relation with data indexed in a parallel data storage system. Some applications also compute UDFs on the joined tuples. The join can be done at the data storage nodes, corresponding to reduce side joins, or by fetching data from the storage system to compute nodes, corresponding to map side join. Both may be suboptimal: reduce side joins may cause skew, while map side joins may lead to a lot of data being transferred and replicated. In this paper, we present techniques to make runtime decisions between the two options on a per key basis, in order to improve the throughput of the join, accounting for UDF computation if any. Our techniques are based on an extended ski-rental algorithm and provide worst-case performance guarantees with respect to the optimal point in the space considered by us. Our techniques use load balancing taking into account the CPU, network and I/O costs as well as the load on compute and storage nodes. We have implemented our techniques on Hadoop, Spark and the Muppet stream processing engine. Our experiments show that our optimization techniques provide a significant improvement in throughput over existing techniques.
Percentile Policies for Tracking of Markovian Random Processes with Asymmetric Cost and Observation
Venue: arXiv cs.IT 2017
Year: 2017

Motivated by wide-ranging applications such as video delivery over networks using Multiple Description Codes, congestion control, and inventory management, we study the state-tracking of a Markovian random process with a known transition matrix and a finite ordered state set. The decision-maker must select a state as an action at each time step to minimize the total expected cost. The decision-maker is faced with asymmetries both in cost and observation: in case the selected state is less than the actual state of the Markovian process, an under-utilization cost occurs and only partial observation about the actual state is revealed; otherwise, the decision incurs an over-utilization cost and reveals full information about the actual state. We can formulate this problem as a Partially Observable Markov Decision Process which can be expressed as a dynamic program based on the last full observed state and the time of full observation. This formulation determines the sequence of actions to be taken between any two consecutive full observations of the actual state. However, this DP grows exponentially in the number of states, with little hope for a computationally feasible solution. We present an interesting class of computationally tractable policies with a percentile structure. A generalization of binary search, this class of policies attempt at any given time to reduce the uncertainty by a given percentage. Among all percentile policies, we search for the one with the minimum expected cost. The result of this search is a heuristic policy which we evaluate through numerical simulations. We show that it outperforms the myopic policies and under some conditions performs close to the optimal policies. Furthermore, we derive a lower bound on the cost of the optimal policy which can be computed with low complexity and give a measure for how close our heuristic policy is to the optimal policy.
Towards Monetary Incentives in Social Q&A Services
Venue: arXiv cs.AI 2017
Year: 2017

Community-based question answering (CQA) services are facing key challenges to motivate domain experts to provide timely answers. Recently, CQA services are exploring new incentive models to engage experts and celebrities by allowing them to set a price on their answers. In this paper, we perform a data-driven analysis on two emerging payment-based CQA systems: Fenda (China) and Whale (US). By analyzing a large dataset of 220K questions (worth 1 million USD collectively), we examine how monetary incentives affect different players in the system. We find that, while monetary incentive enables quick answers from experts, it also drives certain users to aggressively game the system for profits. In addition, in this supplier-driven marketplace, users need to proactively adjust their price to make profits. Famous people are unwilling to lower their price, which in turn hurts their income and engagement over time. Finally, we discuss the key implications to future CQA design.
Generative Poisoning Attack Method Against Neural Networks
Venue: arXiv cs.CR 2017
Year: 2017

Poisoning attack is identified as a severe security threat to machine learning algorithms. In many applications, for example, deep neural network (DNN) models collect public data as the inputs to perform re-training, where the input data can be poisoned. Although poisoning attack against support vector machines (SVM) has been extensively studied before, there is still very limited knowledge about how such attack can be implemented on neural networks (NN), especially DNNs. In this work, we first examine the possibility of applying traditional gradient-based method (named as the direct gradient method) to generate poisoned data against NNs by leveraging the gradient of the target model w.r.t. the normal data. We then propose a generative method to accelerate the generation rate of the poisoned data: an auto-encoder (generator) used to generate poisoned data is updated by a reward function of the loss, and the target NN model (discriminator) receives the poisoned data to calculate the loss w.r.t. the normal data. Our experiment results show that the generative method can speed up the poisoned data generation rate by up to 239.38x compared with the direct gradient method, with slightly lower model accuracy degradation. A countermeasure is also designed to detect such poisoning attack methods by checking the loss of the target model.
Wavelet Domain Residual Network (WavResNet) for Low-Dose X-ray CT Reconstruction
Venue: arXiv cs.CV 2017
Year: 2017

Model based iterative reconstruction (MBIR) algorithms for low-dose X-ray CT are computationally complex because of the repeated use of the forward and backward projection. Inspired by this success of deep learning in computer vision applications, we recently proposed a deep convolutional neural network (CNN) for low-dose X-ray CT and won the second place in 2016 AAPM Low-Dose CT Grand Challenge. However, some of the texture are not fully recovered, which was unfamiliar to some radiologists. To cope with this problem, here we propose a direct residual learning approach on directional wavelet domain to solve this problem and to improve the performance against previous work. In particular, the new network estimates the noise of each input wavelet transform, and then the de-noised wavelet coefficients are obtained by subtracting the noise from the input wavelet transform bands. The experimental results confirm that the proposed network has significantly improved performance, preserving the detail texture of the original images.
Power Allocation for Full-Duplex Relay Selection in Underlay Cognitive Radio Networks: Coherent versus Non-Coherent Scenarios
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates power control and relay selection in Full Duplex Cognitive Relay Networks (FDCRNs), where the secondary-user (SU) relays can simultaneously receive data from the SU source and forward them to the SU destination. We study both non-coherent and coherent scenarios. In the non-coherent case, the SU relay forwards the signal from the SU source without regulating the phase; while in the coherent scenario, the SU relay regulates the phase when forwarding the signal to minimize the interference at the primary-user (PU) receiver. We consider the problem of maximizing the transmission rate from the SU source to the SU destination subject to the interference constraint at the PU receiver and power constraints at both the SU source and SU relay. We then develop a mathematical model to analyze the data rate performance of the FDCRN considering the self-interference effects at the FD relay. We develop low-complexity and high-performance joint power control and relay selection algorithms. Extensive numerical results are presented to illustrate the impacts of power level parameters and the self-interference cancellation quality on the rate performance. Moreover, we demonstrate the significant gain of phase regulation at the SU relay.
L-Graphs and Monotone L-Graphs
Venue: arXiv cs.CG 2017
Year: 2017

In an $\mathsf{L}$-embedding of a graph, each vertex is represented by an $\mathsf{L}$-segment, and two segments intersect each other if and only if the corresponding vertices are adjacent in the graph. If the corner of each $\mathsf{L}$-segment in an $\mathsf{L}$-embedding lies on a straight line, we call it a monotone $\mathsf{L}$-embedding. In this paper we give a full characterization of monotone $\mathsf{L}$-embeddings by introducing a new class of graphs which we call "non-jumping" graphs. We show that a graph admits a monotone $\mathsf{L}$-embedding if and only if the graph is a non-jumping graph. Further, we show that outerplanar graphs, convex bipartite graphs, interval graphs, 3-leaf power graphs, and complete graphs are subclasses of non-jumping graphs. Finally, we show that distance-hereditary graphs and $k$-leaf power graphs ($k\le 4$) admit $\mathsf{L}$-embeddings.
Face Alignment with Cascaded Semi-Parametric Deep Greedy Neural Forests
Venue: arXiv cs.CV 2017
Year: 2017

Face alignment is an active topic in computer vision, consisting in aligning a shape model on the face. To this end, most modern approaches refine the shape in a cascaded manner, starting from an initial guess. Those shape updates can either be applied in the feature point space (\textit{i.e.} explicit updates) or in a low-dimensional, parametric space. In this paper, we propose a semi-parametric cascade that first aligns a parametric shape, then captures more fine-grained deformations of an explicit shape. For the purpose of learning shape updates at each cascade stage, we introduce a deep greedy neural forest (GNF) model, which is an improved version of deep neural forest (NF). GNF appears as an ideal regressor for face alignment, as it combines differentiability, high expressivity and fast evaluation runtime. The proposed framework is very fast and achieves high accuracies on multiple challenging benchmarks, including small, medium and large pose experiments.
Conditional Hardness for Sensitivity Problems
Venue: arXiv cs.DS 2017
Year: 2017

In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity. In this paper we prove conditional lower bounds for sensitivity problems. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the (4/3 - ε)-approximate diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible. We further show under the BMM conjecture that many problems, such as reachability or approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We give more lower bounds under the Strong Exponential Time Hypothesis and the All Pairs Shortest Paths Conjecture. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required. Finally, we give the first algorithm for the (1 + ε)-approximate radius, diameter, and eccentricity problems in directed or undirected unweighted graphs in case of single edges failures. The algorithm has a truly subcubic running time for graphs with a truly subquadratic number of edges; it is tight w.r.t. the conditional lower bounds we obtain.
A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane
Venue: arXiv cs.CG 2017
Year: 2017

The Euclidean TSP with neighborhoods (TSPN) problem seeks a shortest tour that visits a given collection of $n$ regions ({\em neighborhoods}). We present the first polynomial-time approximation scheme for TSPN for a set of regions given by arbitrary disjoint fat regions in the plane. This improves substantially upon the known approximation algorithms, and is the first PTAS for TSPN on regions of non-comparable sizes. Our result is based on a novel extension of the $m$-guillotine method. The result applies to regions that are "fat" in a very weak sense: each region $P_i$ has area $Ω([diam(P_i)]^2)$, but is otherwise arbitrary.
Effect of Adaptive and Cooperative Adaptive Cruise Control on Throughput of Signalized Arterials
Venue: arXiv cs.SY 2017
Year: 2017

The paper evaluates the influence of the maximum vehicle acceleration and variable proportions of ACC/CACC vehicles on the throughput of an intersection. Two cases are studied: (1) free road downstream of the intersection; and (2) red light at some distance downstream of the intersection. Simulation of a 4-mile stretch of an arterial with 13 signalized intersections is used to evaluate the impact of (C)ACC vehicles on the mean and standard deviation of travel time as the proportion of (C)ACC vehicles is increased. The results suggest a very high urban mobility benefit of (C)ACC vehicles at little or no cost in infrastructure.