OpenRaiser/Intern-Atlas huggingface dataset:
SAFFRON: A Fast, Efficient, and Robust Framework for Group Testing based on Sparse-Graph Codes
Venue: arXiv cs.IT 2015
Year: 2015

Group testing tackles the problem of identifying a population of $K$ defective items from a set of $n$ items by pooling groups of items efficiently in order to cut down the number of tests needed. The result of a test for a group of items is positive if any of the items in the group is defective and negative otherwise. The goal is to judiciously group subsets of items such that defective items can be reliably recovered using the minimum number of tests, while also having a low-complexity decoding procedure. We describe SAFFRON (Sparse-grAph codes Framework For gROup testiNg), a non-adaptive group testing paradigm that recovers at least a $(1-ε)$-fraction (for any arbitrarily small $ε> 0$) of $K$ defective items with high probability with $m=6C(ε)K\log_2{n}$ tests, where $C(ε)$ is a precisely characterized constant that depends only on $ε$. For instance, it can provably recover at least $(1-10^{-6})K$ defective items with $m \simeq 68 K \log_2{n}$ tests. The computational complexity of the decoding algorithm of SAFFRON is $\mathcal{O}(K\log n)$, which is order-optimal. Further, we robustify SAFFRON such that it can reliably recover the set of $K$ defective items even in the presence of erroneous or noisy test results. We also propose Singleton-Only-SAFFRON, a variant of SAFFRON, that recovers all the $K$ defective items with $m=2e(1+α)K\log K \log_2 n$ tests with probability $1-\mathcal{O}{\left(\frac{1}{K^α}\right)}$, where $α>0$ is a constant. By leveraging powerful design and analysis tools from modern sparse-graph coding theory, SAFFRON is the first approach to reliable, large-scale probabilistic group testing that offers both precisely characterizable number of tests needed (down to the constants) together with order-optimal decoding complexity.
A Dictionary Learning Approach for Factorial Gaussian Models
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we develop a parameter estimation method for factorially parametrized models such as Factorial Gaussian Mixture Model and Factorial Hidden Markov Model. Our contributions are two-fold. First, we show that the emission matrix of the standard Factorial Model is unidentifiable even if the true assignment matrix is known. Secondly, we address the issue of identifiability by making a one component sharing assumption and derive a parameter learning algorithm for this case. Our approach is based on a dictionary learning problem of the form $X = O R$, where the goal is to learn the dictionary $O$ given the data matrix $X$. We argue that due to the specific structure of the activation matrix $R$ in the shared component factorial mixture model, and an incoherence assumption on the shared component, it is possible to extract the columns of the $O$ matrix without the need for alternating between the estimation of $O$ and $R$.
On Lossy Joint Source-Channel Coding In Energy Harvesting Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

We study the problem of lossy joint source-channel coding in a single-user energy harvesting communication system with causal energy arrivals and the energy storage unit may have leakage. In particular, we investigate the achievable distortion in the transmission of a single source via an energy harvesting transmitter over a point-to-point channel. We consider an adaptive joint source-channel coding system, where the length of channel codewords varies based on the available battery charge. We first establish a lower bound on the achievable distortion. Then, as necessary conditions for local optimality, we obtain two coupled equations that determine the mismatch ratio between channel symbols and source symbols as well as the transmission power, both as functions of the battery charge. As examples of continuous and discrete sources, we consider Gaussian and binary sources respectively. For the Gaussian case, we obtain a closed-form expression for the mismatch factor in terms of the $Lambert W$ function, and show that an increasing transmission power policy results in a decreasing mismatch factor policy and vice versa. Finally, we numerically compare the performance of the adaptive mismatch factor scheme to the case of a constant mismatch factor.
Learning to Predict Independent of Span
Venue: arXiv cs.LG 2015
Year: 2015

We consider how to learn multi-step predictions efficiently. Conventional algorithms wait until observing actual outcomes before performing the computations to update their predictions. If predictions are made at a high rate or span over a large amount of time, substantial computation can be required to store all relevant observations and to update all predictions when the outcome is finally observed. We show that the exact same predictions can be learned in a much more computationally congenial way, with uniform per-step computation that does not depend on the span of the predictions. We apply this idea to various settings of increasing generality, repeatedly adding desired properties and each time deriving an equivalent span-independent algorithm for the conventional algorithm that satisfies these desiderata. Interestingly, along the way several known algorithmic constructs emerge spontaneously from our derivations, including dutch eligibility traces, temporal difference errors, and averaging. This allows us to link these constructs one-to-one to the corresponding desiderata, unambiguously connecting the `how' to the `why'. Each step, we make sure that the derived algorithm subsumes the previous algorithms, thereby retaining their properties. Ultimately we arrive at a single general temporal-difference algorithm that is applicable to the full setting of reinforcement learning.
Enabling adaptive scientific workflows via trigger detection
Venue: arXiv cs.CE 2015
Year: 2015

Next generation architectures necessitate a shift away from traditional workflows in which the simulation state is saved at prescribed frequencies for post-processing analysis. While the need to shift to in~situ workflows has been acknowledged for some time, much of the current research is focused on static workflows, where the analysis that would have been done as a post-process is performed concurrently with the simulation at user-prescribed frequencies. Recently, research efforts are striving to enable adaptive workflows, in which the frequency, composition, and execution of computational and data manipulation steps dynamically depend on the state of the simulation. Adapting the workflow to the state of simulation in such a data-driven fashion puts extremely strict efficiency requirements on the analysis capabilities that are used to identify the transitions in the workflow. In this paper we build upon earlier work on trigger detection using sublinear techniques to drive adaptive workflows. Here we propose a methodology to detect the time when sudden heat release occurs in simulations of turbulent combustion. Our proposed method provides an alternative metric that can be used along with our former metric to increase the robustness of trigger detection. We show the effectiveness of our metric empirically for predicting heat release for two use cases.
Cold Object Identification in the Java Virtual Machine
Venue: arXiv cs.PL 2015
Year: 2015

Many Java applications instantiate objects within the Java heap that are persistent but seldom if ever referenced by the application. Examples include strings, such as error messages, and collections of value objects that are preloaded for fast access but they may include objects that are seldom referenced. This paper describes a stack-based framework for detecting these "cold" objects at runtime, with a view to marshaling and sequestering them in designated regions of the heap where they may be preferentially paged out to a backing store, thereby freeing physical memory pages for occupation by more active objects. Furthermore, we evaluate the correctness and efficiency of stack-based approach with an Access Barrier. The experimental results from a series of SPECjvm2008 benchmarks are presented.
Recursive Training of 2D-3D Convolutional Networks for Neuronal Boundary Detection
Venue: arXiv cs.CV 2015
Year: 2015

Efforts to automate the reconstruction of neural circuits from 3D electron microscopic (EM) brain images are critical for the field of connectomics. An important computation for reconstruction is the detection of neuronal boundaries. Images acquired by serial section EM, a leading 3D EM technique, are highly anisotropic, with inferior quality along the third dimension. For such images, the 2D max-pooling convolutional network has set the standard for performance at boundary detection. Here we achieve a substantial gain in accuracy through three innovations. Following the trend towards deeper networks for object recognition, we use a much deeper network than previously employed for boundary detection. Second, we incorporate 3D as well as 2D filters, to enable computations that use 3D context. Finally, we adopt a recursively trained architecture in which a first network generates a preliminary boundary map that is provided as input along with the original image to a second network that generates a final boundary map. Backpropagation training is accelerated by ZNN, a new implementation of 3D convolutional networks that uses multicore CPU parallelism for speed. Our hybrid 2D-3D architecture could be more generally applicable to other types of anisotropic 3D images, including video, and our recursive framework for any image labeling problem.
Reversible Barbed Congruence on Configuration Structures
Venue: arXiv cs.LO 2015
Year: 2015

A standard contextual equivalence for process algebras is strong barbed congruence. Configuration structures are a denotational semantics for processes in which one can define equivalences that are more discriminating, i.e. that distinguish the denotation of terms equated by barbed congruence. Hereditary history preserving bisimulation (HHPB) is such a relation. We define a strong back and forth barbed congruence using a reversible process algebra and show that the relation induced by the back and forth congruence is equivalent to HHPB, providing a contextual characterization of HHPB.
Application Distribution Model In Volunteer Computing Environment Using Peer-to-Peer Torrent Like Approach
Venue: arXiv cs.DC 2015
Year: 2015

Volunteer computing has been known as an alternative solution to solve complex problems. It is acknowledged for its simplicity and its ability to work on multiple operating systems. Nonetheless, setting up a server for volunteer computing can be time consuming and relatively complex to be implemented. This paper offer a model which can ease the effort of setting up a server by making the agent works two ways, as seeder and leecher, like P2P torrent approaches. The model consists of measurement units to manage applications to be distributed, system hierarchy, and basic procedures for the server and the agent. The model has been tested in four scenarios using 2,000,000 to 3,000,000 integer data employing up to six nodes. The tests demonstrate speedup in three of the scenarios.
Warehouse Layout Method Based on Ant Colony and Backtracking Algorithm
Venue: arXiv cs.AI 2015
Year: 2015

Warehouse is one of the important aspects of a company. Therefore, it is necessary to improve Warehouse Management System (WMS) to have a simple function that can determine the layout of the storage goods. In this paper we propose an improved warehouse layout method based on ant colony algorithm and backtracking algorithm. The method works on two steps. First, it generates a solutions parameter tree from backtracking algorithm. Then second, it deducts the solutions parameter by using a combination of ant colony algorithm and backtracking algorithm. This method was tested by measuring the time needed to build the tree and to fill up the space using two scenarios. The method needs 0.294 to 33.15 seconds to construct the tree and 3.23 seconds (best case) to 61.41 minutes (worst case) to fill up the warehouse. This method is proved to be an attractive alternative solution for warehouse layout system.
Robust Node Estimation and Topology Discovery Algorithm in Large-Scale Wireless Sensor Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper introduces a novel algorithm for cardinality, i.e., the number of nodes, estimation in large scale anonymous graphs using statistical inference methods. Applications of this work include estimating the number of sensor devices, online social users, active protein cells, etc. In anonymous graphs, each node possesses little or non-existing information on the network topology. In particular, this paper assumes that each node only knows its unique identifier. The aim is to estimate the cardinality of the graph and the neighbours of each node by querying a small portion of them. While the former allows the design of more efficient coding schemes for the network, the second provides a reliable way for routing packets. As a reference for comparison, this work considers the Best Linear Unbiased Estimators (BLUE). For dense graphs and specific running times, the proposed algorithm produces a cardinality estimate proportional to the BLUE. Furthermore, for an arbitrary number of iterations, the estimate converges to the BLUE as the number of queried nodes tends to the total number of nodes in the network. Simulation results confirm the theoretical results by revealing that, for a moderate running time, asking a small group of nodes is sufficient to perform an estimation of 95% of the whole network.
Duration and Interval Hidden Markov Model for Sequential Data Analysis
Venue: arXiv cs.AI 2015
Year: 2015

Analysis of sequential event data has been recognized as one of the essential tools in data modeling and analysis field. In this paper, after the examination of its technical requirements and issues to model complex but practical situation, we propose a new sequential data model, dubbed Duration and Interval Hidden Markov Model (DI-HMM), that efficiently represents "state duration" and "state interval" of data events. This has significant implications to play an important role in representing practical time-series sequential data. This eventually provides an efficient and flexible sequential data retrieval. Numerical experiments on synthetic and real data demonstrate the efficiency and accuracy of the proposed DI-HMM.
DeepWriterID: An End-to-end Online Text-independent Writer Identification System
Venue: arXiv cs.CV 2015
Year: 2015

Owing to the rapid growth of touchscreen mobile terminals and pen-based interfaces, handwriting-based writer identification systems are attracting increasing attention for personal authentication, digital forensics, and other applications. However, most studies on writer identification have not been satisfying because of the insufficiency of data and difficulty of designing good features under various conditions of handwritings. Hence, we introduce an end-to-end system, namely DeepWriterID, employed a deep convolutional neural network (CNN) to address these problems. A key feature of DeepWriterID is a new method we are proposing, called DropSegment. It designs to achieve data augmentation and improve the generalized applicability of CNN. For sufficient feature representation, we further introduce path signature feature maps to improve performance. Experiments were conducted on the NLPR handwriting database. Even though we only use pen-position information in the pen-down state of the given handwriting samples, we achieved new state-of-the-art identification rates of 95.72% for Chinese text and 98.51% for English text.
"The Good, The Bad And The Ugly": Evaluation of Wi-Fi Steganography
Venue: arXiv cs.MM 2015
Year: 2015

In this paper we propose a new method for the evaluation of network steganography algorithms based on the new concept of "the moving observer". We considered three levels of undetectability named: "good", "bad", and "ugly". To illustrate this method we chose Wi-Fi steganography as a solid family of information hiding protocols. We present the state of the art in this area covering well-known hiding techniques for 802.11 networks. "The moving observer" approach could help not only in the evaluation of steganographic algorithms, but also might be a starting point for a new detection system of network steganography. The concept of a new detection system, called MoveSteg, is explained in detail.
Games for Dependent Types
Venue: arXiv cs.LO 2015
Year: 2015

We present a model of dependent type theory (DTT) with Pi-, 1-, Sigma- and intensional Id-types, which is based on a slight variation of the category of AJM-games and history-free winning strategies. The model satisfies Streicher's criteria of intensionality and refutes function extensionality. The principle of uniqueness of identity proofs is satisfied. We show it contains a submodel as a full subcategory which gives a faithful model of DTT with Pi-, 1-, Sigma- and intensional Id-types and, additionally, finite inductive type families. This smaller model is fully (and faithfully) complete with respect to the syntax at the type hierarchy built without Id-types, as well as at the class of types where we allow for one strictly positive occurrence of an Id-type. Definability for the full type hierarchy with Id-types remains to be investigated.
Using User Generated Online Photos to Estimate and Monitor Air Pollution in Major Cities
Venue: arXiv cs.CV 2015
Year: 2015

With the rapid development of economy in China over the past decade, air pollution has become an increasingly serious problem in major cities and caused grave public health concerns in China. Recently, a number of studies have dealt with air quality and air pollution. Among them, some attempt to predict and monitor the air quality from different sources of information, ranging from deployed physical sensors to social media. These methods are either too expensive or unreliable, prompting us to search for a novel and effective way to sense the air quality. In this study, we propose to employ the state of the art in computer vision techniques to analyze photos that can be easily acquired from online social media. Next, we establish the correlation between the haze level computed directly from photos with the official PM 2.5 record of the taken city at the taken time. Our experiments based on both synthetic and real photos have shown the promise of this image-based approach to estimating and monitoring air pollution.
The Mont-Blanc Project: First Phase Successfully Finished
Venue: arXiv cs.DC 2015
Year: 2015

Running from October 2011 to June 2015, the aim of the European project Mont-Blanc has been to develop an approach to Exascale computing based on embedded power-efficient technology. The main goals of the project were to i) build an HPC prototype using currently available energy-efficient embedded technology, ii) design a Next Generation system to overcome the limitations of the built prototype and iii) port a set of representative Exascale applications to the system. This article summarises the contributions from the Leibniz Supercomputing Centre (LRZ) and the Juelich Supercomputing Centre (JSC), Germany, to the Mont-Blanc project.
Efficient Representation of Uncertainty for Stochastic Economic Dispatch
Venue: arXiv cs.CE 2015
Year: 2015

Stochastic economic dispatch models address uncertainties in forecasts of renewable generation output by considering a finite number of realizations drawn from a stochastic process model, typically via Monte Carlo sampling. Accurate evaluations of expectations or higher-order moments for quantities of interest, e.g., generating cost, can require a prohibitively large number of samples. We propose an alternative to Monte Carlo sampling based on Polynomial Chaos expansions. These representations are based on sparse quadrature methods, and enable accurate propagation of uncertainties in model parameters. We also investigate a method based on Karhunen-Loeve expansions that enables us to efficiently represent uncertainties in renewable energy generation. Considering expected production cost, we demonstrate that the proposed approach can yield several orders of magnitude reduction in computational cost for solving stochastic economic dispatch relative to Monte Carlo sampling, for a given target error threshold.
Rank-1 Tensor Approximation Methods and Application to Deflation
Venue: arXiv cs.NA 2015
Year: 2015

Because of the attractiveness of the canonical polyadic (CP) tensor decomposition in various applications, several algorithms have been designed to compute it, but efficient ones are still lacking. Iterative deflation algorithms based on successive rank-1 approximations can be used to perform this task, since the latter are rather easy to compute. We first present an algebraic rank-1 approximation method that performs better than the standard higher-order singular value decomposition (HOSVD) for three-way tensors. Second, we propose a new iterative rank-1 approximation algorithm that improves any other rank-1 approximation method. Third, we describe a probabilistic framework allowing to study the convergence of deflation CP decomposition (DCPD) algorithms based on successive rank-1 approximations. A set of computer experiments then validates theoretical results and demonstrates the efficiency of DCPD algorithms compared to other ones.
Accelerating the Kamada-Kawai algorithm for boundary detection in a mobile ad hoc network
Venue: arXiv cs.NI 2015
Year: 2015

Force-directed algorithms such as the Kamada-Kawai algorithm have shown promising results for solving the boundary detection problem in a mobile ad hoc network. However, the classical Kamada-Kawai algorithm does not scale well when it is used in networks with large numbers of nodes. It also produces poor results in non-convex networks. To address these problems, this paper proposes an improved version of the Kamada-Kawai algorithm. The proposed extension includes novel heuristics and algorithms that achieve a faster energy level reduction. Our experimental results show that the improved algorithm can significantly shorten the processing time and detect boundary nodes with an acceptable level of accuracy.
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
Venue: arXiv cs.DS 2015
Year: 2015

We give a general unified method that can be used for $L_1$ {\em closeness testing} of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testing the equivalence of two unknown (potentially arbitrary) univariate distributions under the $\mathcal{A}_k$-distance metric: Given sample access to distributions with density functions $p, q: I \to \mathbb{R}$, we want to distinguish between the cases that $p=q$ and $\|p-q\|_{\mathcal{A}_k} \ge ε$ with probability at least $2/3$. We show that for any $k \ge 2, ε>0$, the {\em optimal} sample complexity of the $\mathcal{A}_k$-closeness testing problem is $Θ(\max\{ k^{4/5}/ε^{6/5}, k^{1/2}/ε^2 \})$. This is the first $o(k)$ sample algorithm for this problem, and yields new, simple $L_1$ closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions.