OpenRaiser/Intern-Atlas huggingface dataset:
Efficient parallel 3D computation of the compressible Euler equations with an invariant-domain preserving second-order finite-element scheme
Venue: arXiv cs.MS 2021
Year: 2021

We discuss the efficient implementation of a high-performance second-order collocation-type finite-element scheme for solving the compressible Euler equations of gas dynamics on unstructured meshes. The solver is based on the convex limiting technique introduced by Guermond et al. (SIAM J. Sci. Comput. 40, A3211-A3239, 2018). As such it is invariant-domain preserving, i.e., the solver maintains important physical invariants and is guaranteed to be stable without the use of ad-hoc tuning parameters. This stability comes at the expense of a significantly more involved algorithmic structure that renders conventional high-performance discretizations challenging. We develop an algorithmic design that allows SIMD vectorization of the compute kernel, identify the main ingredients for a good node-level performance, and report excellent weak and strong scaling of a hybrid thread/MPI parallelization.
Robustifying the Deployment of tinyML Models for Autonomous mini-vehicles
Venue: arXiv cs.CV 2021
Year: 2021

Standard-size autonomous navigation vehicles have rapidly improved thanks to the breakthroughs of deep learning. However, scaling autonomous driving to low-power systems deployed on dynamic environments poses several challenges that prevent their adoption. To address them, we propose a closed-loop learning flow for autonomous driving mini-vehicles that includes the target environment in-the-loop. We leverage a family of compact and high-throughput tinyCNNs to control the mini-vehicle, which learn in the target environment by imitating a computer vision algorithm, i.e., the expert. Thus, the tinyCNNs, having only access to an on-board fast-rate linear camera, gain robustness to lighting conditions and improve over time. Further, we leverage GAP8, a parallel ultra-low-power RISC-V SoC, to meet the inference requirements. When running the family of CNNs, our GAP8's solution outperforms any other implementation on the STM32L4 and NXP k64f (Cortex-M4), reducing the latency by over 13x and the energy consummation by 92%.
Multi-Task Variational Information Bottleneck
Venue: arXiv cs.LG 2021
Year: 2021

Multi-task learning (MTL) is an important subject in machine learning and artificial intelligence. Its applications to computer vision, signal processing, and speech recognition are ubiquitous. Although this subject has attracted considerable attention recently, the performance and robustness of the existing models to different tasks have not been well balanced. This article proposes an MTL model based on the architecture of the variational information bottleneck (VIB), which can provide a more effective latent representation of the input features for the downstream tasks. Extensive observations on three public data sets under adversarial attacks show that the proposed model is competitive to the state-of-the-art algorithms concerning the prediction accuracy. Experimental results suggest that combining the VIB and the task-dependent uncertainties is a very effective way to abstract valid information from the input features for accomplishing multiple tasks.
A Truly Self-Sovereign Identity System
Venue: arXiv cs.CR 2021
Year: 2021

Existing digital identity management systems fail to deliver the desirable properties of control by the users of their own identity data, credibility of disclosed identity data, and network-level anonymity. The recently proposed Self-Sovereign Identity (SSI) approach promises to give users these properties. However, we argue that without addressing privacy at the network level, SSI systems cannot deliver on this promise. In this paper we present the design and analysis of our solution TCID, created in collaboration with the Dutch government. TCID is a system consisting of a set of components that together satisfy seven functional requirements to guarantee the desirable system properties. We show that the latency incurred by network-level anonymization in TCID is significantly larger than that of identity data disclosure protocols but is still low enough for practical situations. We conclude that current research on SSI is too narrowly focused on these data disclosure protocols.
Adversarial Example Games
Venue: arXiv cs.LG 2021
Year: 2021

The existence of adversarial examples capable of fooling trained neural network classifiers calls for a much better understanding of possible attacks to guide the development of safeguards against them. This includes attack methods in the challenging non-interactive blackbox setting, where adversarial attacks are generated without any access, including queries, to the target model. Prior attacks in this setting have relied mainly on algorithmic innovations derived from empirical observations (e.g., that momentum helps), lacking principled transferability guarantees. In this work, we provide a theoretical foundation for crafting transferable adversarial examples to entire hypothesis classes. We introduce Adversarial Example Games (AEG), a framework that models the crafting of adversarial examples as a min-max game between a generator of attacks and a classifier. AEG provides a new way to design adversarial examples by adversarially training a generator and a classifier from a given hypothesis class (e.g., architecture). We prove that this game has an equilibrium, and that the optimal generator is able to craft adversarial examples that can attack any classifier from the corresponding hypothesis class. We demonstrate the efficacy of AEG on the MNIST and CIFAR-10 datasets, outperforming prior state-of-the-art approaches with an average relative improvement of $29.9\%$ and $47.2\%$ against undefended and robust models (Table 2 & 3) respectively.
Cross-Layer Deanonymization Methods in the Lightning Protocol
Venue: arXiv cs.CR 2021
Year: 2021

Bitcoin (BTC) pseudonyms (layer 1) can effectively be deanonymized using heuristic clustering techniques. However, while performing transactions off-chain (layer 2) in the Lightning Network (LN) seems to enhance privacy, a systematic analysis of the anonymity and privacy leakages due to the interaction between the two layers is missing. We present clustering heuristics that group BTC addresses, based on their interaction with the LN, as well as LN nodes, based on shared naming and hosting information. We also present linking heuristics that link 45.97% of all LN nodes to 29.61% BTC addresses interacting with the LN. These links allow us to attribute information (e.g., aliases, IP addresses) to 21.19% of the BTC addresses contributing to their deanonymization. Further, these deanonymization results suggest that the security and privacy of LN payments are weaker than commonly believed, with LN users being at the mercy of as few as five actors that control 36 nodes and over 33% of the total capacity. Overall, this is the first paper to present a method for linking LN nodes with BTC addresses across layers and to discuss privacy and security implications.
Dropout as a Regularizer of Interaction Effects
Venue: arXiv cs.LG 2021
Year: 2021

We examine Dropout through the perspective of interactions. This view provides a symmetry to explain Dropout: given $N$ variables, there are ${N \choose k}$ possible sets of $k$ variables to form an interaction (i.e. $\mathcal{O}(N^k)$); conversely, the probability an interaction of $k$ variables survives Dropout at rate $p$ is $(1-p)^k$ (decaying with $k$). These rates effectively cancel, and so Dropout regularizes against higher-order interactions. We prove this perspective analytically and empirically. This perspective of Dropout as a regularizer against interaction effects has several practical implications: (1) higher Dropout rates should be used when we need stronger regularization against spurious high-order interactions, (2) caution should be exercised when interpreting Dropout-based explanations and uncertainty measures, and (3) networks trained with Input Dropout are biased estimators. We also compare Dropout to other regularizers and find that it is difficult to obtain the same selective pressure against high-order interactions.
Learning to search efficiently for causally near-optimal treatments
Venue: arXiv cs.LG 2021
Year: 2021

Finding an effective medical treatment often requires a search by trial and error. Making this search more efficient by minimizing the number of unnecessary trials could lower both costs and patient suffering. We formalize this problem as learning a policy for finding a near-optimal treatment in a minimum number of trials using a causal inference framework. We give a model-based dynamic programming algorithm which learns from observational data while being robust to unmeasured confounding. To reduce time complexity, we suggest a greedy algorithm which bounds the near-optimality constraint. The methods are evaluated on synthetic and real-world healthcare data and compared to model-free reinforcement learning. We find that our methods compare favorably to the model-free baseline while offering a more transparent trade-off between search time and treatment efficacy.
Proofs of Useless Work -- Positive and Negative Results for Wasteless Mining Systems
Venue: arXiv cs.CR 2021
Year: 2021

Many blockchain systems today, including Bitcoin, rely on Proof of Work (PoW). Proof of work is crucial to the liveness and security of cryptocurrencies. The assumption when using PoW is that a lot of trial and error is required on average before a valid block is generated. One of the main concerns raised with regard to this kind of system is the inherent need to "waste" energy on "meaningless" problems. In fact, the Bitcoin system is believed to consume more electricity than several small countries. In this work we formally define three properties that are necessary for wasteless PoW systems: (1) solve "meaningful" problems (2) solve them efficiently and (3) be secure against double-spend attacks. These properties aim to create an open market for problem-solving, in which miners produce solutions to problems in the most efficient way (wasteless). The security of the system stems from the economical incentive created by the demand for solutions to these problems. We analyze these properties, and deduce constraints that must apply to such PoW systems. In our main result, we conclude that under realistic assumptions, the set of allowed problems must be preimage resistant functions in order to keep the system secure and efficient.
Reinforcement Learning and its Connections with Neuroscience and Psychology
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning methods have recently been very successful at performing complex sequential tasks like playing Atari games, Go and Poker. These algorithms have outperformed humans in several tasks by learning from scratch, using only scalar rewards obtained through interaction with their environment. While there certainly has been considerable independent innovation to produce such results, many core ideas in reinforcement learning are inspired by phenomena in animal learning, psychology and neuroscience. In this paper, we comprehensively review a large number of findings in both neuroscience and psychology that evidence reinforcement learning as a promising candidate for modeling learning and decision making in the brain. In doing so, we construct a mapping between various classes of modern RL algorithms and specific findings in both neurophysiological and behavioral literature. We then discuss the implications of this observed relationship between RL, neuroscience and psychology and its role in advancing research in both AI and brain science.
Entanglement-Assisted Quantum Error Correcting Codes From RS Codes and BCH Codes with Extension Degree 2
Venue: arXiv cs.IT 2021
Year: 2021

Entanglement-assisted quantum error correcting codes (EAQECCs) constructed from Reed-Solomon codes and BCH codes are considered in this work. It is provided a complete and explicit formula for the parameters of EAQECCs coming from any Reed-Solomon code, for the Hermitian metric, and from any BCH code with extension degree $2$ and consecutive cyclotomic cosets, for both the Euclidean and the Hermitian metric. The main task in this work is the computation of a completely general formula for $c$, the minimum number of required maximally entangled quantum states.
Learning to Segment from Scribbles using Multi-scale Adversarial Attention Gates
Venue: arXiv cs.CV 2021
Year: 2021

Large, fine-grained image segmentation datasets, annotated at pixel-level, are difficult to obtain, particularly in medical imaging, where annotations also require expert knowledge. Weakly-supervised learning can train models by relying on weaker forms of annotation, such as scribbles. Here, we learn to segment using scribble annotations in an adversarial game. With unpaired segmentation masks, we train a multi-scale GAN to generate realistic segmentation masks at multiple resolutions, while we use scribbles to learn their correct position in the image. Central to the model's success is a novel attention gating mechanism, which we condition with adversarial signals to act as a shape prior, resulting in better object localization at multiple scales. Subject to adversarial conditioning, the segmentor learns attention maps that are semantic, suppress the noisy activations outside the objects, and reduce the vanishing gradient problem in the deeper layers of the segmentor. We evaluated our model on several medical (ACDC, LVSC, CHAOS) and non-medical (PPSS) datasets, and we report performance levels matching those achieved by models trained with fully annotated segmentation masks. We also demonstrate extensions in a variety of settings: semi-supervised learning; combining multiple scribble sources (a crowdsourcing scenario) and multi-task learning (combining scribble and mask supervision). We release expert-made scribble annotations for the ACDC dataset, and the code used for the experiments, at https://vios-s.github.io/multiscale-adversarial-attention-gates
Epileptic Seizures Detection Using Deep Learning Techniques: A Review
Venue: arXiv cs.LG 2021
Year: 2021

A variety of screening approaches have been proposed to diagnose epileptic seizures, using electroencephalography (EEG) and magnetic resonance imaging (MRI) modalities. Artificial intelligence encompasses a variety of areas, and one of its branches is deep learning (DL). Before the rise of DL, conventional machine learning algorithms involving feature extraction were performed. This limited their performance to the ability of those handcrafting the features. However, in DL, the extraction of features and classification are entirely automated. The advent of these techniques in many areas of medicine, such as in the diagnosis of epileptic seizures, has made significant advances. In this study, a comprehensive overview of works focused on automated epileptic seizure detection using DL techniques and neuroimaging modalities is presented. Various methods proposed to diagnose epileptic seizures automatically using EEG and MRI modalities are described. In addition, rehabilitation systems developed for epileptic seizures using DL have been analyzed, and a summary is provided. The rehabilitation tools include cloud computing techniques and hardware required for implementation of DL algorithms. The important challenges in accurate detection of automated epileptic seizures using DL with EEG and MRI modalities are discussed. The advantages and limitations in employing DL-based techniques for epileptic seizures diagnosis are presented. Finally, the most promising DL models proposed and possible future works on automated epileptic seizure detection are delineated.
Improved bounds for noisy group testing with constant tests per item
Venue: arXiv cs.IT 2021
Year: 2021

The group testing problem is concerned with identifying a small set of infected individuals in a large population. At our disposal is a testing procedure that allows us to test several individuals together. In an idealized setting, a test is positive if and only if at least one infected individual is included and negative otherwise. Significant progress was made in recent years towards understanding the information-theoretic and algorithmic properties in this noiseless setting. In this paper, we consider a noisy variant of group testing where test results are flipped with certain probability, including the realistic scenario where sensitivity and specificity can take arbitrary values. Using a test design where each individual is assigned to a fixed number of tests, we derive explicit algorithmic bounds for two commonly considered inference algorithms and thereby naturally extend the results of Scarlett \& Cevher (2016) and Scarlett \& Johnson (2020). We provide improved performance guarantees for the efficient algorithms in these noisy group testing models -- indeed, for a large set of parameter choices the bounds provided in the paper are the strongest currently proved.
Maximizing Cohesion and Separation in Graph Representation Learning: A Distance-aware Negative Sampling Approach
Venue: arXiv cs.LG 2021
Year: 2021

The objective of unsupervised graph representation learning (GRL) is to learn a low-dimensional space of node embeddings that reflect the structure of a given unlabeled graph. Existing algorithms for this task rely on negative sampling objectives that maximize the similarity in node embeddings at nearby nodes (referred to as "cohesion") by maintaining positive and negative corpus of node pairs. While positive samples are drawn from node pairs that co-occur in short random walks, conventional approaches construct negative corpus by uniformly sampling random pairs, thus ignoring valuable information about structural dissimilarity among distant node pairs (referred to as "separation"). In this paper, we present a novel Distance-aware Negative Sampling (DNS) which maximizes the separation of distant node-pairs while maximizing cohesion at nearby node-pairs by setting the negative sampling probability proportional to the pair-wise shortest distances. Our approach can be used in conjunction with any GRL algorithm and we demonstrate the efficacy of our approach over baseline negative sampling methods over downstream node classification tasks on a number of benchmark datasets and GRL algorithms. All our codes and datasets are available at https://github.com/Distance-awareNS/DNS/.
Few-Shot Semantic Segmentation Augmented with Image-Level Weak Annotations
Venue: arXiv cs.CV 2021
Year: 2021

Despite the great progress made by deep neural networks in the semantic segmentation task, traditional neural-networkbased methods typically suffer from a shortage of large amounts of pixel-level annotations. Recent progress in fewshot semantic segmentation tackles the issue by only a few pixel-level annotated examples. However, these few-shot approaches cannot easily be applied to multi-way or weak annotation settings. In this paper, we advance the few-shot segmentation paradigm towards a scenario where image-level annotations are available to help the training process of a few pixel-level annotations. Our key idea is to learn a better prototype representation of the class by fusing the knowledge from the image-level labeled data. Specifically, we propose a new framework, called PAIA, to learn the class prototype representation in a metric space by integrating image-level annotations. Furthermore, by considering the uncertainty of pseudo-masks, a distilled soft masked average pooling strategy is designed to handle distractions in image-level annotations. Extensive empirical results on two datasets show superior performance of PAIA.
Failure-Resilient Coverage Maximization with Multiple Robots
Venue: arXiv cs.RO 2021
Year: 2021

The task of maximizing coverage using multiple robots has several applications such as surveillance, exploration, and environmental monitoring. A major challenge of deploying such multi-robot systems in a practical scenario is to ensure resilience against robot failures. A recent work introduced the Resilient Coverage Maximization (RCM) problem where the goal is to maximize a submodular coverage utility when the robots are subject to adversarial attacks or failures. The RCM problem is known to be NP-hard. In this paper, we propose two approximation algorithms for the RCM problem, namely, the Ordered Greedy (OrG) and the Local Search (LS) algorithm. Both algorithms empirically outperform the state-of-the-art solution in terms of accuracy and running time. To demonstrate the effectiveness of our proposed solution, we empirically compare our proposed algorithms with the existing solution and a brute force optimal algorithm. We also perform a case study on the persistent monitoring problem to show the applicability of our proposed algorithms in a practical setting.
When Text Simplification Is Not Enough: Could a Graph-Based Visualization Facilitate Consumers' Comprehension of Dietary Supplement Information?
Venue: arXiv cs.CY 2021
Year: 2021

Dietary supplements are widely used but not always safe. With the rapid development of the Internet, consumers usually seek health information including dietary supplement information online. To help consumers access quality online dietary supplement information, we have identified trustworthy dietary supplement information sources and built an evidence-based knowledge base of dietary supplement information-the integrated DIetary Supplement Knowledge base (iDISK) that integrates and standardizes dietary supplement related information across these different sources. However, as information in iDISK was collected from scientific sources, the complex medical jargon is a barrier for consumers' comprehension. To assess how different approaches to simplify and represent dietary supplement information from iDISK will affect lay consumers' comprehension, using a crowdsourcing platform, we recruited participants to read dietary supplement information in four different representations from iDISK: original text, syntactic and lexical text simplification, manual text simplification, and a graph-based visualization. We then assessed how the different simplification and representation strategies affected consumers' comprehension of dietary supplement information in terms of accuracy and response time to a set of comprehension questions. With responses from 690 qualified participants, our experiments confirmed that the manual approach had the best performance for both accuracy and response time to the comprehension questions, while the graph-based approach ranked the second outperforming other representations. In some cases, the graph-based representation outperformed the manual approach in terms of response time. A hybrid approach that combines text and graph-based representations might be needed to accommodate consumers' different information needs and information seeking behavior.
Explaining Fast Improvement in Online Imitation Learning
Venue: arXiv cs.LG 2021
Year: 2021

Online imitation learning (IL) is an algorithmic framework that leverages interactions with expert policies for efficient policy optimization. Here policies are optimized by performing online learning on a sequence of loss functions that encourage the learner to mimic expert actions, and if the online learning has no regret, the agent can provably learn an expert-like policy. Online IL has demonstrated empirical successes in many applications and interestingly, its policy improvement speed observed in practice is usually much faster than existing theory suggests. In this work, we provide an explanation of this phenomenon. Let $ξ$ denote the policy class bias and assume the online IL loss functions are convex, smooth, and non-negative. We prove that, after $N$ rounds of online IL with stochastic feedback, the policy improves in $\tilde{O}(1/N + \sqrt{ξ/N})$ in both expectation and high probability. In other words, we show that adopting a sufficiently expressive policy class in online IL has two benefits: both the policy improvement speed increases and the performance bias decreases.