OpenRaiser/Intern-Atlas huggingface dataset:
Limited Feedback Designs for Machine-type Communications Exploiting User Cooperation
Venue: arXiv cs.IT 2019
Year: 2019

Multiuser multiple-input multiple-output (MIMO) systems are a prime candidate for use in massive connection density in machine-type communication (MTC) networks. One of the key challenges of MTC networks is to obtain accurate channel state information (CSI) at the access point (AP) so that the spectral efficiency can be improved by enabling enhanced MIMO techniques. However, current communication mechanisms relying upon frequency division duplexing (FDD) might not fully support an enormous number of devices due to the rate-constrained limited feedback and the time-consuming scheduling architectures. In this paper, we propose a user cooperation-based limited feedback strategy to support high connection density in massive MTC networks. In the proposed algorithm, two close-in users share the quantized version of channel information in order to improve channel feedback accuracy. The cooperation process is performed without any transmitter interventions (i.e., in a grant-free manner) to satisfy the low-latency requirement that is vital for MTC services. Moreover, based on the sum-rate throughput analysis, we develop an adaptive cooperation algorithm with a view to activating/deactivating the user cooperation mode according to channel and network conditions.
The Synchronizing Probability Function for Primitive Sets of Matrices
Venue: arXiv cs.FL 2019
Year: 2019

Motivated by recent results relating synchronizing DFAs and primitive sets, we tackle the synchronization process and the related longstanding Černý conjecture by studying the primitivity phenomenon for sets of nonnegative matrices having neither zero-rows nor zero-columns. We formulate the primitivity process in the setting of a two-player probabilistic game and we make use of convex optimization techniques to describe its behavior. We develop a tool for approximating and upper bounding the exponent of any primitive set and supported by numerical results we state a conjecture that, if true, would imply a quadratic upper bound on the reset threshold of a new class of automata.
DNN or k-NN: That is the Generalize vs. Memorize Question
Venue: arXiv cs.LG 2019
Year: 2019

This paper studies the relationship between the classification performed by deep neural networks (DNNs) and the decision of various classical classifiers, namely k-nearest neighbours (k-NN), support vector machines (SVM) and logistic regression (LR), at various layers of the network. This comparison provides us with new insights as to the ability of neural networks to both memorize the training data and generalize to new data at the same time, where k-NN serves as the ideal estimator that perfectly memorizes the data. We show that memorization of non-generalizing networks happens only at the last layers. Moreover, the behavior of DNNs compared to the linear classifiers SVM and LR is quite the same on the training and test data regardless of whether the network generalizes. On the other hand, the similarity to k-NN holds only at the absence of overfitting. Our results suggests that k-NN behavior of the network on new data is a sign of generalization. Moreover, it shows that memorization and generalization, which are traditionally considered to be contradicting to each other, are compatible and complementary.
Towards a more flexible Language of Thought: Bayesian grammar updates after each concept exposure
Venue: arXiv cs.AI 2019
Year: 2019

Recent approaches to human concept learning have successfully combined the power of symbolic, infinitely productive rule systems and statistical learning to explain our ability to learn new concepts from just a few examples. The aim of most of these studies is to reveal the underlying language structuring these representations and providing a general substrate for thought. However, describing a model of thought that is fixed once trained is against the extensive literature that shows how experience shapes concept learning. Here, we ask about the plasticity of these symbolic descriptive languages. We perform a concept learning experiment that demonstrates that humans can change very rapidly the repertoire of symbols they use to identify concepts, by compiling expressions which are frequently used into new symbols of the language. The pattern of concept learning times is accurately described by a Bayesian agent that rationally updates the probability of compiling a new expression according to how useful it has been to compress concepts so far. By portraying the Language of Thought as a flexible system of rules, we also highlight the difficulties to pin it down empirically.
Event2Mind: Commonsense Inference on Events, Intents, and Reactions
Venue: arXiv cs.CL 2019
Year: 2019

We investigate a new commonsense inference task: given an event described in a short free-form text ("X drinks coffee in the morning"), a system reasons about the likely intents ("X wants to stay awake") and reactions ("X feels alert") of the event's participants. To support this study, we construct a new crowdsourced corpus of 25,000 event phrases covering a diverse range of everyday events and situations. We report baseline performance on this task, demonstrating that neural encoder-decoder models can successfully compose embedding representations of previously unseen events and reason about the likely intents and reactions of the event participants. In addition, we demonstrate how commonsense inference on people's intents and reactions can help unveil the implicit gender inequality prevalent in modern movie scripts.
Towards Enabling Novel Edge-Enabled Applications
Venue: arXiv cs.DC 2019
Year: 2019

Edge computing has emerged as a distributed computing paradigm to overcome practical scalability limits of cloud computing. The main principle of edge computing is to leverage on computational resources outside of the cloud for performing computations closer to data sources, avoiding unnecessary data transfers to the cloud and enabling faster responses for clients. While this paradigm has been successfully employed to improve response times in some contexts, mostly by having clients perform pre-processing and/or filtering of data, or by leveraging on distributed caching infrastructures, we argue that the combination of edge and cloud computing has the potential to enable novel applications. However, to do so, some significant research challenges have to be tackled by the computer science community. In this paper, we discuss different edge resources and their potential use, motivated by envisioned use cases. We then discuss concrete research challenges that are in the critical path towards realizing our edge vision. We conclude by proposing a research agenda to allow the full exploitation of the potential for the emerging hybrid cloud/edge paradigm.
Cooperative Multi-Bitrate Video Caching and Transcoding in Multicarrier NOMA-Assisted Heterogeneous Virtualized MEC Networks
Venue: arXiv cs.IT 2019
Year: 2019

Cooperative video caching and transcoding in mobile edge computing (MEC) networks is a new paradigm for future wireless networks, e.g., 5G and 5G beyond, to reduce scarce and expensive backhaul resource usage by prefetching video files within radio access networks (RANs). Integration of this technique with other advent technologies, such as wireless network virtualization and multicarrier non-orthogonal multiple access (MC-NOMA), provides more flexible video delivery opportunities, which leads to enhancements both for the network's revenue and for the end-users' service experience. In this regard, we propose a two-phase RAF for a parallel cooperative joint multi-bitrate video caching and transcoding in heterogeneous virtualized MEC networks. In the cache placement phase, we propose novel proactive delivery-aware cache placement strategies (DACPSs) by jointly allocating physical and radio resources based on network stochastic information to exploit flexible delivery opportunities. Then, for the delivery phase, we propose a delivery policy based on the user requests and network channel conditions. The optimization problems corresponding to both phases aim to maximize the total revenue of network slices, i.e., virtual networks. Both problems are non-convex and suffer from high-computational complexities. For each phase, we show how the problem can be solved efficiently. We also propose a low-complexity RAF in which the complexity of the delivery algorithm is significantly reduced. A Delivery-aware cache refreshment strategy (DACRS) in the delivery phase is also proposed to tackle the dynamically changes of network stochastic information. Extensive numerical assessments demonstrate a performance improvement of up to 30% for our proposed DACPSs and DACRS over traditional approaches.
General solutions for nonlinear differential equations: a rule-based self-learning approach using deep reinforcement learning
Venue: arXiv cs.LG 2019
Year: 2019

A universal rule-based self-learning approach using deep reinforcement learning (DRL) is proposed for the first time to solve nonlinear ordinary differential equations and partial differential equations. The solver consists of a deep neural network-structured actor that outputs candidate solutions, and a critic derived only from physical rules (governing equations and boundary and initial conditions). Solutions in discretized time are treated as multiple tasks sharing the same governing equation, and the current step parameters provide an ideal initialization for the next owing to the temporal continuity of the solutions, which shows a transfer learning characteristic and indicates that the DRL solver has captured the intrinsic nature of the equation. The approach is verified through solving the Schrödinger, Navier-Stokes, Burgers', Van der Pol, and Lorenz equations and an equation of motion. The results indicate that the approach gives solutions with high accuracy, and the solution process promises to get faster.
Positive and Unlabeled Learning through Negative Selection and Imbalance-aware Classification
Venue: arXiv cs.LG 2019
Year: 2019

Motivated by applications in protein function prediction, we consider a challenging supervised classification setting in which positive labels are scarce and there are no explicit negative labels. The learning algorithm must thus select which unlabeled examples to use as negative training points, possibly ending up with an unbalanced learning problem. We address these issues by proposing an algorithm that combines active learning (for selecting negative examples) with imbalance-aware learning (for mitigating the label imbalance). In our experiments we observe that these two techniques operate synergistically, outperforming state-of-the-art methods on standard protein function prediction benchmarks.
Joint Path Selection and Rate Allocation Framework for 5G Self-Backhauled mmWave Networks
Venue: arXiv cs.NI 2019
Year: 2019

Owing to severe path loss and unreliable transmission over a long distance at higher frequency bands, we investigate the problem of path selection and rate allocation for multi-hop self-backhaul millimeter wave (mmWave) networks. Enabling multi-hop mmWave transmissions raises a potential issue of increased latency, and thus, in this work we aim at addressing the fundamental questions: how to select the best multi-hop paths and how to allocate rates over these paths subject to latency constraints? In this regard, we propose a new system design, which exploits multiple antenna diversity, mmWave bandwidth, and traffic splitting techniques to improve the downlink transmission. The studied problem is cast as a network utility maximization, subject to an upper delay bound constraint, network stability, and network dynamics. By leveraging stochastic optimization, the problem is decoupled into: path selection and rate allocation sub-problems, whereby a framework which selects the best paths is proposed using reinforcement learning techniques. Moreover, the rate allocation is a nonconvex program, which is converted into a convex one by using the successive convex approximation method. Via mathematical analysis, we provide a comprehensive performance analysis and convergence proofs for the proposed solution. Numerical results show that our approach ensures reliable communication with a guaranteed probability of up to $99.9999\%$, and reduces latency by $50.64\%$ and $92.9\%$ as compared to baseline models. Furthermore, the results showcase the key trade-off between latency and network arrival rate.
Adaptive Recovery of Dictionary-sparse Signals using Binary Measurements
Venue: arXiv cs.IT 2019
Year: 2019

One-bit compressive sensing (CS) is an advanced version of sparse recovery in which the sparse signal of interest can be recovered from extremely quantized measurements. Namely, only the sign of each measurement is available to us. In many applications, the ground-truth signal is not sparse itself, but can be represented in a redundant dictionary. A strong line of research has addressed conventional CS in this signal model including its extension to one-bit measurements. However, one-bit CS suffers from the extremely large number of required measurements to achieve a predefined reconstruction error level. A common alternative to resolve this issue is to exploit adaptive schemes. Adaptive sampling acts on the acquired samples to trace the signal in an efficient way. In this work, we utilize an adaptive sampling strategy to recover dictionary-sparse signals from binary measurements. For this task, a multi-dimensional threshold is proposed to incorporate the previous signal estimates into the current sampling procedure. This strategy substantially reduces the required number of measurements for exact recovery. Our proof approach is based on the recent tools in high dimensional geometry in particular random hyperplane tessellation and Gaussian width. We show through rigorous and numerical analysis that the proposed algorithm considerably outperforms state of the art approaches. Further, our algorithm reaches an exponential error decay in terms of the number of quantized measurements.
The Adaptive Sampling Revisited
Venue: arXiv cs.DS 2019
Year: 2019

The problem of estimating the number $n$ of distinct keys of a large collection of $N$ data is well known in computer science. A classical algorithm is the adaptive sampling (AS). $n$ can be estimated by $R.2^D$, where $R$ is the final bucket (cache) size and $D$ is the final depth at the end of the process. Several new interesting questions can be asked about AS (some of them were suggested by P.Flajolet and popularized by J.Lumbroso). The distribution of $W=\log (R2^D/n)$ is known, we rederive this distribution in a simpler way. We provide new results on the moments of $D$ and $W$. We also analyze the final cache size $R$ distribution. We consider colored keys: assume that among the $n$ distinct keys, $n_C$ do have color $C$. We show how to estimate $p=\frac{n_C}{n}$. We also study colored keys with some multiplicity given by some distribution function. We want to estimate mean an variance of this distribution. Finally, we consider the case where neither colors nor multiplicities are known. There we want to estimate the related parameters. An appendix is devoted to the case where the hashing function provides bits with probability different from $1/2$.
Optimal Sketching Bounds for Exp-concave Stochastic Minimization
Venue: arXiv cs.LG 2019
Year: 2019

We derive optimal statistical and computational complexity bounds for exp-concave stochastic minimization in terms of the effective dimension. For common eigendecay patterns of the population covariance matrix, this quantity is significantly smaller than the ambient dimension. Our results reveal interesting connections to sketching results in numerical linear algebra. In particular, our statistical analysis highlights a novel and natural relationship between algorithmic stability of empirical risk minimization and ridge leverage scores, which play significant role in sketching-based methods. Our main computational result is a fast implementation of a sketch-to-precondition approach in the context of exp-concave empirical risk minimization.
Implicit Reparameterization Gradients
Venue: arXiv cs.LG 2019
Year: 2019

By providing a simple and efficient way of computing low-variance gradients of continuous random variables, the reparameterization trick has become the technique of choice for training a variety of latent variable models. However, it is not applicable to a number of important continuous distributions. We introduce an alternative approach to computing reparameterization gradients based on implicit differentiation and demonstrate its broader applicability by applying it to Gamma, Beta, Dirichlet, and von Mises distributions, which cannot be used with the classic reparameterization trick. Our experiments show that the proposed approach is faster and more accurate than the existing gradient estimators for these distributions.
Improved Person Detection on Omnidirectional Images with Non-maxima Suppression
Venue: arXiv cs.CV 2019
Year: 2019

We propose a person detector on omnidirectional images, an accurate method to generate minimal enclosing rectangles of persons. The basic idea is to adapt the qualitative detection performance of a convolutional neural network based method, namely YOLOv2 to fish-eye images. The design of our approach picks up the idea of a state-of-the-art object detector and highly overlapping areas of images with their regions of interests. This overlap reduces the number of false negatives. Based on the raw bounding boxes of the detector we fine-tuned overlapping bounding boxes by three approaches: non-maximum suppression, soft non-maximum suppression and soft non-maximum suppression with Gaussian smoothing. The evaluation was done on the PIROPO database and an own annotated Flat dataset, supplemented with bounding boxes on omnidirectional images. We achieve an average precision of 64.4 % with YOLOv2 for the class person on PIROPO and 77.6 % on Flat. For this purpose we fine-tuned the soft non-maximum suppression with Gaussian smoothing.
Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations
Venue: arXiv cs.MA 2019
Year: 2019

Consider a network of agents connected by communication links, where each agent holds a real value. The gossip problem consists in estimating the average of the values diffused in the network in a distributed manner. We develop a method solving the gossip problem that depends only on the spectral dimension of the network, that is, in the communication network set-up, the dimension of the space in which the agents live. This contrasts with previous work that required the spectral gap of the network as a parameter, or suffered from slow mixing. Our method shows an important improvement over existing algorithms in the non-asymptotic regime, i.e., when the values are far from being fully mixed in the network. Our approach stems from a polynomial-based point of view on gossip algorithms, as well as an approximation of the spectral measure of the graphs with a Jacobi measure. We show the power of the approach with simulations on various graphs, and with performance guarantees on graphs of known spectral dimension, such as grids and random percolation bonds. An extension of this work to distributed Laplacian solvers is discussed. As a side result, we also use the polynomial-based point of view to show the convergence of the message passing algorithm for gossip of Moallemi \& Van Roy on regular graphs. The explicit computation of the rate of the convergence shows that message passing has a slow rate of convergence on graphs with small spectral gap.
High throughput quantitative metallography for complex microstructures using deep learning: A case study in ultrahigh carbon steel
Venue: arXiv cs.CV 2019
Year: 2019

We apply a deep convolutional neural network segmentation model to enable novel automated microstructure segmentation applications for complex microstructures typically evaluated manually and subjectively. We explore two microstructure segmentation tasks in an openly-available ultrahigh carbon steel microstructure dataset: segmenting cementite particles in the spheroidized matrix, and segmenting larger fields of view featuring grain boundary carbide, spheroidized particle matrix, particle-free grain boundary denuded zone, and Widmanstätten cementite. We also demonstrate how to combine these data-driven microstructure segmentation models to obtain empirical cementite particle size and denuded zone width distributions from more complex micrographs containing multiple microconstituents. The full annotated dataset is available on materialsdata.nist.gov (https://materialsdata.nist.gov/handle/11256/964).
Echo: Compiler-based GPU Memory Footprint Reduction for LSTM RNN Training
Venue: arXiv cs.LG 2019
Year: 2019

The Long-Short-Term-Memory Recurrent Neural Networks (LSTM RNNs) are a popular class of machine learning models for analyzing sequential data. Their training on modern GPUs, however, is limited by the GPU memory capacity. Our profiling results of the LSTM RNN-based Neural Machine Translation (NMT) model reveal that feature maps of the attention and RNN layers form the memory bottleneck and runtime is unevenly distributed across different layers when training on GPUs. Based on these two observations, we propose to recompute the feature maps rather than stashing them persistently in the GPU memory. While the idea of feature map recomputation has been considered before, existing solutions fail to deliver satisfactory footprint reduction, as they do not address two key challenges. For each feature map recomputation to be effective and efficient, its effect on (1) the total memory footprint, and (2) the total execution time has to be carefully estimated. To this end, we propose *Echo*, a new compiler-based optimization scheme that addresses the first challenge with a practical mechanism that estimates the memory benefits of recomputation over the entire computation graph, and the second challenge by non-conservatively estimating the recomputation overhead leveraging layer specifics. *Echo* reduces the GPU memory footprint automatically and transparently without any changes required to the training source code, and is effective for models beyond LSTM RNNs. We evaluate *Echo* on numerous state-of-the-art machine learning workloads on real systems with modern GPUs and observe footprint reduction ratios of 1.89X on average and 3.13X maximum. Such reduction can be converted into faster training with a larger batch size, savings in GPU energy consumption (e.g., training with one GPU as fast as with four), and/or an increase in the maximum number of layers under the same GPU memory budget.
Constrained Graph Variational Autoencoders for Molecule Design
Venue: arXiv cs.LG 2019
Year: 2019

Graphs are ubiquitous data structures for representing interactions between entities. With an emphasis on the use of graphs to represent chemical molecules, we explore the task of learning to generate graphs that conform to a distribution observed in training data. We propose a variational autoencoder model in which both encoder and decoder are graph-structured. Our decoder assumes a sequential ordering of graph extension steps and we discuss and analyze design choices that mitigate the potential downsides of this linearization. Experiments compare our approach with a wide range of baselines on the molecule generation task and show that our method is more successful at matching the statistics of the original dataset on semantically important metrics. Furthermore, we show that by using appropriate shaping of the latent space, our model allows us to design molecules that are (locally) optimal in desired properties.