OpenRaiser/Intern-Atlas huggingface dataset:
Still Simpler Static Level Ancestors
Venue: arXiv cs.DS 2020
Year: 2020

A level-ancestor or LA query about a rooted tree $T$ takes as arguments a node $v$ in $T$, of depth $d_v$, say, and an integer $d$ with $0\le d\le d_v$ and returns the ancestor of $v$ in $T$ of depth $d$. The static LA problem is to process a given rooted tree $T$ so as to support efficient subsequent processing of LA queries about $T$. All previous efficient solutions to the static LA problem work by reducing a given instance of the problem to a smaller instance of the same or a related problem, solved with a less efficient data structure, and a collection of small micro-instances for which a different solution is provided. We indicate the first efficient solution to the static LA problem that works directly, without resorting to reductions or micro-instances.
VoteAgain: A scalable coercion-resistant voting system
Venue: arXiv cs.CR 2020
Year: 2020

The strongest threat model for voting systems considers coercion resistance: protection against coercers that force voters to modify their votes, or to abstain. Existing remote voting systems either do not provide this property; require an expensive tallying phase; or burden users with the need to store cryptographic key material and with the responsibility to deceive their coercers. We propose VoteAgain, a scalable voting scheme that relies on the revoting paradigm to provide coercion resistance. VoteAgain uses a novel deterministic ballot padding mechanism to ensure that coercers cannot see whether a vote has been replaced. This mechanism ensures tallies take quasilinear time, making VoteAgain the first revoting scheme that can handle elections with millions of voters. We prove that VoteAgain provides ballot privacy, coercion resistance, and verifiability; and we demonstrate its scalability using a prototype implementation of all cryptographic primitives.
A Dynamic Tree Algorithm for On-demand Peer-to-peer Ride-sharing Matching
Venue: arXiv cs.DS 2020
Year: 2020

Innovative shared mobility services provide on-demand flexible mobility options and have the potential to alleviate traffic congestion. These attractive services are challenging from different perspectives. One major challenge in such systems is to find suitable ride-sharing matchings between drivers and passengers with respect to the system objective and constraints, and to provide optimal pickup and drop-off sequence to the drivers. In this paper, we develop an efficient dynamic tree algorithm to find the optimal pickup and drop-off sequence. The algorithm finds an initial solution to the problem, keeps track of previously explored feasible solutions, and reduces the solution search space when considering new requests. In addition, an efficient pre-processing procedure to select candidate passenger requests is proposed, which further improves the algorithm performance. Numerical experiments are conducted on a real size network to illustrate the efficiency of our algorithm. Sensitivity analysis suggests that small vehicle capacities and loose excess travel time constraints do not guarantee overall savings in vehicle kilometer traveled.
Updating Weight Values for Function Point Counting
Venue: arXiv cs.SE 2020
Year: 2020

While software development productivity has grown rapidly, the weight values assigned to count standard Function Point (FP) created at IBM twenty-five years ago have never been updated. This obsolescence raises critical questions about the validity of the weight values; it also creates other problems such as ambiguous classification, crisp boundary, as well as subjective and locally defined weight values. All of these challenges reveal the need to calibrate FP in order to reflect both the specific software application context and the trend of todays software development techniques more accurately. We have created a FP calibration model that incorporates the learning ability of neural networks as well as the capability of capturing human knowledge using fuzzy logic. The empirical validation using ISBSG Data Repository (release 8) shows an average improvement of 22% in the accuracy of software effort estimations with the new calibration.
Predicting Video features from EEG and Vice versa
Venue: arXiv cs.CV 2020
Year: 2020

In this paper we explore predicting facial or lip video features from electroencephalography (EEG) features and predicting EEG features from recorded facial or lip video frames using deep learning models. The subjects were asked to read out loud English sentences shown to them on a computer screen and their simultaneous EEG signals and facial video frames were recorded. Our model was able to generate very broad characteristics of the facial or lip video frame from input EEG features. Our results demonstrate the first step towards synthesizing high quality facial or lip video from recorded EEG features. We demonstrate results for a data set consisting of seven subjects.
Character-level Transformer-based Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Neural machine translation (NMT) is nowadays commonly applied at the subword level, using byte-pair encoding. A promising alternative approach focuses on character-level translation, which simplifies processing pipelines in NMT considerably. This approach, however, must consider relatively longer sequences, rendering the training process prohibitively expensive. In this paper, we discuss a novel, Transformer-based approach, that we compare, both in speed and in quality to the Transformer at subword and character levels, as well as previously developed character-level models. We evaluate our models on 4 language pairs from WMT'15: DE-EN, CS-EN, FI-EN and RU-EN. The proposed novel architecture can be trained on a single GPU and is 34% percent faster than the character-level Transformer; still, the obtained results are at least on par with it. In addition, our proposed model outperforms the subword-level model in FI-EN and shows close results in CS-EN. To stimulate further research in this area and close the gap with subword-level NMT, we make all our code and models publicly available.
CAPre: Code-Analysis based Prefetching for Persistent Object Stores
Venue: arXiv cs.DB 2020
Year: 2020

Data prefetching aims to improve access times to data storage systems by predicting data records that are likely to be accessed by subsequent requests and retrieving them into a memory cache before they are needed. In the case of Persistent Object Stores, previous approaches to prefetching have been based on predictions made through analysis of the store's schema, which generates rigid predictions, or monitoring access patterns to the store while applications are executed, which introduces memory and/or computation overhead. In this paper, we present CAPre, a novel prefetching system for Persistent Object Stores based on static code analysis of object-oriented applications. CAPre generates the predictions at compile-time and does not introduce any overhead to the application execution. Moreover, CAPre is able to predict large amounts of objects that will be accessed in the near future, thus enabling the object store to perform parallel prefetching if the objects are distributed, in a much more aggressive way than in schema-based prediction algorithms. We integrate CAPre into a distributed Persistent Object Store and run a series of experiments that show that it can reduce the execution time of applications from 9% to over 50%, depending on the nature of the application and its persistent data model.
Comparative Study of Machine Learning Models and BERT on SQuAD
Venue: arXiv cs.CL 2020
Year: 2020

This study aims to provide a comparative analysis of performance of certain models popular in machine learning and the BERT model on the Stanford Question Answering Dataset (SQuAD). The analysis shows that the BERT model, which was once state-of-the-art on SQuAD, gives higher accuracy in comparison to other models. However, BERT requires a greater execution time even when only 100 samples are used. This shows that with increasing accuracy more amount of time is invested in training the data. Whereas in case of preliminary machine learning models, execution time for full data is lower but accuracy is compromised.
Empowering Multilevel DSMLs with Integrated Runtime Verification
Venue: arXiv cs.SE 2020
Year: 2020

Within Model-Driven Software Engineering, Domain-Specific Modelling has proven to be a powerful technique to specify systems and systems' behaviour in a formal, yet understandable way. Runtime verification (RV) has been successfully used to verify the correctness of such behaviour. Specifying behaviour requires managing various levels of abstractions, making multilevel modelling (MLM) a suitable approach for this task. In this paper, we present an approach to combine MLM and RV with an example from the domain of distributed real-time systems. The semantics of the specified behaviour as well as the evaluation of correctness properties are given by model transformation rules. This facilitates simulation of the system and checking against real-time temporal logic correctness properties.
One of these (Few) Things is Not Like the Others
Venue: arXiv cs.CV 2020
Year: 2020

To perform well, most deep learning based image classification systems require large amounts of data and computing resources. These constraints make it difficult to quickly personalize to individual users or train models outside of fairly powerful machines. To deal with these problems, there has been a large body of research into teaching machines to learn to classify images based on only a handful of training examples, a field known as few-shot learning. Few-shot learning research traditionally makes the simplifying assumption that all images belong to one of a fixed number of previously seen groups. However, many image datasets, such as a camera roll on a phone, will be noisy and contain images that may not be relevant or fit into any clear group. We propose a model which can both classify new images based on a small number of examples and recognize images which do not belong to any previously seen group. We adapt previous few-shot learning work to include a simple mechanism for learning a cutoff that determines whether an image should be excluded or classified. We examine how well our method performs in a realistic setting, benchmarking the approach on a noisy and ambiguous dataset of images. We evaluate performance over a spectrum of model architectures, including setups small enough to be run on low powered devices, such as mobile phones or web browsers. We find that this task of excluding irrelevant images poses significant extra difficulty beyond that of the traditional few-shot task. We decompose the sources of this error, and suggest future improvements that might alleviate this difficulty.
Designing with Static Capabilities and Effects: Use, Mention, and Invariants
Venue: arXiv cs.PL 2020
Year: 2020

Capabilities (whether object or reference capabilities) are fundamentally tools to restrict effects. Thus static capabilities (object or reference) and effect systems take different technical machinery to the same core problem of statically restricting or reasoning about effects in programs. Any time two approaches can in principle address the same sets of problems, it becomes important to understand the trade-offs between the approaches, how these trade-offs might interact with the problem at hand. Experts who have worked in these areas tend to find the trade-offs somewhat obvious, having considered them in context before. However, this kind of design discussion is often written down only implicitly as comparison between two approaches for a specific program reasoning problem, rather than as a discussion of general trade-offs between general classes of techniques. As a result, it is not uncommon to set out to solve a problem with one technique, only to find the other better-suited. We discuss the trade-offs between static capabilities (specifically reference capabilities) and effect systems, articulating the challenges each approach tends to have in isolation, and how these are sometimes mitigated. We also put our discussion in context, by appealing to examples of how these trade-offs were considered in the course of developing prior systems in the area. Along the way, we highlight how seemingly-minor aspects of type systems -- weakening/framing and the mere existence of type contexts -- play a subtle role in the efficacy of these systems.
Delving into the Imbalance of Positive Proposals in Two-stage Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

Imbalance issue is a major yet unsolved bottleneck for the current object detection models. In this work, we observe two crucial yet never discussed imbalance issues. The first imbalance lies in the large number of low-quality RPN proposals, which makes the R-CNN module (i.e., post-classification layers) become highly biased towards the negative proposals in the early training stage. The second imbalance stems from the unbalanced ground-truth numbers across different testing images, resulting in the imbalance of the number of potentially existing positive proposals in testing phase. To tackle these two imbalance issues, we incorporates two innovations into Faster R-CNN: 1) an R-CNN Gradient Annealing (RGA) strategy to enhance the impact of positive proposals in the early training stage. 2) a set of Parallel R-CNN Modules (PRM) with different positive/negative sampling ratios during training on one same backbone. Our RGA and PRM can totally bring 2.0% improvements on AP on COCO minival. Experiments on CrowdHuman further validates the effectiveness of our innovations across various kinds of object detection tasks.
Self-Training for Domain Adaptive Scene Text Detection
Venue: arXiv cs.CV 2020
Year: 2020

Though deep learning based scene text detection has achieved great progress, well-trained detectors suffer from severe performance degradation for different domains. In general, a tremendous amount of data is indispensable to train the detector in the target domain. However, data collection and annotation are expensive and time-consuming. To address this problem, we propose a self-training framework to automatically mine hard examples with pseudo-labels from unannotated videos or images. To reduce the noise of hard examples, a novel text mining module is implemented based on the fusion of detection and tracking results. Then, an image-to-video generation method is designed for the tasks that videos are unavailable and only images can be used. Experimental results on standard benchmarks, including ICDAR2015, MSRA-TD500, ICDAR2017 MLT, demonstrate the effectiveness of our self-training method. The simple Mask R-CNN adapted with self-training and fine-tuned on real data can achieve comparable or even superior results with the state-of-the-art methods.
A Comprehensive Study on Software Aging across Android Versions and Vendors
Venue: arXiv cs.SE 2020
Year: 2020

This paper analyzes the phenomenon of software aging - namely, the gradual performance degradation and resource exhaustion in the long run - in the Android OS. The study intends to highlight if, and to what extent, devices from different vendors, under various usage conditions and configurations, are affected by software aging and which parts of the system are the main contributors. The results demonstrate that software aging systematically determines a gradual loss of responsiveness perceived by the user, and an unjustified depletion of physical memory. The analysis reveals differences in the aging trends due to the workload factors and to the type of running applications, as well as differences due to vendors' customization. Moreover, we analyze several system-level metrics to trace back the software aging effects to their main causes. We show that bloated Java containers are a significant contributor to software aging, and that it is feasible to mitigate aging through a micro-rejuvenation solution at the container level.
A traceability and auditing framework for electronic equipment reverse logistics based on blockchain: the case of mobile phones
Venue: arXiv cs.CY 2020
Year: 2020

Human beings produce electronic waste (e-waste) at an unprecedented pace. Mobile phones and other inter-connected smart devices make a significant contribution to the generation of e-waste. Reverse logistics (RL) activities play an essential role in managing mobile phones during their end-of-life. However, remanufacturing and/or refurbishing of mobile phones might prove difficult not only from an operational point of view but also from a data management and privacy perspective (due to privacy-related regulatory frameworks like the EU General Data Protection Regulation directive). In this paper, we propose a distributed trustless and secure framework for electronic equipment RL activities based on blockchain technology. We consider the remanufacturing/refurbishing recovery option for mobile phones, and we develop an autonomous and effective back-end data sharing architecture based on smart contracts/blockchain technology for keeping track of all the remanufacturing/refurbishing processes. For demonstrating the applicability of our approach, we develop a functional set of smart contracts and a local private blockchain. The benefits of our framework are further discussed, along with fruitful areas for future research.
Invariant 3D Shape Recognition using Predictive Modular Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

In this paper PREMONN (PREdictive MOdular Neural Networks) model/architecture is generalized to functions of two variables and to non-Euclidean spaces. It is presented in the context of 3D invariant shape recognition and texture recognition. PREMONN uses local relation, it is modular and exhibits incremental learning. The recognition process can start at any point on a shape or texture, so a reference point is not needed. Its local relation characteristic enables it to recognize shape and texture even in presence of occlusion. The analysis is mainly mathematical. However, we present some experimental results. The methods presented in this paper can be applied to many problems such as gesture recognition, action recognition, dynamic texture recognition etc.
A Novel Confidence-Based Algorithm for Structured Bandits
Venue: arXiv cs.LG 2020
Year: 2020

We study finite-armed stochastic bandits where the rewards of each arm might be correlated to those of other arms. We introduce a novel phased algorithm that exploits the given structure to build confidence sets over the parameters of the true bandit problem and rapidly discard all sub-optimal arms. In particular, unlike standard bandit algorithms with no structure, we show that the number of times a suboptimal arm is selected may actually be reduced thanks to the information collected by pulling other arms. Furthermore, we show that, in some structures, the regret of an anytime extension of our algorithm is uniformly bounded over time. For these constant-regret structures, we also derive a matching lower bound. Finally, we demonstrate numerically that our approach better exploits certain structures than existing methods.
Geometric algorithms for predicting resilience and recovering damage in neural networks
Venue: arXiv cs.NE 2020
Year: 2020

Biological neural networks have evolved to maintain performance despite significant circuit damage. To survive damage, biological network architectures have both intrinsic resilience to component loss and also activate recovery programs that adjust network weights through plasticity to stabilize performance. Despite the importance of resilience in technology applications, the resilience of artificial neural networks is poorly understood, and autonomous recovery algorithms have yet to be developed. In this paper, we establish a mathematical framework to analyze the resilience of artificial neural networks through the lens of differential geometry. Our geometric language provides natural algorithms that identify local vulnerabilities in trained networks as well as recovery algorithms that dynamically adjust networks to compensate for damage. We reveal striking vulnerabilities in commonly used image analysis networks, like MLP's and CNN's trained on MNIST and CIFAR10 respectively. We also uncover high-performance recovery paths that enable the same networks to dynamically re-adjust their parameters to compensate for damage. Broadly, our work provides procedures that endow artificial systems with resilience and rapid-recovery routines to enhance their integration with IoT devices as well as enable their deployment for critical applications.
Bayesian Neural Networks at Scale: A Performance Analysis and Pruning Study
Venue: arXiv cs.LG 2020
Year: 2020

Bayesian neural Networks (BNNs) are a promising method of obtaining statistical uncertainties for neural network predictions but with a higher computational overhead which can limit their practical usage. This work explores the use of high performance computing with distributed training to address the challenges of training BNNs at scale. We present a performance and scalability comparison of training the VGG-16 and Resnet-18 models on a Cray-XC40 cluster. We demonstrate that network pruning can speed up inference without accuracy loss and provide an open source software package, {\it{BPrune}} to automate this pruning. For certain models we find that pruning up to 80\% of the network results in only a 7.0\% loss in accuracy. With the development of new hardware accelerators for Deep Learning, BNNs are of considerable interest for benchmarking performance. This analysis of training a BNN at scale outlines the limitations and benefits compared to a conventional neural network.
Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Modeling multivariate time series has long been a subject that has attracted researchers from a diverse range of fields including economics, finance, and traffic. A basic assumption behind multivariate time series forecasting is that its variables depend on one another but, upon looking closely, it is fair to say that existing methods fail to fully exploit latent spatial dependencies between pairs of variables. In recent years, meanwhile, graph neural networks (GNNs) have shown high capability in handling relational dependencies. GNNs require well-defined graph structures for information propagation which means they cannot be applied directly for multivariate time series where the dependencies are not known in advance. In this paper, we propose a general graph neural network framework designed specifically for multivariate time series data. Our approach automatically extracts the uni-directed relations among variables through a graph learning module, into which external knowledge like variable attributes can be easily integrated. A novel mix-hop propagation layer and a dilated inception layer are further proposed to capture the spatial and temporal dependencies within the time series. The graph learning, graph convolution, and temporal convolution modules are jointly learned in an end-to-end framework. Experimental results show that our proposed model outperforms the state-of-the-art baseline methods on 3 of 4 benchmark datasets and achieves on-par performance with other approaches on two traffic datasets which provide extra structural information.