OpenRaiser/Intern-Atlas huggingface dataset:
A new generation of science overlay maps with an application to the history of biosystematics
Venue: arXiv cs.DL 2015
Year: 2015

The paper proposes a text-mining based analytical framework aiming at the cognitive organization of complex scientific discourses. The approach is based on models recently developed in science mapping, being a generalization of the so-called Science Overlay Mapping methodology, referred to as Topic Overlay Mapping (TOM). It is shown that via applications of TOM in visualization, document clustering, time series analysis etc. the in-depth exploration and even the measurement of cognitive complexity and its dynamics is feasible for scientific domains. As a use case, an empirical study is presented into the discovery of a long-standing complex, interdisciplinary discourse, the debate on the species concept in biosystematics.
New Perspectives on Multiple Source Localization in Wireless Sensor Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we address the challenging problem of multiple source localization in Wireless Sensor Networks (WSN). We develop an efficient statistical algorithm, based on the novel application of Sequential Monte Carlo (SMC) sampler methodology, that is able to deal with an unknown number of sources given quantized data obtained at the fusion center from different sensors with imperfect wireless channels. We also derive the Posterior Cramér-Rao Bound (PCRB) of the source location estimate. The PCRB is used to analyze the accuracy of the proposed SMC sampler algorithm and the impact that quantization has on the accuracy of location estimates of the sources. Extensive experiments show that the benefits of the proposed scheme in terms of the accuracy of the estimation method that are required for model selection (i.e., the number of sources) and the estimation of the source characteristics compared to the classical importance sampling method.
Effect of Number of Users in Multi-level Coded Caching
Venue: arXiv cs.IT 2015
Year: 2015

It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. This has also been extended to the case when content has non-uniform popularity through several models. In this paper we focus on a multi-level popularity model, where content is divided into levels based on popularity. We consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup). When the capacity approximation is universal (independent of number of popularity levels as well as number of users, files and caches), we demonstrate a dichotomy in the order-optimal strategies for these two extreme cases. In the multi-user case, sharing memory among the levels is order-optimal, whereas for the single-user case clustering popularity levels and allocating all the memory to them is the order-optimal scheme. In proving these results, we develop new information-theoretic lower bounds for the problem.
Non-Adaptive Policies for 20 Questions Target Localization
Venue: arXiv cs.IT 2015
Year: 2015

The problem of target localization with noise is addressed. The target is a sample from a continuous random variable with known distribution and the goal is to locate it with minimum mean squared error distortion. The localization scheme or policy proceeds by queries, or questions, weather or not the target belongs to some subset as it is addressed in the 20-question framework. These subsets are not constrained to be intervals and the answers to the queries are noisy. While this situation is well studied for adaptive querying, this paper is focused on the non adaptive querying policies based on dyadic questions. The asymptotic minimum achievable distortion under such policies is derived. Furthermore, a policy named the Aurelian1 is exhibited which achieves asymptotically this distortion.
Differentially Private Projected Histograms of Multi-Attribute Data for Classification
Venue: arXiv cs.CR 2015
Year: 2015

In this paper, we tackle the problem of constructing a differentially private synopsis for the classification analyses. Several the state-of-the-art methods follow the structure of existing classification algorithms and are all iterative, which is suboptimal due to the locally optimal choices and the over-divided privacy budget among many sequentially composed steps. Instead, we propose a new approach, PrivPfC, a new differentially private method for releasing data for classification. The key idea is to privately select an optimal partition of the underlying dataset using the given privacy budget in one step. Given one dataset and the privacy budget, PrivPfC constructs a pool of candidate grids where the number of cells of each grid is under a data-aware and privacy-budget-aware threshold. After that, PrivPfC selects an optimal grid via the exponential mechanism by using a novel quality function which minimizes the expected number of misclassified records on which a histogram classifier is constructed using the published grid. Finally, PrivPfC injects noise into each cell of the selected grid and releases the noisy grid as the private synopsis of the data. If the size of the candidate grid pool is larger than the processing capability threshold set by the data curator, we add a step in the beginning of PrivPfC to prune the set of attributes privately. We introduce a modified $χ^2$ quality function with low sensitivity and use it to evaluate an attribute's relevance to the classification label variable. Through extensive experiments on real datasets, we demonstrate PrivPfC's superiority over the state-of-the-art methods.
Securing Data against Limited-Knowledge Adversaries in Distributed Storage Systems
Venue: arXiv cs.IT 2015
Year: 2015

We study the problem of constructing secure regenerating codes that protect data integrity in distributed storage systems (DSS) in which some nodes may be compromised by a malicious adversary. The adversary can corrupt the data stored on and transmitted by the nodes under its control. The "damage" incurred by the actions of the adversary depends on how much information it knows about the data in the whole DSS. We focus on the limited-knowledge model in which the adversary knows only the data on the nodes under its control. The only secure capacity-achieving codes known in the literature for this model are for the bandwidth-limited regime and repair degree $d=n-1$, i.e., when a node fails in a DSS with $n$ nodes all the remaining $n-1$ nodes are contacted for repair. We extend these results to the more general case of $d\leq n-1$ in the bandwidth-limited regime. Our capacity-achieving scheme is based on the use of product-matrix codes with special hashing functions and allow the identification of the compromised nodes and their elimination from the DSS while preserving the data integrity.
Minimum HGR Correlation Principle: From Marginals to Joint Distribution
Venue: arXiv cs.IT 2015
Year: 2015

Given low order moment information over the random variables $\mathbf{X} = (X_1,X_2,\ldots,X_p)$ and $Y$, what distribution minimizes the Hirschfeld-Gebelein-Rényi (HGR) maximal correlation coefficient between $\mathbf{X}$ and $Y$, while remains faithful to the given moments? The answer to this question is important especially in order to fit models over $(\mathbf{X},Y)$ with minimum dependence among the random variables $\mathbf{X}$ and $Y$. In this paper, we investigate this question first in the continuous setting by showing that the jointly Gaussian distribution achieves the minimum HGR correlation coefficient among distributions with the given first and second order moments. Then, we pose a similar question in the discrete scenario by fixing the pairwise marginals of the random variables $\mathbf{X}$ and $Y$. To answer this question in the discrete setting, we first derive a lower bound for the HGR correlation coefficient over the class of distributions with fixed pairwise marginals. Then we show that this lower bound is tight if there exists a distribution with certain {\it additive} structure satisfying the given pairwise marginals. Moreover, the distribution with the additive structure achieves the minimum HGR correlation coefficient. Finally, we conclude by showing that the event of obtaining pairwise marginals containing an additive structured distribution has a positive Lebesgue measure over the probability simplex.
Open Data Platform for Knowledge Access in Plant Health Domain : VESPA Mining
Venue: arXiv cs.IR 2015
Year: 2015

Important data are locked in ancient literature. It would be uneconomic to produce these data again and today or to extract them without the help of text mining technologies. Vespa is a text mining project whose aim is to extract data on pest and crops interactions, to model and predict attacks on crops, and to reduce the use of pesticides. A few attempts proposed an agricultural information access. Another originality of our work is to parse documents with a dependency of the document architecture.
LTL Fragments are Hard for Standard Parameterisations
Venue: arXiv cs.LO 2015
Year: 2015

We classify the complexity of the LTL satisfiability and model checking problems for several standard parameterisations. The investigated parameters are temporal depth, number of propositional variables and formula treewidth, resp., pathwidth. We show that all operator fragments of LTL under the investigated parameterisations are intractable in the sense of parameterised complexity.
Repair Scheduling in Wireless Distributed Storage with D2D Communication
Venue: arXiv cs.IT 2015
Year: 2015

We consider distributed storage (DS) for a wireless network where mobile devices arrive and depart according to a Poisson random process. Content is stored in a number of mobile devices, using an erasure correcting code. When requesting a piece of content, a user retrieves the content from the mobile devices using device-to-device communication or, if not possible, from the base station (BS), at the expense of a higher communication cost. We consider the repair problem when a device that stores data leaves the network. In particular, we introduce a repair scheduling where repair is performed (from storage devices or the BS) periodically. We derive analytical expressions for the overall communication cost of repair and download as a function of the repair interval. We illustrate the analysis by giving results for maximum distance separable codes and regenerating codes. Our results indicate that DS can reduce the overall communication cost with respect to the case where content is only downloaded from the BS, provided that repairs are performed frequently enough. The required repair frequency depends on the code used for storage and the network parameters. In particular, minimum bandwidth regenerating codes require very frequent repairs, while maximum distance separable codes give better performance if repair is performed less frequently. We also show that instantaneous repair is not always optimal.
TC: Throughput Centric Successive Cancellation Decoder Hardware Implementation for Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents a hardware architecture of fast simplified successive cancellation (fast-SSC) algorithm for polar codes, which significantly reduces the decoding latency and dramatically increases the throughput. Algorithmically, fast-SSC algorithm suffers from the fact that its decoder scheduling and the consequent architecture depends on the code rate; this is a challenge for rate-compatible system. However, by exploiting the homogeneousness between the decoding processes of fast constituent polar codes and regular polar codes, the presented design is compatible with any rate. The scheduling plan and the intendedly designed process core are also described. Results show that, compared with the state-of-art decoder, proposed design can achieve at least 60% latency reduction for the codes with length N = 1024. By using Nangate FreePDK 45nm process, proposed design can reach throughput up to 5.81 Gbps and 2.01 Gbps for (1024, 870) and (1024, 512) polar code, respectively.
Analysis of Stopping Active Learning based on Stabilizing Predictions
Venue: arXiv cs.LG 2015
Year: 2015

Within the natural language processing (NLP) community, active learning has been widely investigated and applied in order to alleviate the annotation bottleneck faced by developers of new NLP systems and technologies. This paper presents the first theoretical analysis of stopping active learning based on stabilizing predictions (SP). The analysis has revealed three elements that are central to the success of the SP method: (1) bounds on Cohen's Kappa agreement between successively trained models impose bounds on differences in F-measure performance of the models; (2) since the stop set does not have to be labeled, it can be made large in practice, helping to guarantee that the results transfer to previously unseen streams of examples at test/application time; and (3) good (low variance) sample estimates of Kappa between successive models can be obtained. Proofs of relationships between the level of Kappa agreement and the difference in performance between consecutive models are presented. Specifically, if the Kappa agreement between two models exceeds a threshold T (where $T>0$), then the difference in F-measure performance between those models is bounded above by $\frac{4(1-T)}{T}$ in all cases. If precision of the positive conjunction of the models is assumed to be $p$, then the bound can be tightened to $\frac{4(1-T)}{(p+1)T}$.
Depth-based hand pose estimation: methods, data, and challenges
Venue: arXiv cs.CV 2015
Year: 2015

Hand pose estimation has matured rapidly in recent years. The introduction of commodity depth sensors and a multitude of practical applications have spurred new advances. We provide an extensive analysis of the state-of-the-art, focusing on hand pose estimation from a single depth frame. To do so, we have implemented a considerable number of systems, and will release all software and evaluation code. We summarize important conclusions here: (1) Pose estimation appears roughly solved for scenes with isolated hands. However, methods still struggle to analyze cluttered scenes where hands may be interacting with nearby objects and surfaces. To spur further progress we introduce a challenging new dataset with diverse, cluttered scenes. (2) Many methods evaluate themselves with disparate criteria, making comparisons difficult. We define a consistent evaluation criteria, rigorously motivated by human experiments. (3) We introduce a simple nearest-neighbor baseline that outperforms most existing systems. This implies that most systems do not generalize beyond their training sets. This also reinforces the under-appreciated point that training data is as important as the model itself. We conclude with directions for future progress.
On the Stability of Online Language Features: How Much Text do you Need to know a Person?
Venue: arXiv cs.CL 2015
Year: 2015

In recent years, numerous studies have inferred personality and other traits from people's online writing. While these studies are encouraging, more information is needed in order to use these techniques with confidence. How do linguistic features vary across different online media, and how much text is required to have a representative sample for a person? In this paper, we examine several large sets of online, user-generated text, drawn from Twitter, email, blogs, and online discussion forums. We examine and compare population-wide results for the linguistic measure LIWC, and the inferred traits of Big5 Personality and Basic Human Values. We also empirically measure the stability of these traits across different sized samples for each individual. Our results highlight the importance of tuning models to each online medium, and include guidelines for the minimum amount of text required for a representative result.
A Framework for Managing Evolving Information Resources on the Data Web
Venue: arXiv cs.DB 2015
Year: 2015

The web of data has brought forth the need to preserve and sustain evolving information within linked datasets; however, a basic requirement of data preservation is the maintenance of the datasets' structural characteristics as well. As open data are often found using different and/or heterogeneous data models and schemata from one source to another, there is a need to reconcile these mismatches and provide common denominations of interpretation on a multitude of levels, in order to be able to preserve and manage the evolution of the generated resources. In this paper, we present a linked data approach for the preservation and archiving of open heterogeneous datasets that evolve through time, at both the structural and the semantic layer. We first propose a set of re-quirements for modelling evolving linked datasets. We then proceed on concep-tualizing a modelling framework for evolving entities and place these in a 2x2 model space that consists of the semantic and the temporal dimensions.
Understanding Game Theory via Wireless Power Control
Venue: arXiv cs.GT 2015
Year: 2015

In this lecture note, we introduce the basic concepts of game theory (GT), a branch of mathematics traditionally studied and applied in the areas of economics, political science, and biology, which has emerged in the last fifteen years as an effective framework for communications, networking, and signal processing (SP). The real catalyzer has been the blooming of all issues related to distributed networks, in which the nodes can be modeled as players in a game competing for system resources. Some relevant notions of GT are introduced by elaborating on a simple application in the context of wireless communications, notably the power control in an interference channel (IC) with two transmitters and two receivers.
Motion Planning for Multi-Link Robots by Implicit Configuration-Space Tiling
Venue: arXiv cs.RO 2015
Year: 2015

We study the problem of motion-planning for free-flying multi-link robots and develop a sampling-based algorithm that is specifically tailored for the task. Our work is based on the simple observation that the set of configurations for which the robot is self-collision free is independent of the obstacles or of the exact placement of the robot. This allows to eliminate the need to perform costly self-collision checks online when solving motion-planning problems, assuming some offline preprocessing. In particular, given a specific robot type our algorithm precomputes a tiling roadmap, which efficiently and implicitly encodes the self-collision free (sub-)space over the entire configuration space, where the latter can be infinite for that matter. To answer any query, in any given scenario, we traverse the tiling roadmap while only testing for collisions with obstacles. Our algorithm suggests more flexibility than the prevailing paradigm in which a precomputed roadmap depends both on the robot and on the scenario at hand. We show through various simulations the effectiveness of this approach on open and closed-chain multi-link robots, where in some settings our algorithm is more than fifty times faster than the state-of-the-art.
Approximating LZ77 via Small-Space Multiple-Pattern Matching
Venue: arXiv cs.DS 2015
Year: 2015

We generalize Karp-Rabin string matching to handle multiple patterns in $\mathcal{O}(n \log n + m)$ time and $\mathcal{O}(s)$ space, where $n$ is the length of the text and $m$ is the total length of the $s$ patterns, returning correct answers with high probability. As a prime application of our algorithm, we show how to approximate the LZ77 parse of a string of length $n$. If the optimal parse consists of $z$ phrases, using only $\mathcal{O}(z)$ working space we can return a parse consisting of at most $(1+\varepsilon)z$ phrases in $\mathcal{O}(\varepsilon^{-1}n\log n)$ time, for any $\varepsilon\in (0,1]$. As previous quasilinear-time algorithms for LZ77 use $Ω(n/\textrm{polylog }n)$ space, but $z$ can be exponentially small in $n$, these improvements in space are substantial.
Efficient Non-parametric Estimation of Multiple Embeddings per Word in Vector Space
Venue: arXiv cs.CL 2015
Year: 2015

There is rising interest in vector-space word embeddings and their use in NLP, especially given recent methods for their fast estimation at very large scale. Nearly all this work, however, assumes a single vector per word type ignoring polysemy and thus jeopardizing their usefulness for downstream tasks. We present an extension to the Skip-gram model that efficiently learns multiple embeddings per word type. It differs from recent related work by jointly performing word sense discrimination and embedding learning, by non-parametrically estimating the number of senses per word type, and by its efficiency and scalability. We present new state-of-the-art results in the word similarity in context task and demonstrate its scalability by training with one machine on a corpus of nearly 1 billion tokens in less than 6 hours.
Locating influential nodes via dynamics-sensitive centrality
Venue: arXiv cs.SI 2015
Year: 2015

With great theoretical and practical significance, locating influential nodes of complex networks is a promising issues. In this paper, we propose a dynamics-sensitive (DS) centrality that integrates topological features and dynamical properties. The DS centrality can be directly applied in locating influential spreaders. According to the empirical results on four real networks for both susceptible-infected-recovered (SIR) and susceptible-infected (SI) spreading models, the DS centrality is much more accurate than degree, $k$-shell index and eigenvector centrality.
Faster Lightweight Lempel-Ziv Parsing
Venue: arXiv cs.DS 2015
Year: 2015

We present an algorithm that computes the Lempel-Ziv decomposition in $O(n(\logσ+ \log\log n))$ time and $n\logσ+ εn$ bits of space, where $ε$ is a constant rational parameter, $n$ is the length of the input string, and $σ$ is the alphabet size. The $n\logσ$ bits in the space bound are for the input string itself which is treated as read-only.
SIFT Vs SURF: Quantifying the Variation in Transformations
Venue: arXiv cs.CV 2015
Year: 2015

This paper studies the robustness of SIFT and SURF against different image transforms (rigid body, similarity, affine and projective) by quantitatively analyzing the variations in the extent of transformations. Previous studies have been comparing the two techniques on absolute transformations rather than the specific amount of deformation caused by the transformation. The paper establishes an exhaustive empirical analysis of such deformations and matching capability of SIFT and SURF with variations in matching parameters and the amount of tolerance. This is helpful in choosing the specific use case for applying these techniques.
Degrees of Freedom of Interference Channels with Hybrid Beam-forming
Venue: arXiv cs.IT 2015
Year: 2015

We study the sum degrees of freedom (DoF) of interference channels with hybrid beam-forming in which hybrid beam-forming composed of analog and digital precodings is employed at each node. For the two-user case, we completely characterize the sum DoF for an arbitrary number of antennas and RF chains by developing an achievable scheme optimized for the hybrid beam-forming structure and deriving its matching upper bound. For a general K-user case, we focus on a symmetric case and obtain lower and upper bounds on the sum DoF, which are tight for certain cases. The results show that hybrid beam-forming can increase the sum DoF of interference channel under certain conditions while it cannot improve the sum DoFs of point-to-point channel, multiple access channel, and broadcast channel. The key insights on this gain is that hybrid beam-forming enables users to manage inter user interference better, and thus each user can increase the dimension of interference-free signal space for its own desired signals.