OpenRaiser/Intern-Atlas huggingface dataset:
Two halves of a meaningful text are statistically different
Venue: arXiv cs.CL 2020
Year: 2020

Which statistical features distinguish a meaningful text (possibly written in an unknown system) from a meaningless set of symbols? Here we answer this question by comparing features of the first half of a text to its second half. This comparison can uncover hidden effects, because the halves have the same values of many parameters (style, genre {\it etc}). We found that the first half has more different words and more rare words than the second half. Also, words in the first half are distributed less homogeneously over the text in the sense of of the difference between the frequency and the inverse spatial period. These differences hold for the significant majority of several hundred relatively short texts we studied. The statistical significance is confirmed via the Wilcoxon test. Differences disappear after random permutation of words that destroys the linear structure of the text. The differences reveal a temporal asymmetry in meaningful texts, which is confirmed by showing that texts are much better compressible in their natural way (i.e. along the narrative) than in the word-inverted form. We conjecture that these results connect the semantic organization of a text (defined by the flow of its narrative) to its statistical features.
The growth rate over trees of any family of set defined by a monadic second order formula is semi-computable
Venue: arXiv cs.DM 2020
Year: 2020

Monadic second order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independent sets or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order $n$ is at most $95^{\frac{n}{13}}$ and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did for minimal dominating sets can be done for any family of sets definable by a monadic second order formula. We first show that, for any monadic second order formula over graphs that characterizes a given kind of subset of its vertices, the maximal number of such sets in a tree can be expressed as the \textit{growth rate of a bilinear system}. This mostly relies on well known links between monadic second order logic over trees and tree automata and basic tree automata manipulations. Then we show that this "growth rate" of a bilinear system can be approximated from above.We then use our implementation of this result to provide bounds on the number of independent dominating sets, total perfect dominating sets, induced matchings, maximal induced matchings, minimal perfect dominating sets, perfect codes and maximal irredundant sets on trees. We also solve a question from D. Y. Kang et al. regarding $r$-matchings and improve a bound from Górska and Skupień on the number of maximal matchings on trees. Remark that this approach is easily generalizable to graphs of bounded tree width or clique width (or any similar class of graphs where tree automata are meaningful).
Contrastive Examples for Addressing the Tyranny of the Majority
Venue: arXiv cs.CV 2020
Year: 2020

Computer vision algorithms, e.g. for face recognition, favour groups of individuals that are better represented in the training data. This happens because of the generalization that classifiers have to make. It is simpler to fit the majority groups as this fit is more important to overall error. We propose to create a balanced training dataset, consisting of the original dataset plus new data points in which the group memberships are intervened, minorities become majorities and vice versa. We show that current generative adversarial networks are a powerful tool for learning these data points, called contrastive examples. We experiment with the equalized odds bias measure on tabular data as well as image data (CelebA and Diversity in Faces datasets). Contrastive examples allow us to expose correlations between group membership and other seemingly neutral features. Whenever a causal graph is available, we can put those contrastive examples in the perspective of counterfactuals.
Decentralized Differentially Private Segmentation with PATE
Venue: arXiv cs.CV 2020
Year: 2020

When it comes to preserving privacy in medical machine learning, two important considerations are (1) keeping data local to the institution and (2) avoiding inference of sensitive information from the trained model. These are often addressed using federated learning and differential privacy, respectively. However, the commonly used Federated Averaging algorithm requires a high degree of synchronization between participating institutions. For this reason, we turn our attention to Private Aggregation of Teacher Ensembles (PATE), where all local models can be trained independently without inter-institutional communication. The purpose of this paper is thus to explore how PATE -- originally designed for classification -- can best be adapted for semantic segmentation. To this end, we build low-dimensional representations of segmentation masks which the student can obtain through low-sensitivity queries to the private aggregator. On the Brain Tumor Segmentation (BraTS 2019) dataset, an Autoencoder-based PATE variant achieves a higher Dice coefficient for the same privacy guarantee than prior work based on noisy Federated Averaging.
InsideBias: Measuring Bias in Deep Networks and Application to Face Gender Biometrics
Venue: arXiv cs.CV 2020
Year: 2020

This work explores the biases in learning processes based on deep neural network architectures. We analyze how bias affects deep learning processes through a toy example using the MNIST database and a case study in gender detection from face images. We employ two gender detection models based on popular deep neural networks. We present a comprehensive analysis of bias effects when using an unbalanced training dataset on the features learned by the models. We show how bias impacts in the activations of gender detection models based on face images. We finally propose InsideBias, a novel method to detect biased models. InsideBias is based on how the models represent the information instead of how they perform, which is the normal practice in other existing methods for bias detection. Our strategy with InsideBias allows to detect biased models with very few samples (only 15 images in our case study). Our experiments include 72K face images from 24K identities and 3 ethnic groups.
Counting Small Induced Subgraphs Satisfying Monotone Properties
Venue: arXiv cs.CC 2020
Year: 2020

Given a graph property $Φ$, the problem $\#\mathsf{IndSub}(Φ)$ asks, on input a graph $G$ and a positive integer $k$, to compute the number of induced subgraphs of size $k$ in $G$ that satisfy $Φ$. The search for explicit criteria on $Φ$ ensuring that $\#\mathsf{IndSub}(Φ)$ is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into "easy" and "hard" properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and Dörfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property $Φ$, the problem $\#\mathsf{IndSub}(Φ)$ cannot be solved in time $f(k)\cdot |V(G)|^{o(k/ {\log^{1/2}(k)})}$ for any function $f$, unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a $\#\mathsf{W}[1]$-completeness result.
Multi-source Attention for Unsupervised Domain Adaptation
Venue: arXiv cs.CL 2020
Year: 2020

Domain adaptation considers the problem of generalising a model learnt using data from a particular source domain to a different target domain. Often it is difficult to find a suitable single source to adapt from, and one must consider multiple sources. Using an unrelated source can result in sub-optimal performance, known as the \emph{negative transfer}. However, it is challenging to select the appropriate source(s) for classifying a given target instance in multi-source unsupervised domain adaptation (UDA). We model source-selection as an attention-learning problem, where we learn attention over sources for a given target instance. For this purpose, we first independently learn source-specific classification models, and a relatedness map between sources and target domains using pseudo-labelled target domain instances. Next, we learn attention-weights over the sources for aggregating the predictions of the source-specific models. Experimental results on cross-domain sentiment classification benchmarks show that the proposed method outperforms prior proposals in multi-source UDA.
A Survey on Activation Functions and their relation with Xavier and He Normal Initialization
Venue: arXiv cs.NE 2020
Year: 2020

In artificial neural network, the activation function and the weight initialization method play important roles in training and performance of a neural network. The question arises is what properties of a function are important/necessary for being a well-performing activation function. Also, the most widely used weight initialization methods - Xavier and He normal initialization have fundamental connection with activation function. This survey discusses the important/necessary properties of activation function and the most widely used activation functions (sigmoid, tanh, ReLU, LReLU and PReLU). This survey also explores the relationship between these activation functions and the two weight initialization methods - Xavier and He normal initialization.
Efficient Suspected Infected Crowds Detection Based on Spatio-Temporal Trajectories
Venue: arXiv cs.DB 2020
Year: 2020

Virus transmission from person to person is an emergency event facing the global public. Early detection and isolation of potentially susceptible crowds can effectively control the epidemic of its disease. Existing metrics can not correctly address the infected rate on trajectories. To solve this problem, we propose a novel spatio-temporal infected rate (IR) measure based on human moving trajectories that can adequately describe the risk of being infected by a given query trajectory of a patient. Then, we manage source data through an efficient spatio-temporal index to make our system more scalable, and can quickly query susceptible crowds from massive trajectories. Besides, we design several pruning strategies that can effectively reduce calculations. Further, we design a spatial first time (SFT) index, which enables us to quickly query multiple trajectories without much I/O consumption and data redundancy. The performance of the solutions is demonstrated in experiments based on real and synthetic trajectory datasets that have shown the effectiveness and efficiency of our solutions.
Secure Federated Learning in 5G Mobile Networks
Venue: arXiv cs.CR 2020
Year: 2020

Machine Learning (ML) is an important enabler for optimizing, securing and managing mobile networks. This leads to increased collection and processing of data from network functions, which in turn may increase threats to sensitive end-user information. Consequently, mechanisms to reduce threats to end-user privacy are needed to take full advantage of ML. We seamlessly integrate Federated Learning (FL) into the 3GPP 5G Network Data Analytics (NWDA) architecture, and add a Multi-Party Computation (MPC) protocol for protecting the confidentiality of local updates. We evaluate the protocol and find that it has much lower overhead than previous work, without affecting ML performance.
Autocalibration of a Mobile UWB Localization System for Ad-Hoc Multi-Robot Deployments in GNSS-Denied Environments
Venue: arXiv cs.RO 2020
Year: 2020

Ultra-wideband (UWB) wireless technology has seen an increased penetration in the robotics field as a robust localization method in recent years. UWB enables high accuracy distance estimation from time-of-flight measurements of wireless signals, even in non-line-of-sight measurements. UWB-based localization systems have been utilized in various types of GNSS-denied environments for ground or aerial autonomous robots. However, most of the existing solutions rely on a fixed and well-calibrated set of UWB nodes, or anchors, to estimate accurately the position of other mobile nodes, or tags, through multilateration. This limits the applicability of such systems for dynamic and ad-hoc deployments, such as post-disaster scenarios where the UWB anchors could be mounted on mobile robots to aid the navigation of UAVs or other robots. We introduce a collaborative algorithm for online autocalibration of anchor positions, enabling not only ad-hoc deployments but also movable anchors, based on Decawave's DWM1001 UWB module. Compared to the built-in autocalibration process from Decawave, we drastically reduce the amount of calibration time and increase the accuracy at the same time. We provide both experimental measurements and simulation results to demonstrate the usability of this algorithm.
Issues and challenges in Cloud Storage Architecture: A Survey
Venue: arXiv cs.NI 2020
Year: 2020

From home appliances to industrial enterprises, the Information and Communication Technology (ICT) industry is revolutionizing the world. We are witnessing the emergence of new technologies (e.g, Cloud computing, Fog computing, Internet of Things (IoT), Artificial Intelligence (AI) and Block-chain) which proves the growing use of ICT (e,g. business, education, health, and home appliances), resulting in massive data generation. It is expected that more than 175 ZB data will be processed annually by 75 billion devices by 2025. The 5G technology (i.e. mobile communication technology) dramatically increases network speed, enabling users to upload ultra high definition videos in real-time, which will generate a massive stream of big data. Furthermore, smart devices, having artificial intelligence, will act like a human being (e.g, a self-driving vehicle, etc) on the network, will also generate big data. This sudden shift and massive data generation created serious challenges in storing and managing heterogeneous data at such a large scale. This article presents a state-of-the-art review of the issues and challenges involved in storing heterogeneous big data, their countermeasures (i.e, from security and management perspectives), and future opportunities of cloud storage. These challenges are reviewed in detail and new dynamics for researchers in the field of cloud storage are discovered.
Composite Travel Generative Adversarial Networks for Tabular and Sequential Population Synthesis
Venue: arXiv cs.LG 2020
Year: 2020

Agent-based transportation modelling has become the standard to simulate travel behaviour, mobility choices and activity preferences using disaggregate travel demand data for entire populations, data that are not typically readily available. Various methods have been proposed to synthesize population data for this purpose. We present a Composite Travel Generative Adversarial Network (CTGAN), a novel deep generative model to estimate the underlying joint distribution of a population, that is capable of reconstructing composite synthetic agents having tabular (e.g. age and sex) as well as sequential mobility data (e.g. trip trajectory and sequence). The CTGAN model is compared with other recently proposed methods such as the Variational Autoencoders (VAE) method, which has shown success in high dimensional tabular population synthesis. We evaluate the performance of the synthesized outputs based on distribution similarity, multi-variate correlations and spatio-temporal metrics. The results show the consistent and accurate generation of synthetic populations and their tabular and spatially sequential attributes, generated over varying spatial scales and dimensions.
Understanding Aesthetic Evaluation using Deep Learning
Venue: arXiv cs.NE 2020
Year: 2020

A bottleneck in any evolutionary art system is aesthetic evaluation. Many different methods have been proposed to automate the evaluation of aesthetics, including measures of symmetry, coherence, complexity, contrast and grouping. The interactive genetic algorithm (IGA) relies on human-in-the-loop, subjective evaluation of aesthetics, but limits possibilities for large search due to user fatigue and small population sizes. In this paper we look at how recent advances in deep learning can assist in automating personal aesthetic judgement. Using a leading artist's computer art dataset, we use dimensionality reduction methods to visualise both genotype and phenotype space in order to support the exploration of new territory in any generative system. Convolutional Neural Networks trained on the user's prior aesthetic evaluations are used to suggest new possibilities similar or between known high quality genotype-phenotype mappings.
On Cyclic Polar Codes and The Burst Erasure Performance of Spatially-Coupled LDPC Codes
Venue: arXiv cs.IT 2020
Year: 2020

Polar codes were introduced in 2009 and proven to achieve the symmetric capacity of any binary-input discrete memoryless channel under low-complexity successive cancellation decoding. In this thesis, we construct cyclic polar codes based on a mixed-radix Cooley-Tukey decomposition of the Galois field Fourier transform. The main results are: we can, for the first time, construct, encode and decode polar codes that are cyclic, with their blocklength being arbitrary; for a given target block erasure rate, we can achieve significantly higher code rates on the erasure channel than the original polar codes, at comparable blocklengths; on the symmetric channel with only errors, we can perform much better than equivalent rate Reed-Solomon codes with the same blocklength, by using soft-decision decoding; and, since the codes are subcodes of higher rate RS codes, a RS decoder can be used if suboptimal performance suffices for the application as a trade-off for higher decoding speed. In 2010, it was shown that spatially-coupled low-density parity-check (LDPC) codes approach the capacity of binary memoryless channels, asymptotically, with belief-propagation (BP) decoding. In this thesis, we are interested in the finite length average performance of randomly coupled LDPC ensembles on binary erasure channels with memory. The significant contributions of this work are: tight lower bounds for the block erasure probability ($P_B$) under various scenarios for the burst pattern; bounds focused on practical scenarios where a burst affects exactly one of the coupled codes; expected error floor for the bit erasure probability ($P_b$) on the binary erasure channel; and, characterization of the performance of random regular ensembles, on erasure channels, with a single vector describing distinct types of size-$2$ stopping sets. All these results are verified using Monte-Carlo simulations.
Continuous learning of face attribute synthesis
Venue: arXiv cs.CV 2020
Year: 2020

The generative adversarial network (GAN) exhibits great superiority in the face attribute synthesis task. However, existing methods have very limited effects on the expansion of new attributes. To overcome the limitations of a single network in new attribute synthesis, a continuous learning method for face attribute synthesis is proposed in this work. First, the feature vector of the input image is extracted and attribute direction regression is performed in the feature space to obtain the axes of different attributes. The feature vector is then linearly guided along the axis so that images with target attributes can be synthesized by the decoder. Finally, to make the network capable of continuous learning, the orthogonal direction modification module is used to extend the newly-added attributes. Experimental results show that the proposed method can endow a single network with the ability to learn attributes continuously, and, as compared to those produced by the current state-of-the-art methods, the synthetic attributes have higher accuracy.
Empirical Models for the Realistic Generation of Cooperative Awareness Messages in Vehicular Networks
Venue: arXiv cs.NI 2020
Year: 2020

Most V2X (Vehicle-to-Everything) applications rely on broadcasting awareness messages known as CAM (Cooperative Awareness Messages) in ETSI or BSM (Basic Safety Message) in SAE standards. A large number of studies have been devoted to guarantee their reliable transmission. However, to date, the studies are generally based on simplified data traffic models that generate awareness messages at periodic intervals or with a constant message size. These models do not accurately represent the real generation of CAM messages that follow specific mobility-based rules. Using simplified and unrealistic traffic models can significantly impact the results and validity of the studies, and hence accurate models for the generation of awareness messages are necessary. This paper proposes the first set of models that can realistically generate CAM messages. The models have been created from real traces collected by two car manufacturers in urban, sub-urban and highway test drives. The models are based on mth order Markov sources, and model the size of CAMs and the time interval between CAMs. The models are openly provided to the community and can be easily integrated into any simulator.
On Learning Rates and Schrödinger Operators
Venue: arXiv cs.LG 2020
Year: 2020

The learning rate is perhaps the single most important parameter in the training of neural networks and, more broadly, in stochastic (nonconvex) optimization. Accordingly, there are numerous effective, but poorly understood, techniques for tuning the learning rate, including learning rate decay, which starts with a large initial learning rate that is gradually decreased. In this paper, we present a general theoretical analysis of the effect of the learning rate in stochastic gradient descent (SGD). Our analysis is based on the use of a learning-rate-dependent stochastic differential equation (lr-dependent SDE) that serves as a surrogate for SGD. For a broad class of objective functions, we establish a linear rate of convergence for this continuous-time formulation of SGD, highlighting the fundamental importance of the learning rate in SGD, and contrasting to gradient descent and stochastic gradient Langevin dynamics. Moreover, we obtain an explicit expression for the optimal linear rate by analyzing the spectrum of the Witten-Laplacian, a special case of the Schrödinger operator associated with the lr-dependent SDE. Strikingly, this expression clearly reveals the dependence of the linear convergence rate on the learning rate -- the linear rate decreases rapidly to zero as the learning rate tends to zero for a broad class of nonconvex functions, whereas it stays constant for strongly convex functions. Based on this sharp distinction between nonconvex and convex problems, we provide a mathematical interpretation of the benefits of using learning rate decay for nonconvex optimization.