OpenRaiser/Intern-Atlas huggingface dataset:
Joint Pilot Sequence Design and Power Control for Max-Min Fairness in Uplink Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

This paper optimizes the pilot assignment and pilot transmit powers to mitigate pilot contamination in Massive MIMO (multiple-input multiple-output) systems. While prior works have treated pilot assignment as a combinatorial problem, we achieve a more tractable problem formulation by directly optimizing the pilot sequences. To this end, we compute a lower bound on the uplink (UL) spectral efficiency (SE), for Rayleigh fading channels with maximum ratio (MR) detection and arbitrary pilot sequences. We optimize the max-min SE with respect to the pilot sequences and pilot powers, under power budget constraints. This becomes an NP-hard signomial problem, but we propose an efficient algorithm to obtain a local optimum with polynomial complexity. Numerical results manifest the near optimality of the proposed algorithm and show significant gains over existing suboptimal algorithms.
Random Triggering Based Sub-Nyquist Sampling System for Sparse Multiband Signal
Venue: arXiv cs.IT 2017
Year: 2017

We propose a novel random triggering based modulated wideband compressive sampling (RT-MWCS) method to facilitate efficient realization of sub-Nyquist rate compressive sampling systems for sparse wideband signals. Under the assumption that the signal is repetitively (not necessarily periodically) triggered, RT-MWCS uses random modulation to obtain measurements of the signal at randomly chosen positions. It uses multiple measurement vector method to estimate the non-zero supports of the signal in the frequency domain. Then, the signal spectrum is solved using least square estimation. The distinct ability of estimating sparse multiband signal is facilitated with the use of level triggering and time to digital converter devices previously used in random equivalent sampling (RES) scheme. Compared to the existing compressive sampling (CS) techniques, such as modulated wideband converter (MWC), RT-MWCS is with simple system architecture and can be implemented with one channel at the cost of more sampling time. Experimental results indicate that, for sparse multiband signal with unknown spectral support, RT-MWCS requires a sampling rate much lower than Nyquist rate, while giving great quality of signal reconstruction.
Neural Episodic Control
Venue: arXiv cs.LG 2017
Year: 2017

Deep reinforcement learning methods attain super-human performance in a wide range of environments. Such methods are grossly inefficient, often taking orders of magnitudes more data than humans to achieve reasonable performance. We propose Neural Episodic Control: a deep reinforcement learning agent that is able to rapidly assimilate new experiences and act upon them. Our agent uses a semi-tabular representation of the value function: a buffer of past experience containing slowly changing state representations and rapidly updated estimates of the value function. We show across a wide range of environments that our agent learns significantly faster than other state-of-the-art, general purpose deep reinforcement learning agents.
Learning across scales - A multiscale method for Convolution Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

In this work we establish the relation between optimal control and training deep Convolution Neural Networks (CNNs). We show that the forward propagation in CNNs can be interpreted as a time-dependent nonlinear differential equation and learning as controlling the parameters of the differential equation such that the network approximates the data-label relation for given training data. Using this continuous interpretation we derive two new methods to scale CNNs with respect to two different dimensions. The first class of multiscale methods connects low-resolution and high-resolution data through prolongation and restriction of CNN parameters. We demonstrate that this enables classifying high-resolution images using CNNs trained with low-resolution images and vice versa and warm-starting the learning process. The second class of multiscale methods connects shallow and deep networks and leads to new training strategies that gradually increase the depths of the CNN while re-using parameters for initializations.
Random vector generation of a semantic space
Venue: arXiv cs.CL 2017
Year: 2017

We show how random vectors and random projection can be implemented in the usual vector space model to construct a Euclidean semantic space from a French synonym dictionary. We evaluate theoretically the resulting noise and show the experimental distribution of the similarities of terms in a neighborhood according to the choice of parameters. We also show that the Schmidt orthogonalization process is applicable and can be used to separate homonyms with distinct semantic meanings. Neighboring terms are easily arranged into semantically significant clusters which are well suited to the generation of realistic lists of synonyms and to such applications as word selection for automatic text generation. This process, applicable to any language, can easily be extended to collocations, is extremely fast and can be updated in real time, whenever new synonyms are proposed.
The Impact of Road Configuration on V2V-based Cooperative Localization
Venue: arXiv cs.SY 2017
Year: 2017

Cooperative localization with map matching has been shown to reduce Global Navigation Satellite System (GNSS) localization error from several meters to sub-meter level by fusing the GNSS measurements of four vehicles in our previous work. While further error reduction is expected to be achievable by increasing the number of vehicles, the quantitative relationship between the estimation error and the number of connected vehicles has neither been systematically investigated nor analytically proved. In this work, a theoretical study is presented that analytically proves the correlation between the localization error and the number of connected vehicles in two cases of practical interest. More specifically, it is shown that, under the assumption of small non-common error, the expected square error of the GNSS common error correction is inversely proportional to the number of vehicles, if the road directions obey a uniform distribution, or inversely proportional to logarithm of the number of vehicles, if the road directions obey a Bernoulli distribution. Numerical simulations are conducted to justify these analytic results. Moreover, the simulation results show that the aforementioned error decrement rates hold even when the assumption of small non-common error is violated.
Theory Morphisms in Church's Type Theory with Quotation and Evaluation
Venue: arXiv cs.LO 2017
Year: 2017

${\rm CTT}_{\rm qe}$ is a version of Church's type theory with global quotation and evaluation operators that is engineered to reason about the interplay of syntax and semantics and to formalize syntax-based mathematical algorithms. ${\rm CTT}_{\rm uqe}$ is a variant of ${\rm CTT}_{\rm qe}$ that admits undefined expressions, partial functions, and multiple base types of individuals. It is better suited than ${\rm CTT}_{\rm qe}$ as a logic for building networks of theories connected by theory morphisms. This paper presents the syntax and semantics of ${\rm CTT}_{\rm uqe}$, defines a notion of a theory morphism from one ${\rm CTT}_{\rm uqe}$ theory to another, and gives two simple examples that illustrate the use of theory morphisms in ${\rm CTT}_{\rm uqe}$.
Sharing Residual Units Through Collective Tensor Factorization in Deep Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Residual units are wildly used for alleviating optimization difficulties when building deep neural networks. However, the performance gain does not well compensate the model size increase, indicating low parameter efficiency in these residual units. In this work, we first revisit the residual function in several variations of residual units and demonstrate that these residual functions can actually be explained with a unified framework based on generalized block term decomposition. Then, based on the new explanation, we propose a new architecture, Collective Residual Unit (CRU), which enhances the parameter efficiency of deep neural networks through collective tensor factorization. CRU enables knowledge sharing across different residual units using shared factors. Experimental results show that our proposed CRU Network demonstrates outstanding parameter efficiency, achieving comparable classification performance to ResNet-200 with the model size of ResNet-50. By building a deeper network using CRU, we can achieve state-of-the-art single model classification accuracy on ImageNet-1k and Places365-Standard benchmark datasets. (Code and trained models are available on GitHub)
No-But-Semantic-Match: Computing Semantically Matched XML Keyword Search Results
Venue: arXiv cs.DB 2017
Year: 2017

Users are rarely familiar with the content of a data source they are querying, and therefore cannot avoid using keywords that do not exist in the data source. Traditional systems may respond with an empty result, causing dissatisfaction, while the data source in effect holds semantically related content. In this paper we study this no-but-semantic-match problem on XML keyword search and propose a solution which enables us to present the top-k semantically related results to the user. Our solution involves two steps: (a) extracting semantically related candidate queries from the original query and (b) processing candidate queries and retrieving the top-k semantically related results. Candidate queries are generated by replacement of non-mapped keywords with candidate keywords obtained from an ontological knowledge base. Candidate results are scored using their cohesiveness and their similarity to the original query. Since the number of queries to process can be large, with each result having to be analyzed, we propose pruning techniques to retrieve the top-$k$ results efficiently. We develop two query processing algorithms based on our pruning techniques. Further, we exploit a property of the candidate queries to propose a technique for processing multiple queries in batch, which improves the performance substantially. Extensive experiments on two real datasets verify the effectiveness and efficiency of the proposed approaches.
What Makes a Good App Description?
Venue: arXiv cs.HC 2017
Year: 2017

In the Google Play store, an introduction page is associated with every mobile application (app) for users to acquire its details, including screenshots, description, reviews, etc. However, it remains a challenge to identify what items influence users most when downloading an app. To explore users' perspective, we conduct a survey to inquire about this question. The results of survey suggest that the participants pay most attention to the app description which gives users a quick overview of the app. Although there exist some guidelines about how to write a good app description to attract more downloads, it is hard to define a high quality app description. Meanwhile, there is no tool to evaluate the quality of app description. In this paper, we employ the method of crowdsourcing to extract the attributes that affect the app descriptions' quality. First, we download some app descriptions from Google Play, then invite some participants to rate their quality with the score from one (very poor) to five (very good). The participants are also requested to explain every score's reasons. By analyzing the reasons, we extract the attributes that the participants consider important during evaluating the quality of app descriptions. Finally, we train the supervised learning models on a sample of 100 app descriptions. In our experiments, the support vector machine model obtains up to 62% accuracy. In addition, we find that the permission, the number of paragraphs and the average number of words in one feature play key roles in defining a good app description.
Fault Tolerant Leader Election in Distributed Systems
Venue: arXiv cs.DC 2017
Year: 2017

There are many distributed systems which use a leader in their logic. When such systems need to be fault tolerant and the current leader suffers a technical problem, it is necesary to apply a special algorithm in order to choose a new leader. In this paper I present a new fault tolerant algorithm which elects a new leader based on a random roulette wheel selection.
On the Deployment of Distributed Antennas for Wireless Power Transfer with Safety Electromagnetic Radiation Level Requirement
Venue: arXiv cs.IT 2017
Year: 2017

The extremely low efficiency is regarded as the bottleneck of Wireless Power Transfer (WPT) technology. To tackle this problem, either enlarging the transfer power or changing the infrastructure of WPT system could be an intuitively proposed way. However, the drastically important issue on the user exposure of electromagnetic radiation is rarely considered while we try to improve the efficiency of WPT. In this paper, a Distributed Antenna Power Beacon (DA-PB) based WPT system where these antennas are uniformly distributed on a circle is analyzed and optimized with the safety electromagnetic radiation level (SERL) requirement. In this model, three key questions are intended to be answered: 1) With the SERL, what is the performance of the harvested power at the users ? 2) How do we configure the parameters to maximize the efficiency of WPT? 3) Under the same constraints, does the DA-PB still have performance gain than the Co-located Antenna PB (CA-PB)? First, the minimum antenna height of DA-PB is derived to make the radio frequency (RF) electromagnetic radiation power density at any location of the charging cell lower than the SERL published by the Federal Communications Commission (FCC). Second, the closed-form expressions of average harvested Direct Current (DC) power per user in the charging cell for pass-loss exponent 2 and 4 are also provided. In order to maximize the average efficiency of WPT, the optimal radii for distributed antennas elements (DAEs) are derived when the pass-loss exponent takes the typical value $2$ and $4$. For comparison, the CA-PB is also analyzed as a benchmark. Simulation results verify our derived theoretical results. And it is shown that the proposed DA-PB indeed achieves larger average harvested DC power than CA-PB and can improve the efficiency of WPT.
Qualitative Assessment of Recurrent Human Motion
Venue: arXiv cs.LG 2017
Year: 2017

Smartphone applications designed to track human motion in combination with wearable sensors, e.g., during physical exercising, raised huge attention recently. Commonly, they provide quantitative services, such as personalized training instructions or the counting of distances. But qualitative monitoring and assessment is still missing, e.g., to detect malpositions, to prevent injuries, or to optimize training success. We address this issue by presenting a concept for qualitative as well as generic assessment of recurrent human motion by processing multi-dimensional, continuous time series tracked with motion sensors. Therefore, our segmentation procedure extracts individual events of specific length and we propose expressive features to accomplish a qualitative motion assessment by supervised classification. We verified our approach within a comprehensive study encompassing 27 athletes undertaking different body weight exercises. We are able to recognize six different exercise types with a success rate of 100% and to assess them qualitatively with an average success rate of 99.3%.
Random CNFs are Hard for Cutting Planes
Venue: arXiv cs.CC 2017
Year: 2017

The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for satisfiability algorithms, and average-case hardness over this distribution has also been linked to hardness of approximation via Feige's hypothesis. We prove that any Cutting Planes refutation for random k-SAT requires exponential size, for k that is logarithmic in the number of variables, in the (interesting) regime where the number of clauses guarantees that the formula is unsatisfiable with high probability.
Learning opacity in Stratal Maximum Entropy Grammar
Venue: arXiv cs.CL 2017
Year: 2017

Opaque phonological patterns are sometimes claimed to be difficult to learn; specific hypotheses have been advanced about the relative difficulty of particular kinds of opaque processes (Kiparsky 1971, 1973), and the kind of data that will be helpful in learning an opaque pattern (Kiparsky 2000). In this paper, we present a computationally implemented learning theory for one grammatical theory of opacity: a Maximum Entropy version of Stratal OT (Bermúdez-Otero 1999, Kiparsky 2000), and test it on simplified versions of opaque French tense-lax vowel alternations and the opaque interaction of diphthong raising and flapping in Canadian English. We find that the difficulty of opacity can be influenced by evidence for stratal affiliation: the Canadian English case is easier if the learner encounters application of raising outside the flapping context, or non-application of raising between words (i.e., <life> with a raised vowel; <lie for> with a non-raised vowel).
Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity
Venue: arXiv cs.LG 2017
Year: 2017

Graph-based semi-supervised learning (SSL) algorithms predict labels for all nodes based on provided labels of a small set of seed nodes. Classic methods capture the graph structure through some underlying diffusion process that propagates through the graph edges. Spectral diffusion, which includes personalized page rank and label propagation, propagates through random walks. Social diffusion propagates through shortest paths. A common ground to these diffusions is their {\em linearity}, which does not distinguish between contributions of few "strong" relations and many "weak" relations. Recently, non-linear methods such as node embeddings and graph convolutional networks (GCN) demonstrated a large gain in quality for SSL tasks. These methods introduce multiple components and greatly vary on how the graph structure, seed label information, and other features are used. We aim here to study the contribution of non-linearity, as an isolated ingredient, to the performance gain. To do so, we place classic linear graph diffusions in a self-training framework. Surprisingly, we observe that SSL using the resulting {\em bootstrapped diffusions} not only significantly improves over the respective non-bootstrapped baselines but also outperform state-of-the-art non-linear SSL methods. Moreover, since the self-training wrapper retains the scalability of the base method, we obtain both higher quality and better scalability.
Constellation Queries over Big Data
Venue: arXiv cs.DB 2017
Year: 2017

A geometrical pattern is a set of points with all pairwise distances (or, more generally, relative distances) specified. Finding matches to such patterns has applications to spatial data in seismic, astronomical, and transportation contexts. For example, a particularly interesting geometric pattern in astronomy is the Einstein cross, which is an astronomical phenomenon in which a single quasar is observed as four distinct sky objects (due to gravitational lensing) when captured by earth telescopes. Finding such crosses, as well as other geometric patterns, is a challenging problem as the potential number of sets of elements that compose shapes is exponentially large in the size of the dataset and the pattern. In this paper, we denote geometric patterns as constellation queries and propose algorithms to find them in large data applications. Our methods combine quadtrees, matrix multiplication, and unindexed join processing to discover sets of points that match a geometric pattern within some additive factor on the pairwise distances. Our distributed experiments show that the choice of composition algorithm (matrix multiplication or nested loops) depends on the freedom introduced in the query geometry through the distance additive factor. Three clearly identified blocks of threshold values guide the choice of the best composition algorithm. Finally, solving the problem for relative distances requires a novel continuous-to-discrete transformation. To the best of our knowledge this paper is the first to investigate constellation queries at scale.
A Unifying Bayesian Optimization Framework for Radio Frequency Localization
Venue: arXiv cs.NI 2017
Year: 2017

We consider the problem of estimating an RF-device's location based on observations, such as received signal strength, from a set of transmitters with known locations. We survey the literature on this problem, showing that previous authors have considered implicitly or explicitly various metrics. We present a novel Bayesian framework that unifies these works and shows how to optimize the location estimation with respect to a given metric. We demonstrate how the framework can incorporate a general class of algorithms, including both model-based methods and data-driven algorithms such fingerprinting. This is illustrated by re-deriving the most popular algorithms within this framework. When used with a data-driven approach, our framework has cognitive self-improving properties in that it provably improves with increasing data compared to traditional methods. Furthermore, we propose using the error-CDF as a unified way of comparing algorithms based on two methods: (i) stochastic dominance, and (ii) an upper bound on error-CDFs. We prove that an algorithm that optimizes any distance based cost function is not stochastically dominated by any other algorithm. This suggests that in lieu of the search for a universally best localization algorithm, the community should focus on finding the best algorithm for a given well-defined objective.
New results on multi-agent system consensus: A graph signal processing perspective
Venue: arXiv cs.SY 2017
Year: 2017

This paper revisits the problem of multi-agent consensus from a graph signal processing perspective. By defining the graph filter from the consensus protocol, we establish the direct relation between average consensus of multi-agent systems and filtering of graph signals. This relation not only provides new insights of the average consensus, it also turns out to be a powerful tool to design effective consensus protocols for uncertain networks, which is difficult to deal with by existing time-domain methods. In this paper, we consider two cases, one is uncertain networks modeled by an estimated Laplacian matrix and a fixed eigenvalue bound, the other is connected graphs with unknown topology. The consensus protocols are designed for both cases based on the protocol filter. Several numerical examples are given to demonstrate the effectiveness of our methods.
A Pursuit of Temporal Accuracy in General Activity Detection
Venue: arXiv cs.CV 2017
Year: 2017

Detecting activities in untrimmed videos is an important but challenging task. The performance of existing methods remains unsatisfactory, e.g., they often meet difficulties in locating the beginning and end of a long complex action. In this paper, we propose a generic framework that can accurately detect a wide variety of activities from untrimmed videos. Our first contribution is a novel proposal scheme that can efficiently generate candidates with accurate temporal boundaries. The other contribution is a cascaded classification pipeline that explicitly distinguishes between relevance and completeness of a candidate instance. On two challenging temporal activity detection datasets, THUMOS14 and ActivityNet, the proposed framework significantly outperforms the existing state-of-the-art methods, demonstrating superior accuracy and strong adaptivity in handling activities with various temporal structures.