OpenRaiser/Intern-Atlas huggingface dataset:
On constant factor approximation for earth mover distance over doubling metrics
Venue: arXiv cs.DS 2010
Year: 2010

Given a metric space $(X,d_X)$, the earth mover distance between two distributions over $X$ is defined as the minimum cost of a bipartite matching between the two distributions. The doubling dimension of a metric $(X, d_X)$ is the smallest value $α$ such that every ball in $X$ can be covered by $2^α$ ball of half the radius. We study efficient algorithms for approximating earth mover distance over metrics with bounded doubling dimension. Given a metric $(X, d_X)$, with $|X| = n$, we can use $\tilde O(n^2)$ preprocessing time to create a data structure of size $\tilde O(n^{1 + \e})$, such that subsequently queried EMDs can be $O(α_X/\e)$-approximated in $\tilde O(n)$ time. We also show a weaker form of sketching scheme, which we call "encoding scheme". Given $(X, d_X)$, by using $\tilde O(n^2)$ preprocessing time, every subsequent distribution $μ$ over $X$ can be encoded into $F(μ)$ in $\tilde O(n^{1 + \e})$ time. Given $F(μ)$ and $F(ν)$, the EMD between $μ$ and $ν$ can be $O(α_X/\e)$-approximated in $\tilde O(n^\e)$ time.
A Hough Transform based Technique for Text Segmentation
Venue: arXiv cs.IR 2010
Year: 2010

Text segmentation is an inherent part of an OCR system irrespective of the domain of application of it. The OCR system contains a segmentation module where the text lines, words and ultimately the characters must be segmented properly for its successful recognition. The present work implements a Hough transform based technique for line and word segmentation from digitized images. The proposed technique is applied not only on the document image dataset but also on dataset for business card reader system and license plate recognition system. For standardization of the performance of the system the technique is also applied on public domain dataset published in the website by CMATER, Jadavpur University. The document images consist of multi-script printed and hand written text lines with variety in script and line spacing in single document image. The technique performs quite satisfactorily when applied on mobile camera captured business card images with low resolution. The usefulness of the technique is verified by applying it in a commercial project for localization of license plate of vehicles from surveillance camera images by the process of segmentation itself. The accuracy of the technique for word segmentation, as verified experimentally, is 85.7% for document images, 94.6% for business card images and 88% for surveillance camera images.
Flux Analysis in Process Models via Causality
Venue: arXiv cs.CE 2010
Year: 2010

We present an approach for flux analysis in process algebra models of biological systems. We perceive flux as the flow of resources in stochastic simulations. We resort to an established correspondence between event structures, a broadly recognised model of concurrency, and state transitions of process models, seen as Petri nets. We show that we can this way extract the causal resource dependencies in simulations between individual state transitions as partial orders of events. We propose transformations on the partial orders that provide means for further analysis, and introduce a software tool, which implements these ideas. By means of an example of a published model of the Rho GTP-binding proteins, we argue that this approach can provide the substitute for flux analysis techniques on ordinary differential equation models within the stochastic setting of process algebras.
Automatic Performance Debugging of SPMD Parallel Programs
Venue: arXiv cs.DC 2010
Year: 2010

Automatic performance debugging of parallel applications usually involves two steps: automatic detection of performance bottlenecks and uncovering their root causes for performance optimization. Previous work fails to resolve this challenging issue in several ways: first, several previous efforts automate analysis processes, but present the results in a confined way that only identifies performance problems with apriori knowledge; second, several tools take exploratory or confirmatory data analysis to automatically discover relevant performance data relationships. However, these efforts do not focus on locating performance bottlenecks or uncovering their root causes. In this paper, we design and implement an innovative system, AutoAnalyzer, to automatically debug the performance problems of single program multi-data (SPMD) parallel programs. Our system is unique in terms of two dimensions: first, without any apriori knowledge, we automatically locate bottlenecks and uncover their root causes for performance optimization; second, our method is lightweight in terms of size of collected and analyzed performance data. Our contribution is three-fold. First, we propose a set of simple performance metrics to represent behavior of different processes of parallel programs, and present two effective clustering and searching algorithms to locate bottlenecks. Second, we propose to use the rough set algorithm to automatically uncover the root causes of bottlenecks. Third, we design and implement the AutoAnalyzer system, and use two production applications to verify the effectiveness and correctness of our methods. According to the analysis results of AutoAnalyzer, we optimize two parallel programs with performance improvements by minimally 20% and maximally 170%.
Robust Vacuity for Branching Temporal Logic
Venue: arXiv cs.LO 2010
Year: 2010

There is a growing interest in techniques for detecting whether a logic specification is satisfied too easily, or vacuously. For example, the specification "every request is eventually followed by an acknowledgment" is satisfied vacuously by a system that never generates any requests. Vacuous satisfaction misleads users of model-checking into thinking that a system is correct. There are several existing definitions of vacuity. Originally, Beer et al. formalized vacuity as insensitivity to syntactic perturbation. However, this definition is only reasonable for vacuity in a single occurrence. Armoni et al. argued that vacuity must be robust -- not affected by semantically invariant changes, such as extending a model with additional atomic propositions. They show that syntactic vacuity is not robust for LTL, and propose an alternative definition -- trace vacuity. In this article, we continue this line of research. We show that trace vacuity is not robust for branching time logic. We refine it to apply uniformly to linear and branching time logic and to not suffer from the common pitfalls of prior definitions. Our new definition -- bisimulation vacuity -- is a proper non-trivial extension of both syntactic and trace vacuity. We discuss the complexity of detecting bisimulation vacuity, and give efficient algorithms to detect vacuity for several practically-relevant subsets of CTL*.
Syntactic Topic Models
Venue: arXiv cs.CL 2010
Year: 2010

The syntactic topic model (STM) is a Bayesian nonparametric model of language that discovers latent distributions of words (topics) that are both semantically and syntactically coherent. The STM models dependency parsed corpora where sentences are grouped into documents. It assumes that each word is drawn from a latent topic chosen by combining document-level features and the local syntactic context. Each document has a distribution over latent topics, as in topic models, which provides the semantic consistency. Each element in the dependency parse tree also has a distribution over the topics of its children, as in latent-state syntax models, which provides the syntactic consistency. These distributions are convolved so that the topic of each word is likely under both its document and syntactic context. We derive a fast posterior inference algorithm based on variational methods. We report qualitative and quantitative studies on both synthetic data and hand-parsed documents. We show that the STM is a more predictive model of language than current models based only on syntax or only on topics.
Accelerating sequential programs using FastFlow and self-offloading
Venue: arXiv cs.DC 2010
Year: 2010

FastFlow is a programming environment specifically targeting cache-coherent shared-memory multi-cores. FastFlow is implemented as a stack of C++ template libraries built on top of lock-free (fence-free) synchronization mechanisms. In this paper we present a further evolution of FastFlow enabling programmers to offload part of their workload on a dynamically created software accelerator running on unused CPUs. The offloaded function can be easily derived from pre-existing sequential code. We emphasize in particular the effective trade-off between human productivity and execution efficiency of the approach.
An Approach to Ad hoc Cloud Computing
Venue: arXiv cs.DC 2010
Year: 2010

We consider how underused computing resources within an enterprise may be harnessed to improve utilization and create an elastic computing infrastructure. Most current cloud provision involves a data center model, in which clusters of machines are dedicated to running cloud infrastructure software. We propose an additional model, the ad hoc cloud, in which infrastructure software is distributed over resources harvested from machines already in existence within an enterprise. In contrast to the data center cloud model, resource levels are not established a priori, nor are resources dedicated exclusively to the cloud while in use. A participating machine is not dedicated to the cloud, but has some other primary purpose such as running interactive processes for a particular user. We outline the major implementation challenges and one approach to tackling them.
Nash equilibria in Fisher market
Venue: arXiv cs.GT 2010
Year: 2010

Much work has been done on the computation of market equilibria. However due to strategic play by buyers, it is not clear whether these are actually observed in the market. Motivated by the observation that a buyer may derive a better payoff by feigning a different utility function and thereby manipulating the Fisher market equilibrium, we formulate the {\em Fisher market game} in which buyers strategize by posing different utility functions. We show that existence of a {\em conflict-free allocation} is a necessary condition for the Nash equilibria (NE) and also sufficient for the symmetric NE in this game. There are many NE with very different payoffs, and the Fisher equilibrium payoff is captured at a symmetric NE. We provide a complete polyhedral characterization of all the NE for the two-buyer market game. Surprisingly, all the NE of this game turn out to be symmetric and the corresponding payoffs constitute a piecewise linear concave curve. We also study the correlated equilibria of this game and show that third-party mediation does not help to achieve a better payoff than NE payoffs.
Capacity Region of Gaussian MIMO Broadcast Channels with Common and Confidential Messages
Venue: arXiv cs.IT 2010
Year: 2010

We study the two-user Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and confidential messages. In this channel, the transmitter sends a common message to both users, and a confidential message to each user which needs to be kept perfectly secret from the other user. We obtain the entire capacity region of this channel. We also explore the connections between the capacity region we obtain for the Gaussian MIMO broadcast channel with common and confidential messages and the capacity region of its non-confidential counterpart, i.e., the Gaussian MIMO broadcast channel with common and private messages, which is not known completely.
An O(loglog n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times
Venue: arXiv cs.DS 2010
Year: 2010

We present the zipper tree, an $O(\log \log n)$-competitive online binary search tree that performs each access in $O(\log n)$ worst-case time. This shows that for binary search trees, optimal worst-case access time and near-optimal amortized access time can be guaranteed simultaneously.
Multidimensional Divide-and-Conquer and Weighted Digital Sums
Venue: arXiv cs.DS 2010
Year: 2010

This paper studies three types of functions arising separately in the analysis of algorithms that we analyze exactly using similar Mellin transform techniques. The first is the solution to a Multidimensional Divide-and-Conquer (MDC) recurrence that arises when solving problems on points in $d$-dimensional space. The second involves weighted digital sums. Write $n$ in its binary representation $n=(b_i b_{i-1}... b_1 b_0)_2$ and set $S_M(n) = \sum_{t=0}^i t^{\bar{M}} b_t 2^t$. We analyze the average $TS_M(n) = \frac{1}{n}\sum_{j<n} S_M(j)$. The third is a different variant of weighted digital sums. Write $n$ as $n=2^{i_1} + 2^{i_2} + ... + 2^{i_k}$ with $i_1 > i_2 > ... > i_k\geq 0$ and set $W_M(n) = \sum_{t=1}^k t^M 2^{i_t}$. We analyze the average $TW_M(n) = \frac{1}{n}\sum_{j<n} W_M(j)$. We show that both the MDC functions and $TS_M(n)$ (with $d=M+1$) have solutions of the form $λ_d n \lg^{d-1}n + \sum_{m=0}^{d-2}(n\lg^m n)A_{d,m}(\lg n) + c_d,$ where $λ_d,c_d$ are constants and $A_{d,m}(u)$'s are periodic functions with period one (given by absolutely convergent Fourier series). We also show that $TW_M(n)$ has a solution of the form $n G_M(\lg n) + d_M \lg^M n + \sum_{d=0}^{M-1}(\lg^d n)G_{M,d}(\lg n),$ where $d_M$ is a constant, $G_M(u)$ and $G_{M,d}(u)$'s are again periodic functions with period one (given by absolutely convergent Fourier series).
Why has (reasonably accurate) Automatic Speech Recognition been so hard to achieve?
Venue: arXiv cs.CL 2010
Year: 2010

Hidden Markov models (HMMs) have been successfully applied to automatic speech recognition for more than 35 years in spite of the fact that a key HMM assumption -- the statistical independence of frames -- is obviously violated by speech data. In fact, this data/model mismatch has inspired many attempts to modify or replace HMMs with alternative models that are better able to take into account the statistical dependence of frames. However it is fair to say that in 2010 the HMM is the consensus model of choice for speech recognition and that HMMs are at the heart of both commercially available products and contemporary research systems. In this paper we present a preliminary exploration aimed at understanding how speech data depart from HMMs and what effect this departure has on the accuracy of HMM-based speech recognition. Our analysis uses standard diagnostic tools from the field of statistics -- hypothesis testing, simulation and resampling -- which are rarely used in the field of speech recognition. Our main result, obtained by novel manipulations of real and resampled data, demonstrates that real data have statistical dependency and that this dependency is responsible for significant numbers of recognition errors. We also demonstrate, using simulation and resampling, that if we `remove' the statistical dependency from data, then the resulting recognition error rates become negligible. Taken together, these results suggest that a better understanding of the structure of the statistical dependency in speech data is a crucial first step towards improving HMM-based speech recognition.
Peak to Average Power Ratio Reduction for Space-Time Codes That Achieve Diversity-Multiplexing Gain Tradeoff
Venue: arXiv cs.IT 2010
Year: 2010

Zheng and Tse have shown that over a quasi-static channel, there exists a fundamental tradeoff, known as the diversity-multiplexing gain (D-MG) tradeoff. In a realistic system, to avoid inefficiently operating the power amplifier, one should consider the situation where constraints are imposed on the peak to average power ratio (PAPR) of the transmitted signal. In this paper, the D-MG tradeoff of multi-antenna systems with PAPR constraints is analyzed. For Rayleigh fading channels, we show that the D-MG tradeoff remains unchanged with any PAPR constraints larger than one. This result implies that, instead of designing codes on a case-by-case basis, as done by most existing works, there possibly exist general methodologies for designing space-time codes with low PAPR that achieve the optimal D-MG tradeoff. As an example of such methodologies, we propose a PAPR reduction method based on constellation shaping that can be applied to existing optimal space-time codes without affecting their optimality in the D-MG tradeoff. Unlike most PAPR reduction methods, the proposed method does not introduce redundancy or require side information being transmitted to the decoder. Two realizations of the proposed method are considered. The first is similar to the method proposed by Kwok except that we employ the Hermite Normal Form (HNF) decomposition instead of the Smith Normal Form (SNF) to reduce complexity. The second takes the idea of integer reversible mapping which avoids the difficulty in matrix decomposition when the number of antennas becomes large. Sphere decoding is performed to verify that the proposed PAPR reduction method does not affect the performance of optimal space-time codes.
Deep Big Simple Neural Nets Excel on Handwritten Digit Recognition
Venue: arXiv cs.NE 2010
Year: 2010

Good old on-line back-propagation for plain multi-layer perceptrons yields a very low 0.35% error rate on the famous MNIST handwritten digits benchmark. All we need to achieve this best result so far are many hidden layers, many neurons per layer, numerous deformed training images, and graphics cards to greatly speed up learning.
Developing Experimental Models for NASA Missions with ASSL
Venue: arXiv cs.SE 2010
Year: 2010

NASA's new age of space exploration augurs great promise for deep space exploration missions whereby spacecraft should be independent, autonomous, and smart. Nowadays NASA increasingly relies on the concepts of autonomic computing, exploiting these to increase the survivability of remote missions, particularly when human tending is not feasible. Autonomic computing has been recognized as a promising approach to the development of self-managing spacecraft systems that employ onboard intelligence and rely less on control links. The Autonomic System Specification Language (ASSL) is a framework for formally specifying and generating autonomic systems. As part of long-term research targeted at the development of models for space exploration missions that rely on principles of autonomic computing, we have employed ASSL to develop formal models and generate functional prototypes for NASA missions. This helps to validate features and perform experiments through simulation. Here, we discuss our work on developing such missions with ASSL.
On The Design of Signature Codes in Decentralized Wireless Networks
Venue: arXiv cs.IT 2010
Year: 2010

This paper addresses a unified approach towards communication in decentralized wireless networks of separate transmitter-receiver pairs. In general, users are unaware of each other's codebooks and there is no central controller to assign the resources in the network to the users. A randomized signaling scheme is introduced in which each user locally spreads its Gaussian signal along a randomly generated spreading code comprised of a sequence of nonzero elements over a certain alphabet. Along with spreading, each transmitter also masks its output independently from transmission to transmission. Using a conditional version of entropy power inequality and a key lemma on the differential entropy of mixed Gaussian random vectors, achievable rates are developed for the users. It is seen that as the number of users increases, the achievable Sum Multiplexing Gain of the network approaches that of a centralized orthogonal scheme where multiuser interference is completely avoided. An interesting observation is that in general the elements of a spreading code are not equiprobable over the underlying alphabet. Finally, using the recently developed extremal inequality of Liu-Viswanath, we present an optimality result showing that transmission of Gaussian signals via spreading and masking yields higher achievable rates than the maximum achievable rate attained by applying masking only.
Low Dimensional Euclidean Volume Preserving Embeddings
Venue: arXiv cs.DM 2010
Year: 2010

Let $\mathcal{P}$ be an $n$-point subset of Euclidean space and $d\geq 3$ be an integer. In this paper we study the following question: What is the smallest (normalized) relative change of the volume of subsets of $\mathcal{P}$ when it is projected into $\RR^d$. We prove that there exists a linear mapping $f:\mathcal{P} \mapsto \RR^d$ that relatively preserves the volume of all subsets of size up to $\lfloor d/2\rfloor$ within at most a factor of $O(n^{2/d}\sqrt{\log n \log\log n})$.
The finite-dimensional Witsenhausen counterexample
Venue: arXiv cs.IT 2010
Year: 2010

Recently, a vector version of Witsenhausen's counterexample was considered and it was shown that in that limit of infinite vector length, certain quantization-based control strategies are provably within a constant factor of the optimal cost for all possible problem parameters. In this paper, finite vector lengths are considered with the dimension being viewed as an additional problem parameter. By applying a large-deviation "sphere-packing" philosophy, a lower bound to the optimal cost for the finite dimensional case is derived that uses appropriate shadows of the infinite-length bound. Using the new lower bound, we show that good lattice-based control strategies achieve within a constant factor of the optimal cost uniformly over all possible problem parameters, including the vector length. For Witsenhausen's original problem -- the scalar case -- the gap between regular lattice-based strategies and the lower bound is numerically never more than a factor of 8.
A Unified Algorithmic Framework for Multi-Dimensional Scaling
Venue: arXiv cs.LG 2010
Year: 2010

In this paper, we propose a unified algorithmic framework for solving many known variants of \mds. Our algorithm is a simple iterative scheme with guaranteed convergence, and is \emph{modular}; by changing the internals of a single subroutine in the algorithm, we can switch cost functions and target spaces easily. In addition to the formal guarantees of convergence, our algorithms are accurate; in most cases, they converge to better quality solutions than existing methods, in comparable time. We expect that this framework will be useful for a number of \mds variants that have not yet been studied. Our framework extends to embedding high-dimensional points lying on a sphere to points on a lower dimensional sphere, preserving geodesic distances. As a compliment to this result, we also extend the Johnson-Lindenstrauss Lemma to this spherical setting, where projecting to a random $O((1/\eps^2) \log n)$-dimensional sphere causes $\eps$-distortion.
Binarizing Business Card Images for Mobile Devices
Venue: arXiv cs.CV 2010
Year: 2010

Business card images are of multiple natures as these often contain graphics, pictures and texts of various fonts and sizes both in background and foreground. So, the conventional binarization techniques designed for document images can not be directly applied on mobile devices. In this paper, we have presented a fast binarization technique for camera captured business card images. A card image is split into small blocks. Some of these blocks are classified as part of the background based on intensity variance. Then the non-text regions are eliminated and the text ones are skew corrected and binarized using a simple yet adaptive technique. Experiment shows that the technique is fast, efficient and applicable for the mobile devices.