OpenRaiser/Intern-Atlas huggingface dataset:
Automation in Human-Machine Networks: How Increasing Machine Agency Affects Human Agency
Venue: arXiv cs.HC 2017
Year: 2017

Efficient human-machine networks require productive interaction between human and machine actors. In this study, we address how a strengthening of machine agency, for example through increasing levels of automation, affect the human actors of the networks. Findings from case studies within air traffic management, crisis management, and crowd evacuation are presented, exemplifying how automation may strengthen the agency of human actors in the network through responsibility sharing and task allocation, and serve as a needed prerequisite of innovation and change.
Speckle Reduction with Trained Nonlinear Diffusion Filtering
Venue: arXiv cs.CV 2017
Year: 2017

Speckle reduction is a prerequisite for many image processing tasks in synthetic aperture radar (SAR) images, as well as all coherent images. In recent years, predominant state-of-the-art approaches for despeckling are usually based on nonlocal methods which mainly concentrate on achieving utmost image restoration quality, with relatively low computational efficiency. Therefore, in this study we aim to propose an efficient despeckling model with both high computational efficiency and high recovery quality. To this end, we exploit a newly-developed trainable nonlinear reaction diffusion(TNRD) framework which has proven a simple and effective model for various image restoration problems. {In the original TNRD applications, the diffusion network is usually derived based on the direct gradient descent scheme. However, this approach will encounter some problem for the task of multiplicative noise reduction exploited in this study. To solve this problem, we employed a new architecture derived from the proximal gradient descent method.} {Taking into account the speckle noise statistics, the diffusion process for the despeckling task is derived. We then retrain all the model parameters in the presence of speckle noise. Finally, optimized nonlinear diffusion filtering models are obtained, which are specialized for despeckling with various noise levels. Experimental results substantiate that the trained filtering models provide comparable or even better results than state-of-the-art nonlocal approaches. Meanwhile, our proposed model merely contains convolution of linear filters with an image, which offers high level parallelism on GPUs. As a consequence, for images of size $512 \times 512$, our GPU implementation takes less than 0.1 seconds to produce state-of-the-art despeckling performance.}
Online Meta-learning by Parallel Algorithm Competition
Venue: arXiv cs.LG 2017
Year: 2017

The efficiency of reinforcement learning algorithms depends critically on a few meta-parameters that modulates the learning updates and the trade-off between exploration and exploitation. The adaptation of the meta-parameters is an open question in reinforcement learning, which arguably has become more of an issue recently with the success of deep reinforcement learning in high-dimensional state spaces. The long learning times in domains such as Atari 2600 video games makes it not feasible to perform comprehensive searches of appropriate meta-parameter values. We propose the Online Meta-learning by Parallel Algorithm Competition (OMPAC) method. In the OMPAC method, several instances of a reinforcement learning algorithm are run in parallel with small differences in the initial values of the meta-parameters. After a fixed number of episodes, the instances are selected based on their performance in the task at hand. Before continuing the learning, Gaussian noise is added to the meta-parameters with a predefined probability. We validate the OMPAC method by improving the state-of-the-art results in stochastic SZ-Tetris and in standard Tetris with a smaller, 10$\times$10, board, by 31% and 84%, respectively, and by improving the results for deep Sarsa($λ$) agents in three Atari 2600 games by 62% or more. The experiments also show the ability of the OMPAC method to adapt the meta-parameters according to the learning progress in different tasks.
Use Generalized Representations, But Do Not Forget Surface Features
Venue: arXiv cs.CL 2017
Year: 2017

Only a year ago, all state-of-the-art coreference resolvers were using an extensive amount of surface features. Recently, there was a paradigm shift towards using word embeddings and deep neural networks, where the use of surface features is very limited. In this paper, we show that a simple SVM model with surface features outperforms more complex neural models for detecting anaphoric mentions. Our analysis suggests that using generalized representations and surface features have different strength that should be both taken into account for improving coreference resolution.
Tight Bounds for Bandit Combinatorial Optimization
Venue: arXiv cs.LG 2017
Year: 2017

We revisit the study of optimal regret rates in bandit combinatorial optimization---a fundamental framework for sequential decision making under uncertainty that abstracts numerous combinatorial prediction problems. We prove that the attainable regret in this setting grows as $\widetildeΘ(k^{3/2}\sqrt{dT})$ where $d$ is the dimension of the problem and $k$ is a bound over the maximal instantaneous loss, disproving a conjecture of Audibert, Bubeck, and Lugosi (2013) who argued that the optimal rate should be of the form $\widetildeΘ(k\sqrt{dT})$. Our bounds apply to several important instances of the framework, and in particular, imply a tight bound for the well-studied bandit shortest path problem. By that, we also resolve an open problem posed by Cesa-Bianchi and Lugosi (2012).
Practical Homomorphic Encryption Over the Integers
Venue: arXiv cs.CR 2017
Year: 2017

We present novel homomorphic encryption schemes for integer arithmetic, intended for use in secure single-party computation in the cloud. These schemes are capable of securely computing only low degree polynomials homomorphically, but this appears sufficient for most practical applications. In this setting, our schemes lead to practical key and ciphertext sizes. We present a sequence of generalisations of our basic schemes, with increasing levels of security, but decreasing practicality. We have evaluated the first four of these algorithms by computing a low-degree inner product. The timings of these computations are extremely favourable. Finally, we use our ideas to derive a fully homomorphic system, which appears impractical, but can homomorphically evaluate arbitrary Boolean circuits.
DALiuGE: A Graph Execution Framework for Harnessing the Astronomical Data Deluge
Venue: arXiv cs.DC 2017
Year: 2017

The Data Activated Liu Graph Engine - DALiuGE - is an execution framework for processing large astronomical datasets at a scale required by the Square Kilometre Array Phase 1 (SKA1). It includes an interface for expressing complex data reduction pipelines consisting of both data sets and algorithmic components and an implementation run-time to execute such pipelines on distributed resources. By mapping the logical view of a pipeline to its physical realisation, DALiuGE separates the concerns of multiple stakeholders, allowing them to collectively optimise large-scale data processing solutions in a coherent manner. The execution in DALiuGE is data-activated, where each individual data item autonomously triggers the processing on itself. Such decentralisation also makes the execution framework very scalable and flexible, supporting pipeline sizes ranging from less than ten tasks running on a laptop to tens of millions of concurrent tasks on the second fastest supercomputer in the world. DALiuGE has been used in production for reducing interferometry data sets from the Karl E. Jansky Very Large Array and the Mingantu Ultrawide Spectral Radioheliograph; and is being developed as the execution framework prototype for the Science Data Processor (SDP) consortium of the Square Kilometre Array (SKA) telescope. This paper presents a technical overview of DALiuGE and discusses case studies from the CHILES and MUSER projects that use DALiuGE to execute production pipelines. In a companion paper, we provide in-depth analysis of DALiuGE's scalability to very large numbers of tasks on two supercomputing facilities.
Capacity of the Aperture-Constrained AWGN Free-Space Communication Channel
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we derive upper and lower bounds as well as a simple closed-form approximation for the capacity of the continuous-time, bandlimited, additive white Gaussian noise channel in a three-dimensional free-space electromagnetic propagation environment subject to constraints on the total effective antenna aperture area of the link and a total transmitter power constraint. We assume that the communication range is much larger than the radius of the sphere containing the antennas at both ends of the link, and we show that, in general, the capacity can only be achieved by transmitting multiple spatially-multiplexed data streams simultaneously over the channel. Furthermore, the lower bound on capacity can be approached asymptotically by transmitting the data streams between a pair of physically-realizable distributed antenna arrays at either end of the link. A consequence of this result is that, in general, communication at close to the maximum achievable data rate on a deep-space communication link can be achieved in practice if and only if the communication system utilizes spatial multiplexing over a distributed MIMO antenna array. Such an approach to deep-space communication does not appear to be envisioned currently by any of the international space agencies or any commercial space companies. A second consequence is that the capacity of a long-range free-space communication link, if properly utilized, grows asymptotically as a function of the square root of the received SNR rather than only logarithmically in the received SNR.
Truthful Mechanisms for Delivery with Mobile Agents
Venue: arXiv cs.GT 2017
Year: 2017

We study the game-theoretic task of selecting mobile agents to deliver multiple items on a network. An instance is given by $m$ messages (physical objects) which have to be transported between specified source-target pairs in a weighted undirected graph, and $k$ mobile heterogeneous agents, each being able to transport one message at a time. Following a recent model by [Bärtschi et al. 2016], each agent $i$ consumes energy proportional to the distance it travels in the graph, where the different rates of energy consumption are given by weight factors $w_i$. We are interested in optimizing or approximating the total energy consumption over all selected agents. Unlike previous research, we assume the weights to be private values known only to the respective agents. We present three different mechanisms which select, route and pay the agents in a truthful way that guarantees voluntary participation of the agents, while approximating the optimum energy consumption by a constant factor. To this end we analyze a previous structural result and an approximation algorithm given by [Bärtschi et al. 2017]. Finally, we show that for some instances in the case of a single package, the sum of the payments can be bounded in terms of the optimum.
Constructing Adjacency Arrays from Incidence Arrays
Venue: arXiv cs.DS 2017
Year: 2017

Graph construction, a fundamental operation in a data processing pipeline, is typically done by multiplying the incidence array representations of a graph, $\mathbf{E}_\mathrm{in}$ and $\mathbf{E}_\mathrm{out}$, to produce an adjacency array of the graph, $\mathbf{A}$, that can be processed with a variety of algorithms. This paper provides the mathematical criteria to determine if the product $\mathbf{A} = \mathbf{E}^{\sf T}_\mathrm{out}\mathbf{E}_\mathrm{in}$ will have the required structure of the adjacency array of the graph. The values in the resulting adjacency array are determined by the corresponding addition $\oplus$ and multiplication $\otimes$ operations used to perform the array multiplication. Illustrations of the various results possible from different $\oplus$ and $\otimes$ operations are provided using a small collection of popular music metadata.
Efficient coordinate-wise leading eigenvector computation
Venue: arXiv cs.NA 2017
Year: 2017

We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product. We establish global convergence with overall runtime guarantees that are at least as good as Lanczos's method and dominate it for slowly decaying spectrum. Our methods are based on combining a shift-and-invert approach with coordinate-wise algorithms for linear regression.
A Branching Time Model of CSP
Venue: arXiv cs.LO 2017
Year: 2017

I present a branching time model of CSP that is finer than all other models of CSP proposed thus far. It is obtained by taking a semantic equivalence from the linear time - branching time spectrum, namely divergence-preserving coupled similarity, and showing that it is a congruence for the operators of CSP. This equivalence belongs to the bisimulation family of semantic equivalences, in the sense that on transition systems without internal actions it coincides with strong bisimilarity. Nevertheless, enough of the equational laws of CSP remain to obtain a complete axiomatisation for closed, recursion-free terms.
Contractibility for Open Global Constraints
Venue: arXiv cs.LO 2017
Year: 2017

Open forms of global constraints allow the addition of new variables to an argument during the execution of a constraint program. Such forms are needed for difficult constraint programming problems where problem construction and problem solving are interleaved, and fit naturally within constraint logic programming. However, in general, filtering that is sound for a global constraint can be unsound when the constraint is open. This paper provides a simple characterization, called contractibility, of the constraints where filtering remains sound when the constraint is open. With this characterization we can easily determine whether a constraint has this property or not. In the latter case, we can use it to derive a contractible approximation to the constraint. We demonstrate this work on both hard and soft constraints. In the process, we formulate two general classes of soft constraints.
Efficient Learning of Mixed Membership Models
Venue: arXiv cs.LG 2017
Year: 2017

We present an efficient algorithm for learning mixed membership models when the number of variables $p$ is much larger than the number of hidden components $k$. This algorithm reduces the computational complexity of state-of-the-art tensor methods, which require decomposing an $O\left(p^3\right)$ tensor, to factorizing $O\left(p/k\right)$ sub-tensors each of size $O\left(k^3\right)$. In addition, we address the issue of negative entries in the empirical method of moments based estimators. We provide sufficient conditions under which our approach has provable guarantees. Our approach obtains competitive empirical results on both simulated and real data.
Image Stitching by Line-guided Local Warping with Global Similarity Constraint
Venue: arXiv cs.CV 2017
Year: 2017

Low-textured image stitching remains a challenging problem. It is difficult to achieve good alignment and it is easy to break image structures due to insufficient and unreliable point correspondences. Moreover, because of the viewpoint variations between multiple images, the stitched images suffer from projective distortions. To solve these problems, this paper presents a line-guided local warping method with a global similarity constraint for image stitching. Line features which serve well for geometric descriptions and scene constraints, are employed to guide image stitching accurately. On one hand, the line features are integrated into a local warping model through a designed weight function. On the other hand, line features are adopted to impose strong geometric constraints, including line correspondence and line colinearity, to improve the stitching performance through mesh optimization. To mitigate projective distortions, we adopt a global similarity constraint, which is integrated with the projective warps via a designed weight strategy. This constraint causes the final warp to slowly change from a projective to a similarity transformation across the image. Finally, the images undergo a two-stage alignment scheme that provides accurate alignment and reduces projective distortion. We evaluate our method on a series of images and compare it with several other methods. The experimental results demonstrate that the proposed method provides a convincing stitching performance and that it outperforms other state-of-the-art methods.
SDN as Active Measurement Infrastructure
Venue: arXiv cs.NI 2017
Year: 2017

Active measurements are integral to the operation and management of networks, and invaluable to supporting empirical network research. Unfortunately, it is often cost-prohibitive and logistically difficult to widely deploy measurement nodes, especially in the core. In this work, we consider the feasibility of tightly integrating measurement within the infrastructure by using Software Defined Networks (SDNs). We introduce "SDN as Active Measurement Infrastructure" (SAAMI) to enable measurements to originate from any location where SDN is deployed, removing the need for dedicated measurement nodes and increasing vantage point diversity. We implement ping and traceroute using SAAMI, as well as a proof-of-concept custom measurement protocol to demonstrate the power and ease of SAAMI's open framework. Via a large-scale measurement campaign using SDN switches as vantage points, we show that SAAMI is accurate, scalable, and extensible.
An Efficient Multiway Mergesort for GPU Architectures
Venue: arXiv cs.DS 2017
Year: 2017

Sorting is a primitive operation that is a building block for countless algorithms. As such, it is important to design sorting algorithms that approach peak performance on a range of hardware architectures. Graphics Processing Units (GPUs) are particularly attractive architectures as they provides massive parallelism and computing power. However, the intricacies of their compute and memory hierarchies make designing GPU-efficient algorithms challenging. In this work we present GPU Multiway Mergesort (MMS), a new GPU-efficient multiway mergesort algorithm. MMS employs a new partitioning technique that exposes the parallelism needed by modern GPU architectures. To the best of our knowledge, MMS is the first sorting algorithm for the GPU that is asymptotically optimal in terms of global memory accesses and that is completely free of shared memory bank conflicts. We realize an initial implementation of MMS, evaluate its performance on three modern GPU architectures, and compare it to competitive implementations available in state-of-the-art GPU libraries. Despite these implementations being highly optimized, MMS compares favorably, achieving performance improvements for most random inputs. Furthermore, unlike MMS, state-of-the-art algorithms are susceptible to bank conflicts. We find that for certain inputs that cause these algorithms to incur large numbers of bank conflicts, MMS can achieve up to a 37.6% speedup over its fastest competitor. Overall, even though its current implementation is not fully optimized, due to its efficient use of the memory hierarchy, MMS outperforms the fastest comparison-based sorting implementations available to date.
Maximum-Likelihood Augmented Discrete Generative Adversarial Networks
Venue: arXiv cs.AI 2017
Year: 2017

Despite the successes in capturing continuous distributions, the application of generative adversarial networks (GANs) to discrete settings, like natural language tasks, is rather restricted. The fundamental reason is the difficulty of back-propagation through discrete random variables combined with the inherent instability of the GAN training objective. To address these problems, we propose Maximum-Likelihood Augmented Discrete Generative Adversarial Networks. Instead of directly optimizing the GAN objective, we derive a novel and low-variance objective using the discriminator's output that follows corresponds to the log-likelihood. Compared with the original, the new objective is proved to be consistent in theory and beneficial in practice. The experimental results on various discrete datasets demonstrate the effectiveness of the proposed approach.
Achievement and Friends: Key Factors of Player Retention Vary Across Player Levels in Online Multiplayer Games
Venue: arXiv cs.SI 2017
Year: 2017

Retaining players over an extended period of time is a long-standing challenge in game industry. Significant effort has been paid to understanding what motivates players enjoy games. While individuals may have varying reasons to play or abandon a game at different stages within the game, previous studies have looked at the retention problem from a snapshot view. This study, by analyzing in-game logs of 51,104 distinct individuals in an online multiplayer game, uniquely offers a multifaceted view of the retention problem over the players' virtual life phases. We find that key indicators of longevity change with the game level. Achievement features are important for players at the initial to the advanced phases, yet social features become the most predictive of longevity once players reach the highest level offered by the game. These findings have theoretical and practical implications for designing online games that are adaptive to meeting the players' needs.
Preventing Hospital Acquired Infections Through a Workflow-Based Cyber-Physical System
Venue: arXiv cs.OH 2017
Year: 2017

Hospital acquired infections (HAI) are infections acquired within the hospital from healthcare workers, patients or from the environment, but which have no connection to the initial reason for the patient's hospital admission. HAI are a serious world-wide problem, leading to an increase in mortality rates, duration of hospitalisation as well as significant economic burden on hospitals. Although clear preventive guidelines exist, studies show that compliance to them is frequently poor. This paper details the software perspective for an innovative, business process software based cyber-physical system that will be implemented as part of a European Union-funded research project. The system is composed of a network of sensors mounted in different sites around the hospital, a series of wearables used by the healthcare workers and a server side workflow engine. For better understanding, we describe the system through the lens of a single, simple clinical workflow that is responsible for a significant portion of all hospital infections. The goal is that when completed, the system will be configurable in the sense of facilitating the creation and automated monitoring of those clinical workflows that when combined, account for over 90\% of hospital infections.
Criticality & Deep Learning I: Generally Weighted Nets
Venue: arXiv cs.AI 2017
Year: 2017

Motivated by the idea that criticality and universality of phase transitions might play a crucial role in achieving and sustaining learning and intelligent behaviour in biological and artificial networks, we analyse a theoretical and a pragmatic experimental set up for critical phenomena in deep learning. On the theoretical side, we use results from statistical physics to carry out critical point calculations in feed-forward/fully connected networks, while on the experimental side we set out to find traces of criticality in deep neural networks. This is our first step in a series of upcoming investigations to map out the relationship between criticality and learning in deep networks.