OpenRaiser/Intern-Atlas huggingface dataset:
Sparse Vector Coding for Ultra-Reliable and Low Latency Communications
Venue: arXiv cs.IT 2018
Year: 2018

Ultra reliable and low latency communication (URLLC) is a newly introduced service category in 5G to support delay-sensitive applications. In order to support this new service category, 3rd Generation Partnership Project (3GPP) sets an aggressive requirement that a packet should be delivered with 10^-5 packet error rate within 1 ms transmission period. Since the current wireless transmission scheme designed to maximize the coding gain by transmitting capacity achieving long codeblock is not relevant for this purpose, a new transmission scheme to support URLLC is required. In this paper, we propose a new approach to support the short packet transmission, called sparse vector coding (SVC). Key idea behind the proposed SVC technique is to transmit the information after the sparse vector transformation. By mapping the information into the position of nonzero elements and then transmitting it after the random spreading, we obtain an underdetermined sparse system for which the principle of compressed sensing can be applied. From the numerical evaluations and performance analysis, we demonstrate that the proposed SVC technique is very effective in URLLC transmission and outperforms the 4G LTE and LTE-Advanced scheme.
Performance Limits of Compressive Sensing Channel Estimation in Dense Cloud RAN
Venue: arXiv cs.IT 2018
Year: 2018

Towards reducing the training signaling overhead in large scale and dense cloud radio access networks (CRAN), various approaches have been proposed based on the channel sparsification assumption, namely, only a small subset of the deployed remote radio heads (RRHs) are of significance to any user in the system. Motivated by the potential of compressive sensing (CS) techniques in this setting, this paper provides a rigorous description of the performance limits of many practical CS algorithms by considering the performance of the, so called, oracle estimator, which knows a priori which RRHs are of significance but not their corresponding channel values. By using tools from stochastic geometry, a closed form analytical expression of the oracle estimator performance is obtained, averaged over distribution of RRH positions and channel statistics. Apart from a bound on practical CS algorithms, the analysis provides important design insights, e.g., on how the training sequence length affects performance, and identifies the operational conditions where the channel sparsification assumption is valid. It is shown that the latter is true only in operational conditions with sufficiently large path loss exponents.
DART: Distribution Aware Retinal Transform for Event-based Cameras
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a generic visual descriptor, termed as distribution aware retinal transform (DART), that encodes the structural context using log-polar grids for event cameras. The DART descriptor is applied to four different problems, namely object classification, tracking, detection and feature matching: (1) The DART features are directly employed as local descriptors in a bag-of-features classification framework and testing is carried out on four standard event-based object datasets (N-MNIST, MNIST-DVS, CIFAR10-DVS, NCaltech-101). (2) Extending the classification system, tracking is demonstrated using two key novelties: (i) For overcoming the low-sample problem for the one-shot learning of a binary classifier, statistical bootstrapping is leveraged with online learning; (ii) To achieve tracker robustness, the scale and rotation equivariance property of the DART descriptors is exploited for the one-shot learning. (3) To solve the long-term object tracking problem, an object detector is designed using the principle of cluster majority voting. The detection scheme is then combined with the tracker to result in a high intersection-over-union score with augmented ground truth annotations on the publicly available event camera dataset. (4) Finally, the event context encoded by DART greatly simplifies the feature correspondence problem, especially for spatio-temporal slices far apart in time, which has not been explicitly tackled in the event-based vision domain.
Conceptual Text Summarizer: A new model in continuous vector space
Venue: arXiv cs.CL 2018
Year: 2018

Traditional methods of summarization are not cost-effective and possible today. Extractive summarization is a process that helps to extract the most important sentences from a text automatically and generates a short informative summary. In this work, we propose an unsupervised method to summarize Persian texts. This method is a novel hybrid approach that clusters the concepts of the text using deep learning and traditional statistical methods. First we produce a word embedding based on Hamshahri2 corpus and a dictionary of word frequencies. Then the proposed algorithm extracts the keywords of the document, clusters its concepts, and finally ranks the sentences to produce the summary. We evaluated the proposed method on Pasokh single-document corpus using the ROUGE evaluation measure. Without using any hand-crafted features, our proposed method achieves state-of-the-art results. We compared our unsupervised method with the best supervised Persian methods and we achieved an overall improvement of ROUGE-2 recall score of 7.5%.
How Algorithmic Confounding in Recommendation Systems Increases Homogeneity and Decreases Utility
Venue: arXiv cs.CY 2018
Year: 2018

Recommendation systems are ubiquitous and impact many domains; they have the potential to influence product consumption, individuals' perceptions of the world, and life-altering decisions. These systems are often evaluated or trained with data from users already exposed to algorithmic recommendations; this creates a pernicious feedback loop. Using simulations, we demonstrate how using data confounded in this way homogenizes user behavior without increasing utility.
Learning Robust Rewards with Adversarial Inverse Reinforcement Learning
Venue: arXiv cs.LG 2018
Year: 2018

Reinforcement learning provides a powerful and general framework for decision making and control, but its application in practice is often hindered by the need for extensive feature and reward engineering. Deep reinforcement learning methods can remove the need for explicit engineering of policy or value features, but still require a manually specified reward function. Inverse reinforcement learning holds the promise of automatic reward acquisition, but has proven exceptionally difficult to apply to large, high-dimensional problems with unknown dynamics. In this work, we propose adverserial inverse reinforcement learning (AIRL), a practical and scalable inverse reinforcement learning algorithm based on an adversarial reward learning formulation. We demonstrate that AIRL is able to recover reward functions that are robust to changes in dynamics, enabling us to learn policies even under significant variation in the environment seen during training. Our experiments show that AIRL greatly outperforms prior methods in these transfer settings.
An Innovations Approach to Viterbi Decoding of Convolutional Codes
Venue: arXiv cs.IT 2018
Year: 2018

We introduce the notion of innovations for Viterbi decoding of convolutional codes. First we define a kind of innovation corresponding to the received data, i.e., the input to a Viterbi decoder. Then the structure of a Scarce-State-Transition (SST) Viterbi decoder is derived in a natural manner. It is shown that the newly defined innovation is just the input to the main decoder in an SST Viterbi decoder and generates the same syndrome as the original received data does. A similar result holds for Quick-Look-In (QLI) codes as well. In this case, however, the precise innovation is not defined. We see that this innovation-like quantity is related to the linear smoothed estimate of the information. The essence of innovations approach to a linear filtering problem is first to whiten the observed data, and then to treat the resulting simpler white-noise observations problem. In our case, this corresponds to the reduction of decoding complexity in the main decoder in an SST Viterbi decoder. We show the distributions related to the main decoder (i.e., the input distribution and the state distribution in the code trellis for the main decoder) are much biased under moderately noisy conditions. We see that these biased distributions actually lead to the complexity reduction in the main decoder. Furthermore, it is shown that the proposed innovations approach can be extended to maximum-likelihood (ML) decoding of block codes as well.
Polyphonic Music Generation with Sequence Generative Adversarial Networks
Venue: arXiv cs.SD 2018
Year: 2018

We propose an application of sequence generative adversarial networks (SeqGAN), which are generative adversarial networks for discrete sequence generation, for creating polyphonic musical sequences. Instead of a monophonic melody generation suggested in the original work, we present an efficient representation of a polyphony MIDI file that simultaneously captures chords and melodies with dynamic timings. The proposed method condenses duration, octaves, and keys of both melodies and chords into a single word vector representation, and recurrent neural networks learn to predict distributions of sequences from the embedded musical word space. We experiment with the original method and the least squares method to the discriminator, which is known to stabilize the training of GANs. The network can create sequences that are musically coherent and shows an improved quantitative and qualitative measures. We also report that careful optimization of reinforcement learning signals of the model is crucial for general application of the model.
A Neural-Symbolic Approach to Design of CAPTCHA
Venue: arXiv cs.CL 2018
Year: 2018

CAPTCHAs based on reading text are susceptible to machine-learning-based attacks due to recent significant advances in deep learning (DL). To address this, this paper promotes image/visual captioning based CAPTCHAs, which is robust against machine-learning-based attacks. To develop image/visual-captioning-based CAPTCHAs, this paper proposes a new image captioning architecture by exploiting tensor product representations (TPR), a structured neural-symbolic framework developed in cognitive science over the past 20 years, with the aim of integrating DL with explicit language structures and rules. We call it the Tensor Product Generation Network (TPGN). The key ideas of TPGN are: 1) unsupervised learning of role-unbinding vectors of words via a TPR-based deep neural network, and 2) integration of TPR with typical DL architectures including Long Short-Term Memory (LSTM) models. The novelty of our approach lies in its ability to generate a sentence and extract partial grammatical structure of the sentence by using role-unbinding vectors, which are obtained in an unsupervised manner. Experimental results demonstrate the effectiveness of the proposed approach.
A Convergent Algorithm for Bi-orthogonal Nonnegative Matrix Tri-Factorization
Venue: arXiv cs.LG 2018
Year: 2018

A convergent algorithm for nonnegative matrix factorization with orthogonality constraints imposed on both factors is proposed in this paper. This factorization concept was first introduced by Ding et al. with intent to further improve clustering capability of NMF. However, as the original algorithm was developed based on multiplicative update rules, the convergence of the algorithm cannot be guaranteed. In this paper, we utilize the technique presented in our previous work to develop the algorithm and prove that it converges to a stationary point inside the solution space.
Linear/Quadratic Programming-Based Optimal Power Flow using Linear Power Flow and Absolute Loss Approximations
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents novel methods to approximate the nonlinear AC optimal power flow (OPF) into tractable linear/quadratic programming (LP/QP) based OPF problems that can be used for power system planning and operation. We derive a linear power flow approximation and consider a convex reformulation of the power losses in the form of absolute value functions. We show four ways how to incorporate this approximation into LP/QP based OPF problems. In a comprehensive case study the usefulness of our OPF methods is analyzed and compared with an existing OPF relaxation and approximation method. As a result, the errors on voltage magnitudes and angles are reasonable, while obtaining near-optimal results for typical scenarios. We find that our methods reduce significantly the computational complexity compared to the nonlinear AC-OPF making them a good choice for planning purposes.
Semantic Structure and Interpretability of Word Embeddings
Venue: arXiv cs.CL 2018
Year: 2018

Dense word embeddings, which encode semantic meanings of words to low dimensional vector spaces have become very popular in natural language processing (NLP) research due to their state-of-the-art performances in many NLP tasks. Word embeddings are substantially successful in capturing semantic relations among words, so a meaningful semantic structure must be present in the respective vector spaces. However, in many cases, this semantic structure is broadly and heterogeneously distributed across the embedding dimensions, which makes interpretation a big challenge. In this study, we propose a statistical method to uncover the latent semantic structure in the dense word embeddings. To perform our analysis we introduce a new dataset (SEMCAT) that contains more than 6500 words semantically grouped under 110 categories. We further propose a method to quantify the interpretability of the word embeddings; the proposed method is a practical alternative to the classical word intrusion test that requires human intervention.
Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR
Venue: arXiv cs.AI 2018
Year: 2018

There has been much discussion of the right to explanation in the EU General Data Protection Regulation, and its existence, merits, and disadvantages. Implementing a right to explanation that opens the black box of algorithmic decision-making faces major legal and technical barriers. Explaining the functionality of complex algorithmic decision-making systems and their rationale in specific cases is a technically challenging problem. Some explanations may offer little meaningful information to data subjects, raising questions around their value. Explanations of automated decisions need not hinge on the general public understanding how algorithmic systems function. Even though such interpretability is of great importance and should be pursued, explanations can, in principle, be offered without opening the black box. Looking at explanations as a means to help a data subject act rather than merely understand, one could gauge the scope and content of explanations according to the specific goal or action they are intended to support. From the perspective of individuals affected by automated decision-making, we propose three aims for explanations: (1) to inform and help the individual understand why a particular decision was reached, (2) to provide grounds to contest the decision if the outcome is undesired, and (3) to understand what would need to change in order to receive a desired result in the future, based on the current decision-making model. We assess how each of these goals finds support in the GDPR. We suggest data controllers should offer a particular type of explanation, unconditional counterfactual explanations, to support these three aims. These counterfactual explanations describe the smallest change to the world that can be made to obtain a desirable outcome, or to arrive at the closest possible world, without needing to explain the internal logic of the system.
Sampling and multilevel coarsening algorithms for fast matrix approximations
Venue: arXiv cs.NA 2018
Year: 2018

This paper addresses matrix approximation problems for matrices that are large, sparse and/or that are representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. Theoretical results are established that characterize the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. We consider a number of standard applications of this technique as well as a few new ones. Among the standard applications we first consider the problem of computing the partial SVD for which a combination of sampling and coarsening yields significantly improved SVD results relative to sampling alone. We also consider the Column subset selection problem, a popular low rank approximation method used in data related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. Numerical experiments illustrate the performances of the methods in various applications.
Text Annotation Graphs: Annotating Complex Natural Language Phenomena
Venue: arXiv cs.CL 2018
Year: 2018

This paper introduces a new web-based software tool for annotating text, Text Annotation Graphs, or TAG. It provides functionality for representing complex relationships between words and word phrases that are not available in other software tools, including the ability to define and visualize relationships between the relationships themselves (semantic hypergraphs). Additionally, we include an approach to representing text annotations in which annotation subgraphs, or semantic summaries, are used to show relationships outside of the sequential context of the text itself. Users can use these subgraphs to quickly find similar structures within the current document or external annotated documents. Initially, TAG was developed to support information extraction tasks on a large database of biomedical articles. However, our software is flexible enough to support a wide range of annotation tasks for any domain. Examples are provided that showcase TAG's capabilities on morphological parsing and event extraction tasks. The TAG software is available at: https://github.com/ CreativeCodingLab/TextAnnotationGraphs.
Just ASK: Building an Architecture for Extensible Self-Service Spoken Language Understanding
Venue: arXiv cs.CL 2018
Year: 2018

This paper presents the design of the machine learning architecture that underlies the Alexa Skills Kit (ASK) a large scale Spoken Language Understanding (SLU) Software Development Kit (SDK) that enables developers to extend the capabilities of Amazon's virtual assistant, Alexa. At Amazon, the infrastructure powers over 25,000 skills deployed through the ASK, as well as AWS's Amazon Lex SLU Service. The ASK emphasizes flexibility, predictability and a rapid iteration cycle for third party developers. It imposes inductive biases that allow it to learn robust SLU models from extremely small and sparse datasets and, in doing so, removes significant barriers to entry for software developers and dialogue systems researchers.
Expressive power of recurrent neural networks
Venue: arXiv cs.LG 2018
Year: 2018

Deep neural networks are surprisingly efficient at solving practical tasks, but the theory behind this phenomenon is only starting to catch up with the practice. Numerous works show that depth is the key to this efficiency. A certain class of deep convolutional networks -- namely those that correspond to the Hierarchical Tucker (HT) tensor decomposition -- has been proven to have exponentially higher expressive power than shallow networks. I.e. a shallow network of exponential width is required to realize the same score function as computed by the deep architecture. In this paper, we prove the expressive power theorem (an exponential lower bound on the width of the equivalent shallow network) for a class of recurrent neural networks -- ones that correspond to the Tensor Train (TT) decomposition. This means that even processing an image patch by patch with an RNN can be exponentially more efficient than a (shallow) convolutional network with one hidden layer. Using theoretical results on the relation between the tensor decompositions we compare expressive powers of the HT- and TT-Networks. We also implement the recurrent TT-Networks and provide numerical evidence of their expressivity.
Neural Discrete Representation Learning
Venue: arXiv cs.LG 2018
Year: 2018

Learning useful representations without supervision remains a key challenge in machine learning. In this paper, we propose a simple yet powerful generative model that learns such discrete representations. Our model, the Vector Quantised-Variational AutoEncoder (VQ-VAE), differs from VAEs in two key ways: the encoder network outputs discrete, rather than continuous, codes; and the prior is learnt rather than static. In order to learn a discrete latent representation, we incorporate ideas from vector quantisation (VQ). Using the VQ method allows the model to circumvent issues of "posterior collapse" -- where the latents are ignored when they are paired with a powerful autoregressive decoder -- typically observed in the VAE framework. Pairing these representations with an autoregressive prior, the model can generate high quality images, videos, and speech as well as doing high quality speaker conversion and unsupervised learning of phonemes, providing further evidence of the utility of the learnt representations.
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
Venue: arXiv cs.CC 2018
Year: 2018

We show that the counting class LWPP [FFK94] remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., $\rm PP^{\mbox{Legitimate Deck}} = PP$) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning, and Torán [KST92] that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our main LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection- and acceptance- gap-value targets to simultaneously be polynomial-sized lists; yet on the other hand, we show that for the #P-based analog of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does. Despite that nonrobustness result for a #P-based class, we show that the #P-based "exact counting" class $\rm C_{=}P$ remains unchanged even if one allows a polynomial number of target values for the number of accepting paths of the machine.