OpenRaiser/Intern-Atlas huggingface dataset:
Syntactic Complexity of Suffix-Free Languages
Venue: arXiv cs.FL 2015
Year: 2015

We solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a suffix-free language with $n$ left quotients (that is, with state complexity $n$) is at most $(n-1)^{n-2}+n-2$ for $n\ge 6$. Since this bound is known to be reachable, this settles the problem. We also reduce the alphabet of the witness languages reaching this bound to five letters instead of $n+2$, and show that it cannot be any smaller. Finally, we prove that the transition semigroup of a minimal deterministic automaton accepting a witness language is unique for each $n$.
An Algorithm for $L_\infty$ Approximation by Step Functions
Venue: arXiv cs.DS 2015
Year: 2015

An algorithm is given for determining an optimal $b$-step approximation of weighted data, where the error is measured with respect to the $L_\infty$ norm. For data presorted by the independent variable the algorithm takes $Θ(n + \log n \cdot b(1+\log n/b))$ time and $Θ(n)$ space. This is $Θ(n \log n)$ in the worst case and $Θ(n)$ when $b = O(n/\log n \log\log n)$. A minor change determines an optimal reduced isotonic regression in the same time and space bounds, and the algorithm also solves the $k$-center problem for 1-dimensional weighted data.
Mining the Workload of Real Grid Computing Systems
Venue: arXiv cs.DC 2015
Year: 2015

Since the mid 1990s, grid computing systems have emerged as an analogy for making computing power as pervasive an easily accessible as an electric power grid. Since then, grid computing systems have been shown to be able to provide very large amounts of storage and computing power to mainly support the scientific and engineering research on a wide geographic scale. Understanding the workload characteristics incoming to such systems is a milestone for the design and the tuning of effective resource management strategies. This is accomplished through the workload characterization, where workload characteristics are analyzed and a possibly realistic model for those is obtained. In this paper, we study the workload of some real grid systems by using a data mining approach to build a workload model for job interarrival time and runtime, and a Bayesian approach to capture user correlations and usage patterns. The final model is then validated against the workload coming from a real grid system.
MIMO Beamforming Design towards Maximizing Mutual Information in Wireless Sensor Network
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers joint beamformer design towards maximizing the mutual information in a coherent wireless sensor network with noisy observation and multiple antennae. Leveraging the weighted minimum mean square error and block coordinate ascent (BCA) framework, we propose two new and efficient methods: batch-mode BCA and cyclic multi-block BCA. The existing batch-mode approaches require stringent conditions such as diagonal channel matrices and positive definite second-order matrices, and are therefore inapplicable to our problem. Our match-mode BCA overcomes the previous limitations via a general second-order cone programming formation, and exhibits a strong convergence property which we have rigorously proven. The existing multi-block approaches rely on numerical solvers to handle the subproblems and some render good performance only at high signal-to-noise ratios. Exploiting the convexity of the trust-region subproblem for the convex case, our multi-block BCA significantly reduces the complexity and enhances the previous results by providing an analytical expression for the energy-preserving optimal solution. Analysis and simulations confirm the advantages of the proposed methods.
Appropriate Causal Models and the Stability of Causation
Venue: arXiv cs.AI 2015
Year: 2015

Causal models defined in terms of structural equations have proved to be quite a powerful way of representing knowledge regarding causality. However, a number of authors have given examples that seem to show that the Halpern-Pearl (HP) definition of causality gives intuitively unreasonable answers. Here it is shown that, for each of these examples, we can give two stories consistent with the description in the example, such that intuitions regarding causality are quite different for each story. By adding additional variables, we can disambiguate the stories. Moreover, in the resulting causal models, the HP definition of causality gives the intuitively correct answer. It is also shown that, by adding extra variables, a modification to the original HP definition made to deal with an example of Hopkins and Pearl may not be necessary. Given how much can be done by adding extra variables, there might be a concern that the notion of causality is somewhat unstable. Can adding extra variables in a "conservative" way (i.e., maintaining all the relations between the variables in the original model) cause the answer to the question "Is X=x a cause of Y=y" to alternate between "yes" and "no"? It is shown that we can have such alternation infinitely often, but if we take normality into consideration, we cannot. Indeed, under appropriate normality assumptions. adding an extra variable can change the answer from "yes" to "no", but after that, it cannot cannot change back to "yes".
Large system analysis of a GLRT for detection with large sensor arrays in temporally white noise
Venue: arXiv cs.IT 2015
Year: 2015

This paper addresses the behaviour of a classical multi-antenna GLRT test that allows to detect the presence of a known signal corrupted by a multi-path propagation channel and by an additive white Gaussian noise with unknown spatial covariance matrix. The paper is focused on the case where the number of sensors M is large, and of the same order of magnitude as the sample size N, a context which is modeled by the large system asymptotic regime M goes to infinity, N goes to infinity in such a way that M/N goes to c for c in (0, infinity). The purpose of this paper is to study the behaviour of a GLRT test statistics in this regime, and to show that the corresponding theoretical analysis allows to accurately predict the performance of the test when M and N are of the same order of magnitude.
Ripple Down Rules for Question Answering
Venue: arXiv cs.CL 2015
Year: 2015

Recent years have witnessed a new trend of building ontology-based question answering systems. These systems use semantic web information to produce more precise answers to users' queries. However, these systems are mostly designed for English. In this paper, we introduce an ontology-based question answering system named KbQAS which, to the best of our knowledge, is the first one made for Vietnamese. KbQAS employs our question analysis approach that systematically constructs a knowledge base of grammar rules to convert each input question into an intermediate representation element. KbQAS then takes the intermediate representation element with respect to a target ontology and applies concept-matching techniques to return an answer. On a wide range of Vietnamese questions, experimental results show that the performance of KbQAS is promising with accuracies of 84.1% and 82.4% for analyzing input questions and retrieving output answers, respectively. Furthermore, our question analysis approach can easily be applied to new domains and new languages, thus saving time and human effort.
A Stochastic Geometry Framework for LOS/NLOS Propagation in Dense Small Cell Networks
Venue: arXiv cs.IT 2015
Year: 2015

The need to carry out analytical studies of wireless systems often motivates the usage of simplified models which, despite their tractability, can easily lead to an overestimation of the achievable performance. In the case of dense small cells networks, the standard single slope path-loss model has been shown to provide interesting, but supposedly too optimistic, properties such as the invariance of the outage/coverage probability and of the spectral efficiency to the base station density. This paper seeks to explore the performance of dense small cells networks when a more accurate path-loss model is taken into account. We first propose a stochastic geometry based framework for small cell networks where the signal propagation accounts for both the Line-of-Sight (LOS) and Non-Line-Of-Sight (NLOS) components, such as the model provided by the 3GPP for evaluation of pico-cells in Heterogeneous Networks. We then study the performance of these networks and we show the dependency of some metrics such as the outage/coverage probability, the spectral efficiency and Area Spectral Efficiency (ASE) on the base station density and on the LOS likelihood of the propagation environment. Specifically, we show that, with LOS/NLOS propagation, dense networks still achieve large ASE gain but, at the same time, suffer from high outage probability.
1-Bit Compressive Sensing: Reformulation and RRSP-Based Sign Recovery Theory
Venue: arXiv cs.IT 2015
Year: 2015

Recently, the 1-bit compressive sensing (1-bit CS) has been studied in the field of sparse signal recovery. Since the amplitude information of sparse signals in 1-bit CS is not available, it is often the support or the sign of a signal that can be exactly recovered with a decoding method. In this paper, we first show that a necessary assumption (that has been overlooked in the literature) should be made for some existing theories and discussions for 1-bit CS. Without such an assumption, the found solution by some existing decoding algorithms might be inconsistent with 1-bit measurements. This motivates us to pursue a new direction to develop uniform and nonuniform recovery theories for 1-bit CS with a new decoding method which always generates a solution consistent with 1-bit measurements. We focus on an extreme case of 1-bit CS, in which the measurements capture only the sign of the product of a sensing matrix and a signal. We show that the 1-bit CS model can be reformulated equivalently as an $\ell_0$-minimization problem with linear constraints. This reformulation naturally leads to a new linear-program-based decoding method, referred to as the 1-bit basis pursuit, which is remarkably different from existing formulations. It turns out that the uniqueness condition for the solution of the 1-bit basis pursuit yields the so-called restricted range space property (RRSP) of the transposed sensing matrix. This concept provides a basis to develop sign recovery conditions for sparse signals through 1-bit measurements. We prove that if the sign of a sparse signal can be exactly recovered from 1-bit measurements with 1-bit basis pursuit, then the sensing matrix must admit a certain RRSP, and that if the sensing matrix admits a slightly enhanced RRSP, then the sign of a $k$-sparse signal can be exactly recovered with 1-bit basis pursuit.
Stabilizing Value Iteration with and without Approximation Errors
Venue: arXiv cs.SY 2015
Year: 2015

Adaptive optimal control using value iteration (VI) initiated from a stabilizing policy is theoretically analyzed in various aspects including the continuity of the result, the stability of the system operated using any single/constant resulting control policy, the stability of the system operated using the evolving/time-varying control policy, the convergence of the algorithm, and the optimality of the limit function. Afterwards, the effect of presence of approximation errors in the involved function approximation processes is incorporated and another set of results for boundedness of the approximate VI as well as stability of the system operated under the results for both cases of applying a single policy or an evolving policy are derived. A feature of the presented results is providing estimations of the region of attraction so that if the initial condition is within the region, the whole trajectory will remain inside it and hence, the function approximation results will be reliable.
A Nested Family of $k$-total Effective Rewards for Positional Games
Venue: arXiv cs.DM 2015
Year: 2015

We consider Gillette's two-person zero-sum stochastic games with perfect information. For each $k \in \ZZ_+$ we introduce an effective reward function, called $k$-total. For $k = 0$ and $1$ this function is known as {\it mean payoff} and {\it total reward}, respectively. We restrict our attention to the deterministic case. For all $k$, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that $k$-total reward games can be embedded into $(k+1)$-total reward games.
A Self-adaptive Auto-scaling Method for Scientific Applications on HPC Environments and Clouds
Venue: arXiv cs.DC 2015
Year: 2015

High intensive computation applications can usually take days to months to finish an execution. During this time, it is common to have variations of the available resources when considering that such hardware is usually shared among a plurality of researchers/departments within an organization. On the other hand, High Performance Clusters can take advantage of Cloud Computing bursting techniques for the execution of applications together with the on-premise resources. In order to meet deadlines, high intensive computational applications can use the Cloud to boost their performance when they are data and task parallel. This article presents an ongoing work towards the use of extended resources of an HPC execution platform together with Cloud. We propose an unified view of such heterogeneous environments and a method that monitors, predicts the application execution time, and dynamically shifts part of the domain -- previously running in local HPC hardware -- to be computed on the Cloud, meeting then a specific deadline. The method is exemplified along with a seismic application that, at runtime, adapts itself to move part of the processing to the Cloud (in a movement called bursting) and also auto-scales (the moved part) over cloud nodes. Our preliminary results show that there is an expected overhead for performing this movement and for synchronizing results, but our outcomes demonstrate it is an important feature for meeting deadlines in the case an on-premise cluster is overloaded or cannot provide the capacity needed for a particular project.
Fracking Deep Convolutional Image Descriptors
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we propose a novel framework for learning local image descriptors in a discriminative manner. For this purpose we explore a siamese architecture of Deep Convolutional Neural Networks (CNN), with a Hinge embedding loss on the L2 distance between descriptors. Since a siamese architecture uses pairs rather than single image patches to train, there exist a large number of positive samples and an exponential number of negative samples. We propose to explore this space with a stochastic sampling of the training set, in combination with an aggressive mining strategy over both the positive and negative samples which we denote as "fracking". We perform a thorough evaluation of the architecture hyper-parameters, and demonstrate large performance gains compared to both standard CNN learning strategies, hand-crafted image descriptors like SIFT, and the state-of-the-art on learned descriptors: up to 2.5x vs SIFT and 1.5x vs the state-of-the-art in terms of the area under the curve (AUC) of the Precision-Recall curve.
Random Walk Initialization for Training Very Deep Feedforward Networks
Venue: arXiv cs.NE 2015
Year: 2015

Training very deep networks is an important open problem in machine learning. One of many difficulties is that the norm of the back-propagated error gradient can grow or decay exponentially. Here we show that training very deep feed-forward networks (FFNs) is not as difficult as previously thought. Unlike when back-propagation is applied to a recurrent network, application to an FFN amounts to multiplying the error gradient by a different random matrix at each layer. We show that the successive application of correctly scaled random matrices to an initial vector results in a random walk of the log of the norm of the resulting vectors, and we compute the scaling that makes this walk unbiased. The variance of the random walk grows only linearly with network depth and is inversely proportional to the size of each layer. Practically, this implies a gradient whose log-norm scales with the square root of the network depth and shows that the vanishing gradient problem can be mitigated by increasing the width of the layers. Mathematical analyses and experimental results using stochastic gradient descent to optimize tasks related to the MNIST and TIMIT datasets are provided to support these claims. Equations for the optimal matrix scaling are provided for the linear and ReLU cases.
A Hoare logic for the coinductive trace-based big-step semantics of While
Venue: arXiv cs.LO 2015
Year: 2015

In search for a foundational framework for reasoning about observable behavior of programs that may not terminate, we have previously devised a trace-based big-step semantics for While. In this semantics, both traces and evaluation (relating initial states of program runs to traces they produce) are defined coinductively. On terminating runs, this semantics agrees with the standard inductive state-based semantics. Here we present a Hoare logic counterpart of our coinductive trace-based semantics and prove it sound and complete. Our logic subsumes the standard partial-correctness state-based Hoare logic as well as the total-correctness variation: they are embeddable. In the converse direction, projections can be constructed: a derivation of a Hoare triple in our trace-based logic can be translated into a derivation in the state-based logic of a translated, weaker Hoare triple. Since we work with a constructive underlying logic, the range of program properties we can reason about has a fine structure; in particular, we can distinguish between termination and nondivergence, e.g., unbounded classically total search fails to be terminating, but is nonetheless nondivergent. Our meta-theory is entirely constructive as well, and we have formalized it in Coq.
Visual Scene Representations: Contrast, Scaling and Occlusion
Venue: arXiv cs.CV 2015
Year: 2015

We study the structure of representations, defined as approximations of minimal sufficient statistics that are maximal invariants to nuisance factors, for visual data subject to scaling and occlusion of line-of-sight. We derive analytical expressions for such representations and show that, under certain restrictive assumptions, they are related to features commonly in use in the computer vision community. This link highlights the condition tacitly assumed by these descriptors, and also suggests ways to improve and generalize them. This new interpretation draws connections to the classical theories of sampling, hypothesis testing and group invariance.
Approximate probabilistic verification of hybrid systems
Venue: arXiv cs.SY 2015
Year: 2015

Hybrid systems whose mode dynamics are governed by non-linear ordinary differential equations (ODEs) are often a natural model for biological processes. However such models are difficult to analyze. To address this, we develop a probabilistic analysis method by approximating the mode transitions as stochastic events. We assume that the probability of making a mode transition is proportional to the measure of the set of pairs of time points and value states at which the mode transition is enabled. To ensure a sound mathematical basis, we impose a natural continuity property on the non-linear ODEs. We also assume that the states of the system are observed at discrete time points but that the mode transitions may take place at any time between two successive discrete time points. This leads to a discrete time Markov chain as a probabilistic approximation of the hybrid system. We then show that for BLTL (bounded linear time temporal logic) specifications the hybrid system meets a specification iff its Markov chain approximation meets the same specification with probability $1$. Based on this, we formulate a sequential hypothesis testing procedure for verifying -approximately- that the Markov chain meets a BLTL specification with high probability. Our case studies on cardiac cell dynamics and the circadian rhythm indicate that our scheme can be applied in a number of realistic settings.
Reflections on organization, emergence, and control in sociotechnical systems
Venue: arXiv cs.CY 2015
Year: 2015

Human and artificial organizations may be described as networks of interacting parts. Those parts exchange data and control information and, as a result of these interactions, organizations produce emergent behaviors and purposes -- traits the characterize "the whole" as "greater than the sum of its parts". In this chapter it is argued that, rather than a static and immutable property, emergence should be interpreted as the result of dynamic interactions between forces of opposite sign: centripetal (positive) forces strengthening emergence by consolidating the whole and centrifugal (negative) forces that weaken the social persona and as such are detrimental to emergence. The result of this interaction is called in this chapter as "quality of emergence". This problem is discussed in the context of a particular class of organizations: conventional hierarchies. We highlight how traditional designs produce behaviors that may severely impact the quality of emergence. Finally we discuss a particular class of organizations that do not suffer from the limitations typical of strict hierarchies and result in greater quality of emergence. In some case, however, these enhancements are counterweighted by a reduced degree of controllability and verifiability.
Occlusion Edge Detection in RGB-D Frames using Deep Convolutional Networks
Venue: arXiv cs.CV 2015
Year: 2015

Occlusion edges in images which correspond to range discontinuity in the scene from the point of view of the observer are an important prerequisite for many vision and mobile robot tasks. Although they can be extracted from range data however extracting them from images and videos would be extremely beneficial. We trained a deep convolutional neural network (CNN) to identify occlusion edges in images and videos with both RGB-D and RGB inputs. The use of CNN avoids hand-crafting of features for automatically isolating occlusion edges and distinguishing them from appearance edges. Other than quantitative occlusion edge detection results, qualitative results are provided to demonstrate the trade-off between high resolution analysis and frame-level computation time which is critical for real-time robotics applications.
Monads need not be endofunctors
Venue: arXiv cs.PL 2015
Year: 2015

We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We show that the Kleisli and Eilenberg-Moore constructions carry over to relative monads and are related to relative adjunctions. Under reasonable assumptions, relative monads are monoids in the functor category concerned and extend to monads, giving rise to a coreflection between relative monads and monads. Arrows are also an instance of relative monads.