OpenRaiser/Intern-Atlas huggingface dataset:
Aggregating Binary Local Descriptors for Image Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

Content-Based Image Retrieval based on local features is computationally expensive because of the complexity of both extraction and matching of local feature. On one hand, the cost for extracting, representing, and comparing local visual descriptors has been dramatically reduced by recently proposed binary local features. On the other hand, aggregation techniques provide a meaningful summarization of all the extracted feature of an image into a single descriptor, allowing us to speed up and scale up the image search. Only a few works have recently mixed together these two research directions, defining aggregation methods for binary local features, in order to leverage on the advantage of both approaches. In this paper, we report an extensive comparison among state-of-the-art aggregation methods applied to binary features. Then, we mathematically formalize the application of Fisher Kernels to Bernoulli Mixture Models. Finally, we investigate the combination of the aggregated binary features with the emerging Convolutional Neural Network (CNN) features. Our results show that aggregation methods on binary features are effective and represent a worthwhile alternative to the direct matching. Moreover, the combination of the CNN with the Fisher Vector (FV) built upon binary features allowed us to obtain a relative improvement over the CNN results that is in line with that recently obtained using the combination of the CNN with the FV built upon SIFTs. The advantage of using the FV built upon binary features is that the extraction process of binary features is about two order of magnitude faster than SIFTs.
Distributed Observers for LTI Systems
Venue: arXiv cs.SY 2017
Year: 2017

We consider the problem of distributed state estimation of a linear time-invariant (LTI) system by a network of sensors. We develop a distributed observer that guarantees asymptotic reconstruction of the state for the most general class of LTI systems, sensor network topologies and sensor measurement structures. Our analysis builds upon the following key observation - a given node can reconstruct a portion of the state solely by using its own measurements and constructing appropriate Luenberger observers; hence it only needs to exchange information with neighbors (via consensus dynamics) for estimating the portion of the state that is not locally detectable. This intuitive approach leads to a new class of distributed observers with several appealing features. Furthermore, by imposing additional constraints on the system dynamics and network topology, we show that it is possible to construct a simpler version of the proposed distributed observer that achieves the same objective while admitting a fully distributed design phase. Our general framework allows extensions to time-varying networks that result from communication losses, and scenarios including faults or attacks at the nodes.
Outage Behavior of Integer Forcing With Random Unitary Pre-Processing
Venue: arXiv cs.IT 2017
Year: 2017

Integer forcing is an equalization scheme for the multiple-input multiple-output communication channel that has been demonstrated to allow operating close to capacity for "most" channels. In this work, the measure of "bad" channels is quantified by considering a compound channel setting where the transmitter communicates over a fixed channel but knows only its mutual information. The transmitter encodes the data into independent streams, all taken from the same linear code. The coded streams are transmitted after applying a unitary transformation. At the receiver side, integer-forcing equalization is applied, followed by standard single-stream decoding. Considering pre-processing matrices drawn from a random ensemble, outage corresponds to the event that the target rate exceeds the achievable rate of integer forcing for a given channel matrix. For the case of the circular unitary ensemble, an explicit universal bound on the outage probability for a given target rate is derived that holds for any channel in the compound class. The derived bound depends only on the gap-to-capacity and the number of transmit antennas. The results are also applied to obtain universal bounds on the gap-to-capacity of multiple-antenna closed-loop multicast, achievable via linear pre-processed integer forcing.
Bound-Based Power Optimization for Multi-Hop Heterogeneous Wireless Industrial Networks Under Statistical Delay Constraints
Venue: arXiv cs.PF 2017
Year: 2017

The noticeably increased deployment of wireless networks for battery-limited industrial applications in recent years highlights the need for tractable performance analysis methodologies as well as efficient QoS-aware transmit power management schemes. In this work, we seek to combine several important aspects of such networks, i.e., multi-hop connectivity, channel heterogeneity and the queuing effect, in order to address these needs. We design delay-bound-based algorithms for transmit power minimization and network lifetime maximization of multi-hop heterogeneous wireless networks using our previously developed stochastic network calculus approach for performance analysis of a cascade of buffered wireless fading channels. Our analysis shows an overall transmit power saving of up to 95% compared to a fixed power allocation scheme when using a service model in terms of the Shannon capacity limit. For a more realistic set-up, we evaluate the performance of the suggested algorithm in a WirelessHART network, which is a widely used communication standard for process automation and other industrial applications. We find that link heterogeneity can significantly reduce network lifetime when no efficient power management is applied. Moreover, we show, using extensive simulation study, that the proposed bound-based power allocation performs reasonably well compared to the real optimum, especially in the case of WirelessHART networks.
A General Characterization of the Statistical Query Complexity
Venue: arXiv cs.LG 2017
Year: 2017

Statistical query (SQ) algorithms are algorithms that have access to an {\em SQ oracle} for the input distribution $D$ instead of i.i.d.~ samples from $D$. Given a query function $ϕ:X \rightarrow [-1,1]$, the oracle returns an estimate of ${\bf E}_{ x\sim D}[ϕ(x)]$ within some tolerance $τ_ϕ$ that roughly corresponds to the number of samples. In this work we demonstrate that the complexity of solving general problems over distributions using SQ algorithms can be captured by a relatively simple notion of statistical dimension that we introduce. SQ algorithms capture a broad spectrum of algorithmic approaches used in theory and practice, most notably, convex optimization techniques. Hence our statistical dimension allows to investigate the power of a variety of algorithmic approaches by analyzing a single linear-algebraic parameter. Such characterizations were investigated over the past 20 years in learning theory but prior characterizations are restricted to the much simpler setting of classification problems relative to a fixed distribution on the domain (Blum et al., 1994; Bshouty and Feldman, 2002; Yang, 2001; Simon, 2007; Feldman, 2012; Szorenyi, 2009). Our characterization is also the first to precisely characterize the necessary tolerance of queries. We give applications of our techniques to two open problems in learning theory and to algorithms that are subject to memory and communication constraints.
Blankets Joint Posterior score for learning Markov network structures
Venue: arXiv cs.AI 2017
Year: 2017

Markov networks are extensively used to model complex sequential, spatial, and relational interactions in a wide range of fields. By learning the structure of independences of a domain, more accurate joint probability distributions can be obtained for inference tasks or, more directly, for interpreting the most significant relations among the variables. Recently, several researchers have investigated techniques for automatically learning the structure from data by obtaining the probabilistic maximum-a-posteriori structure given the available data. However, all the approximations proposed decompose the posterior of the whole structure into local sub-problems, by assuming that the posteriors of the Markov blankets of all the variables are mutually independent. In this work, we propose a scoring function for relaxing such assumption. The Blankets Joint Posterior score computes the joint posterior of structures as a joint distribution of the collection of its Markov blankets. Essentially, the whole posterior is obtained by computing the posterior of the blanket of each variable as a conditional distribution that takes into account information from other blankets in the network. We show in our experimental results that the proposed approximation can improve the sample complexity of state-of-the-art scores when learning complex networks, where the independence assumption between blanket variables is clearly incorrect.
Low-Complexity Massive MIMO Subspace Estimation and Tracking from Low-Dimensional Projections
Venue: arXiv cs.IT 2017
Year: 2017

Massive MIMO is a variant of multiuser MIMO, where the number of antennas $M$ at the base-station is large, and generally much larger than the number of spatially multiplexed data streams to/from the users. It has been observed that in many realistic propagation scenarios as well as in spatially correlated channel models used in standardizations, although the user channel vectors have a very high-dim $M$, they lie on low-dim subspaces due to their limited angular spread. This low-dim subspace structure remains stable across many coherence blocks and can be exploited in several ways to improve the system performance. A main challenge, however, is to estimate this signal subspace from samples of users' channel vectors as fast and efficiently as possible. In a recent work, we addressed this problem and proposed a very effective novel algorithm referred to as Approximate Maximum-Likelihood (AML), which was formulated as a semi-definite program (SDP). In this paper, we address two problems left open in our previous work: computational complexity and tracking. The algorithm proposed in this paper is reminiscent of Multiple Measurement Vectors (MMV) problem in Compressed Sensing and is proved to be equivalent to the AML Algorithm for sufficiently dense angular grids. It has also a very low computational complexity and is able to track sharp transitions in the channel statistics very quickly. Although mainly motivated by massive MIMO applications, our proposed algorithm is of independent interest in other related subspace estimation applications. We assess the estimation/tracking performance of our proposed algorithm empirically via numerical simulations, especially in practically relevant situations where a direct implementation of the SDP would be infeasible in real-time. We also compare the performance of our algorithm with other related subspace estimation algorithms in the literature.
Exact Structure Learning of Bayesian Networks by Optimal Path Extension
Venue: arXiv cs.AI 2017
Year: 2017

Bayesian networks are probabilistic graphical models often used in big data analytics. The problem of exact structure learning is to find a network structure that is optimal under certain scoring criteria. The problem is known to be NP-hard and the existing methods are both computationally and memory intensive. In this paper, we introduce a new approach for exact structure learning. Our strategy is to leverage relationship between a partial network structure and the remaining variables to constraint the number of ways in which the partial network can be optimally extended. Via experimental results, we show that the method provides up to three times improvement in runtime, and orders of magnitude reduction in memory consumption over the current best algorithms.
Stochastic Rank-1 Bandits
Venue: arXiv cs.LG 2017
Year: 2017

We propose stochastic rank-$1$ bandits, a class of online learning problems where at each step a learning agent chooses a pair of row and column arms, and receives the product of their values as a reward. The main challenge of the problem is that the individual values of the row and column are unobserved. We assume that these values are stochastic and drawn independently. We propose a computationally-efficient algorithm for solving our problem, which we call Rank1Elim. We derive a $O((K + L) (1 / Δ) \log n)$ upper bound on its $n$-step regret, where $K$ is the number of rows, $L$ is the number of columns, and $Δ$ is the minimum of the row and column gaps; under the assumption that the mean row and column rewards are bounded away from zero. To the best of our knowledge, we present the first bandit algorithm that finds the maximum entry of a rank-$1$ matrix whose regret is linear in $K + L$, $1 / Δ$, and $\log n$. We also derive a nearly matching lower bound. Finally, we evaluate Rank1Elim empirically on multiple problems. We observe that it leverages the structure of our problems and can learn near-optimal solutions even if our modeling assumptions are mildly violated.
Learning Sentimental Influences from Users' Behaviors
Venue: arXiv cs.SI 2017
Year: 2017

Modeling interpersonal influence on different sentimental polarities is a fundamental problem in opinion formation and viral marketing. There has not been seen an effective solution for learning sentimental influences from users' behaviors yet. Previous related works on information propagation directly define interpersonal influence between each pair of users as a parameter, which is independent from each others, even if the influences come from or affect the same user. And influences are learned from user's propagation behaviors, namely temporal cascades, while sentiments are not associated with them. Thus we propose to model the interpersonal influence by latent influence and susceptibility matrices defined on individual users and sentiment polarities. Such low-dimensional and distributed representations naturally make the interpersonal influences related to the same user coupled with each other, and in turn, reduce the model complexity. Sentiments act on different rows of parameter matrices, depicting their effects in modeling cascades. With the iterative optimization algorithm of projected stochastic gradient descent over shuffled mini-batches and Adadelta update rule, negative cases are repeatedly sampled with the distribution of infection frequencies users, for reducing computation cost and optimization imbalance. Experiments are conducted on Microblog dataset. The results show that our model achieves better performance than the state-of-the-art and pair-wise models. Besides, analyzing the distribution of learned users' sentimental influences and susceptibilities results some interesting discoveries.
WikiReading: A Novel Large-scale Language Understanding Task over Wikipedia
Venue: arXiv cs.CL 2017
Year: 2017

We present WikiReading, a large-scale natural language understanding task and publicly-available dataset with 18 million instances. The task is to predict textual values from the structured knowledge base Wikidata by reading the text of the corresponding Wikipedia articles. The task contains a rich variety of challenging classification and extraction sub-tasks, making it well-suited for end-to-end models such as deep neural networks (DNNs). We compare various state-of-the-art DNN-based architectures for document classification, information extraction, and question answering. We find that models supporting a rich answer space, such as word or character sequences, perform best. Our best-performing model, a word-level sequence to sequence model with a mechanism to copy out-of-vocabulary words, obtains an accuracy of 71.8%.
Learning with Value-Ramp
Venue: arXiv cs.LG 2017
Year: 2017

We study a learning principle based on the intuition of forming ramps. The agent tries to follow an increasing sequence of values until the agent meets a peak of reward. The resulting Value-Ramp algorithm is natural, easy to configure, and has a robust implementation with natural numbers.
High-Efficiency Device Positioning and Location-Aware Communications in Dense 5G Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this article, the prospects and enabling technologies for high-efficiency device positioning and location-aware communications in emerging 5G networks are reviewed. We will first describe some key technical enablers and demonstrate by means of realistic ray-tracing and map based evaluations that positioning accuracies below one meter can be achieved by properly fusing direction and delay related measurements on the network side, even when tracking moving devices. We will then discuss the possibilities and opportunities that such high-efficiency positioning capabilities can offer, not only for location-based services in general, but also for the radio access network itself. In particular, we will demonstrate that geometric location-based beamforming schemes become technically feasible, which can offer substantially reduced reference symbol overhead compared to classical full channel state information (CSI)-based beamforming. At the same time, substantial power savings can be realized in future wideband 5G networks where acquiring full CSI calls for wideband reference signals while location estimation and tracking can, in turn, be accomplished with narrowband pilots.
Generalized Assignment Problem: Truthful Mechanism Design without Money
Venue: arXiv cs.GT 2017
Year: 2017

In this paper, we study a problem of truthful mechanism design for a strategic variant of the generalized assignment problem (GAP) in a both payment-free and prior-free environment. In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we study, bins are held by strategic agents, and each agent may hide its compatibility with some items in order to obtain items of higher values. The compatibility between an agent and an item encodes the willingness of the agent to receive the item. Our goal is to maximize total value (sum of agents' values, or social welfare) while certifying no agent can benefit from hiding its compatibility with items. The model has applications in auctions with budgeted bidders. For two variants of the problem, namely \emph{multiple knapsack problem} in which each item has the same size and value over bins, and \emph{density-invariant GAP} in which each item has the same value density over the bins, we propose truthful $4$-approximation algorithms. For the general problem, we propose an $O(\ln{(U/L)})$-approximation mechanism where $U$ and $L$ are the upper and lower bounds for value densities of the compatible item-bin pairs.
Anomaly detection and classification for streaming data using PDEs
Venue: arXiv cs.LG 2017
Year: 2017

Nondominated sorting, also called Pareto Depth Analysis (PDA), is widely used in multi-objective optimization and has recently found important applications in multi-criteria anomaly detection. Recently, a partial differential equation (PDE) continuum limit was discovered for nondominated sorting leading to a very fast approximate sorting algorithm called PDE-based ranking. We propose in this paper a fast real-time streaming version of the PDA algorithm for anomaly detection that exploits the computational advantages of PDE continuum limits. Furthermore, we derive new PDE continuum limits for sorting points within their nondominated layers and show how the new PDEs can be used to classify anomalies based on which criterion was more significantly violated. We also prove statistical convergence rates for PDE-based ranking, and present the results of numerical experiments with both synthetic and real data.
A Strong Baseline for Learning Cross-Lingual Word Embeddings from Sentence Alignments
Venue: arXiv cs.CL 2017
Year: 2017

While cross-lingual word embeddings have been studied extensively in recent years, the qualitative differences between the different algorithms remain vague. We observe that whether or not an algorithm uses a particular feature set (sentence IDs) accounts for a significant performance gap among these algorithms. This feature set is also used by traditional alignment algorithms, such as IBM Model-1, which demonstrate similar performance to state-of-the-art embedding algorithms on a variety of benchmarks. Overall, we observe that different algorithmic approaches for utilizing the sentence ID feature space result in similar performance. This paper draws both empirical and theoretical parallels between the embedding and alignment literature, and suggests that adding additional sources of information, which go beyond the traditional signal of bilingual sentence-aligned corpora, may substantially improve cross-lingual word embeddings, and that future baselines should at least take such features into account.
Efficient Computation of Slepian Functions for Arbitrary Regions on the Sphere
Venue: arXiv cs.DM 2017
Year: 2017

In this paper, we develop a new method for the fast and memory-efficient computation of Slepian functions on the sphere. Slepian functions, which arise as the solution of the Slepian concentration problem on the sphere, have desirable properties for applications where measurements are only available within a spatially limited region on the sphere and/or a function is required to be analyzed over the spatially limited region. Slepian functions are currently not easily computed for large band-limits for an arbitrary spatial region due to high computational and large memory storage requirements. For the special case of a polar cap, the symmetry of the region enables the decomposition of the Slepian concentration problem into smaller subproblems and consequently the efficient computation of Slepian functions for large band-limits. By exploiting the efficient computation of Slepian functions for the polar cap region on the sphere, we develop a formulation, supported by a fast algorithm, for the approximate computation of Slepian functions for an arbitrary spatial region to enable the analysis of modern datasets that support large band-limits. For the proposed algorithm, we carry out accuracy analysis of the approximation, computational complexity analysis, and review of memory storage requirements. We illustrate, through numerical experiments, that the proposed method enables faster computation, and has smaller storage requirements, while allowing for sufficiently accurate computation of the Slepian functions.
Living in Parallel Realities -- Co-Existing Schema Versions with a Bidirectional Database Evolution Language
Venue: arXiv cs.DB 2017
Year: 2017

We introduce end-to-end support of co-existing schema versions within one database. While it is state of the art to run multiple versions of a continuously developed application concurrently, it is hard to do the same for databases. In order to keep multiple co-existing schema versions alive; which are all accessing the same data set; developers usually employ handwritten delta code (e.g. views and triggers in SQL). This delta code is hard to write and hard to maintain: if a database administrator decides to adapt the physical table schema, all handwritten delta code needs to be adapted as well, which is expensive and error-prone in practice. In this paper, we present InVerDa: developers use the simple bidirectional database evolution language BiDEL, which carries enough information to generate all delta code automatically. Without additional effort, new schema versions become immediately accessible and data changes in any version are visible in all schema versions at the same time. InVerDa also allows for easily changing the physical table design without affecting the availability of co-existing schema versions. This greatly increases robustness (orders of magnitude less lines of code) and allows for significant performance optimization. A main contribution is the formal evaluation that each schema version acts like a common full-fledged database schema independently of the chosen physical table design.