OpenRaiser/Intern-Atlas huggingface dataset:
Universal Simulation of Directed Systems in the abstract Tile Assembly Model Requires Undirectedness
Venue: arXiv cs.CG 2016
Year: 2016

As a mathematical model of self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) is a remarkable platform for studying the behaviors and powers of self-assembling systems. Capable of Turing universal computation, the aTAM allows algorithmic self-assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. Adding to its completeness, the aTAM was shown to also be intrinsically universal, which means that there exists a single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a seed structure which will then cause self-assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the universal simulator previously given makes use of nondeterminism in terms of tile types placed in several key locations when different assembly sequences are followed, even when simulating a directed system, meaning one that has exactly one unique terminal assembly. The question then became whether or not that nondeterminism is fundamentally required. Here, we answer that in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This provides insight into the role of nondeterminism in self-assembly, which is itself a fundamentally nondeterministic process. To achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to design systems with precisely controllable space resources available to embedded computations. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers.
Highly Efficient Compact Pose SLAM with SLAM++
Venue: arXiv cs.RO 2016
Year: 2016

Maximum likelihood estimation (MLE) is a well-known estimation method used in many robotic and computer vision applications. Under Gaussian assumption, the MLE converts to a nonlinear least squares (NLS) problem. Efficient solutions to NLS exist and they are based on iteratively solving sparse linear systems until convergence. In general, the existing solutions provide only an estimation of the mean state vector, the resulting covariance being computationally too expensive to recover. Nevertheless, in many simultaneous localisation and mapping (SLAM) applications, knowing only the mean vector is not enough. Data association, obtaining reduced state representations, active decisions and next best view are only a few of the applications that require fast state covariance recovery. Furthermore, computer vision and robotic applications are in general performed online. In this case, the state is updated and recomputed every step and its size is continuously growing, therefore, the estimation process may become highly computationally demanding. This paper introduces a general framework for incremental MLE called SLAM++, which fully benefits from the incremental nature of the online applications, and provides efficient estimation of both the mean and the covariance of the estimate. Based on that, we propose a strategy for maintaining a sparse and scalable state representation for large scale mapping, which uses information theory measures to integrate only informative and non-redundant contributions to the state representation. SLAM++ differs from existing implementations by performing all the matrix operations by blocks. This led to extremely fast matrix manipulation and arithmetic operations. Even though this paper tests SLAM++ efficiency on SLAM problems, its applicability remains general.
The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs
Venue: arXiv cs.DS 2016
Year: 2016

Estimating the size of the maximum matching is a canonical problem in graph algorithms, and one that has attracted extensive study over a range of different computational models. We present improved streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity) graphs. * Insert-Only Streams: We present a one-pass algorithm that takes O(c log^2 n) space and approximates the size of the maximum matching in graphs with arboricity c within a factor of O(c). This improves significantly on the state-of-the-art O~(cn^{2/3})-space streaming algorithms. * Dynamic Streams: Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying c-bounded arboricity graph, we present a one-pass algorithm that uses space O~(c^{10/3}n^{2/3}) and returns an O(c)-estimator for the size of the maximum matching. This algorithm improves the state-of-the-art O~(cn^{4/5})-space algorithms, where the O~(.) notation hides logarithmic in $n$ dependencies. In contrast to the previous works, our results take more advantage of the streaming access to the input and characterize the matching size based on the ordering of the edges in the stream in addition to the degree distributions and structural properties of the sparse graphs.
A Modular Formalization of Reversibility for Concurrent Models and Languages
Venue: arXiv cs.LO 2016
Year: 2016

Causal-consistent reversibility is the reference notion of reversibility for concurrency. We introduce a modular framework for defining causal-consistent reversible extensions of concurrent models and languages. We show how our framework can be used to define reversible extensions of formalisms as different as CCS and concurrent X-machines. The generality of the approach allows for the reuse of theories and techniques in different settings.
Automatic text extraction and character segmentation using maximally stable extremal regions
Venue: arXiv cs.CV 2016
Year: 2016

Text detection and segmentation is an important prerequisite for many content based image analysis tasks. The paper proposes a novel text extraction and character segmentation algorithm using Maximally Stable Extremal Regions as basic letter candidates. These regions are then subjected to thresholding and thereafter various connected components are determined to identify separate characters. The algorithm is tested along a set of various JPEG, PNG and BMP images over four different character sets; English, Russian, Hindi and Urdu. The algorithm gives good results for English and Russian character set; however character segmentation in Urdu and Hindi language is not much accurate. The algorithm is simple, efficient, involves no overhead as required in training and gives good results for even low quality images. The paper also proposes various challenges in text extraction and segmentation for multilingual inputs.
OpenCL + OpenSHMEM Hybrid Programming Model for the Adapteva Epiphany Architecture
Venue: arXiv cs.DC 2016
Year: 2016

There is interest in exploring hybrid OpenSHMEM + X programming models to extend the applicability of the OpenSHMEM interface to more hardware architectures. We present a hybrid OpenCL + OpenSHMEM programming model for device-level programming for architectures like the Adapteva Epiphany many-core RISC array processor. The Epiphany architecture comprises a 2D array of low-power RISC cores with minimal uncore functionality connected by a 2D mesh Network-on-Chip (NoC). The Epiphany architecture offers high computational energy efficiency for integer and floating point calculations as well as parallel scalability. The Epiphany-III is available as a coprocessor in platforms that also utilize an ARM CPU host. OpenCL provides good functionality for supporting a co-design programming model in which the host CPU offloads parallel work to a coprocessor. However, the OpenCL memory model is inconsistent with the Epiphany memory architecture and lacks support for inter-core communication. We propose a hybrid programming model in which OpenSHMEM provides a better solution by replacing the non-standard OpenCL extensions introduced to achieve high performance with the Epiphany architecture. We demonstrate the proposed programming model for matrix-matrix multiplication based on Cannon's algorithm showing that the hybrid model addresses the deficiencies of using OpenCL alone to achieve good benchmark performance.
From Manual Android Tests to Automated and Platform Independent Test Scripts
Venue: arXiv cs.SE 2016
Year: 2016

Because Mobile apps are extremely popular and often mission critical nowadays, companies invest a great deal of resources in testing the apps they provide to their customers. Testing is particularly important for Android apps, which must run on a multitude of devices and operating system versions. Unfortunately, as we confirmed in many interviews with quality assurance professionals, app testing is today a very human intensive, and therefore tedious and error prone, activity. To address this problem, and better support testing of Android apps, we propose a new technique that allows testers to easily create platform independent test scripts for an app and automatically run the generated test scripts on multiple devices and operating system versions. The technique does so without modifying the app under test or the runtime system, by (1) intercepting the interactions of the tester with the app and (2) providing the tester with an intuitive way to specify expected results that it then encode as test oracles. We implemented our technique in a tool named Barista and used the tool to evaluate the practical usefulness and applicability of our approach. Our results show that Barista can faithfully encode user defined test cases as test scripts with built-in oracles, generates test scripts that can run on multiple platforms, and can outperform a state-of-the-art tool with similar functionality. Barista and our experimental infrastructure are publicly available.
Coz: Finding Code that Counts with Causal Profiling
Venue: arXiv cs.PF 2016
Year: 2016

Improving performance is a central concern for software developers. To locate optimization opportunities, developers rely on software profilers. However, these profilers only report where programs spent their time: optimizing that code may have no impact on performance. Past profilers thus both waste developer time and make it difficult for them to uncover significant optimization opportunities. This paper introduces causal profiling. Unlike past profiling approaches, causal profiling indicates exactly where programmers should focus their optimization efforts, and quantifies their potential impact. Causal profiling works by running performance experiments during program execution. Each experiment calculates the impact of any potential optimization by virtually speeding up code: inserting pauses that slow down all other code running concurrently. The key insight is that this slowdown has the same relative effect as running that line faster, thus "virtually" speeding it up. We present Coz, a causal profiler, which we evaluate on a range of highly-tuned applications: Memcached, SQLite, and the PARSEC benchmark suite. Coz identifies previously unknown optimization opportunities that are both significant and targeted. Guided by Coz, we improve the performance of Memcached by 9%, SQLite by 25%, and accelerate six PARSEC applications by as much as 68%; in most cases, these optimizations involve modifying under 10 lines of code.
Density Matching Reward Learning
Venue: arXiv cs.RO 2016
Year: 2016

In this paper, we focus on the problem of inferring the underlying reward function of an expert given demonstrations, which is often referred to as inverse reinforcement learning (IRL). In particular, we propose a model-free density-based IRL algorithm, named density matching reward learning (DMRL), which does not require model dynamics. The performance of DMRL is analyzed theoretically and the sample complexity is derived. Furthermore, the proposed DMRL is extended to handle nonlinear IRL problems by assuming that the reward function is in the reproducing kernel Hilbert space (RKHS) and kernel DMRL (KDMRL) is proposed. The parameters for KDMRL can be computed analytically, which greatly reduces the computation time. The performance of KDMRL is extensively evaluated in two sets of experiments: grid world and track driving experiments. In grid world experiments, the proposed KDMRL method is compared with both model-based and model-free IRL methods and shows superior performance on a nonlinear reward setting and competitive performance on a linear reward setting in terms of expected value differences. Then we move on to more realistic experiments of learning different driving styles for autonomous navigation in complex and dynamic tracks using KDMRL and receding horizon control.
Nominal Unification of Higher Order Expressions with Recursive Let
Venue: arXiv cs.PL 2016
Year: 2016

A sound and complete algorithm for nominal unification of higher-order expressions with a recursive let is described, and shown to run in non-deterministic polynomial time. We also explore specializations like nominal letrec-matching for plain expressions and for DAGs and determine the complexity of corresponding unification problems.
Coded Network Function Virtualization: Fault Tolerance via In-Network Coding
Venue: arXiv cs.IT 2016
Year: 2016

Network Function Virtualization (NFV) prescribes the instantiation of network functions on general-purpose network devices, such as servers and switches. While yielding a more flexible and cost-effective network architecture, NFV is potentially limited by the fact that commercial off-the-shelf hardware is less reliable than the dedicated network elements used in conventional cellular deployments. The typical solution for this problem is to duplicate network functions across geographically distributed hardware in order to ensure diversity. In contrast, this letter proposes to leverage channel coding in order to enhance the robustness on NFV to hardware failure. The proposed approach targets the network function of uplink channel decoding, and builds on the algebraic structure of the encoded data frames in order to perform in-network coding on the signals to be processed at different servers. The key principles underlying the proposed coded NFV approach are presented for a simple embodiment and extensions are discussed. Numerical results demonstrate the potential gains obtained with the proposed scheme as compared to the conventional diversity-based fault-tolerant scheme in terms of error probability.
A Bayesian Perspective on Residential Demand Response Using Smart Meter Data
Venue: arXiv cs.SY 2016
Year: 2016

The widespread deployment of Advanced Metering Infrastructure has made granular data of residential electricity consumption available on a large scale. Smart meters enable a two way communication between residential customers and utilities. One field of research that relies on such granular consumption data is Residential Demand Response, where individual users are incentivized to temporarily reduce their consumption during periods of high marginal cost of electricity. To quantify the economic potential of Residential Demand Response, it is important to estimate the reductions during Demand Response hours, taking into account the heterogeneity of electricity users. In this paper, we incorporate latent variables representing behavioral archetypes of electricity users into the process of short term load forecasting with Machine Learning methods, thereby differentiating between varying levels of energy consumption. The latent variables are constructed by fitting Conditional Mixture Models of Linear Regressions and Hidden Markov Models on smart meter readings of a Residential Demand Response program in the western United States. We observe a notable increase in the accuracy of short term load forecasts compared to the case without latent variables. We then estimate the reductions during Demand Response events conditional on the latent variables, and discover a higher DR reduction among users with automated smart home devices compared to those without.
Human Pose Estimation from Depth Images via Inference Embedded Multi-task Learning
Venue: arXiv cs.CV 2016
Year: 2016

Human pose estimation (i.e., locating the body parts / joints of a person) is a fundamental problem in human-computer interaction and multimedia applications. Significant progress has been made based on the development of depth sensors, i.e., accessible human pose prediction from still depth images [32]. However, most of the existing approaches to this problem involve several components/models that are independently designed and optimized, leading to suboptimal performances. In this paper, we propose a novel inference-embedded multi-task learning framework for predicting human pose from still depth images, which is implemented with a deep architecture of neural networks. Specifically, we handle two cascaded tasks: i) generating the heat (confidence) maps of body parts via a fully convolutional network (FCN); ii) seeking the optimal configuration of body parts based on the detected body part proposals via an inference built-in MatchNet [10], which measures the appearance and geometric kinematic compatibility of body parts and embodies the dynamic programming inference as an extra network layer. These two tasks are jointly optimized. Our extensive experiments show that the proposed deep model significantly improves the accuracy of human pose estimation over other several state-of-the-art methods or SDKs. We also release a large-scale dataset for comparison, which includes 100K depth images under challenging scenarios.
A Non-stationary Service Curve Model for Estimation of Cellular Sleep Scheduling
Venue: arXiv cs.NI 2016
Year: 2016

While steady-state solutions of backlog and delay have been derived for essential wireless systems, the analysis of transient phases still poses significant challenges. Considering the majority of short-lived and interactive flows, transient startup effects, as caused by sleep scheduling in cellular networks, have, however, a substantial impact on the performance. To facilitate reasoning about the transient behavior of systems, this paper contributes a notion of non-stationary service curves. Models of systems with sleep scheduling are derived and transient backlogs and delays are analyzed. Further, measurement methods that estimate the service of an unknown system from observations of selected probe traffic are developed. Fundamental limitations of existing measurement methods are explained by the non-convexity of the transient service and further difficulties are shown to be due to the super-additivity of network service processes. A novel two-phase probing technique is devised that first determines the shape of a minimal probe and subsequently obtains an accurate estimate of the unknown service. In a comprehensive measurement campaign, the method is used to evaluate the service of cellular networks with sleep scheduling (2G, 3G, and 4G), revealing considerable transient backlog and delay overshoots that persist for long relaxation times.
Supervisor Synthesis to Thwart Cyber Attack with Bounded Sensor Reading Alterations
Venue: arXiv cs.FL 2016
Year: 2016

One of the major challenges about cyber physical systems is how to prevent cyber attacks to ensure system integrity. There has been a large number of different types of attacks discussed in the modern control and computer science communities. In this paper we aim to investigate one special type of attacks in the discrete-event system framework, where an attacker can arbitrarily alter sensor readings after intercepting them from a target system in order to trick a given supervisor to issue control commands improperly, driving the system to an undesirable state. We first consider the cyber attack problem from an attacker point of view, and formulate an attack with bounded sensor reading alterations (ABSRA) problem. We then show that the supremal (or least restrictive) ABSRA exists and can be synthesized, as long as the plant model and the supervisor model are regular, i.e., representable by finite-state automata. Upon the synthesis of the supremal ABSRA, we present a synthesis algorithm, which ensures that a computed supervisor will be ABSRA-robust , i.e., either an ABSRA will be detectable or will not lead the system to an undesirable state.
Machine Learning with Memristors via Thermodynamic RAM
Venue: arXiv cs.ET 2016
Year: 2016

Thermodynamic RAM (kT-RAM) is a neuromemristive co-processor design based on the theory of AHaH Computing and implemented via CMOS and memristors. The co-processor is a 2-D array of differential memristor pairs (synapses) that can be selectively coupled together (neurons) via the digital bit addressing of the underlying CMOS RAM circuitry. The chip is designed to plug into existing digital computers and be interacted with via a simple instruction set. Anti-Hebbian and Hebbian (AHaH) computing forms the theoretical framework from which a nature-inspired type of computing architecture is built where, unlike von Neumann architectures, memory and processor are physically combined for synaptic operations. Through exploitation of AHaH attractor states, memristor-based circuits converge to attractor basins that represents machine learning solutions such as unsupervised feature learning, supervised classification and anomaly detection. Because kT-RAM eliminates the need to shuttle bits back and forth between memory and processor and can operate at very low voltage levels, it can significantly surpass CPU, GPU, and FPGA performance for synaptic integration and learning operations. Here, we present a memristor technology developed for use in kT-RAM, in particular bi-directional incremental adaptation of conductance via short low-voltage 1.0 V, 1.0 microsecond pulses.
Computation of the incomplete gamma function for negative values of the argument
Venue: arXiv cs.MS 2016
Year: 2016

An algorithm for computing the incomplete gamma function $γ^*(a,z)$ for real values of the parameter $a$ and negative real values of the argument $z$ is presented. The algorithm combines the use of series expansions, Poincaré-type expansions, uniform asymptotic expansions and recurrence relations, depending on the parameter region. A relative accuracy $\sim 10^{-13}$ in the parameter region $(a,z) \in [-500,\,500] \times [-500,\,0)$ can be obtained when computing the function $γ^*(a,z)$ with the Fortran 90 module IncgamNEG implementing the algorithm.
Every Filter Extracts A Specific Texture In Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Many works have concentrated on visualizing and understanding the inner mechanism of convolutional neural networks (CNNs) by generating images that activate some specific neurons, which is called deep visualization. However, it is still unclear what the filters extract from images intuitively. In this paper, we propose a modified code inversion algorithm, called feature map inversion, to understand the function of filter of interest in CNNs. We reveal that every filter extracts a specific texture. The texture from higher layer contains more colours and more intricate structures. We also demonstrate that style of images could be a combination of these texture primitives. Two methods are proposed to reallocate energy distribution of feature maps randomly and purposefully. Then, we inverse the modified code and generate images of diverse styles. With these results, we provide an explanation about why Gram matrix of feature maps \cite{Gatys_2016_CVPR} could represent image style.