OpenRaiser/Intern-Atlas huggingface dataset:
A Distributed Laplacian Solver and its Applications to Electrical Flow and Random Spanning Tree Computation
Venue: arXiv cs.DC 2020
Year: 2020

We use queueing networks to present a new approach to solving Laplacian systems. This marks a significant departure from the existing techniques, mostly based on graph-theoretic constructions and sampling. Our distributed solver works for a large and important class of Laplacian systems that we call "one-sink" Laplacian systems. Specifically, our solver can produce solutions for systems of the form $Lx = b$ where exactly one of the coordinates of $b$ is negative. Our solver is a distributed algorithm that takes $\widetilde{O}(t_{hit} d_{\max})$ time (where $\widetilde{O}$ hides $\text{poly}\log n$ factors) to produce an approximate solution where $t_{hit}$ is the worst-case hitting time of the random walk on the graph, which is $Θ(n)$ for a large set of important graphs, and $d_{\max}$ is the generalized maximum degree of the graph. The class of one-sink Laplacians includes the important voltage computation problem and allows us to compute the effective resistance between nodes in a distributed setting. As a result, our Laplacian solver can be used to adapt the approach by Kelner and Mądry (2009) to give the first distributed algorithm to compute approximate random spanning trees efficiently.
Learning Novel Policies For Tasks
Venue: arXiv cs.LG 2020
Year: 2020

In this work, we present a reinforcement learning algorithm that can find a variety of policies (novel policies) for a task that is given by a task reward function. Our method does this by creating a second reward function that recognizes previously seen state sequences and rewards those by novelty, which is measured using autoencoders that have been trained on state sequences from previously discovered policies. We present a two-objective update technique for policy gradient algorithms in which each update of the policy is a compromise between improving the task reward and improving the novelty reward. Using this method, we end up with a collection of policies that solves a given task as well as carrying out action sequences that are distinct from one another. We demonstrate this method on maze navigation tasks, a reaching task for a simulated robot arm, and a locomotion task for a hopper. We also demonstrate the effectiveness of our approach on deceptive tasks in which policy gradient methods often get stuck.
Can NetGAN be improved on short random walks?
Venue: arXiv cs.LG 2020
Year: 2020

Graphs are useful structures that can model several important real-world problems. Recently, learning graphs have drawn considerable attention, leading to the proposal of new methods for learning these data structures. One of these studies produced NetGAN, a new approach for generating graphs via random walks. Although NetGAN has shown promising results in terms of accuracy in the tasks of generating graphs and link prediction, the choice of vertices from which it starts random walks can lead to inconsistent and highly variable results, especially when the length of walks is short. As an alternative to random starting, this study aims to establish a new method for initializing random walks from a set of dense vertices. We purpose estimating the importance of a node based on the inverse of its influence over the whole vertices of its neighborhood through random walks of different sizes. The proposed method manages to achieve significantly better accuracy, less variance and lesser outliers.
Correlated Variational Auto-Encoders
Venue: arXiv cs.LG 2020
Year: 2020

Variational Auto-Encoders (VAEs) are capable of learning latent representations for high dimensional data. However, due to the i.i.d. assumption, VAEs only optimize the singleton variational distributions and fail to account for the correlations between data points, which might be crucial for learning latent representations from dataset where a priori we know correlations exist. We propose Correlated Variational Auto-Encoders (CVAEs) that can take the correlation structure into consideration when learning latent representations with VAEs. CVAEs apply a prior based on the correlation structure. To address the intractability introduced by the correlated prior, we develop an approximation by average of a set of tractable lower bounds over all maximal acyclic subgraphs of the undirected correlation graph. Experimental results on matching and link prediction on public benchmark rating datasets and spectral clustering on a synthetic dataset show the effectiveness of the proposed method over baseline algorithms.
A Brief Survey of Multilingual Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

We present a survey on multilingual neural machine translation (MNMT), which has gained a lot of traction in the recent years. MNMT has been useful in improving translation quality as a result of knowledge transfer. MNMT is more promising and interesting than its statistical machine translation counterpart because end-to-end modeling and distributed representations open new avenues. Many approaches have been proposed in order to exploit multilingual parallel corpora for improving translation quality. However, the lack of a comprehensive survey makes it difficult to determine which approaches are promising and hence deserve further exploration. In this paper, we present an in-depth survey of existing literature on MNMT. We categorize various approaches based on the resource scenarios as well as underlying modeling principles. We hope this paper will serve as a starting point for researchers and engineers interested in MNMT.
Finding Dominating Induced Matchings in $S_{1,1,5}$-Free Graphs in Polynomial Time
Venue: arXiv cs.DM 2020
Year: 2020

Let $G=(V,E)$ be a finite undirected graph. An edge set $E' \subseteq E$ is a {\em dominating induced matching} ({\em d.i.m.}) in $G$ if every edge in $E$ is intersected by exactly one edge of $E'$. The \emph{Dominating Induced Matching} (\emph{DIM}) problem asks for the existence of a d.i.m.\ in $G$; this problem is also known as the \emph{Efficient Edge Domination} problem; it is the Efficient Domination problem for line graphs. The DIM problem is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but is solvable in linear time for $P_7$-free graphs, and in polynomial time for $S_{1,2,4}$-free graphs as well as for $S_{2,2,2}$-free graphs and for $S_{2,2,3}$-free graphs. In this paper, combining two distinct approaches, we solve it in polynomial time for $S_{1,1,5}$-free graphs.
Capacity and Price Competition in Markets with Congestion Effects
Venue: arXiv cs.GT 2020
Year: 2020

We study oligopolistic competition in service markets where firms offer a service to customers. The service quality of a firm - from the perspective of a customer - depends on the congestion and the charged price. A firm can set a price for the service offered and additionally decides on the service capacity in order to mitigate congestion. The total profit of a firm is derived from the gained revenue minus the capacity investment cost. Firms simultaneously set capacities and prices in order to maximize their profit and customers subsequently choose the services with lowest combined cost (congestion and price). For this basic model, Johari et al. (2010) derived the first existence and uniqueness results of pure Nash equilibria (PNE) assuming mild conditions on congestion functions. Their existence proof relies on Kakutani's fixed-point theorem and a key assumption for the theorem to work is that demand for service is elastic (modeled by a smooth and strictly decreasing inverse demand function). In this paper, we consider the case of perfectly inelastic demand, i.e. there is a fixed volume of customers requesting service. This scenario applies to realistic cases where customers are not willing to drop out of the market, e.g. if prices are regulated by reasonable price caps. We investigate existence, uniqueness and quality of PNE for models with inelastic demand and price caps. We show that for linear congestion cost functions, there exists a PNE. This result requires a completely new proof approach compared to previous approaches, since the best response correspondences of firms may be empty, thus standard fixed-point arguments are not directly applicable. We show that the game is C-secure (see McLennan et al. (2011)), which leads to the existence of PNE. We furthermore show that the PNE is unique, and that the efficiency compared to a social optimum is unbounded in general.
Graphical Models in Meshed Distribution Grids: Topology estimation, change detection and limitations
Venue: arXiv cs.SY 2020
Year: 2020

Graphical models are a succinct way to represent the structure in probability distributions. This article analyzes the graphical model of nodal voltages in non-radial power distribution grids. Using algebraic and structural properties of graphical models, algorithms exactly determining topology and detecting line changes for distribution grids are presented along with their theoretical limitations. We show that if distribution grids have cycles/loops of size greater than three, then nodal voltages are sufficient for efficient topology estimation without additional assumptions on system parameters. In contrast, line failure or change detection using nodal voltages does not require any structural assumption. Under noisy measurements, we provide the first non-trivial bounds on the maximum noise that the system can tolerate for asymptotically correct topology recovery. The performance of the designed algorithms is validated with nonlinear AC power flow samples generated by Matpower on test grids, including scenarios with injection correlations and system noise.
Fiduciary Bandits
Venue: arXiv cs.GT 2020
Year: 2020

Recommendation systems often face exploration-exploitation tradeoffs: the system can only learn about the desirability of new options by recommending them to some user. Such systems can thus be modeled as multi-armed bandit settings; however, users are self-interested and cannot be made to follow recommendations. We ask whether exploration can nevertheless be performed in a way that scrupulously respects agents' interests---i.e., by a system that acts as a fiduciary. More formally, we introduce a model in which a recommendation system faces an exploration-exploitation tradeoff under the constraint that it can never recommend any action that it knows yields lower reward in expectation than an agent would achieve if it acted alone. Our main contribution is a positive result: an asymptotically optimal, incentive compatible, and ex-ante individually rational recommendation algorithm.
TGView3D System Description: 3-Dimensional Visualization of Theory Graphs
Venue: arXiv cs.HC 2020
Year: 2020

We describe TGView3D, an interactive 3D graph viewer optimized for exploring theory graphs. To exploit the three spatial dimensions, it extends a force-directed layout with a hierarchical component. Because of the limitations of regular displays, the system also supports the use of a head-mounted display and utilizes several virtual realty interaction concepts.
Multilinear Compressive Learning
Venue: arXiv cs.CV 2020
Year: 2020

Compressive Learning is an emerging topic that combines signal acquisition via compressive sensing and machine learning to perform inference tasks directly on a small number of measurements. Many data modalities naturally have a multi-dimensional or tensorial format, with each dimension or tensor mode representing different features such as the spatial and temporal information in video sequences or the spatial and spectral information in hyperspectral images. However, in existing compressive learning frameworks, the compressive sensing component utilizes either random or learned linear projection on the vectorized signal to perform signal acquisition, thus discarding the multi-dimensional structure of the signals. In this paper, we propose Multilinear Compressive Learning, a framework that takes into account the tensorial nature of multi-dimensional signals in the acquisition step and builds the subsequent inference model on the structurally sensed measurements. Our theoretical complexity analysis shows that the proposed framework is more efficient compared to its vector-based counterpart in both memory and computation requirement. With extensive experiments, we also empirically show that our Multilinear Compressive Learning framework outperforms the vector-based framework in object classification and face recognition tasks, and scales favorably when the dimensionalities of the original signals increase, making it highly efficient for high-dimensional multi-dimensional signals.
On a caching system with object sharing
Venue: arXiv cs.PF 2020
Year: 2020

We consider a content-caching system thatis shared by a number of proxies. The cache could belocated in an edge-cloud datacenter and the proxies couldeach serve a large population of mobile end-users. Eachproxy operates its own LRU-list of a certain capacity inthe shared cache. The length of objects simultaneouslyappearing in plural LRU-lists is equally divided amongthem,i.e., object sharing among the LRUs. We provide a "working-set" approximation for this system to quicklyestimate the cache-hit probabilities under such objectsharing, which can be used to facilitate admission control.Also, a way to reduce ripple evictions,i.e.,setrequestoverhead, is suggested. We give numerical results for ourMemCacheD with Object Sharing (MCD-OS) prototype.
Guiding Inferences in Connection Tableau by Recurrent Neural Networks
Venue: arXiv cs.AI 2020
Year: 2020

We present a dataset and experiments on applying recurrent neural networks (RNNs) for guiding clause selection in the connection tableau proof calculus. The RNN encodes a sequence of literals from the current branch of the partial proof tree to a hidden vector state; using it, the system selects a clause for extending the proof tree. The training data and learning setup are described, and the results are discussed and compared with state of the art using gradient boosted trees. Additionally, we perform a conjecturing experiment in which the RNN does not just select an existing clause, but completely constructs the next tableau goal.
Are all the frames equally important?
Venue: arXiv cs.HC 2020
Year: 2020

In this work, we address the problem of measuring and predicting temporal video saliency - a metric which defines the importance of a video frame for human attention. Unlike the conventional spatial saliency which defines the location of the salient regions within a frame (as it is done for still images), temporal saliency considers importance of a frame as a whole and may not exist apart from context. The proposed interface is an interactive cursor-based algorithm for collecting experimental data about temporal saliency. We collect the first human responses and perform their analysis. As a result, we show that qualitatively, the produced scores have very explicit meaning of the semantic changes in a frame, while quantitatively being highly correlated between all the observers. Apart from that, we show that the proposed tool can simultaneously collect fixations similar to the ones produced by eye-tracker in a more affordable way. Further, this approach may be used for creation of first temporal saliency datasets which will allow training computational predictive algorithms. The proposed interface does not rely on any special equipment, which allows to run it remotely and cover a wide audience.
Leaking Information Through Cache LRU States
Venue: arXiv cs.CR 2020
Year: 2020

The Least-Recently Used cache replacement policy and its variants are widely deployed in modern processors. This paper shows for the first time in detail that the LRU states of caches can be used to leak information: any access to a cache by a sender will modify the LRU state, and the receiver is able to observe this through a timing measurement. This paper presents LRU timing-based channels both when the sender and the receiver have shared memory, e.g., shared library data pages, and when they are separate processes without shared memory. In addition, the new LRU timing-based channels are demonstrated on both Intel and AMD processors in scenarios where the sender and the receiver are sharing the cache in both hyper-threaded setting and time-sliced setting. The transmission rate of the LRU channels can be up to 600Kbps per cache set in the hyper-threaded setting. Different from the majority of existing cache channels which require the sender to trigger cache misses, the new LRU channels work with the sender only having cache hits, making the channel faster and more stealthy. This paper also demonstrates that the new LRU channels can be used in transient execution attacks, e.g., Spectre. Further, this paper shows that the LRU channels pose threats to existing secure cache designs, and this work demonstrates the LRU channels affect the secure PL cache. The paper finishes by discussing and evaluating possible defenses.
Auditable Register Emulations
Venue: arXiv cs.DC 2020
Year: 2020

The widespread prevalence of data breaches amplifies the importance of auditing storage systems. In this work, we initiate the study of auditable storage emulations, which provide the capability for an auditor to report the previously executed reads in a register. We precisely define the notion of auditable register and its properties, and establish tight bounds and impossibility results for auditable storage emulations in the presence of faulty storage objects. Our formulation considers loggable read-write registers that securely store data using information dispersal and support fast reads. In such a scenario, given a maximum number~$f$ of faulty storage objects and a minimum number~$τ$ of data blocks required to recover a stored value, we prove that (1) auditability is impossible if $τ\leq 2f $; (2) implementing a weak form of auditability requires $τ\geq 3f+1$; and (3) a stronger form of auditability is impossible. We also show that signing read requests overcomes the lower bound of weak auditability, while totally ordering operations or using non-fast reads enables strong auditability.
Cube-Split: A Structured Grassmannian Constellation for Non-Coherent SIMO Communications
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we propose a practical structured constellation for non-coherent communication with a single transmit antenna over Rayleigh flat and block fading channel without instantaneous channel state information. The constellation symbols belong to the Grassmannian of lines and are defined up to a complex scaling. The constellation is generated by partitioning the Grassmannian of lines into a collection of bent hypercubes and defining a mapping onto each of these bent hypercubes such that the resulting symbols are approximately uniformly distributed on the Grassmannian. With a reasonable choice of parameters, this so-called cube-split constellation has higher packing efficiency, represented by the minimum distance, than the existing structured constellations. Furthermore, exploiting the constellation structure, we propose low-complexity greedy symbol decoder and log-likelihood ratio computation, as well as an efficient way to associate it to a multilevel code with multistage decoding. Numerical results show that the performance of the cube-split constellation is close to that of a numerically optimized constellation and better than other structured constellations. It also outperforms a coherent pilot-based scheme in terms of error probability and achievable data rate in the regime of short coherence time and large constellation size.
Explainable Machine Learning for Scientific Insights and Discoveries
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning methods have been remarkably successful for a wide range of application areas in the extraction of essential information from data. An exciting and relatively recent development is the uptake of machine learning in the natural sciences, where the major goal is to obtain novel scientific insights and discoveries from observational or simulated data. A prerequisite for obtaining a scientific outcome is domain knowledge, which is needed to gain explainability, but also to enhance scientific consistency. In this article we review explainable machine learning in view of applications in the natural sciences and discuss three core elements which we identified as relevant in this context: transparency, interpretability, and explainability. With respect to these core elements, we provide a survey of recent scientific works that incorporate machine learning and the way that explainable machine learning is used in combination with domain knowledge from the application areas.
LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
Venue: arXiv cs.IT 2020
Year: 2020

Gradient-based distributed learning in Parameter Server (PS) computing architectures is subject to random delays due to straggling worker nodes, as well as to possible communication bottlenecks between PS and workers. Solutions have been recently proposed to separately address these impairments based on the ideas of gradient coding, worker grouping, and adaptive worker selection. This paper provides a unified analysis of these techniques in terms of wall-clock time, communication, and computation complexity measures. Furthermore, in order to combine the benefits of gradient coding and grouping in terms of robustness to stragglers with the communication and computation load gains of adaptive selection, novel strategies, named Lazily Aggregated Gradient Coding (LAGC) and Grouped-LAG (G-LAG), are introduced. Analysis and results show that G-LAG provides the best wall-clock time and communication performance, while maintaining a low computational cost, for two representative distributions of the computing times of the worker nodes.
Generative Imputation and Stochastic Prediction
Venue: arXiv cs.LG 2020
Year: 2020

In many machine learning applications, we are faced with incomplete datasets. In the literature, missing data imputation techniques have been mostly concerned with filling missing values. However, the existence of missing values is synonymous with uncertainties not only over the distribution of missing values but also over target class assignments that require careful consideration. In this paper, we propose a simple and effective method for imputing missing features and estimating the distribution of target assignments given incomplete data. In order to make imputations, we train a simple and effective generator network to generate imputations that a discriminator network is tasked to distinguish. Following this, a predictor network is trained using the imputed samples from the generator network to capture the classification uncertainties and make predictions accordingly. The proposed method is evaluated on CIFAR-10 and MNIST image datasets as well as five real-world tabular classification datasets, under different missingness rates and structures. Our experimental results show the effectiveness of the proposed method in generating imputations as well as providing estimates for the class uncertainties in a classification task when faced with missing values.