OpenRaiser/Intern-Atlas huggingface dataset:
D-SPACE4Cloud: A Design Tool for Big Data Applications
Venue: arXiv cs.DC 2016
Year: 2016

The last years have seen a steep rise in data generation worldwide, with the development and widespread adoption of several software projects targeting the Big Data paradigm. Many companies currently engage in Big Data analytics as part of their core business activities, nonetheless there are no tools and techniques to support the design of the underlying hardware configuration backing such systems. In particular, the focus in this report is set on Cloud deployed clusters, which represent a cost-effective alternative to on premises installations. We propose a novel tool implementing a battery of optimization and prediction techniques integrated so as to efficiently assess several alternative resource configurations, in order to determine the minimum cost cluster deployment satisfying QoS constraints. Further, the experimental campaign conducted on real systems shows the validity and relevance of the proposed method.
Revenue Maximization in Service Systems with Heterogeneous Customers
Venue: arXiv cs.GT 2016
Year: 2016

In this paper, we consider revenue maximization problem for a two server system in the presence of heterogeneous customers. We assume that the customers differ in their cost for unit delay and this is modeled as a continuous random variable with a distribution $F.$ We also assume that each server charges an admission price to each customer that decide to join its queue. We first consider the monopoly problem where both the servers belong to a single operator. The heterogeneity of the customer makes the analysis of the problem difficult. The difficulty lies in the inability to characterize the equilibrium queue arrival rates as a function of the admission prices. We provide an equivalent formulation with the queue arrival rates as the optimization variable simplifying the analysis for revenue rate maximization for the monopoly. We then consider the duopoly problem where each server competes with the other server to maximize its revenue rate. For the duopoly problem, the interest is to obtain the set of admission prices satisfying the Nash equilibrium conditions. While the problem is in general difficult to analyze, we consider the special case when the two servers are identical. For such a duopoly system, we obtain the necessary condition for existence of symmetric Nash equilibrium of the admission prices. The knowledge of the distribution $F$ characterizing the heterogeneity of the customers is necessary to solve the monopoly and the duopoly problem. However, for most practical scenarios, the functional form of $F$ may not be known to the system operator and in such cases, the revenue maximizing prices cannot be determined. In the last part of the paper, we provide a simple method to estimate the distribution $F$ by suitably varying the admission prices. We illustrate the method with some numerical examples.
Towards Multi-Agent Communication-Based Language Learning
Venue: arXiv cs.CL 2016
Year: 2016

We propose an interactive multimodal framework for language learning. Instead of being passively exposed to large amounts of natural text, our learners (implemented as feed-forward neural networks) engage in cooperative referential games starting from a tabula rasa setup, and thus develop their own language from the need to communicate in order to succeed at the game. Preliminary experiments provide promising results, but also suggest that it is important to ensure that agents trained in this way do not develop an adhoc communication code only effective for the game they are playing
Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics (extended version)
Venue: arXiv cs.DB 2016
Year: 2016

A database D may be inconsistent wrt a given set IC of integrity constraints. Consistent Query Answering (CQA) is the problem of computing from D the answers to a query that are consistent wrt IC . Consistent answers are invariant under all the repairs of D, i.e. the consistent instances that minimally depart from D. Three classes of repair have been considered in the literature: those that minimize set-theoretically the set of tuples in the symmetric difference; those that minimize the changes of attribute values, and those that minimize the cardinality of the set of tuples in the symmetric difference. The latter class has not been systematically investigated. In this paper we obtain algorithmic and complexity theoretic results for CQA under this cardinality-based repair semantics. We do this in the usual, static setting, but also in a dynamic framework where a consistent database is affected by a sequence of updates, which may make it inconsistent. We also establish comparative results with the other two kinds of repairs in the dynamic case.
Pure Exploration of Multi-armed Bandit Under Matroid Constraints
Venue: arXiv cs.LG 2016
Year: 2016

We study the pure exploration problem subject to a matroid constraint (Best-Basis) in a stochastic multi-armed bandit game. In a Best-Basis instance, we are given $n$ stochastic arms with unknown reward distributions, as well as a matroid $\mathcal{M}$ over the arms. Let the weight of an arm be the mean of its reward distribution. Our goal is to identify a basis of $\mathcal{M}$ with the maximum total weight, using as few samples as possible. The problem is a significant generalization of the best arm identification problem and the top-$k$ arm identification problem, which have attracted significant attentions in recent years. We study both the exact and PAC versions of Best-Basis, and provide algorithms with nearly-optimal sample complexities for these versions. Our results generalize and/or improve on several previous results for the top-$k$ arm identification problem and the combinatorial pure exploration problem when the combinatorial constraint is a matroid.
Optimal Jammer Placement in Wireless Localization Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this study, the optimal jammer placement problem is proposed and analyzed for wireless localization systems. In particular, the optimal location of a jammer node is obtained by maximizing the minimum of the Cramer-Rao lower bounds (CRLBs) for a number of target nodes under location related constraints for the jammer node. For scenarios with more than two target nodes, theoretical results are derived to specify conditions under which the jammer node is located as close to a certain target node as possible, or the optimal location of the jammer node is determined by two of the target nodes. Also, explicit expressions are provided for the optimal location of the jammer node in the presence of two target nodes. In addition, in the absence of distance constraints for the jammer node, it is proved, for scenarios with more than two target nodes, that the optimal jammer location lies on the convex hull formed by the locations of the target nodes and is determined by two or three of the target nodes, which have equalized CRLBs. Numerical examples are presented to provide illustrations of the theoretical results in different scenarios.
An Efficient Likelihood-Based Modulation Classification Algorithm for MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

Blind algorithms for multiple-input multiple-output (MIMO) signals interception have recently received considerable attention because of their important applications in modern civil and military communication fields. One key step in the interception process is to blindly recognize the modulation type of the MIMO signals. This can be performed by employing a Modulation Classification (MC) algorithm, which can be feature-based or likelihood-based. To overcome the problems associated with the existing likelihood-based MC algorithms, a new algorithm is developed in this paper. We formulated the MC problem as maximizing a global likelihood function formed by combining the likelihood functions for the estimated transmitted signals, where Minimum Mean Square Error (MMSE) filtering is employed to separate the MIMO channel into several sub-channels. Simulation results showed that the proposed algorithm works well under various operating conditions, and performs close to the performance upper bound with reasonable complexity.
A note on privacy preserving iteratively reweighted least squares
Venue: arXiv cs.CR 2016
Year: 2016

Iteratively reweighted least squares (IRLS) is a widely-used method in machine learning to estimate the parameters in the generalised linear models. In particular, IRLS for L1 minimisation under the linear model provides a closed-form solution in each step, which is a simple multiplication between the inverse of the weighted second moment matrix and the weighted first moment vector. When dealing with privacy sensitive data, however, developing a privacy preserving IRLS algorithm faces two challenges. First, due to the inversion of the second moment matrix, the usual sensitivity analysis in differential privacy incorporating a single datapoint perturbation gets complicated and often requires unrealistic assumptions. Second, due to its iterative nature, a significant cumulative privacy loss occurs. However, adding a high level of noise to compensate for the privacy loss hinders from getting accurate estimates. Here, we develop a practical algorithm that overcomes these challenges and outputs privatised and accurate IRLS solutions. In our method, we analyse the sensitivity of each moments separately and treat the matrix inversion and multiplication as a post-processing step, which simplifies the sensitivity analysis. Furthermore, we apply the {\it{concentrated differential privacy}} formalism, a more relaxed version of differential privacy, which requires adding a significantly less amount of noise for the same level of privacy guarantee, compared to the conventional and advanced compositions of differentially private mechanisms.
Deeply-Fused Nets
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we present a novel deep learning approach, deeply-fused nets. The central idea of our approach is deep fusion, i.e., combine the intermediate representations of base networks, where the fused output serves as the input of the remaining part of each base network, and perform such combinations deeply over several intermediate representations. The resulting deeply fused net enjoys several benefits. First, it is able to learn multi-scale representations as it enjoys the benefits of more base networks, which could form the same fused network, other than the initial group of base networks. Second, in our suggested fused net formed by one deep and one shallow base networks, the flows of the information from the earlier intermediate layer of the deep base network to the output and from the input to the later intermediate layer of the deep base network are both improved. Last, the deep and shallow base networks are jointly learnt and can benefit from each other. More interestingly, the essential depth of a fused net composed from a deep base network and a shallow base network is reduced because the fused net could be composed from a less deep base network, and thus training the fused net is less difficult than training the initial deep base network. Empirical results demonstrate that our approach achieves superior performance over two closely-related methods, ResNet and Highway, and competitive performance compared to the state-of-the-arts.
Isolating Mice and Elephant in Data Centers
Venue: arXiv cs.NI 2016
Year: 2016

Data centers traffic is composed by numerous latency-sensitive "mice" flows, which is consisted of only several packets, and a few throughput-sensitive "elephant" flows, which occupy more than 80% of overall load. Generally, the short-lived "mice" flows induce transient congestion and the long-lived "elephant" flows cause persistent congestion. The network congestion is a major performance inhibitor. Conventionally, the hop-by-hop and end-to-end flow control mechanisms are employed to relief transient and persistent congestion, respectively. However, in face of the mixture of elephants and mice, we find the hybrid congestion control scheme including hop-by-hop and end-to-end flow control mechanisms suffers from serious performance impairments. As a step further, our in-depth analysis reveals that the hybrid scheme performs poor at latency of mice and throughput of elephant. Motivated by this understanding, we argue for isolating mice and elephants in different queues, such that the hop-by-hop and end-to-end flow control mechanisms are independently imposed to short-lived and long-lived flows, respectively. Our solution is readily-deployable and compatible with current commodity network devices and can leverage various congestion control mechanisms. Extensive simulations show that our proposal of isolation can simultaneously improve the latency of mice by at least 30% and the link utilization to almost 100%.
Design and development a children's speech database
Venue: arXiv cs.CL 2016
Year: 2016

The report presents the process of planning, designing and the development of a database of spoken children's speech whose native language is Bulgarian. The proposed model is designed for children between the age of 4 and 6 without speech disorders, and reflects their specific capabilities. At this age most children cannot read, there is no sustained concentration, they are emotional, etc. The aim is to unite all the media information accompanying the recording and processing of spoken speech, thereby to facilitate the work of researchers in the field of speech recognition. This database will be used for the development of systems for children's speech recognition, children's speech synthesis systems, games which allow voice control, etc. As a result of the proposed model a prototype system for speech recognition is presented.
C-FLAT: Control-FLow ATtestation for Embedded Systems Software
Venue: arXiv cs.CR 2016
Year: 2016

Remote attestation is a crucial security service particularly relevant to increasingly popular IoT (and other embedded) devices. It allows a trusted party (verifier) to learn the state of a remote, and potentially malware-infected, device (prover). Most existing approaches are static in nature and only check whether benign software is initially loaded on the prover. However, they are vulnerable to run-time attacks that hijack the application's control or data flow, e.g., via return-oriented programming or data-oriented exploits. As a concrete step towards more comprehensive run-time remote attestation, we present the design and implementation of Control- FLow ATtestation (C-FLAT) that enables remote attestation of an application's control-flow path, without requiring the source code. We describe a full prototype implementation of C-FLAT on Raspberry Pi using its ARM TrustZone hardware security extensions. We evaluate C-FLAT's performance using a real-world embedded (cyber-physical) application, and demonstrate its efficacy against control-flow hijacking attacks.
DeepCut: Object Segmentation from Bounding Box Annotations using Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose DeepCut, a method to obtain pixelwise object segmentations given an image dataset labelled with bounding box annotations. It extends the approach of the well-known GrabCut method to include machine learning by training a neural network classifier from bounding box annotations. We formulate the problem as an energy minimisation problem over a densely-connected conditional random field and iteratively update the training targets to obtain pixelwise object segmentations. Additionally, we propose variants of the DeepCut method and compare those to a naive approach to CNN training under weak supervision. We test its applicability to solve brain and lung segmentation problems on a challenging fetal magnetic resonance dataset and obtain encouraging results in terms of accuracy.
Timing Channel: Achievable Rate in the Finite Block-Length Regime
Venue: arXiv cs.IT 2016
Year: 2016

The exponential server timing channel is known to be the simplest, and in some sense canonical, queuing timing channel. The capacity of this infinite-memory channel is known. Here, we discuss practical finite-length restrictions on the codewords and attempt to understand the maximal rate that can be achieved for a target error probability. By using Markov chain analysis, we prove a lower bound on the maximal channel coding rate achievable at blocklength $n$ and error probability $ε$. The bound is approximated by $C- n^{-1/2} σQ^{-1}(ε)$ where $Q$ denotes the Q-function and $σ^2$ is the asymptotic variance of the underlying Markov chain. A closed form expression for $σ^2$ is given.
Multi-Object Tracking and Identification over Sets
Venue: arXiv cs.CV 2016
Year: 2016

The ability for an autonomous agent or robot to track and identify potentially multiple objects in a dynamic environment is essential for many applications, such as automated surveillance, traffic monitoring, human-robot interaction, etc. The main challenge is due to the noisy and incomplete perception including inevitable false negative and false positive errors from a low-level detector. In this paper, we propose a novel multi-object tracking and identification over sets approach to address this challenge. We define joint states and observations both as finite sets, and develop motion and observation functions accordingly. The object identification problem is then formulated and solved by using expectation-maximization methods. The set formulation enables us to avoid directly performing observation-to-object association. We empirically confirm that the overall algorithm outperforms the state-of-the-art in a popular PETS dataset.
Adaptive Neural Compilation
Venue: arXiv cs.AI 2016
Year: 2016

This paper proposes an adaptive neural-compilation framework to address the problem of efficient program learning. Traditional code optimisation strategies used in compilers are based on applying pre-specified set of transformations that make the code faster to execute without changing its semantics. In contrast, our work involves adapting programs to make them more efficient while considering correctness only on a target input distribution. Our approach is inspired by the recent works on differentiable representations of programs. We show that it is possible to compile programs written in a low-level language to a differentiable representation. We also show how programs in this representation can be optimised to make them efficient on a target distribution of inputs. Experimental results demonstrate that our approach enables learning specifically-tuned algorithms for given data distributions with a high success rate.
Compliant Conditions for Polynomial Time Approximation of Operator Counts
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we develop a computationally simpler version of the operator count heuristic for a particular class of domains. The contribution of this abstract is threefold, we (1) propose an efficient closed form approximation to the operator count heuristic using the Lagrangian dual; (2) leverage compressed sensing techniques to obtain an integer approximation for operator counts in polynomial time; and (3) discuss the relationship of the proposed formulation to existing heuristics and investigate properties of domains where such approaches appear to be useful.
Towards Assistive Feeding with a General-Purpose Mobile Manipulator
Venue: arXiv cs.RO 2016
Year: 2016

General-purpose mobile manipulators have the potential to serve as a versatile form of assistive technology. However, their complexity creates challenges, including the risk of being too difficult to use. We present a proof-of-concept robotic system for assistive feeding that consists of a Willow Garage PR2, a high-level web-based interface, and specialized autonomous behaviors for scooping and feeding yogurt. As a step towards use by people with disabilities, we evaluated our system with 5 able-bodied participants. All 5 successfully ate yogurt using the system and reported high rates of success for the system's autonomous behaviors. Also, Henry Evans, a person with severe quadriplegia, operated the system remotely to feed an able-bodied person. In general, people who operated the system reported that it was easy to use, including Henry. The feeding system also incorporates corrective actions designed to be triggered either autonomously or by the user. In an offline evaluation using data collected with the feeding system, a new version of our multimodal anomaly detection system outperformed prior versions.
The Many Worlds of Modal λ-calculi: I. Curry-Howard for Necessity, Possibility and Time
Venue: arXiv cs.LO 2016
Year: 2016

This is a survey of λ-calculi that, through the Curry-Howard isomorphism, correspond to constructive modal logics. We cover the prehistory of the subject and then concentrate on the developments that took place in the 1990s and early 2000s. We discuss logical aspects, modal λ-calculi, and their categorical semantics. The logics underlying the calculi surveyed are constructive versions of K, K4, S4, and LTL.
Towards optimal nonlinearities for sparse recovery using higher-order statistics
Venue: arXiv cs.IT 2016
Year: 2016

We consider machine learning techniques to develop low-latency approximate solutions to a class of inverse problems. More precisely, we use a probabilistic approach for the problem of recovering sparse stochastic signals that are members of the $\ell_p$-balls. In this context, we analyze the Bayesian mean-square-error (MSE) for two types of estimators: (i) a linear estimator and (ii) a structured estimator composed of a linear operator followed by a Cartesian product of univariate nonlinear mappings. By construction, the complexity of the proposed nonlinear estimator is comparable to that of its linear counterpart since the nonlinear mapping can be implemented efficiently in hardware by means of look-up tables (LUTs). The proposed structure lends itself to neural networks and iterative shrinkage/thresholding-type algorithms restricted to a single iterate (e.g. due to imposed hardware or latency constraints). By resorting to an alternating minimization technique, we obtain a sequence of optimized linear operators and nonlinear mappings that converge in the MSE objective. The result is attractive for real-time applications where general iterative and convex optimization methods are infeasible.
The Importance of Worker Reputation Information in Microtask-Based Crowd Work Systems
Venue: arXiv cs.HC 2016
Year: 2016

This paper presents the first systematic investigation of the potential performance gains for crowd work systems, deriving from available information at the requester about individual worker reputation. In particular, we first formalize the optimal task assignment problem when workers' reputation estimates are available, as the maximization of a monotone (submodular) function subject to Matroid constraints. Then, being the optimal problem NP-hard, we propose a simple but efficient greedy heuristic task allocation algorithm. We also propose a simple "maximum a-posteriori" decision rule and a decision algorithm based on message passing. Finally, we test and compare different solutions, showing that system performance can greatly benefit from information about workers' reputation. Our main findings are that: i) even largely inaccurate estimates of workers' reputation can be effectively exploited in the task assignment to greatly improve system performance; ii) the performance of the maximum a-posteriori decision rule quickly degrades as worker reputation estimates become inaccurate; iii) when workers' reputation estimates are significantly inaccurate, the best performance can be obtained by combining our proposed task assignment algorithm with the message-passing decision algorithm.