OpenRaiser/Intern-Atlas huggingface dataset:
Backpropagation for long sequences: beyond memory constraints with constant overheads
Venue: arXiv cs.DC 2018
Year: 2018

Naive backpropagation through time has a memory footprint that grows linearly in the sequence length, due to the need to store each state of the forward propagation. This is a problem for large networks. Strategies have been developed to trade memory for added computations, which results in a sublinear growth of memory footprint or computation overhead. In this work, we present a library that uses asynchronous storing and prefetching to move data to and from slow and cheap stor- age. The library only stores and prefetches states as frequently as possible without delaying the computation, and uses the optimal Revolve backpropagation strategy for the computations in between. The memory footprint of the backpropagation can thus be reduced to any size (e.g. to fit into DRAM), while the computational overhead is constant in the sequence length, and only depends on the ratio between compute and transfer times on a given hardware. We show in experiments that by exploiting asyncronous data transfer, our strategy is always at least as fast, and usually faster than the previously studied "optimal" strategies.
Shallow decision-making analysis in General Video Game Playing
Venue: arXiv cs.AI 2018
Year: 2018

The General Video Game AI competitions have been the testing ground for several techniques for game playing, such as evolutionary computation techniques, tree search algorithms, hyper heuristic based or knowledge based algorithms. So far the metrics used to evaluate the performance of agents have been win ratio, game score and length of games. In this paper we provide a wider set of metrics and a comparison method for evaluating and comparing agents. The metrics and the comparison method give shallow introspection into the agent's decision making process and they can be applied to any agent regardless of its algorithmic nature. In this work, the metrics and the comparison method are used to measure the impact of the terms that compose a tree policy of an MCTS based agent, comparing with several baseline agents. The results clearly show how promising such general approach is and how it can be useful to understand the behaviour of an AI agent, in particular, how the comparison with baseline agents can help understanding the shape of the agent decision landscape. The presented metrics and comparison method represent a step toward to more descriptive ways of logging and analysing agent's behaviours.
Adaptive Computation of the Discrete Fréchet Distance
Venue: arXiv cs.CG 2018
Year: 2018

The discrete Fr{é}chet distance is a measure of similarity between point sequences which permits to abstract differences of resolution between the two curves, approximating the original Fr{é}chet distance between curves. Such distance between sequences of respective length $n$ and $m$ can be computed in time within $O(nm)$ and space within $O(n+m)$ using classical dynamic programing techniques, a complexity likely to be optimal in the worst case over sequences of similar lenght unless the Strong Exponential Hypothesis is proved incorrect. We propose a parameterized analysis of the computational complexity of the discrete Fr{é}chet distance in fonction of the area of the dynamic program matrix relevant to the computation, measured by its \emph{certificate width} $ω$. We prove that the discrete Fr{é}chet distance can be computed in time within $((n+m)ω)$ and space within $O(n+m+ω)$.
Alchemist: An Apache Spark <=> MPI Interface
Venue: arXiv cs.DC 2018
Year: 2018

The Apache Spark framework for distributed computation is popular in the data analytics community due to its ease of use, but its MapReduce-style programming model can incur significant overheads when performing computations that do not map directly onto this model. One way to mitigate these costs is to off-load computations onto MPI codes. In recent work, we introduced Alchemist, a system for the analysis of large-scale data sets. Alchemist calls MPI-based libraries from within Spark applications, and it has minimal coding, communication, and memory overheads. In particular, Alchemist allows users to retain the productivity benefits of working within the Spark software ecosystem without sacrificing performance efficiency in linear algebra, machine learning, and other related computations. In this paper, we discuss the motivation behind the development of Alchemist, and we provide a detailed overview its design and usage. We also demonstrate the efficiency of our approach on medium-to-large data sets, using some standard linear algebra operations, namely matrix multiplication and the truncated singular value decomposition of a dense matrix, and we compare the performance of Spark with that of Spark+Alchemist. These computations are run on the NERSC supercomputer Cori Phase 1, a Cray XC40.
Past Visions of Artificial Futures: One Hundred and Fifty Years under the Spectre of Evolving Machines
Venue: arXiv cs.AI 2018
Year: 2018

The influence of Artificial Intelligence (AI) and Artificial Life (ALife) technologies upon society, and their potential to fundamentally shape the future evolution of humankind, are topics very much at the forefront of current scientific, governmental and public debate. While these might seem like very modern concerns, they have a long history that is often disregarded in contemporary discourse. Insofar as current debates do acknowledge the history of these ideas, they rarely look back further than the origin of the modern digital computer age in the 1940s-50s. In this paper we explore the earlier history of these concepts. We focus in particular on the idea of self-reproducing and evolving machines, and potential implications for our own species. We show that discussion of these topics arose in the 1860s, within a decade of the publication of Darwin's The Origin of Species, and attracted increasing interest from scientists, novelists and the general public in the early 1900s. After introducing the relevant work from this period, we categorise the various visions presented by these authors of the future implications of evolving machines for humanity. We suggest that current debates on the co-evolution of society and technology can be enriched by a proper appreciation of the long history of the ideas involved.
C-BPMN: A Context Aware BPMN for Modeling Complex Business Process
Venue: arXiv cs.SE 2018
Year: 2018

A complex business process demands adaptability as it has been highly influenced by the contextual information. The contextual information declares the underlying semantics on which the process logic depends. Thus one of the challenges of a business process modeling is to include the context sensitivity within the modeling itself. BPMN is the widely accepted tool in this field. All the process modeling languages like EPC, UML, BPMN are not able to express the context awareness as required. In this paper an attempt has been made to offer a means for modeling a complex business process with necessary contextual information. We have proposed a context model in terms of a graph, extended the existing BPMN by adding new construct and integrated the said components to achieve our goal. The methodology as stated certainly offers necessary understandability, maintainability and the adaptability as a whole. Moreover the model is validated using Colored Petri Net and is expected to behave properly in a real life environment.
gprHOG and the popularity of Histogram of Oriented Gradients (HOG) for Buried Threat Detection in Ground-Penetrating Radar
Venue: arXiv cs.CV 2018
Year: 2018

Substantial research has been devoted to the development of algorithms that automate buried threat detection (BTD) with ground penetrating radar (GPR) data, resulting in a large number of proposed algorithms. One popular algorithm GPR-based BTD, originally applied by Torrione et al., 2012, is the Histogram of Oriented Gradients (HOG) feature. In a recent large-scale comparison among five veteran institutions, a modified version of HOG referred to here as "gprHOG", performed poorly compared to other modern algorithms. In this paper, we provide experimental evidence demonstrating that the modifications to HOG that comprise gprHOG result in a substantially better-performing algorithm. The results here, in conjunction with the large-scale algorithm comparison, suggest that HOG is not competitive with modern GPR-based BTD algorithms. Given HOG's popularity, these results raise some questions about many existing studies, and suggest gprHOG (and especially HOG) should be employed with caution in future studies.
Adversarial Domain Adaptation for Classification of Prostate Histopathology Whole-Slide Images
Venue: arXiv cs.CV 2018
Year: 2018

Automatic and accurate Gleason grading of histopathology tissue slides is crucial for prostate cancer diagnosis, treatment, and prognosis. Usually, histopathology tissue slides from different institutions show heterogeneous appearances because of different tissue preparation and staining procedures, thus the predictable model learned from one domain may not be applicable to a new domain directly. Here we propose to adopt unsupervised domain adaptation to transfer the discriminative knowledge obtained from the source domain to the target domain without requiring labeling of images at the target domain. The adaptation is achieved through adversarial training to find an invariant feature space along with the proposed Siamese architecture on the target domain to add a regularization that is appropriate for the whole-slide images. We validate the method on two prostate cancer datasets and obtain significant classification improvement of Gleason scores as compared with the baseline models.
Learning to track on-the-fly using a particle filter with annealed- weighted QPSO modeled after a singular Dirac delta potential
Venue: arXiv cs.NE 2018
Year: 2018

This paper proposes an evolutionary Particle Filter with a memory guided proposal step size update and an improved, fully-connected Quantum-behaved Particle Swarm Optimization (QPSO) resampling scheme for visual tracking applications. The proposal update step uses importance weights proportional to velocities encountered in recent memory to limit the swarm movement within probable regions of interest. The QPSO resampling scheme uses a fitness weighted mean best update to bias the swarm towards the fittest section of particles while also employing a simulated annealing operator to avoid subpar fine tune during latter course of iterations. By moving particles closer to high likelihood landscapes of the posterior distribution using such constructs, the sample impoverishment problem that plagues the Particle Filter is mitigated to a great extent. Experimental results using benchmark sequences imply that the proposed method outperforms competitive candidate trackers such as the Particle Filter and the traditional Particle Swarm Optimization based Particle Filter on a suite of tracker performance indices.
Mining large-scale human mobility data for long-term crime prediction
Venue: arXiv cs.CY 2018
Year: 2018

Traditional crime prediction models based on census data are limited, as they fail to capture the complexity and dynamics of human activity. With the rise of ubiquitous computing, there is the opportunity to improve such models with data that make for better proxies of human presence in cities. In this paper, we leverage large human mobility data to craft an extensive set of features for crime prediction, as informed by theories in criminology and urban studies. We employ averaging and boosting ensemble techniques from machine learning, to investigate their power in predicting yearly counts for different types of crimes occurring in New York City at census tract level. Our study shows that spatial and spatio-temporal features derived from Foursquare venues and checkins, subway rides, and taxi rides, improve the baseline models relying on census and POI data. The proposed models achieve absolute R^2 metrics of up to 65% (on a geographical out-of-sample test set) and up to 89% (on a temporal out-of-sample test set). This proves that, next to the residential population of an area, the ambient population there is strongly predictive of the area's crime levels. We deep-dive into the main crime categories, and find that the predictive gain of the human dynamics features varies across crime types: such features bring the biggest boost in case of grand larcenies, whereas assaults are already well predicted by the census features. Furthermore, we identify and discuss top predictive features for the main crime categories. These results offer valuable insights for those responsible for urban policy or law enforcement.
On the Soundness of Coroutines with Snapshots
Venue: arXiv cs.PL 2018
Year: 2018

Coroutines are a general control flow construct that can eliminate control flow fragmentation inherent in event-driven programs, and are still missing in many popular languages. Coroutines with snapshots are a first-class, type-safe, stackful coroutine model, which unifies many variants of suspendable computing, and is sufficiently general to express iterators, single-assignment variables, async-await, actors, event streams, backtracking, symmetric coroutines and continuations. In this paper, we develop a formal model called $λ_{\rightsquigarrow}$ (lambda-squiggly) that captures the essence of type-safe, stackful, delimited coroutines with snapshots. We prove the standard progress and preservation safety properties. Finally, we show a formal transformation from the $λ_{\rightsquigarrow}$ calculus to the simply-typed lambda calculus with references.
BindsNET: A machine learning-oriented spiking neural networks library in Python
Venue: arXiv cs.NE 2018
Year: 2018

The development of spiking neural network simulation software is a critical component enabling the modeling of neural systems and the development of biologically inspired algorithms. Existing software frameworks support a wide range of neural functionality, software abstraction levels, and hardware devices, yet are typically not suitable for rapid prototyping or application to problems in the domain of machine learning. In this paper, we describe a new Python package for the simulation of spiking neural networks, specifically geared towards machine learning and reinforcement learning. Our software, called BindsNET, enables rapid building and simulation of spiking networks and features user-friendly, concise syntax. BindsNET is built on top of the PyTorch deep neural networks library, enabling fast CPU and GPU computation for large spiking networks. The BindsNET framework can be adjusted to meet the needs of other existing computing and hardware environments, e.g., TensorFlow. We also provide an interface into the OpenAI gym library, allowing for training and evaluation of spiking networks on reinforcement learning problems. We argue that this package facilitates the use of spiking networks for large-scale machine learning experimentation, and show some simple examples of how we envision BindsNET can be used in practice. BindsNET code is available at https://github.com/Hananel-Hazan/bindsnet
Study of Automatic GPU Offloading Technology for Open IoT
Venue: arXiv cs.DC 2018
Year: 2018

IoT technologies have been progressed. Now Open IoT concept has attracted attentions which achieve various IoT services by integrating horizontal separated devices and services. For Open IoT era, we have proposed the Tacit Computing technology to discover the devices with necessary data for users on demand and use them dynamically. However, existing Tacit Computing does not care about performance and operation cost. Therefore in this paper, we propose an automatic GPU offloading technology as an elementary technology of Tacit Computing which uses Genetic Algorithm to extract appropriate offload loop statements to improve performances. We evaluate a C/C++ matrix manipulation to verify effectiveness of GPU offloading and confirm more than 35 times performances within 1 hour tuning time.
Graph Compression Using Pattern Matching Techniques
Venue: arXiv cs.DS 2018
Year: 2018

Graphs can be used to represent a wide variety of data belonging to different domains. Graphs can capture the relationship among data in an efficient way, and have been widely used. In recent times, with the advent of Big Data, there has been a need to store and compute on large data sets efficiently. However, considering the size of the data sets in question, finding optimal methods to store and process the data has been a challenge. Therefore, in this paper, we study different graph compression techniques and propose novel algorithms to do the same. Specifically, given a graph G = (V, E), where V is the set of vertices and E is the set of edges, and |V| = n, we propose techniques to compress the adjacency matrix representation of the graph. Our algorithms are based on finding patterns within the adjacency matrix data, and replacing the common patterns with specific markers. All the techniques proposed here are lossless compression of graphs. Based on the experimental results, it is observed that our proposed techniques achieve almost 70% compression as compared to adjacency matrix representation. The results show that large graphs can be efficiently stored in smaller memory and exploit the parallel processing power of compute nodes as well as efficiently transfer data between resources.
How Do Source-side Monolingual Word Embeddings Impact Neural Machine Translation?
Venue: arXiv cs.CL 2018
Year: 2018

Using pre-trained word embeddings as input layer is a common practice in many natural language processing (NLP) tasks, but it is largely neglected for neural machine translation (NMT). In this paper, we conducted a systematic analysis on the effect of using pre-trained source-side monolingual word embedding in NMT. We compared several strategies, such as fixing or updating the embeddings during NMT training on varying amounts of data, and we also proposed a novel strategy called dual-embedding that blends the fixing and updating strategies. Our results suggest that pre-trained embeddings can be helpful if properly incorporated into NMT, especially when parallel data is limited or additional in-domain monolingual data is readily available.
The universal approximation power of finite-width deep ReLU networks
Venue: arXiv cs.LG 2018
Year: 2018

We show that finite-width deep ReLU neural networks yield rate-distortion optimal approximation (Bölcskei et al., 2018) of polynomials, windowed sinusoidal functions, one-dimensional oscillatory textures, and the Weierstrass function, a fractal function which is continuous but nowhere differentiable. Together with their recently established universal approximation property of affine function systems (Bölcskei et al., 2018), this shows that deep neural networks approximate vastly different signal structures generated by the affine group, the Weyl-Heisenberg group, or through warping, and even certain fractals, all with approximation error decaying exponentially in the number of neurons. We also prove that in the approximation of sufficiently smooth functions finite-width deep networks require strictly smaller connectivity than finite-depth wide networks.
On the evolution of technical lag in the npm package dependency network
Venue: arXiv cs.SE 2018
Year: 2018

Software packages developed and distributed through package managers extensively depend on other packages. These dependencies are regularly updated, for example to add new features, resolve bugs or fix security issues. In order to take full advantage of the benefits of this type of reuse, developers should keep their dependencies up to date by relying on the latest releases. In practice, however, this is not always possible, and packages lag behind with respect to the latest version of their dependencies. This phenomenon is described as technical lag in the literature. In this paper, we perform an empirical study of technical lag in the npm dependency network by investigating its evolution for over 1.4M releases of 120K packages and 8M dependencies between these releases. We explore how technical lag increases over time, taking into account the release type and the use of package dependency constraints. We also discuss how technical lag can be reduced by relying on the semantic versioning policy.
Wireless Video Caching and Dynamic Streaming under Differentiated Quality Requirements
Venue: arXiv cs.NI 2018
Year: 2018

This paper considers one-hop device-to-device (D2D)-assisted wireless caching networks that cache video files of varying quality levels, with the assumption that the base station can control the video quality but cache-enabled devices cannot. Two problems arise in such a caching network: file placement problem and node association problem. This paper suggests a method to cache videos of different qualities, and thus of varying file sizes, by maximizing the sum of video quality measures that users can enjoy. There exists an interesting trade-off between video quality and video diversity, i.e., the ability to provision diverse video files. By caching high-quality files, the cache-enabled devices can provide high-quality video, but cannot cache a variety of files. Conversely, when the device caches various files, it cannot provide a good quality for file-requesting users. In addition, when multiple devices cache the same file but their qualities are different, advanced node association is required for file delivery. This paper proposes a node association algorithm that maximizes time-averaged video quality for multiple users under a playback delay constraint. In this algorithm, we also consider request collision, the situation where several users request files from the same device at the same time, and we propose two ways to cope with the collision: scheduling of one user and non-orthogonal multiple access. Simulation results verify that the proposed caching method and the node association algorithm work reliably.
Energy-efficient localised rollback after failures via data flow analysis
Venue: arXiv cs.DC 2018
Year: 2018

Exascale systems will suffer failures hourly. HPC programmers rely mostly on application-level checkpoint and a global rollback to recover. In recent years, techniques reducing the number of rolling back processes have been implemented via message logging. However, the log-based approaches have weaknesses, such as being dependent on complex modifications within an MPI implementation, and the fact that a full restart may be required in the general case. To address the limitations of all log-based mechanisms, we return to checkpoint-only mechanisms, but advocate data-flow-driven recovery (DFR), a fundamentally different approach relying on analysis of the data flow of iterative codes, and the well-known concept of data-flow graphs. We demonstrate the effectiveness of DFR for an MPI stencil code to optimise rollback and reduce the overall energy consumption by 10-12 % on idling nodes during localised rollback. We also provide large-scale estimates for the energy savings of DFR compared to global rollback, which for stencil codes increase as n square for a process count n.
Learning Several Languages from Labeled Strings: State Merging and Evolutionary Approaches
Venue: arXiv cs.FL 2018
Year: 2018

The problem of learning pairwise disjoint deterministic finite automata (DFA) from positive examples has been recently addressed. In this paper, we address the problem of identifying a set of DFAs from labeled strings and come up with two methods. The first is based on state merging and a heuristic related to the size of each state merging iteration. State merging operations involving a large number of states are extracted, to provide sub-DFAs. The second method is based on a multi-objective evolutionary algorithm whose fitness function takes into account the accuracy of the DFA w.r.t. the learning sample, as well as the desired number of DFAs. We evaluate our methods on a dataset originated from industry.