OpenRaiser/Intern-Atlas huggingface dataset:
Distribution-based Bisimulation and Bisimulation Metric in Probabilistic Automata
Venue: arXiv cs.FL 2015
Year: 2015

Probabilistic automata were introduced by Rabin in 1963 as language acceptors. Two automata are equivalent if and only if they accept each word with the same probability. On the other side, in the process algebra community, probabilistic automata were re-proposed by Segala in 1995 which are more general than Rabin's automata. Bisimulations have been proposed for Segala's automata to characterize the equivalence between them. So far the two notions of equivalences and their characteristics have been studied mostly independently. In this paper, we consider Segala's automata, and propose a novel notion of distribution-based bisimulation by joining the existing equivalence and bisimilarities. We demonstrate the utility of our definition by studying distribution-based bisimulation metrics, which gives rise to a robust notion of equivalence for Rabin's automata. We compare our notions of bisimulation to some existing distribution-based bisimulations and discuss their compositionality and relations to trace equivalence. Finally, we show the decidability and complexity of all relations.
Does diversity of papers affect their citations? Evidence from American Physical Society Journals
Venue: arXiv cs.DL 2015
Year: 2015

In this work, we study the correlation between interdisciplinarity of papers within physical sciences and their citations by using meta data of articles published in American Physical Society's Physical Review journals between 1985 to 2012. We use the Weitzman diversity index to measure the diversity of papers and authors, exploiting the hierarchical structure of PACS (Physics and Astronomy Classification Scheme) codes. We find that the fraction of authors with high diversity is increasing with time, where as the fraction of least diversity are decreasing, and moderate diversity authors have higher tendency to switch over to other diversity groups. The diversity index of papers is correlated with the citations they received in a given time period from their publication year. Papers with lower and higher end of diversity index receive lesser citations than the moderate diversity papers.
Principal Component Analysis (PCA)-based Massive-MIMO Channel Feedback
Venue: arXiv cs.IT 2015
Year: 2015

Channel-state-information (CSI) feedback methods are considered, especially for massive or very large-scale multiple-input multiple-output (MIMO) systems. To extract essential information from the CSI without redundancy that arises from the highly correlated antennas, a receiver transforms (sparsifies) a correlated CSI vector to an uncorrelated sparse CSI vector by using a Karhunen-Loeve transform (KLT) matrix that consists of the eigen vectors of covariance matrix of CSI vector and feeds back the essential components of the sparse CSI, i.e., a principal component analysis method. A transmitter then recovers the original CSI through the inverse transformation of the feedback vector. Herein, to obtain the covariance matrix at transceiver, we derive analytically the covariance matrix of spatially correlated Rayleigh fading channels based on its statistics including transmit antennas' and receive antennas' correlation matrices, channel variance, and channel delay profile. With the knowledge of the channel statistics, the transceiver can readily obtain the covariance matrix and KLT matrix. Compression feedback error and bit-error-rate performance of the proposed method are analyzed. Numerical results verify that the proposed method is promising, which reduces significantly the feedback overhead of the massive-MIMO systems with marginal performance degradation from full-CSI feedback (e.g., feedback amount reduction by 80%, i.e., 1/5 of original CSI, with spectral efficiency reduction by only 2%). Furthermore, we show numerically that, for a given limited feedback amount, we can find the optimal number of transmit antennas to achieve the largest spectral efficiency, which is a new design framework.
DNA-Level Splice Junction Prediction using Deep Recurrent Neural Networks
Venue: arXiv cs.LG 2015
Year: 2015

A eukaryotic gene consists of multiple exons (protein coding regions) and introns (non-coding regions), and a splice junction refers to the boundary between a pair of exon and intron. Precise identification of spice junctions on a gene is important for deciphering its primary structure, function, and interaction. Experimental techniques for determining exon/intron boundaries include RNA-seq, which is often accompanied by computational approaches. Canonical splicing signals are known, but computational junction prediction still remains challenging because of a large number of false positives and other complications. In this paper, we exploit deep recurrent neural networks (RNNs) to model DNA sequences and to detect splice junctions thereon. We test various RNN units and architectures including long short-term memory units, gated recurrent units, and recently proposed iRNN for in-depth design space exploration. According to our experimental results, the proposed approach significantly outperforms not only conventional machine learning-based methods but also a recent state-of-the-art deep belief network-based technique in terms of prediction accuracy.
Approximating Nash Equilibrium Uniqueness of Power Control In Practical WSNs
Venue: arXiv cs.NI 2015
Year: 2015

Transmission power has a major impact on link and communication reliability and network lifetime in Wireless Sensor Networks. We study power control in a multi-hop Wireless Sensor Network where nodes' communication interfere with each other. Our objective is to determine each node's transmission power level that will reduce the communication interference and keep energy consumption to a minimum. We propose a potential game approach to obtain the unique equilibrium of the network transmission power allocation. The unique equilibrium is located in a continuous domain. However, radio transceivers accept only discrete values for transmission power level setting. We study the viability and performance of mapping the continuous solution from the potential game to the discrete domain required by the radio. We demonstrate the success of our approach through TOSSIM simulation when nodes use the Collection Tree Protocol for routing the data. Also, we show results of our method from the Indriya testbed. We compare it with the case where the motes use Collection Tree Protocol with the maximum transmission power.
Extension of cellular automata by introducing an algorithm of recursive estimation of neighbors
Venue: arXiv cs.CC 2015
Year: 2015

This study focuses on an extended model of a standard cellular automaton (CA) that includes an extra index consisting of a radius that defines a perception area for each cell in addition to the radius defined by the CA rule. Extended standard CA rules form a sequence ordered by this index, which includes the CA rule as its first term. This extension aims at constructing a model that can be used within the CA framework to study the relationship between information processing and pattern formation in collective systems. Although the extension presented here is merely an extrapolation to a CA with a larger rule neighborhood, the extra radius can be interpreted as an individual difference of each cell, which provides a new perspective to CA. Some pattern formations in extended one-dimensional elementary CAs and two-dimensional Life-like CAs are presented. It is expected that the extended CA can be applied to various simulations of complex systems and other fields.
Finding Needles in a Haystack: Missing Tag Detection in Large RFID Systems
Venue: arXiv cs.OH 2015
Year: 2015

Radio frequency identification (RFID) technology has been widely used in missing tag detection to reduce and avoid inventory shrinkage. In this application, promptly finding out the missing event is of paramount importance. However, existing missing tag detection protocols cannot efficiently handle the presence of a large number of unexpected tags whose IDs are not known to the reader, which shackles the time efficiency. To deal with the problem of detecting missing tags in the presence of unexpected tags, this paper introduces a two-phase Bloom filter-based missing tag detection protocol (BMTD). The proposed BMTD exploits Bloom filter in sequence to first deactivate the unexpected tags and then test the membership of the expected tags, thus dampening the interference from the unexpected tags and considerably reducing the detection time. Moreover, the theoretical analysis of the protocol parameters is performed to minimize the detection time of the proposed BMTD and achieve the required reliability simultaneously. Extensive experiments are then conducted to evaluate the performance of the proposed BMTD. The results demonstrate that the proposed BMTD significantly outperforms the state-of-the-art solutions.
Symphony from Synapses: Neocortex as a Universal Dynamical Systems Modeller using Hierarchical Temporal Memory
Venue: arXiv cs.NE 2015
Year: 2015

Reverse engineering the brain is proving difficult, perhaps impossible. While many believe that this is just a matter of time and effort, a different approach might help. Here, we describe a very simple idea which explains the power of the brain as well as its structure, exploiting complex dynamics rather than abstracting it away. Just as a Turing Machine is a Universal Digital Computer operating in a world of symbols, we propose that the brain is a Universal Dynamical Systems Modeller, evolved bottom-up (itself using nested networks of interconnected, self-organised dynamical systems) to prosper in a world of dynamical systems. Recent progress in Applied Mathematics has produced startling evidence of what happens when abstract Dynamical Systems interact. Key latent information describing system A can be extracted by system B from very simple signals, and signals can be used by one system to control and manipulate others. Using these facts, we show how a region of the neocortex uses its dynamics to intrinsically "compute" about the external and internal world. Building on an existing "static" model of cortical computation (Hawkins' Hierarchical Temporal Memory - HTM), we describe how a region of neocortex can be viewed as a network of components which together form a Dynamical Systems modelling module, connected via sensory and motor pathways to the external world, and forming part of a larger dynamical network in the brain. Empirical modelling and simulations of Dynamical HTM are possible with simple extensions and combinations of currently existing open source software. We list a number of relevant projects.
Solving stable matching problems using answer set programming
Venue: arXiv cs.AI 2015
Year: 2015

Since the introduction of the stable marriage problem (SMP) by Gale and Shapley (1962), several variants and extensions have been investigated. While this variety is useful to widen the application potential, each variant requires a new algorithm for finding the stable matchings. To address this issue, we propose an encoding of the SMP using answer set programming (ASP), which can straightforwardly be adapted and extended to suit the needs of specific applications. The use of ASP also means that we can take advantage of highly efficient off-the-shelf solvers. To illustrate the flexibility of our approach, we show how our ASP encoding naturally allows us to select optimal stable matchings, i.e. matchings that are optimal according to some user-specified criterion. To the best of our knowledge, our encoding offers the first exact implementation to find sex-equal, minimum regret, egalitarian or maximum cardinality stable matchings for SMP instances in which individuals may designate unacceptable partners and ties between preferences are allowed. This paper is under consideration in Theory and Practice of Logic Programming (TPLP).
Typed realizability for first-order classical analysis
Venue: arXiv cs.LO 2015
Year: 2015

We describe a realizability framework for classical first-order logic in which realizers live in (a model of) typed λμ-calculus. This allows a direct interpretation of classical proofs, avoiding the usual negative translation to intuitionistic logic. We prove that the usual terms of Gödel's system T realize the axioms of Peano arithmetic, and that under some assumptions on the computational model, the bar recursion operator realizes the axiom of dependent choice. We also perform a proper analysis of relativization, which allows for less technical proofs of adequacy. Extraction of algorithms from proofs of Π02 formulas relies on a novel implementation of Friedman's trick exploiting the control possibilities of the language. This allows to have extracted programs with simpler types than in the case of negative translation followed by intuitionistic realizability.
The read/write protocol complex is collapsible
Venue: arXiv cs.DC 2015
Year: 2015

The celebrated \emph{asynchronous computability theorem} provides a characterization of the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by writing and taking atomic snapshots of a shared memory. Several variations of the model have been proposed (immediate snapshots and iterated immediate snapshots), all equivalent for wait-free solution of decision tasks, in spite of the fact that the protocol complexes that arise from the different models are structurally distinct. The topological and combinatorial properties of these snapshot protocol complexes have been studied in detail, providing explanations for why the asynchronous computability theorem holds in all the models. In reality concurrent systems do not provide processes with snapshot operations. Instead, snapshots are implemented (by a wait-free protocol) using operations that write and read individual shared memory locations. Thus, read/write protocols are also computationally equivalent to snapshot protocols. However, the structure of the read/write protocol complex has not been studied. In this paper we show that the read/write iterated protocol complex is collapsible (and hence contractible). Furthermore, we show that a distributed protocol that wait-free implements atomic snapshots in effect is performing the collapses.
Differential Evolution with Event-Triggered Impulsive Control
Venue: arXiv cs.NE 2015
Year: 2015

Differential evolution (DE) is a simple but powerful evolutionary algorithm, which has been widely and successfully used in various areas. In this paper, an event-triggered impulsive control scheme (ETI) is introduced to improve the performance of DE. Impulsive control, the concept of which derives from control theory, aims at regulating the states of a network by instantly adjusting the states of a fraction of nodes at certain instants, and these instants are determined by event-triggered mechanism (ETM). By introducing impulsive control and ETM into DE, we hope to change the search performance of the population in a positive way after revising the positions of some individuals at certain moments. At the end of each generation, the impulsive control operation is triggered when the update rate of the population declines or equals to zero. In detail, inspired by the concepts of impulsive control, two types of impulses are presented within the framework of DE in this paper: stabilizing impulses and destabilizing impulses. Stabilizing impulses help the individuals with lower rankings instantly move to a desired state determined by the individuals with better fitness values. Destabilizing impulses randomly alter the positions of inferior individuals within the range of the current population. By means of intelligently modifying the positions of a part of individuals with these two kinds of impulses, both exploitation and exploration abilities of the whole population can be meliorated. In addition, the proposed ETI is flexible to be incorporated into several state-of-the-art DE variants. Experimental results over the CEC 2014 benchmark functions exhibit that the developed scheme is simple yet effective, which significantly improves the performance of the considered DE algorithms.
Non-Zero Sum Games for Reactive Synthesis
Venue: arXiv cs.LO 2015
Year: 2015

In this invited contribution, we summarize new solution concepts useful for the synthesis of reactive systems that we have introduced in several recent publications. These solution concepts are developed in the context of non-zero sum games played on graphs. They are part of the contributions obtained in the inVEST project funded by the European Research Council.
Improving Latency in a Signal Processing System on the Epiphany Architecture
Venue: arXiv cs.DC 2015
Year: 2015

In this paper we use the Adapteva Epiphany manycore chip to demonstrate how the throughput and the latency of a baseband signal processing chain, typically found in LTE or WiFi, can be optimized by a combination of task- and data parallelization, and data pipelining. The parallelization and data pipelining are facilitated by the shared memory architecture of the Epiphany, and the fact that a processor on one core can write directly into the memory of any other core on the chip.
Reconstruction of Enhanced Ultrasound Images From Compressed Measurements Using Simultaneous Direction Method of Multipliers
Venue: arXiv cs.CV 2015
Year: 2015

High resolution ultrasound image reconstruction from a reduced number of measurements is of great interest in ultrasound imaging, since it could enhance both the frame rate and image resolution. Compressive deconvolution, combining compressed sensing and image deconvolution, represents an interesting possibility to consider this challenging task. The model of compressive deconvolution includes, in addition to the compressive sampling matrix, a 2D convolution operator carrying the information on the system point spread function. Through this model, the resolution of reconstructed ultrasound images from compressed measurements mainly depends on three aspects: the acquisition setup, i.e. the incoherence of the sampling matrix, the image regularization, i.e. the sparsity prior, and the optimization technique. In this paper, we mainly focused on the last two aspects. We proposed a novel simultaneous direction method of multipliers-based optimization scheme to invert the linear model, including two regularization terms expressing the sparsity of the RF images in a given basis and the generalized Gaussian statistical assumption on tissue reflectivity functions. The performance of the method is evaluated on both simulated and in vivo data.
An Incoercible E-Voting Scheme Based on Revised Simplified Verifiable Re-encryption Mix-nets
Venue: arXiv cs.CR 2015
Year: 2015

Simplified verifiable re-encryption mix-net (SVRM) is revised and a scheme for e-voting systems is developed based on it. The developed scheme enables e-voting systems to satisfy all essential requirements of elections. Namely, they satisfy requirements about privacy, verifiability, fairness and robustness. It also successfully protects voters from coercers except cases where the coercers force voters to abstain from elections. In detail, voters can conceal correspondences between them and their votes, anyone can verify the accuracy of election results, and interim election results are concealed from any entity. About incoercibility, provided that erasable-state voting booths which disable voters to memorize complete information exchanged between them and election authorities for constructing votes are available, coercer C cannot know candidates that voters coerced by C had chosen even if the candidates are unique to the voters. In addition, elections can be completed without reelections even when votes were handled illegitimately.
Successive Ray Refinement and Its Application to Coordinate Descent for LASSO
Venue: arXiv cs.LG 2015
Year: 2015

Coordinate descent is one of the most popular approaches for solving Lasso and its extensions due to its simplicity and efficiency. When applying coordinate descent to solving Lasso, we update one coordinate at a time while fixing the remaining coordinates. Such an update, which is usually easy to compute, greedily decreases the objective function value. In this paper, we aim to improve its computational efficiency by reducing the number of coordinate descent iterations. To this end, we propose a novel technique called Successive Ray Refinement (SRR). SRR makes use of the following ray continuation property on the successive iterations: for a particular coordinate, the value obtained in the next iteration almost always lies on a ray that starts at its previous iteration and passes through the current iteration. Motivated by this ray-continuation property, we propose that coordinate descent be performed not directly on the previous iteration but on a refined search point that has the following properties: on one hand, it lies on a ray that starts at a history solution and passes through the previous iteration, and on the other hand, it achieves the minimum objective function value among all the points on the ray. We propose two schemes for defining the search point and show that the refined search point can be efficiently obtained. Empirical results for real and synthetic data sets show that the proposed SRR can significantly reduce the number of coordinate descent iterations, especially for small Lasso regularization parameters.
An Introduction to Effectus Theory
Venue: arXiv cs.LO 2015
Year: 2015

Effectus theory is a new branch of categorical logic that aims to capture the essentials of quantum logic, with probabilistic and Boolean logic as special cases. Predicates in effectus theory are not subobjects having a Heyting algebra structure, like in topos theory, but `characteristic' functions, forming effect algebras. Such effect algebras are algebraic models of quantitative logic, in which double negation holds. Effects in quantum theory and fuzzy predicates in probability theory form examples of effect algebras. This text is an account of the basics of effectus theory. It includes the fundamental duality between states and effects, with the associated Born rule for validity of an effect (predicate) in a particular state. A basic result says that effectuses can be described equivalently in both `total' and `partial' form. So-called `commutative' and `Boolean' effectuses are distinguished, for probabilistic and classical models. It is shown how these Boolean effectuses are essentially extensive categories. A large part of the theory is devoted to the logical notions of comprehension and quotient, which are described abstractly as right adjoint to truth, and as left adjoint to falisity, respectively. It is illustrated how comprehension and quotients are closely related to measurement. The paper closes with a section on `non-commutative' effectus theory, where the appropriate formalisation is not entirely clear yet.
Modeling Progress in AI
Venue: arXiv cs.AI 2015
Year: 2015

Participants in recent discussions of AI-related issues ranging from intelligence explosion to technological unemployment have made diverse claims about the nature, pace, and drivers of progress in AI. However, these theories are rarely specified in enough detail to enable systematic evaluation of their assumptions or to extrapolate progress quantitatively, as is often done with some success in other technological domains. After reviewing relevant literatures and justifying the need for more rigorous modeling of AI progress, this paper contributes to that research program by suggesting ways to account for the relationship between hardware speed increases and algorithmic improvements in AI, the role of human inputs in enabling AI capabilities, and the relationships between different sub-fields of AI. It then outlines ways of tailoring AI progress models to generate insights on the specific issue of technological unemployment, and outlines future directions for research on AI progress.