OpenRaiser/Intern-Atlas huggingface dataset:
Informative Path Planning with Local Penalization for Decentralized and Asynchronous Swarm Robotic Search
Venue: arXiv cs.MA 2019
Year: 2019

Decentralized swarm robotic solutions to searching for targets that emit a spatially varying signal promise task parallelism, time efficiency, and fault tolerance. It is, however, challenging for swarm algorithms to offer scalability and efficiency, while preserving mathematical insights into the exhibited behavior. A new decentralized search method (called Bayes-Swarm), founded on batch Bayesian Optimization (BO) principles, is presented here to address these challenges. Unlike swarm heuristics approaches, Bayes-Swarm decouples the knowledge generation and task planning process, thus preserving insights into the emergent behavior. Key contributions lie in: 1) modeling knowledge extraction over trajectories, unlike in BO; 2) time-adaptively balancing exploration/exploitation and using an efficient local penalization approach to account for potential interactions among different robots' planned samples; and 3) presenting an asynchronous implementation of the algorithm. This algorithm is tested on case studies with bimodal and highly multimodal signal distributions. Up to 76 times better efficiency is demonstrated compared to an exhaustive search baseline. The benefits of exploitation/exploration balancing, asynchronous planning, and local penalization, and scalability with swarm size, are also demonstrated.
Application Inference using Machine Learning based Side Channel Analysis
Venue: arXiv cs.CR 2019
Year: 2019

The proliferation of ubiquitous computing requires energy-efficient as well as secure operation of modern processors. Side channel attacks are becoming a critical threat to security and privacy of devices embedded in modern computing infrastructures. Unintended information leakage via physical signatures such as power consumption, electromagnetic emission (EM) and execution time have emerged as a key security consideration for SoCs. Also, information published on purpose at user privilege level accessible through software interfaces results in software only attacks. In this paper, we used a supervised learning based approach for inferring applications executing on android platform based on features extracted from EM side-channel emissions and software exposed dynamic voltage frequency scaling(DVFS) states. We highlight the importance of machine learning based approach in utilizing these multi-dimensional features on a complex SoC, against profiling-based approaches. We also show that learning the instantaneous frequency states polled from onboard frequency driver (cpufreq) is adequate to identify a known application and flag potentially malicious unknown application. The experimental results on benchmarking applications running on ARMv8 processor in Snapdragon 820 board demonstrates early detection of these apps, and atleast 85% accuracy in detecting unknown applications. Overall, the highlight is to utilize a low-complexity path to application inference attacks through learning instantaneous frequency states pattern of CPU core.
Speed Scaling with Tandem Servers
Venue: arXiv cs.DS 2019
Year: 2019

Speed scaling for a tandem server setting is considered, where there is a series of servers, and each job has to be processed by each of the servers in sequence. Servers have a variable speed, their power consumption being a convex increasing function of the speed. We consider the worst case setting as well as the stochastic setting. In the worst case setting, the jobs are assumed to be of unit size with arbitrary (possibly adversarially determined) arrival instants. For this problem, we devise an online speed scaling algorithm that is constant competitive with respect to the optimal offline algorithm that has non-causal information. The proposed algorithm, at all times, uses the same speed on all active servers, such that the total power consumption equals the number of outstanding jobs. In the stochastic setting, we consider a more general tandem network, with a parallel bank of servers at each stage. In this setting, we show that random routing with a simple gated static speed selection is constant competitive. In both cases, the competitive ratio depends only on the power functions, and is independent of the workload and the number of servers.
Pairwise Link Prediction
Venue: arXiv cs.SI 2019
Year: 2019

Link prediction is a common problem in network science that transects many disciplines. The goal is to forecast the appearance of new links or to find links missing in the network. Typical methods for link prediction use the topology of the network to predict the most likely future or missing connections between a pair of nodes. However, network evolution is often mediated by higher-order structures involving more than pairs of nodes; for example, cliques on three nodes (also called triangles) are key to the structure of social networks, but the standard link prediction framework does not directly predict these structures. To address this gap, we propose a new link prediction task called "pairwise link prediction" that directly targets the prediction of new triangles, where one is tasked with finding which nodes are most likely to form a triangle with a given edge. We develop two PageRank-based methods for our pairwise link prediction problem and make natural extensions to existing link prediction methods. Our experiments on a variety of networks show that diffusion based methods are less sensitive to the type of graphs used and more consistent in their results. We also show how our pairwise link prediction framework can be used to get better predictions within the context of standard link prediction evaluation.
Regularizing Neural Networks for Future Trajectory Prediction via Inverse Reinforcement Learning Framework
Venue: arXiv cs.CV 2019
Year: 2019

Predicting distant future trajectories of agents in a dynamic scene is not an easy problem because the future trajectory of an agent is affected by not only his/her past trajectory but also the scene contexts. To tackle this problem, we propose a model based on recurrent neural networks (RNNs) and a novel method for training the model. The proposed model is based on an encoder-decoder architecture where the encoder encodes inputs (past trajectories and scene context information) while the decoder produces a trajectory from the context vector given by the encoder. We train the networks of the proposed model to produce a future trajectory, which is the closest to the true trajectory, while maximizing a reward from a reward function. The reward function is also trained at the same time to maximize the margin between the rewards from the ground-truth trajectory and its estimate. The reward function plays the role of a regularizer for the proposed model so the trained networks are able to better utilize the scene context information for the prediction task. We evaluated the proposed model on several public datasets. Experimental results show that the prediction performance of the proposed model is much improved by the regularization, which outperforms the-state-of-the-arts in terms of accuracy. The implementation codes are available at https://github.com/d1024choi/traj-pred-irl/.
Increasing broadband reach withHybrid Access Networks
Venue: arXiv cs.NI 2019
Year: 2019

End-users and governments force network operators to deploy faster Internet access services everywhere. Access technologies such as FTTx, VDSL2, DOCSIS3.0 can provide such services in cities. However, it is not cost-effective for network operators to deploy them in less densely populated regions. The recently proposed Hybrid Access Networks allow to boost xDSL networks by using the available capacity in existing LTE networks. We first present the three architectures defined by the Broadband Forum for such Hybrid Access Networks. Then we describe our experience with the implementation and the deployment of Multipath TCP-based Hybrid Access Networks.
Out-of-Distribution Detection Using Neural Rendering Generative Models
Venue: arXiv cs.LG 2019
Year: 2019

Out-of-distribution (OoD) detection is a natural downstream task for deep generative models, due to their ability to learn the input probability distribution. There are mainly two classes of approaches for OoD detection using deep generative models, viz., based on likelihood measure and the reconstruction loss. However, both approaches are unable to carry out OoD detection effectively, especially when the OoD samples have smaller variance than the training samples. For instance, both flow based and VAE models assign higher likelihood to images from SVHN when trained on CIFAR-10 images. We use a recently proposed generative model known as neural rendering model (NRM) and derive metrics for OoD. We show that NRM unifies both approaches since it provides a likelihood estimate and also carries out reconstruction in each layer of the neural network. Among various measures, we found the joint likelihood of latent variables to be the most effective one for OoD detection. Our results show that when trained on CIFAR-10, lower likelihood (of latent variables) is assigned to SVHN images. Additionally, we show that this metric is consistent across other OoD datasets. To the best of our knowledge, this is the first work to show consistently lower likelihood for OoD data with smaller variance with deep generative models.
Optimally Self-Healing IoT Choreographies
Venue: arXiv cs.NI 2019
Year: 2019

In the industrial Internet of Things domain, applications are moving from the Cloud into the edge, closer to the devices producing and consuming data. This means applications move from the scalable and homogeneous cloud environment into a constrained heterogeneous edge network. Making edge applications reliable enough to fulfill Industrie 4.0 use cases is still an open research challenge. Maintaining operation of an edge system requires advanced management techniques to mitigate the failure of devices. This paper tackles this challenge with a twofold approach: (1) a policy-enabled failure detector that enables adaptable failure detection and (2) an allocation component for the efficient selection of failure mitigation actions. We evaluate the parameters and performance of our failure detection approach and the performance of an energy-efficient allocation technique, and present a vision for a complete system as well as an example use case.
Neural Networks as Explicit Word-Based Rules
Venue: arXiv cs.CL 2019
Year: 2019

Filters of convolutional networks used in computer vision are often visualized as image patches that maximize the response of the filter. We use the same approach to interpret weight matrices in simple architectures for natural language processing tasks. We interpret a convolutional network for sentiment classification as word-based rules. Using the rule, we recover the performance of the original model.
String Attractors and Combinatorics on Words
Venue: arXiv cs.DS 2019
Year: 2019

The notion of \emph{string attractor} has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-based compressors. A string attractor for a word $w=w[1]w[2]\cdots w[n]$ is a subset $Γ$ of the positions $\{1,\ldots,n\}$, such that all distinct factors of $w$ have an occurrence crossing at least one of the elements of $Γ$. While finding the smallest string attractor for a word is a NP-complete problem, it has been proved in [Kempa and Prezza, 2018] that dictionary compressors can be interpreted as algorithms approximating the smallest string attractor for a given word. In this paper we explore the notion of string attractor from a combinatorial point of view, by focusing on several families of finite words. The results presented in the paper suggest that the notion of string attractor can be used to define new tools to investigate combinatorial properties of the words.
About Fibonacci trees. II -- generalized Fibonacci trees
Venue: arXiv cs.DM 2019
Year: 2019

In this second paper, we look at the following question: are the properties of the trees associated to the tilings $\{p,4\}$ and $\{p$+$2,3\}$ of the hyperbolic plane still true if we consider a finitely generated tree by the same rules but rooted at a black node? The direct answer is no, but new properties arise, no more complex than in the case of a tree rooted at a white node, and worth of interest. The present paper is an extension of the previous paper: arXiv:1904.12135.
Deadeye Visualization Revisited: Investigation of Preattentiveness and Applicability in Virtual Environments
Venue: arXiv cs.HC 2019
Year: 2019

Visualizations rely on highlighting to attract and guide our attention. To make an object of interest stand out independently from a number of distractors, the underlying visual cue, e.g., color, has to be preattentive. In our prior work, we introduced Deadeye as an instantly recognizable highlighting technique that works by rendering the target object for one eye only. In contrast to prior approaches, Deadeye excels by not modifying any visual properties of the target. However, in the case of 2D visualizations, the method requires an additional setup to allow dichoptic presentation, which is a considerable drawback. As a follow-up to requests from the community, this paper explores Deadeye as a highlighting technique for 3D visualizations, because such stereoscopic scenarios support dichoptic presentation out of the box. Deadeye suppresses binocular disparities for the target object, so we cannot assume the applicability of our technique as a given fact. With this motivation, the paper presents quantitative evaluations of Deadeye in VR, including configurations with multiple heterogeneous distractors as an important robustness challenge. After confirming the preserved preattentiveness (all average accuracies above 90 %) under such real-world conditions, we explore VR volume rendering as an example application scenario for Deadeye. We depict a possible workflow for integrating our technique, conduct an exploratory survey to demonstrate benefits and limitations, and finally provide related design implications.
Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications
Venue: arXiv cs.DS 2019
Year: 2019

In this paper we identify a new class of sparse near-quadratic random Boolean matrices that have full row rank over $\mathbb{F}_2=\{0,1\}$ with high probability and can be transformed into echelon form in almost linear time by a simple version of Gauss elimination. The random matrix with dimensions $n(1-\varepsilon) \times n$ is generated as follows: In each row, identify a block of length $L=O((\log n)/\varepsilon)$ at a random position. The entries outside the block are 0, the entries inside the block are given by fair coin tosses. Sorting the rows according to the positions of the blocks transforms the matrix into a kind of band matrix, on which, as it turns out, Gauss elimination works very efficiently with high probability. For the proof, the effects of Gauss elimination are interpreted as a ("coin-flipping") variant of Robin Hood hashing, whose behaviour can be captured in terms of a simple Markov model from queuing theory. Bounds for expected construction time and high success probability follow from results in this area. By employing hashing, this matrix family leads to a new implementation of a retrieval data structure, which represents an arbitrary function $f\colon S \to \{0,1\}$ for some set $S$ of $m=(1-\varepsilon)n$ keys. It requires $m/(1-\varepsilon)$ bits of space, construction takes $O(m/\varepsilon^2$) expected time on a word RAM, while queries take $O(1/\varepsilon)$ time and access only one contiguous segment of $O((\log m)/\varepsilon)$ bits in the representation. The method is competitive with state-of-the-art methods. By well-established methods the retrieval data structure leads to efficient constructions of (static) perfect hash functions and (static) Bloom filters with almost optimal space and very local storage access patterns for queries.
Metamorphic Detection of Adversarial Examples in Deep Learning Models With Affine Transformations
Venue: arXiv cs.CV 2019
Year: 2019

Adversarial attacks are small, carefully crafted perturbations, imperceptible to the naked eye; that when added to an image cause deep learning models to misclassify the image with potentially detrimental outcomes. With the rise of artificial intelligence models in consumer safety and security intensive industries such as self-driving cars, camera surveillance and face recognition, there is a growing need for guarding against adversarial attacks. In this paper, we present an approach that uses metamorphic testing principles to automatically detect such adversarial attacks. The approach can detect image manipulations that are so small, that they are impossible to detect by a human through visual inspection. By applying metamorphic relations based on distance ratio preserving affine image transformations which compare the behavior of the original and transformed image; we show that our proposed approach can determine whether or not the input image is adversarial with a high degree of accuracy.
Fast Haar Transforms for Graph Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Graph Neural Networks (GNNs) have become a topic of intense research recently due to their powerful capability in high-dimensional classification and regression tasks for graph-structured data. However, as GNNs typically define the graph convolution by the orthonormal basis for the graph Laplacian, they suffer from high computational cost when the graph size is large. This paper introduces Haar basis which is a sparse and localized orthonormal system for a coarse-grained chain on graph. The graph convolution under Haar basis, called Haar convolution, can be defined accordingly for GNNs. The sparsity and locality of the Haar basis allow Fast Haar Transforms (FHTs) on graph, by which a fast evaluation of Haar convolution between graph data and filters can be achieved. We conduct experiments on GNNs equipped with Haar convolution, which demonstrates state-of-the-art results on graph-based regression and node classification tasks.
Hacking VMAF with Video Color and Contrast Distortion
Venue: arXiv cs.MM 2019
Year: 2019

Video quality measurement takes an important role in many applications. Full-reference quality metrics which are usually used in video codecs comparisons are expected to reflect any changes in videos. In this article, we consider different color corrections of compressed videos which increase the values of full-reference metric VMAF and almost don't decrease other widely-used metric SSIM. The proposed video contrast enhancement approach shows the metric inapplicability in some cases for video codecs comparisons, as it may be used for cheating in the comparisons via tuning to improve this metric values.
Cake cutting: Explicit examples for impossibility results
Venue: arXiv cs.GT 2019
Year: 2019

In this article we suggest a model of computation for the cake cutting problem. In this model the mediator can ask the same queries as in the Robertson-Webb model but he or she can only perform algebraic operations as in the Blum-Shub-Smale model. All existing algorithms described in the Robertson-Webb model can be described in this new model.We show that in this model there exist explicit couples of measures for which no algorithm outputs an equitable fair division with connected parts.We also show that there exist explicit set of measures for which no algorithm in this model outputs a fair division which maximizes the utilitarian social welfare function.The main tool of our approach is Galois theory.
Sparse Networks from Scratch: Faster Training without Losing Performance
Venue: arXiv cs.LG 2019
Year: 2019

We demonstrate the possibility of what we call sparse learning: accelerated training of deep neural networks that maintain sparse weights throughout training while achieving dense performance levels. We accomplish this by developing sparse momentum, an algorithm which uses exponentially smoothed gradients (momentum) to identify layers and weights which reduce the error efficiently. Sparse momentum redistributes pruned weights across layers according to the mean momentum magnitude of each layer. Within a layer, sparse momentum grows weights according to the momentum magnitude of zero-valued weights. We demonstrate state-of-the-art sparse performance on MNIST, CIFAR-10, and ImageNet, decreasing the mean error by a relative 8%, 15%, and 6% compared to other sparse algorithms. Furthermore, we show that sparse momentum reliably reproduces dense performance levels while providing up to 5.61x faster training. In our analysis, ablations show that the benefits of momentum redistribution and growth increase with the depth and size of the network. Additionally, we find that sparse momentum is insensitive to the choice of its hyperparameters suggesting that sparse momentum is robust and easy to use.
On Designing Machine Learning Models for Malicious Network Traffic Classification
Venue: arXiv cs.CR 2019
Year: 2019

Machine learning (ML) started to become widely deployed in cyber security settings for shortening the detection cycle of cyber attacks. To date, most ML-based systems are either proprietary or make specific choices of feature representations and machine learning models. The success of these techniques is difficult to assess as public benchmark datasets are currently unavailable. In this paper, we provide concrete guidelines and recommendations for using supervised ML in cyber security. As a case study, we consider the problem of botnet detection from network traffic data. Among our findings we highlight that: (1) feature representations should take into consideration attack characteristics; (2) ensemble models are well-suited to handle class imbalance; (3) the granularity of ground truth plays an important role in the success of these methods.
Explaining an increase in predicted risk for clinical alerts
Venue: arXiv cs.LG 2019
Year: 2019

Much work aims to explain a model's prediction on a static input. We consider explanations in a temporal setting where a stateful dynamical model produces a sequence of risk estimates given an input at each time step. When the estimated risk increases, the goal of the explanation is to attribute the increase to a few relevant inputs from the past. While our formal setup and techniques are general, we carry out an in-depth case study in a clinical setting. The goal here is to alert a clinician when a patient's risk of deterioration rises. The clinician then has to decide whether to intervene and adjust the treatment. Given a potentially long sequence of new events since she last saw the patient, a concise explanation helps her to quickly triage the alert. We develop methods to lift static attribution techniques to the dynamical setting, where we identify and address challenges specific to dynamics. We then experimentally assess the utility of different explanations of clinical alerts through expert evaluation.