OpenRaiser/Intern-Atlas huggingface dataset:
Reading Text in the Wild with Convolutional Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

In this work we present an end-to-end system for text spotting -- localising and recognising text in natural scene images -- and text based image retrieval. This system is based on a region proposal mechanism for detection and deep convolutional neural networks for recognition. Our pipeline uses a novel combination of complementary proposal generation techniques to ensure high recall, and a fast subsequent filtering stage for improving precision. For the recognition and ranking of proposals, we train very large convolutional neural networks to perform word recognition on the whole proposal region at the same time, departing from the character classifier based systems of the past. These networks are trained solely on data produced by a synthetic text generation engine, requiring no human labelled data. Analysing the stages of our pipeline, we show state-of-the-art performance throughout. We perform rigorous experiments across a number of standard end-to-end text spotting benchmarks and text-based image retrieval datasets, showing a large improvement over all previous methods. Finally, we demonstrate a real-world application of our text spotting system to allow thousands of hours of news footage to be instantly searchable via a text query.
Decomposition of Big Tensors With Low Multilinear Rank
Venue: arXiv cs.NA 2014
Year: 2014

Tensor decompositions are promising tools for big data analytics as they bring multiple modes and aspects of data to a unified framework, which allows us to discover complex internal structures and correlations of data. Unfortunately most existing approaches are not designed to meet the major challenges posed by big data analytics. This paper attempts to improve the scalability of tensor decompositions and provides two contributions: A flexible and fast algorithm for the CP decomposition (FFCP) of tensors based on their Tucker compression; A distributed randomized Tucker decomposition approach for arbitrarily big tensors but with relatively low multilinear rank. These two algorithms can deal with huge tensors, even if they are dense. Extensive simulations provide empirical evidence of the validity and efficiency of the proposed algorithms.
Document clustering using graph based document representation with constraints
Venue: arXiv cs.IR 2014
Year: 2014

Document clustering is an unsupervised approach in which a large collection of documents (corpus) is subdivided into smaller, meaningful, identifiable, and verifiable sub-groups (clusters). Meaningful representation of documents and implicitly identifying the patterns, on which this separation is performed, is the challenging part of document clustering. We have proposed a document clustering technique using graph based document representation with constraints. A graph data structure can easily capture the non-linear relationships of nodes, document contains various feature terms that can be non-linearly connected hence a graph can easily represents this information. Constrains, are explicit conditions for document clustering where background knowledge is use to set the direction for Linking or Not-Linking a set of documents for a target clusters, thus guiding the clustering process. We deemed clustering is an ill-define problem, there can be many clustering results. Background knowledge can be used to drive the clustering algorithm in the right direction. We have proposed three different types of constraints, Instance level, corpus level and cluster level constraints. A new algorithm Constrained HAC is also proposed which will incorporate Instance level constraints as prior knowledge; it will guide the clustering process leading to better results. Extensive set of experiments have been performed on both synthetic and standard document clustering datasets, results are compared on standard clustering measures like: purity, entropy and F-measure. Results clearly establish that our proposed approach leads to improvement in cluster quality.
Opportunistic Routing for the Vehicular Energy Network
Venue: arXiv cs.SY 2014
Year: 2014

Vehicular energy network (VEN) is a vehicular network which can transport energy over a large geographical area by means of electric vehicles (EVs). In the near future, an abundance of EVs, plentiful generation of the renewables, and mature wireless energy transfer and vehicular communication technologies will expedite the realization of VEN. To transmit energy from a source to a destination, we need to establish energy paths, which are composed of segments of vehicular routes, while satisfying various design objectives. In this paper, we develop a method to construct all energy paths for a particular energy source-destination pair, followed by some analytical results of the method. We describe how to utilize the energy paths to develop optimization models for different design goals and propose two solutions. We also develop a heuristic for the power loss minimization problem. We compare the performance of the three solution methods with artificial and real-world traffic networks and provide a comprehensive comparison in terms of solution quality, computation time, solvable problem size, and applicability. This paper lays the foundations of VEN routing.
Emergent Behaviors over Signed Random Dynamical Networks: Relative-State-Flipping Model
Venue: arXiv cs.SI 2014
Year: 2014

We study asymptotic dynamical patterns that emerge among a set of nodes interacting in a dynamically evolving signed random network, where positive links carry out standard consensus and negative links induce relative-state flipping. A sequence of deterministic signed graphs define potential node interactions that take place independently. Each node receives a positive recommendation consistent with the standard consensus algorithm from its positive neighbors, and a negative recommendation defined by relative-state flipping from its negative neighbors. After receiving these recommendations, each node puts a deterministic weight to each recommendation, and then encodes these weighted recommendations in its state update through stochastic attentions defined by two Bernoulli random variables. We establish a number of conditions regarding almost sure convergence and divergence of the node states. We also propose a condition for almost sure state clustering for essentially weakly balanced graphs, with the help of several martingale convergence lemmas. Some fundamental differences on the impact of the deterministic weights and stochastic attentions to the node state evolution are highlighted between the current relative-state-flipping model and the state-flipping model considered in Altafini 2013 and Shi et al. 2014.
Statistical Modeling and Probabilistic Analysis of Cellular Networks with Determinantal Point Processes
Venue: arXiv cs.IT 2014
Year: 2014

Although the Poisson point process (PPP) has been widely used to model base station (BS) locations in cellular networks, it is an idealized model that neglects the spatial correlation among BSs. The present paper proposes the use of determinantal point process (DPP) to take into account these correlations; in particular the repulsiveness among macro base station locations. DPPs are demonstrated to be analytically tractable by leveraging several unique computational properties. Specifically, we show that the empty space function, the nearest neighbor function, the mean interference and the signal-to-interference ratio (SIR) distribution have explicit analytical representations and can be numerically evaluated for cellular networks with DPP configured BSs. In addition, the modeling accuracy of DPPs is investigated by fitting three DPP models to real BS location data sets from two major U.S. cities. Using hypothesis testing for various performance metrics of interest, we show that these fitted DPPs are significantly more accurate than popular choices such as the PPP and the perturbed hexagonal grid model.
Consistent optimization of AMS by logistic loss minimization
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we theoretically justify an approach popular among participants of the Higgs Boson Machine Learning Challenge to optimize approximate median significance (AMS). The approach is based on the following two-stage procedure. First, a real-valued function is learned by minimizing a surrogate loss for binary classification, such as logistic loss, on the training sample. Then, a threshold is tuned on a separate validation sample, by direct optimization of AMS. We show that the regret of the resulting (thresholded) classifier measured with respect to the squared AMS, is upperbounded by the regret of the underlying real-valued function measured with respect to the logistic loss. Hence, we prove that minimizing logistic surrogate is a consistent method of optimizing AMS.
Chases and Escapes, and Optimization Problems
Venue: arXiv cs.AI 2014
Year: 2014

We propose a new approach for solving combinatorial optimization problem by utilizing the mechanism of chases and escapes, which has a long history in mathematics. In addition to the well-used steepest descent and neighboring search, we perform a chase and escape game on the "landscape" of the cost function. We have created a concrete algorithm for the Traveling Salesman Problem. Our preliminary test indicates a possibility that this new fusion of chases and escapes problem into combinatorial optimization search is fruitful.
Multipath forwarding strategies in Information Centric Networks with AIMD congestion control
Venue: arXiv cs.NI 2014
Year: 2014

A content can be replicated in more than one node, in Information Centric Networks (ICNs). Thus, more than one path can be followed to reach the same content, and it is necessary to decide the interface(s) to be selected in every network node to forward content requests towards such multiple content containers. A multipath forwarding strategy defines how to perform this choice. In this paper we propose a general analytical model to evaluate the effect of multipath forwarding strategies on the performance of an ICN content delivery, whose congestion control follows a receiver driven, loss-based AIMD scheme. We use the model to understand the behavior of ICN multipath forwarding strategies proposed in the literature so far, and to devise and evaluate a novel strategy. The considered multipath forwarding strategies are also evaluated in a realistic network setting, by using the PlanetLab testbed.
HotBox: Testing Temperature Effects in Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

Low-power wireless networks, especially in outside deployments, are exposed to a wide range of temperatures. The detrimental effect of high temperatures on communication quality is well known. To investigate these influences under controlled conditions, we present HotBox, a solution with the following properties: (1) It allows exposition of sensor motes to a wide range of temperatures with a high degree of accuracy. (2) It supports specifying exact spatial orientation of motes which, if not ensured, interferes with repeatable experiment setups. (3) It is reasonably easy to assemble by following the information (code, PCB schematics, hardware list and crafting instructions) available online, facilitating further use of the platforms by other researchers. After presenting HotBox, we will show its performance and prove its feasibility as evaluation platform by conducting several experiments. These experiments additionally provide further insight into the influence of temperature effects on communication performance in low-power wireless networks.
School of the future: smartphones as a laboratory in pocket of each student
Venue: arXiv cs.CY 2014
Year: 2014

The idea to unite student smartphones in a scalable network and use the network to collect data of personal environmental sensors and health indicators is proposed. Access to the sensors, which are available in every smartphone will provide the appropriate software. Such a monitoring at the global level would reveal the impact of the electromagnetic radiation, environmental pollution and weather factors on human health. Participation in these measurements increases the educational and social activity of students. [in Ukrainian]
Perturbed Datasets Methods for Hypothesis Testing and Structure of Corresponding Confidence Sets
Venue: arXiv cs.SY 2014
Year: 2014

Hypothesis testing methods that do not rely on exact distribution assumptions have been emerging lately. The method of sign-perturbed sums (SPS) is capable of characterizing confidence regions with exact confidence levels for linear regression and linear dynamical systems parameter estimation problems if the noise distribution is symmetric. This paper describes a general family of hypothesis testing methods that have an exact user chosen confidence level based on finite sample count and without relying on an assumed noise distribution. It is shown that the SPS method belongs to this family and we provide another hypothesis test for the case where the symmetry assumption is replaced with exchangeability. In the case of linear regression problems it is shown that the confidence regions are connected, bounded and possibly non-convex sets in both cases. To highlight the importance of understanding the structure of confidence regions corresponding to such hypothesis tests it is shown that confidence sets for linear dynamical systems parameter estimates generated using the SPS method can have non-connected parts, which have far reaching consequences.
Rediscovering the Alphabet - On the Innate Universal Grammar
Venue: arXiv cs.CL 2014
Year: 2014

Universal Grammar (UG) theory has been one of the most important research topics in linguistics since introduced five decades ago. UG specifies the restricted set of languages learnable by human brain, and thus, many researchers believe in its biological roots. Numerous empirical studies of neurobiological and cognitive functions of the human brain, and of many natural languages, have been conducted to unveil some aspects of UG. This, however, resulted in different and sometimes contradicting theories that do not indicate a universally unique grammar. In this research, we tackle the UG problem from an entirely different perspective. We search for the Unique Universal Grammar (UUG) that facilitates communication and knowledge transfer, the sole purpose of a language. We formulate this UG and show that it is unique, intrinsic, and cosmic, rather than humanistic. Initial analysis on a widespread natural language already showed some positive results.
Bounded Treewidth and Space-Efficient Linear Algebra
Venue: arXiv cs.CC 2014
Year: 2014

Motivated by a recent result of Elberfeld, Jakoby and Tantau showing that $\mathsf{MSO}$ properties are Logspace computable on graphs of bounded tree-width, we consider the complexity of computing the determinant of the adjacency matrix of a bounded tree-width graph and as our main result prove that it is in Logspace. It is important to notice that the determinant is neither an $\mathsf{MSO}$-property nor counts the number of solutions of an $\mathsf{MSO}$-predicate. This technique yields Logspace algorithms for counting the number of spanning arborescences and directed Euler tours in bounded tree-width digraphs. We demonstrate some linear algebraic applications of the determinant algorithm by describing Logspace procedures for the characteristic polynomial, the powers of a weighted bounded tree-width graph and feasibility of a system of linear equations where the underlying bipartite graph has bounded tree-width. Finally, we complement our upper bounds by proving $\mathsf{L}$-hardness of the problems of computing the determinant, and of powering a bounded tree-width matrix. We also show the $\mathsf{GapL}$-hardness of Iterated Matrix Multiplication where each matrix has bounded tree-width.
Patterns of Text Reuse in a Scientific Corpus
Venue: arXiv cs.DL 2014
Year: 2014

We consider the incidence of text "reuse" by researchers, via a systematic pairwise comparison of the text content of all articles deposited to arXiv.org from 1991--2012. We measure the global frequencies of three classes of text reuse, and measure how chronic text reuse is distributed among authors in the dataset. We infer a baseline for accepted practice, perhaps surprisingly permissive compared with other societal contexts, and a clearly delineated set of aberrant authors. We find a negative correlation between the amount of reused text in an article and its influence, as measured by subsequent citations. Finally, we consider the distribution of countries of origin of articles containing large amounts of reused text.
Error Floor Analysis of Coded Slotted ALOHA over Packet Erasure Channels
Venue: arXiv cs.IT 2014
Year: 2014

We present a framework for the analysis of the error floor of coded slotted ALOHA (CSA) for finite frame lengths over the packet erasure channel. The error floor is caused by stopping sets in the corresponding bipartite graph, whose enumeration is, in general, not a trivial problem. We therefore identify the most dominant stopping sets for the distributions of practical interest. The derived analytical expressions allow us to accurately predict the error floor at low to moderate channel loads and characterize the unequal error protection inherent in CSA.
Semantic Enhancement of Lecture Material
Venue: arXiv cs.CY 2014
Year: 2014

Today's lectures are often talks following a straight line of slides. In many lectures the process of content teaching is not as efficient as it could be. Technologies, such as smart-phones and wireless communication, enable a new level of interaction between lecturer, content and audience. We describe how current lecture material can be semantically enhanced, to interactively assist the audience during and after a lecture.
The Influence of the Generator's License on Generated Artifacts
Venue: arXiv cs.SE 2014
Year: 2014

Open sourcing modelling tools and generators becomes more and more important as open source software as a whole becomes more important. We evaluate the impact open source licenses of code generators have on the intellectual property (IP) of generated artifacts comparing the most common open source licenses by categories found in literature. Restrictively licensed generators do have effects on the IP and therefore on the usability of the artifacts they produce. We then how how this effects can be shaped to the needs of the licensor and the licensee.
On the number of active links in random wireless networks
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents results on the typical number of simultaneous point-to-point transmissions above a minimum rate that can be sustained in a network with $n$ transmitter-receiver node pairs when all transmitting nodes can potentially interfere with all receivers. In particular we obtain a scaling law when the fading gains are independent Rayleigh distributed random variables and the transmitters over different realizations are located at the points of a stationary Poisson field in the plane. We show that asymptotically with probability approaching 1, the number of simultaneous transmissions (links that can transmit at greater than a minimum rate) is of the order of $O(n^{\frac{1}{4}})$. These asymptotic results are confirmed from simulations.
Distortion-transmission trade-off in real-time transmission of Markov sources
Venue: arXiv cs.IT 2014
Year: 2014

The problem of optimal real-time transmission of a Markov source under constraints on the expected number of transmissions is considered, both for the discounted and long term average cases. This setup is motivated by applications where transmission is sporadic and the cost of switching on the radio and transmitting is significantly more important than the size of the transmitted data packet. For this model, we characterize the distortion-transmission function, i.e., the minimum expected distortion that can be achieved when the expected number of transmissions is less than or equal to a particular value. In particular, we show that the distortion-transmission function is a piecewise linear, convex, and decreasing function. We also give an explicit characterization of each vertex of the piecewise linear function. To prove the results, the optimization problem is cast as a decentralized constrained stochastic control problem. We first consider the Lagrange relaxation of the constrained problem and identify the structure of optimal transmission and estimation strategies. In particular, we show that the optimal transmission is of a threshold type. Using these structural results, we obtain dynamic programs for the Lagrange relaxations. We identify the performance of an arbitrary threshold-type transmission strategy and use the idea of calibration from multi-armed bandits to determine the optimal transmission strategy for the Lagrange relaxation. Finally, we show that the optimal strategy for the constrained setup is a randomized strategy that randomizes between two deterministic strategies that differ only at one state. By evaluating the performance of these strategies, we determine the shape of the distortion-transmission function. These results are illustrated using an example of transmitting a birth-death Markov source.
A Biological-Realtime Neuromorphic System in 28 nm CMOS using Low-Leakage Switched Capacitor Circuits
Venue: arXiv cs.ET 2014
Year: 2014

A switched-capacitor (SC) neuromorphic system for closed-loop neural coupling in 28 nm CMOS is presented, occupying 600 um by 600 um. It offers 128 input channels (i.e. presynaptic terminals), 8192 synapses and 64 output channels (i.e. neurons). Biologically realistic neuron and synapse dynam- ics are achieved via a faithful translation of the behavioural equations to SC circuits. As leakage currents significantly affect circuit behaviour at this technology node, dedicated compensation techniques are employed to achieve biological-realtime operation, with faithful reproduction of time constants of several 100 ms at room temperature. Power draw of the overall system is 1.9 mW.
Switched-Capacitor Realization of Presynaptic Short-Term-Plasticity and Stop-Learning Synapses in 28 nm CMOS
Venue: arXiv cs.ET 2014
Year: 2014

Synaptic dynamics, such as long- and short-term plasticity, play an important role in the complexity and biological realism achievable when running neural networks on a neuromorphic IC. For example, they endow the IC with an ability to adapt and learn from its environment. In order to achieve the mil- lisecond to second time constants required for these synaptic dynamics, analog subthreshold circuits are usually employed. However, due to process variation and leakage problems, it is almost impossible to port these types of circuits to modern sub-100nm technologies. In contrast, we present a neuromor- phic system in a 28 nm CMOS process that employs switched capacitor (SC) circuits to implement 128 short term plasticity presynapses as well as 8192 stop-learning synapses. The neuromorphic system consumes an area of 0.36 mm2 and runs at a power consumption of 1.9 mW. The circuit makes use of a technique for minimizing leakage effects allowing for real-time operation with time constants up to sev- eral seconds. Since we rely on SC techniques for all calculations, the system is composed of only generic mixed-signal building blocks. These generic building blocks make the system easy to port between technologies and the large digital circuit part inherent in an SC system benefits fully from technology scaling.
Generalised Entropy MDPs and Minimax Regret
Venue: arXiv cs.LG 2014
Year: 2014

Bayesian methods suffer from the problem of how to specify prior beliefs. One interesting idea is to consider worst-case priors. This requires solving a stochastic zero-sum game. In this paper, we extend well-known results from bandit theory in order to discover minimax-Bayes policies and discuss when they are practical.