OpenRaiser/Intern-Atlas huggingface dataset:
Data provenance, curation and quality in metrology
Venue: arXiv cs.DB 2021
Year: 2021

Data metrology -- the assessment of the quality of data -- particularly in scientific and industrial settings, has emerged as an important requirement for the UK National Physical Laboratory (NPL) and other national metrology institutes. Data provenance and data curation are key components for emerging understanding of data metrology. However, to date provenance research has had limited visibility to or uptake in metrology. In this work, we summarize a scoping study carried out with NPL staff and industrial participants to understand their current and future needs for provenance, curation and data quality. We then survey provenance technology and standards that are relevant to metrology. We analyse the gaps between requirements and the current state of the art.
Significant Otter: Understanding the Role of Biosignals in Communication
Venue: arXiv cs.HC 2021
Year: 2021

With the growing ubiquity of wearable devices, sensed physiological responses provide new means to connect with others. While recent research demonstrates the expressive potential for biosignals, the value of sharing these personal data remains unclear. To understand their role in communication, we created Significant Otter, an Apple Watch/iPhone app that enables romantic partners to share and respond to each other's biosignals in the form of animated otter avatars. In a one-month study with 20 couples, participants used Significant Otter with biosignals sensing OFF and ON. We found that while sensing OFF enabled couples to keep in touch, sensing ON enabled easier and more authentic communication that fostered social connection. However, the addition of biosignals introduced concerns about autonomy and agency over the messages they sent. We discuss design implications and future directions for communication systems that recommend messages based on biosignals.
Differentially Private Quantiles
Venue: arXiv cs.LG 2021
Year: 2021

Quantiles are often used for summarizing and understanding data. If that data is sensitive, it may be necessary to compute quantiles in a way that is differentially private, providing theoretical guarantees that the result does not reveal private information. However, when multiple quantiles are needed, existing differentially private algorithms fare poorly: they either compute quantiles individually, splitting the privacy budget, or summarize the entire distribution, wasting effort. In either case the result is reduced accuracy. In this work we propose an instance of the exponential mechanism that simultaneously estimates exactly $m$ quantiles from $n$ data points while guaranteeing differential privacy. The utility function is carefully structured to allow for an efficient implementation that returns estimates of all $m$ quantiles in time $O(mn\log(n) + m^2n)$. Experiments show that our method significantly outperforms the current state of the art on both real and synthetic data while remaining efficient enough to be practical.
Deciphering Social Opinion Polarization Towards Political Event Based on Content and Structural Analysis
Venue: arXiv cs.SI 2021
Year: 2021

There are some shreds of evidence that social opinion polarization leads to the breakup of the relationship, some in the scale of small communities, but others can divide large organizations or even a nation. The legacy methodology to answer the root cause of opinion polarization in the society commonly use random sampling or questionnaire-based approach, which considered expensive in term of time and money. On the contrary, the opportunity to employ big data approach using social media data provides a rich source to investigate several questions, such as: how social opinion polarization formed, dynamic social network mechanisms during time-windows observation, identification of dominant actors and communities. The power of the big data approach lies in the number of data analyzed, where the more data involved in the process, the more accurate to describe the population condition. Today, computing power is no longer become an obstacle to process large-scale data, thus the observation of the social opinion polarization process is possible.
Reinforced Contact Tracing and Epidemic Intervention
Venue: arXiv cs.AI 2021
Year: 2021

The recent outbreak of COVID-19 poses a serious threat to people's lives. Epidemic control strategies have also caused damage to the economy by cutting off humans' daily commute. In this paper, we develop an Individual-based Reinforcement Learning Epidemic Control Agent (IDRLECA) to search for smart epidemic control strategies that can simultaneously minimize infections and the cost of mobility intervention. IDRLECA first hires an infection probability model to calculate the current infection probability of each individual. Then, the infection probabilities together with individuals' health status and movement information are fed to a novel GNN to estimate the spread of the virus through human contacts. The estimated risks are used to further support an RL agent to select individual-level epidemic-control actions. The training of IDRLECA is guided by a specially designed reward function considering both the cost of mobility intervention and the effectiveness of epidemic control. Moreover, we design a constraint for control-action selection that eases its difficulty and further improve exploring efficiency. Extensive experimental results demonstrate that IDRLECA can suppress infections at a very low level and retain more than 95% of human mobility.
Guarded Kleene Algebra with Tests: Coequations, Coinduction, and Completeness
Venue: arXiv cs.LO 2021
Year: 2021

Guarded Kleene Algebra with Tests (GKAT) is an efficient fragment of KAT, as it allows for almost linear decidability of equivalence. In this paper, we study the (co)algebraic properties of GKAT. Our initial focus is on the fragment that can distinguish between unsuccessful programs performing different actions, by omitting the so-called early termination axiom. We develop an operational (coalgebraic) and denotational (algebraic) semantics and show that they coincide. We then characterize the behaviors of GKAT expressions in this semantics, leading to a coequation that captures the covariety of automata corresponding to behaviors of GKAT expressions. Finally, we prove that the axioms of the reduced fragment are sound and complete w.r.t. the semantics, and then build on this result to recover a semantics that is sound and complete w.r.t. the full set of axioms.
Model-based Meta Reinforcement Learning using Graph Structured Surrogate Models
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning is a promising paradigm for solving sequential decision-making problems, but low data efficiency and weak generalization across tasks are bottlenecks in real-world applications. Model-based meta reinforcement learning addresses these issues by learning dynamics and leveraging knowledge from prior experience. In this paper, we take a closer look at this framework, and propose a new Thompson-sampling based approach that consists of a new model to identify task dynamics together with an amortized policy optimization step. We show that our model, called a graph structured surrogate model (GSSM), outperforms state-of-the-art methods in predicting environment dynamics. Additionally, our approach is able to obtain high returns, while allowing fast execution during deployment by avoiding test time policy gradient optimization.
New Techniques for Universality in Unambiguous Register Automata
Venue: arXiv cs.FL 2021
Year: 2021

Register automata are finite automata equipped with a finite set of registers ranging over the domain of some relational structure like $(\mathbb N;=)$ or $(\mathbb Q;<)$. Register automata process words over the domain, and along a run of the automaton, the registers can store data from the input word for later comparisons. It is long known that the universality problem, i.e., the problem to decide whether a given register automaton accepts all words over the domain, is undecidable. Recently, we proved the problem to be decidable in 2-ExpSpace if the register automaton under study is over $(\mathbb N;=)$ and unambiguous, i.e., every input word has at most one accepting run; this result was shortly after improved to 2-ExpTime by Barloy and Clemente. In this paper, we go one step further and prove that the problem is in ExpSpace, and in PSpace if the number of registers is fixed. Our proof is based on new techniques that additionally allow us to show that the problem is in PSpace for single-register automata over $(\mathbb Q;<)$. As a third technical contribution we prove that the problem is decidable (in ExpSpace) for a more expressive model of unambiguous register automata, where the registers can take values nondeterministically, if defined over $(\mathbb N;=)$ and only one register is used.
On the sampling Lovász Local Lemma for atomic constraint satisfaction problems
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of sampling an approximately uniformly random satisfying assignment for atomic constraint satisfaction problems i.e. where each constraint is violated by only one assignment to its variables. Let $p$ denote the maximum probability of violation of any constraint and let $Δ$ denote the maximum degree of the line graph of the constraints. Our main result is a nearly-linear (in the number of variables) time algorithm for this problem, which is valid in a Lovász local lemma type regime that is considerably less restrictive compared to previous works. In particular, we provide sampling algorithms for the uniform distribution on: (1) $q$-colorings of $k$-uniform hypergraphs with $Δ\lesssim q^{(k-4)/3 + o_{q}(1)}.$ The exponent $1/3$ improves the previously best-known $1/7$ in the case $q, Δ= O(1)$ [Jain, Pham, Vuong; arXiv, 2020] and $1/9$ in the general case [Feng, He, Yin; STOC 2021]. (2) Satisfying assignments of Boolean $k$-CNF formulas with $Δ\lesssim 2^{k/5.741}.$ The constant $5.741$ in the exponent improves the previously best-known $7$ in the case $k = O(1)$ [Jain, Pham, Vuong; arXiv, 2020] and $13$ in the general case [Feng, He, Yin; STOC 2021]. (3) Satisfying assignments of general atomic constraint satisfaction problems with $p\cdot Δ^{7.043} \lesssim 1.$ The constant $7.043$ improves upon the previously best-known constant of $350$ [Feng, He, Yin; STOC 2021]. At the heart of our analysis is a novel information-percolation type argument for showing the rapid mixing of the Glauber dynamics for a carefully constructed projection of the uniform distribution on satisfying assignments. Notably, there is no natural partial order on the space, and we believe that the techniques developed for the analysis may be of independent interest.
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
Venue: arXiv cs.DS 2021
Year: 2021

A graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. The class of Helly graphs is the discrete analogue of the class of hyperconvex metric spaces. It is also known that every graph isometrically embeds into a Helly graph, making the latter an important class of graphs in Metric Graph Theory. We study diameter, radius and all eccentricity computations within the Helly graphs. Under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time on general graphs. In contrast to these negative results, it was recently shown that the radius and the diameter of an $n$-vertex $m$-edge Helly graph $G$ can be computed with high probability in $\tilde{\mathcal O}(m\sqrt{n})$ time (i.e., subquadratic in $n+m$). In this paper, we improve that result by presenting a deterministic ${\mathcal O}(m\sqrt{n})$ time algorithm which computes not only the radius and the diameter but also all vertex eccentricities in a Helly graph. Furthermore, we give a parameterized linear-time algorithm for this problem on Helly graphs, with the parameter being the Gromov hyperbolicity $δ$. More specifically, we show that the radius and a central vertex of an $m$-edge $δ$-hyperbolic Helly graph $G$ can be computed in $\mathcal O(δm)$ time and that all vertex eccentricities in $G$ can be computed in $\mathcal O(δ^2 m)$ time. To show this more general result, we heavily use our new structural properties obtained for Helly graphs.
Efficient Competitions and Online Learning with Strategic Forecasters
Venue: arXiv cs.LG 2021
Year: 2021

Winner-take-all competitions in forecasting and machine-learning suffer from distorted incentives. Witkowski et al. 2018 identified this problem and proposed ELF, a truthful mechanism to select a winner. We show that, from a pool of $n$ forecasters, ELF requires $Θ(n\log n)$ events or test data points to select a near-optimal forecaster with high probability. We then show that standard online learning algorithms select an $ε$-optimal forecaster using only $O(\log(n) / ε^2)$ events, by way of a strong approximate-truthfulness guarantee. This bound matches the best possible even in the nonstrategic setting. We then apply these mechanisms to obtain the first no-regret guarantee for non-myopic strategic experts.
A Multi-disciplinary Ensemble Algorithm for Clustering Heterogeneous Datasets
Venue: arXiv cs.LG 2021
Year: 2021

Clustering is a commonly used method for exploring and analysing data where the primary objective is to categorise observations into similar clusters. In recent decades, several algorithms and methods have been developed for analysing clustered data. We notice that most of these techniques deterministically define a cluster based on the value of the attributes, distance, and density of homogenous and single-featured datasets. However, these definitions are not successful in adding clear semantic meaning to the clusters produced. Evolutionary operators and statistical and multi-disciplinary techniques may help in generating meaningful clusters. Based on this premise, we propose a new evolutionary clustering algorithm (ECAStar) based on social class ranking and meta-heuristic algorithms for stochastically analysing heterogeneous and multiple-featured datasets. The ECAStar is integrated with recombinational evolutionary operators, Levy flight optimisation, and some statistical techniques, such as quartiles and percentiles, as well as the Euclidean distance of the K-means algorithm. Experiments are conducted to evaluate the ECAStar against five conventional approaches: K-means (KM), K-meansPlusPlus (KMPlusPlus), expectation maximisation (EM), learning vector quantisation (LVQ), and the genetic algorithm for clusteringPlusPlus (GENCLUSTPlusPlus).
Boosting Low-Resource Biomedical QA via Entity-Aware Masking Strategies
Venue: arXiv cs.CL 2021
Year: 2021

Biomedical question-answering (QA) has gained increased attention for its capability to provide users with high-quality information from a vast scientific literature. Although an increasing number of biomedical QA datasets has been recently made available, those resources are still rather limited and expensive to produce. Transfer learning via pre-trained language models (LMs) has been shown as a promising approach to leverage existing general-purpose knowledge. However, finetuning these large models can be costly and time consuming, often yielding limited benefits when adapting to specific themes of specialised domains, such as the COVID-19 literature. To bootstrap further their domain adaptation, we propose a simple yet unexplored approach, which we call biomedical entity-aware masking (BEM). We encourage masked language models to learn entity-centric knowledge based on the pivotal entities characterizing the domain at hand, and employ those entities to drive the LM fine-tuning. The resulting strategy is a downstream process applicable to a wide variety of masked LMs, not requiring additional memory or components in the neural architectures. Experimental results show performance on par with state-of-the-art models on several biomedical QA datasets.
Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Information
Venue: arXiv cs.LG 2021
Year: 2021

Training and evaluation of fair classifiers is a challenging problem. This is partly due to the fact that most fairness metrics of interest depend on both the sensitive attribute information and label information of the data points. In many scenarios it is not possible to collect large datasets with such information. An alternate approach that is commonly used is to separately train an attribute classifier on data with sensitive attribute information, and then use it later in the ML pipeline to evaluate the bias of a given classifier. While such decoupling helps alleviate the problem of demographic scarcity, it raises several natural questions such as: how should the attribute classifier be trained?, and how should one use a given attribute classifier for accurate bias estimation? In this work we study this question from both theoretical and empirical perspectives. We first experimentally demonstrate that the test accuracy of the attribute classifier is not always correlated with its effectiveness in bias estimation for a downstream model. In order to further investigate this phenomenon, we analyze an idealized theoretical model and characterize the structure of the optimal classifier. Our analysis has surprising and counter-intuitive implications where in certain regimes one might want to distribute the error of the attribute classifier as unevenly as possible among the different subgroups. Based on our analysis we develop heuristics for both training and using attribute classifiers for bias estimation in the data scarce regime. We empirically demonstrate the effectiveness of our approach on real and simulated data.
Searching for Search Errors in Neural Morphological Inflection
Venue: arXiv cs.CL 2021
Year: 2021

Neural sequence-to-sequence models are currently the predominant choice for language generation tasks. Yet, on word-level tasks, exact inference of these models reveals the empty string is often the global optimum. Prior works have speculated this phenomenon is a result of the inadequacy of neural models for language generation. However, in the case of morphological inflection, we find that the empty string is almost never the most probable solution under the model. Further, greedy search often finds the global optimum. These observations suggest that the poor calibration of many neural models may stem from characteristics of a specific subset of tasks rather than general ill-suitedness of such models for language generation.
A Review of Testing Object-Based Environment Perception for Safe Automated Driving
Venue: arXiv cs.RO 2021
Year: 2021

Safety assurance of automated driving systems must consider uncertain environment perception. This paper reviews literature addressing how perception testing is realized as part of safety assurance. We focus on testing for verification and validation purposes at the interface between perception and planning, and structure our analysis along the three axes 1) test criteria and metrics, 2) test scenarios, and 3) reference data. Furthermore, the analyzed literature includes related safety standards, safety-independent perception algorithm benchmarking, and sensor modeling. We find that the realization of safety-aware perception testing remains an open issue since challenges concerning the three testing axes and their interdependencies currently do not appear to be sufficiently solved.
Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments
Venue: arXiv cs.LG 2021
Year: 2021

We study black-box reward poisoning attacks against reinforcement learning (RL), in which an adversary aims to manipulate the rewards to mislead a sequence of RL agents with unknown algorithms to learn a nefarious policy in an environment unknown to the adversary a priori. That is, our attack makes minimum assumptions on the prior knowledge of the adversary: it has no initial knowledge of the environment or the learner, and neither does it observe the learner's internal mechanism except for its performed actions. We design a novel black-box attack, U2, that can provably achieve a near-matching performance to the state-of-the-art white-box attack, demonstrating the feasibility of reward poisoning even in the most challenging black-box setting.
Shape-Tailored Deep Neural Networks
Venue: arXiv cs.CV 2021
Year: 2021

We present Shape-Tailored Deep Neural Networks (ST-DNN). ST-DNN extend convolutional networks (CNN), which aggregate data from fixed shape (square) neighborhoods, to compute descriptors defined on arbitrarily shaped regions. This is natural for segmentation, where descriptors should describe regions (e.g., of objects) that have diverse shape. We formulate these descriptors through the Poisson partial differential equation (PDE), which can be used to generalize convolution to arbitrary regions. We stack multiple PDE layers to generalize a deep CNN to arbitrary regions, and apply it to segmentation. We show that ST-DNN are covariant to translations and rotations and robust to domain deformations, natural for segmentation, which existing CNN based methods lack. ST-DNN are 3-4 orders of magnitude smaller then CNNs used for segmentation. We show that they exceed segmentation performance compared to state-of-the-art CNN-based descriptors using 2-3 orders smaller training sets on the texture segmentation problem.
Fast Graph Learning with Unique Optimal Solutions
Venue: arXiv cs.LG 2021
Year: 2021

We consider two popular Graph Representation Learning (GRL) methods: message passing for node classification and network embedding for link prediction. For each, we pick a popular model that we: (i) linearize and (ii) and switch its training objective to Frobenius norm error minimization. These simplifications can cast the training into finding the optimal parameters in closed-form. We program in TensorFlow a functional form of Truncated Singular Value Decomposition (SVD), such that, we could decompose a dense matrix $\mathbf{M}$, without explicitly computing $\mathbf{M}$. We achieve competitive performance on popular GRL tasks while providing orders of magnitude speedup. We open-source our code at http://github.com/samihaija/tf-fsvd