OpenRaiser/Intern-Atlas huggingface dataset:
An algorithmic comparison of the Hyper-Reduction and the Discrete Empirical Interpolation Method for a nonlinear thermal problem
Venue: arXiv cs.CE 2017
Year: 2017

A novel algorithmic discussion of the methodological and numerical differences of competing parametric model reduction techniques for nonlinear problems are presented. First, the Galerkin reduced basis (RB) formulation is presented which fails at providing significant gains with respect to the computational efficiency for nonlinear problems. Renown methods for the reduction of the computing time of nonlinear reduced order models are the Hyper-Reduction and the (Discrete) Empirical Interpolation Method (EIM, DEIM). An algorithmic description and a methodological comparison of both methods are provided. The accuracy of the predictions of the hyper-reduced model and the (D)EIM in comparison to the Galerkin RB is investigated. All three approaches are applied to a simple uncertainty quantification of a planar nonlinear thermal conduction problem. The results are compared to computationally intense finite element simulations.
A Framework for Application-aware Networking by Delegating Traffic Management of SDNs
Venue: arXiv cs.NI 2017
Year: 2017

Presence of a logically centralized controller in software-defined networks enables smart and fine-grained management of network traffic. Generally, traffic management includes measurement, analysis and control of traffic in order to improve resource utilization. This is done by inspecting corresponding performance requirements using metrics such as packet delay, jitter, loss rate and bandwidth utilization from global network view. There has been many works regarding traffic management of software-defined networks and how it could help to efficiently allocate resources. However, the vast majority of these solutions are bounded to indirect information retrieved within the border of ingress and egress switches. This means that the three stage loop of measurement, analysis and control is performed on switches in between this border while the traffic flowing in network originates from applications on end hosts. In this work, we present a framework for incorporating network applications into the task of traffic management using the concept of software-defined networking. We demonstrate how this could help applications to receive desired level of quality of service by implementing a prototype of an API for flow bandwidth reservation using OpenFlow and OVSDB protocols.
Achieving Perfect Location Privacy in Wireless Devices Using Anonymization
Venue: arXiv cs.IT 2017
Year: 2017

The popularity of mobile devices and location-based services (LBS) has created great concern regarding the location privacy of their users. Anonymization is a common technique that is often used to protect the location privacy of LBS users. Here, we present an information-theoretic approach to define the notion of perfect location privacy. We show how LBS's should use the anonymization method to ensure that their users can achieve perfect location privacy. First, we assume that a user's current location is independent from her past locations. Using this i.i.d model, we show that if the pseudonym of the user is changed before $O(n^{\frac{2}{r-1}})$ observations are made by the adversary for that user, then the user has perfect location privacy. Here, n is the number of the users in the network and r is the number of all possible locations that users can go to. Next, we model users' movements using Markov chains to better model real-world movement patterns. We show that perfect location privacy is achievable for a user if the user's pseudonym is changed before $O(n^{\frac{2}{|E|-r}})$ observations are collected by the adversary for the user, where |E| is the number of edges in the user's Markov chain model.
Federated Learning: Strategies for Improving Communication Efficiency
Venue: arXiv cs.LG 2017
Year: 2017

Federated Learning is a machine learning setting where the goal is to train a high-quality centralized model while training data remains distributed over a large number of clients each with unreliable and relatively slow network connections. We consider learning algorithms for this setting where on each round, each client independently computes an update to the current model based on its local data, and communicates this update to a central server, where the client-side updates are aggregated to compute a new global model. The typical clients in this setting are mobile phones, and communication efficiency is of the utmost importance. In this paper, we propose two ways to reduce the uplink communication costs: structured updates, where we directly learn an update from a restricted space parametrized using a smaller number of variables, e.g. either low-rank or a random mask; and sketched updates, where we learn a full model update and then compress it using a combination of quantization, random rotations, and subsampling before sending it to the server. Experiments on both convolutional and recurrent networks show that the proposed methods can reduce the communication cost by two orders of magnitude.
Active Network Alignment: A Matching-Based Approach
Venue: arXiv cs.SI 2017
Year: 2017

Network alignment is the problem of matching the nodes of two graphs, maximizing the similarity of the matched nodes and the edges between them. This problem is encountered in a wide array of applications-from biological networks to social networks to ontologies-where multiple networked data sources need to be integrated. Due to the difficulty of the task, an accurate alignment can rarely be found without human assistance. Thus, it is of great practical importance to develop network alignment algorithms that can optimally leverage experts who are able to provide the correct alignment for a small number of nodes. Yet, only a handful of existing works address this active network alignment setting. The majority of the existing active methods focus on absolute queries ("are nodes $a$ and $b$ the same or not?"), whereas we argue that it is generally easier for a human expert to answer relative queries ("which node in the set $\{b_1, \ldots, b_n\}$ is the most similar to node $a$?"). This paper introduces two novel relative-query strategies, TopMatchings and GibbsMatchings, which can be applied on top of any network alignment method that constructs and solves a bipartite matching problem. Our methods identify the most informative nodes to query by sampling the matchings of the bipartite graph associated to the network-alignment instance. We compare the proposed approaches to several commonly-used query strategies and perform experiments on both synthetic and real-world datasets. Our sampling-based strategies yield the highest overall performance, outperforming all the baseline methods by more than 15 percentage points in some cases. In terms of accuracy, TopMatchings and GibbsMatchings perform comparably. However, GibbsMatchings is significantly more scalable, but it also requires hyperparameter tuning for a temperature parameter.
StuffNet: Using 'Stuff' to Improve Object Detection
Venue: arXiv cs.CV 2017
Year: 2017

We propose a Convolutional Neural Network (CNN) based algorithm - StuffNet - for object detection. In addition to the standard convolutional features trained for region proposal and object detection [31], StuffNet uses convolutional features trained for segmentation of objects and 'stuff' (amorphous categories such as ground and water). Through experiments on Pascal VOC 2010, we show the importance of features learnt from stuff segmentation for improving object detection performance. StuffNet improves performance from 18.8% mAP to 23.9% mAP for small objects. We also devise a method to train StuffNet on datasets that do not have stuff segmentation labels. Through experiments on Pascal VOC 2007 and 2012, we demonstrate the effectiveness of this method and show that StuffNet also significantly improves object detection performance on such datasets.
The Spread of Cooperative Strategies on Grids with Random Asynchronous Updating
Venue: arXiv cs.DM 2017
Year: 2017

The Prisoner's Dilemma Process on a graph $G$ is an iterative process where each vertex, with a fixed strategy (cooperate or defect), plays the game with each of its neighbours. At the end of a round each vertex may change its strategy to that of its neighbour with the highest pay-off. Here we study the spread of cooperative and selfish behaviours on a toroidal grid, where each vertex is initially a cooperator with probability $p$. When vertices are permitted to change their strategies via a randomized asynchronous update scheme, we find that for some values of $p$ the limiting density of cooperators may be modelled as a polynomial in $p$. Theoretical bounds for this density are confirmed via simulation.
Cryptography with right-angled Artin groups
Venue: arXiv cs.CR 2017
Year: 2017

In this paper we propose right-angled Artin groups as a platform for secret sharing schemes based on the efficiency (linear time) of the word problem. Inspired by previous work of Grigoriev-Shpilrain in the context of graphs, we define two new problems: Subgroup Isomorphism Problem and Group Homomorphism Problem. Based on them, we also propose two new authentication schemes. For right-angled Artin groups, the Group Homomorphism and Graph Homomorphism problems are equivalent, and the later is known to be NP-complete. In the case of the Subgroup Isomorphism problem, we bring some results due to Bridson who shows there are right-angled Artin groups in which this problem is unsolvable.
Modular Deep Q Networks for Sim-to-real Transfer of Visuo-motor Policies
Venue: arXiv cs.RO 2017
Year: 2017

While deep learning has had significant successes in computer vision thanks to the abundance of visual data, collecting sufficiently large real-world datasets for robot learning can be costly. To increase the practicality of these techniques on real robots, we propose a modular deep reinforcement learning method capable of transferring models trained in simulation to a real-world robotic task. We introduce a bottleneck between perception and control, enabling the networks to be trained independently, but then merged and fine-tuned in an end-to-end manner to further improve hand-eye coordination. On a canonical, planar visually-guided robot reaching task a fine-tuned accuracy of 1.6 pixels is achieved, a significant improvement over naive transfer (17.5 pixels), showing the potential for more complicated and broader applications. Our method provides a technique for more efficient learning and transfer of visuo-motor policies for real robotic systems without relying entirely on large real-world robot datasets.
An Efficient Minibatch Acceptance Test for Metropolis-Hastings
Venue: arXiv cs.LG 2017
Year: 2017

We present a novel Metropolis-Hastings method for large datasets that uses small expected-size minibatches of data. Previous work on reducing the cost of Metropolis-Hastings tests yield variable data consumed per sample, with only constant factor reductions versus using the full dataset for each sample. Here we present a method that can be tuned to provide arbitrarily small batch sizes, by adjusting either proposal step size or temperature. Our test uses the noise-tolerant Barker acceptance test with a novel additive correction variable. The resulting test has similar cost to a normal SGD update. Our experiments demonstrate several order-of-magnitude speedups over previous work.
Exploitation of Semantic Keywords for Malicious Event Classification
Venue: arXiv cs.CV 2017
Year: 2017

Learning an event classifier is challenging when the scenes are semantically different but visually similar. However, as humans, we typically handle such tasks painlessly by adding our background semantic knowledge. Motivated by this observation, we aim to provide an empirical study about how additional information such as semantic keywords can boost up the discrimination of such events. To demonstrate the validity of this study, we first construct a novel Malicious Crowd Dataset containing crowd images with two events, benign and malicious, which look visually similar. Note that the primary focus of this paper is not to provide the state-of-the-art performance on this dataset but to show the beneficial aspects of using semantically-driven keyword information. By leveraging crowd-sourcing platforms, such as Amazon Mechanical Turk, we collect semantic keywords associated with images and then subsequently identify a subset of keywords (e.g. police, fire, etc.) unique to specific events. We first show that by using recently introduced attention models, a naive CNN-based event classifier actually learns to primarily focus on local attributes associated with the discriminant semantic keywords identified by the Turks. We further show that incorporating the keyword-driven information into early- and late-fusion approaches can significantly enhance malicious event classification.
The K Shortest Paths Problem with Application to Routing
Venue: arXiv cs.DS 2017
Year: 2017

Due to the computational complexity of finding almost shortest simple paths, we propose that identifying a larger collection of (nonbacktracking) paths is more efficient than finding almost shortest simple paths on positively weighted real-world networks. First, we present an easy to implement $O(m\log m+kL)$ solution for finding all (nonbacktracking) paths with bounded length $D$ between two arbitrary nodes on a positively weighted graph, where $L$ is an upperbound for the number of nodes in any of the $k$ outputted paths. Subsequently, we illustrate that for undirected Chung-Lu random graphs, the ratio between the number of nonbacktracking and simple paths asymptotically approaches $1$ with high probability for a wide range of parameters. We then consider an application to the almost shortest paths algorithm to measure path diversity for internet routing in a snapshot of the Autonomous System graph subject to an edge deletion process.
Safety Verification of Deep Neural Networks
Venue: arXiv cs.AI 2017
Year: 2017

Deep neural networks have achieved impressive experimental results in image classification, but can surprisingly be unstable with respect to adversarial perturbations, that is, minimal changes to the input image that cause the network to misclassify it. With potential applications including perception modules and end-to-end controllers for self-driving cars, this raises concerns about their safety. We develop a novel automated verification framework for feed-forward multi-layer neural networks based on Satisfiability Modulo Theory (SMT). We focus on safety of image classification decisions with respect to image manipulations, such as scratches or changes to camera angle or lighting conditions that would result in the same class being assigned by a human, and define safety for an individual decision in terms of invariance of the classification within a small neighbourhood of the original image. We enable exhaustive search of the region by employing discretisation, and propagate the analysis layer by layer. Our method works directly with the network code and, in contrast to existing methods, can guarantee that adversarial examples, if they exist, are found for the given region and family of manipulations. If found, adversarial examples can be shown to human testers and/or used to fine-tune the network. We implement the techniques using Z3 and evaluate them on state-of-the-art networks, including regularised and deep learning networks. We also compare against existing techniques to search for adversarial examples and estimate network robustness.
DSValidator: An Automated Counterexample Reproducibility Tool for Digital Systems (Tool Demonstration)
Venue: arXiv cs.SY 2017
Year: 2017

An automated counterexample reproducibility tool based on MATLAB is presented, called DSValidator, with the goal of reproducing counterexamples that refute specific properties related to digital systems. We exploit counterexamples generated by the Digital System Verifier (DSVerifier), which is a model checking tool based on satisfiability modulo theories for digital systems. DSValidator reproduces the execution of a digital system, relating its input with the counterexample, in order to establish trust in a verification result. We show that DSValidator can validate a set of intricate counterexamples for digital controllers used in a real quadrotor attitude system within seconds and also expose incorrect verification results in DSVerifier. The resulting toolbox leverages the potential of combining different verification tools for validating digital systems via an exchangeable counterexample format.
Quantized Precoding for Massive MU-MIMO
Venue: arXiv cs.IT 2017
Year: 2017

Massive multiuser (MU) multiple-input multiple-output (MIMO) is foreseen to be one of the key technologies in fifth-generation wireless communication systems. In this paper, we investigate the problem of downlink precoding for a narrowband massive MU-MIMO system with low-resolution digital-to-analog converters (DACs) at the base station (BS). We analyze the performance of linear precoders, such as maximal-ratio transmission and zero-forcing, subject to coarse quantization. Using Bussgang's theorem, we derive a closed-form approximation on the rate achievable under such coarse quantization. Our results reveal that the performance attainable with infinite-resolution DACs can be approached using DACs having only 3 to 4 bits of resolution, depending on the number of BS antennas and the number of user equipments (UEs). For the case of 1-bit DACs, we also propose novel nonlinear precoding algorithms that significantly outperform linear precoders at the cost of an increased computational complexity. Specifically, we show that nonlinear precoding incurs only a 3 dB penalty compared to the infinite-resolution case for an uncoded bit error rate of 10^-3, in a system with 128 BS antennas that uses 1-bit DACs and serves 16 single-antenna UEs. In contrast, the penalty for linear precoders is about 8 dB.
Bias-Aware Sketches
Venue: arXiv cs.DS 2017
Year: 2017

Linear sketching algorithms have been widely used for processing large-scale distributed and streaming datasets. Their popularity is largely due to the fact that linear sketches can be naturally composed in the distributed model and be efficiently updated in the streaming model. The errors of linear sketches are typically expressed in terms of the sum of coordinates of the input vector excluding those largest ones, or, the mass on the tail of the vector. Thus, the precondition for these algorithms to perform well is that the mass on the tail is small, which is, however, not always the case -- in many real-world datasets the coordinates of the input vector have a {\em bias}, which will generate a large mass on the tail. In this paper we propose linear sketches that are {\em bias-aware}. We rigorously prove that they achieve strictly better error guarantees than the corresponding existing sketches, and demonstrate their practicality and superiority via an extensive experimental evaluation on both real and synthetic datasets.
The Effect of Pokémon Go on The Pulse of the City: A Natural Experiment
Venue: arXiv cs.SI 2017
Year: 2017

Pokémon Go, a location-based game that uses augmented reality techniques, received unprecedented media coverage due to claims that it allowed for greater access to public spaces, increasing the number of people out on the streets, and generally improving health, social, and security indices. However, the true impact of Pokémon Go on people's mobility patterns in a city is still largely unknown. In this paper, we perform a natural experiment using data from mobile phone networks to evaluate the effect of Pokémon Go on the pulse of a big city: Santiago, capital of Chile. We found significant effects of the game on the floating population of Santiago compared to movement prior to the game's release in August 2016: in the following week, up to 13.8\% more people spent time outside at certain times of the day, even if they do not seem to go out of their usual way. These effects were found by performing regressions using count models over the states of the cellphone network during each day under study. The models used controlled for land use, daily patterns, and points of interest in the city. Our results indicate that, on business days, there are more people on the street at commuting times, meaning that people did not change their daily routines but slightly adapted them to play the game. Conversely, on Saturday and Sunday night, people indeed went out to play, but favored places close to where they live. Even if the statistical effects of the game do not reflect the massive change in mobility behavior portrayed by the media, at least in terms of expanse, they do show how "the street" may become a new place of leisure. This change should have an impact on long-term infrastructure investment by city officials, and on the drafting of public policies aimed at stimulating pedestrian traffic.
Socratic Learning: Augmenting Generative Models to Incorporate Latent Subsets in Training Data
Venue: arXiv cs.LG 2017
Year: 2017

A challenge in training discriminative models like neural networks is obtaining enough labeled training data. Recent approaches use generative models to combine weak supervision sources, like user-defined heuristics or knowledge bases, to label training data. Prior work has explored learning accuracies for these sources even without ground truth labels, but they assume that a single accuracy parameter is sufficient to model the behavior of these sources over the entire training set. In particular, they fail to model latent subsets in the training data in which the supervision sources perform differently than on average. We present Socratic learning, a paradigm that uses feedback from a corresponding discriminative model to automatically identify these subsets and augments the structure of the generative model accordingly. Experimentally, we show that without any ground truth labels, the augmented generative model reduces error by up to 56.06% for a relation extraction task compared to a state-of-the-art weak supervision technique that utilizes generative models.
Universal adversarial perturbations
Venue: arXiv cs.CV 2017
Year: 2017

Given a state-of-the-art deep neural network classifier, we show the existence of a universal (image-agnostic) and very small perturbation vector that causes natural images to be misclassified with high probability. We propose a systematic algorithm for computing universal perturbations, and show that state-of-the-art deep neural networks are highly vulnerable to such perturbations, albeit being quasi-imperceptible to the human eye. We further empirically analyze these universal perturbations and show, in particular, that they generalize very well across neural networks. The surprising existence of universal perturbations reveals important geometric correlations among the high-dimensional decision boundary of classifiers. It further outlines potential security breaches with the existence of single directions in the input space that adversaries can possibly exploit to break a classifier on most natural images.
Tracing where IoT data are collected and aggregated
Venue: arXiv cs.PL 2017
Year: 2017

The Internet of Things (IoT) offers the infrastructure of the information society. It hosts smart objects that automatically collect and exchange data of various kinds, directly gathered from sensors or generated by aggregations. Suitable coordination primitives and analysis mechanisms are in order to design and reason about IoT systems, and to intercept the implied technological shifts. We address these issues from a foundational point of view. To study them, we define IoT-LySa, a process calculus endowed with a static analysis that tracks the provenance and the manipulation of IoT data, and how they flow in the system. The results of the analysis can be used by a designer to check the behaviour of smart objects, in particular to verify non-functional properties, among which security.