OpenRaiser/Intern-Atlas huggingface dataset:
Learning Deep Generative Models with Doubly Stochastic MCMC
Venue: arXiv cs.LG 2016
Year: 2016

We present doubly stochastic gradient MCMC, a simple and generic method for (approximate) Bayesian inference of deep generative models (DGMs) in a collapsed continuous parameter space. At each MCMC sampling step, the algorithm randomly draws a mini-batch of data samples to estimate the gradient of log-posterior and further estimates the intractable expectation over hidden variables via a neural adaptive importance sampler, where the proposal distribution is parameterized by a deep neural network and learnt jointly. We demonstrate the effectiveness on learning various DGMs in a wide range of tasks, including density estimation, data generation and missing data imputation. Our method outperforms many state-of-the-art competitors.
Task-based adaptive multiresolution for time-space multi-scale reaction-diffusion systems on multi-core architectures
Venue: arXiv cs.NA 2016
Year: 2016

A new solver featuring time-space adaptation and error control has been recently introduced to tackle the numerical solution of stiff reaction-diffusion systems. Based on operator splitting, finite volume adaptive multiresolution and high order time integrators with specific stability properties for each operator, this strategy yields high computational efficiency for large multidimensional computations on standard architectures such as powerful workstations. However, the data structure of the original implementation, based on trees of pointers, provides limited opportunities for efficiency enhancements, while posing serious challenges in terms of parallel programming and load balancing. The present contribution proposes a new implementation of the whole set of numerical methods including Radau5 and ROCK4, relying on a fully different data structure together with the use of a specific library, TBB, for shared-memory, task-based parallelism with work-stealing. The performance of our implementation is assessed in a series of test-cases of increasing difficulty in two and three dimensions on multi-core and many-core architectures, demonstrating high scalability.
Success Probability and Area Spectral Efficiency in Multiuser MIMO HetNets
Venue: arXiv cs.IT 2016
Year: 2016

We derive a general and closed-form result for the success probability in downlink multiple-antenna (MIMO) heterogeneous cellular networks (HetNets), utilizing a novel Toeplitz matrix representation. This main result, which is equivalently the signal-to-interference ratio (SIR) distribution, includes multiuser MIMO, single-user MIMO and per-tier biasing for $K$ different tiers of randomly placed base stations (BSs), assuming zero-forcing precoding and perfect channel state information. The large SIR limit of this result admits a simple closed form that is accurate at moderate SIRs, e.g., above 5 dB. These results reveal that the SIR-invariance property of SISO HetNets does not hold for MIMO HetNets; instead the success probability may decrease as the network density increases. We prove that the maximum success probability is achieved by activating only one tier of BSs, while the maximum area spectral efficiency (ASE) is achieved by activating all the BSs. This reveals a unique tradeoff between the ASE and link reliability in multiuser MIMO HetNets. To achieve the maximum ASE while guaranteeing a certain link reliability, we develop efficient algorithms to find the optimal BS densities. It is shown that as the link reliability requirement increases, more BSs and more tiers should be deactivated.
Dexteroid: Detecting Malicious Behaviors in Android Apps Using Reverse-Engineered Life Cycle Models
Venue: arXiv cs.CR 2016
Year: 2016

The amount of Android malware has increased greatly during the last few years. Static analysis is widely used in detecting such malware by analyzing the code without execution. The effectiveness of current tools relies on the app model as well as the malware detection algorithm which analyzes the app model. If the model and/or the algorithm is inadequate, then sophisticated attacks that are triggered by specific sequences of events will not be detected. This paper presents a static analysis framework called Dexteroid, which uses reverse-engineered life cycle models to accurately capture the behaviors of Android components. Dexteroid systematically derives event sequences from the models, and uses them to detect attacks launched by specific ordering of events. A prototype implementation of Dexteroid detects two types of attacks: (1) leakage of private information, and (2) sending SMS to premium-rate numbers. A series of experiments are conducted on 1526 Google Play apps, 1259 Genome Malware apps, and a suite of benchmark apps called DroidBench and the results are compared with a state-of-the-art static analysis tool called FlowDroid. The evaluation results show that the proposed framework is effective and efficient in terms of precision, recall, and execution time.
Decentralized Abstractions For Multi-Agent Systems Under Coupled Constraints
Venue: arXiv cs.SY 2016
Year: 2016

The goal of this report is to define abstractions for multi-agent systems with feedback interconnection in their dynamics. In the proposed decentralized framework, we specify a finite or countable transition system for each agent which only takes into account the discrete positions of its neighbors. The dynamics of the considered systems consist of two components. An appropriate feedback law which guarantees that certain system and network requirements are fulfilled and induces coupled constraints, and additional free inputs which we exploit in order to accomplish high level tasks. In this work, we provide sufficient conditions on the space and time discretization for the abstraction of the system's behaviour which ensure that we can extract a well posed and hence meaningful transition system. Furthermore, these conditions include design parameters whose tuning provides the possibility for multiple transitions, and hence, enable the construction of transition systems with motion planning capabilities.
Constrained adaptive sensing
Venue: arXiv cs.IT 2016
Year: 2016

Suppose that we wish to estimate a vector $\mathbf{x} \in \mathbb{C}^n$ from a small number of noisy linear measurements of the form $\mathbf{y} = \mathbf{A x} + \mathbf{z}$, where $\mathbf{z}$ represents measurement noise. When the vector $\mathbf{x}$ is sparse, meaning that it has only $s$ nonzeros with $s \ll n$, one can obtain a significantly more accurate estimate of $\mathbf{x}$ by adaptively selecting the rows of $\mathbf{A}$ based on the previous measurements provided that the signal-to-noise ratio (SNR) is sufficiently large. In this paper we consider the case where we wish to realize the potential of adaptivity but where the rows of $\mathbf{A}$ are subject to physical constraints. In particular, we examine the case where the rows of $\mathbf{A}$ are constrained to belong to a finite set of allowable measurement vectors. We demonstrate both the limitations and advantages of adaptive sensing in this constrained setting. We prove that for certain measurement ensembles, the benefits offered by adaptive designs fall far short of the improvements that are possible in the unconstrained adaptive setting. On the other hand, we also provide both theoretical and empirical evidence that in some scenarios adaptivity does still result in substantial improvements even in the constrained setting. To illustrate these potential gains, we propose practical algorithms for constrained adaptive sensing by exploiting connections to the theory of optimal experimental design and show that these algorithms exhibit promising performance in some representative applications.
Ranking the Importance Level of Intermediaries to a Criminal using a Reliance Measure
Venue: arXiv cs.SI 2016
Year: 2016

Recent research on finding important intermediate nodes in a network suspected to contain criminal activity is highly dependent on network centrality values. Betweenness centrality, for example, is widely used to rank the nodes that act as brokers in the shortest paths connecting all source and all the end nodes in a network. However both the shortest path node betweenness and the linearly scaled betweenness can only show rankings for all the nodes in a network. In this paper we explore the mathematical concept of pair-dependency on intermediate nodes, adapting the concept to criminal relationships and introducing a new source-intermediate reliance measure. To illustrate our measure, we apply it to rank the nodes in the Enron email dataset and the Noordin Top Terrorist networks. We compare the reliance ranking with Google PageRank, Markov centrality as well as betweenness centrality and show that a criminal investigation using the reliance measure, will lead to a different prioritisation in terms of possible people to investigate. While the ranking for the Noordin Top terrorist network nodes yields more extreme differences than for the Enron email transaction network, in the latter the reliance values for the set of finance managers immediately identified another employee convicted of money laundering.
Last-use Opacity: A Strong Safety Property for Transactional Memory with Early Release Support
Venue: arXiv cs.DC 2016
Year: 2016

Transaction Memory (TM) is a concurrency control abstraction that allows the programmer to specify blocks of code to be executed atomically as transactions. However, since transactional code can contain just about any operation attention must be paid to the state of shared variables at any given time. E.g., contrary to a database transaction, if a TM transaction reads a stale value it may execute dangerous operations, like attempt to divide by zero, access an illegal memory address, or enter an infinite loop. Thus serializability is insufficient, and stronger safety properties are required in TM, which regulate what values can be read, even by transactions that abort. Hence, a number of TM safety properties were developed, including opacity, and TMS1 and TMS2. However, such strong properties preclude using early release as a technique for optimizing TM, because they virtually forbid reading from live transactions. On the other hand, properties that do allow early release are either not strong enough to prevent any of the problems mentioned above (recoverability), or add additional conditions on transactions with early release that limit their applicability (elastic opacity, live opacity, virtual world consistency). This paper introduces last-use opacity, a new TM safety property that is meant to be a compromise between strong properties like opacity and serializability. The property eliminates all but a small class of inconsistent views and poses no stringent conditions on transactions. For illustration, we present a last-use opaque TM algorithm and show that it satisfies the new safety property.
Cubic TSP - a 1.3-approximation
Venue: arXiv cs.DM 2016
Year: 2016

We prove that every simple bridgeless cubic graph with n >= 8 vertices has a travelling salesman tour of length at most 1.3n - 2, which can be constructed in polynomial time.
A Deep Memory-based Architecture for Sequence-to-Sequence Learning
Venue: arXiv cs.CL 2016
Year: 2016

We propose DEEPMEMORY, a novel deep architecture for sequence-to-sequence learning, which performs the task through a series of nonlinear transformations from the representation of the input sequence (e.g., a Chinese sentence) to the final output sequence (e.g., translation to English). Inspired by the recently proposed Neural Turing Machine (Graves et al., 2014), we store the intermediate representations in stacked layers of memories, and use read-write operations on the memories to realize the nonlinear transformations between the representations. The types of transformations are designed in advance but the parameters are learned from data. Through layer-by-layer transformations, DEEPMEMORY can model complicated relations between sequences necessary for applications such as machine translation between distant languages. The architecture can be trained with normal back-propagation on sequenceto-sequence data, and the learning can be easily scaled up to a large corpus. DEEPMEMORY is broad enough to subsume the state-of-the-art neural translation model in (Bahdanau et al., 2015) as its special case, while significantly improving upon the model with its deeper architecture. Remarkably, DEEPMEMORY, being purely neural network-based, can achieve performance comparable to the traditional phrase-based machine translation system Moses with a small vocabulary and a modest parameter size.
Kernel Cuts: MRF meets Kernel & Spectral Clustering
Venue: arXiv cs.CV 2016
Year: 2016

We propose a new segmentation model combining common regularization energies, e.g. Markov Random Field (MRF) potentials, and standard pairwise clustering criteria like Normalized Cut (NC), average association (AA), etc. These clustering and regularization models are widely used in machine learning and computer vision, but they were not combined before due to significant differences in the corresponding optimization, e.g. spectral relaxation and combinatorial max-flow techniques. On the one hand, we show that many common applications using MRF segmentation energies can benefit from a high-order NC term, e.g. enforcing balanced clustering of arbitrary high-dimensional image features combining color, texture, location, depth, motion, etc. On the other hand, standard clustering applications can benefit from an inclusion of common pairwise or higher-order MRF constraints, e.g. edge alignment, bin-consistency, label cost, etc. To address joint energies like NC+MRF, we propose efficient Kernel Cut algorithms based on bound optimization. While focusing on graph cut and move-making techniques, our new unary (linear) kernel and spectral bound formulations for common pairwise clustering criteria allow to integrate them with any regularization functionals with existing discrete or continuous solvers.
Discrete Gaussian Sampling Reduces to CVP and SVP
Venue: arXiv cs.CC 2016
Year: 2016

The discrete Gaussian $D_{L- t, s}$ is the distribution that assigns to each vector $x$ in a shifted lattice $L - t$ probability proportional to $e^{-π\|x\|^2/s^2}$. It has long been an important tool in the study of lattices. More recently, algorithms for discrete Gaussian sampling (DGS) have found many applications in computer science. In particular, polynomial-time algorithms for DGS with very high parameters $s$ have found many uses in cryptography and in reductions between lattice problems. And, in the past year, Aggarwal, Dadush, Regev, and Stephens-Davidowitz showed $2^{n+o(n)}$-time algorithms for DGS with a much wider range of parameters and used them to obtain the current fastest known algorithms for the two most important lattice problems, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Motivated by its increasing importance, we investigate the complexity of DGS itself and its relationship to CVP and SVP. Our first result is a polynomial-time dimension-preserving reduction from DGS to CVP. There is a simple reduction from CVP to DGS, so this shows that DGS is equivalent to CVP. Our second result, which we find to be more surprising, is a polynomial-time dimension-preserving reduction from centered DGS (the important special case when $ t = 0$) to SVP. In the other direction, there is a simple reduction from $γ$-approximate SVP for any $γ= Ω(\sqrt{n/\log n})$, and we present some (relatively weak) evidence to suggest that this might be the best achievable approximation factor. We also show that our CVP result extends to a much wider class of distributions and even to other norms.
Amplifying the Impact of Open Access: Wikipedia and the Diffusion of Science
Venue: arXiv cs.DL 2016
Year: 2016

With the rise of Wikipedia as a first-stop source for scientific knowledge, it is important to compare its representation of that knowledge to that of the academic literature. Here we identify the 250 most heavily used journals in each of 26 research fields (4,721 journals, 19.4M articles in total) indexed by the Scopus database, and test whether topic, academic status, and accessibility make articles from these journals more or less likely to be referenced on Wikipedia. We find that a journal's academic status (impact factor) and accessibility (open access policy) both strongly increase the probability of it being referenced on Wikipedia. Controlling for field and impact factor, the odds that an open access journal is referenced on the English Wikipedia are 47% higher compared to paywall journals. One of the implications of this study is that a major consequence of open access policies is to significantly amplify the diffusion of science, through an intermediary like Wikipedia, to a broad audience.
Keypoint Encoding for Improved Feature Extraction from Compressed Video at Low Bitrates
Venue: arXiv cs.MM 2016
Year: 2016

In many mobile visual analysis applications, compressed video is transmitted over a communication network and analyzed by a server. Typical processing steps performed at the server include keypoint detection, descriptor calculation, and feature matching. Video compression has been shown to have an adverse effect on feature-matching performance. The negative impact of compression can be reduced by using the keypoints extracted from the uncompressed video to calculate descriptors from the compressed video. Based on this observation, we propose to provide these keypoints to the server as side information and to extract only the descriptors from the compressed video. First, we introduce four different frame types for keypoint encoding to address different types of changes in video content. These frame types represent a new scene, the same scene, a slowly changing scene, or a rapidly moving scene and are determined by comparing features between successive video frames. Then, we propose Intra, Skip and Inter modes of encoding the keypoints for different frame types. For example, keypoints for new scenes are encoded using the Intra mode, and keypoints for unchanged scenes are skipped. As a result, the bitrate of the side information related to keypoint encoding is significantly reduced. Finally, we present pairwise matching and image retrieval experiments conducted to evaluate the performance of the proposed approach using the Stanford mobile augmented reality dataset and 720p format videos. The results show that the proposed approach offers significantly improved feature matching and image retrieval performance at a given bitrate.
PLG2: Multiperspective Processes Randomization and Simulation for Online and Offline Settings
Venue: arXiv cs.SE 2016
Year: 2016

Process mining represents an important field in BPM and data mining research. Recently, it has gained importance also for practitioners: more and more companies are creating business process intelligence solutions. The evaluation of process mining algorithms requires, as any other data mining task, the availability of large amount of real-world data. Despite the increasing availability of such datasets, they are affected by many limitations, in primis the absence of a "gold standard" (i.e., the reference model). This paper extends an approach, already available in the literature, for the generation of random processes. Novelties have been introduced throughout the work and, in particular, they involve the complete support for multiperspective models and logs (i.e., the control-flow perspective is enriched with time and data information) and for online settings (i.e., generation of multiperspective event streams and concept drifts). The proposed new framework is able to almost entirely cover the spectrum of possible scenarios that can be observed in the real-world. The proposed approach is implemented as a publicly available Java application, with a set of APIs for the programmatic execution of experiments.
Multiuser Detection for Random Access Bandwidth Request in WiMAX
Venue: arXiv cs.IT 2016
Year: 2016

Random access is a multiple access communication protocol where the users simultaneously communicate with a base station (BS) in an uncoordinated fashion. In this work, we consider the problem of multiuser detection in a random access bandwidth request context. We propose an enhanced random access scheme where the fixed/low-mobility M2M devices pre-equalize their random access codes using the estimated frequency response of the slowly-varying wireless channel. Consequently, we have developed two different multiuser detection algorithms. The first algorithm works in a greedy fashion where it performs cross-correlation of the received signal with a set of decoder sequences and detects active users based on the correlation output. We derive the condition under which the algorithm can detect a given number of active users with high probability. Subsequently, we demonstrate an efficient decoder design procedure which enhances the user detection performance. A basis mismatched sparse recovery technique has been applied in the second algorithm which exploit an inherent structure of the random access protocol. The performance of the proposed schemes is demonstrated in a WiMAX network environment.
Symbolic Derivation of Mean-Field PDEs from Lattice-Based Models
Venue: arXiv cs.SC 2016
Year: 2016

Transportation processes, which play a prominent role in the life and social sciences, are typically described by discrete models on lattices. For studying their dynamics a continuous formulation of the problem via partial differential equations (PDE) is employed. In this paper we propose a symbolic computation approach to derive mean-field PDEs from a lattice-based model. We start with the microscopic equations, which state the probability to find a particle at a given lattice site. Then the PDEs are formally derived by Taylor expansions of the probability densities and by passing to an appropriate limit as the time steps and the distances between lattice sites tend to zero. We present an implementation in a computer algebra system that performs this transition for a general class of models. In order to rewrite the mean-field PDEs in a conservative formulation, we adapt and implement symbolic integration methods that can handle unspecified functions in several variables. To illustrate our approach, we consider an application in crowd motion analysis where the dynamics of bidirectional flows are studied. However, the presented approach can be applied to various transportation processes of multiple species with variable size in any dimension, for example, to confirm several proposed mean-field models for cell motility.
Full-Duplex vs. Half-Duplex Secret-Key Generation
Venue: arXiv cs.IT 2016
Year: 2016

Full-duplex (FD) communication is regarded as a key technology in future 5G and Internet of Things (IoT) systems. In addition to high data rate constraints, the success of these systems depends on the ability to allow for confidentiality and security. Secret-key agreement from reciprocal wireless channels can be regarded as a valuable supplement for security at the physical layer. In this work, we study the role of FD communication in conjunction with secret-key agreement. We first introduce two complementary key generation models for FD and half-duplex (HD) settings and compare the performance by introducing the key-reconciliation function. Furthermore, we study the impact of the so called probing-reconciliation trade-off, the role of a strong eavesdropper and analyze the system in the high SNR regime. We show that under certain conditions, the FD mode enforces a deteriorating impact on the capabilities of the eavesdropper and offers several advantages in terms of secret-key rate over the conventional HD setups. Our analysis reveals as an interesting insight that perfect self-interference cancellation is not necessary in order to obtain performance gains over the HD mode.