OpenRaiser/Intern-Atlas huggingface dataset:
Dynamically Weighted Ensemble-based Prediction System for Adaptively Modeling Driver Reaction Time
Venue: arXiv cs.HC 2019
Year: 2019

Predicting a driver's cognitive state, or more specifically, modeling a driver's reaction time (RT) in response to the appearance of a potential hazard warrants urgent research. In the last two decades, the electric field that is generated by the activities in the brain, monitored by an electroencephalogram (EEG), has been proven to be a robust physiological indicator of human behavior. However, mapping the human brain can be extremely challenging, especially owing to the variability in human beings over time, both within and among individuals. Factors such as fatigue, inattention and stress can induce homeostatic changes in the brain, which affect the observed relationship between brain dynamics and behavioral performance, and thus make the existing systems for predicting RT difficult to generalize. To solve this problem, an ensemble-based weighted prediction system is presented herein. This system comprises a set of prediction submodels that are individually trained using groups of data with similar EEG-RT relationships. To obtain a final prediction, the prediction outcomes of the sub-models are then multiplied by weights that are derived from the EEG alpha coherences of 10 channels plus theta band powers of 30 channels, whose changes were found to be indicators of variations in the EEG-RT relationship. The results thus obtained reveal that the proposed system with a time-varying adaptive weighting mechanism significantly outperforms the conventional system in modeling a driver's RT. The adaptive design of the proposed system demonstrates its feasibility in coping with the variability in the brain-behavior relationship. In this contribution surprisingly simple EEG-based adaptive methods are used in combination with an ensemble scheme to significantly increase system performance.
Domain Adaptation for Real-Time Student Performance Prediction
Venue: arXiv cs.CY 2019
Year: 2019

Increasingly fast development and update cycle of online course contents, and diverse demographics of students in each online classroom, make student performance prediction in real-time (before the course finishes) and/or on curriculum without specific historical performance data available interesting topics for both industrial research and practical needs. In this research, we tackle the problem of real-time student performance prediction with on-going courses in a domain adaptation framework, which is a system trained on students' labeled outcome from one set of previous coursework but is meant to be deployed on another. In particular, we first introduce recently-developed GritNet architecture which is the current state of the art for student performance prediction problem, and develop a new \emph{unsupervised} domain adaptation method to transfer a GritNet trained on a past course to a new course without any (students' outcome) label. Our results for real Udacity students' graduation predictions show that the GritNet not only \emph{generalizes} well from one course to another across different Nanodegree programs, but enhances real-time predictions explicitly in the first few weeks when accurate predictions are most challenging.
Data-Driven Clustering via Parameterized Lloyd's Families
Venue: arXiv cs.DS 2019
Year: 2019

Algorithms for clustering points in metric spaces is a long-studied area of research. Clustering has seen a multitude of work both theoretically, in understanding the approximation guarantees possible for many objective functions such as k-median and k-means clustering, and experimentally, in finding the fastest algorithms and seeding procedures for Lloyd's algorithm. The performance of a given clustering algorithm depends on the specific application at hand, and this may not be known up front. For example, a "typical instance" may vary depending on the application, and different clustering heuristics perform differently depending on the instance. In this paper, we define an infinite family of algorithms generalizing Lloyd's algorithm, with one parameter controlling the initialization procedure, and another parameter controlling the local search procedure. This family of algorithms includes the celebrated k-means++ algorithm, as well as the classic farthest-first traversal algorithm. We design efficient learning algorithms which receive samples from an application-specific distribution over clustering instances and learn a near-optimal clustering algorithm from the class. We show the best parameters vary significantly across datasets such as MNIST, CIFAR, and mixtures of Gaussians. Our learned algorithms never perform worse than k-means++, and on some datasets we see significant improvements.
The Reachability Problem for Petri Nets is Not Elementary
Venue: arXiv cs.FL 2019
Year: 2019

Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes. The central algorithmic problem for Petri nets is reachability: whether from the given initial configuration there exists a sequence of valid execution steps that reaches the given final configuration. The complexity of the problem has remained unsettled since the 1960s, and it is one of the most prominent open questions in the theory of verification. Decidability was proved by Mayr in his seminal STOC 1981 work, and the currently best published upper bound is non-primitive recursive Ackermannian of Leroux and Schmitz from LICS 2019. We establish a non-elementary lower bound, i.e. that the reachability problem needs a tower of exponentials of time and space. Until this work, the best lower bound has been exponential space, due to Lipton in 1976. The new lower bound is a major breakthrough for several reasons. Firstly, it shows that the reachability problem is much harder than the coverability (i.e., state reachability) problem, which is also ubiquitous but has been known to be complete for exponential space since the late 1970s. Secondly, it implies that a plethora of problems from formal languages, logic, concurrent systems, process calculi and other areas, that are known to admit reductions from the Petri nets reachability problem, are also not elementary. Thirdly, it makes obsolete the currently best lower bounds for the reachability problems for two key extensions of Petri nets: with branching and with a pushdown stack.
A Novel Warehouse Multi-Robot Automation System with Semi-Complete and Computationally Efficient Path Planning and Adaptive Genetic Task Allocation Algorithms
Venue: arXiv cs.MA 2019
Year: 2019

We consider the problem of warehouse multi-robot automation system in discrete-time and discrete-space configuration with focus on the task allocation and conflict-free path planning. We present a system design where a centralized server handles the task allocation and each robot performs local path planning distributively. A genetic-based task allocation algorithm is firstly presented, with modification to enable heuristic learning. A semi-complete potential field based local path planning algorithm is then proposed, named the recursive excitation/relaxation artificial potential field (RERAPF). A mathematical proof is also presented to show the semi-completeness of the RERAPF algorithm. The main contribution of this paper is the modification of conventional artificial potential field (APF) to be semi-complete while computationally efficient, resolving the traditional issue of incompleteness. Simulation results are also presented for performance evaluation of the proposed path planning algorithm and the overall system.
A Microbenchmark Characterization of the Emu Chick
Venue: arXiv cs.DC 2019
Year: 2019

The Emu Chick is a prototype system designed around the concept of migratory memory-side processing. Rather than transferring large amounts of data across power-hungry, high-latency interconnects, the Emu Chick moves lightweight thread contexts to near-memory cores before the beginning of each memory read. The current prototype hardware uses FPGAs to implement cache-less "Gossamer cores for doing computational work and a stationary core to run basic operating system functions and migrate threads between nodes. In this multi-node characterization of the Emu Chick, we extend an earlier single-node investigation (Hein, et al. AsHES 2018) of the the memory bandwidth characteristics of the system through benchmarks like STREAM, pointer chasing, and sparse matrix-vector multiplication. We compare the Emu Chick hardware to architectural simulation and an Intel Xeon-based platform. Our results demonstrate that for many basic operations the Emu Chick can use available memory bandwidth more efficiently than a more traditional, cache-based architecture although bandwidth usage suffers for computationally intensive workloads like SpMV. Moreover, the Emu Chick provides stable, predictable performance with up to 65% of the peak bandwidth utilization on a random-access pointer chasing benchmark with weak locality.
In-Edge AI: Intelligentizing Mobile Edge Computing, Caching and Communication by Federated Learning
Venue: arXiv cs.NI 2019
Year: 2019

Recently, along with the rapid development of mobile communication technology, edge computing theory and techniques have been attracting more and more attentions from global researchers and engineers, which can significantly bridge the capacity of cloud and requirement of devices by the network edges, and thus can accelerate the content deliveries and improve the quality of mobile services. In order to bring more intelligence to the edge systems, compared to traditional optimization methodology, and driven by the current deep learning techniques, we propose to integrate the Deep Reinforcement Learning techniques and Federated Learning framework with the mobile edge systems, for optimizing the mobile edge computing, caching and communication. And thus, we design the "In-Edge AI" framework in order to intelligently utilize the collaboration among devices and edge nodes to exchange the learning parameters for a better training and inference of the models, and thus to carry out dynamic system-level optimization and application-level enhancement while reducing the unnecessary system communication load. "In-Edge AI" is evaluated and proved to have near-optimal performance but relatively low overhead of learning, while the system is cognitive and adaptive to the mobile communication systems. Finally, we discuss several related challenges and opportunities for unveiling a promising upcoming future of "In-Edge AI".
Compressed Sensing with Adversarial Sparse Noise via L1 Regression
Venue: arXiv cs.DS 2019
Year: 2019

We present a simple and effective algorithm for the problem of \emph{sparse robust linear regression}. In this problem, one would like to estimate a sparse vector $w^* \in \mathbb{R}^n$ from linear measurements corrupted by sparse noise that can arbitrarily change an adversarially chosen $η$ fraction of measured responses $y$, as well as introduce bounded norm noise to the responses. For Gaussian measurements, we show that a simple algorithm based on L1 regression can successfully estimate $w^*$ for any $η< η_0 \approx 0.239$, and that this threshold is tight for the algorithm. The number of measurements required by the algorithm is $O(k \log \frac{n}{k})$ for $k$-sparse estimation, which is within constant factors of the number needed without any sparse noise. Of the three properties we show---the ability to estimate sparse, as well as dense, $w^*$; the tolerance of a large constant fraction of outliers; and tolerance of adversarial rather than distributional (e.g., Gaussian) dense noise---to the best of our knowledge, no previous result achieved more than two.
An Evaluation of Bayesian Methods for Bathymetry-based Localization of Autonomous Underwater Robots
Venue: arXiv cs.RO 2019
Year: 2019

This paper presents an evaluation of a number of probabilistic algorithms for localization of autonomous underwater vehicles (AUVs) using bathymetry data. The algorithms, based on the principles of the Bayes filter, work by fusing bathymetry information with depth and altitude data from an AUV. Four different Bayes filter-based algorithms are used to design the localization algorithms: the Extended Kalman Filter (EKF), Unscented Kalman Filter (UKF), Particle Filter (PF), and Marginalized Particle Filter (MPF). We evaluate the performance of these four Bayesian bathymetry-based AUV localization approaches under variable conditions and available computational resources. The localization algorithms overcome unique challenges of the underwater domain, including visual distortion and radio frequency (RF) signal attenuation, which often make landmark-based localization infeasible. Evaluation results on real-world bathymetric data show the effectiveness of each algorithm under a variety of conditions, with the MPF being the most accurate.
On the Optimal Broadcast Rate of the Two-Sender Unicast Index Coding Problem with Fully-Participated Interactions
Venue: arXiv cs.IT 2019
Year: 2019

The problem of two-sender unicast index coding consists of two senders and a set of receivers. Each receiver demands a unique message and possesses some of the messages demanded by other receivers as its side-information. Every demanded message is present with at least one of the senders. Senders avail the knowledge of the side-information at the receivers to reduce the number of broadcast transmissions. Solution to this problem consists of finding the optimal number of coded transmissions from the two senders. One important class of the two-sender problem consists of the messages at the senders and the side-information at the receivers satisfying \emph{fully-participated interactions}. This paper provides the optimal broadcast rates, for all the unsolved cases of the two-sender problem with fully-participated interactions when the associated \emph{interaction digraphs} contain cycles. The optimal broadcast rates are provided in terms of those of the three independent single-sender problems associated with the two-sender problem. This paper also provides an achievable broadcast rate with $t$-bit messages for any finite $t$ and any two-sender problem with fully-participated interactions belonging to $(i)$ any one of the six instances (classes) of the two-sender problem when the associated interaction digraph does not contain any cycle, and $(ii)$ one of the classes of the two-sender problem when the associated interaction digraph contains cycles. The achievable broadcast rates are obtained by exploiting the symmetries of the confusion graph to color the same according to the two-sender graph coloring.
Visual navigation for airborne control of ground robots from tethered platform: creation of the first prototype
Venue: arXiv cs.RO 2019
Year: 2019

We propose control systems for the coordination of the ground robots. We develop robot efficient coordination using the devices located on towers or a tethered aerial apparatus tracing the robots on controlled area and supervising their environment including natural and artificial markings. The simple prototype of such a system was created in the Laboratory of Applied Mathematics of Ariel University (under the supervision of Prof. Domoshnitsky Alexander) in collaboration with company TRANSIST VIDEO LLC (Skolkovo, Moscow). We plan to create much more complicated prototype using Kamin grant (Israel)
The Privacy Policy Landscape After the GDPR
Venue: arXiv cs.CR 2019
Year: 2019

The EU General Data Protection Regulation (GDPR) is one of the most demanding and comprehensive privacy regulations of all time. A year after it went into effect, we study its impact on the landscape of privacy policies online. We conduct the first longitudinal, in-depth, and at-scale assessment of privacy policies before and after the GDPR. We gauge the complete consumption cycle of these policies, from the first user impressions until the compliance assessment. We create a diverse corpus of two sets of 6,278 unique English-language privacy policies from inside and outside the EU, covering their pre-GDPR and the post-GDPR versions. The results of our tests and analyses suggest that the GDPR has been a catalyst for a major overhaul of the privacy policies inside and outside the EU. This overhaul of the policies, manifesting in extensive textual changes, especially for the EU-based websites, comes at mixed benefits to the users. While the privacy policies have become considerably longer, our user study with 470 participants on Amazon MTurk indicates a significant improvement in the visual representation of privacy policies from the users' perspective for the EU websites. We further develop a new workflow for the automated assessment of requirements in privacy policies. Using this workflow, we show that privacy policies cover more data practices and are more consistent with seven compliance requirements post the GDPR. We also assess how transparent the organizations are with their privacy practices by performing specificity analysis. In this analysis, we find evidence for positive changes triggered by the GDPR, with the specificity level improving on average. Still, we find the landscape of privacy policies to be in a transitional phase; many policies still do not meet several key GDPR requirements or their improved coverage comes with reduced specificity.
DeepOrigin: End-to-End Deep Learning for Detection of New Malware Families
Venue: arXiv cs.CR 2019
Year: 2019

In this paper, we present a novel method of differentiating known from previously unseen malware families. We utilize transfer learning by learning compact file representations that are used for a new classification task between previously seen malware families and novel ones. The learned file representations are composed of static and dynamic features of malware and are invariant to small modifications that do not change their malicious functionality. Using an extensive dataset that consists of thousands of variants of malicious files, we were able to achieve 97.7% accuracy when classifying between seen and unseen malware families. Our method provides an important focalizing tool for cybersecurity researchers and greatly improves the overall ability to adapt to the fast-moving pace of the current threat landscape.
On $k$-abelian Equivalence and Generalized Lagrange Spectra
Venue: arXiv cs.DM 2019
Year: 2019

We study the set of $k$-abelian critical exponents of all Sturmian words. It has been proven that in the case $k = 1$ this set coincides with the Lagrange spectrum. Thus the sets obtained when $k > 1$ can be viewed as generalized Lagrange spectra. We characterize these generalized spectra in terms of the usual Lagrange spectrum and prove that when $k > 1$ the spectrum is a dense non-closed set. This is in contrast with the case $k = 1$, where the spectrum is a closed set containing a discrete part and a half-line. We describe explicitly the least accumulation points of the generalized spectra. Our geometric approach allows the study of $k$-abelian powers in Sturmian words by means of continued fractions.
Tunable Measures for Information Leakage and Applications to Privacy-Utility Tradeoffs
Venue: arXiv cs.IT 2019
Year: 2019

We introduce a tunable measure for information leakage called maximal alpha-leakage. This measure quantifies the maximal gain of an adversary in inferring any (potentially random) function of a dataset from a release of the data. The inferential capability of the adversary is, in turn, quantified by a class of adversarial loss functions that we introduce as $α$-loss, $α\in[1,\infty]$. The choice of $α$ determines the specific adversarial action and ranges from refining a belief (about any function of the data) for $α=1$ to guessing the most likely value for $α=\infty$ while refining the $α^{th}$ moment of the belief for $α$ in between. Maximal alpha-leakage then quantifies the adversarial gain under $α$-loss over all possible functions of the data. In particular, for the extremal values of $α=1$ and $α=\infty$, maximal alpha-leakage simplifies to mutual information and maximal leakage, respectively. For $α\in(1,\infty)$ this measure is shown to be the Arimoto channel capacity of order $α$. We show that maximal alpha-leakage satisfies data processing inequalities and a sub-additivity property thereby allowing for a weak composition result. Building upon these properties, we use maximal alpha-leakage as the privacy measure and study the problem of data publishing with privacy guarantees, wherein the utility of the released data is ensured via a hard distortion constraint. Unlike average distortion, hard distortion provides a deterministic guarantee of fidelity. We show that under a hard distortion constraint, for $α>1$ the optimal mechanism is independent of $α$, and therefore, the resulting optimal tradeoff is the same for all values of $α>1$. Finally, the tunability of maximal alpha-leakage as a privacy measure is also illustrated for binary data with average Hamming distortion as the utility measure.
Nonconvex Robust Low-rank Matrix Recovery
Venue: arXiv cs.IT 2019
Year: 2019

In this paper we study the problem of recovering a low-rank matrix from a number of random linear measurements that are corrupted by outliers taking arbitrary values. We consider a nonsmooth nonconvex formulation of the problem, in which we explicitly enforce the low-rank property of the solution by using a factored representation of the matrix variable and employ an $\ell_1$-loss function to robustify the solution against outliers. We show that even when a constant fraction (which can be up to almost half) of the measurements are arbitrarily corrupted, as long as certain measurement operators arising from the measurement model satisfy the so-called $\ell_1/\ell_2$-restricted isometry property, the ground-truth matrix can be exactly recovered from any global minimum of the resulting optimization problem. Furthermore, we show that the objective function of the optimization problem is sharp and weakly convex. Consequently, a subgradient Method (SubGM) with geometrically diminishing step sizes will converge linearly to the ground-truth matrix when suitably initialized. We demonstrate the efficacy of the SubGM for the nonconvex robust low-rank matrix recovery problem with various numerical experiments.
Hierarchical Deep Multiagent Reinforcement Learning with Temporal Abstraction
Venue: arXiv cs.LG 2019
Year: 2019

Multiagent reinforcement learning (MARL) is commonly considered to suffer from non-stationary environments and exponentially increasing policy space. It would be even more challenging when rewards are sparse and delayed over long trajectories. In this paper, we study hierarchical deep MARL in cooperative multiagent problems with sparse and delayed reward. With temporal abstraction, we decompose the problem into a hierarchy of different time scales and investigate how agents can learn high-level coordination based on the independent skills learned at the low level. Three hierarchical deep MARL architectures are proposed to learn hierarchical policies under different MARL paradigms. Besides, we propose a new experience replay mechanism to alleviate the issue of the sparse transitions at the high level of abstraction and the non-stationarity of multiagent learning. We empirically demonstrate the effectiveness of our approaches in two domains with extremely sparse feedback: (1) a variety of Multiagent Trash Collection tasks, and (2) a challenging online mobile game, i.e., Fever Basketball Defense.