OpenRaiser/Intern-Atlas huggingface dataset:
Regular Hilberg Processes: An Example of Processes with a Vanishing Entropy Rate
Venue: arXiv cs.IT 2016
Year: 2016

A regular Hilberg process is a stationary process that satisfies both a hyperlogarithmic growth of maximal repetition and a power-law growth of topological entropy, which are a kind of dual conditions. The hyperlogarithmic growth of maximal repetition has been experimentally observed for texts in natural language, whereas the power-law growth of topological entropy implies a vanishing Shannon entropy rate and thus probably does not hold for natural language. In this paper, we provide a constructive example of regular Hilberg processes, which we call random hierarchical association (RHA) processes. Our construction does not apply the standard cutting and stacking method. For the constructed RHA processes, we demonstrate that the expected length of any uniquely decodable code is orders of magnitude larger than the Shannon block entropy of the ergodic component of the RHA process. Our proposition supplements the classical result by Shields concerning nonexistence of universal redundancy rates.
Blocking Avoidance in Transportation Systems
Venue: arXiv cs.SY 2016
Year: 2016

The blocking problem naturally arises in transportation systems as multiple vehicles with different itineraries share available resources. In this paper, we investigate the impact of the blocking problem to the waiting time at the intersections of transportation systems. We assume that different vehicles, depending on their Internet connection capabilities, may communicate their intentions (e.g., whether they will turn left or right or continue straight) to intersections (specifically to devices attached to traffic lights). We consider that information collected by these devices are transmitted to and processed in a cloud-based traffic control system. Thus, a cloud-based system, based on the intention information, can calculate average waiting times at intersections. We consider this problem as a queuing model, and we characterize average waiting times by taking into account (i) blocking probability, and (ii) vehicles' ability to communicate their intentions. Then, by using average waiting times at intersection, we develop a shortest delay algorithm that calculates the routes with shortest delays between two points in a transportation network. Our simulation results confirm our analysis, and demonstrate that our shortest delay algorithm significantly improves over baselines that are unaware of the blocking problem.
Capturing an Omnidirectional Evader in Convex Environments using a Differential Drive Robot
Venue: arXiv cs.RO 2016
Year: 2016

We study the problem of capturing an Omnidirectional Evader in convex environments using a Differential Drive Robot (DDR). The DDR wins the game if at any time instant it captures (collides with) the evader. The evader wins if it can avoid capture forever. Both players are unit disks with the same maximum (bounded) speed, but the DDR can only change its motion direction at a bounded rate. We show that despite this limitation, the DDR can capture the evader.
Performance Analysis and Coherent Guaranteed Cost Control for Uncertain Quantum Systems Using Small Gain and Popov Methods
Venue: arXiv cs.SY 2016
Year: 2016

This paper extends applications of the quantum small gain and Popov methods from existing results on robust stability to performance analysis results for a class of uncertain quantum systems. This class of systems involves a nominal linear quantum system and is subject to quadratic perturbations in the system Hamiltonian. Based on these two methods, coherent guaranteed cost controllers are designed for a given quantum system to achieve improved control performance. An illustrative example also shows that the quantum Popov approach can obtain less conservative results than the quantum small gain approach for the same uncertain quantum system.
Uplink HARQ for Distributed and Cloud RAN via Separation of Control and Data Planes
Venue: arXiv cs.IT 2016
Year: 2016

The implementation of uplink HARQ in a Cloud- Radio Access Network RAN (C-RAN) architecture is constrained by the two-way latency on the fronthaul links connecting the Remote Radio Heads (RRHs) with the Baseband Units (BBUs) that perform decoding. To overcome this limitation, this work considers an architecture based on the separation of control and data planes, in which retransmission control decisions are made at the edge of the network, that is, by the RRHs or User Equipments (UEs), while data decoding is carried out remotely at the BBUs. This solution enables low-latency local retransmission decisions to be made at the RRHs or UEs, which are not subject to the fronthaul latency constraints, while at the same time leveraging the decoding capability of the BBUs. A system with BBU Hoteling system is considered first in which each RRH has a dedicated BBU in the cloud. For this system, the control-data separation leverages low-latency local feedback from an RRH to drive the HARQ process of a given UE. Throughput and probability of error of this solution are analyzed for the three standard HARQ modes of Type-I, Chase Combining and Incremental Redundancy over a general fading MIMO link. Then, novel user-centric low-latency feedback strategies are proposed and analyzed for the C-RAN architecture, with a single centralized BBU, based on limited "hard" or "soft" local feedback from the RRHs to the UE and on retransmission decisions taken at the UE. The analysis presented in this work allows the optimization of the considered schemes, as well as the investigation of the impact of system parameters such as HARQ protocol type, blocklength and number of antennas on the performance of low-latency local HARQ decisions in BBU Hoteling and C-RAN architectures.
Towards universal neural nets: Gibbs machines and ACE
Venue: arXiv cs.CV 2016
Year: 2016

We study from a physics viewpoint a class of generative neural nets, Gibbs machines, designed for gradual learning. While including variational auto-encoders, they offer a broader universal platform for incrementally adding newly learned features, including physical symmetries. Their direct connection to statistical physics and information geometry is established. A variational Pythagorean theorem justifies invoking the exponential/Gibbs class of probabilities for creating brand new objects. Combining these nets with classifiers, gives rise to a brand of universal generative neural nets - stochastic auto-classifier-encoders (ACE). ACE have state-of-the-art performance in their class, both for classification and density estimation for the MNIST data set.
Explicit resilient functions matching Ajtai-Linial
Venue: arXiv cs.CC 2016
Year: 2016

A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the function. Resilient functions have been extensively studied with a variety of applications in cryptography, distributed computing, and pseudorandomness. The best known balanced resilient function on n variables due to Ajtai and Linial ([AL93]) is Omega(n/(log^2 n))-resilient. However, the construction of Ajtai and Linial is by the probabilistic method and does not give an efficiently computable function. In this work we give an explicit monotone depth three almost-balanced Boolean function on n bits that is Omega(n/(log^2 n))-resilient matching the work of Ajtai and Linial. The best previous explicit construction due to Meka [Meka09] (which only gives a logarithmic depth function) and Chattopadhyay and Zuckermman [CZ15] were only n^{1-c}-resilient for any constant c < 1. Our construction and analysis are motivated by (and simplifies parts of) the recent breakthrough of [CZ15] giving explicit two-sources extractors for polylogarithmic min-entropy; a key ingredient in their result was the construction of explicit constant-depth resilient functions. An important ingredient in our construction is a new randomness optimal oblivious sampler which preserves moment generating functions of sums of variables and could be useful elsewhere.
Differentially Private Online Learning for Cloud-Based Video Recommendation with Multimedia Big Data in Social Networks
Venue: arXiv cs.LG 2016
Year: 2016

With the rapid growth in multimedia services and the enormous offers of video contents in online social networks, users have difficulty in obtaining their interests. Therefore, various personalized recommendation systems have been proposed. However, they ignore that the accelerated proliferation of social media data has led to the big data era, which has greatly impeded the process of video recommendation. In addition, none of them has considered both the privacy of users' contexts (e,g., social status, ages and hobbies) and video service vendors' repositories, which are extremely sensitive and of significant commercial value. To handle the problems, we propose a cloud-assisted differentially private video recommendation system based on distributed online learning. In our framework, service vendors are modeled as distributed cooperative learners, recommending videos according to user's context, while simultaneously adapting the video-selection strategy based on user-click feedback to maximize total user clicks (reward). Considering the sparsity and heterogeneity of big social media data, we also propose a novel geometric differentially private model, which can greatly reduce the performance (recommendation accuracy) loss. Our simulation shows the proposed algorithms outperform other existing methods and keep a delicate balance between computing accuracy and privacy preserving level.
Fast Randomized Singular Value Thresholding for Low-rank Optimization
Venue: arXiv cs.CV 2016
Year: 2016

Rank minimization can be converted into tractable surrogate problems, such as Nuclear Norm Minimization (NNM) and Weighted NNM (WNNM). The problems related to NNM, or WNNM, can be solved iteratively by applying a closed-form proximal operator, called Singular Value Thresholding (SVT), or Weighted SVT, but they suffer from high computational cost of Singular Value Decomposition (SVD) at each iteration. We propose a fast and accurate approximation method for SVT, that we call fast randomized SVT (FRSVT), with which we avoid direct computation of SVD. The key idea is to extract an approximate basis for the range of the matrix from its compressed matrix. Given the basis, we compute partial singular values of the original matrix from the small factored matrix. In addition, by developping a range propagation method, our method further speeds up the extraction of approximate basis at each iteration. Our theoretical analysis shows the relationship between the approximation bound of SVD and its effect to NNM via SVT. Along with the analysis, our empirical results quantitatively and qualitatively show that our approximation rarely harms the convergence of the host algorithms. We assess the efficiency and accuracy of the proposed method on various computer vision problems, e.g., subspace clustering, weather artifact removal, and simultaneous multi-image alignment and rectification.
Recognizing and Drawing IC-planar Graphs
Venue: arXiv cs.CG 2016
Year: 2016

IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-planar graphs. Given an embedded IC-planar graph $G$ with $n$ vertices, we present an $O(n)$-time algorithm that computes a straight-line drawing of $G$ in quadratic area, and an $O(n^3)$-time algorithm that computes a straight-line drawing of $G$ with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is NP-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar.
A tree-based kernel for graphs with continuous attributes
Venue: arXiv cs.LG 2016
Year: 2016

The availability of graph data with node attributes that can be either discrete or real-valued is constantly increasing. While existing kernel methods are effective techniques for dealing with graphs having discrete node labels, their adaptation to non-discrete or continuous node attributes has been limited, mainly for computational issues. Recently, a few kernels especially tailored for this domain, and that trade predictive performance for computational efficiency, have been proposed. In this paper, we propose a graph kernel for complex and continuous nodes' attributes, whose features are tree structures extracted from specific graph visits. The kernel manages to keep the same complexity of state-of-the-art kernels while implicitly using a larger feature space. We further present an approximated variant of the kernel which reduces its complexity significantly. Experimental results obtained on six real-world datasets show that the kernel is the best performing one on most of them. Moreover, in most cases the approximated version reaches comparable performances to current state-of-the-art kernels in terms of classification accuracy while greatly shortening the running times.
Security Concerns in Minimum Storage Cooperative Regenerating Codes
Venue: arXiv cs.IT 2016
Year: 2016

Here, we revisit the problem of exploring the secrecy capacity of minimum storage cooperative regenerating (MSCR) codes under the $\{l_1,l_2\}$-eavesdropper model, where the eavesdropper can observe the data stored on $l_1$ nodes and the repair downloads of an additional $l_2$ nodes. Compared to minimum storage regenerating (MSR) codes which support only single node repairs, MSCR codes allow efficient simultaneous repairs of multiple failed nodes, referred to as a \emph{repair group}. However, the repair data sent from a helper node to another failed node may vary with different repair groups or the sets of helper nodes, which would inevitably leak more data information to the eavesdropper and even render the storage system unable to maintain any data secrecy. In this paper, we introduce and study a special category of MSCR codes, termed "\emph{stable}" MSCR codes, where the repair data from any one helper node to any one failed node is required to be independent of the repair group or the set of helper nodes. Our main contributions include: 1. Demonstrating that two existing MSCR codes inherently are not stable and thus have poor secrecy capacity, 2. Converting one existing MSCR code to a stable one, which offers better secrecy capacity when compared to the original one, 3. Employing information theoretic analysis to characterize the secrecy capacity of stable MSCR codes in certain situations.
An On-line Variational Bayesian Model for Multi-Person Tracking from Cluttered Scenes
Venue: arXiv cs.CV 2016
Year: 2016

Object tracking is an ubiquitous problem that appears in many applications such as remote sensing, audio processing, computer vision, human-machine interfaces, human-robot interaction, etc. Although thoroughly investigated in computer vision, tracking a time-varying number of persons remains a challenging open problem. In this paper, we propose an on-line variational Bayesian model for multi-person tracking from cluttered visual observations provided by person detectors. The contributions of this paper are the followings. First, we propose a variational Bayesian framework for tracking an unknown and varying number of persons. Second, our model results in a variational expectation-maximization (VEM) algorithm with closed-form expressions for the posterior distributions of the latent variables and for the estimation of the model parameters. Third, the proposed model exploits observations from multiple detectors, and it is therefore multimodal by nature. Finally, we propose to embed both object-birth and object-visibility processes in an effort to robustly handle person appearances and disappearances over time. Evaluated on classical multiple person tracking datasets, our method shows competitive results with respect to state-of-the-art multiple-object tracking models, such as the probability hypothesis density (PHD) filter among others.
Efficient Sampling for k-Determinantal Point Processes
Venue: arXiv cs.LG 2016
Year: 2016

Determinantal Point Processes (DPPs) are elegant probabilistic models of repulsion and diversity over discrete sets of items. But their applicability to large sets is hindered by expensive cubic-complexity matrix operations for basic tasks such as sampling. In light of this, we propose a new method for approximate sampling from discrete $k$-DPPs. Our method takes advantage of the diversity property of subsets sampled from a DPP, and proceeds in two stages: first it constructs coresets for the ground set of items; thereafter, it efficiently samples subsets based on the constructed coresets. As opposed to previous approaches, our algorithm aims to minimize the total variation distance to the original distribution. Experiments on both synthetic and real datasets indicate that our sampling algorithm works efficiently on large data sets, and yields more accurate samples than previous approaches.
Learning Optimal Control via Forward and Backward Stochastic Differential Equations
Venue: arXiv cs.SY 2016
Year: 2016

In this paper we present a novel sampling-based numerical scheme designed to solve a certain class of stochastic optimal control problems, utilizing forward and backward stochastic differential equations (FBSDEs). By means of a nonlinear version of the Feynman-Kac lemma, we obtain a probabilistic representation of the solution to the nonlinear Hamilton-Jacobi-Bellman equation, expressed in the form of a decoupled system of FBSDEs. This system of FBSDEs can then be simulated by employing linear regression techniques. To enhance the efficiency of the proposed scheme when treating more complex nonlinear systems, we then derive an iterative modification based on Girsanov's theorem on the change of measure, which features importance sampling. The modified scheme is capable of learning the optimal control without requiring an initial guess. We present simulations that validate the algorithm and demonstrate its efficiency in treating nonlinear dynamics.
Parsing Expression Grammars Made Practical
Venue: arXiv cs.PL 2016
Year: 2016

Parsing Expression Grammars (PEGs) define languages by specifying recursive-descent parser that recognises them. The PEG formalism exhibits desirable properties, such as closure under composition, built-in disambiguation, unification of syntactic and lexical concerns, and closely matching programmer intuition. Unfortunately, state of the art PEG parsers struggle with left-recursive grammar rules, which are not supported by the original definition of the formalism and can lead to infinite recursion under naive implementations. Likewise, support for associativity and explicit precedence is spotty. To remedy these issues, we introduce Autumn, a general purpose PEG library that supports left-recursion, left and right associativity and precedence rules, and does so efficiently. Furthermore, we identify infix and postfix operators as a major source of inefficiency in left-recursive PEG parsers and show how to tackle this problem. We also explore the extensibility of the PEG paradigm by showing how one can easily introduce new parsing operators and how our parser accommodates custom memoization and error handling strategies. We compare our parser to both state of the art and battle-tested PEG and CFG parsers, such as Rats!, Parboiled and ANTLR.
Modeling Dense Urban Wireless Networks with 3D Stochastic Geometry
Venue: arXiv cs.NI 2016
Year: 2016

Over the past decade, many works on the modeling of wireless networks using stochastic geometry have been proposed. Results about probability of coverage, throughput or mean interference, have been provided for a wide variety of networks (cellular, ad-hoc, cognitive, sensors, etc). These results notably allow to tune network protocol parameters. Nevertheless, in their vast majority, these works assume that the wireless network deployment is flat: nodes are placed on the Euclidean plane. However, this assumption is disproved in dense urban environments where many nodes are deployed in high buildings. In this letter, we derive the exact form of the probability of coverage for the cases where the interferers form a 3D Poisson Point Process (PPP) and a 3D Modified Matern Process (MMP), and compare the results with the 2D case. The main goal of this letter is to show that the 2D model, although being the most common, can lead either to an optimistic or a pessimistic evaluation of the probability of coverage depending on the parameters of the model.
Two betweenness centrality measures based on Randomized Shortest Paths
Venue: arXiv cs.SI 2016
Year: 2016

This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortest paths, but also take into account longer paths depending on an inverse temperature parameter. RSP's have previously proven to be useful in defining distance measures on networks. In this work we study their utility in quantifying the importance of the nodes of a network. The proposed RSP betweenness centralities combine, in an optimal way, the ideas of using the shortest and purely random paths for analysing the roles of network nodes, avoiding issues involving these two paradigms. We present the derivations of these measures and how they can be computed in an efficient way. In addition, we show with real world examples the potential of the RSP betweenness centralities in identifying interesting nodes of a network that more traditional methods might fail to notice.
Estimation of the Direct-Path Relative Transfer Function for Supervised Sound-Source Localization
Venue: arXiv cs.SD 2016
Year: 2016

This paper addresses the problem of binaural localization of a single speech source in noisy and reverberant environments. For a given binaural microphone setup, the binaural response corresponding to the direct-path propagation of a single source is a function of the source direction. In practice, this response is contaminated by noise and reverberations. The direct-path relative transfer function (DP-RTF) is defined as the ratio between the direct-path acoustic transfer function of the two channels. We propose a method to estimate the DP-RTF from the noisy and reverberant microphone signals in the short-time Fourier transform domain. First, the convolutive transfer function approximation is adopted to accurately represent the impulse response of the sensors in the STFT domain. Second, the DP-RTF is estimated by using the auto- and cross-power spectral densities at each frequency and over multiple frames. In the presence of stationary noise, an inter-frame spectral subtraction algorithm is proposed, which enables to achieve the estimation of noise-free auto- and cross-power spectral densities. Finally, the estimated DP-RTFs are concatenated across frequencies and used as a feature vector for the localization of speech source. Experiments with both simulated and real data show that the proposed localization method performs well, even under severe adverse acoustic conditions, and outperforms state-of-the-art localization methods under most of the acoustic conditions.
Liberating language research from dogmas of the 20th century
Venue: arXiv cs.CL 2016
Year: 2016

A commentary on the article "Large-scale evidence of dependency length minimization in 37 languages" by Futrell, Mahowald & Gibson (PNAS 2015 112 (33) 10336-10341).