OpenRaiser/Intern-Atlas huggingface dataset:
Detecting Covert Cryptomining using HPC
Venue: arXiv cs.CR 2020
Year: 2020

Cybercriminals have been exploiting cryptocurrencies to commit various unique financial frauds. Covert cryptomining - which is defined as an unauthorized harnessing of victims' computational resources to mine cryptocurrencies - is one of the prevalent ways nowadays used by cybercriminals to earn financial benefits. Such exploitation of resources causes financial losses to the victims. In this paper, we present our novel and efficient approach to detect covert cryptomining. Our solution is a generic solution that, unlike currently available solutions to detect covert cryptomining, is not tailored to a specific cryptocurrency or a particular form of cryptomining. In particular, we focus on the core mining algorithms and utilize Hardware Performance Counters (HPC) to create clean signatures that grasp the execution pattern of these algorithms on a processor. We built a complete implementation of our solution employing advanced machine learning techniques. We evaluated our methodology on two different processors through an exhaustive set of experiments. In our experiments, we considered all the cryptocurrencies mined by the top-10 mining pools, which collectively represent the largest share (84% during Q3 2018) of the cryptomining market. Our results show that our classifier can achieve a near-perfect classification with samples of length as low as five seconds. Due to its robust and practical design, our solution can even adapt to zero-day cryptocurrencies. Finally, we believe our solution is scalable and can be deployed to tackle the uprising problem of covert cryptomining.
Recurrent Neural Networks for Time Series Forecasting: Current Status and Future Directions
Venue: arXiv cs.LG 2020
Year: 2020

Recurrent Neural Networks (RNN) have become competitive forecasting methods, as most notably shown in the winning method of the recent M4 competition. However, established statistical models such as ETS and ARIMA gain their popularity not only from their high accuracy, but they are also suitable for non-expert users as they are robust, efficient, and automatic. In these areas, RNNs have still a long way to go. We present an extensive empirical study and an open-source software framework of existing RNN architectures for forecasting, that allow us to develop guidelines and best practices for their use. For example, we conclude that RNNs are capable of modelling seasonality directly if the series in the dataset possess homogeneous seasonal patterns, otherwise we recommend a deseasonalization step. Comparisons against ETS and ARIMA demonstrate that the implemented (semi-)automatic RNN models are no silver bullets, but they are competitive alternatives in many situations.
A Tight Uniform Continuity Bound for Equivocation
Venue: arXiv cs.IT 2020
Year: 2020

We prove a tight uniform continuity bound for the conditional Shannon entropy of discrete finitely supported random variables in terms of total variation distance.
Approximate Query Service on Autonomous IoT Cameras
Venue: arXiv cs.DB 2020
Year: 2020

Elf is a runtime for an energy-constrained camera to continuously summarize video scenes as approximate object counts. Elf's novelty centers on planning the camera's count actions under energy constraint. (1) Elf explores the rich action space spanned by the number of sample image frames and the choice of per-frame object counters; it unifies errors from both sources into one single bounded error. (2) To decide count actions at run time, Elf employs a learning-based planner, jointly optimizing for past and future videos without delaying result materialization. Tested with more than 1,000 hours of videos and under realistic energy constraints, Elf continuously generates object counts within only 11% of the true counts on average. Alongside the counts, Elf presents narrow errors shown to be bounded and up to 3.4x smaller than competitive baselines. At a higher level, Elf makes a case for advancing the geographic frontier of video analytics.
Error Analysis of Elitist Randomized Search Heuristics
Venue: arXiv cs.NE 2020
Year: 2020

When globally optimal solutions of complicated optimization problems cannot be located by evolutionary algorithms (EAs) in polynomial expected running time, the hitting time/running time analysis is not flexible enough to accommodate the requirement of theoretical study, because sometimes we have no idea on what approximation ratio is available in polynomial expected running time. Thus, it is necessary to propose an alternative routine for the theoretical analysis of EAs. To bridge the gap between theoretical analysis and algorithm implementation, in this paper we perform an error analysis where expected approximation error is estimated to evaluate performances of randomized search heuristics (RSHs). Based on the Markov chain model of RSHs, the multi-step transition matrix can be computed by diagonalizing the one-step transition matrix, and a general framework for estimation of expected approximation errors is proposed. Case studies indicate that the error analysis works well for both uni- and multi-modal benchmark problems. It leads to precise estimations of approximation error instead of asymptotic results on fitness values, which demonstrates its competitiveness to fixed budget analysis.
On Loss Functions for Supervised Monaural Time-Domain Speech Enhancement
Venue: arXiv cs.SD 2020
Year: 2020

Many deep learning-based speech enhancement algorithms are designed to minimize the mean-square error (MSE) in some transform domain between a predicted and a target speech signal. However, optimizing for MSE does not necessarily guarantee high speech quality or intelligibility, which is the ultimate goal of many speech enhancement algorithms. Additionally, only little is known about the impact of the loss function on the emerging class of time-domain deep learning-based speech enhancement systems. We study how popular loss functions influence the performance of deep learning-based speech enhancement systems. First, we demonstrate that perceptually inspired loss functions might be advantageous if the receiver is the human auditory system. Furthermore, we show that the learning rate is a crucial design parameter even for adaptive gradient-based optimizers, which has been generally overlooked in the literature. Also, we found that waveform matching performance metrics must be used with caution as they in certain situations can fail completely. Finally, we show that a loss function based on scale-invariant signal-to-distortion ratio (SI-SDR) achieves good general performance across a range of popular speech enhancement evaluation metrics, which suggests that SI-SDR is a good candidate as a general-purpose loss function for speech enhancement systems.
Local Partial Zero-Forcing Precoding for Cell-Free Massive MIMO
Venue: arXiv cs.IT 2020
Year: 2020

Cell-free Massive MIMO (multiple-input multiple-output) is a promising distributed network architecture for 5G-and-beyond systems. It guarantees ubiquitous coverage at high spectral efficiency (SE) by leveraging signal co-processing at multiple access points (APs), aggressive spatial user multiplexing and extraordinary macro-diversity gain. In this study, we propose two distributed precoding schemes, referred to as \textit{local partial zero-forcing} (PZF) and \textit{local protective partial zero-forcing} (PPZF), that further improve the spectral efficiency by providing an adaptable trade-off between interference cancelation and boosting of the desired signal, with no additional front-hauling overhead, and implementable by APs with very few antennas. We derive closed-form expressions for the achievable SE under the assumption of independent Rayleigh fading channel, channel estimation error and pilot contamination. PZF and PPZF can substantially outperform maximum ratio transmission and zero-forcing, and their performance is comparable to that achieved by regularized zero-forcing (RZF), which is a benchmark in the downlink. Importantly, these closed-form expressions can be employed to devise optimal (long-term) power control strategies that are also suitable for RZF, whose closed-form expression for the SE is not available.
A Note on the Probability of Rectangles for Correlated Binary Strings
Venue: arXiv cs.IT 2020
Year: 2020

Consider two sequences of $n$ independent and identically distributed fair coin tosses, $X=(X_1,\ldots,X_n)$ and $Y=(Y_1,\ldots,Y_n)$, which are $ρ$-correlated for each $j$, i.e. $\mathbb{P}[X_j=Y_j] = {1+ρ\over 2}$. We study the question of how large (small) the probability $\mathbb{P}[X \in A, Y\in B]$ can be among all sets $A,B\subset\{0,1\}^n$ of a given cardinality. For sets $|A|,|B| = Θ(2^n)$ it is well known that the largest (smallest) probability is approximately attained by concentric (anti-concentric) Hamming balls, and this can be proved via the hypercontractive inequality (reverse hypercontractivity). Here we consider the case of $|A|,|B| = 2^{Θ(n)}$. By applying a recent extension of the hypercontractive inequality of Polyanskiy-Samorodnitsky (J. Functional Analysis, 2019), we show that Hamming balls of the same size approximately maximize $\mathbb{P}[X \in A, Y\in B]$ in the regime of $ρ\to 1$. We also prove a similar tight lower bound, i.e. show that for $ρ\to 0$ the pair of opposite Hamming balls approximately minimizes the probability $\mathbb{P}[X \in A, Y\in B]$.
Optimal Causal Rate-Constrained Sampling of the Wiener Process
Venue: arXiv cs.IT 2020
Year: 2020

We consider the following communication scenario. An encoder causally observes the Wiener process and decides when and what to transmit about it. A decoder makes real-time estimation of the process using causally received codewords. We determine the causal encoding and decoding policies that jointly minimize the mean-square estimation error, under the long-term communication rate constraint of $R$ bits per second. We show that an optimal encoding policy can be implemented as a causal sampling policy followed by a causal compressing policy. We prove that the optimal encoding policy samples the Wiener process once the innovation passes either $\sqrt{\frac{1}{R}}$ or $-\sqrt{\frac{1}{R}}$, and compresses the sign of the innovation (SOI) using a 1-bit codeword. The SOI coding scheme achieves the operational distortion-rate function, which is equal to $D^{\mathrm{op}}(R)=\frac{1}{6R}$. Surprisingly, this is significantly better than the distortion-rate tradeoff achieved in the limit of infinite delay by the best non-causal code. This is because the SOI coding scheme leverages the free timing information supplied by the zero-delay channel between the encoder and the decoder. The key to unlock that gain is the event-triggered nature of the SOI sampling policy. In contrast, the distortion-rate tradeoffs achieved with deterministic sampling policies are much worse: we prove that the causal informational distortion-rate function in that scenario is as high as $D_{\mathrm{DET}}(R) = \frac{5}{6R}$. It is achieved by the uniform sampling policy with the sampling interval $\frac{1}{R}$. In either case, the optimal strategy is to sample the process as fast as possible and to transmit 1-bit codewords to the decoder without delay.
Mogrifier LSTM
Venue: arXiv cs.CL 2020
Year: 2020

Many advances in Natural Language Processing have been based upon more expressive models for how inputs interact with the context in which they occur. Recurrent networks, which have enjoyed a modicum of success, still lack the generalization and systematicity ultimately required for modelling language. In this work, we propose an extension to the venerable Long Short-Term Memory in the form of mutual gating of the current input and the previous output. This mechanism affords the modelling of a richer space of interactions between inputs and their context. Equivalently, our model can be viewed as making the transition function given by the LSTM context-dependent. Experiments demonstrate markedly improved generalization on language modelling in the range of 3-4 perplexity points on Penn Treebank and Wikitext-2, and 0.01-0.05 bpc on four character-based datasets. We establish a new state of the art on all datasets with the exception of Enwik8, where we close a large gap between the LSTM and Transformer models.
3D Morphable Face Models -- Past, Present and Future
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we provide a detailed survey of 3D Morphable Face Models over the 20 years since they were first proposed. The challenges in building and applying these models, namely capture, modeling, image formation, and image analysis, are still active research topics, and we review the state-of-the-art in each of these areas. We also look ahead, identifying unsolved challenges, proposing directions for future research and highlighting the broad range of current and future applications.
Population-based Gradient Descent Weight Learning for Graph Coloring Problems
Venue: arXiv cs.LG 2020
Year: 2020

Graph coloring involves assigning colors to the vertices of a graph such that two vertices linked by an edge receive different colors. Graph coloring problems are general models that are very useful to formulate many relevant applications and, however, are computationally difficult. In this work, a general population-based weight learning framework for solving graph coloring problems is presented. Unlike existing methods for graph coloring that are specific to the considered problem, the presented work targets a generic objective by introducing a unified method that can be applied to different graph coloring problems. This work distinguishes itself by its solving approach that formulates the search of a solution as a continuous weight tensor optimization problem and takes advantage of a gradient descent method computed in parallel on graphics processing units. The proposed approach is also characterized by its general global loss function that can easily be adapted to different graph coloring problems. The usefulness of the proposed approach is demonstrated by applying it to solve two typical graph coloring problems and performing large computational studies on popular benchmarks. Improved best-known results (new upper bounds) are reported for several large graphs.
Personalization of Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

We discuss training techniques, objectives and metrics toward personalization of deep learning models. In machine learning, personalization addresses the goal of a trained model to target a particular individual by optimizing one or more performance metrics, while conforming to certain constraints. To personalize, we investigate three methods of ``curriculum learning`` and two approaches for data grouping, i.e., augmenting the data of an individual by adding similar data identified with an auto-encoder. We show that both ``curriculuum learning'' and ``personalized'' data augmentation lead to improved performance on data of an individual. Mostly, this comes at the cost of reduced performance on a more general, broader dataset.
$\mathrm{P}\ne\mathrm{NP}$ and All Non-Empty Sets in $\mathrm{NP}\cup\mathrm{coNP}$ Have P-Optimal Proof Systems Relative to an Oracle
Venue: arXiv cs.CC 2020
Year: 2020

As one step in a working program initiated by Pudlák [Pud17] we construct an oracle relative to which $\mathrm{P}\ne\mathrm{NP}$ and all non-empty sets in $\mathrm{NP}\cup\mathrm{coNP}$ have $\mathrm{P}$-optimal proof systems.
NP-completeness of the game Kingdomino
Venue: arXiv cs.CC 2020
Year: 2020

Kingdomino is a board game designed by Bruno Cathala and edited by Blue Orange since 2016. The goal is to place $2 \times 1$ dominoes on a grid layout, and get a better score than other players. Each $1 \times 1$ domino cell has a color that must match at least one adjacent cell, and an integer number of crowns (possibly none) used to compute the score. We prove that even with full knowledge of the future of the game, in order to maximize their score at Kingdomino, players are faced with an NP-complete optimization problem.
DRLViz: Understanding Decisions and Memory in Deep Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

We present DRLViz, a visual analytics interface to interpret the internal memory of an agent (e.g. a robot) trained using deep reinforcement learning. This memory is composed of large temporal vectors updated when the agent moves in an environment and is not trivial to understand due to the number of dimensions, dependencies to past vectors, spatial/temporal correlations, and co-correlation between dimensions. It is often referred to as a black box as only inputs (images) and outputs (actions) are intelligible for humans. Using DRLViz, experts are assisted to interpret decisions using memory reduction interactions, and to investigate the role of parts of the memory when errors have been made (e.g. wrong direction). We report on DRLViz applied in the context of video games simulators (ViZDoom) for a navigation scenario with item gathering tasks. We also report on experts evaluation using DRLViz, and applicability of DRLViz to other scenarios and navigation problems beyond simulation games, as well as its contribution to black box models interpretability and explainability in the field of visual analytics.
Distance Restricted Manipulation in Voting
Venue: arXiv cs.GT 2020
Year: 2020

We introduce the notion of {\em Distance Restricted Manipulation}, where colluding manipulator(s) need to compute if there exist votes which make their preferred alternative win the election when their knowledge about the others' votes is a little inaccurate. We use the Kendall-Tau distance to model the manipulators' confidence in the non-manipulators' votes. To this end, we study this problem in two settings - one where the manipulators need to compute a manipulating vote that succeeds irrespective of perturbations in others' votes ({\em Distance Restricted Strong Manipulation}), and the second where the manipulators need to compute a manipulating vote that succeeds for at least one possible vote profile of the others ({\em Distance Restricted Weak Manipulation}). We show that {\em Distance Restricted Strong Manipulation} admits polynomial-time algorithms for every scoring rule, maximin, Bucklin, and simplified Bucklin voting rules for a single manipulator, and for the $k$-approval rule for any number of manipulators, but becomes intractable for the Copeland$^α$ voting rule for every $α\in[0,1]$ even for a single manipulator. In contrast, {\em Distance Restricted Weak Manipulation} is intractable for almost all the common voting rules, with the exception of the plurality rule. For a constant number of alternatives, we show that both the problems are polynomial-time solvable for every anonymous and efficient voting rule.
Look and Modify: Modification Networks for Image Captioning
Venue: arXiv cs.CV 2020
Year: 2020

Attention-based neural encoder-decoder frameworks have been widely used for image captioning. Many of these frameworks deploy their full focus on generating the caption from scratch by relying solely on the image features or the object detection regional features. In this paper, we introduce a novel framework that learns to modify existing captions from a given framework by modeling the residual information, where at each timestep the model learns what to keep, remove or add to the existing caption allowing the model to fully focus on "what to modify" rather than on "what to predict". We evaluate our method on the COCO dataset, trained on top of several image captioning frameworks and show that our model successfully modifies captions yielding better ones with better evaluation scores.
Deep Reinforcement Learning for Control of Probabilistic Boolean Networks
Venue: arXiv cs.LG 2020
Year: 2020

Probabilistic Boolean Networks (PBNs) were introduced as a computational model for the study of complex dynamical systems, such as Gene Regulatory Networks (GRNs). Controllability in this context is the process of making strategic interventions to the state of a network in order to drive it towards some other state that exhibits favourable biological properties. In this paper we study the ability of a Double Deep Q-Network with Prioritized Experience Replay in learning control strategies within a finite number of time steps that drive a PBN towards a target state, typically an attractor. The control method is model-free and does not require knowledge of the network's underlying dynamics, making it suitable for applications where inference of such dynamics is intractable. We present extensive experiment results on two synthetic PBNs and the PBN model constructed directly from gene-expression data of a study on metastatic-melanoma.
Distributed Training of Embeddings using Graph Analytics
Venue: arXiv cs.LG 2020
Year: 2020

Many applications today, such as NLP, network analysis, and code analysis, rely on semantically embedding objects into low-dimensional fixed-length vectors. Such embeddings naturally provide a way to perform useful downstream tasks, such as identifying relations among objects or predicting objects for a given context, etc. Unfortunately, the training necessary for accurate embeddings is usually computationally intensive and requires processing large amounts of data. Furthermore, distributing this training is challenging. Most embedding training uses stochastic gradient descent (SGD), an "inherently" sequential algorithm. Prior approaches to parallelizing SGD do not honor these dependencies and thus potentially suffer poor convergence. This paper presents a distributed training framework for a class of applications that use Skip-gram-like models to generate embeddings. We call this class Any2Vec and it includes Word2Vec, DeepWalk, and Node2Vec among others. We first formulate Any2Vec training algorithm as a graph application and leverage the state-of-the-art distributed graph analytics framework, D-Galois. We adapt D-Galois to support dynamic graph generation and repartitioning, and incorporate novel communication optimizations. Finally, we introduce a novel way to combine gradients during distributed training to prevent accuracy loss. We show that our framework, called GraphAny2Vec, matches on a cluster of 32 hosts the accuracy of the state-of-the-art shared-memory implementations of Word2Vec and Vertex2Vec on 1 host, and gives a geo-mean speedup of 12x and 5x respectively. Furthermore, GraphAny2Vec is on average 2x faster than the state-of-the-art distributed Word2Vec implementation, DMTK, on 32 hosts. We also show the superiority of our Gradient Combiner independent of GraphAny2Vec by incorporating it in DMTK, which raises its accuracy by > 30%.
Large Scale Question Answering using Tourism Data
Venue: arXiv cs.CL 2020
Year: 2020

We introduce the novel task of answering entity-seeking recommendation questions using a collection of reviews that describe candidate answer entities. We harvest a QA dataset that contains 47,124 paragraph-sized real user questions from travelers seeking recommendations for hotels, attractions and restaurants. Each question can have thousands of candidate answers to choose from and each candidate is associated with a collection of unstructured reviews. This dataset is especially challenging because commonly used neural architectures for reasoning and QA are prohibitively expensive for a task of this scale. As a solution, we design a scalable cluster-select-rerank approach. It first clusters text for each entity to identify exemplar sentences describing an entity. It then uses a scalable neural information retrieval (IR) module to select a set of potential entities from the large candidate set. A reranker uses a deeper attention-based architecture to pick the best answers from the selected entities. This strategy performs better than a pure IR or a pure attention-based reasoning approach yielding nearly 25% relative improvement in Accuracy@3 over both approaches.