OpenRaiser/Intern-Atlas huggingface dataset:
A Tractable Framework for the Analysis of Dense Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2018
Year: 2018

This paper investigates the downlink performance of K-tier heteregeneous cellular networks (HCNs) under general settings. First, Gaussian approximation bounds for the standardized aggregate wireless interference (AWI) in dense K-tier HCNs are obtained for when base stations (BSs) in each tier are distributed over the plane according to a spatial and general Poisson point process. The Kolmogorov-Smirnov (KS) distance is used to measure deviations of the distribution of the standardized AWI from the standard normal distribution. An explicit and analytical expression bounding the KS distance between these two distributions is obtained as a function of a broad range of network parameters such as per-tier transmission power levels, per-tier BS intensity, BS locations, general fading statistics, and general bounded path-loss models. Bounds achieve a good statistical match between the standardized AWI distribution and its normal approximation even for moderately dense HCNs. Second, various spatial performance metrics of interest such as outage capacity, ergodic capacity and area spectral efficiency in the downlink of K-tier HCNs for general signal propogation models are investigated by making use of the derived distribution approximation results. Considering two specific BS association policies, it is shown that the derived performance bounds track the actual performance metrics reasonably well for a wide range of BS intensities, with the gap among them becoming negligibly small for denser HCN deployments.
Automatically 'Verifying' Discrete-Time Complex Systems through Learning, Abstraction and Refinement
Venue: arXiv cs.SE 2018
Year: 2018

Precisely modeling complex systems like cyber-physical systems is challenging, which often render model-based system verification techniques like model checking infeasible. To overcome this challenge, we propose a method called LAR to automatically `verify' such complex systems through a combination of learning, abstraction and refinement from a set of system log traces. We assume that log traces and sampling frequency are adequate to capture `enough' behaviour of the system. Given a safety property and the concrete system log traces as input, LAR automatically learns and refines system models, and produces two kinds of outputs. One is a counterexample with a bounded probability of being spurious. The other is a probabilistic model based on which the given property is `verified'. The model can be viewed as a proof obligation, i.e., the property is verified if the model is correct. It can also be used for subsequent system analysis activities like runtime monitoring or model-based testing. Our method has been implemented as a self-contained software toolkit. The evaluation on multiple benchmark systems as well as a real-world water treatment system shows promising results.
Combinatorial Multi-Armed Bandit with General Reward Functions
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we study the stochastic combinatorial multi-armed bandit (CMAB) framework that allows a general nonlinear reward function, whose expected value may not depend only on the means of the input random variables but possibly on the entire distributions of these variables. Our framework enables a much larger class of reward functions such as the $\max()$ function and nonlinear utility functions. Existing techniques relying on accurate estimations of the means of random variables, such as the upper confidence bound (UCB) technique, do not work directly on these functions. We propose a new algorithm called stochastically dominant confidence bound (SDCB), which estimates the distributions of underlying random variables and their stochastically dominant confidence bounds. We prove that SDCB can achieve $O(\log{T})$ distribution-dependent regret and $\tilde{O}(\sqrt{T})$ distribution-independent regret, where $T$ is the time horizon. We apply our results to the $K$-MAX problem and expected utility maximization problems. In particular, for $K$-MAX, we provide the first polynomial-time approximation scheme (PTAS) for its offline problem, and give the first $\tilde{O}(\sqrt T)$ bound on the $(1-ε)$-approximation regret of its online problem, for any $ε>0$.
An Efficient Optimal Algorithm for the Successive Minima Problem
Venue: arXiv cs.IT 2018
Year: 2018

In many applications including integer-forcing linear multiple-input and multiple-output (MIMO) receiver design, one needs to solve a successive minima problem (SMP) on an $n$-dimensional lattice to get an optimal integer coefficient matrix $\A^\star\in \mathbb{Z}^{n\times n}$. In this paper, we first propose an efficient optimal SMP algorithm with an $\bigO(n^2)$ memory complexity. The main idea behind the new algorithm is it first initializes with a suitable suboptimal solution, which is then updated, via a novel algorithm with only $\bigO(n^2)$ flops in each updating, until $\A^{\star}$ is obtained. Different from existing algorithms which find $\A^\star$ column by column through using a sphere decoding search strategy $n$ times, the new algorithm uses a search strategy once only. We then rigorously prove the optimality of the proposed algorithm. Furthermore, we theoretically analyze its complexity. In particular, we not only show that the new algorithm is $Ω(n)$ times faster than the most efficient existing algorithm with polynomial memory complexity, but also assert that it is even more efficient than the most efficient existing algorithm with exponential memory complexity. Finally, numerical simulations are presented to illustrate the optimality and efficiency of our novel SMP algorithm.
The societal impact of big data: A research roadmap for Europe
Venue: arXiv cs.CY 2018
Year: 2018

With its rapid growth and increasing adoption, big data is producing a substantial impact in society. Its usage is opening both opportunities such as new business models and economic gains and risks such as privacy violations and discrimination. Europe is in need of a comprehensive strategy to optimise the use of data for a societal benefit and increase the innovation and competitiveness of its productive activities. In this paper, we contribute to the definition of this strategy with a research roadmap to capture the economic, social and ethical, legal and political benefits associated with the use of big data in Europe. The present roadmap considers the positive and negative externalities associated with big data, maps research and innovation topics in the areas of data management, processing, analytics, protection, visualisation, as well as non-technical topics, to the externalities they can tackle, and provides a time frame to address these topics in order to deliver social impact, skills development and standardisation. Finally, it also identifies what sectors will be most benefited by each of the research efforts. The goal of the roadmap is to guide European research efforts to develop a socially responsible big data economy, and to allow stakeholders to identify and meet big data challenges and proceed with a shared understanding of the societal impact, positive and negative externalities and concrete problems worth investigating in future programmes.
Survey on Misbehavior Detection in Cooperative Intelligent Transportation Systems
Venue: arXiv cs.CR 2018
Year: 2018

Cooperative Intelligent Transportation Systems (cITS) are a promising technology to enhance driving safety and efficiency. Vehicles communicate wirelessly with other vehicles and infrastructure, thereby creating a highly dynamic and heterogeneously managed ad-hoc network. It is these network properties that make it a challenging task to protect integrity of the data and guarantee its correctness. A major component is the problem that traditional security mechanisms like PKI-based asymmetric cryptography only exclude outsider attackers that do not possess key material. However, because attackers can be insiders within the network (i.e., possess valid key material), this approach cannot detect all possible attacks. In this survey, we present misbehavior detection mechanisms that can detect such insider attacks based on attacker behavior and information analysis. In contrast to well-known intrusion detection for classical IT systems, these misbehavior detection mechanisms analyze information semantics to detect attacks, which aligns better with highly application-tailored communication protocols foreseen for cITS. In our survey, we provide an extensive introduction to the cITS ecosystem and discuss shortcomings of PKI-based security. We derive and discuss a classification for misbehavior detection mechanisms, provide an in-depth overview of seminal papers on the topic, and highlight open issues and possible future research trends.
Computability in Basic Quantum Mechanics
Venue: arXiv cs.LO 2018
Year: 2018

The basic notions of quantum mechanics are formulated in terms of separable infinite dimensional Hilbert space $\mathcal{H}$. In terms of the Hilbert lattice $\mathcal{L}$ of closed linear subspaces of $\mathcal{H}$ the notions of state and observable can be formulated as kinds of measures as in [21]. The aim of this paper is to show that there is a good notion of computability for these data structures in the sense of Weihrauch's Type Two Effectivity (TTE) [26]. Instead of explicitly exhibiting admissible representations for the data types under consideration we show that they do live within the category $\mathbf{QCB}_0$ which is equivalent to the category $\mathbf{AdmRep}$ of admissible representations and continuously realizable maps between them. For this purpose in case of observables we have to replace measures by valuations which allows us to prove an effective version of von Neumann's Spectral Theorem.
TensorLy: Tensor Learning in Python
Venue: arXiv cs.LG 2018
Year: 2018

Tensors are higher-order extensions of matrices. While matrix methods form the cornerstone of machine learning and data analysis, tensor methods have been gaining increasing traction. However, software support for tensor operations is not on the same footing. In order to bridge this gap, we have developed \emph{TensorLy}, a high-level API for tensor methods and deep tensorized neural networks in Python. TensorLy aims to follow the same standards adopted by the main projects of the Python scientific community, and seamlessly integrates with them. Its BSD license makes it suitable for both academic and commercial applications. TensorLy's backend system allows users to perform computations with NumPy, MXNet, PyTorch, TensorFlow and CuPy. They can be scaled on multiple CPU or GPU machines. In addition, using the deep-learning frameworks as backend allows users to easily design and train deep tensorized neural networks. TensorLy is available at https://github.com/tensorly/tensorly
Towards Blended Reactive Planning and Acting using Behavior Trees
Venue: arXiv cs.RO 2018
Year: 2018

In this paper, we show how a planning algorithm can be used to automatically create and update a Behavior Tree (BT), controlling a robot in a dynamic environment. The planning part of the algorithm is based on the idea of back chaining. Starting from a goal condition we iteratively select actions to achieve that goal, and if those actions have unmet preconditions, they are extended with actions to achieve them in the same way. The fact that BTs are inherently modular and reactive makes the proposed solution blend acting and planning in a way that enables the robot to efficiently react to external disturbances. If an external agent undoes an action the robot reexecutes it without re-planning, and if an external agent helps the robot, it skips the corresponding actions, again without replanning. We illustrate our approach in two different robotics scenarios.
Improving incremental recommenders with online bagging
Venue: arXiv cs.IR 2018
Year: 2018

Online recommender systems often deal with continuous, potentially fast and unbounded flows of data. Ensemble methods for recommender systems have been used in the past in batch algorithms, however they have never been studied with incremental algorithms that learn from data streams. We evaluate online bagging with an incremental matrix factorization algorithm for top-N recommendation with positive-only -- binary -- ratings. Our results show that online bagging is able to improve accuracy up to 35% over the baseline, with small computational overhead.
emgr - The Empirical Gramian Framework
Venue: arXiv cs.MS 2018
Year: 2018

System Gramian matrices are a well-known encoding for properties of input-output systems such as controllability, observability or minimality. These so-called system Gramians were developed in linear system theory for applications such as model order reduction of control systems. Empirical Gramian are an extension to the system Gramians for parametric and nonlinear systems as well as a data-driven method of computation. The empirical Gramian framework - emgr - implements the empirical Gramians in a uniform and configurable manner, with applications such as Gramian-based (nonlinear) model reduction, decentralized control, sensitivity analysis, parameter identification and combined state and parameter reduction.
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners
Venue: arXiv cs.DS 2018
Year: 2018

The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted $m$-edge and $n$-node graphs require $Ω(\min\{n^ω, mn\})$ time (for $2\leqω<2.373$). In this paper, we drastically improve these runtimes as follows: * Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in $\widetilde{O}(m)$ time computes an $\widetilde{O}(1)$-multiplicative approximation of the girth as well as an $\widetilde{O}(1)$-multiplicative roundtrip spanner with $\widetilde{O}(n)$ edges with high probability (w.h.p). * Nearly Tight Additive Approximations: For unweighted graphs and any $α\in (0,1)$ we give an algorithm that in $\widetilde{O}(mn^{1 - α})$ time computes an $O(n^α)$-additive approximation of the girth w.h.p, and partially derandomize it. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial Boolean matrix multiplication. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than $Ω(\min\{n^ω, mn\})$ time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.
Bidirectional Attention Flow for Machine Comprehension
Venue: arXiv cs.CL 2018
Year: 2018

Machine comprehension (MC), answering a query about a given context paragraph, requires modeling complex interactions between the context and the query. Recently, attention mechanisms have been successfully extended to MC. Typically these methods use attention to focus on a small portion of the context and summarize it with a fixed-size vector, couple attentions temporally, and/or often form a uni-directional attention. In this paper we introduce the Bi-Directional Attention Flow (BIDAF) network, a multi-stage hierarchical process that represents the context at different levels of granularity and uses bi-directional attention flow mechanism to obtain a query-aware context representation without early summarization. Our experimental evaluations show that our model achieves the state-of-the-art results in Stanford Question Answering Dataset (SQuAD) and CNN/DailyMail cloze test.
Simulations for Deep Random Secrecy Protocol
Venue: arXiv cs.CR 2018
Year: 2018

We present numerical simulations measuring secrecy and efficiency rate of Perfect Secrecy protocol presented in former article named Perfect Secrecy under Deep Random assumption. Those simulations specifically measure the respective error rates of both legitimate partner and eavesdropper experimented during the exchange of a data flow through the protocol. Those measured error rates also enable us to estimate a lower bound of the Crytpologic Limit introduced in article named Perfect Secrecy under Deep Random assumption. We discuss the variation of the protocol parameters and their impact on the measured performance.
Closure and Nonclosure Properties of the Compressible and Rankable Sets
Venue: arXiv cs.LO 2018
Year: 2018

The rankable and compressible sets have been studied for more than a quarter of a century, ever since Allender [1] and Goldberg and Sipser [6] introduced the formal study of polynomial-time ranking. Yet even after all that time, whether the rankable and compressible sets are closed under the most important boolean and other operations remains essentially unexplored. The present paper studies these questions for both polynomial-time and recursion-theoretic compression and ranking, and for almost every case arrives at a Closed, a Not-Closed, or a Closed-Iff-Well-Known-Complexity-Classes-Collapse result for the given operation. Even though compression and ranking classes are capturing something quite natural about the structure of sets, it turns out that they are quite fragile with respect to closure properties, and many fail to possess even the most basic of closure properties. For example, we show that with respect to the join (aka disjoint union) operation: the P-rankable sets are not closed, whether the semistrongly P-rankable sets are closed is closely linked to whether P = UP $\cap$ coUP, and the strongly P-rankable sets are closed.
Neural Taylor Approximations: Convergence and Exploration in Rectifier Networks
Venue: arXiv cs.LG 2018
Year: 2018

Modern convolutional networks, incorporating rectifiers and max-pooling, are neither smooth nor convex; standard guarantees therefore do not apply. Nevertheless, methods from convex optimization such as gradient descent and Adam are widely used as building blocks for deep learning algorithms. This paper provides the first convergence guarantee applicable to modern convnets, which furthermore matches a lower bound for convex nonsmooth functions. The key technical tool is the neural Taylor approximation -- a straightforward application of Taylor expansions to neural networks -- and the associated Taylor loss. Experiments on a range of optimizers, layers, and tasks provide evidence that the analysis accurately captures the dynamics of neural optimization. The second half of the paper applies the Taylor approximation to isolate the main difficulty in training rectifier nets -- that gradients are shattered -- and investigates the hypothesis that, by exploring the space of activation configurations more thoroughly, adaptive optimizers such as RMSProp and Adam are able to converge to better solutions.
Detecting tala Computationally in Polyphonic Context - A Novel Approach
Venue: arXiv cs.SD 2018
Year: 2018

In North-Indian-Music-System(NIMS),tabla is mostly used as percussive accompaniment for vocal-music in polyphonic-compositions. The human auditory system uses perceptual grouping of musical-elements and easily filters the tabla component, thereby decoding prominent rhythmic features like tala, tempo from a polyphonic composition. For Western music, lots of work have been reported for automated drum analysis of polyphonic composition. However, attempts at computational analysis of tala by separating the tabla-signal from mixed signal in NIMS have not been successful. Tabla is played with two components - right and left. The right-hand component has frequency overlap with voice and other instruments. So, tala analysis of polyphonic-composition, by accurately separating the tabla-signal from the mixture is a baffling task, therefore an area of challenge. In this work we propose a novel technique for successfully detecting tala using left-tabla signal, producing meaningful results because the left-tabla normally doesn't have frequency overlap with voice and other instruments. North-Indian-rhythm follows complex cyclic pattern, against linear approach of Western-rhythm. We have exploited this cyclic property along with stressed and non-stressed methods of playing tabla-strokes to extract a characteristic pattern from the left-tabla strokes, which, after matching with the grammar of tala-system, determines the tala and tempo of the composition. A large number of polyphonic(vocal+tabla+other-instruments) compositions has been analyzed with the methodology and the result clearly reveals the effectiveness of proposed techniques.
Approximate Capacity Region of the Two-User Gaussian Interference Channel with Noisy Channel-Output Feedback
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, the capacity region of the linear deterministic interference channel with noisy channel-output feedback (LD-IC-NF) is fully characterized. The proof of achievability is based on random coding arguments and rate splitting; block-Markov superposition coding; and backward decoding. The proof of converse reuses some of the existing outer bounds and includes new ones obtained using genie-aided models. Following the insight gained from the analysis of the LD-IC-NF, an achievability region and a converse region for the two-user Gaussian interference channel with noisy channel-output feedback (GIC-NF) are presented. Finally, the achievability region and the converse region are proven to approximate the capacity region of the G-IC-NF to within 4.4 bits.
Backtracking Spatial Pyramid Pooling (SPP)-based Image Classifier for Weakly Supervised Top-down Salient Object Detection
Venue: arXiv cs.CV 2018
Year: 2018

Top-down saliency models produce a probability map that peaks at target locations specified by a task/goal such as object detection. They are usually trained in a fully supervised setting involving pixel-level annotations of objects. We propose a weakly supervised top-down saliency framework using only binary labels that indicate the presence/absence of an object in an image. First, the probabilistic contribution of each image region to the confidence of a CNN-based image classifier is computed through a backtracking strategy to produce top-down saliency. From a set of saliency maps of an image produced by fast bottom-up saliency approaches, we select the best saliency map suitable for the top-down task. The selected bottom-up saliency map is combined with the top-down saliency map. Features having high combined saliency are used to train a linear SVM classifier to estimate feature saliency. This is integrated with combined saliency and further refined through a multi-scale superpixel-averaging of saliency map. We evaluate the performance of the proposed weakly supervised topdown saliency and achieve comparable performance with fully supervised approaches. Experiments are carried out on seven challenging datasets and quantitative results are compared with 40 closely related approaches across 4 different applications.