OpenRaiser/Intern-Atlas huggingface dataset:
From Simulation to Real World Maneuver Execution using Deep Reinforcement Learning
Venue: arXiv cs.RO 2021
Year: 2021

Deep Reinforcement Learning has proved to be able to solve many control tasks in different fields, but the behavior of these systems is not always as expected when deployed in real-world scenarios. This is mainly due to the lack of domain adaptation between simulated and real-world data together with the absence of distinction between train and test datasets. In this work, we investigate these problems in the autonomous driving field, especially for a maneuver planning module for roundabout insertions. In particular, we present a system based on multiple environments in which agents are trained simultaneously, evaluating the behavior of the model in different scenarios. Finally, we analyze techniques aimed at reducing the gap between simulated and real-world data showing that this increased the generalization capabilities of the system both on unseen and real-world scenarios.
Corpus and Models for Lemmatisation and POS-tagging of Classical French Theatre
Venue: arXiv cs.CL 2021
Year: 2021

This paper describes the process of building an annotated corpus and training models for classical French literature, with a focus on theatre, and particularly comedies in verse. It was originally developed as a preliminary step to the stylometric analyses presented in Cafiero and Camps [2019]. The use of a recent lemmatiser based on neural networks and a CRF tagger allows to achieve accuracies beyond the current state-of-the art on the in-domain test, and proves to be robust during out-of-domain tests, i.e.up to 20th c.novels.
Neural Collaborative Reasoning
Venue: arXiv cs.IR 2021
Year: 2021

Existing Collaborative Filtering (CF) methods are mostly designed based on the idea of matching, i.e., by learning user and item embeddings from data using shallow or deep models, they try to capture the associative relevance patterns in data, so that a user embedding can be matched with relevant item embeddings using designed or learned similarity functions. However, as a cognition rather than a perception intelligent task, recommendation requires not only the ability of pattern recognition and matching from data, but also the ability of cognitive reasoning in data. In this paper, we propose to advance Collaborative Filtering (CF) to Collaborative Reasoning (CR), which means that each user knows part of the reasoning space, and they collaborate for reasoning in the space to estimate preferences for each other. Technically, we propose a Neural Collaborative Reasoning (NCR) framework to bridge learning and reasoning. Specifically, we integrate the power of representation learning and logical reasoning, where representations capture similarity patterns in data from perceptual perspectives, and logic facilitates cognitive reasoning for informed decision making. An important challenge, however, is to bridge differentiable neural networks and symbolic reasoning in a shared architecture for optimization and inference. To solve the problem, we propose a modularized reasoning architecture, which learns logical operations such as AND ($\wedge$), OR ($\vee$) and NOT ($\neg$) as neural modules for implication reasoning ($\rightarrow$). In this way, logical expressions can be equivalently organized as neural networks, so that logical reasoning and prediction can be conducted in a continuous space. Experiments on real-world datasets verified the advantages of our framework compared with both shallow, deep and reasoning models.
VPR-Bench: An Open-Source Visual Place Recognition Evaluation Framework with Quantifiable Viewpoint and Appearance Change
Venue: arXiv cs.CV 2021
Year: 2021

Visual Place Recognition (VPR) is the process of recognising a previously visited place using visual information, often under varying appearance conditions and viewpoint changes and with computational constraints. VPR is related to the concepts of localisation, loop closure, image retrieval and is a critical component of many autonomous navigation systems ranging from autonomous vehicles to drones and computer vision systems. While the concept of place recognition has been around for many years, VPR research has grown rapidly as a field over the past decade due to improving camera hardware and its potential for deep learning-based techniques, and has become a widely studied topic in both the computer vision and robotics communities. This growth however has led to fragmentation and a lack of standardisation in the field, especially concerning performance evaluation. Moreover, the notion of viewpoint and illumination invariance of VPR techniques has largely been assessed qualitatively and hence ambiguously in the past. In this paper, we address these gaps through a new comprehensive open-source framework for assessing the performance of VPR techniques, dubbed "VPR-Bench". VPR-Bench (Open-sourced at: https://github.com/MubarizZaffar/VPR-Bench) introduces two much-needed capabilities for VPR researchers: firstly, it contains a benchmark of 12 fully-integrated datasets and 10 VPR techniques, and secondly, it integrates a comprehensive variation-quantified dataset for quantifying viewpoint and illumination invariance. We apply and analyse popular evaluation metrics for VPR from both the computer vision and robotics communities, and discuss how these different metrics complement and/or replace each other, depending upon the underlying applications and system requirements.
Three-Filters-to-Normal: An Accurate and Ultrafast Surface Normal Estimator
Venue: arXiv cs.CV 2021
Year: 2021

This paper proposes three-filters-to-normal (3F2N), an accurate and ultrafast surface normal estimator (SNE), which is designed for structured range sensor data, e.g., depth/disparity images. 3F2N SNE computes surface normals by simply performing three filtering operations (two image gradient filters in horizontal and vertical directions, respectively, and a mean/median filter) on an inverse depth image or a disparity image. Despite the simplicity of 3F2N SNE, no similar method already exists in the literature. To evaluate the performance of our proposed SNE, we created three large-scale synthetic datasets (easy, medium and hard) using 24 3D mesh models, each of which is used to generate 1800--2500 pairs of depth images (resolution: 480X640 pixels) and the corresponding ground-truth surface normal maps from different views. 3F2N SNE demonstrates the state-of-the-art performance, outperforming all other existing geometry-based SNEs, where the average angular errors with respect to the easy, medium and hard datasets are 1.66 degrees, 5.69 degrees and 15.31 degrees, respectively. Furthermore, our C++ and CUDA implementations achieve a processing speed of over 260 Hz and 21 kHz, respectively. Our datasets and source code are publicly available at sites.google.com/view/3f2n.
From Symmetric to Asymmetric Asynchronous Byzantine Consensus
Venue: arXiv cs.DC 2021
Year: 2021

Consensus is arguably one of the most important notions in distributed computing. Among asynchronous, randomized, and signature-free implementations, the protocols of Mostéfaoui et al. (PODC 2014 and JACM 2015) represent a landmark result, which has been extended later and taken up in practical systems. The protocols achieve optimal resilience and takes, in expectation, only a constant expected number of rounds of quadratic message complexity. Randomization is provided through a common-coin primitive. In traditional consensus protocols, all involved processes adhere to a global, symmetric failure model, typically only defined by bounds on the number of faulty processes. Motivated by applications to blockchains, however, more flexible trust assumptions have recently been considered. In particular, with asymmetric trust, a process is free to choose which other processes it trusts and which ones might collude against it. This paper revisits the optimal asynchronous protocol of Mostéfaoui et al. and shows how to realize it with asymmetric trust. The paper starts by pointing out in detail why some versions of this protocol may violate liveness. Then it proposes a fix for the protocol that does not affect its properties, but lets it regain the simplicity of its original version (PODC 2014). At the same time, the paper shows how to realize randomized signature-free asynchronous Byzantine consensus with asymmetric quorums. This results in an optimal consensus protocol with subjective, asymmetric trust and constant expected running time. It is suitable for applications to blockchains, for instance.
Sham: A DSL for Fast DSLs
Venue: arXiv cs.PL 2021
Year: 2021

Domain-specific languages (DSLs) are touted as both easy to embed in programs and easy to optimize. Yet these goals are often in tension. Embedded or internal DSLs fit naturally with a host language, while inheriting the host's performance characteristics. External DSLs can use external optimizers and languages but sit apart from the host. We present Sham, a toolkit designed to enable internal DSLs with high performance. Sham provides a domain-specific language (embedded in Racket) for implementing other high-performance DSLs, with transparent compilation to assembly code at runtime. Sham is well suited as both a compilation target for other embedded DSLs and for transparently replacing DSL support code with faster versions. Sham provides seamless inter-operation with its host language without requiring any additional effort from its users. Sham also provides a framework for defining language syntax which implements Sham's own language interface as well. We validate Sham's design on a series of case studies, ranging from Krishnamurthi's classic automata DSL to a sound synthesis DSL and a probabilistic programming language. All of these are existing DSLs where we replaced the backend using Sham, resulting in major performance gains. We present an example-driven description of how Sham can smoothly enhance an existing DSL into a high-performance one. When compared to existing approaches for implementing high-performance DSLs, Sham's design aims for both simplicity and programmer control. This makes it easier to port our techniques to other languages and frameworks, or borrow Sham's innovations "à la carte" without adopting the whole approach. Sham builds a sophisticated and powerful DSL construction toolkit atop fundamental language features including higher-order functions, data structures, and a foreign-function interface (FFI), all readily available in other languages. Furthermore, Sham's approach allows DSL developers to simply write functions, either using Sham or generating Sham, without needing to work through complex staging or partial evaluation systems.
Distilling Knowledge from Ensembles of Acoustic Models for Joint CTC-Attention End-to-End Speech Recognition
Venue: arXiv cs.LG 2021
Year: 2021

Knowledge distillation has been widely used to compress existing deep learning models while preserving the performance on a wide range of applications. In the specific context of Automatic Speech Recognition (ASR), distillation from ensembles of acoustic models has recently shown promising results in increasing recognition performance. In this paper, we propose an extension of multi-teacher distillation methods to joint CTC-attention end-to-end ASR systems. We also introduce three novel distillation strategies. The core intuition behind them is to integrate the error rate metric to the teacher selection rather than solely focusing on the observed losses. In this way, we directly distill and optimize the student toward the relevant metric for speech recognition. We evaluate these strategies under a selection of training procedures on different datasets (TIMIT, Librispeech, Common Voice) and various languages (English, French, Italian). In particular, state-of-the-art error rates are reported on the Common Voice French, Italian and TIMIT datasets.
Griefing-Penalty: Countermeasure for Griefing Attack in Lightning Network
Venue: arXiv cs.CR 2021
Year: 2021

Lightning Network can execute unlimited number of off-chain payments, without incurring the cost of recording each of them in the blockchain. However, conditional payments in such networks is susceptible to Griefing Attack. In this attack, an adversary doesn't resolve the payment with the intention of blocking channel capacity of the network. We propose an efficient countermeasure for the attack, known as Griefing-Penalty. If any party in the network mounts a griefing attack, it needs to pay a penalty proportional to the collateral cost of executing a payment. The penalty is used for compensating affected parties in the network. We propose a new payment protocol HTLC-GP or Hashed Timelock Contract with Griefing-Penalty to demonstrate the utility of the countermeasure. Upon comparing our protocol with existing payment protocol Hashed Timelock Contract, we observe that the average revenue earned by the attacker decreases substantially for HTLC-GP as compared to HTLC. We also study the impact of path length for routing a transaction and rate of griefing-penalty on the budget invested by an adversary for mounting the attack. The budget needed for mounting griefing attack in HTLC-GP is 12 times more than the budget needed by attacker in HTLC, given that each payment instance being routed via path length of hop count 20.
List Decodable Mean Estimation in Nearly Linear Time
Venue: arXiv cs.DS 2021
Year: 2021

Learning from data in the presence of outliers is a fundamental problem in statistics. Until recently, no computationally efficient algorithms were known to compute the mean of a high dimensional distribution under natural assumptions in the presence of even a small fraction of outliers. In this paper, we consider robust statistics in the presence of overwhelming outliers where the majority of the dataset is introduced adversarially. With only an $α< 1/2$ fraction of "inliers" (clean data) the mean of a distribution is unidentifiable. However, in their influential work, [CSV17] introduces a polynomial time algorithm recovering the mean of distributions with bounded covariance by outputting a succinct list of $O(1/α)$ candidate solutions, one of which is guaranteed to be close to the true distributional mean; a direct analog of 'List Decoding' in the theory of error correcting codes. In this work, we develop an algorithm for list decodable mean estimation in the same setting achieving up to constants the information theoretically optimal recovery, optimal sample complexity, and in nearly linear time up to polylogarithmic factors in dimension. Our conceptual innovation is to design a descent style algorithm on a nonconvex landscape, iteratively removing minima to generate a succinct list of solutions. Our runtime bottleneck is a saddle-point optimization for which we design custom primal dual solvers for generalized packing and covering SDP's under Ky-Fan norms, which may be of independent interest.
Mirror Descent Policy Optimization
Venue: arXiv cs.LG 2021
Year: 2021

Mirror descent (MD), a well-known first-order method in constrained convex optimization, has recently been shown as an important tool to analyze trust-region algorithms in reinforcement learning (RL). However, there remains a considerable gap between such theoretically analyzed algorithms and the ones used in practice. Inspired by this, we propose an efficient RL algorithm, called {\em mirror descent policy optimization} (MDPO). MDPO iteratively updates the policy by {\em approximately} solving a trust-region problem, whose objective function consists of two terms: a linearization of the standard RL objective and a proximity term that restricts two consecutive policies to be close to each other. Each update performs this approximation by taking multiple gradient steps on this objective function. We derive {\em on-policy} and {\em off-policy} variants of MDPO, while emphasizing important design choices motivated by the existing theory of MD in RL. We highlight the connections between on-policy MDPO and two popular trust-region RL algorithms: TRPO and PPO, and show that explicitly enforcing the trust-region constraint is in fact {\em not} a necessity for high performance gains in TRPO. We then show how the popular soft actor-critic (SAC) algorithm can be derived by slight modifications of off-policy MDPO. Overall, MDPO is derived from the MD principles, offers a unified approach to viewing a number of popular RL algorithms, and performs better than or on-par with TRPO, PPO, and SAC in a number of continuous control tasks. Code is available at \url{https://github.com/manantomar/Mirror-Descent-Policy-Optimization}.
Fast Decoding of Codes in the Rank, Subspace, and Sum-Rank Metric
Venue: arXiv cs.IT 2021
Year: 2021

We speed up existing decoding algorithms for three code classes in different metrics: interleaved Gabidulin codes in the rank metric, lifted interleaved Gabidulin codes in the subspace metric, and linearized Reed-Solomon codes in the sum-rank metric. The speed-ups are achieved by new algorithms that reduce the cores of the underlying computational problems of the decoders to one common tool: computing left and right approximant bases of matrices over skew polynomial rings. To accomplish this, we describe a skew-analogue of the existing PM-Basis algorithm for matrices over ordinary polynomials. This captures the bulk of the work in multiplication of skew polynomials, and the complexity benefit comes from existing algorithms performing this faster than in classical quadratic complexity. The new algorithms for the various decoding-related computational problems are interesting in their own and have further applications, in particular parts of decoders of several other codes and foundational problems related to the remainder-evaluation of skew polynomials.
Applying the Transformer to Character-level Transduction
Venue: arXiv cs.CL 2021
Year: 2021

The transformer has been shown to outperform recurrent neural network-based sequence-to-sequence models in various word-level NLP tasks. Yet for character-level transduction tasks, e.g. morphological inflection generation and historical text normalization, there are few works that outperform recurrent models using the transformer. In an empirical study, we uncover that, in contrast to recurrent sequence-to-sequence models, the batch size plays a crucial role in the performance of the transformer on character-level tasks, and we show that with a large enough batch size, the transformer does indeed outperform recurrent models. We also introduce a simple technique to handle feature-guided character-level transduction that further improves performance. With these insights, we achieve state-of-the-art performance on morphological inflection and historical text normalization. We also show that the transformer outperforms a strong baseline on two other character-level transduction tasks: grapheme-to-phoneme conversion and transliteration.
Hierarchical Isometry Properties of Hierarchical Measurements
Venue: arXiv cs.IT 2021
Year: 2021

A new class of measurement operators, coined hierarchical measurement operators, and prove results guaranteeing the efficient, stable and robust recovery of hierarchically structured signals from such measurements. We derive bounds on their hierarchical restricted isometry properties based on the restricted isometry constants of their constituent matrices, generalizing and extending prior work on Kronecker-product measurements. As an exemplary application, we apply the theory to two communication scenarios. The fast and scalable HiHTP algorithm is shown to be suitable for solving these types of problems and its performance is evaluated numerically in terms of sparse signal recovery and block detection capability.
Sequential Fundraising and Mutual Insurance
Venue: arXiv cs.GT 2021
Year: 2021

Seed fundraising for ventures often takes place by sequentially approaching potential contributors, who make observable decisions. The fundraising succeeds when a target number of investments is reached. Though resembling classic information cascades models, its behavior is radically different, exhibiting surprising complexities. Assuming a common distribution for contributors' levels of information, we show that participants rely on {\em mutual insurance}, i.e., invest despite unfavorable information, trusting future player strategies to protect them from loss. {\em Delegation} occurs when contributors invest unconditionally, empowering the decision to future players. Often, all early contributors delegate, in effect empowering the last few contributors to decide the outcome. Similar dynamics hold in sequential voting, as in voting in committees.
Markets for Efficient Public Good Allocation with Social Distancing
Venue: arXiv cs.GT 2021
Year: 2021

Public goods are often either over-consumed in the absence of regulatory mechanisms, or remain completely unused, as in the Covid-19 pandemic, where social distance constraints are enforced to limit the number of people who can share public spaces. In this work, we plug this gap through market based mechanisms designed to efficiently allocate capacity constrained public goods. To design these mechanisms, we leverage the theory of Fisher markets, wherein each agent in the economy is endowed with an artificial currency budget that they can spend to avail public goods. While Fisher markets provide a strong methodological backbone to model resource allocation problems, their applicability is limited to settings involving two types of constraints - budgets of individual buyers and capacities of goods. Thus, we introduce a modified Fisher market, where each individual may have additional physical constraints, characterize its solution properties and establish the existence of a market equilibrium. Furthermore, to account for additional constraints we introduce a social convex optimization problem where we perturb the budgets of agents such that the KKT conditions of the perturbed social problem establishes equilibrium prices. Finally, to compute the budget perturbations we present a fixed point scheme and illustrate convergence guarantees through numerical experiments. Thus, our mechanism, both theoretically and computationally, overcomes a fundamental limitation of classical Fisher markets, which only consider capacity and budget constraints.
Extracting Daily Dosage from Medication Instructions in EHRs: An Automated Approach and Lessons Learned
Venue: arXiv cs.CL 2021
Year: 2021

Medication timelines have been shown to be effective in helping physicians visualize complex patient medication information. A key feature in many such designs is a longitudinal representation of a medication's daily dosage and its changes over time. However, daily dosage as a discrete value is generally not provided and needs to be derived from free text instructions (Sig). Existing works in daily dosage extraction are narrow in scope, targeting dosage extraction for a single drug from clinical notes. Here, we present an automated approach to calculate daily dosage for all medications, combining deep learning-based named entity extractor with lexicon dictionaries and regular expressions, achieving 0.98 precision and 0.95 recall on an expert-generated dataset of 1,000 Sigs. We also analyze our expert-generated dataset, discuss the challenges in understanding the complex information contained in Sigs, and provide insights to guide future work in the general-purpose daily dosage calculation task.