OpenRaiser/Intern-Atlas huggingface dataset:
Improving Human Performance Using Mixed Granularity of Control in Multi-Human Multi-Robot Interaction
Venue: arXiv cs.RO 2020
Year: 2020

Due to the potentially large number of units involved, the interaction with a multi-robot system is likely to exceed the limits of the span of apprehension of any individual human operator. In previous work, we studied how this issue can be tackled by interacting with the robots in two modalities -- environment-oriented and robot-oriented. In this paper, we study how this concept can be applied to the case in which multiple human operators perform supervisory control on a multi-robot system. While the presence of extra operators suggests that more complex tasks could be accomplished, little research exists on how this could be achieved efficiently. In particular, one challenge arises -- the out-of-the-loop performance problem caused by a lack of engagement in the task, awareness of its state, and trust in the system and in the other operators. Through a user study involving 28 human operators and 8 real robots, we study how the concept of mixed granularity in multi-human multi-robot interaction affects user engagement, awareness, and trust while balancing the workload between multiple operators.
Streaming PTAS for Constrained k-Means
Venue: arXiv cs.DS 2020
Year: 2020

We generalise the results of Bhattacharya et al. (Journal of Computing Systems, 62(1):93-115, 2018) for the list-$k$-means problem defined as -- for a (unknown) partition $X_1, ..., X_k$ of the dataset $X \subseteq \mathbb{R}^d$, find a list of $k$-center sets (each element in the list is a set of $k$ centers) such that at least one of $k$-center sets $\{c_1, ..., c_k\}$ in the list gives an $(1+\varepsilon)$-approximation with respect to the cost function $\min_{\textrm{permutation } π} \left[ \sum_{i=1}^{k} \sum_{x \in X_i} ||x - c_{π(i)}||^2 \right]$. The list-$k$-means problem is important for the constrained $k$-means problem since algorithms for the former can be converted to PTAS for various versions of the latter. Following are the consequences of our generalisations: - Streaming algorithm: Our $D^2$-sampling based algorithm running in a single iteration allows us to design a 2-pass, logspace streaming algorithm for the list-$k$-means problem. This can be converted to a 4-pass, logspace streaming PTAS for various constrained versions of the $k$-means problem. - Faster PTAS under stability: Our generalisation is also useful in $k$-means clustering scenarios where finding good centers becomes easy once good centers for a few "bad" clusters have been chosen. One such scenario is clustering under stability where the number of such bad clusters is a constant. Using the above idea, we significantly improve the running time of the known algorithm from $O(dn^3) (k \log{n})^{poly(\frac{1}β, \frac{1}{\varepsilon})}$ to $O \left(dn^3 k^{\tilde{O}_{β\varepsilon}(\frac{1}{β\varepsilon})} \right)$.
Towards Shape Biased Unsupervised Representation Learning for Domain Generalization
Venue: arXiv cs.CV 2020
Year: 2020

It is known that, without awareness of the process, our brain appears to focus on the general shape of objects rather than superficial statistics of context. On the other hand, learning autonomously allows discovering invariant regularities which help generalization. In this work, we propose a learning framework to improve the shape bias property of self-supervised methods. Our method learns semantic and shape biased representations by integrating domain diversification and jigsaw puzzles. The first module enables the model to create a dynamic environment across arbitrary domains and provides a domain exploration vs. exploitation trade-off, while the second module allows the model to explore this environment autonomously. This universal framework does not require prior knowledge of the domain of interest. Extensive experiments are conducted on several domain generalization datasets, namely, PACS, Office-Home, VLCS, and Digits. We show that our framework outperforms state-of-the-art domain generalization methods by a large margin.
Graph Neural Networks for Maximum Constraint Satisfaction
Venue: arXiv cs.AI 2020
Year: 2020

Many combinatorial optimization problems can be phrased in the language of constraint satisfaction problems. We introduce a graph neural network architecture for solving such optimization problems. The architecture is generic; it works for all binary constraint satisfaction problems. Training is unsupervised, and it is sufficient to train on relatively small instances; the resulting networks perform well on much larger instances (at least 10-times larger). We experimentally evaluate our approach for a variety of problems, including Maximum Cut and Maximum Independent Set. Despite being generic, we show that our approach matches or surpasses most greedy and semi-definite programming based algorithms and sometimes even outperforms state-of-the-art heuristics for the specific problems.
Control of criticality and computation in spiking neuromorphic networks with plasticity
Venue: arXiv cs.ET 2020
Year: 2020

The critical state is assumed to be optimal for any computation in recurrent neural networks, because criticality maximizes a number of abstract computational properties. We challenge this assumption by evaluating the performance of a spiking recurrent neural network on a set of tasks of varying complexity at - and away from critical network dynamics. To that end, we developed a spiking network with synaptic plasticity on a neuromorphic chip. We show that the distance to criticality can be easily adapted by changing the input strength, and then demonstrate a clear relation between criticality, task-performance and information-theoretic fingerprint. Whereas the information-theoretic measures all show that network capacity is maximal at criticality, this is not the case for performance on specific tasks: Only the complex, memory-intensive tasks profit from criticality, whereas the simple tasks suffer from it. Thereby, we challenge the general assumption that criticality would be beneficial for any task, and provide instead an understanding of how the collective network state should be tuned to task requirement to achieve optimal performance.
Bias In, Bias Out? Evaluating the Folk Wisdom
Venue: arXiv cs.LG 2020
Year: 2020

We evaluate the folk wisdom that algorithmic decision rules trained on data produced by biased human decision-makers necessarily reflect this bias. We consider a setting where training labels are only generated if a biased decision-maker takes a particular action, and so "biased" training data arise due to discriminatory selection into the training data. In our baseline model, the more biased the decision-maker is against a group, the more the algorithmic decision rule favors that group. We refer to this phenomenon as "bias reversal." We then clarify the conditions that give rise to bias reversal. Whether a prediction algorithm reverses or inherits bias depends critically on how the decision-maker affects the training data as well as the label used in training. We illustrate our main theoretical results in a simulation study applied to the New York City Stop, Question and Frisk dataset.
Do Compressed Representations Generalize Better?
Venue: arXiv cs.LG 2020
Year: 2020

One of the most studied problems in machine learning is finding reasonable constraints that guarantee the generalization of a learning algorithm. These constraints are usually expressed as some simplicity assumptions on the target. For instance, in the Vapnik-Chervonenkis (VC) theory the space of possible hypotheses is considered to have a limited VC dimension. In this paper, the constraint on the entropy $H(X)$ of the input variable $X$ is studied as a simplicity assumption. It is proven that the sample complexity to achieve an $ε$-$δ$ Probably Approximately Correct (PAC) hypothesis is bounded by $\frac{2^{ \left.6H(X)\middle/ε\right.}+\log{\frac{1}δ}}{ε^2}$ which is sharp up to the $\frac{1}{ε^2}$ factor. Morever, it is shown that if a feature learning process is employed to learn the compressed representation from the dataset, this bound no longer exists. These findings have important implications on the Information Bottleneck (IB) theory which had been utilized to explain the generalization power of Deep Neural Networks (DNNs), but its applicability for this purpose is currently under debate by researchers. In particular, this is a rigorous proof for the previous heuristic that compressed representations are exponentially easier to be learned. However, our analysis pinpoints two factors preventing the IB, in its current form, to be applicable in studying neural networks. Firstly, the exponential dependence of sample complexity on $\frac{1}ε$, which can lead to a dramatic effect on the bounds in practical applications when $ε$ is small. Secondly, our analysis reveals that arguments based on input compression are inherently insufficient to explain generalization of methods like DNNs in which the features are also learned using available data.
Spectral Lower Bounds on the I/O Complexity of Computation Graphs
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of finding lower bounds on the I/O complexity of arbitrary computations in a two level memory hierarchy. Executions of complex computations can be formalized as an evaluation order over the underlying computation graph. However, prior methods for finding I/O lower bounds leverage the graph structures for specific problems (e.g matrix multiplication) which cannot be applied to arbitrary graphs. In this paper, we first present a novel method to bound the I/O of any computation graph using the first few eigenvalues of the graph's Laplacian. We further extend this bound to the parallel setting. This spectral bound is not only efficiently computable by power iteration, but can also be computed in closed form for graphs with known spectra. We apply our spectral method to compute closed-form analytical bounds on two computation graphs (the Bellman-Held-Karp algorithm for the traveling salesman problem and the Fast Fourier Transform), as well as provide a probabilistic bound for random Erdos Renyi graphs. We empirically validate our bound on four computation graphs, and find that our method provides tighter bounds than current empirical methods and behaves similarly to previously published I/O bounds.
Path Planning Tolerant to Degraded Locomotion Conditions
Venue: arXiv cs.RO 2020
Year: 2020

Mobile robots, especially those driving outdoors and in unstructured terrain, sometimes suffer from failures and errors in locomotion, like unevenly pressurized or flat tires, loose axes or de-tracked tracks. Those are errors that go unnoticed by the odometry of the robot. Other factors that influence the locomotion performance of the robot, like the weight and distribution of the payload, the terrain over which the robot is driving or the battery charge could not be compensated for by the PID speed or position controller of the robot, because of the physical limits of the system. Traditional planning systems are oblivious to those problems and may thus plan unfeasible trajectories. Also, the path following modules oblivious to those problems will generate sub-optimal motion patterns, if they can get to the goal at all. In this paper, we present an adaptive path planning algorithm that is tolerant to such degraded locomotion conditions. We do this by constantly observing the executed motions of the robot via simultaneously localization and mapping (SLAM). From the executed path and the given motion commands, we constantly on the fly collect and cluster motion primitives (MP), which are in turn used for planning. Therefore the robot can automatically detect and adapt to different locomotion conditions and reflect those in the planned paths.
TinyBERT: Distilling BERT for Natural Language Understanding
Venue: arXiv cs.CL 2020
Year: 2020

Language model pre-training, such as BERT, has significantly improved the performances of many natural language processing tasks. However, pre-trained language models are usually computationally expensive, so it is difficult to efficiently execute them on resource-restricted devices. To accelerate inference and reduce model size while maintaining accuracy, we first propose a novel Transformer distillation method that is specially designed for knowledge distillation (KD) of the Transformer-based models. By leveraging this new KD method, the plenty of knowledge encoded in a large teacher BERT can be effectively transferred to a small student Tiny-BERT. Then, we introduce a new two-stage learning framework for TinyBERT, which performs Transformer distillation at both the pretraining and task-specific learning stages. This framework ensures that TinyBERT can capture he general-domain as well as the task-specific knowledge in BERT. TinyBERT with 4 layers is empirically effective and achieves more than 96.8% the performance of its teacher BERTBASE on GLUE benchmark, while being 7.5x smaller and 9.4x faster on inference. TinyBERT with 4 layers is also significantly better than 4-layer state-of-the-art baselines on BERT distillation, with only about 28% parameters and about 31% inference time of them. Moreover, TinyBERT with 6 layers performs on-par with its teacher BERTBASE.
In Conclusion Not Repetition: Comprehensive Abstractive Summarization With Diversified Attention Based On Determinantal Point Processes
Venue: arXiv cs.CL 2020
Year: 2020

Various Seq2Seq learning models designed for machine translation were applied for abstractive summarization task recently. Despite these models provide high ROUGE scores, they are limited to generate comprehensive summaries with a high level of abstraction due to its degenerated attention distribution. We introduce Diverse Convolutional Seq2Seq Model(DivCNN Seq2Seq) using Determinantal Point Processes methods(Micro DPPs and Macro DPPs) to produce attention distribution considering both quality and diversity. Without breaking the end to end architecture, DivCNN Seq2Seq achieves a higher level of comprehensiveness compared to vanilla models and strong baselines. All the reproducible codes and datasets are available online.
Efficiently Reusing Old Models Across Languages via Transfer Learning
Venue: arXiv cs.CL 2020
Year: 2020

Recent progress in neural machine translation is directed towards larger neural networks trained on an increasing amount of hardware resources. As a result, NMT models are costly to train, both financially, due to the electricity and hardware cost, and environmentally, due to the carbon footprint. It is especially true in transfer learning for its additional cost of training the "parent" model before transferring knowledge and training the desired "child" model. In this paper, we propose a simple method of re-using an already trained model for different language pairs where there is no need for modifications in model architecture. Our approach does not need a separate parent model for each investigated language pair, as it is typical in NMT transfer learning. To show the applicability of our method, we recycle a Transformer model trained by different researchers and use it to seed models for different language pairs. We achieve better translation quality and shorter convergence times than when training from random initialization.
Hate begets Hate: A Temporal Study of Hate Speech
Venue: arXiv cs.SI 2020
Year: 2020

With the ongoing debate on 'freedom of speech' vs. 'hate speech' there is an urgent need to carefully understand the consequences of the inevitable culmination of the two, i.e., 'freedom of hate speech' over time. An ideal scenario to understand this would be to observe the effects of hate speech in an (almost) unrestricted environment. Hence, we perform the first temporal analysis of hate speech on Gab.com, a social media site with very loose moderation policy. We first generate temporal snapshots of Gab from millions of posts and users. Using these temporal snapshots, we compute an activity vector based on DeGroot model to identify hateful users. The amount of hate speech in Gab is steadily increasing and the new users are becoming hateful at an increased and faster rate. Further, our analysis analysis reveals that the hate users are occupying the prominent positions in the Gab network. Also, the language used by the community as a whole seem to correlate more with that of the hateful users as compared to the non-hateful ones. We discuss how, many crucial design questions in CSCW open up from our work.
On the edge-length ratio of 2-trees
Venue: arXiv cs.CG 2020
Year: 2020

We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. 770 (2019), 88--94] and, for any given constant $r$, we provide a $2$-tree which does not admit a planar straight-line drawing with a ratio bounded by $r$. When the ratio is restricted to adjacent edges only, we prove that any $2$-tree admits a planar straight-line drawing whose edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small $\varepsilon > 0$, hence the upper bound on the local edge-length ratio of partial $2$-trees is $4$.
FALCON: Lightweight and Accurate Convolution
Venue: arXiv cs.CV 2020
Year: 2020

How can we efficiently compress Convolutional Neural Network (CNN) while retaining their accuracy on classification tasks? Depthwise Separable Convolution (DSConv), which replaces a standard convolution with a depthwise convolution and a pointwise convolution, has been used for building lightweight architectures. However, previous works based on depthwise separable convolution are limited when compressing a trained CNN model since 1) they are mostly heuristic approaches without a precise understanding of their relations to standard convolution, and 2) their accuracies do not match that of the standard convolution. In this paper, we propose FALCON, an accurate and lightweight method to compress CNN. FALCON uses GEP, our proposed mathematical formulation to approximate the standard convolution kernel, to interpret existing convolution methods based on depthwise separable convolution. By exploiting the knowledge of a trained standard model and carefully determining the order of depthwise separable convolution via GEP, FALCON achieves sufficient accuracy close to that of the trained standard model. Furthermore, this interpretation leads to developing a generalized version rank-k FALCON which performs k independent FALCON operations and sums up the result. Experiments show that FALCON 1) provides higher accuracy than existing methods based on depthwise separable convolution and tensor decomposition, and 2) reduces the number of parameters and FLOPs of standard convolution by up to a factor of 8 while ensuring similar accuracy. We also demonstrate that rank-k FALCON further improves the accuracy while sacrificing a bit of compression and computation reduction rates.
Neural networks are a priori biased towards Boolean functions with low entropy
Venue: arXiv cs.LG 2020
Year: 2020

Understanding the inductive bias of neural networks is critical to explaining their ability to generalise. Here, for one of the simplest neural networks -- a single-layer perceptron with n input neurons, one output neuron, and no threshold bias term -- we prove that upon random initialisation of weights, the a priori probability $P(t)$ that it represents a Boolean function that classifies t points in ${0,1}^n$ as 1 has a remarkably simple form: $P(t) = 2^{-n}$ for $0\leq t < 2^n$. Since a perceptron can express far fewer Boolean functions with small or large values of t (low entropy) than with intermediate values of t (high entropy) there is, on average, a strong intrinsic a-priori bias towards individual functions with low entropy. Furthermore, within a class of functions with fixed t, we often observe a further intrinsic bias towards functions of lower complexity. Finally, we prove that, regardless of the distribution of inputs, the bias towards low entropy becomes monotonically stronger upon adding ReLU layers, and empirically show that increasing the variance of the bias term has a similar effect.
Federated Learning in Mobile Edge Networks: A Comprehensive Survey
Venue: arXiv cs.NI 2020
Year: 2020

In recent years, mobile devices are equipped with increasingly advanced sensing and computing capabilities. Coupled with advancements in Deep Learning (DL), this opens up countless possibilities for meaningful applications. Traditional cloudbased Machine Learning (ML) approaches require the data to be centralized in a cloud server or data center. However, this results in critical issues related to unacceptable latency and communication inefficiency. To this end, Mobile Edge Computing (MEC) has been proposed to bring intelligence closer to the edge, where data is produced. However, conventional enabling technologies for ML at mobile edge networks still require personal data to be shared with external parties, e.g., edge servers. Recently, in light of increasingly stringent data privacy legislations and growing privacy concerns, the concept of Federated Learning (FL) has been introduced. In FL, end devices use their local data to train an ML model required by the server. The end devices then send the model updates rather than raw data to the server for aggregation. FL can serve as an enabling technology in mobile edge networks since it enables the collaborative training of an ML model and also enables DL for mobile edge network optimization. However, in a large-scale and complex mobile edge network, heterogeneous devices with varying constraints are involved. This raises challenges of communication costs, resource allocation, and privacy and security in the implementation of FL at scale. In this survey, we begin with an introduction to the background and fundamentals of FL. Then, we highlight the aforementioned challenges of FL implementation and review existing solutions. Furthermore, we present the applications of FL for mobile edge network optimization. Finally, we discuss the important challenges and future research directions in FL
Aspect and Opinion Term Extraction for Hotel Reviews using Transfer Learning and Auxiliary Labels
Venue: arXiv cs.CL 2020
Year: 2020

Aspect and opinion term extraction is a critical step in Aspect-Based Sentiment Analysis (ABSA). Our study focuses on evaluating transfer learning using pre-trained BERT (Devlin et al., 2018) to classify tokens from hotel reviews in bahasa Indonesia. The primary challenge is the language informality of the review texts. By utilizing transfer learning from a multilingual model, we achieved up to 2% difference on token level F1-score compared to the state-of-the-art Bi-LSTM model with fewer training epochs (3 vs. 200 epochs). The fine-tuned model clearly outperforms the Bi-LSTM model on the entity level. Furthermore, we propose a method to include CRF with auxiliary labels as an output layer for the BERT-based models. The CRF addition further improves the F1-score for both token and entity level.