OpenRaiser/Intern-Atlas huggingface dataset:
A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
Venue: arXiv cs.DS 2021
Year: 2021

In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i.e. a projection of a regular cube. Examples of zonotopal lattices include lattices of Voronoi's first kind and tensor products of root lattices of type A. The combinatorial structure of zonotopal lattices can be described by regular matroids/totally unimodular matrices. We observe that a linear algebra version of the minimum mean cycle canceling method can be applied for efficiently solving the closest vector problem in a zonotopal lattice if the lattice is given as the integral kernel of a totally unimodular matrix.
A Game Theoretic Framework for Model Based Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Model-based reinforcement learning (MBRL) has recently gained immense interest due to its potential for sample efficiency and ability to incorporate off-policy data. However, designing stable and efficient MBRL algorithms using rich function approximators have remained challenging. To help expose the practical challenges in MBRL and simplify algorithm design from the lens of abstraction, we develop a new framework that casts MBRL as a game between: (1) a policy player, which attempts to maximize rewards under the learned model; (2) a model player, which attempts to fit the real-world data collected by the policy player. For algorithm development, we construct a Stackelberg game between the two players, and show that it can be solved with approximate bi-level optimization. This gives rise to two natural families of algorithms for MBRL based on which player is chosen as the leader in the Stackelberg game. Together, they encapsulate, unify, and generalize many previous MBRL algorithms. Furthermore, our framework is consistent with and provides a clear basis for heuristics known to be important in practice from prior works. Finally, through experiments we validate that our proposed algorithms are highly sample efficient, match the asymptotic performance of model-free policy gradient, and scale gracefully to high-dimensional tasks like dexterous hand manipulation. Additional details and code can be obtained from the project page at https://sites.google.com/view/mbrl-game
SongNet: Rigid Formats Controlled Text Generation
Venue: arXiv cs.CL 2021
Year: 2021

Neural text generation has made tremendous progress in various tasks. One common characteristic of most of the tasks is that the texts are not restricted to some rigid formats when generating. However, we may confront some special text paradigms such as Lyrics (assume the music score is given), Sonnet, SongCi (classical Chinese poetry of the Song dynasty), etc. The typical characteristics of these texts are in three folds: (1) They must comply fully with the rigid predefined formats. (2) They must obey some rhyming schemes. (3) Although they are restricted to some formats, the sentence integrity must be guaranteed. To the best of our knowledge, text generation based on the predefined rigid formats has not been well investigated. Therefore, we propose a simple and elegant framework named SongNet to tackle this problem. The backbone of the framework is a Transformer-based auto-regressive language model. Sets of symbols are tailor-designed to improve the modeling performance especially on format, rhyme, and sentence integrity. We improve the attention mechanism to impel the model to capture some future information on the format. A pre-training and fine-tuning framework is designed to further improve the generation quality. Extensive experiments conducted on two collected corpora demonstrate that our proposed framework generates significantly better results in terms of both automatic metrics and the human evaluation.
IDDA: a large-scale multi-domain dataset for autonomous driving
Venue: arXiv cs.CV 2021
Year: 2021

Semantic segmentation is key in autonomous driving. Using deep visual learning architectures is not trivial in this context, because of the challenges in creating suitable large scale annotated datasets. This issue has been traditionally circumvented through the use of synthetic datasets, that have become a popular resource in this field. They have been released with the need to develop semantic segmentation algorithms able to close the visual domain shift between the training and test data. Although exacerbated by the use of artificial data, the problem is extremely relevant in this field even when training on real data. Indeed, weather conditions, viewpoint changes and variations in the city appearances can vary considerably from car to car, and even at test time for a single, specific vehicle. How to deal with domain adaptation in semantic segmentation, and how to leverage effectively several different data distributions (source domains) are important research questions in this field. To support work in this direction, this paper contributes a new large scale, synthetic dataset for semantic segmentation with more than 100 different source visual domains. The dataset has been created to explicitly address the challenges of domain shift between training and test data in various weather and view point conditions, in seven different city types. Extensive benchmark experiments assess the dataset, showcasing open challenges for the current state of the art. The dataset will be available at: https://idda-dataset.github.io/home/ .
CWY Parametrization: a Solution for Parallelized Optimization of Orthogonal and Stiefel Matrices
Venue: arXiv cs.LG 2021
Year: 2021

We introduce an efficient approach for optimization over orthogonal groups on highly parallel computation units such as GPUs or TPUs. As in earlier work, we parametrize an orthogonal matrix as a product of Householder reflections. However, to overcome low parallelization capabilities of computing Householder reflections sequentially, we propose employing an accumulation scheme called the compact WY (or CWY) transform -- a compact parallelization-friendly matrix representation for the series of Householder reflections. We further develop a novel Truncated CWY (or T-CWY) approach for Stiefel manifold parametrization which has a competitive complexity and, again, yields benefits when computed on GPUs and TPUs. We prove that our CWY and T-CWY methods lead to convergence to a stationary point of the training objective when coupled with stochastic gradient descent. We apply our methods to train recurrent neural network architectures in the tasks of neural machine translation and video prediction.
Evolving Diverse Sets of Tours for the Travelling Salesperson Problem
Venue: arXiv cs.NE 2021
Year: 2021

Evolving diverse sets of high quality solutions has gained increasing interest in the evolutionary computation literature in recent years. With this paper, we contribute to this area of research by examining evolutionary diversity optimisation approaches for the classical Traveling Salesperson Problem (TSP). We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions when adopting these measures. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches. Furthermore, we compare our approaches in terms of theoretical properties and the final set of tours obtained by the evolutionary diversity optimisation algorithm.
Survey of Crosschain Communications Protocols
Venue: arXiv cs.CR 2021
Year: 2021

Crosschain communications allows information to be communicated between blockchains. Consensus in the context of crosschain communications relates to how participants on one blockchain are convinced of the state of a remote blockchain. It describes how parties associated with a source blockchain come to agreement and communicate with a destination blockchain such that information from the source blockchain can be trusted. This paper surveys crosschain communications protocols, presenting them based on the top-level usage scenarios they are trying to meet: value swapping, crosschain messaging, and blockchain pinning. It analyses how each protocol achieves crosschain consensus, what trust assumptions are made, their ability to operate successfully in Permissionless and Permissioned blockchains contexts, and whether the protocol delivers atomic updates across blockchains.
Almost-Reed--Muller Codes Achieve Constant Rates for Random Errors
Venue: arXiv cs.IT 2021
Year: 2021

This paper considers '$δ$-almost Reed-Muller codes', i.e., linear codes spanned by evaluations of all but a $δ$ fraction of monomials of degree at most $d$. It is shown that for any $δ> 0$ and any $\varepsilon>0$, there exists a family of $δ$-almost Reed-Muller codes of constant rate that correct $1/2-\varepsilon$ fraction of random errors with high probability. For exact Reed-Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed-Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC '15). Our approach is based on the recent polarization result for Reed-Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed-Muller code entropies.
Discrete Variational Attention Models for Language Generation
Venue: arXiv cs.LG 2021
Year: 2021

Variational autoencoders have been widely applied for natural language generation, however, there are two long-standing problems: information under-representation and posterior collapse. The former arises from the fact that only the last hidden state from the encoder is transformed to the latent space, which is insufficient to summarize data. The latter comes as a result of the imbalanced scale between the reconstruction loss and the KL divergence in the objective function. To tackle these issues, in this paper we propose the discrete variational attention model with categorical distribution over the attention mechanism owing to the discrete nature in languages. Our approach is combined with an auto-regressive prior to capture the sequential dependency from observations, which can enhance the latent space for language generation. Moreover, thanks to the property of discreteness, the training of our proposed approach does not suffer from posterior collapse. Furthermore, we carefully analyze the superiority of discrete latent space over the continuous space with the common Gaussian distribution. Extensive experiments on language generation demonstrate superior advantages of our proposed approach in comparison with the state-of-the-art counterparts.
An effective construction for cut-and-project rhombus tilings with global n-fold rotational symmetry
Venue: arXiv cs.DM 2021
Year: 2021

We give an explicit and effective construction for rhombus cut-and-project tilings with global n-fold rotational symmetry for any n. This construction is based on the dualization of regular n-fold multigrids. The main point is to prove the regularity of these multigrids, for this we use a result on trigonometric diophantine equations.
Partial Volume Segmentation of Brain MRI Scans of any Resolution and Contrast
Venue: arXiv cs.CV 2021
Year: 2021

Partial voluming (PV) is arguably the last crucial unsolved problem in Bayesian segmentation of brain MRI with probabilistic atlases. PV occurs when voxels contain multiple tissue classes, giving rise to image intensities that may not be representative of any one of the underlying classes. PV is particularly problematic for segmentation when there is a large resolution gap between the atlas and the test scan, e.g., when segmenting clinical scans with thick slices, or when using a high-resolution atlas. In this work, we present PV-SynthSeg, a convolutional neural network (CNN) that tackles this problem by directly learning a mapping between (possibly multi-modal) low resolution (LR) scans and underlying high resolution (HR) segmentations. PV-SynthSeg simulates LR images from HR label maps with a generative model of PV, and can be trained to segment scans of any desired target contrast and resolution, even for previously unseen modalities where neither images nor segmentations are available at training. PV-SynthSeg does not require any preprocessing, and runs in seconds. We demonstrate the accuracy and flexibility of the method with extensive experiments on three datasets and 2,680 scans. The code is available at https://github.com/BBillot/SynthSeg.
Learnings from Technological Interventions in a Low Resource Language: A Case-Study on Gondi
Venue: arXiv cs.CL 2021
Year: 2021

The primary obstacle to developing technologies for low-resource languages is the lack of usable data. In this paper, we report the adoption and deployment of 4 technology-driven methods of data collection for Gondi, a low-resource vulnerable language spoken by around 2.3 million tribal people in south and central India. In the process of data collection, we also help in its revival by expanding access to information in Gondi through the creation of linguistic resources that can be used by the community, such as a dictionary, children's stories, an app with Gondi content from multiple sources and an Interactive Voice Response (IVR) based mass awareness platform. At the end of these interventions, we collected a little less than 12,000 translated words and/or sentences and identified more than 650 community members whose help can be solicited for future translation efforts. The larger goal of the project is collecting enough data in Gondi to build and deploy viable language technologies like machine translation and speech to text systems that can help take the language onto the internet.
Assurance 2.0: A Manifesto
Venue: arXiv cs.SE 2021
Year: 2021

System assurance is confronted by significant challenges. Some of these are new, for example, autonomous systems with major functions driven by machine learning and AI, and ultra-rapid system development, while others are the familiar, persistent issues of the need for efficient, effective and timely assurance. Traditional assurance is seen as a brake on innovation and often costly and time consuming. We therefore propose a modernized framework, Assurance 2.0, as an enabler that supports innovation and continuous incremental assurance. Perhaps unexpectedly, it does so by making assurance more rigorous, with increased focus on the reasoning and evidence employed, and explicit identification of defeaters and counterevidence.
Polarized-VAE: Proximity Based Disentangled Representation Learning for Text Generation
Venue: arXiv cs.CL 2021
Year: 2021

Learning disentangled representations of real-world data is a challenging open problem. Most previous methods have focused on either supervised approaches which use attribute labels or unsupervised approaches that manipulate the factorization in the latent space of models such as the variational autoencoder (VAE) by training with task-specific losses. In this work, we propose polarized-VAE, an approach that disentangles select attributes in the latent space based on proximity measures reflecting the similarity between data points with respect to these attributes. We apply our method to disentangle the semantics and syntax of sentences and carry out transfer experiments. Polarized-VAE outperforms the VAE baseline and is competitive with state-of-the-art approaches, while being more a general framework that is applicable to other attribute disentanglement tasks.
A Game-Theoretic Utility Network for Cooperative Multi-Agent Decisions in Adversarial Environments
Venue: arXiv cs.MA 2021
Year: 2021

Underlying relationships among multi-agent systems (MAS) in hazardous scenarios can be represented as Game-theoretic models. We measure the performance of MAS achieving tasks from the perspective of balancing success probability and system costs. This paper proposes a new network-based model called Game-theoretic Utility Tree (GUT), which decomposes high-level strategies into executable low-level actions for cooperative MAS decisions. This is combined with a new payoff measure based on agent needs for real-time strategy games. We present an Explore game domain to evaluate GUT against the state-of-the-art QMIX decision-making method. Conclusive results on extensive numerical simulations indicate that GUT can organize more complex relationships among MAS cooperation, helping the group achieve challenging tasks with lower costs and a higher winning rate.
OF-VO: Efficient Navigation among Pedestrians Using Commodity Sensors
Venue: arXiv cs.RO 2021
Year: 2021

We present a modified velocity-obstacle (VO) algorithm that uses probabilistic partial observations of the environment to compute velocities and navigate a robot to a target. Our system uses commodity visual sensors, including a mono-camera and a 2D Lidar, to explicitly predict the velocities and positions of surrounding obstacles through optical flow estimation, object detection, and sensor fusion. A key aspect of our work is coupling the perception (OF: optical flow) and planning (VO) components for reliable navigation. Overall, our OF-VO algorithm using learning-based perception and model-based planning methods offers better performance than prior algorithms in terms of navigation time and success rate of collision avoidance. Our method also provides bounds on the probabilistic collision avoidance algorithm. We highlight the realtime performance of OF-VO on a Turtlebot navigating among pedestrians in both simulated and real-world scenes. A demo video is available at https://gamma.umd.edu/ofvo/
Supervised Contrastive Learning
Venue: arXiv cs.LG 2021
Year: 2021

Contrastive learning applied to self-supervised representation learning has seen a resurgence in recent years, leading to state of the art performance in the unsupervised training of deep image models. Modern batch contrastive approaches subsume or significantly outperform traditional contrastive losses such as triplet, max-margin and the N-pairs loss. In this work, we extend the self-supervised batch contrastive approach to the fully-supervised setting, allowing us to effectively leverage label information. Clusters of points belonging to the same class are pulled together in embedding space, while simultaneously pushing apart clusters of samples from different classes. We analyze two possible versions of the supervised contrastive (SupCon) loss, identifying the best-performing formulation of the loss. On ResNet-200, we achieve top-1 accuracy of 81.4% on the ImageNet dataset, which is 0.8% above the best number reported for this architecture. We show consistent outperformance over cross-entropy on other datasets and two ResNet variants. The loss shows benefits for robustness to natural corruptions and is more stable to hyperparameter settings such as optimizers and data augmentations. Our loss function is simple to implement, and reference TensorFlow code is released at https://t.ly/supcon.
Efficient Algorithms for Approximating Quantum Partition Functions
Venue: arXiv cs.DS 2021
Year: 2021

We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature. Our algorithm is based on the quantum cluster expansion of Netočný and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts. Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.
Robust testing of low-dimensional functions
Venue: arXiv cs.CC 2021
Year: 2021

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. A recent work of the authors showed that linear $k$-juntas are testable. Thus there exists an algorithm to distinguish between: 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ which is a linear $k$-junta with surface area $s$, 2. $f$ is $ε$-far from any linear $k$-junta with surface area $(1+ε)s$, where the query complexity of the algorithm is independent of the ambient dimension $n$. Following the surge of interest in noise-tolerant property testing, in this paper we prove a noise-tolerant (or robust) version of this result. Namely, we give an algorithm which given any $c>0$, $ε>0$, distinguishes between 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ has correlation at least $c$ with some linear $k$-junta with surface area $s$. 2. $f$ has correlation at most $c-ε$ with any linear $k$-junta with surface area at most $s$. The query complexity of our tester is $k^{\mathsf{poly}(s/ε)}$. Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class $\mathcal{C}$ of linear $k$-juntas with surface area bounded by $s$. As a consequence, we obtain a fully noise tolerant tester with query complexity $k^{O(\mathsf{poly}(\log k/ε))}$ for the class of intersection of $k$-halfspaces (for constant $k$) over the Gaussian space. Our query complexity is independent of the ambient dimension $n$. Previously, no non-trivial noise tolerant testers were known even for a single halfspace.
Deep Learning Based Packet Detection and Carrier Frequency Offset Estimation in IEEE 802.11ah
Venue: arXiv cs.IT 2021
Year: 2021

Wi-Fi systems based on the IEEE 802.11 standards are the most popular wireless interfaces that use Listen Before Talk (LBT) method for channel access. The distinctive feature of a majority of LBT-based systems is that the transmitters use preambles that precede the data to allow the receivers to perform packet detection and carrier frequency offset (CFO) estimation. Preambles usually contain repetitions of training symbols with good correlation properties, while conventional digital receivers apply correlation-based methods for both packet detection and CFO estimation. However, in recent years, data-based machine learning methods are disrupting physical layer research. Promising results have been presented, in particular, in the domain of deep learning (DL)-based channel estimation. In this paper, we present a performance and complexity analysis of packet detection and CFO estimation using both the conventional and the DL-based approaches. The goal of the study is to investigate under which conditions the performance of the DL-based methods approach or even surpass the conventional methods, but also, under which conditions their performance is inferior. Focusing on the emerging IEEE 802.11ah standard, our investigation uses both the standard-based simulated environment, and a real-world testbed based on Software Defined Radios.