OpenRaiser/Intern-Atlas huggingface dataset:
Routing Game on Parallel Networks: the Convergence of Atomic to Nonatomic
Venue: arXiv cs.GT 2018
Year: 2018

We consider an instance of a nonatomic routing game. We assume that the network is parallel, that is, constituted of only two nodes, an origin and a destination. We consider infinitesimal players that have a symmetric network cost, but are heterogeneous through their set of feasible strategies and their individual utilities. We show that if an atomic routing game instance is correctly defined to approximate the nonatomic instance, then an atomic Nash Equilibrium will approximate the nonatomic Wardrop Equilibrium. We give explicit bounds on the distance between the equilibria according to the parameters of the atomic instance. This approximation gives a method to compute the Wardrop equilibrium at an arbitrary precision.
Deep Painterly Harmonization
Venue: arXiv cs.GR 2018
Year: 2018

Copying an element from a photo and pasting it into a painting is a challenging task. Applying photo compositing techniques in this context yields subpar results that look like a collage --- and existing painterly stylization algorithms, which are global, perform poorly when applied locally. We address these issues with a dedicated algorithm that carefully determines the local statistics to be transferred. We ensure both spatial and inter-scale statistical consistency and demonstrate that both aspects are key to generating quality results. To cope with the diversity of abstraction levels and types of paintings, we introduce a technique to adjust the parameters of the transfer depending on the painting. We show that our algorithm produces significantly better results than photo compositing or global stylization techniques and that it enables creative painterly edits that would be otherwise difficult to achieve.
An ADMM-Based Universal Framework for Adversarial Attacks on Deep Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Deep neural networks (DNNs) are known vulnerable to adversarial attacks. That is, adversarial examples, obtained by adding delicately crafted distortions onto original legal inputs, can mislead a DNN to classify them as any target labels. In a successful adversarial attack, the targeted mis-classification should be achieved with the minimal distortion added. In the literature, the added distortions are usually measured by L0, L1, L2, and L infinity norms, namely, L0, L1, L2, and L infinity attacks, respectively. However, there lacks a versatile framework for all types of adversarial attacks. This work for the first time unifies the methods of generating adversarial examples by leveraging ADMM (Alternating Direction Method of Multipliers), an operator splitting optimization approach, such that L0, L1, L2, and L infinity attacks can be effectively implemented by this general framework with little modifications. Comparing with the state-of-the-art attacks in each category, our ADMM-based attacks are so far the strongest, achieving both the 100% attack success rate and the minimal distortion.
A Counting Semantics for Monitoring LTL Specifications over Finite Traces
Venue: arXiv cs.LO 2018
Year: 2018

We consider the problem of monitoring a Linear Time Logic (LTL) specification that is defined on infinite paths, over finite traces. For example, we may need to draw a verdict on whether the system satisfies or violates the property "p holds infinitely often." The problem is that there is always a continuation of a finite trace that satisfies the property and a different continuation that violates it. We propose a two-step approach to address this problem. First, we introduce a counting semantics that computes the number of steps to witness the satisfaction or violation of a formula for each position in the trace. Second, we use this information to make a prediction on inconclusive suffixes. In particular, we consider a good suffix to be one that is shorter than the longest witness for a satisfaction, and a bad suffix to be shorter than or equal to the longest witness for a violation. Based on this assumption, we provide a verdict assessing whether a continuation of the execution on the same system will presumably satisfy or violate the property.
Visualization Tool for Environmental Sensing and Public Health Data
Venue: arXiv cs.HC 2018
Year: 2018

To assist residents affected by oil and gas development, public health professionals in a non-profit organization have collected community data, including symptoms, air quality, and personal stories. However, the organization was unable to aggregate and visualize these data computationally. We present the Environmental Health Channel, an interactive web-based tool for visualizing environmental sensing and public health data. This tool enables discussing and disseminating scientific evidence to reveal local environmental and health impacts of industrial activities.
Characterising information-theoretic storage and transfer in continuous time processes
Venue: arXiv cs.IT 2018
Year: 2018

The characterisation of information processing is an important task in complex systems science. Information dynamics is a quantitative methodology for modelling the intrinsic information processing conducted by a process represented as a time series, but to date has only been formulated in discrete time. Building on previous work which demonstrated how to formulate transfer entropy in continuous time, we give a total account of information processing in this setting, incorporating information storage. We find that a convergent rate of predictive capacity, comprised of the transfer entropy and active information storage, does not exist, arising through divergent rates of active information storage. We identify that active information storage can be decomposed into two separate quantities that characterise predictive capacity stored in a process: active memory utilisation and instantaneous predictive capacity. The latter involves prediction related to path regularity and so solely inherits the divergent properties of the active information storage, whilst the former permits definitions of pathwise and rate quantities. We formulate measures of memory utilisation for jump and neural spiking processes and illustrate measures of information processing in synthetic neural spiking models and coupled Ornstein-Uhlenbeck models. The application to synthetic neural spiking models demonstrates that active memory utilisation for point processes consists of discontinuous jump contributions (at spikes) interrupting a continuously varying contribution (relating to waiting times between spikes), complementing the behaviour previously demonstrated for transfer entropy in these processes.
A Deep Active Survival Analysis Approach for Precision Treatment Recommendations: Application of Prostate Cancer
Venue: arXiv cs.LG 2018
Year: 2018

Survival analysis has been developed and applied in the number of areas including manufacturing, finance, economics and healthcare. In healthcare domain, usually clinical data are high-dimensional, sparse and complex and sometimes there exists few amount of time-to-event (labeled) instances. Therefore building an accurate survival model from electronic health records is challenging. With this motivation, we address this issue and provide a new survival analysis framework using deep learning and active learning with a novel sampling strategy. First, our approach provides better representation with lower dimensions from clinical features using labeled (time-to-event) and unlabeled (censored) instances and then actively trains the survival model by labeling the censored data using an oracle. As a clinical assistive tool, we introduce a simple effective treatment recommendation approach based on our survival model. In the experimental study, we apply our approach on SEER-Medicare data related to prostate cancer among African-Americans and white patients. The results indicate that our approach outperforms significantly than baseline models.
Recurrent Neural Networks for Person Re-identification Revisited
Venue: arXiv cs.CV 2018
Year: 2018

The task of person re-identification has recently received rising attention due to the high performance achieved by new methods based on deep learning. In particular, in the context of video-based re-identification, many state-of-the-art works have explored the use of Recurrent Neural Networks (RNNs) to process input sequences. In this work, we revisit this tool by deriving an approximation which reveals the small effect of recurrent connections, leading to a much simpler feed-forward architecture. Using the same parameters as the recurrent version, our proposed feed-forward architecture obtains very similar accuracy. More importantly, our model can be combined with a new training process to significantly improve re-identification performance. Our experiments demonstrate that the proposed models converge substantially faster than recurrent ones, with accuracy improvements by up to 5% on two datasets. The performance achieved is better or on par with other RNN-based person re-identification techniques.
Echo-Liquid State Deep Learning for $360^\circ$ Content Transmission and Caching in Wireless VR Networks with Cellular-Connected UAVs
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, the problem of content caching and transmission is studied for a wireless virtual reality (VR) network in which unmanned aerial vehicles (UAVs) capture videos on live games or sceneries and transmit them to small base stations (SBSs) that service the VR users. However, due to its limited capacity, the wireless network may not be able to meet the delay requirements of such 360 content transmissions. To meet the VR delay requirements, the UAVs can extract specific visible content (e.g., user field of view) from the original 360 data and send this visible content to the users so as to reduce the traffic load over backhaul and radio access links. To further alleviate the UAV-SBS backhaul traffic, the SBSs can also cache the popular contents that users request. This joint content caching and transmission problem is formulated as an optimization problem whose goal is to maximize the users' reliability, defined as the probability that the content transmission delay of each user satisfies the instantaneous VR delay target. To address this problem, a distributed deep learning algorithm that brings together new neural network ideas from liquid state machine (LSM) and echo state networks (ESNs) is proposed. The proposed algorithm enables each SBS to predict the users' reliability so as to find the optimal contents to cache and content transmission format for each UAV. Analytical results are derived to expose the various network factors that impact content caching and content transmission format selection. Simulation results show that the proposed algorithm yields 25.4% gain of reliability compared to Q-learning. The results also show that the proposed algorithm can achieve 14.7% gain of reliability due to the reduction of traffic load over backhaul compared to the proposed algorithm with random caching.
Planning Multi-Fingered Grasps as Probabilistic Inference in a Learned Deep Network
Venue: arXiv cs.RO 2018
Year: 2018

We propose a novel approach to multi-fingered grasp planning leveraging learned deep neural network models. We train a convolutional neural network to predict grasp success as a function of both visual information of an object and grasp configuration. We can then formulate grasp planning as inferring the grasp configuration which maximizes the probability of grasp success. We efficiently perform this inference using a gradient-ascent optimization inside the neural network using the backpropagation algorithm. Our work is the first to directly plan high quality multifingered grasps in configuration space using a deep neural network without the need of an external planner. We validate our inference method performing both multifinger and two-finger grasps on real robots. Our experimental results show that our planning method outperforms existing planning methods for neural networks; while offering several other benefits including being data-efficient in learning and fast enough to be deployed in real robotic applications.
Community-Empowered Air Quality Monitoring System
Venue: arXiv cs.HC 2018
Year: 2018

Developing information technology to democratize scientific knowledge and support citizen empowerment is a challenging task. In our case, a local community suffered from air pollution caused by industrial activity. The residents lacked the technological fluency to gather and curate diverse scientific data to advocate for regulatory change. We collaborated with the community in developing an air quality monitoring system which integrated heterogeneous data over a large spatial and temporal scale. The system afforded strong scientific evidence by using animated smoke images, air quality data, crowdsourced smell reports, and wind data. In our evaluation, we report patterns of sharing smoke images among stakeholders. Our survey study shows that the scientific knowledge provided by the system encourages agonistic discussions with regulators, empowers the community to support policy making, and rebalances the power relationship between stakeholders.
Mixed H2/H-infinity Data-Driven Control Design for Hard Disk Drives
Venue: arXiv cs.SY 2018
Year: 2018

A frequency based data-driven control design considering mixed H2/H-infinity control objectives is developed for multiple input-single output systems. The main advantage of the data-driven control over the model-based control is its ability to use the frequency response measurements of the controlled plant directly without the need to identify a model for the plant. In the proposed methodology, multiple sets of measurements can be considered in the design process to accommodate variations in the system dynamics. The controller is obtained by translating the mixed H2/H-infinity control objectives into a convex optimization problem. The H-infinity norm is used to shape closed loop transfer functions and guarantee closed loop stability, while the H2 norm is used to constrain and/or minimize the variance of signals in the time domain. The proposed data-driven design methodology is used to design a track following controller for a dual-stage HDD. The sensitivity decoupling structure[16] is considered as the controller structure. The compensators inside this controller structure are designed and compared by decoupling the system into two single input-single-output systems as well as solving for a single input-double output controller.
On top fan-in vs formal degree for depth-$3$ arithmetic circuits
Venue: arXiv cs.CC 2018
Year: 2018

We show that over the field of complex numbers, \emph{every} homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, such that any depth-$3$ arithmetic circuit computing $P$ must have top fan-in at least $Ω(n)$. As an application, we get a new tradeoff between the top fan-in and formal degree in an approximate analog of the celebrated depth reduction result of Gupta, Kamath, Kayal and Saptharishi [GKKS13]. Formally, we show that if a degree $d$ homogeneous polynomial $P$ can be computed by an arithmetic circuit of size $s$, then for every $t \leq d$, $P$ is in the border of a depth-$3$ circuit of top fan-in $s^{O(t)}$ and formal degree $s^{O(d/t)}$. To the best of our knowledge, the upper bound on the top fan-in in the original proof of [GKKS13] is always at least $s^{O(\sqrt{d})}$, regardless of the formal degree.
Individual and Group Stability in Neutral Restrictions of Hedonic Games
Venue: arXiv cs.GT 2018
Year: 2018

We consider a class of coalition formation games called hedonic games, i.e., games in which the utility of a player is completely determined by the coalition that the player belongs to. We first define the class of subset-additive hedonic games and show that they have the same representation power as the class of hedonic games. We then define a restriction of subset-additive hedonic games that we call subset-neutral hedonic games and generalize a result by Bogomolnaia and Jackson (2002) by showing the existence of a Nash stable partition and an individually stable partition in such games. We also consider neutrally anonymous hedonic games and show that they form a subclass of the subset-additive hedonic games. Finally, we show the existence of a core stable partition that is also individually stable in neutrally anonymous hedonic games by exhibiting an algorithm to compute such a partition.
Implementing Push-Pull Efficiently in GraphBLAS
Venue: arXiv cs.DC 2018
Year: 2018

We factor Beamer's push-pull, also known as direction-optimized breadth-first-search (DOBFS) into 3 separable optimizations, and analyze them for generalizability, asymptotic speedup, and contribution to overall speedup. We demonstrate that masking is critical for high performance and can be generalized to all graph algorithms where the sparsity pattern of the output is known a priori. We show that these graph algorithm optimizations, which together constitute DOBFS, can be neatly and separably described using linear algebra and can be expressed in the GraphBLAS linear-algebra-based framework. We provide experimental evidence that with these optimizations, a DOBFS expressed in a linear-algebra-based graph framework attains competitive performance with state-of-the-art graph frameworks on the GPU and on a multi-threaded CPU, achieving 101 GTEPS on a Scale 22 RMAT graph.
A Manga-Driven System Requirements Development PBL Exercise
Venue: arXiv cs.SE 2018
Year: 2018

We conducted a Project-Based Learning (PBL)-type exercise incorporating Japanese cartoon (manga) techniques into Requirements Development (RD) processes. Manga has established techniques, such as those for character setting and story development, that we thought are also valid for RD processes. Using this manga-driven method, students were able to clarify high-level project goals early in the development life-cycle, and succeeded in defining high quality and unique system ideas.
Protocol and Tools for Conducting Agile Software Engineering Research in an Industrial-Academic Setting: A Preliminary Study
Venue: arXiv cs.SE 2018
Year: 2018

Conducting empirical research in software engineering industry is a process, and as such, it should be generalizable. The aim of this paper is to discuss how academic researchers may address some of the challenges they encounter during conducting empirical research in the software industry by means of a systematic and structured approach. The protocol developed in this paper should serve as a practical guide for researchers and help them with conducting empirical research in this complex environment.
Optimization of a Power Splitting Protocol for Two-Way Multiple Energy Harvesting Relay System
Venue: arXiv cs.NI 2018
Year: 2018

Energy harvesting (EH) combined with cooperative communications constitutes a promising solution for future wireless technologies. They enable additional efficiency and increased lifetime to wireless networks. This paper investigates a multiple-relay selection scheme for an EH-based two-way relaying (TWR) system. All relays are considered as EH nodes that harvest energy from renewable energy and radio frequency (RF) sources. Some of them are selected to forward data to the destinations. The power splitting (PS) protocol, by which the EH node splits the input RF signal into two components for EH and information transmission, is adopted at the relay nodes. The objective is to jointly optimize i) the set of selected relays, ii) their PS ratios, and iii) their transmit power levels in order to maximize data rate-based utilities over multiple coherent time slots. A joint-optimization solution based on geometric programming (GP) and binary particle swarm optimization is proposed to solve non-convex problems for two utility functions reflecting the level of fairness in the TWR transmission. Numerical results illustrate the system's behavior versus various parameters and show that the performance of the proposed scheme is very close to that of the optimal branch-and-bound method and that GP outperforms the dual problem-based method.
Uniqueness for the 3-State Antiferromagnetic Potts Model on the Tree
Venue: arXiv cs.DM 2018
Year: 2018

The antiferromagnetic $q$-state Potts model is perhaps the most canonical model for which the uniqueness threshold on the tree is not yet understood, largely because of the absence of monotonicities. Jonasson established the uniqueness threshold in the zero-temperature case, which corresponds to the $q$-colourings model. In the permissive case (where the temperature is positive), the Potts model has an extra parameter $β\in(0,1)$, which makes the task of analysing the uniqueness threshold even harder and much less is known. In this paper, we focus on the case $q=3$ and give a detailed analysis of the Potts model on the tree by refining Jonasson's approach. In particular, we establish the uniqueness threshold on the $d$-ary tree for all values of $d\geq 2$. When $d\geq3$, we show that the 3-state antiferromagnetic Potts model has uniqueness for all $β\geq 1-3/(d+1)$. The case $d=2$ is critical since it relates to the 3-colourings model on the binary tree ($β=0$), which has non-uniqueness. Nevertheless, we show that the Potts model has uniqueness for all $β\in (0,1)$ on the binary tree. Both of these results are tight since it is known that uniqueness does not hold in the complementary regime. Our proof technique gives for general $q>3$ an analytical condition for proving uniqueness based on the two-step recursion on the tree, which we conjecture to be sufficient to establish the uniqueness threshold for all non-critical cases ($q\neq d+1$).
Software Engineering for Millennials, by Millennials
Venue: arXiv cs.CY 2018
Year: 2018

Software engineers need to manage both technical and professional skills in order to be successful. Our university offers a 5.5 year program that mixes computer science, software and computer engineering, where the first two years are mostly math and physics courses. As such, our students' first real teamwork experience is during the introductory SE course, where they modify open source projects in groups of 6-8. However, students have problems working in such large teams, and feel that the course material and project are "disconnected". We decided to redesign this course in 2017, trying to achieve a balance between theory and practice, and technical and professional skills, with a maximum course workload of 150 hrs per semester. We share our experience in this paper, discussing the strategies we used to improve teamwork and help students learn new technologies in a more autonomous manner. We also discuss what we learned from the two times we taught the new course.
The Monge-Kantorovich Optimal Transport Distance for Image Comparison
Venue: arXiv cs.CV 2018
Year: 2018

This paper focuses on the Monge-Kantorovich formulation of the optimal transport problem and the associated $L^2$ Wasserstein distance. We use the $L^2$ Wasserstein distance in the Nearest Neighbour (NN) machine learning architecture to demonstrate the potential power of the optimal transport distance for image comparison. We compare the Wasserstein distance to other established distances - including the partial differential equation (PDE) formulation of the optimal transport problem - and demonstrate that on the well known MNIST optical character recognition dataset, it achieves excellent results.