OpenRaiser/Intern-Atlas huggingface dataset:
ICDAR 2015 Text Reading in the Wild Competition
Venue: arXiv cs.CV 2015
Year: 2015

Recently, text detection and recognition in natural scenes are becoming increasing popular in the computer vision community as well as the document analysis community. However, majority of the existing ideas, algorithms and systems are specifically designed for English. This technical report presents the final results of the ICDAR 2015 Text Reading in the Wild (TRW 2015) competition, which aims at establishing a benchmark for assessing detection and recognition algorithms devised for both Chinese and English scripts and providing a playground for researchers from the community. In this article, we describe in detail the dataset, tasks, evaluation protocols and participants of this competition, and report the performance of the participating methods. Moreover, promising directions for future research are discussed.
A cognitive neural architecture able to learn and communicate through natural language
Venue: arXiv cs.CL 2015
Year: 2015

Communicative interactions involve a kind of procedural knowledge that is used by the human brain for processing verbal and nonverbal inputs and for language production. Although considerable work has been done on modeling human language abilities, it has been difficult to bring them together to a comprehensive tabula rasa system compatible with current knowledge of how verbal information is processed in the brain. This work presents a cognitive system, entirely based on a large-scale neural architecture, which was developed to shed light on the procedural knowledge involved in language elaboration. The main component of this system is the central executive, which is a supervising system that coordinates the other components of the working memory. In our model, the central executive is a neural network that takes as input the neural activation states of the short-term memory and yields as output mental actions, which control the flow of information among the working memory components through neural gating mechanisms. The proposed system is capable of learning to communicate through natural language starting from tabula rasa, without any a priori knowledge of the structure of phrases, meaning of words, role of the different classes of words, only by interacting with a human through a text-based interface, using an open-ended incremental learning process. It is able to learn nouns, verbs, adjectives, pronouns and other word classes, and to use them in expressive language. The model was validated on a corpus of 1587 input sentences, based on literature on early language assessment, at the level of about 4-years old child, and produced 521 output sentences, expressing a broad range of language processing functionalities.
The Smart Sampling Kalman Filter with Symmetric Samples
Venue: arXiv cs.SY 2015
Year: 2015

Nonlinear Kalman Filters are powerful and widely-used techniques when trying to estimate the hidden state of a stochastic nonlinear dynamic system. In this paper, we extend the Smart Sampling Kalman Filter (S2KF) with a new point symmetric Gaussian sampling scheme. This not only improves the S2KF's estimation quality, but also reduces the time needed to compute the required optimal Gaussian samples drastically. Moreover, we improve the numerical stability of the sample computation, which allows us to accurately approximate a thousand-dimensional Gaussian distribution using tens of thousands of optimally placed samples. We evaluate the new symmetric S2KF by computing higher-order moments of standard normal distributions and investigate the estimation quality of the S2KF when dealing with symmetric measurement equations. Finally, extended object tracking based on many measurements per time step is considered. This high-dimensional estimation problem shows the advantage of the S2KF being able to use an arbitrary number of samples independent of the state dimension, in contrast to other state-of-the-art sample-based Kalman Filters.
A Practical Parallel Algorithm for Diameter Approximation of Massive Weighted Graphs
Venue: arXiv cs.DC 2015
Year: 2015

We present a space and time efficient practical parallel algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. The core of the algorithm is a weighted graph decomposition strategy generating disjoint clusters of bounded weighted radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; moreover, for important practical classes of graphs, it runs in a number of rounds asymptotically smaller than those required by the natural approximation provided by the state-of-the-art $Δ$-stepping SSSP algorithm, which is its only practical linear-space competitor in the aforementioned computational scenario. We complement our theoretical findings with an extensive experimental analysis on large benchmark graphs, which demonstrates that our algorithm attains substantial improvements on a number of key performance indicators with respect to the aforementioned competitor, while featuring a similar approximation ratio (a small constant less than 1.4, as opposed to the polylogarithmic theoretical bound).
Formalization of closure properties for context-free grammars
Venue: arXiv cs.FL 2015
Year: 2015

Context-free language theory is a well-established area of mathematics, relevant to computer science foundations and technology. This paper presents the preliminary results of an ongoing formalization project using context-free grammars and the Coq proof assistant. The results obtained so far include the representation of context-free grammars, the description of algorithms for some operations on them (union, concatenation and closure) and the proof of related theorems (e.g. the correctness of these algorithms). A brief survey of related works is presented, as well as plans for further development.
Convolutional Dictionary Learning through Tensor Factorization
Venue: arXiv cs.LG 2015
Year: 2015

Tensor methods have emerged as a powerful paradigm for consistent learning of many latent variable models such as topic models, independent component analysis and dictionary learning. Model parameters are estimated via CP decomposition of the observed higher order input moments. However, in many domains, additional invariances such as shift invariances exist, enforced via models such as convolutional dictionary learning. In this paper, we develop novel tensor decomposition algorithms for parameter estimation of convolutional models. Our algorithm is based on the popular alternating least squares method, but with efficient projections onto the space of stacked circulant matrices. Our method is embarrassingly parallel and consists of simple operations such as fast Fourier transforms and matrix multiplications. Our algorithm converges to the dictionary much faster and more accurately compared to the alternating minimization over filters and activation maps.
Isometric sketching of any set via the Restricted Isometry Property
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we show that for the purposes of dimensionality reduction certain class of structured random matrices behave similarly to random Gaussian matrices. This class includes several matrices for which matrix-vector multiply can be computed in log-linear time, providing efficient dimensionality reduction of general sets. In particular, we show that using such matrices any set from high dimensions can be embedded into lower dimensions with near optimal distortion. We obtain our results by connecting dimensionality reduction of any set to dimensionality reduction of sparse vectors via a chaining argument.
DisCoF$^+$: Asynchronous DisCoF with Flexible Decoupling for Cooperative Pathfinding in Distributed Systems
Venue: arXiv cs.RO 2015
Year: 2015

In our prior work, we outlined an approach, named DisCoF, for cooperative pathfinding in distributed systems with limited sensing and communication range. Contrasting to prior works on cooperative pathfinding with completeness guarantees, which often assume the access to global information, DisCoF does not make this assumption. The implication is that at any given time in DisCoF, the robots may not all be aware of each other, which is often the case in distributed systems. As a result, DisCoF represents an inherently online approach since coordination can only be realized in an opportunistic manner between robots that are within each other's sensing and communication range. However, there are a few assumptions made in DisCoF to facilitate a formal analysis, which must be removed to work with distributed multi-robot platforms. In this paper, we present DisCoF$^+$, which extends DisCoF by enabling an asynchronous solution, as well as providing flexible decoupling between robots for performance improvement. We also extend the formal results of DisCoF to DisCoF$^+$. Furthermore, we evaluate our implementation of DisCoF$^+$ and demonstrate a simulation of it running in a distributed multi-robot environment. Finally, we compare DisCoF$^+$ with DisCoF in terms of plan quality and planning performance.
Nonlinear frames and sparse reconstructions in Banach spaces
Venue: arXiv cs.IT 2015
Year: 2015

In the first part of this paper, we consider nonlinear extension of frame theory by introducing bi-Lipschitz maps $F$ between Banach spaces. Our linear model of bi-Lipschitz maps is the analysis operator associated with Hilbert frames, $p$-frames, Banach frames, g-frames and fusion frames. In general Banach space setting, stable algorithm to reconstruct a signal $x$ from its noisy measurement $F(x)+ε$ may not exist. In this paper, we establish exponential convergence of two iterative reconstruction algorithms when $F$ is not too far from some bounded below linear operator with bounded pseudo-inverse, and when $F$ is a well-localized map between two Banach spaces with dense Hilbert subspaces. The crucial step to prove the later conclusion is a novel fixed point theorem for a well-localized map on a Banach space. In the second part of this paper, we consider stable reconstruction of sparse signals in a union ${\bf A}$ of closed linear subspaces of a Hilbert space ${\bf H}$ from their nonlinear measurements. We create an optimization framework called sparse approximation triple $({\bf A}, {\bf M}, {\bf H})$, and show that the minimizer $$x^*={\rm argmin}_{\hat x\in {\mathbf M}\ {\rm with} \ \|F(\hat x)-F(x^0)\|\le ε} \|\hat x\|_{\mathbf M}$$ provides a suboptimal approximation to the original sparse signal $x^0\in {\bf A}$ when the measurement map $F$ has the sparse Riesz property and almost linear property on ${\mathbf A}$. The above two new properties is also discussed in this paper when $F$ is not far away from a linear measurement operator $T$ having the restricted isometry property.
Indefinite waitings in MIRELA systems
Venue: arXiv cs.SE 2015
Year: 2015

MIRELA is a high-level language and a rapid prototyping framework dedicated to systems where virtual and digital objects coexist in the same environment and interact in real time. Its semantics is given in the form of networks of timed automata, which can be checked using symbolic methods. This paper shows how to detect various kinds of indefinite waitings in the components of such systems. The method is experimented using the PRISM model checker.
Distributed Recurrent Neural Forward Models with Synaptic Adaptation for Complex Behaviors of Walking Robots
Venue: arXiv cs.NE 2015
Year: 2015

Walking animals, like stick insects, cockroaches or ants, demonstrate a fascinating range of locomotive abilities and complex behaviors. The locomotive behaviors can consist of a variety of walking patterns along with adaptation that allow the animals to deal with changes in environmental conditions, like uneven terrains, gaps, obstacles etc. Biological study has revealed that such complex behaviors are a result of a combination of biome- chanics and neural mechanism thus representing the true nature of embodied interactions. While the biomechanics helps maintain flexibility and sustain a variety of movements, the neural mechanisms generate movements while making appropriate predictions crucial for achieving adaptation. Such predictions or planning ahead can be achieved by way of in- ternal models that are grounded in the overall behavior of the animal. Inspired by these findings, we present here, an artificial bio-inspired walking system which effectively com- bines biomechanics (in terms of the body and leg structures) with the underlying neural mechanisms. The neural mechanisms consist of 1) central pattern generator based control for generating basic rhythmic patterns and coordinated movements, 2) distributed (at each leg) recurrent neural network based adaptive forward models with efference copies as internal models for sensory predictions and instantaneous state estimations, and 3) searching and elevation control for adapting the movement of an individual leg to deal with different environmental conditions. Using simulations we show that this bio-inspired approach with adaptive internal models allows the walking robot to perform complex loco- motive behaviors as observed in insects, including walking on undulated terrains, crossing large gaps as well as climbing over high obstacles...
Bootstrapping Skills
Venue: arXiv cs.AI 2015
Year: 2015

The monolithic approach to policy representation in Markov Decision Processes (MDPs) looks for a single policy that can be represented as a function from states to actions. For the monolithic approach to succeed (and this is not always possible), a complex feature representation is often necessary since the policy is a complex object that has to prescribe what actions to take all over the state space. This is especially true in large domains with complicated dynamics. It is also computationally inefficient to both learn and plan in MDPs using a complex monolithic approach. We present a different approach where we restrict the policy space to policies that can be represented as combinations of simpler, parameterized skills---a type of temporally extended action, with a simple policy representation. We introduce Learning Skills via Bootstrapping (LSB) that can use a broad family of Reinforcement Learning (RL) algorithms as a "black box" to iteratively learn parametrized skills. Initially, the learned skills are short-sighted but each iteration of the algorithm allows the skills to bootstrap off one another, improving each skill in the process. We prove that this bootstrapping process returns a near-optimal policy. Furthermore, our experiments demonstrate that LSB can solve MDPs that, given the same representational power, could not be solved by a monolithic approach. Thus, planning with learned skills results in better policies without requiring complex policy representations.
Design, Analysis and Evaluation of Control Algorithms for Applications in Smart Grids
Venue: arXiv cs.SY 2015
Year: 2015

In many countries, the currently observable transformation of the power supply system from a centrally controlled system towards a complex "system of systems", comprising lots of autonomously interacting components, leads to a significant amount of research regarding novel control concepts. To facilitate the structured development of such approaches regarding the criticality of the targeted system, the research and development of a distributed control concept is demonstrated by employing an integrated methodology comprising both the Smart Grids Architecture Model framework (SGAM) and the Smart Grid Algorithm Engineering process model (SGAE). Along the way, a taxonomy of evaluation criteria and evaluation methods for such approaches is presented. For the whole paper, the Dynamic Virtual Power Plants business case (DVPP) serves as motivating example.
Random Maxout Features
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we propose and study random maxout features, which are constructed by first projecting the input data onto sets of randomly generated vectors with Gaussian elements, and then outputing the maximum projection value for each set. We show that the resulting random feature map, when used in conjunction with linear models, allows for the locally linear estimation of the function of interest in classification tasks, and for the locally linear embedding of points when used for dimensionality reduction or data visualization. We derive generalization bounds for learning that assess the error in approximating locally linear functions by linear functions in the maxout feature space, and empirically evaluate the efficacy of the approach on the MNIST and TIMIT classification tasks.
Matched Metrics and Channels
Venue: arXiv cs.IT 2015
Year: 2015

The most common decision criteria for decoding are maximum likelihood decoding and nearest neighbor decoding. It is well-known that maximum likelihood decoding coincides with nearest neighbor decoding with respect to the Hamming metric on the binary symmetric channel. In this work we study channels and metrics for which those two criteria do and do not coincide for general codes.
A Novel Hybrid Approach for Cephalometric Landmark Detection
Venue: arXiv cs.CV 2015
Year: 2015

Cephalometric analysis has an important role in dentistry and especially in orthodontics as a treatment planning tool to gauge the size and special relationships of the teeth, jaws and cranium. The first step of using such analyses is localizing some important landmarks known as cephalometric landmarks on craniofacial in x-ray image. The past decade has seen a growing interest in automating this process. In this paper, a novel hybrid approach is proposed for automatic detection of cephalometric landmarks. Here, the landmarks are categorized into three main sets according to their anatomical characteristics and usage in well-known cephalometric analyses. Consequently, to have a reliable and accurate detection system, three methods named edge tracing, weighted template matching, and analysis based estimation are designed, each of which is consistent and well-suited for one category. Edge tracing method is suggested to predict those landmarks which are located on edges. Weighted template matching method is well-suited for landmarks located in an obvious and specific structure which can be extracted or searchable in a given x-ray image. The last but not the least method is named analysis based estimation. This method is based on the fact that in cephalometric analyses the relations between landmarks are used and the locations of some landmarks are never used individually. Therefore the third suggested method has a novelty in estimating the desired relations directly. The effectiveness of the proposed approach is compared with the state of the art methods and the results were promising especially in real world applications.
New Results for Domineering from Combinatorial Game Theory Endgame Databases
Venue: arXiv cs.AI 2015
Year: 2015

We have constructed endgame databases for all single-component positions up to 15 squares for Domineering, filled with exact Combinatorial Game Theory (CGT) values in canonical form. The most important findings are as follows. First, as an extension of Conway's [8] famous Bridge Splitting Theorem for Domineering, we state and prove another theorem, dubbed the Bridge Destroying Theorem for Domineering. Together these two theorems prove very powerful in determining the CGT values of large positions as the sum of the values of smaller fragments, but also to compose larger positions with specified values from smaller fragments. Using the theorems, we then prove that for any dyadic rational number there exist Domineering positions with that value. Second, we investigate Domineering positions with infinitesimal CGT values, in particular ups and downs, tinies and minies, and nimbers. In the databases we find many positions with single or double up and down values, but no ups and downs with higher multitudes. However, we prove that such single-component ups and downs easily can be constructed. Further, we find Domineering positions with 11 different tinies and minies values. For each we give an example. Next, for nimbers we find many Domineering positions with values up to *3. This is surprising, since Drummond-Cole [10] suspected that no *2 and *3 positions in standard Domineering would exist. We show and characterize many *2 and *3 positions. Finally, we give some Domineering positions with values interesting for other reasons. Third, we have investigated the temperature of all positions in our databases. There appears to be exactly one position with temperature 2 (as already found before) and no positions with temperature larger than 2. This supports Berlekamp's conjecture that 2 is the highest possible temperature in Domineering.
Generalizing Permissive-Upgrade in Dynamic Information Flow Analysis
Venue: arXiv cs.CR 2015
Year: 2015

Preventing implicit information flows by dynamic program analysis requires coarse approximations that result in false positives, because a dynamic monitor sees only the executed trace of the program. One widely deployed method is the no-sensitive-upgrade check, which terminates a program whenever a variable's taint is upgraded (made more sensitive) due to a control dependence on tainted data. Although sound, this method is restrictive, e.g., it terminates the program even if the upgraded variable is never used subsequently. To counter this, Austin and Flanagan introduced the permissive-upgrade check, which allows a variable upgrade due to control dependence, but marks the variable "partially-leaked". The program is stopped later if it tries to use the partially-leaked variable. Permissive-upgrade handles the dead-variable assignment problem and remains sound. However, Austin and Flanagan develop permissive-upgrade only for a two-point (low-high) security lattice and indicate a generalization to pointwise products of such lattices. In this paper, we develop a non-trivial and non-obvious generalization of permissive-upgrade to arbitrary lattices. The key difficulty lies in finding a suitable notion of partial leaks that is both sound and permissive and in developing a suitable definition of memory equivalence that allows an inductive proof of soundness.
Towards Benchmarking Scene Background Initialization
Venue: arXiv cs.CV 2015
Year: 2015

Given a set of images of a scene taken at different times, the availability of an initial background model that describes the scene without foreground objects is the prerequisite for a wide range of applications, ranging from video surveillance to computational photography. Even though several methods have been proposed for scene background initialization, the lack of a common groundtruthed dataset and of a common set of metrics makes it difficult to compare their performance. To move first steps towards an easy and fair comparison of these methods, we assembled a dataset of sequences frequently adopted for background initialization, selected or created ground truths for quantitative evaluation through a selected suite of metrics, and compared results obtained by some existing methods, making all the material publicly available.