OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Neural Turing Machine with Soft and Hard Addressing Schemes
Venue: arXiv cs.LG 2017
Year: 2017

We extend neural Turing machine (NTM) model into a dynamic neural Turing machine (D-NTM) by introducing a trainable memory addressing scheme. This addressing scheme maintains for each memory cell two separate vectors, content and address vectors. This allows the D-NTM to learn a wide variety of location-based addressing strategies including both linear and nonlinear ones. We implement the D-NTM with both continuous, differentiable and discrete, non-differentiable read/write mechanisms. We investigate the mechanisms and effects of learning to read and write into a memory through experiments on Facebook bAbI tasks using both a feedforward and GRUcontroller. The D-NTM is evaluated on a set of Facebook bAbI tasks and shown to outperform NTM and LSTM baselines. We have done extensive analysis of our model and different variations of NTM on bAbI task. We also provide further experimental results on sequential pMNIST, Stanford Natural Language Inference, associative recall and copy tasks.
A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model
Venue: arXiv cs.CC 2017
Year: 2017

We present the first linear lower bound for the number of bits required to be accessed in the worst case to increment an integer in an arbitrary space- optimal binary representation. The best previously known lower bound was logarithmic. It is known that a logarithmic number of read bits in the worst case is enough to increment some of the integer representations that use one bit of redundancy, therefore we show an exponential gap between space-optimal and redundant counters. Our proof is based on considering the increment procedure for a space optimal counter as a permutation and calculating its parity. For every space optimal counter, the permutation must be odd, and implementing an odd permutation requires reading at least half the bits in the worst case. The combination of these two observations explains why the worst-case space-optimal problem is substantially different from both average-case approach with constant expected number of reads and almost space optimal representations with logarithmic number of reads in the worst case.
GfcLLL: A Greedy Selection Based Approach for Fixed-Complexity LLL Reduction
Venue: arXiv cs.IT 2017
Year: 2017

The LLL lattice reduction has been widely used to decrease the bit error rate (BER) of the Babai point, but its running time varies much from matrix to matrix. To address this problem, some fixed-complexity LLL reductions (FCLLL) have been proposed. In this paper, we propose two greedy selection based FCLLL algorithms: GfcLLL(1) and GfcLLL(2). Simulations show that both of them give Babai points with lower BER in similar or much shorter CPU time than existing ones.
On a method for Rock Classification using Textural Features and Genetic Optimization
Venue: arXiv cs.CV 2017
Year: 2017

In this work we present a method to classify a set of rock textures based on a Spectral Analysis and the extraction of the texture Features of the resulted images. Up to 520 features were tested using 4 different filters and all 31 different combinations were verified. The classification process relies on a Naive Bayes classifier. We performed two kinds of optimizations: statistical optimization with covariance-based Principal Component Analysis (PCA) and a genetic optimization, for 10,000 randomly defined samples, achieving a final maximum classification success of 91% against the original 70% success ratio (without any optimization nor filters used). After the optimization 9 types of features emerged as most relevant.
Coordinate-Descent Diffusion Learning by Networked Agents
Venue: arXiv cs.MA 2017
Year: 2017

This work examines the mean-square error performance of diffusion stochastic algorithms under a generalized coordinate-descent scheme. In this setting, the adaptation step by each agent is limited to a random subset of the coordinates of its stochastic gradient vector. The selection of coordinates varies randomly from iteration to iteration and from agent to agent across the network. Such schemes are useful in reducing computational complexity at each iteration in power-intensive large data applications. They are also useful in modeling situations where some partial gradient information may be missing at random. Interestingly, the results show that the steady-state performance of the learning strategy is not always degraded, while the convergence rate suffers some degradation. The results provide yet another indication of the resilience and robustness of adaptive distributed strategies.
Sequence Training and Adaptation of Highway Deep Neural Networks
Venue: arXiv cs.CL 2017
Year: 2017

Highway deep neural network (HDNN) is a type of depth-gated feedforward neural network, which has shown to be easier to train with more hidden layers and also generalise better compared to conventional plain deep neural networks (DNNs). Previously, we investigated a structured HDNN architecture for speech recognition, in which the two gate functions were tied across all the hidden layers, and we were able to train a much smaller model without sacrificing the recognition accuracy. In this paper, we carry on the study of this architecture with sequence-discriminative training criterion and speaker adaptation techniques on the AMI meeting speech recognition corpus. We show that these two techniques improve speech recognition accuracy on top of the model trained with the cross entropy criterion. Furthermore, we demonstrate that the two gate functions that are tied across all the hidden layers are able to control the information flow over the whole network, and we can achieve considerable improvements by only updating these gate functions in both sequence training and adaptation experiments.
Predicting and Understanding Law-Making with Word Vectors and an Ensemble Model
Venue: arXiv cs.CL 2017
Year: 2017

Out of nearly 70,000 bills introduced in the U.S. Congress from 2001 to 2015, only 2,513 were enacted. We developed a machine learning approach to forecasting the probability that any bill will become law. Starting in 2001 with the 107th Congress, we trained models on data from previous Congresses, predicted all bills in the current Congress, and repeated until the 113th Congress served as the test. For prediction we scored each sentence of a bill with a language model that embeds legislative vocabulary into a high-dimensional, semantic-laden vector space. This language representation enables our investigation into which words increase the probability of enactment for any topic. To test the relative importance of text and context, we compared the text model to a context-only model that uses variables such as whether the bill's sponsor is in the majority party. To test the effect of changes to bills after their introduction on our ability to predict their final outcome, we compared using the bill text and meta-data available at the time of introduction with using the most recent data. At the time of introduction context-only predictions outperform text-only, and with the newest data text-only outperforms context-only. Combining text and context always performs best. We conducted a global sensitivity analysis on the combined model to determine important variables predicting enactment.
Accelerated Evaluation of Automated Vehicles in Car-Following Maneuvers
Venue: arXiv cs.OH 2017
Year: 2017

The safety of Automated Vehicles (AVs) must be assured before their release and deployment. The current approach to evaluation relies primarily on (i) testing AVs on public roads or (ii) track testing with scenarios defined in a test matrix. These two methods have completely opposing drawbacks: the former, while offering realistic scenarios, takes too much time to execute; the latter, though it can be completed in a short amount of time, has no clear correlation to safety benefits in the real world. To avoid the aforementioned problems, we propose Accelerated Evaluation, focusing on the car-following scenario. The stochastic human-controlled vehicle (HV) motions are modeled based on 1.3 million miles of naturalistic driving data collected by the University of Michigan Safety Pilot Model Deployment Program. The statistics of the HV behaviors are then modified to generate more intense interactions between HVs and AVs to accelerate the evaluation procedure. The Importance Sampling theory was used to ensure that the safety benefits of AVs are accurately assessed under accelerated tests. Crash, injury and conflict rates for a simulated AV are simulated to demonstrate the proposed approach. Results show that test duration is reduced by a factor of 300 to 100,000 compared with the non-accelerated (naturalistic) evaluation. In other words, the proposed techniques have great potential for accelerating the AV evaluation process.
At Every Corner: Determining Corner Points of Two-User Gaussian Interference Channels
Venue: arXiv cs.IT 2017
Year: 2017

The corner points of the capacity region of the two-user Gaussian interference channel under strong or weak interference are determined using the notions of almost Gaussian random vectors, almost lossless addition of random vectors, and almost linearly dependent random vectors. In particular, the "missing" corner point problem is solved in a manner that differs from previous works in that it avoids the use of integration over a continuum of SNR values or of Monge-Kantorovitch transportation problems.
A mathematical evaluation of vote transfer systems
Venue: arXiv cs.GT 2017
Year: 2017

The paper builds a general model of vote transfer systems on the basis of the current Hungarian electoral rules. It combines single-seat districts and list mandates with three possible compensation rule for 'wasted' votes in constituencies: no compensation (direct vote transfer, DVT), compensation for votes cast for losing party candidates (positive vote transfer, PVT) and compensation for all votes that are not necessary to win the district (negative vote transfer, NVT). The model is studied in the case of two parties. When the number of votes for the majority party follows a uniform distribution in each district, DVT results in the greatest expected seat share, however, application of PVT, and, especially, NVT increases the probability of winning the election. The trade-off between vote transfer formulas and the number of list mandates reveals that the majority party should use an appropriately calibrated NVT system if it focuses on these two variables.
LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain
Venue: arXiv cs.NA 2017
Year: 2017

We study $k$-SVD that is to obtain the first $k$ singular vectors of a matrix $A$. Recently, a few breakthroughs have been discovered on $k$-SVD: Musco and Musco [1] proved the first gap-free convergence result using the block Krylov method, Shamir [2] discovered the first variance-reduction stochastic method, and Bhojanapalli et al. [3] provided the fastest $O(\mathsf{nnz}(A) + \mathsf{poly}(1/\varepsilon))$-time algorithm using alternating minimization. In this paper, we put forward a new and simple LazySVD framework to improve the above breakthroughs. This framework leads to a faster gap-free method outperforming [1], and the first accelerated and stochastic method outperforming [2]. In the $O(\mathsf{nnz}(A) + \mathsf{poly}(1/\varepsilon))$ running-time regime, LazySVD outperforms [3] in certain parameter regimes without even using alternating minimization.
Do semantic parts emerge in Convolutional Neural Networks?
Venue: arXiv cs.CV 2017
Year: 2017

Semantic object parts can be useful for several visual recognition tasks. Lately, these tasks have been addressed using Convolutional Neural Networks (CNN), achieving outstanding results. In this work we study whether CNNs learn semantic parts in their internal representation. We investigate the responses of convolutional filters and try to associate their stimuli with semantic parts. We perform two extensive quantitative analyses. First, we use ground-truth part bounding-boxes from the PASCAL-Part dataset to determine how many of those semantic parts emerge in the CNN. We explore this emergence for different layers, network depths, and supervision levels. Second, we collect human judgements in order to study what fraction of all filters systematically fire on any semantic part, even if not annotated in PASCAL-Part. Moreover, we explore several connections between discriminative power and semantics. We find out which are the most discriminative filters for object recognition, and analyze whether they respond to semantic parts or to other image patches. We also investigate the other direction: we determine which semantic parts are the most discriminative and whether they correspond to those parts emerging in the network. This enables to gain an even deeper understanding of the role of semantic parts in the network.
Making recommendations bandwidth aware
Venue: arXiv cs.IT 2017
Year: 2017

This paper asks how much we can gain in terms of bandwidth and user satisfaction, if recommender systems became bandwidth aware and took into account not only the user preferences, but also the fact that they may need to serve these users under bandwidth constraints, as is the case over wireless networks. We formulate this as a new problem in the context of index coding: we relax the index coding requirements to capture scenarios where each client has preferences associated with messages. The client is satisfied to receive any message she does not already have, with a satisfaction proportional to her preference for that message. We consistently find, over a number of scenarios we sample, that although the optimization problems are in general NP-hard, significant bandwidth savings are possible even when restricted to polynomial time algorithms.
Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
Venue: arXiv cs.DS 2017
Year: 2017

Understanding the local behaviour of structured multi-dimensional data is a fundamental problem in various areas of computer science. As the amount of data is often huge, it is desirable to obtain sublinear time algorithms, and specifically property testers, to understand local properties of the data. We focus on the natural local problem of testing pattern freeness: given a large $d$-dimensional array $A$ and a fixed $d$-dimensional pattern $P$ over a finite alphabet, we say that $A$ is $P$-free if it does not contain a copy of the forbidden pattern $P$ as a consecutive subarray. The distance of $A$ to $P$-freeness is the fraction of entries of $A$ that need to be modified to make it $P$-free. For any $ε\in [0,1]$ and any large enough pattern $P$ over any alphabet, other than a very small set of exceptional patterns, we design a tolerant tester that distinguishes between the case that the distance is at least $ε$ and the case that it is at most $a_d ε$, with query complexity and running time $c_d ε^{-1}$, where $a_d < 1$ and $c_d$ depend only on $d$. To analyze the testers we establish several combinatorial results, including the following $d$-dimensional modification lemma, which might be of independent interest: for any large enough pattern $P$ over any alphabet (excluding a small set of exceptional patterns for the binary case), and any array $A$ containing a copy of $P$, one can delete this copy by modifying one of its locations without creating new $P$-copies in $A$. Our results address an open question of Fischer and Newman, who asked whether there exist efficient testers for properties related to tight substructures in multi-dimensional structured data. They serve as a first step towards a general understanding of local properties of multi-dimensional arrays, as any such property can be characterized by a fixed family of forbidden patterns.
A BCMP Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we present a queueing network approach to the problem of routing and rebalancing a fleet of self-driving vehicles providing on-demand mobility within a capacitated road network. We refer to such systems as autonomous mobility-on-demand systems, or AMoD. We first cast an AMoD system into a closed, multi-class BCMP queueing network model. Second, we present analysis tools that allow the characterization of performance metrics for a given routing policy, in terms, e.g., of vehicle availabilities, and first and second order moments of vehicle throughput. Third, we propose a scalable method for the synthesis of routing policies, with performance guarantees in the limit of large fleet sizes. Finally, we validate our theoretical results on a case study of New York City. Collectively, this paper provides a unifying framework for the analysis and control of AMoD systems, which subsumes earlier Jackson and network flow models, provides a quite large set of modeling options (e.g., the inclusion of road capacities and general travel time distributions), and allows the analysis of second and higher-order moments for the performance metrics.
A Real-Time Deep Learning Pedestrian Detector for Robot Navigation
Venue: arXiv cs.RO 2017
Year: 2017

A real-time Deep Learning based method for Pedestrian Detection (PD) is applied to the Human-Aware robot navigation problem. The pedestrian detector combines the Aggregate Channel Features (ACF) detector with a deep Convolutional Neural Network (CNN) in order to obtain fast and accurate performance. Our solution is firstly evaluated using a set of real images taken from onboard and offboard cameras and, then, it is validated in a typical robot navigation environment with pedestrians (two distinct experiments are conducted). The results on both tests show that our pedestrian detector is robust and fast enough to be used on robot navigation applications.
DiaSys: Improving SoC Insight Through On-Chip Diagnosis
Venue: arXiv cs.DC 2017
Year: 2017

To find the cause of a functional or non-functional defect (bug) in software running on a multi-processor System-on-Chip (MPSoC), developers need insight into the chip. Tracing systems provide this insight non-intrusively, at the cost of high off-chip bandwidth requirements. This I/O bottleneck limits the observability, a problem becoming more severe as more functionality is integrated on-chip. In this paper, we present DiaSys, an MPSoC diagnosis system with the potential to replace today's tracing systems. Its main idea is to partially execute the analysis of observation data on the chip; in consequence, more information and less data is sent to the attached host PC. With DiaSys, the data analysis is performed by the diagnosis application. Its input are events, which are generated by observation hardware at interesting points in the program execution (like a function call). Its outputs are events with higher information density. The event transformation is modeled as dataflow application. For execution, it is mapped in part to dedicated and distributed on-chip components, and in part to the host PC; the off-chip boundary is transparent to the developer of the diagnosis application. We implement DiaSys as extension to an existing SoC with four tiles and a mesh network running on an FPGA platform. Two usage examples confirm that DiaSys is flexible enough to replace a tracing system, while significantly lowering the off-chip bandwidth requirements. In our examples, the debugging of a race-condition bug, and the creation of a lock contention profile, we see a reduction of trace bandwidth of more than three orders of magnitude, compared to a full trace created by a common tracing system.
On QoS-assured degraded provisioning in service-differentiated multi-layer elastic optical networks
Venue: arXiv cs.NI 2017
Year: 2017

The emergence of new network applications is driving network operators to not only fulfill dynamic bandwidth requirements, but offer various grades of service. Degraded provisioning provides an effective solution to flexibly allocate resources in various dimensions to reduce blocking for differentiated demands when network congestion occurs. In this work, we investigate the novel problem of online degraded provisioning in service-differentiated multi-layer networks with optical elasticity. Quality of Service (QoS) is assured by service-holding-time prolongation and immediate access as soon as the service arrives without set-up delay. We decompose the problem into degraded routing and degraded resource allocation stages, and design polynomial-time algorithms with the enhanced multi-layer architecture to increase the network flexibility in temporal and spectral dimensions. Illustrative results verify that we can achieve significant reduction of network service failures, especially for requests with higher priorities. The results also indicate that degradation in optical layer can increase the network capacity, while the degradation in electric layer provides flexible time-bandwidth exchange.
High-dimensional approximate $r$-nets
Venue: arXiv cs.CG 2017
Year: 2017

The construction of $r$-nets offers a powerful tool in computational and metric geometry. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate $r$-nets with respect to Euclidean distance. For any fixed $ε>0$, the approximation factor is $1+ε$ and the complexity is polynomial in the dimension and subquadratic in the number of points. The algorithm succeeds with high probability. More specifically, the best previously known LSH-based construction of Eppstein et al.\ \cite{EHS15} is improved in terms of complexity by reducing the dependence on $ε$, provided that $ε$ is sufficiently small. Our method does not require LSH but, instead, follows Valiant's \cite{Val15} approach in designing a sequence of reductions of our problem to other problems in different spaces, under Euclidean distance or inner product, for which $r$-nets are computed efficiently and the error can be controlled. Our result immediately implies efficient solutions to a number of geometric problems in high dimension, such as finding the $(1+ε)$-approximate $k$th nearest neighbor distance in time subquadratic in the size of the input.
The Minrank of Random Graphs
Venue: arXiv cs.CC 2017
Year: 2017

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching some ones to zeros (i.e., deleting edges) and then setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of (linear) index coding (Bar-Yossef et al., FOCS'06), network coding and distributed storage, and to Valiant's approach for proving superlinear circuit lower bounds (Valiant, Boolean Function Complexity '92). We prove tight bounds on the minrank of random Erdős-Rényi graphs $G(n,p)$ for all regimes of $p\in[0,1]$. In particular, for any constant $p$, we show that $\mathsf{minrk}(G) = Θ(n/\log n)$ with high probability, where $G$ is chosen from $G(n,p)$. This bound gives a near quadratic improvement over the previous best lower bound of $Ω(\sqrt{n})$ (Haviv and Langberg, ISIT'12), and partially settles an open problem raised by Lubetzky and Stav (FOCS '07). Our lower bound matches the well-known upper bound obtained by the "clique covering" solution, and settles the linear index coding problem for random graphs. Finally, our result suggests a new avenue of attack, via derandomization, on Valiant's approach for proving superlinear lower bounds for logarithmic-depth semilinear circuits.