OpenRaiser/Intern-Atlas huggingface dataset:
Fast and Energy-Efficient CNN Inference on IoT Devices
Venue: arXiv cs.DC 2016
Year: 2016

Convolutional Neural Networks (CNNs) exhibit remarkable performance in various machine learning tasks. As sensor-equipped internet of things (IoT) devices permeate into every aspect of modern life, it is increasingly important to run CNN inference, a computationally intensive application, on resource constrained devices. We present a technique for fast and energy-efficient CNN inference on mobile SoC platforms, which are projected to be a major player in the IoT space. We propose techniques for efficient parallelization of CNN inference targeting mobile GPUs, and explore the underlying tradeoffs. Experiments with running Squeezenet on three different mobile devices confirm the effectiveness of our approach. For further study, please refer to the project repository available on our GitHub page: https://github.com/mtmd/Mobile_ConvNet
Deep Recurrent Convolutional Neural Network: Improving Performance For Speech Recognition
Venue: arXiv cs.CL 2016
Year: 2016

A deep learning approach has been widely applied in sequence modeling problems. In terms of automatic speech recognition (ASR), its performance has significantly been improved by increasing large speech corpus and deeper neural network. Especially, recurrent neural network and deep convolutional neural network have been applied in ASR successfully. Given the arising problem of training speed, we build a novel deep recurrent convolutional network for acoustic modeling and then apply deep residual learning to it. Our experiments show that it has not only faster convergence speed but better recognition accuracy over traditional deep convolutional recurrent network. In the experiments, we compare the convergence speed of our novel deep recurrent convolutional networks and traditional deep convolutional recurrent networks. With faster convergence speed, our novel deep recurrent convolutional networks can reach the comparable performance. We further show that applying deep residual learning can boost the convergence speed of our novel deep recurret convolutional networks. Finally, we evaluate all our experimental networks by phoneme error rate (PER) with our proposed bidirectional statistical n-gram language model. Our evaluation results show that our newly proposed deep recurrent convolutional network applied with deep residual learning can reach the best PER of 17.33\% with the fastest convergence speed on TIMIT database. The outstanding performance of our novel deep recurrent convolutional neural network with deep residual learning indicates that it can be potentially adopted in other sequential problems.
Approximate Furthest Neighbor with Application to Annulus Query
Venue: arXiv cs.DS 2016
Year: 2016

Much recent work has been devoted to approximate nearest neighbor queries. Motivated by applications in recommender systems, we consider approximate furthest neighbor (AFN) queries and present a simple, fast, and highly practical data structure for answering AFN queries in high- dimensional Euclidean space. The method builds on the technique of In- dyk (SODA 2003), storing random projections to provide sublinear query time for AFN. However, we introduce a different query algorithm, improving on Indyk's approximation factor and reducing the running time by a logarithmic factor. We also present a variation based on a query- independent ordering of the database points; while this does not have the provable approximation factor of the query-dependent data structure, it offers significant improvement in time and space complexity. We give a theoretical analysis, and experimental results. As an application, the query-dependent approach is used for deriving a data structure for the approximate annulus query problem, which is defined as follows: given an input set S and two parameters r > 0 and w >= 1, construct a data structure that returns for each query point q a point p in S such that the distance between p and q is at least r/w and at most wr.
Limbo: A Fast and Flexible Library for Bayesian Optimization
Venue: arXiv cs.LG 2016
Year: 2016

Limbo is an open-source C++11 library for Bayesian optimization which is designed to be both highly flexible and very fast. It can be used to optimize functions for which the gradient is unknown, evaluations are expensive, and runtime cost matters (e.g., on embedded systems or robots). Benchmarks on standard functions show that Limbo is about 2 times faster than BayesOpt (another C++ library) for a similar accuracy.
SPEAKE(a)R: Turn Speakers to Microphones for Fun and Profit
Venue: arXiv cs.CR 2016
Year: 2016

It is possible to manipulate the headphones (or earphones) connected to a computer, silently turning them into a pair of eavesdropping microphones - with software alone. The same is also true for some types of loudspeakers. This paper focuses on this threat in a cyber-security context. We present SPEAKE(a)R, a software that can covertly turn the headphones connected to a PC into a microphone. We present technical background and explain why most of PCs and laptops are susceptible to this type of attack. We examine an attack scenario in which malware can use a computer as an eavesdropping device, even when a microphone is not present, muted, taped, or turned off. We measure the signal quality and the effective distance, and survey the defensive countermeasures.
Randomized Mechanisms for Selling Reserved Instances in Cloud
Venue: arXiv cs.GT 2016
Year: 2016

Selling reserved instances (or virtual machines) is a basic service in cloud computing. In this paper, we consider a more flexible pricing model for instance reservation, in which a customer can propose the time length and number of resources of her request, while in today's industry, customers can only choose from several predefined reservation packages. Under this model, we design randomized mechanisms for customers coming online to optimize social welfare and providers' revenue. We first consider a simple case, where the requests from the customers do not vary too much in terms of both length and value density. We design a randomized mechanism that achieves a competitive ratio $\frac{1}{42}$ for both \emph{social welfare} and \emph{revenue}, which is a improvement as there is usually no revenue guarantee in previous works such as \cite{azar2015ec,wang2015selling}. This ratio can be improved up to $\frac{1}{11}$ when we impose a realistic constraint on the maximum number of resources used by each request. On the hardness side, we show an upper bound $\frac{1}{3}$ on competitive ratio for any randomized mechanism. We then extend our mechanism to the general case and achieve a competitive ratio $\frac{1}{42\log k\log T}$ for both social welfare and revenue, where $T$ is the ratio of the maximum request length to the minimum request length and $k$ is the ratio of the maximum request value density to the minimum request value density. This result outperforms the previous upper bound $\frac{1}{CkT}$ for deterministic mechanisms \cite{wang2015selling}. We also prove an upper bound $\frac{2}{\log 8kT}$ for any randomized mechanism. All the mechanisms we provide are in a greedy style. They are truthful and easy to be integrated into practical cloud systems.
SMCL - Stochastic Model Checker for Learning in Games
Venue: arXiv cs.GT 2016
Year: 2016

A stochastic model checker is presented for analysing the performance of game-theoretic learning algorithms. The method enables the comparison of short-term behaviour of learning algorithms intended for practical use. The procedure of comparison is automated and it can be tuned for accuracy and speed. Users can choose from among various learning algorithms to select a suitable one for a given practical problem. The powerful performance of the method is enabled by a novel behaviour-similarity-relation, which compacts large state spaces into small ones. The stochastic model checking tool is tested on a set of examples classified into four categories to demonstrate the effectiveness of selecting suitable algorithms for distributed decision making.
Can Co-robots Learn to Teach?
Venue: arXiv cs.RO 2016
Year: 2016

We explore beyond existing work on learning from demonstration by asking the question: Can robots learn to teach?, that is, can a robot autonomously learn an instructional policy from expert demonstration and use it to instruct or collaborate with humans in executing complex tasks in uncertain environments? In this paper we pursue a solution to this problem by leveraging the idea that humans often implicitly decompose a higher level task into several subgoals whose execution brings the task closer to completion. We propose Dirichlet process based non-parametric Inverse Reinforcement Learning (DPMIRL) approach for reward based unsupervised clustering of task space into subgoals. This approach is shown to capture the latent subgoals that a human teacher would have utilized to train a novice. The notion of action primitive is introduced as the means to communicate instruction policy to humans in the least complicated manner, and as a computationally efficient tool to segment demonstration data. We evaluate our approach through experiments on hydraulic actuated scaled model of an excavator and evaluate and compare different teaching strategies utilized by the robot.
Purchasing a C_4 online
Venue: arXiv cs.DS 2016
Year: 2016

Let $G$ be a graph with edge set $(e_1,e_2,...e_N)$. We independently associate to each edge $e_i$ of $G$ a cost ${x}_i$ that is drawn from a Uniform [0, 1] distribution. Suppose $\mathcal{F}$ is a set of targeted structures that consists of subgraphs of $G$. We would like to buy a subset of $\mathcal{F}$ at small cost, however we do not know a priori the values of the random variables ${x}_1,...,{x}_N$. Instead, we inspect the random variables $x_i$ one at a time. As soon as we inspect the random variable associated with the cost of an edge we have to decide whether we want to buy that edge or reject it for ever. In the present paper we consider the case where $G$ is the complete graph on $n$ vertices and $\mathcal{F}$ is the set of all $C_4$ -cycles on 4 vertices- out of which we want to buy one.
A causal framework for discovering and removing direct and indirect discrimination
Venue: arXiv cs.LG 2016
Year: 2016

Anti-discrimination is an increasingly important task in data science. In this paper, we investigate the problem of discovering both direct and indirect discrimination from the historical data, and removing the discriminatory effects before the data is used for predictive analysis (e.g., building classifiers). We make use of the causal network to capture the causal structure of the data. Then we model direct and indirect discrimination as the path-specific effects, which explicitly distinguish the two types of discrimination as the causal effects transmitted along different paths in the network. Based on that, we propose an effective algorithm for discovering direct and indirect discrimination, as well as an algorithm for precisely removing both types of discrimination while retaining good data utility. Different from previous works, our approaches can ensure that the predictive models built from the modified data will not incur discrimination in decision making. Experiments using real datasets show the effectiveness of our approaches.
Sar image despeckling based on nonlocal similarity sparse decomposition
Venue: arXiv cs.CV 2016
Year: 2016

This letter presents a method of synthetic aperture radar (SAR) image despeckling aimed to preserve the detail information while suppressing speckle noise. This method combines the nonlocal self-similarity partition and a proposed modified sparse decomposition. The nonlocal partition method groups a series of structure-similarity data sets. Each data set has a good sparsity for learning an over-complete dictionary in sparse representation. In the sparse decomposition, we propose a novel method to identify principal atoms from over-complete dictionary to form a principal dictionary. Despeckling is performed on each data set over the principal dictionary with principal atoms. Experimental results demonstrate that the proposed method can achieve high performances in terms of both speckle noise reduction and structure details preservation.
Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising
Venue: arXiv cs.DS 2016
Year: 2016

In this work, we study the guaranteed delivery model which is widely used in online display advertising. In the guaranteed delivery scenario, ad exposures (which are also called impressions in some works) to users are guaranteed by contracts signed in advance between advertisers and publishers. A crucial problem for the advertising platform is how to fully utilize the valuable user traffic to generate as much as possible revenue. Different from previous works which usually minimize the penalty of unsatisfied contracts and some other cost (e.g. representativeness), we propose the novel consumption minimization model, in which the primary objective is to minimize the user traffic consumed to satisfy all contracts. Under this model, we develop a near optimal method to deliver ads for users. The main advantage of our method lies in that it consumes nearly as least as possible user traffic to satisfy all contracts, therefore more contracts can be accepted to produce more revenue. It also enables the publishers to estimate how much user traffic is redundant or short so that they can sell or buy this part of traffic in bulk in the exchange market. Furthermore, it is robust with regard to priori knowledge of user type distribution. Finally, the simulation shows that our method outperforms the traditional state-of-the-art methods.
Future Wireless Network: MyNET Platform and End-to-End Network Slicing
Venue: arXiv cs.NI 2016
Year: 2016

Future wireless networks are facing new challenges. These new challenges require new solutions and strategies of the network deployment, management, and operation. Many driving factors are decisive in the re-definition and re-design of the future wireless network architecture. In the previously published paper "5G Wireless Network - MyNET and SONAC", MyNET and SONAC, a future network architecture, are described. This paper elaborates MyNET platform with more details. The design principles of MyNET architecture, the development of MyNET platform, the functions of MyNET platform, the automation of the creation and the management of end-to-end slices by MyNET, and the new capabilities enabled by MyNET are described in details.
The Reactive Synthesis Competition: SYNTCOMP 2016 and Beyond
Venue: arXiv cs.LO 2016
Year: 2016

We report on the design of the third reactive synthesis competition (SYNTCOMP 2016), including a major extension of the competition to specifications in full linear temporal logic. We give a brief overview of the synthesis problem as considered in SYNTCOMP, and present the rules of the competition in 2016, as well as the ideas behind our design choices. Furthermore, we evaluate the recent changes to the competition based on the experiences with SYNTCOMP 2016. Finally, we give an outlook on further changes and extensions of the competition that are planned for the future.
Approaching Symbolic Parallelization by Synthesis of Recurrence Decompositions
Venue: arXiv cs.PL 2016
Year: 2016

We present GraSSP, a novel approach to perform automated parallelization relying on recent advances in formal verification and synthesis. GraSSP augments an existing sequential program with an additional functionality to decompose data dependencies in loop iterations, to compute partial results, and to compose them together. We show that for some classes of the sequential prefix sum problems, such parallelization can be performed efficiently.
A Novel Control-flow based Intrusion Detection Technique for Big Data Systems
Venue: arXiv cs.CR 2016
Year: 2016

Security and distributed infrastructure are two of the most common requirements for big data software. But the security features of the big data platforms are still premature. It is critical to identify, modify, test and execute some of the existing security mechanisms before using them in the big data world. In this paper, we propose a novel intrusion detection technique that understands and works according to the needs of big data systems. Our proposed technique identifies program level anomalies using two methods - a profiling method that models application behavior by creating process signatures from control-flow graphs; and a matching method that checks for coherence among the replica nodes of a big data system by matching the process signatures. The profiling method creates a process signature by reducing the control-flow graph of a process to a set of minimum spanning trees and then creates a hash of that set. The matching method first checks for similarity in process behavior by matching the received process signature with the local signature and then shares the result with all replica datanodes for consensus. Experimental results show only 0.8% overhead due to the proposed technique when tested on the hadoop map-reduce examples in real-time.
A Survey on Privacy-preserving Schemes for Smart Grid Communications
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, we present a comprehensive survey of privacy-preserving schemes for Smart Grid communications. Specifically, we select and in-detail examine thirty privacy preserving schemes developed for or applied in the context of Smart Grids. Based on the communication and system models, we classify these schemes that are published between 2013 and 2016, in five categories, including, 1) Smart grid with the advanced metering infrastructure, 2) Data aggregation communications, 3) Smart grid marketing architecture, 4) Smart community of home gateways, and 5) Vehicle-to grid architecture. For each scheme, we survey the attacks of leaking privacy, countermeasures, and game theoretic approaches. In addition, we review the survey articles published in the recent years that deal with Smart Grids communications, applications, standardization, and security. Based on the current survey, several recommendations for further research are discussed at the end of this paper.
Patterns in treeshelves
Venue: arXiv cs.DM 2016
Year: 2016

We study the distribution and the popularity of left children on sets of treeshelves avoiding a pattern of size three. (Treeshelves are ordered binary increasing trees where every child is connected to its parent by a left or a right link.) The considered patterns are sub-treeshelves, and for each such a pattern we provide exponential generating function for the corresponding distribution and popularity. Finally, we present constructive bijections between treeshelves avoiding a pattern of size three and some classes of simpler combinatorial objects.
SimAthens: A spatial microsimulation approach to the estimation and analysis of small-area income distributions and poverty rates in Athens, Greece
Venue: arXiv cs.MA 2016
Year: 2016

Published during a severe economic crisis, this study presents the first spatial microsimulation model for the analysis of income inequalities and poverty in Greece. First, we present a brief overview of the method and discuss its potential for the analysis of multidimensional poverty and income inequality in Greece. We then present the SimAthens model, based on a combination of small-area demographic and socioeconomic information available from the Greek census of population with data from the European Union Statistics on Income and Living Conditions (EU-SILC). The model is based on an iterative proportional fitting (IPF) algorithm, and is used to reweigh EU-SILC records to fit in small-area descriptions for Athens based on 2001 and 2011 censuses. This is achieved by using demographic and socioeconomic characteristics as constraint variables. Finally, synthesis of the labor market and occupations are chosen as the main variables for externally validating our results, in order to verify the integrity of the model. Results of this external validation process are found to be extremely satisfactory, indicating a high goodness of fit between simulated and real values. Finally, the study presents a number of model outputs, illustrating changes in social and economic geography, during a severe economic crisis, offering a great opportunity for discussing further potential of this model in policy analysis.
A General Theory of Information and Computation
Venue: arXiv cs.IT 2016
Year: 2016

This paper fills a gap in our understanding of the interaction between information and computation. It unifies other approaches to measuring information like Kolmogorov complexity and Shannon information. We define a theory about information flow in deterministic computing based on three fundamental observations: 1) Information is measured in logarithms, 2) All countable sets contain the same amount of information and 3) Deterministic computing does not create information. We analyze the flow of information through computational processes: exactly, for primitive recursive functions and elementary artithmetical operations and, under maximal entropy, for polynomial functions and diophantine equations. Thus we get, by the MRDP-theorem, a theory of flow of information for general computable functions. We prove some results like the Fueter-Pólya conjecture and the existence of an information conserving enumeration of all finite sets of numbers. We also show that the information flow in more complex derivatives of the primitive recursive functions like addition and multiplication is not trivial: in particular associativity is not information efficient for addition. Using the Cantor pairing function we develop a universal measuring device for partitions of the set of finite sets of numbers. We show that these sets can be enumerated by a polynomial function when ordered by cardinality, but not when ordered by their sums.
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
Venue: arXiv cs.DS 2016
Year: 2016

In the Minimum k-Union problem (MkU) we are given a set system with n sets and are asked to select k sets in order to minimize the size of their union. Despite being a very natural problem, it has received surprisingly little attention: the only known approximation algorithm is an $O(\sqrt{n})$-approximation due to [Chlamtáč et al APPROX '16]. This problem can also be viewed as the bipartite version of the Small Set Vertex Expansion problem (SSVE), which we call the Small Set Bipartite Vertex Expansion problem (SSBVE). SSVE, in which we are asked to find a set of k nodes to minimize their vertex expansion, has not been as well studied as its edge-based counterpart Small Set Expansion (SSE), but has recently received significant attention, e.g. [Louis-Makarychev APPROX '15]. However, due to the connection to Unique Games and hardness of approximation the focus has mostly been on sets of size $k = Ω(n)$, while we focus on the case of general $k$, for which no polylogarithmic approximation is known. We improve the upper bound for this problem by giving an $n^{1/4+\varepsilon}$ approximation for SSBVE for any constant $\varepsilon > 0$. Our algorithm follows in the footsteps of Densest $k$-Subgraph (DkS) and related problems, by designing a tight algorithm for random models, and then extending it to give the same guarantee for arbitrary instances. Moreover, we show that this is tight under plausible complexity conjectures: it cannot be approximated better than $O(n^{1/4})$ assuming an extension of the so-called "Dense vs Random" conjecture for DkS to hypergraphs. We show that the same bound is also matched by an integrality gap for a super-constant number of rounds of the Sherali-Adams LP hierarchy, and an even worse integrality gap for the natural SDP relaxation. Finally, we design a simple bicriteria $\tilde O(\sqrt{n})$ approximation for the more general SSVE problem.