OpenRaiser/Intern-Atlas huggingface dataset:
Deep Sentence Embedding Using Long Short-Term Memory Networks: Analysis and Application to Information Retrieval
Venue: arXiv cs.CL 2016
Year: 2016

This paper develops a model that addresses sentence embedding, a hot topic in current natural language processing research, using recurrent neural networks with Long Short-Term Memory (LSTM) cells. Due to its ability to capture long term memory, the LSTM-RNN accumulates increasingly richer information as it goes through the sentence, and when it reaches the last word, the hidden layer of the network provides a semantic representation of the whole sentence. In this paper, the LSTM-RNN is trained in a weakly supervised manner on user click-through data logged by a commercial web search engine. Visualization and analysis are performed to understand how the embedding process works. The model is found to automatically attenuate the unimportant words and detects the salient keywords in the sentence. Furthermore, these detected keywords are found to automatically activate different cells of the LSTM-RNN, where words belonging to a similar topic activate the same cell. As a semantic representation of the sentence, the embedding vector can be used in many different applications. These automatic keyword detection and topic allocation abilities enabled by the LSTM-RNN allow the network to perform document retrieval, a difficult language processing task, where the similarity between the query and documents can be measured by the distance between their corresponding sentence embedding vectors computed by the LSTM-RNN. On a web search task, the LSTM-RNN embedding is shown to significantly outperform several existing state of the art methods. We emphasize that the proposed model generates sentence embedding vectors that are specially useful for web document retrieval tasks. A comparison with a well known general sentence embedding method, the Paragraph Vector, is performed. The results show that the proposed method in this paper significantly outperforms it for web document retrieval task.
On the complexity of computing the $k$-restricted edge-connectivity of a graph
Venue: arXiv cs.DS 2016
Year: 2016

The \emph{$k$-restricted edge-connectivity} of a graph $G$, denoted by $λ_k(G)$, is defined as the minimum size of an edge set whose removal leaves exactly two connected components each containing at least $k$ vertices. This graph invariant, which can be seen as a generalization of a minimum edge-cut, has been extensively studied from a combinatorial point of view. However, very little is known about the complexity of computing $λ_k(G)$. Very recently, in the parameterized complexity community the notion of \emph{good edge separation} of a graph has been defined, which happens to be essentially the same as the $k$-restricted edge-connectivity. Motivated by the relevance of this invariant from both combinatorial and algorithmic points of view, in this article we initiate a systematic study of its computational complexity, with special emphasis on its parameterized complexity for several choices of the parameters. We provide a number of NP-hardness and W[1]-hardness results, as well as FPT-algorithms.
Simulating Auxiliary Inputs, Revisited
Venue: arXiv cs.CR 2016
Year: 2016

For any pair $(X,Z)$ of correlated random variables we can think of $Z$ as a randomized function of $X$. Provided that $Z$ is short, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as \emph{simulating auxiliary inputs}. This idea of simulating auxiliary information turns out to be a powerful tool in computer science, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: \begin{enumerate}[(a)] We discuss and compare efficiency of known results, finding the flaw in the best known bound claimed in the TCC'14 paper "How to Fake Auxiliary Inputs". We present a novel boosting algorithm for constructing the simulator. Our technique essentially fixes the flaw. This boosting proof is of independent interest, as it shows how to handle "negative mass" issues when constructing probability measures in descent algorithms. Our bounds are much better than bounds known so far. To make the simulator $(s,ε)$-indistinguishable we need the complexity $O\left(s\cdot 2^{5\ell}ε^{-2}\right)$ in time/circuit size, which is better by a factor $ε^{-2}$ compared to previous bounds. In particular, with our technique we (finally) get meaningful provable security for the EUROCRYPT'09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like $\mathsf{AES256}$.
Matrix Product State for Feature Extraction of Higher-Order Tensors
Venue: arXiv cs.CV 2016
Year: 2016

This paper introduces matrix product state (MPS) decomposition as a computational tool for extracting features of multidimensional data represented by higher-order tensors. Regardless of tensor order, MPS extracts its relevant features to the so-called core tensor of maximum order three which can be used for classification. Mainly based on a successive sequence of singular value decompositions (SVD), MPS is quite simple to implement without any recursive procedure needed for optimizing local tensors. Thus, it leads to substantial computational savings compared to other tensor feature extraction methods such as higher-order orthogonal iteration (HOOI) underlying the Tucker decomposition (TD). Benchmark results show that MPS can reduce significantly the feature space of data while achieving better classification performance compared to HOOI.
Counting Triangles in Large Graphs on GPU
Venue: arXiv cs.DC 2016
Year: 2016

The clustering coefficient and the transitivity ratio are concepts often used in network analysis, which creates a need for fast practical algorithms for counting triangles in large graphs. Previous research in this area focused on sequential algorithms, MapReduce parallelization, and fast approximations. In this paper we propose a parallel triangle counting algorithm for CUDA GPU. We describe the implementation details necessary to achieve high performance and present the experimental evaluation of our approach. Our algorithm achieves 8 to 15 times speedup over the CPU implementation and is capable of finding 3.8 billion triangles in an 89 million edges graph in less than 10 seconds on the Nvidia Tesla C2050 GPU.
Multiscale Combinatorial Grouping for Image Segmentation and Object Proposal Generation
Venue: arXiv cs.CV 2016
Year: 2016

We propose a unified approach for bottom-up hierarchical image segmentation and object proposal generation for recognition, called Multiscale Combinatorial Grouping (MCG). For this purpose, we first develop a fast normalized cuts algorithm. We then propose a high-performance hierarchical segmenter that makes effective use of multiscale information. Finally, we propose a grouping strategy that combines our multiscale regions into highly-accurate object proposals by exploring efficiently their combinatorial space. We also present Single-scale Combinatorial Grouping (SCG), a faster version of MCG that produces competitive proposals in under five second per image. We conduct an extensive and comprehensive empirical validation on the BSDS500, SegVOC12, SBD, and COCO datasets, showing that MCG produces state-of-the-art contours, hierarchical regions, and object proposals.
Tropical Dominating Sets in Vertex-Coloured Graphs
Venue: arXiv cs.DM 2016
Year: 2016

Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that the tropical dominating set problem is NP-complete even when restricted to a simple path. Then, we establish upper bounds related to various parameters of the graph such as minimum degree and number of edges. We also give upper bounds for random graphs. Last, we give approximability and inapproximability results for general and restricted classes of graphs, and establish a FPT algorithm for interval graphs.
Maximizing Monotone Submodular Functions over the Integer Lattice
Venue: arXiv cs.DS 2016
Year: 2016

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function $f:\mathbb{Z}_+^n \to \mathbb{R}_+$ is given via an evaluation oracle. Assume further that $f$ satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time $(1-1/e-ε)$-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a $(1-1/e-ε)$-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property.
Wireless Sensor Network Virtualization: A Survey
Venue: arXiv cs.NI 2016
Year: 2016

Wireless Sensor Networks (WSNs) are the key components of the emerging Internet-of-Things (IoT) paradigm. They are now ubiquitous and used in a plurality of application domains. WSNs are still domain specific and usually deployed to support a specific application. However, as WSN nodes are becoming more and more powerful, it is getting more and more pertinent to research how multiple applications could share a very same WSN infrastructure. Virtualization is a technology that can potentially enable this sharing. This paper is a survey on WSN virtualization. It provides a comprehensive review of the state-of-the-art and an in-depth discussion of the research issues. We introduce the basics of WSN virtualization and motivate its pertinence with carefully selected scenarios. Existing works are presented in detail and critically evaluated using a set of requirements derived from the scenarios. The pertinent research projects are also reviewed. Several research issues are also discussed with hints on how they could be tackled.
Mapping-equivalence and oid-equivalence of single-function object-creating conjunctive queries
Venue: arXiv cs.DB 2016
Year: 2016

Conjunctive database queries have been extended with a mechanism for object creation to capture important applications such as data exchange, data integration, and ontology-based data access. Object creation generates new object identifiers in the result, that do not belong to the set of constants in the source database. The new object identifiers can be also seen as Skolem terms. Hence, object-creating conjunctive queries can also be regarded as restricted second-order tuple-generating dependencies (SO tgds), considered in the data exchange literature. In this paper, we focus on the class of single-function object-creating conjunctive queries, or sifo CQs for short. We give a new characterization for oid-equivalence of sifo CQs that is simpler than the one given by Hull and Yoshikawa and places the problem in the complexity class NP. Our characterization is based on Cohen's equivalence notions for conjunctive queries with multiplicities. We also solve the logical entailment problem for sifo CQs, showing that also this problem belongs to NP. Results by Pichler et al. have shown that logical equivalence for more general classes of SO tgds is either undecidable or decidable with as yet unknown complexity upper bounds.
Learning Equilibria of a Stochastic Game on Gaussian Interference Channels with Incomplete Information
Venue: arXiv cs.IT 2016
Year: 2016

We consider a wireless communication system in which $N$ transmitter-receiver pairs want to communicate with each other. Each transmitter transmits data at a certain rate using a power that depends on the channel gain to its receiver. If a receiver can successfully receive the message, it sends an acknowledgment (ACK), else it sends a negative ACK (NACK). Each user aims to maximize its probability of successful transmission. We formulate this problem as a stochastic game and propose a fully distributed learning algorithm to find a correlated equilibrium (CE). In addition, we use a no regret algorithm to find a coarse correlated equilibrium (CCE) for our power allocation game. We also propose a fully distributed learning algorithm to find a Pareto optimal solution. In general Pareto points do not guarantee fairness among the users, therefore we also propose an algorithm to compute a Nash bargaining solution which is Pareto optimal and provides fairness among users. Finally, under the same game theoretic setup, we study these equilibria and Pareto points when each transmitter sends data at multiple rates rather than at a fixed rate. We compare the sum rate obtained at the CE, CCE, Nash bargaining solution and the Pareto point and also via some other well known recent algorithms.
Prototyping Real-Time Full Duplex Radios
Venue: arXiv cs.IT 2016
Year: 2016

In this article, we present a real-time full duplex radio system for 5G wireless networks. Full duplex radios are capable of opening new possibilities in contexts of high traffic demand where there are limited radio resources. A critical issue, however, to implementing full duplex radios, in real wireless environments, is being able to cancel self-interference. To overcome the self-interference challenge, we prototype our design on a software-defined radio (SDR) platform. This design combines a dual-polarization antenna-based analog part with a digital self-interference canceller that operates in real-time. Prototype test results confirm that the proposed full-duplex system achieves about 1.9 times higher throughput than a half-duplex system. This article concludes with a discussion of implementationchallenges that remain for researchers seeking the most viable solution for full duplex communications.
Nonadaptive group testing with random set of defectives
Venue: arXiv cs.IT 2016
Year: 2016

In a group testing scheme, a set of tests is designed to identify a small number $t$ of defective items that are present among a large number $N$ of items. Each test takes as input a group of items and produces a binary output indicating whether any defective item is present in the group. In a non-adaptive scheme designing a testing scheme is equivalent to the construction of a disjunct matrix, an $M \times N$ binary matrix where the union of supports of any $t$ columns does not contain the support of any other column. In this paper we consider the scenario where defective items are random and follow simple probability distributions. In particular we consider the cases where 1) each item can be defective independently with probability $\frac{t}{N}$ and 2) each $t$-set of items can be defective with uniform probability. In both cases our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before and it is known that $O(t\log N)$ tests are necessary as well as sufficient (via random coding) in both cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on \emph{constant-weight error-correcting codes} and their minimum distance. We go beyond the minimum distance analysis and connect the average distance of a constant weight code to the parameters of the resulting test matrix. With our relaxed requirements, we show that using explicit constant-weight codes (e.g., based on algebraic geometry codes) we may achieve a number of tests equal to $O(t \frac{\log^2 N}{ \log t})$ for both the first and the second cases.
Capacity of Random Channels with Large Alphabets
Venue: arXiv cs.IT 2016
Year: 2016

We consider discrete memoryless channels with input alphabet size $n$ and output alphabet size $m$, where $m=$ceil$(γn)$ for some constant $γ>0$. The channel transition matrix consists of entries that, before being normalised, are independent and identically distributed nonnegative random variables $V$ and such that $E[(V \log V)^2]<\infty$. We prove that in the limit as $n\to \infty$ the capacity of such a channel converges to $Ent(V) / E[V]$ almost surely and in $L^2$, where $Ent(V):= E[V\log V]-E[V] \log E[V]$ denotes the entropy of $V$. We further show that, under slightly different model assumptions, the capacity of these random channels converges to this asymptotic value exponentially in $n$. Finally, we present an application in the context of Bayesian optimal experiment design.
Exploring the Practical Limits of Cooperative Awareness in Vehicular Communications
Venue: arXiv cs.NI 2016
Year: 2016

We perform an extensive study of cooperative awareness in vehicular communication based on periodic message exchange. We start by analyzing measurements collected on four test sites across Europe. To measure cooperative awareness, we use three metrics: 1) neighborhood awareness ratio; 2) ratio of neighbors above range; and 3) packet delivery rate. Using the collected data, we define a simple model for calculating neighborhood awareness given packet delivery ratio for a given environment. Finally, we perform realistic, large-scale simulations to explore the achievable performance of cooperative awareness under realistic transmit power and transmit rate constraints. Our measurements and simulation results show that: i) above a certain threshold, there is little benefit in increasing cooperative message rate to improve the awareness; higher transmit power and fewer messages transmissions are a better approach, since message delivery is dominated by shadowing. ii) the efficacy of cooperative awareness varies greatly in different environments on both large scale (e.g., 90\% awareness is achievable up to 200~m in urban and over 500~m in highway) and small scale (e.g., vehicles in nearby streets can have significantly different awareness); iii) V2V and V2I communication have distinct awareness patterns; iv) each location has a distinct transmit power that achieves high awareness; and v) achieving high awareness levels results in increased reception of potentially unwanted messages; therefore, a balance needs to be found between awareness and interference, depending on the specific context. We hope our results will serve as a starting point for designing more effective periodic message exchange services for cooperative awareness.
Communication Efficient Distributed Kernel Principal Component Analysis
Venue: arXiv cs.LG 2016
Year: 2016

Kernel Principal Component Analysis (KPCA) is a key machine learning algorithm for extracting nonlinear features from data. In the presence of a large volume of high dimensional data collected in a distributed fashion, it becomes very costly to communicate all of this data to a single data center and then perform kernel PCA. Can we perform kernel PCA on the entire dataset in a distributed and communication efficient fashion while maintaining provable and strong guarantees in solution quality? In this paper, we give an affirmative answer to the question by developing a communication efficient algorithm to perform kernel PCA in the distributed setting. The algorithm is a clever combination of subspace embedding and adaptive sampling techniques, and we show that the algorithm can take as input an arbitrary configuration of distributed datasets, and compute a set of global kernel principal components with relative error guarantees independent of the dimension of the feature space or the total number of data points. In particular, computing $k$ principal components with relative error $ε$ over $s$ workers has communication cost $\tilde{O}(s ρk/ε+s k^2/ε^3)$ words, where $ρ$ is the average number of nonzero entries in each data point. Furthermore, we experimented the algorithm with large-scale real world datasets and showed that the algorithm produces a high quality kernel PCA solution while using significantly less communication than alternative approaches.
Study of all the periods of a Neuronal Recurrence Equation
Venue: arXiv cs.NE 2016
Year: 2016

We characterize the structure of the periods of a neuronal recurrence equation. Firstly, we give a characterization of k-chains in 0-1 periodic sequences. Secondly, we characterize the periods of all cycles of some neuronal recurrence equation. Thirdly, we explain how these results can be used to deduce the existence of the generalized period-halving bifurcation.
A Robust and Efficient Method for Solving Point Distance Problems by Homotopy
Venue: arXiv cs.CG 2016
Year: 2016

The goal of Point Distance Solving Problems is to find 2D or 3D placements of points knowing distances between some pairs of points. The common guideline is to solve them by a numerical iterative method (\emph{e.g.} Newton-Raphson method). A sole solution is obtained whereas many exist. However the number of solutions can be exponential and methods should provide solutions close to a sketch drawn by the user.Geometric reasoning can help to simplify the underlying system of equations by changing a few equations and triangularizing it.This triangularization is a geometric construction of solutions, called construction plan. We aim at finding several solutions close to the sketch on a one-dimensional path defined by a global parameter-homotopy using a construction plan. Some numerical instabilities may be encountered due to specific geometric configurations. We address this problem by changing on-the-fly the construction plan.Numerical results show that this hybrid method is efficient and robust.
Socializing the Semantic Gap: A Comparative Survey on Image Tag Assignment, Refinement and Retrieval
Venue: arXiv cs.IR 2016
Year: 2016

Where previous reviews on content-based image retrieval emphasize on what can be seen in an image to bridge the semantic gap, this survey considers what people tag about an image. A comprehensive treatise of three closely linked problems, i.e., image tag assignment, refinement, and tag-based image retrieval is presented. While existing works vary in terms of their targeted tasks and methodology, they rely on the key functionality of tag relevance, i.e. estimating the relevance of a specific tag with respect to the visual content of a given image and its social context. By analyzing what information a specific method exploits to construct its tag relevance function and how such information is exploited, this paper introduces a taxonomy to structure the growing literature, understand the ingredients of the main works, clarify their connections and difference, and recognize their merits and limitations. For a head-to-head comparison between the state-of-the-art, a new experimental protocol is presented, with training sets containing 10k, 100k and 1m images and an evaluation on three test sets, contributed by various research groups. Eleven representative works are implemented and evaluated. Putting all this together, the survey aims to provide an overview of the past and foster progress for the near future.
Fine-grained Language Composition: A Case Study
Venue: arXiv cs.PL 2016
Year: 2016

Although run-time language composition is common, it normally takes the form of a crude Foreign Function Interface (FFI). While useful, such compositions tend to be coarse-grained and slow. In this paper we introduce a novel fine-grained syntactic composition of PHP and Python which allows users to embed each language inside the other, including referencing variables across languages. This composition raises novel design and implementation challenges. We show that good solutions can be found to the design challenges; and that the resulting implementation imposes an acceptable performance overhead of, at most, 2.6x.