OpenRaiser/Intern-Atlas huggingface dataset:
The effects of regularisation on RNN models for time series forecasting: Covid-19 as an example
Venue: arXiv cs.LG 2021
Year: 2021

Many research papers that propose models to predict the course of the COVID-19 pandemic either use handcrafted statistical models or large neural networks. Even though large neural networks are more powerful than simpler statistical models, they are especially hard to train on small datasets. This paper not only presents a model with grater flexibility than the other proposed neural networks, but also presents a model that is effective on smaller datasets. To improve performance on small data, six regularisation methods were tested. The results show that the GRU combined with 20% Dropout achieved the lowest RMSE scores. The main finding was that models with less access to data relied more on the regulariser. Applying Dropout to a GRU model trained on only 28 days of data reduced the RMSE by 23%.
The impact of the additional features on the performance of regression analysis: a case study on regression analysis of music signal
Venue: arXiv cs.SD 2021
Year: 2021

Machine learning techniques nowadays play a vital role in many burning issues of real-world problems when it involves data. In addition, when the task is complex, people are in dilemma in choosing deep learning techniques or going without them. This paper is about whether we should always rely on deep learning techniques or it is really possible to overcome the performance of deep learning algorithms by simple statistical machine learning algorithms by understanding the application and processing the data so that it can help in increasing the performance of the algorithm by a notable amount. The paper mentions the importance of data preprocessing than that of the selection of the algorithm. It discusses the functions involving trigonometric, logarithmic, and exponential terms and also talks about functions that are purely trigonometric. Finally, we discuss regression analysis on music signals to justify our claim.
Graph Neural Networks for Inconsistent Cluster Detection in Incremental Entity Resolution
Venue: arXiv cs.LG 2021
Year: 2021

Online stores often utilize product relationships such as bundles and substitutes to improve their catalog quality and guide customers through myriad choices. Entity resolution using pairwise product matching models offers a means of inferring relationships between products. In mature data repositories, the relationships may be mostly correct but require incremental improvements owing to errors in the original data or in the entity resolution system. It is critical to devise incremental entity resolution (IER) approaches for improving the health of relationships. However, most existing research on IER focuses on the addition of new products or information into existing relationships. Relatively little research has been done for detecting low quality within current relationships. This paper proposes a novel method for identifying inconsistent clusters (IC), existing groups of related products that do not belong together. We propose to treat the identification of inconsistent clusters as a supervised learning task which predicts whether a graph of products with similarities as weighted edges should be partitioned into multiple clusters. In this case, the problem becomes a classification task on weighted graphs and represents an interesting application area for modern tools such as Graph Neural Networks (GNNs). We demonstrate that existing Message Passing neural networks perform well at this task, exceeding traditional graph processing techniques. We also develop a novel message aggregation scheme for Message Passing Neural Networks that further improves the performance of GNNs on this task. We apply the model to synthetic datasets, a public benchmark dataset, and an internal application. Our results demonstrate the value of graph classification in IER and the ability of graph neural networks to develop useful representations for graph partitioning.
A new version of Toom's proof
Venue: arXiv cs.FL 2021
Year: 2021

There are several proofs now for the stability of Toom's example of a two-dimensional stable cellular automaton and its application to fault-tolerant computation. Simon and Berman simplified and strengthened Toom's original proof: the present report is a simplified exposition of their proof.
An Open-Source Tool for Classification Models in Resource-Constrained Hardware
Venue: arXiv cs.LG 2021
Year: 2021

Applications that need to sense, measure, and gather real-time information from the environment frequently face three main restrictions: power consumption, cost, and lack of infrastructure. Most of the challenges imposed by these limitations can be better addressed by embedding Machine Learning (ML) classifiers in the hardware that senses the environment, creating smart sensors able to interpret the low-level data stream. However, for this approach to be cost-effective, we need highly efficient classifiers suitable to execute in unresourceful hardware, such as low-power microcontrollers. In this paper, we present an open-source tool named EmbML - Embedded Machine Learning that implements a pipeline to develop classifiers for resource-constrained hardware. We describe its implementation details and provide a comprehensive analysis of its classifiers considering accuracy, classification time, and memory usage. Moreover, we compare the performance of its classifiers with classifiers produced by related tools to demonstrate that our tool provides a diverse set of classification algorithms that are both compact and accurate. Finally, we validate EmbML classifiers in a practical application of a smart sensor and trap for disease vector mosquitoes.
Improving Code Autocompletion with Transfer Learning
Venue: arXiv cs.SE 2021
Year: 2021

Software language models have achieved promising results predicting code completion usages, and several industry studies have described successful IDE integrations. Recently, accuracy in autocompletion prediction improved 12.8% from training on a real-world dataset collected from programmers' IDE activity. But what if limited examples of IDE autocompletion in the target programming language are available for model training? In this paper, we investigate the efficacy of pretraining autocompletion models on non-IDE, non-autocompletion, and different-language example code sequences. We find that these unsupervised pretrainings improve model accuracy by over 50% on very small fine-tuning datasets and over 10% on 50k labeled examples. We confirm the real-world impact of these pretrainings in an online setting through A/B testing on thousands of IDE autocompletion users, finding that pretraining is responsible for increases of up to 6.63% autocompletion usage.
Sufficient reasons for classifier decisions in the presence of constraints
Venue: arXiv cs.AI 2021
Year: 2021

Recent work has unveiled a theory for reasoning about the decisions made by binary classifiers: a classifier describes a Boolean function, and the reasons behind an instance being classified as positive are the prime-implicants of the function that are satisfied by the instance. One drawback of these works is that they do not explicitly treat scenarios where the underlying data is known to be constrained, e.g., certain combinations of features may not exist, may not be observable, or may be required to be disregarded. We propose a more general theory, also based on prime-implicants, tailored to taking constraints into account. The main idea is to view classifiers in the presence of constraints as describing partial Boolean functions, i.e., that are undefined on instances that do not satisfy the constraints. We prove that this simple idea results in reasons that are no less (and sometimes more) succinct. That is, not taking constraints into account (e.g., ignored, or taken as negative instances) results in reasons that are subsumed by reasons that do take constraints into account. We illustrate this improved parsimony on synthetic classifiers and classifiers learned from real data.
Robust Beamforming for Enhancing Security in Multibeam Satellite Systems
Venue: arXiv cs.IT 2021
Year: 2021

This paper proposes a robust beamforming (BF) scheme to enhance physical layer security (PLS) of the downlink of a multibeam satellite system in the presence of either uncoordinated or coordinated eavesdroppers (Eves). Specifically, with knowing only the approximate locations of the Eves, we aim at maximizing the worst-case achievable secrecy rate (ASR) of the legitimate user (LU), subject to the constraints of per-antenna transmit power and quality of service (QoS) requirement of the LU. Since the optimization problem is non-convex, we first adopt the discretization method to deal with the unknown regions of the Eves and then exploit the log-sum-exp function to approximate the objective function. Afterwards, a BF method joint alternating direction method of multipliers (ADMM) with Dinkelbach iteration is presented to solve this non-convex problem. Finally, simulation results verify that our robust BF algorithm can effectively improve the security of multibeam satellite systems.
Changeable Sweep Coverage Problem
Venue: arXiv cs.CC 2021
Year: 2021

Sweep coverage is to realize the periodic coverage of targets by planning the periodic sweeping paths of mobile sensors. It is difficult for sensors to reduce energy consumption by reducing the moving distances. Therefore, charging technology is the best way to extend the lifetime of the sweep coverage network. This paper studies the sweep coverage of rechargeable sensors: the sensors are rechargeable, constantly sweep between the target points and the charging stations not only tp meet the periodic coverage requirement of the target points, but also need to return to the charging stations during the charging period to avoid running out of energy. This paper proposes the general definition of Chargeable Sweep Coverage (CSC) problem for the first time, and studies the complexity of the CSC problem by analyzing CSC problems under different constraints, and then proposes two kinds of CSC problems under special constraints: 1) The sensors need to return to their original charging stations for charging; 2) The sensors can go to different charging stations for charging, and the number of charging stations is 2. Both of these problems are NP-hard. In this paper, these two problems are modeled as the maximum set coverage problem, and the approximation algorithms are obtained by reducing the number of candidate paths to polynomials. The validity and scalability of the proposed algorithms is proved by theoretical proof and experimental simulation.
On Sparsity Awareness in Distributed Computations
Venue: arXiv cs.DC 2021
Year: 2021

We extract a core principle underlying seemingly different fundamental distributed settings, showing sparsity awareness may induce faster algorithms for problems in these settings. To leverage this, we establish a new framework by developing an intermediate auxiliary model weak enough to be simulated in the CONGEST model given low mixing time, as well as in the recently introduced HYBRID model. We prove that despite imposing harsh restrictions, this artificial model allows balancing massive data transfers with high bandwidth utilization. We exemplify the power of our methods, by deriving shortest-paths algorithms improving upon the state-of-the-art. Specifically, we show the following for graphs of $n$ nodes: A $(3+ε)$ approximation for weighted APSP in $(n^{1/2}+n/δ)τ_{mix}\cdot 2^{O(\sqrt\log n)}$ rounds in the CONGEST model, where $δ$ is the minimum degree of the graph and $τ_{mix}$ is its mixing time. For graphs with $δ=τ_{mix}\cdot 2^{ω(\sqrt\log n)}$, this takes $o(n)$ rounds, despite the $Ω(n)$ lower bound for general graphs [Nanongkai, STOC'14]. An $(n^{7/6}/m^{1/2}+n^2/m)\cdotτ_{mix}\cdot 2^{O(\sqrt\log n)}$-round exact SSSP algorithm in the CONGNEST model, for graphs with $m$ edges and a mixing time of $τ_{mix}$. This improves upon the algorithm of [Chechik and Mukhtar, PODC'20] for significant ranges of values of $m$ and $τ_{mix}$. A CONGESTED CLIQUE simulation in the CONGEST model improving upon the state-of-the-art simulation of [Ghaffari, Kuhn, and SU, PODC'17] by a factor proportional to the average degree in the graph. An $\tilde O(n^{5/17}/ε^9)$-round algorithm for a $(1+ε)$ approximation for SSSP in the HYBRID model. The only previous $o(n^{1/3})$ round algorithm for distance approximations in this model is for a much larger factor [Augustine, Hinnenthal, Kuhn, Scheideler, Schneider, SODA'20].
Learning symbol relation tree for online mathematical expression recognition
Venue: arXiv cs.CV 2021
Year: 2021

This paper proposes a method for recognizing online handwritten mathematical expressions (OnHME) by building a symbol relation tree (SRT) directly from a sequence of strokes. A bidirectional recurrent neural network learns from multiple derived paths of SRT to predict both symbols and spatial relations between symbols using global context. The recognition system has two parts: a temporal classifier and a tree connector. The temporal classifier produces an SRT by recognizing an OnHME pattern. The tree connector splits the SRT into several sub-SRTs. The final SRT is formed by looking up the best combination among those sub-SRTs. Besides, we adopt a tree sorting method to deal with various stroke orders. Recognition experiments indicate that the proposed OnHME recognition system is competitive to other methods. The recognition system achieves 44.12% and 41.76% expression recognition rates on the Competition on Recognition of Online Handwritten Mathematical Expressions (CROHME) 2014 and 2016 testing sets.
Superevents: Towards Native Semantic Segmentation for Event-based Cameras
Venue: arXiv cs.CV 2021
Year: 2021

Most successful computer vision models transform low-level features, such as Gabor filter responses, into richer representations of intermediate or mid-level complexity for downstream visual tasks. These mid-level representations have not been explored for event cameras, although it is especially relevant to the visually sparse and often disjoint spatial information in the event stream. By making use of locally consistent intermediate representations, termed as superevents, numerous visual tasks ranging from semantic segmentation, visual tracking, depth estimation shall benefit. In essence, superevents are perceptually consistent local units that delineate parts of an object in a scene. Inspired by recent deep learning architectures, we present a novel method that employs lifetime augmentation for obtaining an event stream representation that is fed to a fully convolutional network to extract superevents. Our qualitative and quantitative experimental results on several sequences of a benchmark dataset highlights the significant potential for event-based downstream applications.
TAR: Generalized Forensic Framework to Detect Deepfakes using Weakly Supervised Learning
Venue: arXiv cs.CV 2021
Year: 2021

Deepfakes have become a critical social problem, and detecting them is of utmost importance. Also, deepfake generation methods are advancing, and it is becoming harder to detect. While many deepfake detection models can detect different types of deepfakes separately, they perform poorly on generalizing the detection performance over multiple types of deepfake. This motivates us to develop a generalized model to detect different types of deepfakes. Therefore, in this work, we introduce a practical digital forensic tool to detect different types of deepfakes simultaneously and propose Transfer learning-based Autoencoder with Residuals (TAR). The ultimate goal of our work is to develop a unified model to detect various types of deepfake videos with high accuracy, with only a small number of training samples that can work well in real-world settings. We develop an autoencoder-based detection model with Residual blocks and sequentially perform transfer learning to detect different types of deepfakes simultaneously. Our approach achieves a much higher generalized detection performance than the state-of-the-art methods on the FaceForensics++ dataset. In addition, we evaluate our model on 200 real-world Deepfake-in-the-Wild (DW) videos of 50 celebrities available on the Internet and achieve 89.49% zero-shot accuracy, which is significantly higher than the best baseline model (gaining 10.77%), demonstrating and validating the practicability of our approach.
PassFlow: Guessing Passwords with Generative Flows
Venue: arXiv cs.CR 2021
Year: 2021

Recent advances in generative machine learning models rekindled research interest in the area of password guessing. Data-driven password guessing approaches based on GANs, language models and deep latent variable models have shown impressive generalization performance and offer compelling properties for the task of password guessing. In this paper, we propose PassFlow, a flow-based generative model approach to password guessing. Flow-based models allow for precise log-likelihood computation and optimization, which enables exact latent variable inference. Additionally, flow-based models provide meaningful latent space representation, which enables operations such as exploration of specific subspaces of the latent space and interpolation. We demonstrate the applicability of generative flows to the context of password guessing, departing from previous applications of flow-networks which are mainly limited to the continuous space of image generation. We show that PassFlow is able to outperform prior state-of-the-art GAN-based approaches in the password guessing task while using a training set that is orders of magnitudes smaller than that of previous art. Furthermore, a qualitative analysis of the generated samples shows that PassFlow can accurately model the distribution of the original passwords, with even non-matched samples closely resembling human-like passwords.
Efficient executions of Pipelined Conjugate Gradient Method on Heterogeneous Architectures
Venue: arXiv cs.DC 2021
Year: 2021

The Preconditioned Conjugate Gradient (PCG) method is widely used for solving linear systems of equations with sparse matrices. A recent version of PCG, Pipelined PCG, eliminates the dependencies in the computations of the PCG algorithm so that the non-dependent computations can be overlapped with communication. In this paper, we propose three methods for efficient execution of the Pipelined PCG algorithm on GPU accelerated heterogeneous architectures. The first two methods achieve task-parallelism using asynchronous executions of different tasks on CPU cores and GPU. The third method achieves data parallelism by decomposing the workload between CPU and GPU based on a performance model. The performance model takes into account the relative performance of CPU cores and GPU using some initial executions and performs 2D data decomposition. We also implement optimization strategies like kernel fusion for GPU and merging vector operations for CPU. Our methods give up to 8x speedup and on average 3x speedup over PCG CPU implementation of Paralution and PETSc libraries. They also give up to 5x speedup and on average 1.45x speedup over PCG GPU implementation of Paralution and PETSc libraries. The third method also provides an efficient solution for solving problems that cannot be fit into the GPU memory and gives up to 2.5x speedup for such problems.
On information rates over a binary input channel
Venue: arXiv cs.IT 2021
Year: 2021

We study communication systems over band-limited Additive White Gaussian Noise (AWGN) channels in which the transmitter output is constrained to be symmetric binary (bi-polar). In this work we improve the original Ozarov-Wyner-Ziv (OWZ) lower bound on capacity by introducing new achievability schemes with two advantages over the studied OWZ scheme which is based on peak-power constrained pulse-amplitude modulation. Our schemes achieve a moderately improved information rate and do so with much less sign transitions of the binary signal. The gap between the known upper-bound based on spectral constrains of bi-polar signals and our achievable lower bound is reduced to 0.93 bits per Nyquist interval at high SNR.
Deciding FO-definability of regular languages
Venue: arXiv cs.LO 2021
Year: 2021

We prove that, similarly to known PSpace-completeness of recognising FO(<)-definability of the language L(A) of a DFA A, deciding both FO(<,C)- and FO(<,MOD)-definability are PSpace-complete. (Here, FO(<,C) extends the first-order logic FO(<) with the standard congruence modulo n relation, and FO(<,MOD) with the quantifiers checking whether the number of positions satisfying a given formula is divisible by a given n>1. These FO-languages are known to define regular languages that are decidable in AC0 and ACC0, respectively.) We obtain these results by first showing that known algebraic characterisations of FO-definability of L(A) can be captured by `localisable' properties of the transition monoid of A. Using our criterion, we then generalise the known proof of PSpace-hardness of FO(<)-definability, and establish the upper bounds not only for arbitrary DFAs but also for two-way NFAs.
DeepObliviate: A Powerful Charm for Erasing Data Residual Memory in Deep Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Machine unlearning has great significance in guaranteeing model security and protecting user privacy. Additionally, many legal provisions clearly stipulate that users have the right to demand model providers to delete their own data from training set, that is, the right to be forgotten. The naive way of unlearning data is to retrain the model without it from scratch, which becomes extremely time and resource consuming at the modern scale of deep neural networks. Other unlearning approaches by refactoring model or training data struggle to gain a balance between overhead and model usability. In this paper, we propose an approach, dubbed as DeepObliviate, to implement machine unlearning efficiently, without modifying the normal training mode. Our approach improves the original training process by storing intermediate models on the hard disk. Given a data point to unlearn, we first quantify its temporal residual memory left in stored models. The influenced models will be retrained and we decide when to terminate the retraining based on the trend of residual memory on-the-fly. Last, we stitch an unlearned model by combining the retrained models and uninfluenced models. We extensively evaluate our approach on five datasets and deep learning models. Compared to the method of retraining from scratch, our approach can achieve 99.0%, 95.0%, 91.9%, 96.7%, 74.1% accuracy rates and 66.7$\times$, 75.0$\times$, 33.3$\times$, 29.4$\times$, 13.7$\times$ speedups on the MNIST, SVHN, CIFAR-10, Purchase, and ImageNet datasets, respectively. Compared to the state-of-the-art unlearning approach, we improve 5.8% accuracy, 32.5$\times$ prediction speedup, and reach a comparable retrain speedup under identical settings on average on these datasets. Additionally, DeepObliviate can also pass the backdoor-based unlearning verification.