OpenRaiser/Intern-Atlas huggingface dataset:
A Deep Learning Based DDoS Detection System in Software-Defined Networking (SDN)
Venue: arXiv cs.NI 2016
Year: 2016

Distributed Denial of Service (DDoS) is one of the most prevalent attacks that an organizational network infrastructure comes across nowadays. We propose a deep learning based multi-vector DDoS detection system in a software-defined network (SDN) environment. SDN provides flexibility to program network devices for different objectives and eliminates the need for third-party vendor-specific hardware. We implement our system as a network application on top of an SDN controller. We use deep learning for feature reduction of a large set of features derived from network traffic headers. We evaluate our system based on different performance metrics by applying it on traffic traces collected from different scenarios. We observe high accuracy with a low false-positive for attack detection in our proposed system.
The Heterogeneous Capacitated $k$-Center Problem
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we initiate the study of the heterogeneous capacitated $k$-center problem: given a metric space $X = (F \cup C, d)$, and a collection of capacities. The goal is to open each capacity at a unique facility location in $F$, and also to assign clients to facilities so that the number of clients assigned to any facility is at most the capacity installed; the objective is then to minimize the maximum distance between a client and its assigned facility. If all the capacities $c_i$'s are identical, the problem becomes the well-studied uniform capacitated $k$-center problem for which constant-factor approximations are known. The additional choice of determining which capacity should be installed in which location makes our problem considerably different from this problem, as well the non-uniform generalizations studied thus far in literature. In fact, one of our contributions is in relating the heterogeneous problem to special-cases of the classical Santa Claus problem. Using this connection, and by designing new algorithms for these special cases, we get the following results: (a)A quasi-polynomial time $O(\log n/ε)$-approximation where every capacity is violated by $1+\varepsilon$, (b) A polynomial time $O(1)$-approximation where every capacity is violated by an $O(\log n)$ factor. We get improved results for the {\em soft-capacities} version where we can place multiple facilities in the same location.
Deep Learning Approximation for Stochastic Control Problems
Venue: arXiv cs.LG 2016
Year: 2016

Many real world stochastic control problems suffer from the "curse of dimensionality". To overcome this difficulty, we develop a deep learning approach that directly solves high-dimensional stochastic control problems based on Monte-Carlo sampling. We approximate the time-dependent controls as feedforward neural networks and stack these networks together through model dynamics. The objective function for the control problem plays the role of the loss function for the deep neural network. We test this approach using examples from the areas of optimal trading and energy storage. Our results suggest that the algorithm presented here achieves satisfactory accuracy and at the same time, can handle rather high dimensional problems.
An unexpected unity among methods for interpreting model predictions
Venue: arXiv cs.AI 2016
Year: 2016

Understanding why a model made a certain prediction is crucial in many data science fields. Interpretable predictions engender appropriate trust and provide insight into how the model may be improved. However, with large modern datasets the best accuracy is often achieved by complex models even experts struggle to interpret, which creates a tension between accuracy and interpretability. Recently, several methods have been proposed for interpreting predictions from complex models by estimating the importance of input features. Here, we present how a model-agnostic additive representation of the importance of input features unifies current methods. This representation is optimal, in the sense that it is the only set of additive values that satisfies important properties. We show how we can leverage these properties to create novel visual explanations of model predictions. The thread of unity that this representation weaves through the literature indicates that there are common principles to be learned about the interpretation of model predictions that apply in many scenarios.
Randomized Distributed Mean Estimation: Accuracy vs Communication
Venue: arXiv cs.DC 2016
Year: 2016

We consider the problem of estimating the arithmetic average of a finite collection of real vectors stored in a distributed fashion across several compute nodes subject to a communication budget constraint. Our analysis does not rely on any statistical assumptions about the source of the vectors. This problem arises as a subproblem in many applications, including reduce-all operations within algorithms for distributed and federated optimization and learning. We propose a flexible family of randomized algorithms exploring the trade-off between expected communication cost and estimation error. Our family contains the full-communication and zero-error method on one extreme, and an $ε$-bit communication and ${\cal O}\left(1/(εn)\right)$ error method on the opposite extreme. In the special case where we communicate, in expectation, a single bit per coordinate of each vector, we improve upon existing results by obtaining $\mathcal{O}(r/n)$ error, where $r$ is the number of bits used to represent a floating point value.
Relaxed Earth Mover's Distances for Chain- and Tree-connected Spaces and their use as a Loss Function in Deep Learning
Venue: arXiv cs.CV 2016
Year: 2016

The Earth Mover's Distance (EMD) computes the optimal cost of transforming one distribution into another, given a known transport metric between them. In deep learning, the EMD loss allows us to embed information during training about the output space structure like hierarchical or semantic relations. This helps in achieving better output smoothness and generalization. However EMD is computationally expensive.Moreover, solving EMD optimization problems usually require complex techniques like lasso. These properties limit the applicability of EMD-based approaches in large scale machine learning. We address in this work the difficulties facing incorporation of EMD-based loss in deep learning frameworks. Additionally, we provide insight and novel solutions on how to integrate such loss function in training deep neural networks. Specifically, we make three main contributions: (i) we provide an in-depth analysis of the fastest state-of-the-art EMD algorithm (Sinkhorn Distance) and discuss its limitations in deep learning scenarios. (ii) we derive fast and numerically stable closed-form solutions for the EMD gradient in output spaces with chain- and tree- connectivity; and (iii) we propose a relaxed form of the EMD gradient with equivalent computational complexity but faster convergence rate. We support our claims with experiments on real datasets. In a restricted data setting on the ImageNet dataset, we train a model to classify 1000 categories using 50K images, and demonstrate that our relaxed EMD loss achieves better Top-1 accuracy than the cross entropy loss. Overall, we show that our relaxed EMD loss criterion is a powerful asset for deep learning in the small data regime.
Optimal Pricing for Submodular Valuations with Bounded Curvature
Venue: arXiv cs.GT 2016
Year: 2016

The optimal pricing problem is a fundamental problem that arises in combinatorial auctions. Suppose that there is one seller who has indivisible items and multiple buyers who want to purchase a combination of the items. The seller wants to sell his items for the highest possible prices, and each buyer wants to maximize his utility (i.e., valuation minus payment) as long as his payment does not exceed his budget. The optimal pricing problem seeks a price of each item and an assignment of items to buyers such that every buyer achieves the maximum utility under the prices. The goal of the problem is to maximize the total payment from buyers. In this paper, we consider the case that the valuations are submodular. We show that the problem is computationally hard even if there exists only one buyer. Then we propose approximation algorithms for the unlimited budget case. We also extend the algorithm for the limited budget case when there exists one buyer and multiple buyers collaborate with each other.
A Framework for Collision-Tolerant Optimal Trajectory Planning of Autonomous Vehicles
Venue: arXiv cs.RO 2016
Year: 2016

Collision-tolerant trajectory planning is the consideration that collisions, if they are planned appropriately, enable more effective path planning for robots capable of handling them. A mixed integer programming (MIP) optimization formulation demonstrates the computational practicality of optimizing trajectories that comprise planned collisions. A damage quantification function is proposed, and the influence of damage functions constraints on the trajectory are studied in simulation. Using a simple example, an increase in performance is achieved under this schema as compared to collision-free optimal trajectories.
An Update on Deductive Synthesis and Repair in the Leon Tool
Venue: arXiv cs.LO 2016
Year: 2016

We report our progress in scaling deductive synthesis and repair of recursive functional Scala programs in the Leon tool. We describe new techniques, including a more precise mechanism for encoding the space of meaningful candidate programs. Our techniques increase the scope of synthesis by expanding the space of programs we can synthesize and by reducing the synthesis time in many cases. As a new example, we present a run-length encoding function for a list of values, which Leon can now automatically synthesize from specification consisting of the decoding function and the local minimality property of the encoded value.
AARC: First draft of the Blueprint Architecture for Authentication and Authorisation Infrastructures
Venue: arXiv cs.CR 2016
Year: 2016

AARC (Authentication and Authorisation for Research Communities) is a two-year EC-funded project to develop and pilot an integrated cross-discipline authentication and authorisation framework, building on existing authentication and authorisation infrastructures (AAIs) and production federated infrastructure. AARC also champions federated access and offers tailored training to complement the actions needed to test AARC results and to promote AARC outcomes. This article describes a high-level blueprint architectures for interoperable AAIs.
Image Segmentation Using Overlapping Group Sparsity
Venue: arXiv cs.CV 2016
Year: 2016

Sparse decomposition has been widely used for different applications, such as source separation, image classification and image denoising. This paper presents a new algorithm for segmentation of an image into background and foreground text and graphics using sparse decomposition. First, the background is represented using a suitable smooth model, which is a linear combination of a few smoothly varying basis functions, and the foreground text and graphics are modeled as a sparse component overlaid on the smooth background. Then the background and foreground are separated using a sparse decomposition framework and imposing some prior information, which promote the smoothness of background, and the sparsity and connectivity of foreground pixels. This algorithm has been tested on a dataset of images extracted from HEVC standard test sequences for screen content coding, and is shown to outperform prior methods, including least absolute deviation fitting, k-means clustering based segmentation in DjVu, and shape primitive extraction and coding algorithm.
On the Relationship of Inconsistent Software Clones and Faults: An Empirical Study
Venue: arXiv cs.SE 2016
Year: 2016

Background: Code cloning - copying and reusing pieces of source code - is a common phenomenon in software development in practice. There have been several empirical studies on the effects of cloning, but there are contradictory results regarding the connection of cloning and faults. Objective: Our aim is to clarify the relationship between code clones and faults. In particular, we focus on inconsistent (or type-3) clones in this work. Method: We conducted a case study with TWT GmbH where we detected the code clones in three Java systems, set them into relation to information from issue tracking and version control and interviewed three key developers. Results: Of the type-3 clones, 17 % contain faults. Developers modified most of the type-3 clones simultaneously and thereby fixed half of the faults in type-3 clones consistently. Type-2 clones with faults all evolved to fixed type-3 clones. Clone length is only weakly correlated with faultiness. Conclusion: There are indications that the developers in two cases have been aware of clones. It might be a reason for the weak relationship between type-3 clones and faults. Hence, it seems important to keep developers aware of clones, potentially with new tool support. Future studies need to investigate if the rate of faults in type-3 clones justifies using them as cues in defect detection.
Structure and algorithms for (cap, even hole)-free graphs
Venue: arXiv cs.DM 2016
Year: 2016

A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph $G$ has a vertex of degree at most $\frac{3}{2}ω(G) -1$, and hence $χ(G)\leq \frac{3}{2}ω(G)$, where $ω(G)$ denotes the size of a largest clique in $G$ and $χ(G)$ denotes the chromatic number of $G$. We give an $O(nm)$ algorithm for $q$-coloring these graphs for fixed $q$ and an $O(nm)$ algorithm for maximum weight stable set. We also give a polynomial-time algorithm for minimum coloring. Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs $G$ without clique cutsets have treewidth at most $6ω(G)-1$ and clique-width at most 48.
DroidLeaks: Benchmarking Resource Leak Bugs for Android Applications
Venue: arXiv cs.SE 2016
Year: 2016

Resource leak bugs in Android apps are pervasive and can cause serious performance degradation and system crashes. In recent years, several resource leak detection techniques have been proposed to assist Android developers in correctly managing system resources. Yet, there exist no common bug benchmarks for effectively and reliably comparing such techniques and quantitatively evaluating their strengths and weaknesses. This paper describes our initial contribution towards constructing such a benchmark. To locate real resource leak bugs, we mined 124,215 code revisions of 34 large-scale open-source Android apps. We successfully found 298 fixed resource leaks, which cover a diverse set of resource classes, from 32 out of the 34 apps. To understand the characteristics of these bugs, we conducted an empirical study, which revealed the root causes of frequent resource leaks in Android apps and common patterns of faults made by developers. With our findings, we further implemented a static checker to detect a common pattern of resource leaks in Android apps. Experiments showed that the checker can effectively locate real resource leaks in popular Android apps, confirming the usefulness of our work.
User Personalized Satisfaction Prediction via Multiple Instance Deep Learning
Venue: arXiv cs.IR 2016
Year: 2016

Community based question answering services have arisen as a popular knowledge sharing pattern for netizens. With abundant interactions among users, individuals are capable of obtaining satisfactory information. However, it is not effective for users to attain answers within minutes. Users have to check the progress over time until the satisfying answers submitted. We address this problem as a user personalized satisfaction prediction task. Existing methods usually exploit manual feature selection. It is not desirable as it requires careful design and is labor intensive. In this paper, we settle this issue by developing a new multiple instance deep learning framework. Specifically, in our settings, each question follows a weakly supervised learning multiple instance learning assumption, where its obtained answers can be regarded as instance sets and we define the question resolved with at least one satisfactory answer. We thus design an efficient framework exploiting multiple instance learning property with deep learning to model the question answer pairs. Extensive experiments on large scale datasets from Stack Exchange demonstrate the feasibility of our proposed framework in predicting askers personalized satisfaction. Our framework can be extended to numerous applications such as UI satisfaction Prediction, multi armed bandit problem, expert finding and so on.
Comparative study of histogram distance measures for re-identification
Venue: arXiv cs.CV 2016
Year: 2016

Color based re-identification methods usually rely on a distance function to measure the similarity between individuals. In this paper we study the behavior of several histogram distance measures in different color spaces. We wonder whether there is a particular histogram distance measure better than others, likewise also, if there is a color space that present better discrimination features. Several experiments are designed and evaluated in several images to obtain measures against various color spaces. We test in several image databases. A measure ranking is generated to calculate the area under the CMC, this area is the indicator used to evaluate which distance measure and color space present the best performance for the considered databases. Also, other parameters such as the image division in horizontal stripes and number of histogram bins, have been studied.
How I Stopped Worrying about the Twitter Archive at the Library of Congress and Learned to Build a Little One for Myself
Venue: arXiv cs.CY 2016
Year: 2016

Twitter is among the commonest sources of data employed in social media research mainly because of its convenient APIs to collect tweets. However, most researchers do not have access to the expensive Firehose and Twitter Historical Archive, and they must rely on data collected with free APIs whose representativeness has been questioned. In 2010 the Library of Congress announced an agreement with Twitter to provide researchers access to the whole Twitter Archive. However, such a task proved to be daunting and, at the moment of this writing, no researcher has had the opportunity to access such materials. Still, there have been experiences that proved that smaller searchable archives are feasible and, therefore, amenable for academics to build with relatively little resources. In this paper I describe my efforts to build one of such archives, covering the first three years of Twitter (actually from March 2006 to July 2009) and containing 1.48 billion tweets. If you carefully follow my directions you may have your very own little Twitter Historical Archive and you may forget about paying for historical tweets. Please note that to achieve that you should be proficient in some programming language, knowable about Twitter APIs, and have some basic knowledge on ElasticSearch; moreover, you may very well get disappointed by the quality of the contents of the final dataset.
Burrows-Wheeler transform and LCP array construction in constant space
Venue: arXiv cs.DS 2016
Year: 2016

In this article we extend the elegant in-place Burrows-Wheeler transform (BWT) algorithm proposed by Crochemore et al. (Crochemore et al., 2015). Our extension is twofold: we first show how to compute simultaneously the longest common prefix (LCP) array as well as the BWT, using constant additional space; we then show how to build the LCP array directly in compressed representation using Elias coding, still using constant additional space and with no asymptotic slowdown. Furthermore, we provide a time/space tradeoff for our algorithm when additional memory is allowed. Our algorithm runs in quadratic time, as does Crochemore et al.'s, and is supported by interesting properties of the BWT and of the LCP array, contributing to our understanding of the time/space tradeoff curve for building indexing structures.
Weakly Supervised Cascaded Convolutional Networks
Venue: arXiv cs.CV 2016
Year: 2016

Object detection is a challenging task in visual understanding domain, and even more so if the supervision is to be weak. Recently, few efforts to handle the task without expensive human annotations is established by promising deep neural network. A new architecture of cascaded networks is proposed to learn a convolutional neural network (CNN) under such conditions. We introduce two such architectures, with either two cascade stages or three which are trained in an end-to-end pipeline. The first stage of both architectures extracts best candidate of class specific region proposals by training a fully convolutional network. In the case of the three stage architecture, the middle stage provides object segmentation, using the output of the activation maps of first stage. The final stage of both architectures is a part of a convolutional neural network that performs multiple instance learning on proposals extracted in the previous stage(s). Our experiments on the PASCAL VOC 2007, 2010, 2012 and large scale object datasets, ILSVRC 2013, 2014 datasets show improvements in the areas of weakly-supervised object detection, classification and localization.
Feedback Control of the Pusher-Slider System: A Story of Hybrid and Underactuated Contact Dynamics
Venue: arXiv cs.RO 2016
Year: 2016

This paper investigates real-time control strategies for dynamical systems that involve frictional contact interactions. Hybridness and underactuation are key characteristics of these systems that complicate the design of feedback controllers. In this research, we examine and test a novel feedback controller design on a planar pushing system, where the purpose is to control the motion of a sliding object on a flat surface using a point robotic pusher. The pusher-slider is a simple dynamical system that retains many of the challenges that are typical of robotic manipulation tasks. Our results show that a model predictive control approach used in tandem with integer programming offers a powerful solution to capture the dynamic constraints associated with the friction cone as well as the hybrid nature of the contact. In order to achieve real-time control, simplifications are proposed to speed up the integer program. The concept of Family of Modes (FOM) is introduced to solve an online convex optimization problem by selecting a set of contact mode schedules that spans a large set of dynamic behaviors that can occur during the prediction horizon. The controller design is applied to stabilize the motion of a sliding object about a nominal trajectory, and to re-plan its trajectory in real-time to follow a moving target. We validate the controller design through numerical simulations and experimental results on an industrial ABB IRB 120 robotic arm.
On measuring performances of C-SPARQL and CQELS
Venue: arXiv cs.DB 2016
Year: 2016

To cope with the massive growth of semantic data streams, several RDF Stream Processing (RSP) engines have been implemented. The efficiency of their throughput, latency and memory consumption can be evaluated using available benchmarks such as LSBench and City- Bench. Nevertheless, these benchmarks lack an in-depth performance evaluation as some measurement metrics have not been considered. The main goal of this paper is to analyze the performance of two popular RSP engines, namely C-SPARQL and CQELS, when varying a set of performance metrics. More precisely, we evaluate the impact of stream rate, number of streams and window size on execution time as well as on memory consumption.