OpenRaiser/Intern-Atlas huggingface dataset:
Faster Dynamic Range Mode
Venue: arXiv cs.DS 2020
Year: 2020

In the dynamic range mode problem, we are given a sequence $a$ of length bounded by $N$ and asked to support element insertion, deletion, and queries for the most frequent element of a contiguous subsequence of $a$. In this work, we devise a deterministic data structure that handles each operation in worst-case $\tilde{O}(N^{0.655994})$ time, thus breaking the $O(N^{2/3})$ per-operation time barrier for this problem. The data structure is achieved by combining the ideas in Williams and Xu (SODA 2020) for batch range mode with a novel data structure variant of the Min-Plus product.
When Residual Learning Meets Dense Aggregation: Rethinking the Aggregation of Deep Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Various architectures (such as GoogLeNets, ResNets, and DenseNets) have been proposed. However, the existing networks usually suffer from either redundancy of convolutional layers or insufficient utilization of parameters. To handle these challenging issues, we propose Micro-Dense Nets, a novel architecture with global residual learning and local micro-dense aggregations. Specifically, residual learning aims to efficiently retrieve features from different convolutional blocks, while the micro-dense aggregation is able to enhance each block and avoid redundancy of convolutional layers by lessening residual aggregations. Moreover, the proposed micro-dense architecture has two characteristics: pyramidal multi-level feature learning which can widen the deeper layer in a block progressively, and dimension cardinality adaptive convolution which can balance each layer using linearly increasing dimension cardinality. The experimental results over three datasets (i.e., CIFAR-10, CIFAR-100, and ImageNet-1K) demonstrate that the proposed Micro-Dense Net with only 4M parameters can achieve higher classification accuracy than state-of-the-art networks, while being 12.1$\times$ smaller depends on the number of parameters. In addition, our micro-dense block can be integrated with neural architecture search based models to boost their performance, validating the advantage of our architecture. We believe our design and findings will be beneficial to the DNN community.
On the decomposition of generalized semiautomata
Venue: arXiv cs.FL 2020
Year: 2020

Semi-automata are abstractions of electronic devices that are deterministic finite-state machines having inputs but no outputs. Generalized semiautomata are obtained from stochastic semiautomata by dropping the restrictions imposed by probability. It is well-known that each stochastic semiautomaton can be decomposed into a sequential product of a dependent source and a deterministic semiautomaton making partly use of the celebrated theorem of Birkhoff-von Neumann. It will be shown that each generalized semiautomaton can be partitioned into a sequential product of a generalized dependent source and a deterministic semiautomaton.
Trollthrottle -- Raising the Cost of Astroturfing
Venue: arXiv cs.CR 2020
Year: 2020

Astroturfing, i.e., the fabrication of public discourse by private or state-controlled sponsors via the creation of fake online accounts, has become incredibly widespread in recent years. It gives a disproportionally strong voice to wealthy and technology-savvy actors, permits targeted attacks on public forums and could in the long run harm the trust users have in the internet as a communication platform. Countering these efforts without deanonymising the participants has not yet proven effective; however, we can raise the cost of astroturfing. Following the principle `one person, one voice', we introduce Trollthrottle, a protocol that limits the number of comments a single person can post on participating websites. Using direct anonymous attestation and a public ledger, the user is free to choose any nickname, but the number of comments is aggregated over all posts on all websites, no matter which nickname was used. We demonstrate the deployability of Trollthrottle by retrofitting it to the popular news aggregator website Reddit and by evaluating the cost of deployment for the scenario of a national newspaper (168k comments per day), an international newspaper (268k c/d) and Reddit itself (4.9M c/d).
Make E Smart Again
Venue: arXiv cs.AI 2020
Year: 2020

In this work in progress, we demonstrate a new use-case for the ENIGMA system. The ENIGMA system using the XGBoost implementation of gradient boosted decision trees has demonstrated high capability to learn to guide the E theorem prover's inferences in real-time. Here, we strip E to the bare bones: we replace the KBO term ordering with an identity relation as the minimal possible ordering, disable literal selection, and replace evolved strategies with a simple combination of the clause weight and FIFO (first in first out) clause evaluation functions. We experimentally demonstrate that ENIGMA can learn to guide E as well as the smart, evolved strategies even without these standard automated theorem prover functionalities. To this end, we experiment with XGBoost's meta-parameters over a dozen loops.
A practical approach to testing random number generators in computer algebra systems
Venue: arXiv cs.MS 2020
Year: 2020

This paper has a practical aim. For a long time, implementations of pseudorandom number generators in standard libraries of programming languages had poor quality. The situation started to improve only recently. Up to now, a large number of libraries and weakly supported mathematical packages use outdated algorithms for random number generation. Four modern sets of statistical tests that can be used for verifying random number generators are described. It is proposed to use command line utilities, which makes it possible to avoid low-level programming in such languages as C or C++. Only free open source systems are considered.
Space of Functions Computed by Deep-Layered Machines
Venue: arXiv cs.LG 2020
Year: 2020

We study the space of functions computed by random-layered machines, including deep neural networks and Boolean circuits. Investigating the distribution of Boolean functions computed on the recurrent and layer-dependent architectures, we find that it is the same in both models. Depending on the initial conditions and computing elements used, we characterize the space of functions computed at the large depth limit and show that the macroscopic entropy of Boolean functions is either monotonically increasing or decreasing with the growing depth.
SOS: Socially Omitting Selfishness in IoT for Smart and Connected Communities
Venue: arXiv cs.DC 2020
Year: 2020

Smart and Connected Communities (SCC) is an emerging field of Internet of Things (IoT), and it is having potential applications to improve human life. The improvement may be in terms of preservation, revitalization, livability, and sustainability of a community. The resources of the nodes and devices in the SCC have certain constraints that may not allow the devices and nodes to cooperate to save their resources such as memory, energy, and buffer, or simply maximize their performance. Thus, to stimulate the nodes to avoid selfish behavior, SSC needs a novel and well-organized solution to motivate nodes for cooperation. This article aims to resolve the issue of selfish behaviors in SCC and to encourage the nodes for cooperation. A novel mechanism Socially Omitting Selfishness (SOS) has been proposed to manage/eradicate selfishness using a socially-oriented election process. The election process elects different heads based on weight and cooperation (using VCG model). The election of heads and incentive mechanism encourages the nodes to show participation and behave as highly cooperative members of the community. Furthermore, an extended version of the Dempster-Shafer model has been used to discourage the selfish behavior of the participating nodes in the SOS scheme. It uses different monitoring and gateway nodes to efficiently employ the proposed scheme. A mathematical model has been developed for the aforementioned aspects and simulated through the NS2 simulation environment to analyze the performance of SOS. The results of the proposed scheme outperform the contemporary schemes in terms of average delivery delay, packet delivery ratio, throughput, and average energy.
Machine Learning based Pallets Detection and Tracking in AGVs
Venue: arXiv cs.CV 2020
Year: 2020

The use of automated guided vehicles (AGVs) has played a pivotal role in manufacturing and distribution operations, providing reliable and efficient product handling. In this project, we constructed a deep learning-based pallets detection and tracking architecture for pallets detection and position tracking. By using data preprocessing and augmentation techniques and experiment with hyperparameter tuning, we achieved the result with 25% reduction of error rate, 28.5% reduction of false negative rate, and 20% reduction of training time.
Adversarial Training for Large Neural Language Models
Venue: arXiv cs.CL 2020
Year: 2020

Generalization and robustness are both key desiderata for designing machine learning methods. Adversarial training can enhance robustness, but past work often finds it hurts generalization. In natural language processing (NLP), pre-training large neural language models such as BERT have demonstrated impressive gain in generalization for a variety of tasks, with further improvement from adversarial fine-tuning. However, these models are still vulnerable to adversarial attacks. In this paper, we show that adversarial pre-training can improve both generalization and robustness. We propose a general algorithm ALUM (Adversarial training for large neural LangUage Models), which regularizes the training objective by applying perturbations in the embedding space that maximizes the adversarial loss. We present the first comprehensive study of adversarial training in all stages, including pre-training from scratch, continual pre-training on a well-trained model, and task-specific fine-tuning. ALUM obtains substantial gains over BERT on a wide range of NLP tasks, in both regular and adversarial scenarios. Even for models that have been well trained on extremely large text corpora, such as RoBERTa, ALUM can still produce significant gains from continual pre-training, whereas conventional non-adversarial methods can not. ALUM can be further combined with task-specific fine-tuning to attain additional gains. The ALUM code is publicly available at https://github.com/namisan/mt-dnn.
Taming the Expressiveness and Programmability of Graph Analytical Queries
Venue: arXiv cs.CL 2020
Year: 2020

Graph database has enjoyed a boom in the last decade, and graph queries accordingly gain a lot of attentions from both the academia and industry. We focus on analytical queries in this paper. While analyzing existing domain-specific languages (DSLs) for analytical queries regarding the perspectives of completeness, expressiveness and programmability, we find out that none of existing work has achieved a satisfactory coverage of these perspectives. Motivated by this, we propose the \flash DSL, which is named after the three primitive operators Filter, LocAl and PuSH. We prove that \flash is Turing complete (completeness), and show that it achieves both good expressiveness and programmability for analytical queries. We provide an implementation of \flash based on code generation, and compare it with native C++ codes and existing DSL using representative queries. The experiment results demonstrate \flash's expressiveness, and its capability of programming complex algorithms that achieve satisfactory runtime.
On the Data Fight Between Cities and Mobility Providers
Venue: arXiv cs.CY 2020
Year: 2020

E-Scooters are changing transportation habits. In an attempt to oversee scooter usage, the Los Angeles Department of Transportation has put forth a specification that requests detailed data on scooter usage from scooter companies. In this work, we first argue that L.A.'s data request for using a new specification is not warranted as proposed use cases can be met by already existing specifications. Second, we show that even the existing specification, that requires companies to publish real-time data of parked scooters, puts the privacy of individuals using the scooters at risk. We then propose an algorithm that enables formal privacy and utility guarantees when publishing parked scooters data, allowing city authorities to meet their use cases while preserving riders' privacy.
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases
Venue: arXiv cs.DS 2020
Year: 2020

We define a notion of isotropy for discrete set distributions. If $μ$ is a distribution over subsets $S$ of a ground set $[n]$, we say that $μ$ is in isotropic position if $P[e \in S]$ is the same for all $e\in [n]$. We design a new approximate sampling algorithm that leverages isotropy for the class of distributions $μ$ that have a log-concave generating polynomial; this class includes determinantal point processes, strongly Rayleigh distributions, and uniform distributions over matroid bases. We show that when $μ$ is in approximately isotropic position, the running time of our algorithm depends polynomially on the size of the set $S$, and only logarithmically on $n$. When $n$ is much larger than the size of $S$, this is significantly faster than prior algorithms, and can even be sublinear in $n$. We then show how to transform a non-isotropic $μ$ into an equivalent approximately isotropic form with a polynomial-time preprocessing step, accelerating subsequent sampling times. The main new ingredient enabling our algorithms is a class of negative dependence inequalities that may be of independent interest. As an application of our results, we show how to approximately count bases of a matroid of rank $k$ over a ground set of $n$ elements to within a factor of $1+ε$ in time $ O((n+1/ε^2)\cdot poly(k, \log n))$. This is the first algorithm that runs in nearly linear time for fixed rank $k$, and achieves an inverse polynomially low approximation error.
A General Stabilization Bound for Influence Propagation in Graphs
Venue: arXiv cs.DM 2020
Year: 2020

We study the stabilization time of a wide class of processes on graphs, in which each node can only switch its state if it is motivated to do so by at least a $\frac{1+λ}{2}$ fraction of its neighbors, for some $0 < λ< 1$. Two examples of such processes are well-studied dynamically changing colorings in graphs: in majority processes, nodes switch to the most frequent color in their neighborhood, while in minority processes, nodes switch to the least frequent color in their neighborhood. We describe a non-elementary function $f(λ)$, and we show that in the sequential model, the worst-case stabilization time of these processes can completely be characterized by $f(λ)$. More precisely, we prove that for any $ε>0$, $O(n^{1+f(λ)+ε})$ is an upper bound on the stabilization time of any proportional majority/minority process, and we also show that there are graph constructions where stabilization indeed takes $Ω(n^{1+f(λ)-ε})$ steps.
Generative Feature Replay For Class-Incremental Learning
Venue: arXiv cs.CV 2020
Year: 2020

Humans are capable of learning new tasks without forgetting previous ones, while neural networks fail due to catastrophic forgetting between new and previously-learned tasks. We consider a class-incremental setting which means that the task-ID is unknown at inference time. The imbalance between old and new classes typically results in a bias of the network towards the newest ones. This imbalance problem can either be addressed by storing exemplars from previous tasks, or by using image replay methods. However, the latter can only be applied to toy datasets since image generation for complex datasets is a hard problem. We propose a solution to the imbalance problem based on generative feature replay which does not require any exemplars. To do this, we split the network into two parts: a feature extractor and a classifier. To prevent forgetting, we combine generative feature replay in the classifier with feature distillation in the feature extractor. Through feature generation, our method reduces the complexity of generative replay and prevents the imbalance problem. Our approach is computationally efficient and scalable to large datasets. Experiments confirm that our approach achieves state-of-the-art results on CIFAR-100 and ImageNet, while requiring only a fraction of the storage needed for exemplar-based continual learning. Code available at \url{https://github.com/xialeiliu/GFR-IL}.
A Study of Cross-Lingual Ability and Language-specific Information in Multilingual BERT
Venue: arXiv cs.CL 2020
Year: 2020

Recently, multilingual BERT works remarkably well on cross-lingual transfer tasks, superior to static non-contextualized word embeddings. In this work, we provide an in-depth experimental study to supplement the existing literature of cross-lingual ability. We compare the cross-lingual ability of non-contextualized and contextualized representation model with the same data. We found that datasize and context window size are crucial factors to the transferability. We also observe the language-specific information in multilingual BERT. By manipulating the latent representations, we can control the output languages of multilingual BERT, and achieve unsupervised token translation. We further show that based on the observation, there is a computationally cheap but effective approach to improve the cross-lingual ability of multilingual BERT.
A System Dynamics Model of Bitcoin: Mining as an Efficient Market and the Possibility of "Peak Hash"
Venue: arXiv cs.CR 2020
Year: 2020

The mining of bitcoin is modeled using system dynamics, showing that the past evolution of the network hash rate can be explained to a large extent by an efficient market hypothesis applied to the mining of blocks. The possibility of a decrease in the network hash rate from the next halving event (May 2020) is exposed, implying that the network may be close to 'peak hash', if the price of bitcoin and the revenues from transaction fees will remain at approximately the present level.
A Practical Guide to Studying Emergent Communication through Grounded Language Games
Venue: arXiv cs.AI 2020
Year: 2020

The question of how an effective and efficient communication system can emerge in a population of agents that need to solve a particular task attracts more and more attention from researchers in many fields, including artificial intelligence, linguistics and statistical physics. A common methodology for studying this question consists of carrying out multi-agent experiments in which a population of agents takes part in a series of scripted and task-oriented communicative interactions, called 'language games'. While each individual language game is typically played by two agents in the population, a large series of games allows the population to converge on a shared communication system. Setting up an experiment in which a rich system for communicating about the real world emerges is a major enterprise, as it requires a variety of software components for running multi-agent experiments, for interacting with sensors and actuators, for conceptualising and interpreting semantic structures, and for mapping between these semantic structures and linguistic utterances. The aim of this paper is twofold. On the one hand, it introduces a high-level robot interface that extends the Babel software system, presenting for the first time a toolkit that provides flexible modules for dealing with each subtask involved in running advanced grounded language game experiments. On the other hand, it provides a practical guide to using the toolkit for implementing such experiments, taking a grounded colour naming game experiment as a didactic example.
Learning Geometric Word Meta-Embeddings
Venue: arXiv cs.CL 2020
Year: 2020

We propose a geometric framework for learning meta-embeddings of words from different embedding sources. Our framework transforms the embeddings into a common latent space, where, for example, simple averaging of different embeddings (of a given word) is more amenable. The proposed latent space arises from two particular geometric transformations - the orthogonal rotations and the Mahalanobis metric scaling. Empirical results on several word similarity and word analogy benchmarks illustrate the efficacy of the proposed framework.
Towards Understanding Normalization in Neural ODEs
Venue: arXiv cs.LG 2020
Year: 2020

Normalization is an important and vastly investigated technique in deep learning. However, its role for Ordinary Differential Equation based networks (neural ODEs) is still poorly understood. This paper investigates how different normalization techniques affect the performance of neural ODEs. Particularly, we show that it is possible to achieve 93% accuracy in the CIFAR-10 classification task, and to the best of our knowledge, this is the highest reported accuracy among neural ODEs tested on this problem.
Personality Assessment from Text for Machine Commonsense Reasoning
Venue: arXiv cs.CY 2020
Year: 2020

This article presents PerSense, a framework to estimate human personality traits based on expressed texts and to use them for commonsense reasoning analysis. The personality assessment approaches include an aggregated Probability Density Functions (PDF), and Machine Learning (ML) models. Our goal is to demonstrate the feasibility of using machine learning algorithms on personality trait data to predict humans' responses to open-ended commonsense questions. We assess the performance of the PerSense algorithms for personality assessment by conducting an experiment focused on Neuroticism, an important personality trait crucial in mental health analysis and suicide prevention by collecting data from a diverse population with different Neuroticism scores. Our analysis shows that the algorithms achieve comparable results to the ground truth data. Specifically, the PDF approach achieves 97% accuracy when the confidence factor, the logarithmic ratio of the first to the second guess probability, is greater than 3. Additionally, ML approach obtains its highest accuracy, 82.2%, with a multilayer Perceptron classifier. To assess the feasibility of commonsense reasoning analysis, we train ML algorithms to predict responses to commonsense questions. Our analysis of data collected with 300 participants demonstrate that PerSense predicts answers to commonsense questions with 82.3% accuracy using a Random Forest classifier.
Non-Blocking Simultaneous Multithreading: Embracing the Resiliency of Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks (DNNs) are known for their inability to utilize underlying hardware resources due to hardware susceptibility to sparse activations and weights. Even in finer granularities, many of the non-zero values hold a portion of zero-valued bits that may cause inefficiencies when executed on hardware. Inspired by conventional CPU simultaneous multithreading (SMT) that increases computer resource utilization by sharing them across several threads, we propose non-blocking SMT (NB-SMT) designated for DNN accelerators. Like conventional SMT, NB-SMT shares hardware resources among several execution flows. Yet, unlike SMT, NB-SMT is non-blocking, as it handles structural hazards by exploiting the algorithmic resiliency of DNNs. Instead of opportunistically dispatching instructions while they wait in a reservation station for available hardware, NB-SMT temporarily reduces the computation precision to accommodate all threads at once, enabling a non-blocking operation. We demonstrate NB-SMT applicability using SySMT, an NB-SMT-enabled output-stationary systolic array (OS-SA). Compared with a conventional OS-SA, a 2-threaded SySMT consumes 1.4x the area and delivers 2x speedup with 33% energy savings and less than 1% accuracy degradation of state-of-the-art CNNs with ImageNet. A 4-threaded SySMT consumes 2.5x the area and delivers, for example, 3.4x speedup and 39% energy savings with 1% accuracy degradation of 40%-pruned ResNet-18.