OpenRaiser/Intern-Atlas huggingface dataset:
Reconstructing occluded Elevation Information in Terrain Maps with Self-supervised Learning
Venue: arXiv cs.RO 2022
Year: 2022

Accurate and complete terrain maps enhance the awareness of autonomous robots and enable safe and optimal path planning. Rocks and topography often create occlusions and lead to missing elevation information in the Digital Elevation Map (DEM). Currently, these occluded areas are either fully avoided during motion planning or the missing values in the elevation map are filled-in using traditional interpolation, diffusion or patch-matching techniques. These methods cannot leverage the high-level terrain characteristics and the geometric constraints of line of sight we humans use intuitively to predict occluded areas. We introduce a self-supervised learning approach capable of training on real-world data without a need for ground-truth information to reconstruct the occluded areas in the DEMs. We accomplish this by adding artificial occlusion to the incomplete elevation maps constructed on a real robot by performing ray casting. We first evaluate a supervised learning approach on synthetic data for which we have the full ground-truth available and subsequently move to several real-world datasets. These real-world datasets were recorded during exploration of both structured and unstructured terrain with a legged robot, and additionally in a planetary scenario on Lunar analogue terrain. We state a significant improvement compared to the baseline methods both on synthetic terrain and for the real-world datasets. Our neural network is able to run in real-time on both CPU and GPU with suitable sampling rates for autonomous ground robots. We motivate the applicability of reconstructing occlusion in elevation maps with preliminary motion planning experiments.
Cross-lingual Transfer of Monolingual Models
Venue: arXiv cs.CL 2022
Year: 2022

Recent studies in zero-shot cross-lingual learning using multilingual models have falsified the previous hypothesis that shared vocabulary and joint pre-training are the keys to cross-lingual generalization. Inspired by this advancement, we introduce a cross-lingual transfer method for monolingual models based on domain adaptation. We study the effects of such transfer from four different languages to English. Our experimental results on GLUE show that the transferred models outperform the native English model independently of the source language. After probing the English linguistic knowledge encoded in the representations before and after transfer, we find that semantic information is retained from the source language, while syntactic information is learned during transfer. Additionally, the results of evaluating the transferred models in source language tasks reveal that their performance in the source domain deteriorates after transfer.
Towards a Game-Theoretic Security Analysis of Off-Chain Protocols
Venue: arXiv cs.CR 2022
Year: 2022

Off-chain protocols constitute one of the most promising approaches to solve the inherent scalability issue of blockchain technologies. The core idea is to let parties transact on-chain only once to establish a channel between them, leveraging later on the resulting channel paths to perform arbitrarily many peer-to-peer transactions off-chain. While significant progress has been made in terms of proof techniques for off-chain protocols, existing approaches do not capture the game-theoretic incentives at the core of their design, which led to overlooking significant attack vectors like the Wormhole attack in the past. In this work we take a first step towards a principled game-theoretic security analysis of off-chain protocols by introducing the first game-theoretic model that is expressive enough to reason about their security. We advocate the use of Extensive Form Games (EFGs) and introduce two instances of EFGs to capture security properties of the closing and the routing of the Lightning Network. Specifically, we model the closing protocol, which relies on punishment mechanisms to disincentivize parties to upload old channel states on-chain. Moreover, we model the routing protocol, thereby formally characterizing the Wormhole attack, a vulnerability that undermines the fee-based incentive mechanism underlying the Lightning Network.
Sublinear Time Eigenvalue Approximation via Random Sampling
Venue: arXiv cs.DS 2022
Year: 2022

We study the problem of approximating the eigenspectrum of a symmetric matrix $\mathbf A \in \mathbb{R}^{n \times n}$ with bounded entries (i.e., $\|\mathbf A\|_{\infty} \leq 1$). We present a simple sublinear time algorithm that approximates all eigenvalues of $\mathbf{A}$ up to additive error $\pm εn$ using those of a randomly sampled $\tilde {O}\left (\frac{\log^3 n}{ε^3}\right ) \times \tilde O\left (\frac{\log^3 n}{ε^3}\right )$ principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values (the magnitudes of the eigenvalues). We give improved error bounds of $\pm ε\sqrt{\text{nnz}(\mathbf{A})}$ and $\pm ε\|\mathbf A\|_F$ when the rows of $\mathbf A$ can be sampled with probabilities proportional to their sparsities or their squared $\ell_2$ norms respectively. Here $\text{nnz}(\mathbf{A})$ is the number of non-zero entries in $\mathbf{A}$ and $\|\mathbf A\|_F$ is its Frobenius norm. Even for the strictly easier problems of approximating the singular values or testing the existence of large negative eigenvalues (Bakshi, Chepurko, and Jayaram, FOCS '20), our results are the first that take advantage of non-uniform sampling to give improved error bounds. From a technical perspective, our results require several new eigenvalue concentration and perturbation bounds for matrices with bounded entries. Our non-uniform sampling bounds require a new algorithmic approach, which judiciously zeroes out entries of a randomly sampled submatrix to reduce variance, before computing the eigenvalues of that submatrix as estimates for those of $\mathbf A$. We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice.
Transaction Placement in Sharded Blockchains
Venue: arXiv cs.DC 2022
Year: 2022

While many researchers adopt a sharding approach to design scaling blockchains, few works have studied the transaction placement problem incurred by sharding protocols. The widely-used hashing placement algorithm renders an overwhelming portion of transactions as cross-shard. In this paper, we analyze the high cost of cross-shard transactions and reveal that most Bitcoin transactions have simple dependencies and can become single-shard under a placement algorithm taking transaction dependencies into account. In addition, we perform a case study of OptChain, which is the state-of-the-art transaction placement algorithm for sharded blockchains, and find a shortcoming of it. A simple fix is proposed, and our evaluation results demonstrate that the proposed fix effectively helps OptChain overcome the shortcoming and significantly improve the system performance under a special workload. The authors of OptChain made some revisions to the algorithm description after noticing our work. Their updated algorithm does not exhibit the shortcoming under the workloads employed by this paper.
GarNet: A Continuous Robot Vision Approach for Predicting Shapes and Visually Perceived Weights of Garments
Venue: arXiv cs.RO 2022
Year: 2022

We present a Garment Similarity Network (GarNet) that learns geometric and physical similarities between known garments by continuously observing a garment while a robot picks it up from a table. The aim is to capture and encode geometric and physical characteristics of a garment into a manifold where a decision can be carried out, such as predicting the garment's shape class and its visually perceived weight. Our approach features an early stop strategy, which means that GarNet does not need to observe a garment being picked up from a crumpled to a hanging state to make a prediction. In our experiments, we find that GarNet achieves prediction accuracies of 92% for shape classification and 95.5% for predicting weights and advances state-of-art approaches by 21% for shape classification.
Small Promise CSPs that reduce to large CSPs
Venue: arXiv cs.CC 2022
Year: 2022

For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A,B) asks whether a given input structure maps homomorphically to A or does not even map to B. We are promised that the input satisfies exactly one of these two cases. If there exists a structure C with homomorphisms $A\to C\to B$, then PCSP(A,B) reduces naturally to CSP(C). To the best of our knowledge all known tractable PCSPs reduce to tractable CSPs in this way. However Barto showed that some PCSPs over finite structures A, B require solving CSPs over infinite C. We show that even when such a reduction to finite C is possible, this structure may become arbitrarily large. For every integer $n>1$ and every prime p we give A, B of size n with a single relation of arity $n^p$ such that PCSP(A, B) reduces via a chain of homomorphisms $ A\to C\to B$ to a tractable CSP over some C of size p but not over any smaller structure. In a second family of examples, for every prime $p\geq 7$ we construct A, B of size $p-1$ with a single ternary relation such that PCSP(A, B) reduces via $A\to C\to B$ to a tractable CSP over some C of size p but not over any smaller structure. In contrast we show that if A, B are graphs and PCSP(A,B) reduces to tractable CSP(C) for some finite digraph C, then already A or B has a tractable CSP. This extends results and answers a question of Deng et al.
Scaling Up Silicon Photonic-based Accelerators: Challenges and Opportunities
Venue: arXiv cs.ET 2022
Year: 2022

Digital accelerators in the latest generation of CMOS processes support multiply and accumulate (MAC) operations at energy efficiencies spanning 10-to-100~fJ/Op. But the operating speed for such MAC operations are often limited to a few hundreds of MHz. Optical or optoelectronic MAC operations on today's SOI-based silicon photonic integrated circuit platforms can be realized at a speed of tens of GHz, leading to much lower latency and higher throughput. In this paper, we study the energy efficiency of integrated silicon photonic MAC circuits based on Mach-Zehnder modulators and microring resonators. We describe the bounds on energy efficiency and scaling limits for NxN optical networks with today's technology, based on the optical and electrical link budget. We also describe research directions that can overcome the current limitations.
EVAGAN: Evasion Generative Adversarial Network for Low Data Regimes
Venue: arXiv cs.CR 2022
Year: 2022

A myriad of recent literary works has leveraged generative adversarial networks (GANs) to generate unseen evasion samples. The purpose is to annex the generated data with the original train set for adversarial training to improve the detection performance of machine learning (ML) classifiers. The quality of generated adversarial samples relies on the adequacy of training data samples. However, in low data regimes like medical diagnostic imaging and cybersecurity, the anomaly samples are scarce in number. This paper proposes a novel GAN design called Evasion Generative Adversarial Network (EVAGAN) that is more suitable for low data regime problems that use oversampling for detection improvement of ML classifiers. EVAGAN not only can generate evasion samples, but its discriminator can act as an evasion-aware classifier. We have considered Auxiliary Classifier GAN (ACGAN) as a benchmark to evaluate the performance of EVAGAN on cybersecurity (ISCX-2014, CIC-2017 and CIC2018) botnet and computer vision (MNIST) datasets. We demonstrate that EVAGAN outperforms ACGAN for unbalanced datasets with respect to detection performance, training stability and time complexity. EVAGAN's generator quickly learns to generate the low sample class and hardens its discriminator simultaneously. In contrast to ML classifiers that require security hardening after being adversarially trained by GAN-generated data, EVAGAN renders it needless. The experimental analysis proves that EVAGAN is an efficient evasion hardened model for low data regimes for the selected cybersecurity and computer vision datasets. Code will be available at HTTPS://www.github.com/rhr407/EVAGAN.
Raising context awareness in motion forecasting
Venue: arXiv cs.CV 2022
Year: 2022

Learning-based trajectory prediction models have encountered great success, with the promise of leveraging contextual information in addition to motion history. Yet, we find that state-of-the-art forecasting methods tend to overly rely on the agent's current dynamics, failing to exploit the semantic contextual cues provided at its input. To alleviate this issue, we introduce CAB, a motion forecasting model equipped with a training procedure designed to promote the use of semantic contextual information. We also introduce two novel metrics - dispersion and convergence-to-range - to measure the temporal consistency of successive forecasts, which we found missing in standard metrics. Our method is evaluated on the widely adopted nuScenes Prediction benchmark as well as on a subset of the most difficult examples from this benchmark. The code is available at github.com/valeoai/CAB
Reliable Neural Networks for Regression Uncertainty Estimation
Venue: arXiv cs.LG 2022
Year: 2022

While deep neural networks are highly performant and successful in a wide range of real-world problems, estimating their predictive uncertainty remains a challenging task. To address this challenge, we propose and implement a loss function for regression uncertainty estimation based on the Bayesian Validation Metric (BVM) framework while using ensemble learning. The proposed loss reproduces maximum likelihood estimation in the limiting case. A series of experiments on in-distribution data show that the proposed method is competitive with existing state-of-the-art methods. Experiments on out-of-distribution data show that the proposed method is robust to statistical change and exhibits superior predictive capability.
Gaussian discrepancy: a probabilistic relaxation of vector balancing
Venue: arXiv cs.DM 2022
Year: 2022

We introduce a novel relaxation of combinatorial discrepancy called Gaussian discrepancy, whereby binary signings are replaced with correlated standard Gaussian random variables. This relaxation effectively reformulates an optimization problem over the Boolean hypercube into one over the space of correlation matrices. We show that Gaussian discrepancy is a tighter relaxation than the previously studied vector and spherical discrepancy problems, and we construct a fast online algorithm that achieves a version of the Banaszczyk bound for Gaussian discrepancy. This work also raises new questions such as the Komlós conjecture for Gaussian discrepancy, which may shed light on classical discrepancy problems.
GoG: Relation-aware Graph-over-Graph Network for Visual Dialog
Venue: arXiv cs.CL 2022
Year: 2022

Visual dialog, which aims to hold a meaningful conversation with humans about a given image, is a challenging task that requires models to reason the complex dependencies among visual content, dialog history, and current questions. Graph neural networks are recently applied to model the implicit relations between objects in an image or dialog. However, they neglect the importance of 1) coreference relations among dialog history and dependency relations between words for the question representation; and 2) the representation of the image based on the fully represented question. Therefore, we propose a novel relation-aware graph-over-graph network (GoG) for visual dialog. Specifically, GoG consists of three sequential graphs: 1) H-Graph, which aims to capture coreference relations among dialog history; 2) History-aware Q-Graph, which aims to fully understand the question through capturing dependency relations between words based on coreference resolution on the dialog history; and 3) Question-aware I-Graph, which aims to capture the relations between objects in an image based on fully question representation. As an additional feature representation module, we add GoG to the existing visual dialogue model. Experimental results show that our model outperforms the strong baseline in both generative and discriminative settings by a significant margin.
Simple Entity-Centric Questions Challenge Dense Retrievers
Venue: arXiv cs.CL 2022
Year: 2022

Open-domain question answering has exploded in popularity recently due to the success of dense retrieval models, which have surpassed sparse models using only a few supervised training examples. However, in this paper, we demonstrate current dense models are not yet the holy grail of retrieval. We first construct EntityQuestions, a set of simple, entity-rich questions based on facts from Wikidata (e.g., "Where was Arve Furset born?"), and observe that dense retrievers drastically underperform sparse methods. We investigate this issue and uncover that dense retrievers can only generalize to common entities unless the question pattern is explicitly observed during training. We discuss two simple solutions towards addressing this critical problem. First, we demonstrate that data augmentation is unable to fix the generalization problem. Second, we argue a more robust passage encoder helps facilitate better question adaptation using specialized question encoders. We hope our work can shed light on the challenges in creating a robust, universal dense retriever that works well across different input distributions.
Slot Filling for Biomedical Information Extraction
Venue: arXiv cs.CL 2022
Year: 2022

Information Extraction (IE) from text refers to the task of extracting structured knowledge from unstructured text. The task typically consists of a series of sub-tasks such as Named Entity Recognition and Relation Extraction. Sourcing entity and relation type specific training data is a major bottleneck in domains with limited resources such as biomedicine. In this work we present a slot filling approach to the task of biomedical IE, effectively replacing the need for entity and relation-specific training data, allowing us to deal with zero-shot settings. We follow the recently proposed paradigm of coupling a Tranformer-based bi-encoder, Dense Passage Retrieval, with a Transformer-based reading comprehension model to extract relations from biomedical text. We assemble a biomedical slot filling dataset for both retrieval and reading comprehension and conduct a series of experiments demonstrating that our approach outperforms a number of simpler baselines. We also evaluate our approach end-to-end for standard as well as zero-shot settings. Our work provides a fresh perspective on how to solve biomedical IE tasks, in the absence of relevant training data. Our code, models and datasets are available at https://github.com/ypapanik/biomedical-slot-filling.
Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms
Venue: arXiv cs.GT 2022
Year: 2022

In the assignment problem, the goal is to assign indivisible items to agents who have ordinal preferences, efficiently and fairly, in a strategyproof manner. In practice, first-choice maximality, i.e., assigning a maximal number of agents their top items, is often identified as an important efficiency criterion and measure of agents' satisfaction. In this paper, we propose a natural and intuitive efficiency property, favoring-eagerness-for-remaining-items (FERI), which requires that each item is allocated to an agent who ranks it highest among remaining items, thereby implying first-choice maximality. Using FERI as a heuristic, we design mechanisms that satisfy ex-post or ex-ante variants of FERI together with combinations of other desirable properties of efficiency (Pareto-efficiency), fairness (strong equal treatment of equals and sd-weak-envy-freeness), and strategyproofness (sd-weak-strategyproofness). We also explore the limits of FERI mechanisms in providing stronger efficiency, fairness, or strategyproofness guarantees through impossibility results.
Modern Evolution Strategies for Creativity: Fitting Concrete Images and Abstract Concepts
Venue: arXiv cs.NE 2022
Year: 2022

Evolutionary algorithms have been used in the digital art scene since the 1970s. A popular application of genetic algorithms is to optimize the procedural placement of vector graphic primitives to resemble a given painting. In recent years, deep learning-based approaches have also been proposed to generate procedural drawings, which can be optimized using gradient descent. In this work, we revisit the use of evolutionary algorithms for computational creativity. We find that modern evolution strategies (ES) algorithms, when tasked with the placement of shapes, offer large improvements in both quality and efficiency compared to traditional genetic algorithms, and even comparable to gradient-based methods. We demonstrate that ES is also well suited at optimizing the placement of shapes to fit the CLIP model, and can produce diverse, distinct geometric abstractions that are aligned with human interpretation of language. Videos and demo: https://es-clip.github.io/
Intelligent Reflecting Surface Aided MIMO with Cascaded LoS Links: Channel Modelling and Full Multiplexing Region
Venue: arXiv cs.IT 2022
Year: 2022

This work studies the modelling and the optimization of intelligent reflecting surface (IRS) assisted multiple-input multiple-output (MIMO) systems through cascaded line-of-sight (LoS) links. In Part I of this work, we build up a new IRS-aided MIMO channel model, named the cascaded LoS MIMO channel. The proposed channel model consists of a transmitter (Tx) and a receiver (Rx) both equipped with uniform linear arrays, and an IRS is used to enable communications between the transmitter and the receiver through the LoS links seen by the IRS. When modeling the reflection of electromagnetic waves at the IRS, we take into account the curvature of the wavefront on different reflecting elements. Based on the established model, we study the spatial multiplexing capability of the cascaded LoS MIMO system. We introduce the notion of full multiplexing region (FMR) for the cascaded LoS MIMO channel, where the FMR is the union of Tx-IRS and IRS-Rx distance pairs that enable full multiplexing communication. Under a special passive beamforming strategy named reflective focusing, we derive an inner bound of the FMR, and provide the corresponding orientation settings of the antenna arrays that enable full multiplexing. Based on the proposed channel model and reflective focusing, the mutual information maximization problem is discussed in Part II.
ARCA23K: An audio dataset for investigating open-set label noise
Venue: arXiv cs.SD 2022
Year: 2022

The availability of audio data on sound sharing platforms such as Freesound gives users access to large amounts of annotated audio. Utilising such data for training is becoming increasingly popular, but the problem of label noise that is often prevalent in such datasets requires further investigation. This paper introduces ARCA23K, an Automatically Retrieved and Curated Audio dataset comprised of over 23000 labelled Freesound clips. Unlike past datasets such as FSDKaggle2018 and FSDnoisy18K, ARCA23K facilitates the study of label noise in a more controlled manner. We describe the entire process of creating the dataset such that it is fully reproducible, meaning researchers can extend our work with little effort. We show that the majority of labelling errors in ARCA23K are due to out-of-vocabulary audio clips, and we refer to this type of label noise as open-set label noise. Experiments are carried out in which we study the impact of label noise in terms of classification performance and representation learning.