OpenRaiser/Intern-Atlas huggingface dataset:
Joint Energy-based Detection and Classificationon of Multilingual Text Lines
Venue: arXiv cs.CV 2014
Year: 2014

This paper proposes a new hierarchical MDL-based model for a joint detection and classification of multilingual text lines in im- ages taken by hand-held cameras. The majority of related text detec- tion methods assume alphabet-based writing in a single language, e.g. in Latin. They use simple clustering heuristics specific to such texts: prox- imity between letters within one line, larger distance between separate lines, etc. We are interested in a significantly more ambiguous problem where images combine alphabet and logographic characters from multiple languages and typographic rules vary a lot (e.g. English, Korean, and Chinese). Complexity of detecting and classifying text lines in multiple languages calls for a more principled approach based on information- theoretic principles. Our new MDL model includes data costs combining geometric errors with classification likelihoods and a hierarchical sparsity term based on label costs. This energy model can be efficiently minimized by fusion moves. We demonstrate robustness of the proposed algorithm on a large new database of multilingual text images collected in the pub- lic transit system of Seoul.
Write-and-f-array: implementation and an application
Venue: arXiv cs.DC 2014
Year: 2014

We introduce a new shared memory object: the write-and-f-array, provide its wait-free implementation and use it to construct an improved wait-free implementation of the fetch-and-add object. The write-and-f-array generalizes single-writer write-and-snapshot object in a similar way that the f-array generalizes the multi-writer snapshot object. More specifically, a write-and-f-array is parameterized by an associative operator $f$ and is conceptually an array with two atomic operations: - write-and-f modifies a single array's element and returns the result of applying $f$ to all the elements, - read returns the result of applying $f$ to all the array's elements. We provide a wait-free implementation of an $N$-element write-and-f-array with $O(N \log N)$ memory complexity, $O(\log^3 N)$ step complexity of the write-and-f operation and $O(1)$ step complexity of the read operation. The implementation uses CAS objects and requires their size to be $Ω(\log M)$, where $M$ is the total number of write-and-f operations executed. We also show, how it can be modified to achieve $O(\log^2 N)$ step complexity of write-and-f, while increasing the memory complexity to $O(N \log^2 N)$. The write-and-f-array can be applied to create a fetch-and-add object for $P$ processes with $O(P \log P)$ memory complexity and $O(\log^3 P)$ step complexity of the fetch-and-add operation. This is the first implementation of fetch-and-add with polylogarithmic step complexity and subquadratic memory complexity that can be implemented without CAS or LL/SC objects of unrealistic size.
Matching in the Pi-Calculus (Technical Report)
Venue: arXiv cs.LO 2014
Year: 2014

We study whether, in the pi-calculus, the match prefix---a conditional operator testing two names for (syntactic) equality---is expressible via the other operators. Previously, Carbone and Maffeis proved that matching is not expressible this way under rather strong requirements (preservation and reflection of observables). Later on, Gorla developed a by now widely-tested set of criteria for encodings that allows much more freedom (e.g. instead of direct translations of observables it allows comparison of calculi with respect to reachability of successful states). In this paper, we offer a considerably stronger separation result on the non-expressibility of matching using only Gorla's relaxed requirements.
Novel and Tuneable Method for Skin Detection Based on Hybrid Color Space and Color Statistical Features
Venue: arXiv cs.CV 2014
Year: 2014

Skin detection is one of the most important and primary stages in some of image processing applications such as face detection and human tracking. So far, many approaches are proposed to done this case. Near all of these methods have tried to find best match intensity distribution with skin pixels based on popular color spaces such as RGB, CMYK or YCbCr. Results show these methods cannot provide an accurate approach for every kinds of skin. In this paper, an approach is proposed to solve this problem using statistical features technique. This approach is including two stages. In the first one, from pure skin statistical features were extracted and at the second stage, the skin pixels are detected using HSV and YCbCr color spaces. In the result part, the proposed approach is applied on FEI database and the accuracy rate reached 99.25 + 0.2. Further proposed method is applied on complex background database and accuracy rate obtained 95.40+0.31%. The proposed approach can be used for all kinds of skin using train stage which is the main advantages of it. Low noise sensitivity and low computational complexity are some of other advantages.
Trainable and Dynamic Computing: Error Backpropagation through Physical Media
Venue: arXiv cs.NE 2014
Year: 2014

Machine learning algorithms, and more in particular neural networks, arguably experience a revolution in terms of performance. Currently, the best systems we have for speech recognition, computer vision and similar problems are based on neural networks, trained using the half-century old backpropagation algorithm. Despite the fact that neural networks are a form of analog computers, they are still implemented digitally for reasons of convenience and availability. In this paper we demonstrate how we can design physical linear dynamic systems with non-linear feedback as a generic platform for dynamic, neuro-inspired analog computing. We show that a crucial advantage of this setup is that the error backpropagation can be performed physically as well, which greatly speeds up the optimisation process. As we show in this paper, using one experimentally validated and one conceptual example, such systems may be the key to providing a relatively straightforward mechanism for constructing highly scalable, fully dynamic analog computers.
Efficient Multi Secret Sharing with Generalized Access Structures
Venue: arXiv cs.CR 2014
Year: 2014

Multi-secret sharing is an extension of secret sharing technique where several secrets are shared between the participants, each according to a specified access structure. The secrets can be reconstructed according to the access structure by participants using their private shares.Each participant has to hold a single share, additional information are made available in a public bulletin board.The scheme is computationally efficient and also each participant can verify the shares of the other participants and also the reconstructed secret.The scheme does not need any secure channel also.
On Distributed Graph Coloring with Iterative Recoloring
Venue: arXiv cs.DC 2014
Year: 2014

Identifying the sets of operations that can be executed simultaneously is an important problem appearing in many parallel applications. By modeling the operations and their interactions as a graph, one can identify the independent operations by solving a graph coloring problem. Many efficient sequential algorithms are known for this NP-Complete problem, but they are typically unsuitable when the operations and their interactions are distributed in the memory of large parallel computers. On top of an existing distributed-memory graph coloring algorithm, we investigate two compatible techniques in this paper for fast and scalable distributed-memory graph coloring. First, we introduce an improvement for the distributed post-processing operation, called recoloring, which drastically improves the number of colors. We propose a novel and efficient communication scheme for recoloring which enables it to scale gracefully. Recoloring must be seeded with an existing coloring of the graph. Our second contribution is to introduce a randomized color selection strategy for initial coloring which quickly produces solutions of modest quality. We extensively evaluate the impact of our new techniques on existing distributed algorithms and show the time-quality tradeoffs. We show that combining an initial randomized coloring with multiple recoloring iterations yields better quality solutions with the smaller runtime at large scale.
Quantum signaling game
Venue: arXiv cs.GT 2014
Year: 2014

We present a quantum approach to a signaling game; a special kind of extensive games of incomplete information. Our model is based on quantum schemes for games in strategic form where players perform unitary operators on their own qubits of some fixed initial state and the payoff function is given by a measurement on the resulting final state. We show that the quantum game induced by our scheme coincides with a signaling game as a special case and outputs nonclassical results in general. As an example, we consider a quantum extension of the signaling game in which the chance move is a three-parameter unitary operator whereas the players' actions are equivalent to classical ones. In this case, we study the game in terms of Nash equilibria and refine the pure Nash equilibria adapting to the quantum game the notion of a weak perfect Bayesian equilibrium.
Measuring Prestige in Online Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

We study the locally-defined social capital metric of Palasek (2013) for determining individuals' prestige within an online social network. From it we derive an equivalent global measure by considering random walks over the network itself. This result inspires a novel expression quantifying the strategic desirability of a potential social connection. We show in silico that ideal social neighbors tend to satisfy a "big fish in a small pond" criterion and that the distribution of neighbor-desirability throughout a network is governed by anti-homophily.
Interpretable Low-Rank Document Representations with Label-Dependent Sparsity Patterns
Venue: arXiv cs.CL 2014
Year: 2014

In context of document classification, where in a corpus of documents their label tags are readily known, an opportunity lies in utilizing label information to learn document representation spaces with better discriminative properties. To this end, in this paper application of a Variational Bayesian Supervised Nonnegative Matrix Factorization (supervised vbNMF) with label-driven sparsity structure of coefficients is proposed for learning of discriminative nonsubtractive latent semantic components occuring in TF-IDF document representations. Constraints are such that the components pursued are made to be frequently occuring in a small set of labels only, making it possible to yield document representations with distinctive label-specific sparse activation patterns. A simple measure of quality of this kind of sparsity structure, dubbed inter-label sparsity, is introduced and experimentally brought into tight connection with classification performance. Representing a great practical convenience, inter-label sparsity is shown to be easily controlled in supervised vbNMF by a single parameter.
A Key Pre-Distribution Scheme based on Multiple Block Codes for Wireless Sensor Networks
Venue: arXiv cs.CR 2014
Year: 2014

A key pre-distribution scheme (KPS) based on multiple codewords of block codes is presented for wireless sensor networks. The connectivity and security of the proposed KPS, quantified in terms of probabilities of sharing common keys for communications of pairs of nodes and their resilience against colluding nodes, are analytically assessed. The analysis is applicable to both linear and nonlinear codes and is simplified in the case of maximum distance separable codes. It is shown that the multiplicity of codes significantly enhances the security and connectivity of KPS at the cost of a modest increase of the nodes storage. Numerical and simulation results are provided, which sheds light on the effect of system parameters of the proposed KPS on its complexity and performance. Specifically, it is shown that the probability of resilience of secure pairs against collusion of other nodes only reduces slowly as the number of colluding nodes increase.
A Parallel Branch and Bound Algorithm for the Maximum Labelled Clique Problem
Venue: arXiv cs.DS 2014
Year: 2014

The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.
Sampled-Data H-infinity Design of Coupling Wave Cancelers in Single-Frequency Full-Duplex Relay Stations
Venue: arXiv cs.SY 2014
Year: 2014

In this article, we propose sampled-data H-infinity design of digital filters that cancel the continuous-time effect of coupling waves in a single-frequency full-duplex relay station. In this study, we model a relay station as a continuous-time system while conventional researches treat it as a discrete-time system. For a continuous-time model, we propose digital feedforward and feedback cancelers based on the sampled-data control theory to cancel coupling waves taking intersample behavior into account. Simulation results are shown to illustrate the effectiveness of the proposed method.
On Joint Source-Channel Coding for Correlated Sources Over Multiple-Access Relay Channels
Venue: arXiv cs.IT 2014
Year: 2014

We study the transmission of correlated sources over discrete memoryless (DM) multiple-access-relay channels (MARCs), in which both the relay and the destination have access to side information arbitrarily correlated with the sources. As the optimal transmission scheme is an open problem, in this work we propose a new joint source-channel coding scheme based on a novel combination of the correlation preserving mapping (CPM) technique with Slepian-Wolf (SW) source coding, and obtain the corresponding sufficient conditions. The proposed coding scheme is based on the decode-and-forward strategy, and utilizes CPM for encoding information simultaneously to the relay and the destination, whereas the cooperation information from the relay is encoded via SW source coding. It is shown that there are cases in which the new scheme strictly outperforms the schemes available in the literature. This is the first instance of a source-channel code that uses CPM for encoding information to two different nodes (relay and destination). In addition to sufficient conditions, we present three different sets of single-letter necessary conditions for reliable transmission of correlated sources over DM MARCs. The newly derived conditions are shown to be at least as tight as the previously known necessary conditions.
On Quantizer Design for Distributed Bayesian Estimation in Sensor Networks
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of distributed estimation under the Bayesian criterion and explore the design of optimal quantizers in such a system. We show that, for a conditionally unbiased and efficient estimator at the fusion center and when local observations have identical distributions, it is optimal to partition the local sensors into groups, with all sensors within a group using the same quantization rule. When all the sensors use identical number of decision regions, use of identical quantizers at the sensors is optimal. When the network is constrained by the capacity of the wireless multiple access channel over which the sensors transmit their quantized observations, we show that binary quantizers at the local sensors are optimal under certain conditions. Based on these observations, we address the location parameter estimation problem and present our optimal quantizer design approach. We also derive the performance limit for distributed location parameter estimation under the Bayesian criterion and find the conditions when the widely used threshold quantizer achieves this limit. We corroborate this result using simulations. We then relax the assumption of conditionally independent observations and derive the optimality conditions of quantizers for conditionally dependent observations. Using counter-examples, we also show that the previous results do not hold in this setting of dependent observations and, therefore, identical quantizers are not optimal.
Boundary value problems in consensus networks
Venue: arXiv cs.SI 2014
Year: 2014

This paper studies the effect of boundary value conditions on consensus networks. Consider a network where some nodes keep their estimates constant while other nodes average their estimates with that of their neighbors. We analyze such networks and show that in contrast to standard consensus networks, the network estimate converges to a general harmonic function on the graph. Furthermore, the final value depends only on the value at the boundary nodes. This has important implications in consensus networks -- for example, we show that consensus networks are extremely sensitive to the existence of a single malicious node or consistent errors in a single node. We also discuss applications of this result in social and sensor networks. We investigate the existence of boundary nodes in human social networks via an experimental study involving human subjects. Finally, the paper is concluded with the numerical studies of the boundary value problems in consensus networks.
Defining Relative Likelihood in Partially-Ordered Preferential Structures
Venue: arXiv cs.AI 2014
Year: 2014

Starting with a likelihood or preference order on worlds, we extend it to a likelihood ordering on sets of worlds in a natural way, and examine the resulting logic. Lewis (1973) earlier considered such a notion of relative likelihood in the context of studying counterfactuals, but he assumed a total preference order on worlds. Complications arise when examining partial orders that are not present for total orders. There are subtleties involving the exact approach to lifting the order on worlds to an order on sets of worlds. In addition, the axiomatization of the logic of relative likelihood in the case of partial orders gives insight into the connection between relative likelihood and default reasoning.
Updating Probabilities
Venue: arXiv cs.AI 2014
Year: 2014

As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a ``naive space', which does not take into account the protocol used, can often lead to counterintuitive results. Here we examine why. A criterion known as CAR (coarsening at random) in the statistical literature characterizes when ``naive' conditioning in a naive space works. We show that the CAR condition holds rather infrequently. We then consider more generalized notions of update such as Jeffrey conditioning and minimizing relative entropy (MRE). We give a generalization of the CAR condition that characterizes when Jeffrey conditioning leads to appropriate answers, but show that there are no such conditions for MRE. This generalizes and interconnects previous results obtained in the literature on CAR and MRE.
Reasoning about Expectation
Venue: arXiv cs.AI 2014
Year: 2014

Expectation is a central notion in probability theory. The notion of expectation also makes sense for other notions of uncertainty. We introduce a propositional logic for reasoning about expectation, where the semantics depends on the underlying representation of uncertainty. We give sound and complete axiomatizations for the logic in the case that the underlying representation is (a) probability, (b) sets of probability measures, (c) belief functions, and (d) possibility measures. We show that this logic is more expressive than the corresponding logic for reasoning about likelihood in the case of sets of probability measures, but equi-expressive in the case of probability, belief, and possibility. Finally, we show that satisfiability for these logics is NP-complete, no harder than satisfiability for propositional logic.
When Augmented Reality Meets Big Data
Venue: arXiv cs.DB 2014
Year: 2014

With computing and sensing woven into the fabric of everyday life, we live in an era where we are awash in a flood of data from which we can gain rich insights. Augmented reality (AR) is able to collect and help analyze the growing torrent of data about user engagement metrics within our personal mobile and wearable devices. This enables us to blend information from our senses and the digitalized world in a myriad of ways that was not possible before. AR and big data have a logical maturity that inevitably converge them. The tread of harnessing AR and big data to breed new interesting applications is starting to have a tangible presence. In this paper, we explore the potential to capture value from the marriage between AR and big data technologies, following with several challenges that must be addressed to fully realize this potential.
Faster and Simpler Sketches of Valuation Functions
Venue: arXiv cs.GT 2014
Year: 2014

We present fast algorithms for sketching valuation functions. Let $N$ ($|N|=n$) be some ground set and $v:2^N\rightarrow \mathbb R$ be a function. We say that $\tilde v:2^N\rightarrow \mathbb R$ is an $α$-sketch of $v$ if for every set $S$ we have that $\frac {v(S)} α \leq \tilde v(S) \leq v(S)$ and $\tilde v$ can be described in $poly(n)$ bits. Goemans et al. [SODA'09] showed that if $v$ is submodular then there exists an $\tilde O(\sqrt n)$-sketch that can be constructed using polynomially many value queries (this is the best possible, as Balcan and Harvey [STOC'11] show that no submodular function admit an $n^{\frac 1 3 - ε}$-sketch). Based on their work, Balcan et al. [COLT'12] and Badanidiyuru et al. [SODA'12] show that if $v$ is subadditive then there exists an $\tilde O(\sqrt n)$-sketch that can be constructed using polynomially many demand queries. All previous sketches are based on complicated geometric constructions. The first step in their constructions is proving the existence of a good sketch by finding an ellipsoid that ``approximates'' $v$ well (this is done by applying John's theorem to ensure the existence of an ellipsoid that is ``close'' to the polymatroid that is associated with $v$). The second step is showing this ellipsoid can be found efficiently, and this is done by repeatedly solving a certain convex program to obtain better approximations of John's ellipsoid. In this paper, we give a much simpler, non-geometric proof for the existence of good sketches, and utilize the proof to obtain much faster algorithms that match the previously obtained approximation bounds. Specifically, we provide an algorithm that finds $\tilde O(\sqrt n)$-sketch of a submodular function with only $\tilde O(n^\frac{3}{2})$ value queries, and an algorithm that finds $\tilde O(\sqrt n)$-sketch of a subadditive function with $O(n)$ demand and value queries.
Algorithms, Initializations, and Convergence for the Nonnegative Matrix Factorization
Venue: arXiv cs.NA 2014
Year: 2014

It is well known that good initializations can improve the speed and accuracy of the solutions of many nonnegative matrix factorization (NMF) algorithms. Many NMF algorithms are sensitive with respect to the initialization of W or H or both. This is especially true of algorithms of the alternating least squares (ALS) type, including the two new ALS algorithms that we present in this paper. We compare the results of six initialization procedures (two standard and four new) on our ALS algorithms. Lastly, we discuss the practical issue of choosing an appropriate convergence criterion.