OpenRaiser/Intern-Atlas huggingface dataset:
Refined Vertex Sparsifiers of Planar Graphs
Venue: arXiv cs.DS 2019
Year: 2019

We study the following version of cut sparsification. Given a large edge-weighted network $G$ with $k$ terminal vertices, compress it into a smaller network $H$ with the same terminals, such that every minimum terminal cut in $H$ approximates the corresponding one in $G$, up to a factor $q\geq 1$ that is called the quality. (The case $q=1$ is known also as a mimicking network). We provide new insights about the structure of minimum terminal cuts, leading to new results for cut sparsifiers of planar graphs. Our first contribution identifies a subset of the minimum terminal cuts, which we call elementary, that generates all the others. Consequently, $H$ is a cut sparsifier if and only if it preserves all the elementary terminal cuts (up to this factor $q$). This structural characterization lead to improved bounds on the size of $H$. For example, it improve the bound of mimicking-network size for planar graphs into a near-optimal one. Our second and main contribution is to refine the known bounds in terms of $γ=γ(G)$, which is defined as the minimum number of faces that are incident to all the terminals in a planar graph $G$. We prove that the number of elementary terminal cuts is $O((2k/γ)^{2γ})$ (compared to $O(2^k)$ terminal cuts), and furthermore obtain a mimicking-network of size $O(γ2^{2γ} k^4)$, which is near-optimal as a function of $γ$. In the analysis we break the elementary terminal cuts into fragments, and count them carefully. Our third contribution is a duality between cut sparsification and distance sparsification for certain planar graphs, when the sparsifier $H$ is required to be a minor of $G$. This duality connects problems that were previously studied separately, implying new results, new proofs of known results, and equivalences between open gaps.
Enabling Multi-Source Neural Machine Translation By Concatenating Source Sentences In Multiple Languages
Venue: arXiv cs.CL 2019
Year: 2019

In this paper, we explore a simple solution to "Multi-Source Neural Machine Translation" (MSNMT) which only relies on preprocessing a N-way multilingual corpus without modifying the Neural Machine Translation (NMT) architecture or training procedure. We simply concatenate the source sentences to form a single long multi-source input sentence while keeping the target side sentence as it is and train an NMT system using this preprocessed corpus. We evaluate our method in resource poor as well as resource rich settings and show its effectiveness (up to 4 BLEU using 2 source languages and up to 6 BLEU using 5 source languages). We also compare against existing methods for MSNMT and show that our solution gives competitive results despite its simplicity. We also provide some insights on how the NMT system leverages multilingual information in such a scenario by visualizing attention.
Performance Constrained Distributed Event-triggered Consensus in Multi-agent Systems
Venue: arXiv cs.SY 2019
Year: 2019

The paper proposes a distributed eventtriggered consensus approach for linear multi-agent systems with guarantees over rate of convergence, resilience to control gain uncertainties, and Pareto optimality of design parameters, namely, the event-triggering threshold (ET) and control gain. The event-triggered consensus problem is first converted to stability problem of an equivalent system. The Lyapunov stability theorem is then used to incorporate the performance constraints with the event-triggered consensus. Using an approximated linear scalarization method, the ET and the control gain are designed simultaneously by solving a convex constrained optimization problem. Followed by some preliminary steps, the optimization can be performed locally, i.e., no global information is required. The effectiveness of the proposed approach is studied through simulations for an experimental multi-agent system.
Tuple-oriented Compression for Large-scale Mini-batch Stochastic Gradient Descent
Venue: arXiv cs.LG 2019
Year: 2019

Data compression is a popular technique for improving the efficiency of data processing workloads such as SQL queries and more recently, machine learning (ML) with classical batch gradient methods. But the efficacy of such ideas for mini-batch stochastic gradient descent (MGD), arguably the workhorse algorithm of modern ML, is an open question. MGD's unique data access pattern renders prior art, including those designed for batch gradient methods, less effective. We fill this crucial research gap by proposing a new lossless compression scheme we call tuple-oriented compression (TOC) that is inspired by an unlikely source, the string/text compression scheme Lempel-Ziv-Welch, but tailored to MGD in a way that preserves tuple boundaries within mini-batches. We then present a suite of novel compressed matrix operation execution techniques tailored to the TOC compression scheme that operate directly over the compressed data representation and avoid decompression overheads. An extensive empirical evaluation with real-world datasets shows that TOC consistently achieves substantial compression ratios by up to 51x and reduces runtimes for MGD workloads by up to 10.2x in popular ML systems.
On Store Languages of Language Acceptors
Venue: arXiv cs.FL 2019
Year: 2019

It is well known that the "store language" of every pushdown automaton -- the set of store configurations (state and stack contents) that can appear as an intermediate step in accepting computations -- is a regular language. Here many models of language acceptors with various data structures are examined, along with a study of their store languages. For each model, an attempt is made to find the simplest model that accepts their store languages. Some connections between store languages of one-way and two-way machines generally are demonstrated, as with connections between nondeterministic and deterministic machines. A nice application of these store language results is also presented, showing a general technique for proving families accepted by many deterministic models are closed under right quotient with regular languages, resolving some open questions (and significantly simplifying proofs for others that are known) in the literature. Lower bounds on the space complexity for recognizing store languages for the languages to be non-regular are obtained.
Quantifiers on languages and codensity monads
Venue: arXiv cs.LO 2019
Year: 2019

This paper contributes to the techniques of topo-algebraic recognition for languages beyond the regular setting as they relate to logic on words. In particular, we provide a general construction on recognisers corresponding to adding one layer of various kinds of quantifiers and prove a corresponding Reutenauer-type theorem. Our main tools are codensity monads and duality theory. Our construction hinges on a measure-theoretic characterisation of the profinite monad of the free S-semimodule monad for finite and commutative semirings S, which generalises our earlier insight that the Vietoris monad on Boolean spaces is the codensity monad of the finite powerset functor.
Bayesian Gates for Reliable Logical Operations under Noisy Condition
Venue: arXiv cs.OH 2019
Year: 2019

The reliability of logical operations is indispensable for the reliable operation of computational systems. Since the down-sizing of micro-fabrication generates non-negligible noise in these systems, a new approach for designing noise-immune gates is required. In this paper, we demonstrate that noise-immune gates can be designed by combining Bayesian inference theory with the idea of computation over a noisy signal. To reveal their practical advantages, the performance of these gates is evaluated in comparison with a stochastic resonance-based gate proposed previously. This approach for computation is also demonstrated to be better than a conventional one that conducts information transmission and computation separately.
Zero-Delay Source-Channel Coding with a One-Bit ADC Front End and Correlated Side Information at the Receiver
Venue: arXiv cs.IT 2019
Year: 2019

Zero-delay transmission of a Gaussian source over an additive white Gaussian noise (AWGN) channel is considered with a one-bit analog-to-digital converter (ADC) front end and a correlated side information at the receiver. The design of the optimal encoder and decoder is studied for two performance criteria, namely, the mean squared error (MSE) distortion and the distortion outage probability (DOP), under an average power constraint on the channel input. For both criteria, necessary optimality conditions for the encoder and the decoder are derived. Using these conditions, it is observed that the numerically optimized encoder (NOE) under the MSE distortion criterion is periodic, and its period increases with the correlation between the source and the receiver side information. For the DOP, it is instead seen that the NOE mappings periodically acquire positive and negative values, which decay to zero with increasing source magnitude, and the interval over which the mapping takes non-zero values, becomes wider with the correlation between the source and the side information.
Tracing Networks of Knowledge in the Digital Age
Venue: arXiv cs.CY 2019
Year: 2019

The emergence of new digital technologies has allowed the study of human behaviour at a scale and at level of granularity that were unthinkable just a decade ago. In particular, by analysing the digital traces left by people interacting in the online and offline worlds, we are able to trace the spreading of knowledge and ideas at both local and global scales. In this article we will discuss how these digital traces can be used to map knowledge across the world, outlining both the limitations and the challenges in performing this type of analysis. We will focus on data collected from social media platforms, large-scale digital repositories and mobile data. Finally, we will provide an overview of the tools that are available to scholars and practitioners for understanding these processes using these emerging forms of data.
Robust Non-Rigid Registration with Reweighted Position and Transformation Sparsity
Venue: arXiv cs.CV 2019
Year: 2019

Non-rigid registration is challenging because it is ill-posed with high degrees of freedom and is thus sensitive to noise and outliers. We propose a robust non-rigid registration method using reweighted sparsities on position and transformation to estimate the deformations between 3-D shapes. We formulate the energy function with position and transformation sparsity on both the data term and the smoothness term, and define the smoothness constraint using local rigidity. The double sparsity based non-rigid registration model is enhanced with a reweighting scheme, and solved by transferring the model into four alternately-optimized subproblems which have exact solutions and guaranteed convergence. Experimental results on both public datasets and real scanned datasets show that our method outperforms the state-of-the-art methods and is more robust to noise and outliers than conventional non-rigid registration methods.
Arrovian Aggregation of Convex Preferences
Venue: arXiv cs.GT 2019
Year: 2019

We consider social welfare functions that satisfy Arrow's classic axioms of independence of irrelevant alternatives and Pareto optimality when the outcome space is the convex hull of some finite set of alternatives. Individual and collective preferences are assumed to be continuous and convex, which guarantees the existence of maximal elements and the consistency of choice functions that return these elements, even without insisting on transitivity. We provide characterizations of both the domains of preferences and the social welfare functions that allow for anonymous Arrovian aggregation. The domains admit arbitrary preferences over alternatives, which completely determine an agent's preferences over all mixed outcomes. On these domains, Arrow's impossibility turns into a complete characterization of a unique social welfare function, which can be readily applied in settings involving divisible resources such as probability, time, or money.
Alignment of the Virtual Scene to the Tracking Space of a Mixed Reality Head-Mounted Display
Venue: arXiv cs.HC 2019
Year: 2019

With the mounting global interest for optical see-through head-mounted displays (OST-HMDs) across medical, industrial and entertainment settings, many systems with different capabilities are rapidly entering the market. Despite such variety, they all require display calibration to create a proper mixed reality environment. With the aid of tracking systems, it is possible to register rendered graphics with tracked objects in the real world. We propose a calibration procedure to properly align the coordinate system of a 3D virtual scene that the user sees with that of the tracker. Our method takes a blackbox approach towards the HMD calibration, where the tracker's data is its input and the 3D coordinates of a virtual object in the observer's eye is the output; the objective is thus to find the 3D projection that aligns the virtual content with its real counterpart. In addition, a faster and more intuitive version of this calibration is introduced in which the user simultaneously aligns multiple points of a single virtual 3D object with its real counterpart; this reduces the number of required repetitions in the alignment from 20 to only 4, which leads to a much easier calibration task for the user. In this paper, both internal (HMD camera) and external tracking systems are studied. We perform experiments with Microsoft HoloLens, taking advantage of its self localization and spatial mapping capabilities to eliminate the requirement for line of sight from the HMD to the object or external tracker. The experimental results indicate an accuracy of up to 4 mm in the average reprojection error based on two separate evaluation methods. We further perform experiments with the internal tracking on the Epson Moverio BT-300 to demonstrate that the method can provide similar results with other HMDs.
An analysis of budgeted parallel search on conditional Galton-Watson trees
Venue: arXiv cs.DS 2019
Year: 2019

Recently Avis and Jordan have demonstrated the efficiency of a simple technique called budgeting for the parallelization of a number of tree search algorithms. The idea is to limit the amount of work that a processor performs before it terminates its search and returns any unexplored nodes to a master process. This limit is set by a critical budget parameter which determines the overhead of the process. In this paper we study the behaviour of the budget parameter on conditional Galton-Watson trees obtaining asymptotically tight bounds on this overhead. We present empirical results to show that this bound is surprisingly accurate in practice.
Time-Contrastive Learning Based DNN Bottleneck Features for Text-Dependent Speaker Verification
Venue: arXiv cs.SD 2019
Year: 2019

In this paper, we present a time-contrastive learning (TCL) based bottleneck (BN)feature extraction method for speech signals with an application to text-dependent (TD) speaker verification (SV). It is well-known that speech signals exhibit quasi-stationary behavior in and only in a short interval, and the TCL method aims to exploit this temporal structure. More specifically, it trains deep neural networks (DNNs) to discriminate temporal events obtained by uniformly segmenting speech signals, in contrast to existing DNN based BN feature extraction methods that train DNNs using labeled data to discriminate speakers or pass-phrases or phones or a combination of them. In the context of speaker verification, speech data of fixed pass-phrases are used for TCL-BN training, while the pass-phrases used for TCL-BN training are excluded from being used for SV, so that the learned features can be considered generic. The method is evaluated on the RedDots Challenge 2016 database. Experimental results show that TCL-BN is superior to the existing speaker and pass-phrase discriminant BN features and the Mel-frequency cepstral coefficient feature for text-dependent speaker verification.
Tight Bounds on Online Checkpointing Algorithms
Venue: arXiv cs.CR 2019
Year: 2019

The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain $k$ memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. Bringmann et al. studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than $1.59-o(1)$ for all $k$, and smaller than $\ln4-o(1)\approx1.39$ for the sparse subset of $k$'s which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of $k$. In this paper we solve the main problems left open in the above-mentioned paper by proving that $\ln4$ is a tight upper and lower bound on the asymptotic discrepancy for all large $k$, and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of $k \leq 10$. In the last part of the paper we describe some new applications of this online checkpointing problem.
Commutative Algorithms Approximate the LLL-distribution
Venue: arXiv cs.DM 2019
Year: 2019

Following the groundbreaking Moser-Tardos algorithm for the Lovasz Local Lemma (LLL), a series of works have exploited a key ingredient of the original analysis, the witness tree lemma, in order to: derive deterministic, parallel and distributed algorithms for the LLL, to estimate the entropy of the output distribution, to partially avoid bad events, to deal with super-polynomially many bad events, and even to devise new algorithmic frameworks. Meanwhile, a parallel line of work, has established tools for analyzing stochastic local search algorithms motivated by the LLL that do not fall within the Moser-Tardos framework. Unfortunately, the aforementioned results do not transfer to these more general settings. Mainly, this is because the witness tree lemma, provably, no longer holds. Here we prove that for commutative algorithms, a class recently introduced by Kolmogorov and which captures the vast majority of LLL applications, the witness tree lemma does hold. Armed with this fact, we extend the main result of Haeupler, Saha, and Srinivasan to commutative algorithms, establishing that the output of such algorithms well-approximates the LLL-distribution, i.e., the distribution obtained by conditioning on all bad events being avoided, and give several new applications. For example, we show that the recent algorithm of Molloy for list coloring number of sparse, triangle-free graphs can output exponential many list colorings of the input graph.
The Emergence of Canalization and Evolvability in an Open-Ended, Interactive Evolutionary System
Venue: arXiv cs.NE 2019
Year: 2019

Natural evolution has produced a tremendous diversity of functional organisms. Many believe an essential component of this process was the evolution of evolvability, whereby evolution speeds up its ability to innovate by generating a more adaptive pool of offspring. One hypothesized mechanism for evolvability is developmental canalization, wherein certain dimensions of variation become more likely to be traversed and others are prevented from being explored (e.g. offspring tend to have similarly sized legs, and mutations affect the length of both legs, not each leg individually). While ubiquitous in nature, canalization almost never evolves in computational simulations of evolution. Not only does that deprive us of in silico models in which to study the evolution of evolvability, but it also raises the question of which conditions give rise to this form of evolvability. Answering this question would shed light on why such evolvability emerged naturally and could accelerate engineering efforts to harness evolution to solve important engineering challenges. In this paper we reveal a unique system in which canalization did emerge in computational evolution. We document that genomes entrench certain dimensions of variation that were frequently explored during their evolutionary history. The genetic representation of these organisms also evolved to be highly modular and hierarchical, and we show that these organizational properties correlate with increased fitness. Interestingly, the type of computational evolutionary experiment that produced this evolvability was very different from traditional digital evolution in that there was no objective, suggesting that open-ended, divergent evolutionary processes may be necessary for the evolution of evolvability.
A Simulator for LLVM Bitcode
Venue: arXiv cs.SE 2019
Year: 2019

In this paper, we introduce an interactive simulator for programs in the form of LLVM bitcode. The main features of the simulator include precise control over thread scheduling, automatic checkpoints and reverse stepping, support for source-level information about functions and variables in C and C++ programs and structured heap visualisation. Additionally, the simulator is compatible with DiVM (DIVINE VM) hypercalls, which makes it possible to load, simulate and analyse counterexamples from an existing model checker.
Fast and Accurate Sparse Coding of Visual Stimuli with a Simple, Ultra-Low-Energy Spiking Architecture
Venue: arXiv cs.ET 2019
Year: 2019

Memristive crossbars have become a popular means for realizing unsupervised and supervised learning techniques. In previous neuromorphic architectures with leaky integrate-and-fire neurons, the crossbar itself has been separated from the neuron capacitors to preserve mathematical rigor. In this work, we sought to simplify the design, creating a fast circuit that consumed significantly lower power at a minimal cost of accuracy. We also showed that connecting the neurons directly to the crossbar resulted in a more efficient sparse coding architecture, and alleviated the need to pre-normalize receptive fields. This work provides derivations for the design of such a network, named the Simple Spiking Locally Competitive Algorithm, or SSLCA, as well as CMOS designs and results on the CIFAR and MNIST datasets. Compared to a non-spiking model which scored 33% on CIFAR-10 with a single-layer classifier, this hardware scored 32% accuracy. When used with a state-of-the-art deep learning classifier, the non-spiking model achieved 82% and our simplified, spiking model achieved 80%, while compressing the input data by 92%. Compared to a previously proposed spiking model, our proposed hardware consumed 99% less energy to do the same work at 21x the throughput. Accuracy held out with online learning to a write variance of 3%, suitable for the often-reported 4-bit resolution required for neuromorphic algorithms; with offline learning to a write variance of 27%; and with read variance to 40%. The proposed architecture's excellent accuracy, throughput, and significantly lower energy usage demonstrate the utility of our innovations.