OpenRaiser/Intern-Atlas huggingface dataset:
Few-Shot Few-Shot Learning and the role of Spatial Attention
Venue: arXiv cs.CV 2020
Year: 2020

Few-shot learning is often motivated by the ability of humans to learn new tasks from few examples. However, standard few-shot classification benchmarks assume that the representation is learned on a limited amount of base class data, ignoring the amount of prior knowledge that a human may have accumulated before learning new tasks. At the same time, even if a powerful representation is available, it may happen in some domain that base class data are limited or non-existent. This motivates us to study a problem where the representation is obtained from a classifier pre-trained on a large-scale dataset of a different domain, assuming no access to its training process, while the base class data are limited to few examples per class and their role is to adapt the representation to the domain at hand rather than learn from scratch. We adapt the representation in two stages, namely on the few base class data if available and on the even fewer data of new tasks. In doing so, we obtain from the pre-trained classifier a spatial attention map that allows focusing on objects and suppressing background clutter. This is important in the new problem, because when base class data are few, the network cannot learn where to focus implicitly. We also show that a pre-trained network may be easily adapted to novel classes, without meta-learning.
Machine Learning for Motor Learning: EEG-based Continuous Assessment of Cognitive Engagement for Adaptive Rehabilitation Robots
Venue: arXiv cs.RO 2020
Year: 2020

Although cognitive engagement (CE) is crucial for motor learning, it remains underutilized in rehabilitation robots, partly because its assessment currently relies on subjective and gross measurements taken intermittently. Here, we propose an end-to-end computational framework that assesses CE in real-time, using electroencephalography (EEG) signals as objective measurements. The framework consists of i) a deep convolutional neural network (CNN) that extracts task-discriminative spatiotemporal EEG to predict the level of CE for two classes -- cognitively engaged vs. disengaged; and ii) a novel sliding window method that predicts continuous levels of CE in real-time. We evaluated our framework on 8 subjects using an in-house Go/No-Go experiment that adapted its gameplay parameters to induce cognitive fatigue. The proposed CNN had an average leave-one-out accuracy of 88.13\%. The CE prediction correlated well with a commonly used behavioral metric based on self-reports taken every 5 minutes ($ρ$=0.93). Our results objectify CE in real-time and pave the way for using CE as a rehabilitation parameter for tailoring robotic therapy to each patient's needs and skills.
Connecting MapReduce Computations to Realistic Machine Models
Venue: arXiv cs.DS 2020
Year: 2020

We explain how the popular, highly abstract MapReduce model of parallel computation (MRC) can be rooted in reality by explaining how it can be simulated on realistic distributed-memory parallel machine models like BSP. We first refine the model (MRC$^+$) to include parameters for total work $w$, bottleneck work $\hat{w}$, data volume $m$, and maximum object sizes $\hat{m}$. We then show matching upper and lower bounds for executing a MapReduce calculation on the distributed-memory machine -- $Θ(w/p+\hat{w}+\log p)$ work and $Θ(m/p+\hat{m}+\log p)$ bottleneck communication volume using $p$ processors.
Active Learning-based Classification in Automated Connected Vehicles
Venue: arXiv cs.NI 2020
Year: 2020

Machine learning has emerged as a promising paradigm for enabling connected, automated vehicles to autonomously cruise the streets and react to unexpected situations. A key challenge, however, is to collect and select real-time and reliable information for the correct classification of unexpected, and often rare, situations that may happen on the road. Indeed, the data generated by vehicles, or received from neighboring vehicles, may be affected by errors or have different levels of resolution and freshness. To tackle this challenge, we propose an active learning framework that, leveraging the information collected through onboard sensors as well as received from other vehicles, effectively deals with scarce and noisy data. In particular, given the available information, our solution selects the data to add to the training set by trading off between two essential features, namely, quality and diversity. The results, obtained using real-world data sets, show that the proposed method significantly outperforms state-of-the-art solutions, providing high classification accuracy at the cost of a limited bandwidth requirement for the data exchange between vehicles.
Performance Analysis of Quantized Uplink Massive MIMO-OFDM With Oversampling Under Adjacent Channel Interference
Venue: arXiv cs.IT 2020
Year: 2020

Massive multiple-input multiple-output (MIMO) systems have attracted much attention lately due to the many advantages they provide over single-antenna systems. Owing to the many antennas, low-cost implementation and low power consumption per antenna are desired. To that end, massive MIMO structures with low-resolution analog-to-digital converters (ADC) have been investigated in many studies. However, the effect of a strong interferer in the adjacent band on quantized massive MIMO systems have not been examined yet. In this study, we analyze the performance of uplink massive MIMO with low-resolution ADCs under frequency selective fading with orthogonal frequency division multiplexing in the perfect and imperfect receiver channel state information cases. We derive analytical expressions for the bit error rate and ergodic capacity. We show that the interfering band can be suppressed by increasing the number of antennas or the oversampling rate when a zero-forcing receiver is employed.
How incomputable is Kolmogorov complexity?
Venue: arXiv cs.IT 2020
Year: 2020

Kolmogorov complexity is the length of the ultimately compressed version of a file (that is, anything which can be put in a computer). Formally, it is the length of a shortest program from which the file can be reconstructed. We discuss the incomputabilty of Kolmogorov complexity, which formal loopholes this leaves us, recent approaches to compute or approximate Kolmogorov complexity, which approaches are problematic and which approaches are viable.
A Lagrangian Approach to Information Propagation in Graph Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

In many real world applications, data are characterized by a complex structure, that can be naturally encoded as a graph. In the last years, the popularity of deep learning techniques has renewed the interest in neural models able to process complex patterns. In particular, inspired by the Graph Neural Network (GNN) model, different architectures have been proposed to extend the original GNN scheme. GNNs exploit a set of state variables, each assigned to a graph node, and a diffusion mechanism of the states among neighbor nodes, to implement an iterative procedure to compute the fixed point of the (learnable) state transition function. In this paper, we propose a novel approach to the state computation and the learning algorithm for GNNs, based on a constraint optimisation task solved in the Lagrangian framework. The state convergence procedure is implicitly expressed by the constraint satisfaction mechanism and does not require a separate iterative phase for each epoch of the learning procedure. In fact, the computational structure is based on the search for saddle points of the Lagrangian in the adjoint space composed of weights, neural outputs (node states), and Lagrange multipliers. The proposed approach is compared experimentally with other popular models for processing graphs.
Dynamics of Cycles in Polyhedra I: The Isolation Lemma
Venue: arXiv cs.DS 2020
Year: 2020

A cycle $C$ of a graph $G$ is \emph{isolating} if every component of $G-V(C)$ is a single vertex. We show that isolating cycles in polyhedral graphs can be extended to larger ones: every isolating cycle $C$ of length $6 \leq |E(C)| < \left \lfloor \frac{2}{3}(|V(G)|+4) \right \rfloor$ implies an isolating cycle $C'$ of larger length that contains $V(C)$. By "hopping" iteratively to such larger cycles, we obtain a powerful and very general inductive motor for proving long cycles and computing them (we will give an algorithm with quadratic running time). This is the first step towards the so far elusive quest of finding a universal induction that captures longest cycles of polyhedral graph classes. Our motor provides also a method to prove linear lower bounds on the length of Tutte cycles, as $C'$ will be a Tutte cycle of $G$ if $C$ is. We prove in addition that $|E(C')| \leq |E(C)|+3$ if $G$ contains no face of size five, which gives a new tool for results about cycle spectra, and provides evidence that faces of size five may obstruct long cycles in many graph classes. We test our motor on the following conjecture about essentially 4-connected graphs. A planar graph is \emph{essentially $4$-connected} if it is 3-connected and every of its 3-separators is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4-connected planar graph $G$ on $n$ vertices contains a cycle of length at least $\frac{2}{5}(n+2)$, and this result has recently been improved multiple times, culminating in the lower bound $\frac{5}{8}(n+2)$. However, the currently best known upper bound is given by an infinite family of such graphs in which no graph $G$ contains a cycle that is longer than $\left \lfloor \frac{2}{3}(n+4) \right \rfloor$; this upper bound is still unmatched. Using isolating cycles, we improve the lower bound to match the upper. All our results are tight.
In-materio neuromimetic devices: Dynamics, information processing and pattern recognition
Venue: arXiv cs.ET 2020
Year: 2020

The story of information processing is a story of great success. Todays' microprocessors are devices of unprecedented complexity and MOSFET transistors are considered as the most widely produced artifact in the history of mankind. The current miniaturization of electronic circuits is pushed almost to the physical limit and begins to suffer from various parasitic effects. These facts stimulate intense research on neuromimetic devices. This feature article is devoted to various in materio implementation of neuromimetic processes, including neuronal dynamics, synaptic plasticity, and higher-level signal and information processing, along with more sophisticated implementations, including signal processing, speech recognition and data security. Due to vast number of papers in the field, only a subjective selection of topics is presented in this review.
Fuzzy Simultaneous Congruences
Venue: arXiv cs.DM 2020
Year: 2020

We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer $s$ that is specified by $n$ fixed remainders modulo integer divisors $a_1,\dots,a_n$ we consider remainder intervals $R_1,\dots,R_n$ such that $s$ is feasible if and only if $s$ is congruent to $r_i$ modulo $a_i$ for some remainder $r_i$ in interval $R_i$ for all $i$. This problem is a special case of a 2-stage integer program with only two variables per constraint which is is closely related to directed Diophantine approximation as well as the mixing set problem. We give a hardness result showing that the problem is NP-hard in general. By investigating the case of harmonic divisors, i.e. $a_{i+1}/a_i$ is an integer for all $i<n$, which was heavily studied for the mixing set problem as well, we also answer a recent algorithmic question from the field of real-time systems. We present an algorithm to decide the feasibility of an instance in time $\mathcal{O}(n^2)$ and we show that if it exists even the smallest feasible solution can be computed in strongly polynomial time $\mathcal{O}(n^3)$.
ConSORT: Context- and Flow-Sensitive Ownership Refinement Types for Imperative Programs
Venue: arXiv cs.PL 2020
Year: 2020

We present ConSORT, a type system for safety verification in the presence of mutability and aliasing. Mutability requires strong updates to model changing invariants during program execution, but aliasing between pointers makes it difficult to determine which invariants must be updated in response to mutation. Our type system addresses this difficulty with a novel combination of refinement types and fractional ownership types. Fractional ownership types provide flow-sensitive and precise aliasing information for reference variables. ConSORT interprets this ownership information to soundly handle strong updates of potentially aliased references. We have proved ConSORT sound and implemented a prototype, fully automated inference tool. We evaluated our tool and found it verifies non-trivial programs including data structure implementations.
Probabilistically Faulty Searching on a Half-Line
Venue: arXiv cs.DS 2020
Year: 2020

We study $p$-Faulty Search, a variant of the classic cow-path optimization problem, where a unit speed robot searches the half-line (or $1$-ray) for a hidden item. The searcher is probabilistically faulty, and detection of the item with each visitation is an independent Bernoulli trial whose probability of success $p$ is known. The objective is to minimize the worst case expected detection time, relative to the distance of the hidden item to the origin. A variation of the same problem was first proposed by Gal in 1980. Then in 2003, Alpern and Gal [The Theory of Search Games and Rendezvous] proposed a so-called monotone solution for searching the line ($2$-rays); that is, a trajectory in which the newly searched space increases monotonically in each ray and in each iteration. Moreover, they conjectured that an optimal trajectory for the $2$-rays problem must be monotone. We disprove this conjecture when the search domain is the half-line ($1$-ray). We provide a lower bound for all monotone algorithms, which we also match with an upper bound. Our main contribution is the design and analysis of a sequence of refined search strategies, outside the family of monotone algorithms, which we call $t$-sub-monotone algorithms. Such algorithms induce performance that is strictly decreasing with $t$, and for all $p \in (0,1)$. The value of $t$ quantifies, in a certain sense, how much our algorithms deviate from being monotone, demonstrating that monotone algorithms are sub-optimal when searching the half-line.
Incremental Nonlinear Fault-Tolerant Control of a Quadrotor with Complete Loss of Two Opposing Rotors
Venue: arXiv cs.RO 2020
Year: 2020

In order to further expand the flight envelope of quadrotors under actuator failures, we design a nonlinear sensor-based fault-tolerant controller to stabilize a quadrotor with failure of two opposing rotors in the high-speed flight condition (> 8m/s). The incremental nonlinear dynamic inversion (INDI) approach which excels in handling model uncertainties is adopted to compensate for the significant unknown aerodynamic effects. The internal dynamics of such an underactuated system have been analyzed, and subsequently stabilized by re-defining the control output. The proposed method can be generalized to control a quadrotor under single-rotor-failure and nominal conditions. For validation, flight tests have been carried out in a large-scale open jet wind tunnel. The position of a damaged quadrotor can be controlled in the presence of significant wind disturbances. A linear quadratic regulator (LQR) approach from the literature has been compared to demonstrate the advantages of the proposed nonlinear method in the windy and high-speed flight condition.
Lake Ice Monitoring with Webcams and Crowd-Sourced Images
Venue: arXiv cs.CV 2020
Year: 2020

Lake ice is a strong climate indicator and has been recognised as part of the Essential Climate Variables (ECV) by the Global Climate Observing System (GCOS). The dynamics of freezing and thawing, and possible shifts of freezing patterns over time, can help in understanding the local and global climate systems. One way to acquire the spatio-temporal information about lake ice formation, independent of clouds, is to analyse webcam images. This paper intends to move towards a universal model for monitoring lake ice with freely available webcam data. We demonstrate good performance, including the ability to generalise across different winters and different lakes, with a state-of-the-art Convolutional Neural Network (CNN) model for semantic image segmentation, Deeplab v3+. Moreover, we design a variant of that model, termed Deep-U-Lab, which predicts sharper, more correct segmentation boundaries. We have tested the model's ability to generalise with data from multiple camera views and two different winters. On average, it achieves intersection-over-union (IoU) values of ~71% across different cameras and ~69% across different winters, greatly outperforming prior work. Going even further, we show that the model even achieves 60% IoU on arbitrary images scraped from photo-sharing web sites. As part of the work, we introduce a new benchmark dataset of webcam images, Photi-LakeIce, from multiple cameras and two different winters, along with pixel-wise ground truth annotations.
Generating Automatic Curricula via Self-Supervised Active Domain Randomization
Venue: arXiv cs.LG 2020
Year: 2020

Goal-directed Reinforcement Learning (RL) traditionally considers an agent interacting with an environment, prescribing a real-valued reward to an agent proportional to the completion of some goal. Goal-directed RL has seen large gains in sample efficiency, due to the ease of reusing or generating new experience by proposing goals. One approach,self-play, allows an agent to "play" against itself by alternatively setting and accomplishing goals, creating a learned curriculum through which an agent can learn to accomplish progressively more difficult goals. However, self-play has been limited to goal curriculum learning or learning progressively harder goals within a single environment. Recent work on robotic agents has shown that varying the environment during training, for example with domain randomization, leads to more robust transfer. As a result, we extend the self-play framework to jointly learn a goal and environment curriculum, leading to an approach that learns the most fruitful domain randomization strategy with self-play. Our method, Self-Supervised Active Domain Randomization(SS-ADR), generates a coupled goal-task curriculum, where agents learn through progressively more difficult tasks and environment variations. By encouraging the agent to try tasks that are just outside of its current capabilities, SS-ADR builds a domain randomization curriculum that enables state-of-the-art results on varioussim2real transfer tasks. Our results show that a curriculum of co-evolving the environment difficulty together with the difficulty of goals set in each environment provides practical benefits in the goal-directed tasks tested.
PTAuth: Temporal Memory Safety via Robust Points-to Authentication
Venue: arXiv cs.CR 2020
Year: 2020

Temporal memory corruptions are commonly exploited software vulnerabilities that can lead to powerful attacks. Despite significant progress made by decades of research on mitigation techniques, existing countermeasures fall short due to either limited coverage or overly high overhead. Furthermore, they require external mechanisms (e.g., spatial memory safety) to protect their metadata. Otherwise, their protection can be bypassed or disabled. To address these limitations, we present robust points-to authentication, a novel runtime scheme for detecting all kinds of temporal memory corruptions. We built a prototype system, called PTAuth, that realizes this scheme on ARM architectures. PTAuth contains a customized compiler for code analysis and instrumentation and a runtime library for performing the points-to authentication as a protected program runs. PTAuth leverages the Pointer Authentication Code (PAC) feature, provided by the ARMv8.3 and later CPUs, which serves as a simple hardware-based encryption primitive. PTAuth uses minimal in-memory metadata and protects its metadata without requiring spatial memory safety. We report our evaluation of PTAuth in terms of security, robustness and performance using 150 vulnerable programs from Juliet test suite and the SPEC CPU2006 benchmarks. PTAuth detects all three categories of heap-based temporal memory corruptions, generates zero false alerts, and slows down program execution by 26% (this number was measured based on software-emulated PAC; it is expected to decrease to 20% when using hardware-based PAC). We also show that PTAuth incurs 2% memory overhead thanks to the efficient use of metadata.
Personalized Federated Learning: A Meta-Learning Approach
Venue: arXiv cs.LG 2020
Year: 2020

In Federated Learning, we aim to train models across multiple computing units (users), while users can only communicate with a common central server, without exchanging their data samples. This mechanism exploits the computational power of all users and allows users to obtain a richer model as their models are trained over a larger set of data points. However, this scheme only develops a common output for all the users, and, therefore, it does not adapt the model to each user. This is an important missing feature, especially given the heterogeneity of the underlying data distribution for various users. In this paper, we study a personalized variant of the federated learning in which our goal is to find an initial shared model that current or new users can easily adapt to their local dataset by performing one or a few steps of gradient descent with respect to their own data. This approach keeps all the benefits of the federated learning architecture, and, by structure, leads to a more personalized model for each user. We show this problem can be studied within the Model-Agnostic Meta-Learning (MAML) framework. Inspired by this connection, we study a personalized variant of the well-known Federated Averaging algorithm and evaluate its performance in terms of gradient norm for non-convex loss functions. Further, we characterize how this performance is affected by the closeness of underlying distributions of user data, measured in terms of distribution distances such as Total Variation and 1-Wasserstein metric.
Familiarization tours for first-time users of highly automated cars: Comparing the effects of virtual environments with different levels of interaction fidelity
Venue: arXiv cs.HC 2020
Year: 2020

Research in aviation and driving has highlighted the importance of training as an effective approach to reduce the costs associated with the supervisory role of the human in automated systems. However, only a few studies have investigated the effect of pre-trip familiarization tours on highly automated driving. In the present study, a driving simulator experiment compared the effectiveness of four familiarization groups, control, video, low fidelity virtual reality (VR), and high fidelity VR on automation trust and driving performance in several critical and non-critical transition tasks. The results revealed the positive impact of familiarization tours on trust, takeover, and handback performance at the first time of measurement. Takeover quality only improved when practice was presented in high-fidelity VR. After three times of exposure to transition requests, trust and transition performance of all groups converged to those of the high fidelity VR group, demonstrating that: a) experiencing automation failures during the training may reduce costs associated with first failures in highly automated driving; b) the VR tour with high level of interaction fidelity is superior to other types of familiarization tour, and c) uneducated and less-educated drivers learn about automation by experiencing it. Knowledge resulting from this research could help develop cost-effective familiarization tours for highly automated vehicles in dealerships and car rental centers.