OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Resource Allocation for Serverless Queries
Venue: arXiv cs.DB 2021
Year: 2021

Optimizing resource allocation for analytical workloads is vital for reducing costs of cloud-data services. At the same time, it is incredibly hard for users to allocate resources per query in serverless processing systems, and they frequently misallocate by orders of magnitude. Unfortunately, prior work focused on predicting peak allocation while ignoring aggressive trade-offs between resource allocation and run-time. Additionally, these methods fail to predict allocation for queries that have not been observed in the past. In this paper, we tackle both these problems. We introduce a system for optimal resource allocation that can predict performance with aggressive trade-offs, for both new and past observed queries. We introduce the notion of a performance characteristic curve (PCC) as a parameterized representation that can compactly capture the relationship between resources and performance. To tackle training data sparsity, we introduce a novel data augmentation technique to efficiently synthesize the entire PCC using a single run of the query. Lastly, we demonstrate the advantages of a constrained loss function coupled with GNNs, over traditional ML methods, for capturing the domain specific behavior through an extensive experimental evaluation over SCOPE big data workloads at Microsoft.
An Empirical Study on the "Usage of Not" in Real-World JSON Schema Documents (Long Version)
Venue: arXiv cs.DB 2021
Year: 2021

In this paper, we study the usage of negation in JSON Schema data modeling. Negation is a logical operator that is rarely present in type systems and schema description languages, since it complicates decision problems. As a consequence, many software tools, but also formal frameworks for working with JSON Schema, do not fully support negation. As of today, the question whether covering negation is practically relevant, or a mainly theoretical exercise (albeit challenging), is open. This motivates us to study whether negation is really used in practice, for which aims, and whether it could be - in principle - replaced by simpler operators. We have collected the most diverse corpus of JSON Schema documents analyzed so far, based on a crawl of 90k open source schemas hosted on GitHub. We perform a systematic analysis, quantify usage patterns of negation, and also qualitatively analyze schemas. We show that negation is indeed used, following a stable set of patterns, with the potential to mature into design patterns.
A New Distributed Method for Training Generative Adversarial Networks
Venue: arXiv cs.LG 2021
Year: 2021

Generative adversarial networks (GANs) are emerging machine learning models for generating synthesized data similar to real data by jointly training a generator and a discriminator. In many applications, data and computational resources are distributed over many devices, so centralized computation with all data in one location is infeasible due to privacy and/or communication constraints. This paper proposes a new framework for training GANs in a distributed fashion: Each device computes a local discriminator using local data; a single server aggregates their results and computes a global GAN. Specifically, in each iteration, the server sends the global GAN to the devices, which then update their local discriminators; the devices send their results to the server, which then computes their average as the global discriminator and updates the global generator accordingly. Two different update schedules are designed with different levels of parallelism between the devices and the server. Numerical results obtained using three popular datasets demonstrate that the proposed framework can outperform a state-of-the-art framework in terms of convergence speed.
Long-term series forecasting with Query Selector -- efficient model of sparse attention
Venue: arXiv cs.LG 2021
Year: 2021

Various modifications of TRANSFORMER were recently used to solve time-series forecasting problem. We propose Query Selector - an efficient, deterministic algorithm for sparse attention matrix. Experiments show it achieves state-of-the art results on ETT, Helpdesk and BPI'12 datasets.
ObserveNet Control: A Vision-Dynamics Learning Approach to Predictive Control in Autonomous Vehicles
Venue: arXiv cs.RO 2021
Year: 2021

A key component in autonomous driving is the ability of the self-driving car to understand, track and predict the dynamics of the surrounding environment. Although there is significant work in the area of object detection, tracking and observations prediction, there is no prior work demonstrating that raw observations prediction can be used for motion planning and control. In this paper, we propose ObserveNet Control, which is a vision-dynamics approach to the predictive control problem of autonomous vehicles. Our method is composed of a: i) deep neural network able to confidently predict future sensory data on a time horizon of up to 10s and ii) a temporal planner designed to compute a safe vehicle state trajectory based on the predicted sensory data. Given the vehicle's historical state and sensing data in the form of Lidar point clouds, the method aims to learn the dynamics of the observed driving environment in a self-supervised manner, without the need to manually specify training labels. The experiments are performed both in simulation and real-life, using CARLA and RovisLab's AMTU mobile platform as a 1:4 scaled model of a car. We evaluate the capabilities of ObserveNet Control in aggressive driving contexts, such as overtaking maneuvers or side cut-off situations, while comparing the results with a baseline Dynamic Window Approach (DWA) and two state-of-the-art imitation learning systems, that is, Learning by Cheating (LBC) and World on Rails (WOR).
Detecting Oxbow Code in Erlang Codebases with the Highest Degree of Certainty
Venue: arXiv cs.SE 2021
Year: 2021

The presence of source code that is no longer needed is a handicap to project maintainability. The larger and longer-lived the project, the higher the chances of accumulating dead code in its different forms. Manually detecting unused code is time-consuming, tedious, error-prone, and requires a great level of deep knowledge about the codebase. In this paper, we examine the kinds of dead code (specifically, oxbow code) that can appear in Erlang projects, and formulate rules to identify them with high accuracy. We also present an open-source static analyzer that implements these rules, allowing for the automatic detection and confident removal of oxbow code in Erlang codebases, actively contributing to increasing their quality and maintainability.
ZIPPER: Exploiting Tile- and Operator-level Parallelism for General and Scalable Graph Neural Network Acceleration
Venue: arXiv cs.AR 2021
Year: 2021

Graph neural networks (GNNs) start to gain momentum after showing significant performance improvement in a variety of domains including molecular science, recommendation, and transportation. Turning such performance improvement of GNNs into practical applications relies on effective and efficient execution, especially for inference. However, neither CPU nor GPU can meet these needs if considering both performance and energy efficiency. That's because accelerating GNNs is challenging due to their excessive memory usage and arbitrary interleaving of diverse operations. Besides, the semantics gap between the high-level GNN programming model and efficient hardware makes it difficult in accelerating general-domain GNNs. To address the challenge, we propose Zipper, an efficient yet general acceleration system for GNNs. The keys to Zipper include a graph-native intermediate representation (IR) and the associated compiler. By capturing GNN primitive operations and representing with GNN IR, Zipper is able to fit GNN semantics into hardware structure for efficient execution. The IR also enables GNN-specific optimizations including sparse graph tiling and redundant operation elimination. We further present an hardware architecture design consisting of dedicated blocks for different primitive operations, along with a run-time scheduler to map a IR program to the hardware blocks. Our evaluation shows that Zipper achieves 93.6x speedup and 147x energy reduction over Intel Xeon CPU, and 1.56x speedup and 4.85x energy reduction over NVIDIA V100 GPU on averages.
RECIST-Net: Lesion detection via grouping keypoints on RECIST-based annotation
Venue: arXiv cs.CV 2021
Year: 2021

Universal lesion detection in computed tomography (CT) images is an important yet challenging task due to the large variations in lesion type, size, shape, and appearance. Considering that data in clinical routine (such as the DeepLesion dataset) are usually annotated with a long and a short diameter according to the standard of Response Evaluation Criteria in Solid Tumors (RECIST) diameters, we propose RECIST-Net, a new approach to lesion detection in which the four extreme points and center point of the RECIST diameters are detected. By detecting a lesion as keypoints, we provide a more conceptually straightforward formulation for detection, and overcome several drawbacks (e.g., requiring extensive effort in designing data-appropriate anchors and losing shape information) of existing bounding-box-based methods while exploring a single-task, one-stage approach compared to other RECIST-based approaches. Experiments show that RECIST-Net achieves a sensitivity of 92.49% at four false positives per image, outperforming other recent methods including those using multi-task learning.
Cobordisms and commutative categorial grammars
Venue: arXiv cs.LO 2021
Year: 2021

We propose a concrete surface representation of abstract categorial grammars in the category of word cobordisms or cowordisms for short, which are certain bipartite graphs decorated with words in a given alphabet, generalizing linear logic proof-nets. We also introduce and study linear logic grammars, directly based on cobordisms and using classical multiplicative linear logic as a typing system.
Learning Attributed Graph Representations with Communicative Message Passing Transformer
Venue: arXiv cs.LG 2021
Year: 2021

Constructing appropriate representations of molecules lies at the core of numerous tasks such as material science, chemistry and drug designs. Recent researches abstract molecules as attributed graphs and employ graph neural networks (GNN) for molecular representation learning, which have made remarkable achievements in molecular graph modeling. Albeit powerful, current models either are based on local aggregation operations and thus miss higher-order graph properties or focus on only node information without fully using the edge information. For this sake, we propose a Communicative Message Passing Transformer (CoMPT) neural network to improve the molecular graph representation by reinforcing message interactions between nodes and edges based on the Transformer architecture. Unlike the previous transformer-style GNNs that treat molecules as fully connected graphs, we introduce a message diffusion mechanism to leverage the graph connectivity inductive bias and reduce the message enrichment explosion. Extensive experiments demonstrated that the proposed model obtained superior performances (around 4$\%$ on average) against state-of-the-art baselines on seven chemical property datasets (graph-level tasks) and two chemical shift datasets (node-level tasks). Further visualization studies also indicated a better representation capacity achieved by our model.
Deep Learning with Nonsmooth Objectives
Venue: arXiv cs.LG 2021
Year: 2021

We explore the potential for using a nonsmooth loss function based on the max-norm in the training of an artificial neural network. We hypothesise that this may lead to superior classification results in some special cases where the training data is either very small or unbalanced. Our numerical experiments performed on a simple artificial neural network with no hidden layers (a setting immediately amenable to standard nonsmooth optimisation techniques) appear to confirm our hypothesis that uniform approximation based approaches may be more suitable for the datasets with reliable training data that either is limited size or biased in terms of relative cluster sizes.
Revisiting the Primal-Dual Method of Multipliers for Optimisation over Centralised Networks
Venue: arXiv cs.DC 2021
Year: 2021

The primal-dual method of multipliers (PDMM) was originally designed for solving a decomposable optimisation problem over a general network. In this paper, we revisit PDMM for optimisation over a centralized network. We first note that the recently proposed method FedSplit [1] implements PDMM for a centralized network. In [1], Inexact FedSplit (i.e., gradient based FedSplit) was also studied both empirically and theoretically. We identify the cause for the poor reported performance of Inexact FedSplit, which is due to the improper initialisation in the gradient operations at the client side. To fix the issue of Inexact FedSplit, we propose two versions of Inexact PDMM, which are referred to as gradient-based PDMM (GPDMM) and accelerated GPDMM (AGPDMM), respectively. AGPDMM accelerates GPDMM at the cost of transmitting two times the number of parameters from the server to each client per iteration compared to GPDMM. We provide a new convergence bound for GPDMM for a class of convex optimisation problems. Our new bounds are tighter than those derived for Inexact FedSplit. We also investigate the update expressions of AGPDMM and SCAFFOLD to find their similarities. It is found that when the number K of gradient steps at the client side per iteration is K=1, both AGPDMM and SCAFFOLD reduce to vanilla gradient descent with proper parameter setup. Experimental results indicate that AGPDMM converges faster than SCAFFOLD when K>1 while GPDMM converges slightly worse than SCAFFOLD.
A Multi-UAV System for Exploration and Target Finding in Cluttered and GPS-Denied Environments
Venue: arXiv cs.RO 2021
Year: 2021

The use of multi-rotor Unmanned Aerial Vehicles (UAVs) for search and rescue as well as remote sensing is rapidly increasing. Multi-rotor UAVs, however, have limited endurance. The range of UAV applications can be widened if teams of multiple UAVs are used. We propose a framework for a team of UAVs to cooperatively explore and find a target in complex GPS-denied environments with obstacles. The team of UAVs autonomously navigates, explores, detects, and finds the target in a cluttered environment with a known map. Examples of such environments include indoor scenarios, urban or natural canyons, caves, and tunnels, where the GPS signal is limited or blocked. The framework is based on a probabilistic decentralised Partially Observable Markov Decision Process which accounts for the uncertainties in sensing and the environment. The team can cooperate efficiently, with each UAV sharing only limited processed observations and their locations during the mission. The system is simulated using the Robotic Operating System and Gazebo. Performance of the system with an increasing number of UAVs in several indoor scenarios with obstacles is tested. Results indicate that the proposed multi-UAV system has improvements in terms of time-cost, the proportion of search area surveyed, as well as successful rates for search and rescue missions.
Structured Proofs for Adversarial Cyber-Physical Systems
Venue: arXiv cs.LO 2021
Year: 2021

Many cyber-physical systems (CPS) are safety-critical, so it is important to formally verify them, e.g. in formal logics that show a model's correctness specification always holds. Constructive Differential Game Logic (CdGL) is such a logic for (constructive) hybrid games, including hybrid systems. To overcome undecidability, the user first writes a proof, for which we present a proof-checking tool. We introduce Kaisar, the first language and tool for CdGL proofs, which until now could only be written by hand with a low-level proof calculus. Kaisar's structured proofs simplify challenging CPS proof tasks, especially by using programming language principles and high-level stateful reasoning. Kaisar exploits CdGL's constructivity and refinement relations to build proofs around models of game strategies. The evaluation reproduces and extends existing case studies on 1D and 2D driving. Proof metrics are compared and reported experiences are discussed for the original studies and their reproductions.
Energy Efficient Data Recovery from Corrupted LoRa Frames
Venue: arXiv cs.IT 2021
Year: 2021

High frame-corruption is widely observed in Long Range Wide Area Networks (LoRaWAN) due to the coexistence with other networks in ISM bands and an Aloha-like MAC layer. LoRa's Forward Error Correction (FEC) mechanism is often insufficient to retrieve corrupted data. In fact, real-life measurements show that at least one-fourth of received transmissions are corrupted. When more frames are dropped, LoRa nodes usually switch over to higher spreading factors (SF), thus increasing transmission times and increasing the required energy. This paper introduces ReDCoS, a novel coding technique at the application layer that improves recovery of corrupted LoRa frames, thus reducing the overall transmission time and energy invested by LoRa nodes by several-fold. ReDCoS utilizes lightweight coding techniques to pre-encode the transmitted data. Therefore, the inbuilt Cyclic Redundancy Check (CRC) that follows is computed based on an already encoded data. At the receiver, we use both the CRC and the coded data to recover data from a corrupted frame beyond the built-in Error Correcting Code (ECC). We compare the performance of ReDCoS to (I) the standard FEC of vanilla-LoRaWAN, and to (ii) RS coding applied as ECC to the data of LoRaWAN. The results indicated a 54x and 13.5x improvement of decoding ratio, respectively, when 20 data symbols were sent. Furthermore, we evaluated ReDCoS on-field using LoRa SX1261 transceivers showing that it outperformed RS-coding by factor of at least 2x (and up to 6x) in terms of the decoding ratio while consuming 38.5% less energy per correctly received transmission.
Over-Parameterization and Generalization in Audio Classification
Venue: arXiv cs.SD 2021
Year: 2021

Convolutional Neural Networks (CNNs) have been dominating classification tasks in various domains, such as machine vision, machine listening, and natural language processing. In machine listening, while generally exhibiting very good generalization capabilities, CNNs are sensitive to the specific audio recording device used, which has been recognized as a substantial problem in the acoustic scene classification (DCASE) community. In this study, we investigate the relationship between over-parameterization of acoustic scene classification models, and their resulting generalization abilities. Specifically, we test scaling CNNs in width and depth, under different conditions. Our results indicate that increasing width improves generalization to unseen devices, even without an increase in the number of parameters.
Using automated decision-making (ADM) to allocate Covid-19 vaccinations? Exploring the roles of trust and social group preference on the legitimacy of ADM vs. human decision-making
Venue: arXiv cs.CY 2021
Year: 2021

In combating the ongoing global health threat of the Covid-19 pandemic, decision-makers have to take actions based on a multitude of relevant health data with severe potential consequences for the affected patients. Because of their presumed advantages in handling and analyzing vast amounts of data, computer systems of automated decision-making (ADM) are implemented and substitute humans in decision-making processes. In this study, we focus on a specific application of ADM in contrast to human decision-making (HDM), namely the allocation of Covid-19 vaccines to the public. In particular, we elaborate on the role of trust and social group preference on the legitimacy of vaccine allocation. We conducted a survey with a 2x2 randomized factorial design among n=1602 German respondents, in which we utilized distinct decision-making agents (HDM vs. ADM) and prioritization of a specific social group (teachers vs. prisoners) as design factors. Our findings show that general trust in ADM systems and preference for vaccination of a specific social group influence the legitimacy of vaccine allocation. However, contrary to our expectations, trust in the agent making the decision did not moderate the link between social group preference and legitimacy. Moreover, the effect was also not moderated by the type of decision-maker (human vs. algorithm). We conclude that trustworthy ADM systems must not necessarily lead to the legitimacy of ADM systems.
A Benchmark for Gait Recognition under Occlusion Collected by Multi-Kinect SDAS
Venue: arXiv cs.CV 2021
Year: 2021

Human gait is one of important biometric characteristics for human identification at a distance. In practice, occlusion usually occurs and seriously affects accuracy of gait recognition. However, there is no available database to support in-depth research of this problem, and state-of-arts gait recognition methods have not paid enough attention to it, thus this paper focuses on gait recognition under occlusion. We collect a new gait recognition database called OG RGB+D database, which breaks through the limitation of other gait databases and includes multimodal gait data of various occlusions (self-occlusion, active occlusion, and passive occlusion) by our multiple synchronous Azure Kinect DK sensors data acquisition system (multi-Kinect SDAS) that can be also applied in security situations. Because Azure Kinect DK can simultaneously collect multimodal data to support different types of gait recognition algorithms, especially enables us to effectively obtain camera-centric multi-person 3D poses, and multi-view is better to deal with occlusion than single-view. In particular, the OG RGB+D database provides accurate silhouettes and the optimized human 3D joints data (OJ) by fusing data collected by multi-Kinects which are more accurate in human pose representation under occlusion. We also use the OJ data to train an advanced 3D multi-person pose estimation model to improve its accuracy of pose estimation under occlusion for universality. Besides, as human pose is less sensitive to occlusion than human appearance, we propose a novel gait recognition method SkeletonGait based on human dual skeleton model using a framework of siamese spatio-temporal graph convolutional networks (siamese ST-GCN). The evaluation results demonstrate that SkeletonGait has competitive performance compared with state-of-art gait recognition methods on OG RGB+D database and popular CAISA-B database.
Prediction of the final rank of Players in PUBG with the optimal number of features
Venue: arXiv cs.LG 2021
Year: 2021

PUBG is an online video game that has become very popular among the youths in recent years. Final rank, which indicates the performance of a player, is one of the most important feature for this game. This paper focuses on predicting the final rank of the players based on their skills and abilities. In this paper we have used different machine learning algorithms to predict the final rank of the players on a dataset obtained from kaggle which has 29 features. Using the correlation heatmap,we have varied the number of features used for the model. Out of these models GBR and LGBM have given the best result with the accuracy of 91.63% and 91.26% respectively for 14 features and the accuracy of 90.54% and 90.01% for 8 features. Although the accuracy of the models with 14 features is slightly better than 8 features, the empirical time taken by 8 features is 1.4x lesser than 14 features for LGBM and 1.5x lesser for GBR. Furthermore, reducing the number of features any more significantly hampers the performance of all the ML models. Therefore, we conclude that 8 is the optimal number of features that can be used to predict the final rank of a player in PUBG with high accuracy and low run-time.