OpenRaiser/Intern-Atlas huggingface dataset:
Recurrent Models for Auditory Attention in Multi-Microphone Distance Speech Recognition
Venue: arXiv cs.LG 2016
Year: 2016

Integration of multiple microphone data is one of the key ways to achieve robust speech recognition in noisy environments or when the speaker is located at some distance from the input device. Signal processing techniques such as beamforming are widely used to extract a speech signal of interest from background noise. These techniques, however, are highly dependent on prior spatial information about the microphones and the environment in which the system is being used. In this work, we present a neural attention network that directly combines multi-channel audio to generate phonetic states without requiring any prior knowledge of the microphone layout or any explicit signal preprocessing for speech enhancement. We embed an attention mechanism within a Recurrent Neural Network (RNN) based acoustic model to automatically tune its attention to a more reliable input source. Unlike traditional multi-channel preprocessing, our system can be optimized towards the desired output in one step. Although attention-based models have recently achieved impressive results on sequence-to-sequence learning, no attention mechanisms have previously been applied to learn potentially asynchronous and non-stationary multiple inputs. We evaluate our neural attention model on the CHiME-3 challenge task, and show that the model achieves comparable performance to beamforming using a purely data-driven method.
A Controller-Recognizer Framework: How necessary is recognition for control?
Venue: arXiv cs.LG 2016
Year: 2016

Recently there has been growing interest in building active visual object recognizers, as opposed to the usual passive recognizers which classifies a given static image into a predefined set of object categories. In this paper we propose to generalize these recently proposed end-to-end active visual recognizers into a controller-recognizer framework. A model in the controller-recognizer framework consists of a controller, which interfaces with an external manipulator, and a recognizer which classifies the visual input adjusted by the manipulator. We describe two most recently proposed controller-recognizer models: recurrent attention model and spatial transformer network as representative examples of controller-recognizer models. Based on this description we observe that most existing end-to-end controller-recognizers tightly, or completely, couple a controller and recognizer. We ask a question whether this tight coupling is necessary, and try to answer this empirically by building a controller-recognizer model with a decoupled controller and recognizer. Our experiments revealed that it is not always necessary to tightly couple them and that by decoupling a controller and recognizer, there is a possibility of building a generic controller that is pretrained and works together with any subsequent recognizer.
Integrating Deep Features for Material Recognition
Venue: arXiv cs.CV 2016
Year: 2016

We propose a method for integration of features extracted using deep representations of Convolutional Neural Networks (CNNs) each of which is learned using a different image dataset of objects and materials for material recognition. Given a set of representations of multiple pre-trained CNNs, we first compute activations of features using the representations on the images to select a set of samples which are best represented by the features. Then, we measure the uncertainty of the features by computing the entropy of class distributions for each sample set. Finally, we compute the contribution of each feature to representation of classes for feature selection and integration. We examine the proposed method on three benchmark datasets for material recognition. Experimental results show that the proposed method achieves state-of-the-art performance by integrating deep features. Additionally, we introduce a new material dataset called EFMD by extending Flickr Material Database (FMD). By the employment of the EFMD with transfer learning for updating the learned CNN models, we achieve 84.0%+/-1.8% accuracy on the FMD dataset which is close to human performance that is 84.9%.
28 GHz Millimeter-Wave Ultrawideband Small-Scale Fading Models in Wireless Channels
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents small-scale fading measurements for 28 GHz outdoor millimeter-wave ultrawideband channels using directional horn antennas at the transmitter and receiver. Power delay profiles were measured at half-wavelength spatial increments over a local area (33 wavelengths) on a linear track in two orthogonal receiver directions in a typical base-to-mobile scenario with fixed transmitter and receiver antenna beam pointing directions. The voltage path amplitudes are shown to follow a Rician distribution, with K-factor ranging from 9 - 15 dB and 5 - 8 dB in line of sight (LOS) and non-line of sight (NLOS) for a vertical-to-vertical co-polarized antenna scenario, respectively, and from 3 - 7 dB in both LOS and NLOS vertical-to-horizontal cross-polarized antenna scenario. The average spatial autocorrelation functions of individual multipath components reveal that signal amplitudes reach a correlation of 0 after 2 and 5 wavelengths in LOS and NLOS co-polarized V-V antenna scenarios. The models provided are useful for recreating path gain statistics of millimeter-wave wideband channel impulse responses over local areas, for the study of multi-element antenna simulations and channel estimation algorithms.
Indoor Office Plan Environment and Layout-Based MmWave Path Loss Models for 28 GHz and 73 GHz
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents large-scale path loss models based on extensive ultra-wideband millimeter-wave propagation measurements performed at 28 GHz and 73 GHz in three typical indoor office layouts -- namely: corridor, open-plan, and closed-plan. A previous study combined all indoor layouts together, while this study separates them for site-specific indoor large-scale path loss model analysis. Measurements were conducted using a 400 megachips-per-second broadband sliding correlator channel sounder with 800 MHz first null-to-null RF bandwidth for 48 transmitter-receiver location combinations with distances ranging 3.9 m to 45.9 m for both co- and cross-polarized antenna configurations in line-of-sight and non-line-of-sight environments. Omnidirectional path loss values were synthesized from over 14,000 directional power delay profiles and were used to generate single-frequency and multi-frequency path loss models for combined, co-, and cross-polarized antennas. Large-scale path loss models that include a cross-polarization discrimination factor are provided for cross-polarized antenna measurements. The results show the value of using the close-in free space reference distance single and multi-frequency path loss models, as they offer simplicity (less parameters) in path loss calculation and prediction, without sacrificing accuracy. Moreover, the current 3GPP floating-intercept path loss model only requires a simple and subtle modification to convert to the close-in free space reference distance models.
A PAC Approach to Application-Specific Algorithm Selection
Venue: arXiv cs.LG 2016
Year: 2016

The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. While there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem. This paper adapts concepts from statistical and online learning theory to reason about application-specific algorithm selection. Our models capture several state-of-the-art empirical and theoretical approaches to the problem, ranging from self-improving algorithms to empirical performance models, and our results identify conditions under which these approaches are guaranteed to perform well. We present one framework that models algorithm selection as a statistical learning problem, and our work here shows that dimension notions from statistical learning theory, historically used to measure the complexity of classes of binary- and real-valued functions, are relevant in a much broader algorithmic context. We also study the online version of the algorithm selection problem, and give possibility and impossibility results for the existence of no-regret learning algorithms.
On The Secrecy of the Cognitive Interference Channel with Partial Channel States
Venue: arXiv cs.IT 2016
Year: 2016

The secrecy problem in the state-dependent cognitive interference channel is considered in this paper. In our model, there are a primary and a secondary (cognitive) transmitter-receiver pairs, in which the cognitive transmitter has the message of the primary one as side information. In addition, the channel is affected by a channel state sequence which is estimated partially at the cognitive transmitter and the corresponding receiver. The cognitive transmitter wishes to cooperate with the primary one, and it sends its individual message which should be confidential at the primary receiver. The achievable equivocation-rate regions for this channel are derived using two approaches: the binning scheme coding, and superposition coding. Then the outer bounds on the capacity are proposed and the results are extended to the Gaussian examples.
Multi-Agent Continuous Transportation with Online Balanced Partitioning
Venue: arXiv cs.MA 2016
Year: 2016

We introduce the concept of continuous transportation task to the context of multi-agent systems. A continuous transportation task is one in which a multi-agent team visits a number of fixed locations, picks up objects, and delivers them to a final destination. The goal is to maximize the rate of transportation while the objects are replenished over time. Examples of problems that need continuous transportation are foraging, area sweeping, and first/last mile problem. Previous approaches typically neglect the interference and are highly dependent on communications among agents. Some also incorporate an additional reconnaissance agent to gather information. In this paper, we present a hybrid of centralized and distributed approaches that minimize the interference and communications in the multi-agent team without the need for a reconnaissance agent. We contribute two partitioning-transportation algorithms inspired by existing algorithms, and contribute one novel online partitioning-transportation algorithm with information gathering in the multi-agent team. Our algorithms have been implemented and tested extensively in the simulation. The results presented in this paper demonstrate the effectiveness of our algorithms that outperform the existing algorithms, even without any communications between the agents and without the presence of a reconnaissance agent.
On Partitioning the Edges of 1-Plane Graphs
Venue: arXiv cs.CG 2016
Year: 2016

A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red-blue edge coloring of an optimal 1-plane graph $G$ partitions the edge set of $G$ into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: $(i)$ Every optimal 1-plane graph has a red-blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. $(ii)$ A red-blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed.
On the Optimal Feedback Rate in Interference-Limited Multi-Antenna Cellular Systems
Venue: arXiv cs.IT 2016
Year: 2016

We consider a downlink cellular network where multi-antenna base stations (BSs) transmit data to single-antenna users by using one of two linear precoding methods with limited feedback: (i) maximum ratio transmission (MRT) for serving a single user or (ii) zero forcing (ZF) for serving multiple users. The BS and user locations are drawn from a Poisson point process, allowing expressions for the signal- to-interference coverage probability and the ergodic spectral efficiency to be derived as a function of system parameters such as the number of BS antennas and feedback bits, and the pathloss exponent. We find a tight lower bound on the optimum number of feedback bits to maximize the net spectral efficiency, which captures the overall system gain by considering both of downlink and uplink spectral efficiency using limited feedback. Our main finding is that, when using MRT, the optimum number of feedback bits scales linearly with the number of antennas, and logarithmically with the channel coherence time. When using ZF, the feedback scales in the same ways as MRT, but also linearly with the pathloss exponent. The derived results provide system-level insights into the preferred channel codebook size by averaging the effects of short-term fading and long-term pathloss.
Cost Minimizing Online Algorithms for Energy Storage Management with Worst-case Guarantee
Venue: arXiv cs.DS 2016
Year: 2016

The fluctuations of electricity prices in demand response schemes and intermittency of renewable energy supplies necessitate the adoption of energy storage in microgrids. However, it is challenging to design effective real-time energy storage management strategies that can deliver assured optimality, without being hampered by the uncertainty of volatile electricity prices and renewable energy supplies. This paper presents a simple effective online algorithm for the charging and discharging decisions of energy storage that minimizes the electricity cost in the presence of electricity price fluctuations and renewable energy supplies, without relying on the future information of prices, demands or renewable energy supplies. The proposed algorithm is supported by a near-best worst-case guarantee (i.e., competitive ratio), as compared to the offline optimal decisions based on full future information. Furthermore, the algorithm can be adapted to take advantage of limited future information, if available. By simulations on real-world data, it is observed that the proposed algorithms can achieve satisfactory outcome in practice.
Breaking Symmetries in Graph Search with Canonizing Sets
Venue: arXiv cs.AI 2016
Year: 2016

There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of the large number of isomorphic representations of their solutions. This paper introduces effective and compact, complete symmetry breaking constraints for small graph search. Enumerating with these symmetry breaks generates all and only non-isomorphic solutions. For small search problems, with up to $10$ vertices, we compute instance independent symmetry breaking constraints. For small search problems with a larger number of vertices we demonstrate the computation of instance dependent constraints which are complete. We illustrate the application of complete symmetry breaking constraints to extend two known sequences from the OEIS related to graph enumeration. We also demonstrate the application of a generalization of our approach to fully-interchangeable matrix search problems.
On bounding the difference between the maximum degree and the chromatic number by a constant
Venue: arXiv cs.DM 2016
Year: 2016

We provide a finite forbidden induced subgraph characterization for the graph class $\varUpsilon_k$, for all $k \in \mathbb{N}_0$, which is defined as follows. A graph is in $\varUpsilon_k$ if for any induced subgraph, $Δ\leq χ-1 + k$ holds, where $Δ$ is the maximum degree and $χ$ is the chromatic number of the subgraph. We compare these results with those given in [O. Schaudt, V. Weil, On bounding the difference between the maximum degree and the clique number, Graphs and Combinatorics 31(5), 1689-1702 (2015). DOI: 10.1007/s00373-014-1468-3], where we studied the graph class $\varOmega_k$, for $k \in \mathbb{N}_0$, whose graphs are such that for any induced subgraph, $Δ\leq ω-1 + k$ holds, where $ω$ denotes the clique number of a graph. In particular, we give a characterization in terms of $\varOmega_k$ and $\varUpsilon_k$ of those graphs where the neighborhood of every vertex is perfect.
SWIM: Synthesizing What I Mean
Venue: arXiv cs.SE 2016
Year: 2016

Modern programming frameworks come with large libraries, with diverse applications such as for matching regular expressions, parsing XML files and sending email. Programmers often use search engines such as Google and Bing to learn about existing APIs. In this paper, we describe SWIM, a tool which suggests code snippets given API-related natural language queries such as "generate md5 hash code". We translate user queries into the APIs of interest using clickthrough data from the Bing search engine. Then, based on patterns learned from open-source code repositories, we synthesize idiomatic code describing the use of these APIs. We introduce \emph{structured call sequences} to capture API-usage patterns. Structured call sequences are a generalized form of method call sequences, with if-branches and while-loops to represent conditional and repeated API usage patterns, and are simple to extract and amenable to synthesis. We evaluated SWIM with 30 common C# API-related queries received by Bing. For 70% of the queries, the first suggested snippet was a relevant solution, and a relevant solution was present in the top 10 results for all benchmarked queries. The online portion of the workflow is also very responsive, at an average of 1.5 seconds per snippet.
Application of Non-orthogonal Multiple Access in LTE and 5G Networks
Venue: arXiv cs.IT 2016
Year: 2016

As the latest member of the multiple access family, non-orthogonal multiple access (NOMA) has been recently proposed for 3GPP Long Term Evolution (LTE) and envisioned to be an essential component of 5th generation (5G) mobile networks. The key feature of NOMA is to serve multiple users at the same time/frequency/code, but with different power levels, which yields a significant spectral efficiency gain over conventional orthogonal MA. This article provides a systematic treatment of this newly emerging technology, from its combination with multiple-input multiple-output (MIMO) technologies, to cooperative NOMA, as well as the interplay between NOMA and cognitive radio. This article also reviews the state of the art in the standardization activities concerning the implementation of NOMA in LTE and 5G networks.
k-Means for Streaming and Distributed Big Sparse Data
Venue: arXiv cs.DS 2016
Year: 2016

We provide the first streaming algorithm for computing a provable approximation to the $k$-means of sparse Big data. Here, sparse Big Data is a set of $n$ vectors in $\mathbb{R}^d$, where each vector has $O(1)$ non-zeroes entries, and $d\geq n$. E.g., adjacency matrix of a graph, web-links, social network, document-terms, or image-features matrices. Our streaming algorithm stores at most $\log n\cdot k^{O(1)}$ input points in memory. If the stream is distributed among $M$ machines, the running time reduces by a factor of $M$, while communicating a total of $M\cdot k^{O(1)}$ (sparse) input points between the machines. % Our main technical result is a deterministic algorithm for computing a sparse $(k,ε)$-coreset, which is a weighted subset of $k^{O(1)}$ input points that approximates the sum of squared distances from the $n$ input points to every $k$ centers, up to $(1\pmε)$ factor, for any given constant $ε>0$. This is the first such coreset of size independent of both $d$ and $n$. Existing algorithms use coresets of size at least polynomial in $d$, or project the input points on a subspace which diminishes their sparsity, thus require memory and communication $Ω(d)=Ω(n)$ even for $k=2$. Experimental results real public datasets shows that our algorithm boost the performance of such given heuristics even in the off-line setting. Open code is provided for reproducibility.
MOCICE-BCubed F$_1$: A New Evaluation Measure for Biclustering Algorithms
Venue: arXiv cs.LG 2016
Year: 2016

The validation of biclustering algorithms remains a challenging task, even though a number of measures have been proposed for evaluating the quality of these algorithms. Although no criterion is universally accepted as the overall best, a number of meta-evaluation conditions to be satisfied by biclustering algorithms have been enunciated. In this work, we present MOCICE-BCubed F$_1$, a new external measure for evaluating biclusterings, in the scenario where gold standard annotations are available for both the object clusters and the associated feature subspaces. Our proposal relies on the so-called micro-objects transformation and satisfies the most comprehensive set of meta-evaluation conditions so far enunciated for biclusterings. Additionally, the proposed measure adequately handles the occurrence of overlapping in both the object and feature spaces. Moreover, when used for evaluating traditional clusterings, which are viewed as a particular case of biclustering, the proposed measure also satisfies the most comprehensive set of meta-evaluation conditions so far enunciated for this task.
Authentication Based Solutions to Counterfeiting of Manufactured Goods
Venue: arXiv cs.CR 2016
Year: 2016

Counterfeiting of manufactured goods is presented as the theft of intellectual property, patents, copyright etc. accompanied by identity theft. The purpose of the identity theft is to facilitate the intellectual property theft. Without it the intellectual property theft would be obvious and the products would be confiscated and destroyed. Authentication solutions, to prevent identity theft, were then developed for the two categories of manufactured goods i.e. goods which can be subjected to destructive screening strategies and goods which cannot e.g. pharmaceutical drugs and currencies, respectively. The solutions developed were found to be analogous to digital signatures. Tamper proof packaging on pharmaceutical drugs is analogous to encryption because it prevents Mallory from interfering with the product. Breaking the tamper proof packaging is a one-way function. Concealed inside the packaging a one-time password, which can be used to authenticate the product over the internet. The name of the authentication website must be common knowledge, just like a public key for authenticating digital signatures. Otherwise the counterfeiters will specify their own authentication website. This solution can be altered for currencies i.e. the one-way function, equivalent to opening the tamper proof packaging, becomes the method of manufacture of the currency.