OpenRaiser/Intern-Atlas huggingface dataset:
Non-Orthogonal Multiple Access for Air-to-Ground Communication
Venue: arXiv cs.IT 2020
Year: 2020

This paper investigates ground-aerial uplink non-orthogonal multiple access (NOMA) cellular networks. A rotary-wing unmanned aerial vehicle (UAV) user and multiple ground users (GUEs) are served by ground base stations (GBSs) by utilizing the uplink NOMA protocol. The UAV is dispatched to upload specific information bits to each target GBSs. Specifically, our goal is to minimize the UAV mission completion time by jointly optimizing the UAV trajectory and UAV-GBS association order while taking into account the UAV's interference to non-associated GBSs. The formulated problem is a mixed integer non-convex problem and involves infinite variables. To tackle this problem, we efficiently check the feasibility of the formulated problem by utilizing graph theory and topology theory. Next, we prove that the optimal UAV trajectory needs to satisfy the \emph{fly-hover-fly} structure. With this insight, we first design an efficient solution with predefined hovering locations by leveraging graph theory techniques. Furthermore, we propose an iterative UAV trajectory design by applying successive convex approximation (SCA) technique, which is guaranteed to coverage to a locally optimal solution. We demonstrate that the two proposed designs exhibit polynomial time complexity. Finally, numerical results show that: 1) the SCA based design outperforms the fly-hover-fly based design; 2) the UAV mission completion time is significantly minimized with proposed NOMA schemes compared with the orthogonal multiple access (OMA) scheme; 3) the increase of GUEs' quality of service (QoS) requirements will increase the UAV mission completion time.
Context is Key: Grammatical Error Detection with Contextual Word Representations
Venue: arXiv cs.CL 2020
Year: 2020

Grammatical error detection (GED) in non-native writing requires systems to identify a wide range of errors in text written by language learners. Error detection as a purely supervised task can be challenging, as GED datasets are limited in size and the label distributions are highly imbalanced. Contextualized word representations offer a possible solution, as they can efficiently capture compositional information in language and can be optimized on large amounts of unsupervised data. In this paper, we perform a systematic comparison of ELMo, BERT and Flair embeddings (Peters et al., 2017; Devlin et al., 2018; Akbik et al., 2018) on a range of public GED datasets, and propose an approach to effectively integrate such representations in current methods, achieving a new state of the art on GED. We further analyze the strengths and weaknesses of different contextual embeddings for the task at hand, and present detailed analyses of their impact on different types of errors.
Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank
Venue: arXiv cs.SI 2020
Year: 2020

Given an input graph G and a node v in G, homogeneous network embedding (HNE) maps the graph structure in the vicinity of v to a compact, fixed-dimensional feature vector. This paper focuses on HNE for massive graphs, e.g., with billions of edges. On this scale, most existing approaches fail, as they incur either prohibitively high costs, or severely compromised result utility. Our proposed solution, called Node-Reweighted PageRank (NRP), is based on a classic idea of deriving embedding vectors from pairwise personalized PageRank (PPR) values. Our contributions are twofold: first, we design a simple and efficient baseline HNE method based on PPR that is capable of handling billion-edge graphs on commodity hardware; second and more importantly, we identify an inherent drawback of vanilla PPR, and address it in our main proposal NRP. Specifically, PPR was designed for a very different purpose, i.e., ranking nodes in G based on their relative importance from a source node's perspective. In contrast, HNE aims to build node embeddings considering the whole graph. Consequently, node embeddings derived directly from PPR are of suboptimal utility. The proposed NRP approach overcomes the above deficiency through an effective and efficient node reweighting algorithm, which augments PPR values with node degree information, and iteratively adjusts embedding vectors accordingly. Overall, NRP takes O(mlogn) time and O(m) space to compute all node embeddings for a graph with m edges and n nodes. Our extensive experiments that compare NRP against 18 existing solutions over 7 real graphs demonstrate that NRP achieves higher result utility than all the solutions for link prediction, graph reconstruction and node classification, while being up to orders of magnitude faster. In particular, on a billion-edge Twitter graph, NRP terminates within 4 hours, using a single CPU core.
Learning-Driven Exploration for Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

Effective and intelligent exploration has been an unresolved problem for reinforcement learning. Most contemporary reinforcement learning relies on simple heuristic strategies such as $ε$-greedy exploration or adding Gaussian noise to actions. These heuristics, however, are unable to intelligently distinguish the well explored and the unexplored regions of state space, which can lead to inefficient use of training time. We introduce entropy-based exploration (EBE) that enables an agent to explore efficiently the unexplored regions of state space. EBE quantifies the agent's learning in a state using merely state-dependent action values and adaptively explores the state space, i.e. more exploration for the unexplored region of the state space. We perform experiments on a diverse set of environments and demonstrate that EBE enables efficient exploration that ultimately results in faster learning without having to tune any hyperparameter. The code to reproduce the experiments is given at \url{https://github.com/Usama1002/EBE-Exploration} and the supplementary video is given at \url{https://youtu.be/nJggIjjzKic}.
A Public-Key Cryptosystem Using Cyclotomic Matrices
Venue: arXiv cs.CR 2020
Year: 2020

Confidentiality and Integrity are two paramount objectives in the evaluation of information and communication technology. In this paper, we propose an arithmetic approach for designing asymmetric key cryptography. Our method is based on the formulation of cyclotomic matrices correspond to the diophantine system. The proposed cyclotomic asymmetric cryptosystem (CAC) utilizes the cyclotomic matrices, whose entries are cyclotomic numbers of order $2l^{2}$, $l$ be prime over a finite field $\mathbb{F}_{p}$ of $p$ elements. The method utilize cyclotomic matrices to design a one-way function. The outcome of a one-way function that is efficient to compute however difficult to compute its inverse unless if secret data about the trapdoor is known. We demonstrate that the encryption and decryption can be efficiently performed with asymptotic complexity of $\mathcal{O}(e^{2.373})$. Besides, we study the computational complexity of the CAC.
Is the Policy Gradient a Gradient?
Venue: arXiv cs.LG 2020
Year: 2020

The policy gradient theorem describes the gradient of the expected discounted return with respect to an agent's policy parameters. However, most policy gradient methods drop the discount factor from the state distribution and therefore do not optimize the discounted objective. What do they optimize instead? This has been an open question for several years, and this lack of theoretical clarity has lead to an abundance of misstatements in the literature. We answer this question by proving that the update direction approximated by most methods is not the gradient of any function. Further, we argue that algorithms that follow this direction are not guaranteed to converge to a "reasonable" fixed point by constructing a counterexample wherein the fixed point is globally pessimal with respect to both the discounted and undiscounted objectives. We motivate this work by surveying the literature and showing that there remains a widespread misunderstanding regarding discounted policy gradient methods, with errors present even in highly-cited papers published at top conferences.
Adversarial training approach for local data debiasing
Venue: arXiv cs.LG 2020
Year: 2020

The widespread use of automated decision processes in many areas of our society raises serious ethical issues concerning the fairness of the process and the possible resulting discriminations. In this work, we propose a novel approach called GANsan whose objective is to prevent the possibility of any discrimination i.e., direct and indirect) based on a sensitive attribute by removing the attribute itself as well as the existing correlations with the remaining attributes. Our sanitization algorithm GANsan is partially inspired by the powerful framework of generative adversarial networks (in particular the Cycle-GANs), which offers a flexible way to learn a distribution empirically or to translate between two different distributions. In contrast to prior work, one of the strengths of our approach is that the sanitization is performed in the same space as the original data by only modifying the other attributes as little as possible and thus preserving the interpretability of the sanitized data. As a consequence, once the sanitizer is trained, it can be applied to new data, such as for instance, locally by an individual on his profile before releasing it. Finally, experiments on a real dataset demonstrate the effectiveness of the proposed approach as well as the achievable trade-off between fairness and utility.
Unsupervised Learning of Object Structure and Dynamics from Videos
Venue: arXiv cs.CV 2020
Year: 2020

Extracting and predicting object structure and dynamics from videos without supervision is a major challenge in machine learning. To address this challenge, we adopt a keypoint-based image representation and learn a stochastic dynamics model of the keypoints. Future frames are reconstructed from the keypoints and a reference frame. By modeling dynamics in the keypoint coordinate space, we achieve stable learning and avoid compounding of errors in pixel space. Our method improves upon unstructured representations both for pixel-level video prediction and for downstream tasks requiring object-level understanding of motion dynamics. We evaluate our model on diverse datasets: a multi-agent sports dataset, the Human3.6M dataset, and datasets based on continuous control tasks from the DeepMind Control Suite. The spatially structured representation outperforms unstructured representations on a range of motion-related tasks such as object tracking, action recognition and reward prediction.
Discovery of Physics from Data: Universal Laws and Discrepancies
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning (ML) and artificial intelligence (AI) algorithms are now being used to automate the discovery of physics principles and governing equations from measurement data alone. However, positing a universal physical law from data is challenging without simultaneously proposing an accompanying discrepancy model to account for the inevitable mismatch between theory and measurements. By revisiting the classic problem of modeling falling objects of different size and mass, we highlight a number of nuanced issues that must be addressed by modern data-driven methods for automated physics discovery. Specifically, we show that measurement noise and complex secondary physical mechanisms, like unsteady fluid drag forces, can obscure the underlying law of gravitation, leading to an erroneous model. We use the sparse identification of nonlinear dynamics (SINDy) method to identify governing equations for real-world measurement data and simulated trajectories. Incorporating into SINDy the assumption that each falling object is governed by a similar physical law is shown to improve the robustness of the learned models, but discrepancies between the predictions and observations persist due to subtleties in drag dynamics. This work highlights the fact that the naive application of ML/AI will generally be insufficient to infer universal physical laws without further modification.
Paper-Patent Citation Linkages as Early Signs for Predicting Delayed Recognized Knowledge: Macro and Micro Evidence
Venue: arXiv cs.DL 2020
Year: 2020

In this study, we investigate the extent to which patent citations to papers can serve as early signs for predicting delayed recognized knowledge in science using a comparative study with a control group, i.e., instant recognition papers. We identify the two opposite groups of papers by the Bcp measure, a parameter-free index for identifying papers which were recognized with delay. We provide a macro (Science/Nature papers dataset) and micro (a case chosen from the dataset) evidence on paper-patent citation linkages as early signs for predicting delayed recognized knowledge in science. It appears that papers with delayed recognition show a stronger and longer technical impact than instant recognition papers. We provide indication that in the more recent years papers with delayed recognition are awakened more often and earlier by a patent rather than by a scientific paper (also called "prince"). We also found that patent citations seem to play an important role to avoid instant recognition papers to level off or to become a so called "flash in the pan", i.e., instant recognition. It also appears that the sleeping beauties may firstly encounter negative citations and then patent citations and finally get widely recognized. In contrast to the two focused fields (biology and chemistry) for instant recognition papers, delayed recognition papers are rather evenly distributed in biology, chemistry, psychology, geology, materials science, and physics. We discovered several pairs of "science sleeping"-"technology [...]. We propose in further research to discover the potential ahead of time and transformative research by using citation delay analysis, patent & NPL analysis, and citation context analysis.
From Decidability to Undecidability by Considering Regular Sets of Instances
Venue: arXiv cs.FL 2020
Year: 2020

We are lifting classical problems from single instances to regular sets of instances. The task of finding a positive instance of the combinatorial problem $P$ in a potentially infinite given regular set is equivalent to the so called intreg-problem of $P$, which asks for a given DFA $A$, whether the intersection of $P$ with $L(A)$ is non-empty. The intreg-problem generalizes the idea of considering multiple instances at once and connects classical combinatorial problems with the field of automata theory. While the question of the decidability of the intreg-problem has been answered positively for several NP- and even PSPACE-complete problems, we are presenting natural problems even from L with an undecidable intreg-problem. We also discuss alphabet sizes and different encoding-schemes elaborating the boundary between problem-variants with a decidable respectively undecidable intreg-problem.
Efficient Set-Valued Prediction in Multi-Class Classification
Venue: arXiv cs.LG 2020
Year: 2020

In cases of uncertainty, a multi-class classifier preferably returns a set of candidate classes instead of predicting a single class label with little guarantee. More precisely, the classifier should strive for an optimal balance between the correctness (the true class is among the candidates) and the precision (the candidates are not too many) of its prediction. We formalize this problem within a general decision-theoretic framework that unifies most of the existing work in this area. In this framework, uncertainty is quantified in terms of conditional class probabilities, and the quality of a predicted set is measured in terms of a utility function. We then address the problem of finding the Bayes-optimal prediction, i.e., the subset of class labels with highest expected utility. For this problem, which is computationally challenging as there are exponentially (in the number of classes) many predictions to choose from, we propose efficient algorithms that can be applied to a broad family of utility functions. Our theoretical results are complemented by experimental studies, in which we analyze the proposed algorithms in terms of predictive accuracy and runtime efficiency.
Unsupervised State Representation Learning in Atari
Venue: arXiv cs.LG 2020
Year: 2020

State representation learning, or the ability to capture latent generative factors of an environment, is crucial for building intelligent agents that can perform a wide variety of tasks. Learning such representations without supervision from rewards is a challenging open problem. We introduce a method that learns state representations by maximizing mutual information across spatially and temporally distinct features of a neural encoder of the observations. We also introduce a new benchmark based on Atari 2600 games where we evaluate representations based on how well they capture the ground truth state variables. We believe this new framework for evaluating representation learning models will be crucial for future representation learning research. Finally, we compare our technique with other state-of-the-art generative and contrastive representation learning methods. The code associated with this work is available at https://github.com/mila-iqia/atari-representation-learning
GAIT: A Geometric Approach to Information Theory
Venue: arXiv cs.LG 2020
Year: 2020

We advocate the use of a notion of entropy that reflects the relative abundances of the symbols in an alphabet, as well as the similarities between them. This concept was originally introduced in theoretical ecology to study the diversity of ecosystems. Based on this notion of entropy, we introduce geometry-aware counterparts for several concepts and theorems in information theory. Notably, our proposed divergence exhibits performance on par with state-of-the-art methods based on the Wasserstein distance, but enjoys a closed-form expression that can be computed efficiently. We demonstrate the versatility of our method via experiments on a broad range of domains: training generative models, computing image barycenters, approximating empirical measures and counting modes.
Progressive Gradient Pruning for Classification, Detection and DomainAdaptation
Venue: arXiv cs.LG 2020
Year: 2020

Although deep neural networks (NNs) have achievedstate-of-the-art accuracy in many visual recognition tasks,the growing computational complexity and energy con-sumption of networks remains an issue, especially for ap-plications on platforms with limited resources and requir-ing real-time processing. Filter pruning techniques haverecently shown promising results for the compression andacceleration of convolutional NNs (CNNs). However, thesetechniques involve numerous steps and complex optimisa-tions because some only prune after training CNNs, whileothers prune from scratch during training by integratingsparsity constraints or modifying the loss function.In this paper we propose a new Progressive GradientPruning (PGP) technique for iterative filter pruning dur-ing training. In contrast to previous progressive pruningtechniques, it relies on a novel filter selection criterion thatmeasures the change in filter weights, uses a new hard andsoft pruning strategy and effectively adapts momentum ten-sors during the backward propagation pass. Experimentalresults obtained after training various CNNs on image datafor classification, object detection and domain adaptationbenchmarks indicate that the PGP technique can achievea better trade-off between classification accuracy and net-work (time and memory) complexity than PSFP and otherstate-of-the-art filter pruning techniques.
Autonomous Navigation of MAVs in Unknown Cluttered Environments
Venue: arXiv cs.RO 2020
Year: 2020

This paper presents an autonomous navigation framework for reaching a goal in unknown 3D cluttered environments. The framework consists of three main components. First, a computationally efficient method for mapping the environment from the disparity measurements obtained from a depth sensor. Second, a stochastic method to generate a path to a given goal, taking into account field of view constraints on the space that is assumed to be safe for navigation. Third, a fast method for the online generation of motion plans, taking into account the robot's dynamic constraints, model, and environmental uncertainty and disturbances. To highlight the contribution with respect to the available literature, we provide a qualitative and quantitative comparison with the state of the art methods for reaching a goal and for exploration in unknown environments, showing the superior performance of our approach. To illustrate the effectiveness of the proposed framework, we present experiments in multiple indoors and outdoors environments running the algorithm fully on board and in real-time, using a robotic platform based on the Intel Ready to Fly drone kit, which represents the implementation in the most frugal platform for navigation in unknown cluttered environments demonstrated to date. Open source code is available at:~\url{https://github.com/IntelLabs/autonomousmavs}. The video of the experimental results can be found at~\url{https://youtu.be/Wq0e7vF6nZM}.
Measuring the engagement level in encrypted group conversations by using temporal networks
Venue: arXiv cs.SI 2020
Year: 2020

Chat groups are well-known for their capacity to promote viral political and marketing campaigns, spread fake news, and create rallies by hundreds of thousands on the streets. Also, with the increasing public awareness regarding privacy and surveillance, many platforms have started to deploy end-to-end encrypted protocols. In this context, the group's conversations are not accessible in plain text or readable format by third-party organizations or even the platform owner. Then, the main challenge that emerges is related to getting insights from users' activity of those groups, but without accessing the messages. Previous approaches evaluated the user engagement by assessing user's activity, however, on limited conditions where the data is encrypted, they cannot be applied. In this work, we present a framework for measuring the level of engagement of group conversations and users, without reading the messages. Our framework creates an ensemble of interaction networks that represent the temporal evolution of the conversation, then, we apply the proposed Engagement Index (EI) for each interval of conversations to assess users' participation. Our results in five datasets from real-world WhatsApp Groups indicate that, based on the EI, it is possible to identify the most engaged users within a time interval, create rankings, and group users according to their engagement and monitor their performance over time.