OpenRaiser/Intern-Atlas huggingface dataset:
Cheating in online gaming spreads through observation and victimization
Venue: arXiv cs.SI 2022
Year: 2022

Antisocial behavior can be contagious, spreading from individual to individual and rippling through social networks. Moreover, it can spread not only through third-party influence from observation, just like innovations or individual behavior do, but also through direct experience, via "pay-it-forward" retaliation. Here, we distinguish between the effects of observation and victimization for the contagion of antisocial behavior by analyzing large-scale digital-trace data. We study the spread of cheating in more than a million matches of an online multiplayer first-person shooter game, in which up to 100 players compete individually or in teams against strangers. We identify event sequences in which a player who observes or is killed by a certain number of cheaters starts cheating, and evaluate the extent to which these sequences would appear if we preserve the team and interaction structure but assume alternative gameplay scenarios. The results reveal that social contagion is only likely to exist for those who both observe and experience cheating, suggesting that third-party influence and "pay-it-forward" reciprocity interact positively. In addition, the effect is present only for those who both observe and experience more than once, suggesting that cheating is more likely to spread after repeated or multi-source exposure. Approaching online games as models of social systems, we use the findings to discuss strategies for targeted interventions to stem the spread of cheating and antisocial behavior more generally in online communities, schools, organizations, and sports.
Topology and adjunction in promise constraint satisfaction
Venue: arXiv cs.CC 2022
Year: 2022

The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a $c$-colouring of a graph that is promised to be $k$-colourable, where $c\geq k$. This problem naturally generalises to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyse the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph colouring and promise graph homomorphism problems.
A Benchmark for Point Clouds Registration Algorithms
Venue: arXiv cs.RO 2022
Year: 2022

Point clouds registration is a fundamental step of many point clouds processing pipelines; however, most algorithms are tested on data that are collected ad-hoc and not shared with the research community. These data often cover only a very limited set of use cases; therefore, the results cannot be generalised. Public datasets proposed until now, taken individually, cover only a few kinds of environment and mostly a single sensor. For these reasons, we developed a benchmark, for localization and mapping applications, using multiple publicly available datasets. In this way, we are able to cover many kinds of environment and many kinds of sensor that can produce point clouds. Furthermore, the ground truth has been thoroughly inspected and evaluated to ensure its quality. For some of the datasets, the accuracy of the ground truth measuring system was not reported by the original authors, therefore we estimated it with our own novel method, based on an iterative registration algorithm. Along with the data, we provide a broad set of registration problems, chosen to cover different types of initial misalignment, various degrees of overlap, and different kinds of registration problems. Lastly, we propose a metric to measure the performances of registration algorithms: it combines the commonly used rotation and translation errors together, to allow an objective comparison of the alignments. This work aims at encouraging authors to use a public and shared benchmark, instead of data collected ad-hoc, to ensure objectivity and repeatability, two fundamental characteristics in any scientific field.
The Operating System of the Neuromorphic BrainScaleS-1 System
Venue: arXiv cs.NE 2022
Year: 2022

BrainScaleS-1 is a wafer-scale mixed-signal accelerated neuromorphic system targeted for research in the fields of computational neuroscience and beyond-von-Neumann computing. The BrainScaleS Operating System (BrainScaleS OS) is a software stack giving users the possibility to emulate networks described in the high-level network description language PyNN with minimal knowledge of the system. At the same time, expert usage is facilitated by allowing to hook into the system at any depth of the stack. We present operation and development methodologies implemented for the BrainScaleS-1 neuromorphic architecture and walk through the individual components of BrainScaleS OS constituting the software stack for BrainScaleS-1 platform operation.
SS-IL: Separated Softmax for Incremental Learning
Venue: arXiv cs.CV 2022
Year: 2022

We consider class incremental learning (CIL) problem, in which a learning agent continuously learns new classes from incrementally arriving training data batches and aims to predict well on all the classes learned so far. The main challenge of the problem is the catastrophic forgetting, and for the exemplar-memory based CIL methods, it is generally known that the forgetting is commonly caused by the classification score bias that is injected due to the data imbalance between the new classes and the old classes (in the exemplar-memory). While several methods have been proposed to correct such score bias by some additional post-processing, e.g., score re-scaling or balanced fine-tuning, no systematic analysis on the root cause of such bias has been done. To that end, we analyze that computing the softmax probabilities by combining the output scores for all old and new classes could be the main cause of the bias. Then, we propose a new method, dubbed as Separated Softmax for Incremental Learning (SS-IL), that consists of separated softmax (SS) output layer combined with task-wise knowledge distillation (TKD) to resolve such bias. Throughout our extensive experimental results on several large-scale CIL benchmark datasets, we show our SS-IL achieves strong state-of-the-art accuracy through attaining much more balanced prediction scores across old and new classes, without any additional post-processing.
Approximate Selection with Guarantees using Proxies
Venue: arXiv cs.DB 2022
Year: 2022

Due to the falling costs of data acquisition and storage, researchers and industry analysts often want to find all instances of rare events in large datasets. For instance, scientists can cheaply capture thousands of hours of video, but are limited by the need to manually inspect long videos to identify relevant objects and events. To reduce this cost, recent work proposes to use cheap proxy models, such as image classifiers, to identify an approximate set of data points satisfying a data selection filter. Unfortunately, this recent work does not provide the statistical accuracy guarantees necessary in scientific and production settings. In this work, we introduce novel algorithms for approximate selection queries with statistical accuracy guarantees. Namely, given a limited number of exact identifications from an oracle, often a human or an expensive machine learning model, our algorithms meet a minimum precision or recall target with high probability. In contrast, existing approaches can catastrophically fail in satisfying these recall and precision targets. We show that our algorithms can improve query result quality by up to 30x for both the precision and recall targets in both real and synthetic datasets.
Surrogate-assisted performance prediction for data-driven knowledge discovery algorithms: application to evolutionary modeling of clinical pathways
Venue: arXiv cs.LG 2022
Year: 2022

The paper proposes and investigates an approach for surrogate-assisted performance prediction of data-driven knowledge discovery algorithms. The approach is based on the identification of surrogate models for prediction of the target algorithm's quality and performance. The proposed approach was implemented and investigated as applied to an evolutionary algorithm for discovering clusters of interpretable clinical pathways in electronic health records of patients with acute coronary syndrome. Several clustering metrics and execution time were used as the target quality and performance metrics respectively. An analytical software prototype based on the proposed approach for the prediction of algorithm characteristics and feature analysis was developed to provide a more interpretable prediction of the target algorithm's performance and quality that can be further used for parameter tuning.
Efficient Conformance Checking using Approximate Alignment Computation with Tandem Repeats
Venue: arXiv cs.SE 2022
Year: 2022

Conformance checking encompasses a body of process mining techniques which aim to find and describe the differences between a process model capturing the expected process behavior and a corresponding event log recording the observed behavior. Alignments are an established technique to compute the distance between a trace in the event log and the closest execution trace of a corresponding process model. Given a cost function, an alignment is optimal when it contains the least number of mismatches between a log trace and a model trace. Determining optimal alignments, however, is computationally expensive, especially in light of the growing size and complexity of event logs from practice, which can easily exceed one million events with traces of several hundred activities. A common limitation of existing alignment techniques is the inability to exploit repetitions in the log. By exploiting a specific form of sequential pattern in traces, namely tandem repeats, we propose a novel approximate technique that uses pre- and post-processing steps to compress the length of a trace and recomputes the alignment cost while guaranteeing that the cost result never under-approximates the optimal cost. In an extensive empirical evaluation with 50 real-life model log pairs and against six state-of-the-art alignment techniques, we show that the proposed compression approach systematically outperforms the baselines by up to an order of magnitude in the presence of traces with repetitions, and that the cost over-approximation, when it occurs, is negligible.
Domain-based Latent Personal Analysis and its use for impersonation detection in social media
Venue: arXiv cs.CL 2022
Year: 2022

Zipf's law defines an inverse proportion between a word's ranking in a given corpus and its frequency in it, roughly dividing the vocabulary into frequent words and infrequent ones. Here, we stipulate that within a domain an author's signature can be derived from, in loose terms, the author's missing popular words and frequently used infrequent-words. We devise a method, termed Latent Personal Analysis (LPA), for finding domain-based attributes for entities in a domain: their distance from the domain and their signature, which determines how they most differ from a domain. We identify the most suitable distance metric for the method among several and construct the distances and personal signatures for authors, the domain's entities. The signature consists of both over-used terms (compared to the average), and missing popular terms. We validate the correctness and power of the signatures in identifying users and set existence conditions. We then show uses for the method in explainable authorship attribution: we define algorithms that utilize LPA to identify two types of impersonation in social media: (1) authors with sockpuppets (multiple) accounts; (2) front users accounts, operated by several authors. We validate the algorithms and employ them over a large scale dataset obtained from a social media site with over 4000 users. We corroborate these results using temporal rate analysis. LPA can further be used to devise personal attributes in a wide range of scientific domains in which the constituents have a long-tail distribution of elements.
Real-Time Segmentation Networks should be Latency Aware
Venue: arXiv cs.CV 2022
Year: 2022

As scene segmentation systems reach visually accurate results, many recent papers focus on making these network architectures faster, smaller and more efficient. In particular, studies often aim at designingreal-time'systems. Achieving this goal is particularly relevant in the context of real-time video understanding for autonomous vehicles, and robots. In this paper, we argue that the commonly used performance metric of mean Intersection over Union (mIoU) does not fully capture the information required to estimate the true performance of these networks when they operate inreal-time'. We propose a change of objective in the segmentation task, and its associated metric that encapsulates this missing information in the following way: We propose to predict the future output segmentation map that will match the future input frame at the time when the network finishes the processing. We introduce the associated latency-aware metric, from which we can determine a ranking. We perform latency timing experiments of some recent networks on different hardware and assess the performances of these networks on our proposed task. We propose improvements to scene segmentation networks to better perform on our task by using multi-frames input and increasing capacity in the initial convolutional layers.
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
Venue: arXiv cs.DS 2022
Year: 2022

Consider the following abstract coin tossing problem: Given a set of $n$ coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time. Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. In this model, the coins are arriving one by one and the algorithm is only allowed to store a limited number of coins at any point -- any coin not present in the memory is lost and can no longer be tossed or compared to arriving coins. Prior algorithms for the coin tossing problem with optimal sample complexity are based on iterative elimination of coins which inherently require storing all the coins, leading to memory-inefficient streaming algorithms. We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only $O(\log{n})$ coins and then iteratively refine it further and further, leading to algorithms with $O(\log\log{(n)})$ memory, $O(\log^*{(n)})$ memory, and finally a one that only stores a single extra coin in memory -- the same exact space needed to just store the best coin throughout the stream. Furthermore, we extend our algorithms to the problem of finding the $k$ most biased coins as well as other exploration problems such as finding top-$k$ elements using noisy comparisons or finding an $ε$-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.
Squares: A Fast Counter-Based RNG
Venue: arXiv cs.DS 2022
Year: 2022

In this article, we propose a new counter-based implementation of John von Neumann's middle-square random number generator (RNG). Several rounds of squaring are applied to a counter to produce a random output. We discovered that four rounds are sufficient to provide satisfactory data. Two versions of the RNG are presented, a 4-round version with 32-bit output and a 5-round version with 64-bit output. Both pass stringent tests of randomness and may be the fastest counter-based generators.
Certifiable Robustness to Adversarial State Uncertainty in Deep Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

Deep Neural Network-based systems are now the state-of-the-art in many robotics tasks, but their application in safety-critical domains remains dangerous without formal guarantees on network robustness. Small perturbations to sensor inputs (from noise or adversarial examples) are often enough to change network-based decisions, which was recently shown to cause an autonomous vehicle to swerve into another lane. In light of these dangers, numerous algorithms have been developed as defensive mechanisms from these adversarial inputs, some of which provide formal robustness guarantees or certificates. This work leverages research on certified adversarial robustness to develop an online certifiably robust for deep reinforcement learning algorithms. The proposed defense computes guaranteed lower bounds on state-action values during execution to identify and choose a robust action under a worst-case deviation in input space due to possible adversaries or noise. Moreover, the resulting policy comes with a certificate of solution quality, even though the true state and optimal action are unknown to the certifier due to the perturbations. The approach is demonstrated on a Deep Q-Network policy and is shown to increase robustness to noise and adversaries in pedestrian collision avoidance scenarios and a classic control task. This work extends one of our prior works with new performance guarantees, extensions to other RL algorithms, expanded results aggregated across more scenarios, an extension into scenarios with adversarial behavior, comparisons with a more computationally expensive method, and visualizations that provide intuition about the robustness algorithm.
Fairness in penalty shootouts: Is it worth using dynamic sequences?
Venue: arXiv cs.GT 2022
Year: 2022

The sequence of moves in a dynamic team tournament may distort the ex-ante winning probabilities and harm efficiency. This paper compares seven soccer penalty shootout rules that determine the kicking order, from a theoretical perspective. Their fairness is evaluated in a reasonable model of First Mover Advantage. We also discuss the probability of reaching the sudden death stage. In the case of stationary scoring probabilities, dynamic mechanisms are not better than static rules. However, it is worth compensating the second-mover by making it the first-mover in the sudden death stage. Our work has the potential to impact decision-makers who can guarantee fairer outcomes in dynamic tournaments by a carefully chosen sequence of actions.
Approximate exploitability: Learning a best response in large games
Venue: arXiv cs.LG 2022
Year: 2022

Researchers have demonstrated that neural networks are vulnerable to adversarial examples and subtle environment changes, both of which one can view as a form of distribution shift. To humans, the resulting errors can look like blunders, eroding trust in these agents. In prior games research, agent evaluation often focused on the in-practice game outcomes. While valuable, such evaluation typically fails to evaluate robustness to worst-case outcomes. Prior research in computer poker has examined how to assess such worst-case performance, both exactly and approximately. Unfortunately, exact computation is infeasible with larger domains, and existing approximations rely on poker-specific knowledge. We introduce ISMCTS-BR, a scalable search-based deep reinforcement learning algorithm for learning a best response to an agent, thereby approximating worst-case performance. We demonstrate the technique in several two-player zero-sum games against a variety of agents, including several AlphaZero-based agents.
Cyber-Physical Mobility Lab: An Open-Source Platform for Networked and Autonomous Vehicles
Venue: arXiv cs.MA 2022
Year: 2022

This paper introduces our Cyber-Physical Mobility Lab (CPM Lab). It is an open-source development environment for networked and autonomous vehicles with focus on networked decision-making, trajectory planning, and control. The CPM Lab hosts 20 physical model-scale vehicles (μCars) which we can seamlessly extend by unlimited simulated vehicles. The code and construction plans are publicly available to enable rebuilding the CPM Lab. Our four-layered architecture enables the seamless use of the same software in simulations and in experiments without any further adaptions. A Data Distribution Service (DDS) based middleware allows adapting the number of vehicles during experiments in a seamless manner. The middleware is also responsible for synchronizing all entities following a logical execution time approach to achieve determinism and reproducibility of experiments. This approach makes the CPM Lab a unique platform for rapid functional prototyping of networked decision-making algorithms. The CPM Lab allows researchers as well as students from different disciplines to see their ideas developing into reality. We demonstrate its capabilities using two example experiments. We are working on a remote access to the CPM Lab via a webinterface.
SARS-CoV-2, a Threat to Privacy?
Venue: arXiv cs.CY 2022
Year: 2022

The global SARS-CoV-2 pandemic is currently putting a massive strain on the world's critical infrastructures. With healthcare systems and internet service providers already struggling to provide reliable service, some operators may, intentionally or unintentionally, lever out privacy-protecting measures to increase their system's efficiency in fighting the virus. Moreover, though it may seem all encouraging to see the effectiveness of authoritarian states in battling the crisis, we, the authors of this paper, would like to raise the community's awareness towards developing more effective means in battling the crisis without the need to limit fundamental human rights. To analyze the current situation, we are discussing and evaluating the steps corporations and governments are taking to condemn the virus by applying established privacy research.
Learning the grammar of drug prescription: recurrent neural network grammars for medication information extraction in clinical texts
Venue: arXiv cs.CL 2022
Year: 2022

In this study, we evaluated the RNNG, a neural top-down transition based parser, for medication information extraction in clinical texts. We evaluated this model on a French clinical corpus. The task was to extract the name of a drug (or a drug class), as well as attributes informing its administration: frequency, dosage, duration, condition and route of administration. We compared the RNNG model that jointly identifies entities, events and their relations with separate BiLSTMs models for entities, events and relations as baselines. We call seq-BiLSTMs the baseline models for relations extraction that takes as extra-input the output of the BiLSTMs for entities and events. Similarly, we evaluated seq-RNNG, a hybrid RNNG model that takes as extra-input the output of the BiLSTMs for entities and events. RNNG outperforms seq-BiLSTM for identifying complex relations, with on average 88.1 [84.4-91.6] % versus 69.9 [64.0-75.4] F-measure. However, RNNG tends to be weaker than the baseline BiLSTM on detecting entities, with on average 82.4 [80.8-83.8] versus 84.1 [82.7-85.6] % F- measure. RNNG trained only for detecting relations tends to be weaker than RNNG with the joint modelling objective, 87.4% [85.8-88.8] versus 88.5% [87.2-89.8]. Seq-RNNG is on par with BiLSTM for entities (84.0 [82.6-85.4] % F-measure) and with RNNG for relations (88.7 [87.4-90.0] % F-measure). The performance of RNNG on relations can be explained both by the model architecture, which provides inductive bias to capture the hierarchy in the targets, and the joint modeling objective which allows the RNNG to learn richer representations. RNNG is efficient for modeling relations between entities or/and events in medical texts and its performances are close to those of a BiLSTM for entity and event detection.