OpenRaiser/Intern-Atlas huggingface dataset:
Simulating Population Protocols in Sub-Constant Time per Interaction
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of efficiently simulating population protocols. In the population model, we are given a distributed system of $n$ agents modeled as identical finite-state machines. In each time step, a pair of agents is selected uniformly at random to interact. In an interaction, agents update their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the performance of these simulators is the data structure storing the agents' states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out $2^{50}$ interactions among the same number of agents in less than 400s.
COVID-19 Contact-tracing Apps: a Survey on the Global Deployment and Challenges
Venue: arXiv cs.CR 2020
Year: 2020

To address the massive spike in uncertainties triggered by the coronavirus disease (COVID-19), there is an ever-increasing number of national governments that are rolling out contact-tracing Apps to aid the containment of the virus. The first hugely contentious issue facing the Apps is the deployment framework, i.e. centralized or decentralized. Based on this, the debate branches out to the corresponding technologies that underpin these architectures, i.e. GPS, QR codes, and Bluetooth. This work conducts a pioneering review of the above scenarios and contributes a geolocation mapping of the current deployment. The Apps vulnerabilities and the directions of research are identified, with a special focus on the Bluetooth-inspired decentralized paradigm.
Real-Time Context-aware Detection of Unsafe Events in Robot-Assisted Surgery
Venue: arXiv cs.RO 2020
Year: 2020

Cyber-physical systems for robotic surgery have enabled minimally invasive procedures with increased precision and shorter hospitalization. However, with increasing complexity and connectivity of software and major involvement of human operators in the supervision of surgical robots, there remain significant challenges in ensuring patient safety. This paper presents a safety monitoring system that, given the knowledge of the surgical task being performed by the surgeon, can detect safety-critical events in real-time. Our approach integrates a surgical gesture classifier that infers the operational context from the time-series kinematics data of the robot with a library of erroneous gesture classifiers that given a surgical gesture can detect unsafe events. Our experiments using data from two surgical platforms show that the proposed system can detect unsafe events caused by accidental or malicious faults within an average reaction time window of 1,693 milliseconds and F1 score of 0.88 and human errors within an average reaction time window of 57 milliseconds and F1 score of 0.76.
Regularized Pooling
Venue: arXiv cs.CV 2020
Year: 2020

In convolutional neural networks (CNNs), pooling operations play important roles such as dimensionality reduction and deformation compensation. In general, max pooling, which is the most widely used operation for local pooling, is performed independently for each kernel. However, the deformation may be spatially smooth over the neighboring kernels. This means that max pooling is too flexible to compensate for actual deformations. In other words, its excessive flexibility risks canceling the essential spatial differences between classes. In this paper, we propose regularized pooling, which enables the value selection direction in the pooling operation to be spatially smooth across adjacent kernels so as to compensate only for actual deformations. The results of experiments on handwritten character images and texture images showed that regularized pooling not only improves recognition accuracy but also accelerates the convergence of learning compared with conventional pooling operations.
Mapping Natural Language Instructions to Mobile UI Action Sequences
Venue: arXiv cs.CL 2020
Year: 2020

We present a new problem: grounding natural language instructions to mobile user interface actions, and create three new datasets for it. For full task evaluation, we create PIXELHELP, a corpus that pairs English instructions with actions performed by people on a mobile UI emulator. To scale training, we decouple the language and action data by (a) annotating action phrase spans in HowTo instructions and (b) synthesizing grounded descriptions of actions for mobile user interfaces. We use a Transformer to extract action phrase tuples from long-range natural language instructions. A grounding Transformer then contextually represents UI objects using both their content and screen position and connects them to object descriptions. Given a starting screen and instruction, our model achieves 70.59% accuracy on predicting complete ground-truth action sequences in PIXELHELP.
Modeling Human Visual Search Performance on Realistic Webpages Using Analytical and Deep Learning Methods
Venue: arXiv cs.HC 2020
Year: 2020

Modeling visual search not only offers an opportunity to predict the usability of an interface before actually testing it on real users, but also advances scientific understanding about human behavior. In this work, we first conduct a set of analyses on a large-scale dataset of visual search tasks on realistic webpages. We then present a deep neural network that learns to predict the scannability of webpage content, i.e., how easy it is for a user to find a specific target. Our model leverages both heuristic-based features such as target size and unstructured features such as raw image pixels. This approach allows us to model complex interactions that might be involved in a realistic visual search task, which can not be easily achieved by traditional analytical models. We analyze the model behavior to offer our insights into how the salience map learned by the model aligns with human intuition and how the learned semantic representation of each target type relates to its visual search performance.
GOBO: Quantizing Attention-Based NLP Models for Low Latency and Energy Efficient Inference
Venue: arXiv cs.LG 2020
Year: 2020

Attention-based models have demonstrated remarkable success in various natural language understanding tasks. However, efficient execution remains a challenge for these models which are memory-bound due to their massive number of parameters. We present GOBO, a model quantization technique that compresses the vast majority (typically 99.9%) of the 32-bit floating-point parameters of state-of-the-art BERT models and their variants to 3 bits while maintaining their accuracy. Unlike other quantization methods, GOBO does not require fine-tuning nor retraining to compensate for the quantization error. We present two practical hardware applications of GOBO. In the first GOBO reduces memory storage and traffic and as a result inference latency and energy consumption. This GOBO memory compression mechanism is plug-in compatible with many architectures; we demonstrate it with the TPU, Eyeriss, and an architecture using Tensor Cores-like units. Second, we present a co-designed hardware architecture that also reduces computation. Uniquely, the GOBO architecture maintains most of the weights in 3b even during computation, a property that: (1) makes the processing elements area efficient, allowing us to pack more compute power per unit area, (2) replaces most multiply-accumulations with additions, and (3) reduces the off-chip traffic by amplifying on-chip memory capacity.
Distilling Knowledge from Pre-trained Language Models via Text Smoothing
Venue: arXiv cs.CL 2020
Year: 2020

This paper studies compressing pre-trained language models, like BERT (Devlin et al.,2019), via teacher-student knowledge distillation. Previous works usually force the student model to strictly mimic the smoothed labels predicted by the teacher BERT. As an alternative, we propose a new method for BERT distillation, i.e., asking the teacher to generate smoothed word ids, rather than labels, for teaching the student model in knowledge distillation. We call this kind of methodTextSmoothing. Practically, we use the softmax prediction of the Masked Language Model(MLM) in BERT to generate word distributions for given texts and smooth those input texts using that predicted soft word ids. We assume that both the smoothed labels and the smoothed texts can implicitly augment the input corpus, while text smoothing is intuitively more efficient since it can generate more instances in one neural network forward step.Experimental results on GLUE and SQuAD demonstrate that our solution can achieve competitive results compared with existing BERT distillation methods.
An Extensive Study on Cross-Dataset Bias and Evaluation Metrics Interpretation for Machine Learning applied to Gastrointestinal Tract Abnormality Classification
Venue: arXiv cs.LG 2020
Year: 2020

Precise and efficient automated identification of Gastrointestinal (GI) tract diseases can help doctors treat more patients and improve the rate of disease detection and identification. Currently, automatic analysis of diseases in the GI tract is a hot topic in both computer science and medical-related journals. Nevertheless, the evaluation of such an automatic analysis is often incomplete or simply wrong. Algorithms are often only tested on small and biased datasets, and cross-dataset evaluations are rarely performed. A clear understanding of evaluation metrics and machine learning models with cross datasets is crucial to bring research in the field to a new quality level. Towards this goal, we present comprehensive evaluations of five distinct machine learning models using Global Features and Deep Neural Networks that can classify 16 different key types of GI tract conditions, including pathological findings, anatomical landmarks, polyp removal conditions, and normal findings from images captured by common GI tract examination instruments. In our evaluation, we introduce performance hexagons using six performance metrics such as recall, precision, specificity, accuracy, F1-score, and Matthews Correlation Coefficient to demonstrate how to determine the real capabilities of models rather than evaluating them shallowly. Furthermore, we perform cross-dataset evaluations using different datasets for training and testing. With these cross-dataset evaluations, we demonstrate the challenge of actually building a generalizable model that could be used across different hospitals. Our experiments clearly show that more sophisticated performance metrics and evaluation methods need to be applied to get reliable models rather than depending on evaluations of the splits of the same dataset, i.e., the performance metrics should always be interpreted together rather than relying on a single metric.
Modeling Document Interactions for Learning to Rank with Regularized Self-Attention
Venue: arXiv cs.IR 2020
Year: 2020

Learning to rank is an important task that has been successfully deployed in many real-world information retrieval systems. Most existing methods compute relevance judgments of documents independently, without holistically considering the entire set of competing documents. In this paper, we explore modeling documents interactions with self-attention based neural networks. Although self-attention networks have achieved state-of-the-art results in many NLP tasks, we find empirically that self-attention provides little benefit over baseline neural learning to rank architecture. To improve the learning of self-attention weights, We propose simple yet effective regularization terms designed to model interactions between documents. Evaluations on publicly available Learning to Rank (LETOR) datasets show that training self-attention network with our proposed regularization terms can significantly outperform existing learning to rank methods.
Graphic Lattices and Matrix Lattices Of Topological Coding
Venue: arXiv cs.IT 2020
Year: 2020

Lattice-based Cryptography is considered to have the characteristics of classical computers and quantum attack resistance. We will design various graphic lattices and matrix lattices based on knowledge of graph theory and topological coding, since many problems of graph theory can be expressed or illustrated by (colored) star-graphic lattices. A new pair of the leaf-splitting operation and the leaf-coinciding operation will be introduced, and we combine graph colorings and graph labellings to design particular proper total colorings as tools to build up various graphic lattices, graph homomorphism lattice, graphic group lattices and Topcode-matrix lattices. Graphic group lattices and (directed) Topcode-matrix lattices enable us to build up connections between traditional lattices and graphic lattices. We present mathematical problems encountered in researching graphic lattices, some problems are: Tree topological authentication, Decompose graphs into Hanzi-graphs, Number String Decomposition Problem, $(p,s)$-gracefully total numbers.
On the complexity of computing integral bases of function fields
Venue: arXiv cs.SC 2020
Year: 2020

Let $\mathcal{C}$ be a plane curve given by an equation $f(x,y)=0$ with $f\in K[x][y]$ a monic squarefree polynomial. We study the problem of computing an integral basis of the algebraic function field $K(\mathcal{C})$ and give new complexity bounds for three known algorithms dealing with this problem. For each algorithm, we study its subroutines and, when it is possible, we modify or replace them so as to take advantage of faster primitives. Then, we combine complexity results to derive an overall complexity estimate for each algorithm. In particular, we modify an algorithm due to Böhm et al. and achieve a quasi-optimal runtime.
Sentiment Analysis Using Simplified Long Short-term Memory Recurrent Neural Networks
Venue: arXiv cs.CL 2020
Year: 2020

LSTM or Long Short Term Memory Networks is a specific type of Recurrent Neural Network (RNN) that is very effective in dealing with long sequence data and learning long term dependencies. In this work, we perform sentiment analysis on a GOP Debate Twitter dataset. To speed up training and reduce the computational cost and time, six different parameter reduced slim versions of the LSTM model (slim LSTM) are proposed. We evaluate two of these models on the dataset. The performance of these two LSTM models along with the standard LSTM model is compared. The effect of Bidirectional LSTM Layers is also studied. The work also consists of a study to choose the best architecture, apart from establishing the best set of hyper parameters for different LSTM Models.
On the Effect of Learned Clauses on Stochastic Local Search
Venue: arXiv cs.AI 2020
Year: 2020

There are two competing paradigms in successful SAT solvers: Conflict-driven clause learning (CDCL) and stochastic local search (SLS). CDCL uses systematic exploration of the search space and has the ability to learn new clauses. SLS examines the neighborhood of the current complete assignment. Unlike CDCL, it lacks the ability to learn from its mistakes. This work revolves around the question whether it is beneficial for SLS to add new clauses to the original formula. We experimentally demonstrate that clauses with a large number of correct literals w. r. t. a fixed solution are beneficial to the runtime of SLS. We call such clauses high-quality clauses. Empirical evaluations show that short clauses learned by CDCL possess the high-quality attribute. We study several domains of randomly generated instances and deduce the most beneficial strategies to add high-quality clauses as a preprocessing step. The strategies are implemented in an SLS solver, and it is shown that this considerably improves the state-of-the-art on randomly generated instances. The results are statistically significant.
Multi-Winner Election Control via Social Influence
Venue: arXiv cs.SI 2020
Year: 2020

In an election, we are given a set of voters, each having a preference list over a set of candidates, that are distributed on a social network. We consider a scenario where voters may change their preference lists as a consequence of the messages received by their neighbors in a social network. Specifically, we consider a political campaign that spreads messages in a social network in support or against a given candidate and the spreading follows a dynamic model for information diffusion. When a message reaches a voter, this latter changes its preference list according to an update rule. The election control problem asks to find a bounded set of nodes to be the starter of a political campaign in support (constructive problem) or against (destructive problem) a given target candidate $c$, in such a way that the margin of victory of $c$ w.r.t. its most voted opponents is maximized. It has been shown that several variants of the problem can be solved within a constant factor approximation of the optimum, which shows that controlling elections by means of social networks is doable and constitutes a real problem for modern democracies. Most of the literature, however, focuses on the case of single-winner elections. In this paper, we define the election control problem in social networks for "multi-winner elections" with the aim of modeling parliamentarian elections. Differently from the single-winner case, we show that the multi-winner election control problem is NP-hard to approximate within any factor in both constructive and destructive cases. We then study a relaxation of the problem where votes are aggregated on the basis of parties (instead of single candidates), which is a variation of the so-called "straight-party voting" used in some real parliamentarian elections. We show that the latter problem remains NP-hard but can be approximated within a constant factor.
Lossy Compression with Distortion Constrained Optimization
Venue: arXiv cs.LG 2020
Year: 2020

When training end-to-end learned models for lossy compression, one has to balance the rate and distortion losses. This is typically done by manually setting a tradeoff parameter $β$, an approach called $β$-VAE. Using this approach it is difficult to target a specific rate or distortion value, because the result can be very sensitive to $β$, and the appropriate value for $β$ depends on the model and problem setup. As a result, model comparison requires extensive per-model $β$-tuning, and producing a whole rate-distortion curve (by varying $β$) for each model to be compared. We argue that the constrained optimization method of Rezende and Viola, 2018 is a lot more appropriate for training lossy compression models because it allows us to obtain the best possible rate subject to a distortion constraint. This enables pointwise model comparisons, by training two models with the same distortion target and comparing their rate. We show that the method does manage to satisfy the constraint on a realistic image compression task, outperforms a constrained optimization method based on a hinge-loss, and is more practical to use for model selection than a $β$-VAE.
Importing Relationships into a Running Graph Database Using Parallel Processing
Venue: arXiv cs.DC 2020
Year: 2020

Importing relationships into a running graph database using multiple threads running concurrently is a difficult task, as multiple threads cannot write information to the same node at the same time. Here we present an algorithm in which relationships are sorted into bins, then imported such that no two threads ever access the same node concurrently. When this algorithm was implemented as a procedure to run on the Neo4j graph database, it reduced the time to import relationships by up to 69% when 32 threads were used.
Behind the Last Line of Defense -- Surviving SoC Faults and Intrusions
Venue: arXiv cs.DC 2020
Year: 2020

Today, leveraging the enormous modular power, diversity and flexibility of manycore systems-on-a-chip (SoCs) requires careful orchestration of complex resources, a task left to low-level software, e.g. hypervisors. In current architectures, this software forms a single point of failure and worthwhile target for attacks: once compromised, adversaries gain access to all information and full control over the platform and the environment it controls. This paper proposes Midir, an enhanced manycore architecture, effecting a paradigm shift from SoCs to distributed SoCs. Midir changes the way platform resources are controlled, by retrofitting tile-based fault containment through well known mechanisms, while securing low-overhead quorum-based consensus on all critical operations, in particular privilege management and, thus, management of containment domains. Allowing versatile redundancy management, Midir promotes resilience for all software levels, including at low level. We explain this architecture, its associated algorithms and hardware mechanisms and show, for the example of a Byzantine fault tolerant microhypervisor, that it outperforms the highly efficient MinBFT by one order of magnitude.
K-EmoCon, a multimodal sensor dataset for continuous emotion recognition in naturalistic conversations
Venue: arXiv cs.HC 2020
Year: 2020

Recognizing emotions during social interactions has many potential applications with the popularization of low-cost mobile sensors, but a challenge remains with the lack of naturalistic affective interaction data. Most existing emotion datasets do not support studying idiosyncratic emotions arising in the wild as they were collected in constrained environments. Therefore, studying emotions in the context of social interactions requires a novel dataset, and K-EmoCon is such a multimodal dataset with comprehensive annotations of continuous emotions during naturalistic conversations. The dataset contains multimodal measurements, including audiovisual recordings, EEG, and peripheral physiological signals, acquired with off-the-shelf devices from 16 sessions of approximately 10-minute long paired debates on a social issue. Distinct from previous datasets, it includes emotion annotations from all three available perspectives: self, debate partner, and external observers. Raters annotated emotional displays at intervals of every 5 seconds while viewing the debate footage, in terms of arousal-valence and 18 additional categorical emotions. The resulting K-EmoCon is the first publicly available emotion dataset accommodating the multiperspective assessment of emotions during social interactions.