OpenRaiser/Intern-Atlas huggingface dataset:
Learning from Incomplete Features by Simultaneous Training of Neural Networks and Sparse Coding
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, the problem of training a classifier on a dataset with incomplete features is addressed. We assume that different subsets of features (random or structured) are available at each data instance. This situation typically occurs in the applications when not all the features are collected for every data sample. A new supervised learning method is developed to train a general classifier, such as a logistic regression or a deep neural network, using only a subset of features per sample, while assuming sparse representations of data vectors on an unknown dictionary. Sufficient conditions are identified, such that, if it is possible to train a classifier on incomplete observations so that their reconstructions are well separated by a hyperplane, then the same classifier also correctly separates the original (unobserved) data samples. Extensive simulation results on synthetic and well-known datasets are presented that validate our theoretical findings and demonstrate the effectiveness of the proposed method compared to traditional data imputation approaches and one state-of-the-art algorithm.
Is Support Set Diversity Necessary for Meta-Learning?
Venue: arXiv cs.LG 2021
Year: 2021

Meta-learning is a popular framework for learning with limited data in which an algorithm is produced by training over multiple few-shot learning tasks. For classification problems, these tasks are typically constructed by sampling a small number of support and query examples from a subset of the classes. While conventional wisdom is that task diversity should improve the performance of meta-learning, in this work we find evidence to the contrary: we propose a modification to traditional meta-learning approaches in which we keep the support sets fixed across tasks, thus reducing task diversity. Surprisingly, we find that not only does this modification not result in adverse effects, it almost always improves the performance for a variety of datasets and meta-learning methods. We also provide several initial analyses to understand this phenomenon. Our work serves to: (i) more closely investigate the effect of support set construction for the problem of meta-learning, and (ii) suggest a simple, general, and competitive baseline for few-shot learning.
A Data-Driven Study of Commonsense Knowledge using the ConceptNet Knowledge Base
Venue: arXiv cs.AI 2021
Year: 2021

Acquiring commonsense knowledge and reasoning is recognized as an important frontier in achieving general Artificial Intelligence (AI). Recent research in the Natural Language Processing (NLP) community has demonstrated significant progress in this problem setting. Despite this progress, which is mainly on multiple-choice question answering tasks in limited settings, there is still a lack of understanding (especially at scale) of the nature of commonsense knowledge itself. In this paper, we propose and conduct a systematic study to enable a deeper understanding of commonsense knowledge by doing an empirical and structural analysis of the ConceptNet knowledge base. ConceptNet is a freely available knowledge base containing millions of commonsense assertions presented in natural language. Detailed experimental results on three carefully designed research questions, using state-of-the-art unsupervised graph representation learning ('embedding') and clustering techniques, reveal deep substructures in ConceptNet relations, allowing us to make data-driven and computational claims about the meaning of phenomena such as 'context' that are traditionally discussed only in qualitative terms. Furthermore, our methodology provides a case study in how to use data-science and computational methodologies for understanding the nature of an everyday (yet complex) psychological phenomenon that is an essential feature of human intelligence.
Solving parametric systems of polynomial equations over the reals through Hermite matrices
Venue: arXiv cs.SC 2021
Year: 2021

We design a new algorithm for solving parametric systems having finitely many complex solutions for generic values of the parameters. More precisely, let $f = (f_1, \ldots, f_m)\subset \mathbb{Q}[y][x]$ with $y = (y_1, \ldots, y_t)$ and $x = (x_1, \ldots, x_n)$, $V\subset \mathbb{C}^{t+n}$ be the algebraic set defined by $f$ and $π$ be the projection $(y, x) \to y$. Under the assumptions that $f$ admits finitely many complex roots for generic values of $y$ and that the ideal generated by $f$ is radical, we solve the following problem. On input $f$, we compute semi-algebraic formulas defining semi-algebraic subsets $S_1, \ldots, S_l$ of the $y$-space such that $\cup_{i=1}^l S_i$ is dense in $\mathbb{R}^t$ and the number of real points in $V\cap π^{-1}(η)$ is invariant when $η$ varies over each $S_i$. This algorithm exploits properties of some well chosen monomial bases in the algebra $\mathbb{Q}(y)[x]/I$ where $I$ is the ideal generated by $f$ in $\mathbb{Q}(y)[x]$ and the specialization property of the so-called Hermite matrices. This allows us to obtain compact representations of the sets $S_i$ by means of semi-algebraic formulas encoding the signature of a symmetric matrix. When $f$ satisfies extra genericity assumptions, we derive complexity bounds on the number of arithmetic operations in $\mathbb{Q}$ and the degree of the output polynomials. Let $d$ be the maximal degree of the $f_i$'s and $D = n(d-1)d^n$, we prove that, on a generic $f=(f_1,\ldots,f_n)$, one can compute those semi-algebraic formulas with $O^~( \binom{t+D}{t}2^{3t}n^{2t+1} d^{3nt+2(n+t)+1})$ operations in $\mathbb{Q}$ and that the polynomials involved have degree bounded by $D$. We report on practical experiments which illustrate the efficiency of our algorithm on generic systems and systems from applications. It allows us to solve problems which are out of reach of the state-of-the-art.
Rules of the Road: Safety and Liveness Guarantees for Autonomous Vehicles
Venue: arXiv cs.MA 2021
Year: 2021

The ability to guarantee safety and progress for all vehicles is vital to the success of the autonomous vehicle industry. We present a framework for designing autonomous vehicle behavior in a way that is safe and guarantees progress for all agents. In this paper, we first introduce a new game paradigm which we term the quasi-simultaneous game. We then define an agent protocol that all agents must use to make decisions in this quasi-simultaneous game setting. According to the protocol, agents first select an intended action using a behavioral profile. Then, the protocol defines whether an agent has precedence to take its intended action or must take a sub-optimal action. The protocol ensures safety under all traffic conditions and liveness for all agents under `sparse' traffic conditions. We provide proofs of correctness of the protocol and validate our results in simulation.
Batch Optimization for DNA Synthesis
Venue: arXiv cs.DS 2021
Year: 2021

Large pools of synthetic DNA molecules have been recently used to reliably store significant volumes of digital data. While DNA as a storage medium has enormous potential because of its high storage density, its practical use is currently severely limited because of the high cost and low throughput of available DNA synthesis technologies. We study the role of batch optimization in reducing the cost of large scale DNA synthesis, which translates to the following algorithmic task. Given a large pool $\mathcal{S}$ of random quaternary strings of fixed length, partition $\mathcal{S}$ into batches in a way that minimizes the sum of the lengths of the shortest common supersequences across batches. We introduce two ideas for batch optimization that both improve (in different ways) upon a naive baseline: (1) using both $(ACGT)^{*}$ and its reverse $(TGCA)^{*}$ as reference strands, and batching appropriately, and (2) batching via the quantiles of an appropriate ordering of the strands. We also prove asymptotically matching lower bounds on the cost of DNA synthesis, showing that one cannot improve upon these two ideas. Our results uncover a surprising separation between two cases that naturally arise in the context of DNA data storage: the asymptotic cost savings of batch optimization are significantly greater in the case where strings in $\mathcal{S}$ do not contain repeats of the same character (homopolymers), as compared to the case where strings in $\mathcal{S}$ are unconstrained.
TransMIA: Membership Inference Attacks Using Transfer Shadow Training
Venue: arXiv cs.CR 2021
Year: 2021

Transfer learning has been widely studied and gained increasing popularity to improve the accuracy of machine learning models by transferring some knowledge acquired in different training. However, no prior work has pointed out that transfer learning can strengthen privacy attacks on machine learning models. In this paper, we propose TransMIA (Transfer learning-based Membership Inference Attacks), which use transfer learning to perform membership inference attacks on the source model when the adversary is able to access the parameters of the transferred model. In particular, we propose a transfer shadow training technique, where an adversary employs the parameters of the transferred model to construct shadow models, to significantly improve the performance of membership inference when a limited amount of shadow training data is available to the adversary. We evaluate our attacks using two real datasets, and show that our attacks outperform the state-of-the-art that does not use our transfer shadow training technique. We also compare four combinations of the learning-based/entropy-based approach and the fine-tuning/freezing approach, all of which employ our transfer shadow training technique. Then we examine the performance of these four approaches based on the distributions of confidence values, and discuss possible countermeasures against our attacks.
Robust Ultra-wideband Range Error Mitigation with Deep Learning at the Edge
Venue: arXiv cs.LG 2021
Year: 2021

Ultra-wideband (UWB) is the state-of-the-art and most popular technology for wireless localization. Nevertheless, precise ranging and localization in non-line-of-sight (NLoS) conditions is still an open research topic. Indeed, multipath effects, reflections, refractions, and complexity of the indoor radio environment can easily introduce a positive bias in the ranging measurement, resulting in highly inaccurate and unsatisfactory position estimation. This article proposes an efficient representation learning methodology that exploits the latest advancement in deep learning and graph optimization techniques to achieve effective ranging error mitigation at the edge. Channel Impulse Response (CIR) signals are directly exploited to extract high semantic features to estimate corrections in either NLoS or LoS conditions. Extensive experimentation with different settings and configurations has proved the effectiveness of our methodology and demonstrated the feasibility of a robust and low computational power UWB range error mitigation.
On Initial Pools for Deep Active Learning
Venue: arXiv cs.LG 2021
Year: 2021

Active Learning (AL) techniques aim to minimize the training data required to train a model for a given task. Pool-based AL techniques start with a small initial labeled pool and then iteratively pick batches of the most informative samples for labeling. Generally, the initial pool is sampled randomly and labeled to seed the AL iterations. While recent studies have focused on evaluating the robustness of various query functions in AL, little to no attention has been given to the design of the initial labeled pool for deep active learning. Given the recent successes of learning representations in self-supervised/unsupervised ways, we study if an intelligently sampled initial labeled pool can improve deep AL performance. We investigate the effect of intelligently sampled initial labeled pools, including the use of self-supervised and unsupervised strategies, on deep AL methods. The setup, hypotheses, methodology, and implementation details were evaluated by peer review before experiments were conducted. Experimental results could not conclusively prove that intelligently sampled initial pools are better for AL than random initial pools in the long run, although a Variational Autoencoder-based initial pool sampling strategy showed interesting trends that merit deeper investigation.
Bayesian Assessments of Aeroengine Performance with Transfer Learning
Venue: arXiv cs.CE 2021
Year: 2021

Aeroengine performance is determined by temperature and pressure profiles along various axial stations within an engine. Given limited sensor measurements both along and between axial stations, we require a statistically principled approach to inferring these profiles. In this paper we detail a Bayesian methodology for interpolating the spatial temperature or pressure profile at axial stations within an aeroengine. The profile at any given axial station is represented as a spatial Gaussian random field on an annulus, with circumferential variations modelled using a Fourier basis and radial variations modelled with a squared exponential kernel. This Gaussian random field is extended to ingest data from multiple axial measurement planes, with the aim of transferring information across the planes. To facilitate this type of transfer learning, a novel planar covariance kernel is proposed, with hyperparameters that characterise the correlation between any two measurement planes. In the scenario where precise frequencies comprising the temperature field are unknown, we utilise a sparsity-promoting prior on the frequencies to encourage sparse representations. This easily extends to cases with multiple engine planes whilst accommodating frequency variations between the planes. The main quantity of interest, the spatial area average is readily obtained in closed form. We term this the Bayesian area average and demonstrate how this metric offers far more precise averages than a sector area average -- a widely used area averaging approach. Furthermore, the Bayesian area average naturally decomposes the posterior uncertainty into terms characterising insufficient sampling and sensor measurement error respectively. This too provides a significant improvement over prior standard deviation based uncertainty breakdowns.
Occlusion Guided Scene Flow Estimation on 3D Point Clouds
Venue: arXiv cs.CV 2021
Year: 2021

3D scene flow estimation is a vital tool in perceiving our environment given depth or range sensors. Unlike optical flow, the data is usually sparse and in most cases partially occluded in between two temporal samplings. Here we propose a new scene flow architecture called OGSF-Net which tightly couples the learning for both flow and occlusions between frames. Their coupled symbiosis results in a more accurate prediction of flow in space. Unlike a traditional multi-action network, our unified approach is fused throughout the network, boosting performances for both occlusion detection and flow estimation. Our architecture is the first to gauge the occlusion in 3D scene flow estimation on point clouds. In key datasets such as Flyingthings3D and KITTI, we achieve the state-of-the-art results.
From Technology to Society: An Overview of Blockchain-based DAO
Venue: arXiv cs.CR 2021
Year: 2021

Decentralized Autonomous Organization (DAO) is believed to play a significant role in our future society governed in a decentralized way. In this article, we first explain the definitions and preliminaries of DAO. Then, we conduct a literature review of the existing studies of DAO published in the recent few years. Through the literature review, we find out that a comprehensive survey towards the state-of-the-art studies of DAO is still missing. To fill this gap, we perform such an overview by identifying and classifying the most valuable proposals and perspectives closely related to the combination of DAO and blockchain technologies. We anticipate that this survey can help researchers, engineers, and educators acknowledge the cutting-edge development of blockchain-related DAO technologies.
Multimodal Dependent Type Theory
Venue: arXiv cs.LO 2021
Year: 2021

We introduce MTT, a dependent type theory which supports multiple modalities. MTT is parametrized by a mode theory which specifies a collection of modes, modalities, and transformations between them. We show that different choices of mode theory allow us to use the same type theory to compute and reason in many modal situations, including guarded recursion, axiomatic cohesion, and parametric quantification. We reproduce examples from prior work in guarded recursion and axiomatic cohesion, thereby demonstrating that MTT constitutes a simple and usable syntax whose instantiations intuitively correspond to previous handcrafted modal type theories. In some cases, instantiating MTT to a particular situation unearths a previously unknown type theory that improves upon prior systems. Finally, we investigate the metatheory of MTT. We prove the consistency of MTT and establish canonicity through an extension of recent type-theoretic gluing techniques. These results hold irrespective of the choice of mode theory, and thus apply to a wide variety of modal situations.
Move to See Better: Self-Improving Embodied Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

Passive methods for object detection and segmentation treat images of the same scene as individual samples and do not exploit object permanence across multiple views. Generalization to novel or difficult viewpoints thus requires additional training with lots of annotations. In contrast, humans often recognize objects by simply moving around, to get more informative viewpoints. In this paper, we propose a method for improving object detection in testing environments, assuming nothing but an embodied agent with a pre-trained 2D object detector. Our agent collects multi-view data, generates 2D and 3D pseudo-labels, and fine-tunes its detector in a self-supervised manner. Experiments on both indoor and outdoor datasets show that (1) our method obtains high-quality 2D and 3D pseudo-labels from multi-view RGB-D data; (2) fine-tuning with these pseudo-labels improves the 2D detector significantly in the test environment; (3) training a 3D detector with our pseudo-labels outperforms a prior self-supervised method by a large margin; (4) given weak supervision, our method can generate better pseudo-labels for novel objects.
Iterative Error Decimation for Syndrome-Based Neural Network Decoders
Venue: arXiv cs.IT 2021
Year: 2021

In this letter, we introduce a new syndrome-based decoder where a deep neural network (DNN) estimates the error pattern from the reliability and syndrome of the received vector. The proposed algorithm works by iteratively selecting the most confident positions to be the error bits of the error pattern, updating the vector received when a new position of the error pattern is selected. Simulation results for the (63,45) and (63,36) BCH codes show that the proposed approach outperforms existing neural network decoders. In addition, the new decoder is flexible in that it can be applied on top of any existing syndrome-based DNN decoder without retraining.
How cumulative is technological knowledge?
Venue: arXiv cs.SI 2021
Year: 2021

Technological cumulativeness is considered one of the main mechanisms for technological progress, yet its exact meaning and dynamics often remain unclear. To develop a better understanding of this mechanism we approach a technology as a body of knowledge consisting of interlinked inventions. Technological cumulativeness can then be understood as the extent to which inventions build on other inventions within that same body of knowledge. The cumulativeness of a technology is therefore characterized by the structure of its knowledge base, which is different from, but closely related to, the size of its knowledge base. We analytically derive equations describing the relation between the cumulativeness and the size of the knowledge base. In addition, we empirically test our ideas for a number of selected technologies, using patent data. Our results suggest that cumulativeness increases proportionally with the size of the knowledge base, at a rate which varies considerably across technologies. At the same time we find that across technologies, this rate is inversely related to the rate of invention over time. This suggests that the cumulativeness increases relatively slow in rapidly growing technologies. In sum, the presented approach allows for an in-depth, systematic analysis of cumulativeness variations across technologies and the knowledge dynamics underlying technology development.
A new operational representation of dependencies in Event Structures
Venue: arXiv cs.LO 2021
Year: 2021

The execution of an event in a complex and distributed system where the dependencies vary during the evolution of the system can be represented in many ways, and one of them is to use Context-Dependent Event structures. Event structures are related to Petri nets. The aim of this paper is to propose what can be the appropriate kind of Petri net corresponding to Context-Dependent Event structures, giving an operational flavour to the dependencies represented in a Context/Dependent Event structure. Dependencies are often operationally represented, in Petri nets, by tokens produced by activities and consumed by others. Here we shift the perspective using contextual arcs to characterize what has happened so far and in this way to describe the dependencies among the various activities.
Optimizing Fitness-For-Use of Differentially Private Linear Queries
Venue: arXiv cs.DB 2021
Year: 2021

In practice, differentially private data releases are designed to support a variety of applications. A data release is fit for use if it meets target accuracy requirements for each application. In this paper, we consider the problem of answering linear queries under differential privacy subject to per-query accuracy constraints. Existing practical frameworks like the matrix mechanism do not provide such fine-grained control (they optimize total error, which allows some query answers to be more accurate than necessary, at the expense of other queries that become no longer useful). Thus, we design a fitness-for-use strategy that adds privacy-preserving Gaussian noise to query answers. The covariance structure of the noise is optimized to meet the fine-grained accuracy requirements while minimizing the cost to privacy.
Robust error bounds for quantised and pruned neural networks
Venue: arXiv cs.LG 2021
Year: 2021

With the rise of smartphones and the internet-of-things, data is increasingly getting generated at the edge on local, personal devices. For privacy, latency and energy saving reasons, this shift is causing machine learning algorithms to move towards decentralisation with the data and algorithms stored, and even trained, locally on devices. The device hardware becomes the main bottleneck for model capability in this set-up, creating a need for slimmed down, more efficient neural networks. Neural network pruning and quantisation are two methods that have been developed for this, with both approaches demonstrating impressive results in reducing the computational cost without sacrificing significantly on model performance. However, the understanding behind these reduction methods remains underdeveloped. To address this issue, a semi-definite program is introduced to bound the worst-case error caused by pruning or quantising a neural network. The method can be applied to many neural network structures and nonlinear activation functions with the bounds holding robustly for all inputs in specified sets. It is hoped that the computed bounds will provide certainty to the performance of these algorithms when deployed on safety-critical systems.