OpenRaiser/Intern-Atlas huggingface dataset:
Tight Lower Bounds on Envy-Free Makespan Approximation
Venue: arXiv cs.DM 2012
Year: 2012

In this work we give a tight lower bound on makespan approximations for envy-free allocation mechanism dedicated to scheduling tasks on unrelated machines. Specifically, we show that no mechanism exists that can guarantee an envy-free allocation of jobs to $m$ machines with a makespan of less than a factor of $O(\log m)$ of the minimal makespan. Combined with previous results, this paper definitively proves that the optimal algorithm for obtaining a minimal makespan for any envy-free division can at best approximate the makespan to a factor of $O(\log m)$.
Graph spectra and the detectability of community structure in networks
Venue: arXiv cs.SI 2012
Year: 2012

We study networks that display community structure -- groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.
Wishbone bus Architecture - A Survey and Comparison
Venue: arXiv cs.AR 2012
Year: 2012

The performance of an on-chip interconnection architecture used for communication between IP cores depends on the efficiency of its bus architecture. Any bus architecture having advantages of faster bus clock speed, extra data transfer cycle, improved bus width and throughput is highly desirable for a low cost, reduced time-to-market and efficient System-on-Chip (SoC). This paper presents a survey of WISHBONE bus architecture and its comparison with three other on-chip bus architectures viz. Advanced Micro controller Bus Architecture (AMBA) by ARM, CoreConnect by IBM and Avalon by Altera. The WISHBONE Bus Architecture by Silicore Corporation appears to be gaining an upper edge over the other three bus architecture types because of its special performance parameters like the use of flexible arbitration scheme and additional data transfer cycle (Read-Modify-Write cycle). Moreover, its IP Cores are available free for use requiring neither any registration nor any agreement or license.
Structured Grammars are Effective
Venue: arXiv cs.FL 2012
Year: 2012

Top-down parsing has received much attention recently. Parsing expression grammars (PEG) allows construction of linear time parsers using packrat algorithm. These techniques however suffer from problem of prefix hiding. We use alternative formalism of relativized regular expressions REGREG for which top-down backtracking parser runs in linear time. This formalism allows to construct fast parsers with modest memory requirements for practical grammars. We show that our formalism is equivalent to PEG.
A Note on the PageRank of Undirected Graphs
Venue: arXiv cs.DS 2012
Year: 2012

The PageRank is a widely used scoring function of networks in general and of the World Wide Web graph in particular. The PageRank is defined for directed graphs, but in some special cases applications for undirected graphs occur. In the literature it is widely noted that the PageRank for undirected graphs are proportional to the degrees of the vertices of the graph. We prove that statement for a particular personalization vector in the definition of the PageRank, and we also show that in general, the PageRank of an undirected graph is not exactly proportional to the degree distribution of the graph: our main theorem gives an upper and a lower bound to the L_1 norm of the difference of the PageRank and the degree distribution vectors.
Complexity and Information: Measuring Emergence, Self-organization, and Homeostasis at Multiple Scales
Venue: arXiv cs.IT 2012
Year: 2012

Concepts used in the scientific study of complex systems have become so widespread that their use and abuse has led to ambiguity and confusion in their meaning. In this paper we use information theory to provide abstract and concise measures of complexity, emergence, self-organization, and homeostasis. The purpose is to clarify the meaning of these concepts with the aid of the proposed formal measures. In a simplified version of the measures (focusing on the information produced by a system), emergence becomes the opposite of self-organization, while complexity represents their balance. Homeostasis can be seen as a measure of the stability of the system. We use computational experiments on random Boolean networks and elementary cellular automata to illustrate our measures at multiple scales.
M-FISH Karyotyping - A New Approach Based on Watershed Transform
Venue: arXiv cs.CV 2012
Year: 2012

Karyotyping is a process in which chromosomes in a dividing cell are properly stained, identified and displayed in a standard format, which helps geneticist to study and diagnose genetic factors behind various genetic diseases and for studying cancer. M-FISH (Multiplex Fluorescent In-Situ Hybridization) provides color karyotyping. In this paper, an automated method for M-FISH chromosome segmentation based on watershed transform followed by naive Bayes classification of each region using the features, mean and standard deviation, is presented. Also, a post processing step is added to re-classify the small chromosome segments to the neighboring larger segment for reducing the chances of misclassification. The approach provided improved accuracy when compared to the pixel-by-pixel approach. The approach was tested on 40 images from the dataset and achieved an accuracy of 84.21 %.
A Converged Algorithm for Tikhonov Regularized Nonnegative Matrix Factorization with Automatic Regularization Parameters Determination
Venue: arXiv cs.LG 2012
Year: 2012

We present a converged algorithm for Tikhonov regularized nonnegative matrix factorization (NMF). We specially choose this regularization because it is known that Tikhonov regularized least square (LS) is the more preferable form in solving linear inverse problems than the conventional LS. Because an NMF problem can be decomposed into LS subproblems, it can be expected that Tikhonov regularized NMF will be the more appropriate approach in solving NMF problems. The algorithm is derived using additive update rules which have been shown to have convergence guarantee. We equip the algorithm with a mechanism to automatically determine the regularization parameters based on the L-curve, a well-known concept in the inverse problems community, but is rather unknown in the NMF research. The introduction of this algorithm thus solves two inherent problems in Tikhonov regularized NMF algorithm research, i.e., convergence guarantee and regularization parameters determination.
Discrimination of English to other Indian languages (Kannada and Hindi) for OCR system
Venue: arXiv cs.CV 2012
Year: 2012

India is a multilingual multi-script country. In every state of India there are two languages one is state local language and the other is English. For example in Andhra Pradesh, a state in India, the document may contain text words in English and Telugu script. For Optical Character Recognition (OCR) of such a bilingual document, it is necessary to identify the script before feeding the text words to the OCRs of individual scripts. In this paper, we are introducing a simple and efficient technique of script identification for Kannada, English and Hindi text words of a printed document. The proposed approach is based on the horizontal and vertical projection profile for the discrimination of the three scripts. The feature extraction is done based on the horizontal projection profile of each text words. We analysed 700 different words of Kannada, English and Hindi in order to extract the discrimination features and for the development of knowledge base. We use the horizontal projection profile of each text word and based on the horizontal projection profile we extract the appropriate features. The proposed system is tested on 100 different document images containing more than 1000 text words of each script and a classification rate of 98.25%, 99.25% and 98.87% is achieved for Kannada, English and Hindi respectively.
Streaming multimedia over WMSNs: an online multipath routing protocol
Venue: arXiv cs.NI 2012
Year: 2012

Routing is a challenge to Wireless Multimedia Sensor Networks (WMSNs) for supporting multimedia applications due to nodes' energy constraints and computational capabilities, and the ways sensor nodes obtain forwarding information. In this paper, we propose an online multipath routing protocol that uses nodes' positions to make forwarding decisions at each hop. Real-time decisions are made without any need to have the entire network topology knowledge. The protocol achieves load-balancing and minimises nodes' energy consumption by utilizing: (a) smart greedy forwarding scheme for selecting next hop, and (b) walking back forwarding scheme to bypass network holes. Performance comparisons of the proposed protocol (schemes) are made with TPGF and GPSR. The results show that our schemes: (a) maximise the overall network lifespan by not draining energy from some specific nodes, (b) provide QoS delivery for video streams by using best nodes along the route, and (c) scale better in high density WMSN.
The citation-based indicator and combined impact indicator - New options for measuring impact
Venue: arXiv cs.DL 2012
Year: 2012

Metrics based on percentile ranks (PRs) for measuring scholarly impact involves complex treatment because of various defects such as overvaluing or devaluing an object caused by percentile ranking schemes, ignoring precise citation variation among those ranked next to each other, and inconsistency caused by additional papers or citations. These defects are especially obvious in a small-sized dataset. To avoid the complicated treatment of PRs based metrics, we propose two new indicators - the citation-based indicator (CBI) and the combined impact indicator (CII). Document types of publications are taken into account. With the two indicators, one would no more be bothered by complex issues encountered by PRs based indicators. For a small-sized dataset with less than 100 papers, special calculation is no more needed. The CBI is based solely on citation counts and the CII measures the integrate contributions of publications and citations. Both virtual and empirical data are used so as to compare the effect of related indicators. The CII and the PRs based indicator I3 are highly correlated but the former reflects citation impact more and the latter relates more to publications.
MIMO Relaying Broadcast Channels with Linear Precoding and Quantized Channel State Information Feedback
Venue: arXiv cs.IT 2012
Year: 2012

Multi-antenna relaying has emerged as a promising technology to enhance the system performance in cellular networks. However, when precoding techniques are utilized to obtain multi-antenna gains, the system generally requires channel state information (CSI) at the transmitters. We consider a linear precoding scheme in a MIMO relaying broadcast channel with quantized CSI feedback from both two-hop links. With this scheme, each remote user feeds back its quantized CSI to the relay, and the relay sends back the quantized precoding information to the base station (BS). An upper bound on the rate loss due to quantized channel knowledge is first characterized. Then, in order to maintain the rate loss within a predetermined gap for growing SNRs, a strategy of scaling quantization quality of both two-hop links is proposed. It is revealed that the numbers of feedback bits of both links should scale linearly with the transmit power at the relay, while only the bit number of feedback from the relay to the BS needs to grow with the increasing transmit power at the BS. Numerical results are provided to verify the proposed strategy for feedback quality control.
Linking Social Networking Sites to Scholarly Information Portals by ScholarLib
Venue: arXiv cs.DL 2012
Year: 2012

Online Social Networks usually provide no or limited way to access scholarly information provided by Digital Libraries (DLs) in order to share and discuss scholarly content with other online community members. The paper addresses the potentials of Social Networking sites (SNSs) for science and proposes initial use cases as well as a basic bi-directional model called ScholarLib for linking SNSs to scholarly DLs. The major aim of ScholarLib is to make scholarly information provided by DLs accessible at SNSs, and vice versa, to enhance retrieval quality at DL side by social information provided by SNSs.
An improved approach to attribute reduction with covering rough sets
Venue: arXiv cs.AI 2012
Year: 2012

Attribute reduction is viewed as an important preprocessing step for pattern recognition and data mining. Most of researches are focused on attribute reduction by using rough sets. Recently, Tsang et al. discussed attribute reduction with covering rough sets in the paper [E. C.C. Tsang, D. Chen, Daniel S. Yeung, Approximations and reducts with covering generalized rough sets, Computers and Mathematics with Applications 56 (2008) 279-289], where an approach based on discernibility matrix was presented to compute all attribute reducts. In this paper, we provide an improved approach by constructing simpler discernibility matrix with covering rough sets, and then proceed to improve some characterizations of attribute reduction provided by Tsang et al. It is proved that the improved discernible matrix is equivalent to the old one, but the computational complexity of discernible matrix is greatly reduced.
A Uniqueness Theorem for Clustering
Venue: arXiv cs.LG 2012
Year: 2012

Despite the widespread use of Clustering, there is distressingly little general theory of clustering available. Questions like "What distinguishes a clustering of data from other data partitioning?", "Are there any principles governing all clustering paradigms?", "How should a user choose an appropriate clustering algorithm for a particular task?", etc. are almost completely unanswered by the existing body of clustering literature. We consider an axiomatic approach to the theory of Clustering. We adopt the framework of Kleinberg, [Kle03]. By relaxing one of Kleinberg's clustering axioms, we sidestep his impossibility result and arrive at a consistent set of axioms. We suggest to extend these axioms, aiming to provide an axiomatic taxonomy of clustering paradigms. Such a taxonomy should provide users some guidance concerning the choice of the appropriate clustering paradigm for a given task. The main result of this paper is a set of abstract properties that characterize the Single-Linkage clustering function. This characterization result provides new insight into the properties of desired data groupings that make Single-Linkage the appropriate choice. We conclude by considering a taxonomy of clustering functions based on abstract properties that each satisfies.
Herding Dynamic Weights for Partially Observed Random Field Models
Venue: arXiv cs.LG 2012
Year: 2012

Learning the parameters of a (potentially partially observable) random field model is intractable in general. Instead of focussing on a single optimal parameter value we propose to treat parameters as dynamical quantities. We introduce an algorithm to generate complex dynamics for parameters and (both visible and hidden) state vectors. We show that under certain conditions averages computed over trajectories of the proposed dynamical system converge to averages computed over the data. Our "herding dynamics" does not require expensive operations such as exponentiation and is fully deterministic.
Bisimulation-based Approximate Lifted Inference
Venue: arXiv cs.AI 2012
Year: 2012

There has been a great deal of recent interest in methods for performing lifted inference; however, most of this work assumes that the first-order model is given as input to the system. Here, we describe lifted inference algorithms that determine symmetries and automatically lift the probabilistic model to speedup inference. In particular, we describe approximate lifted inference techniques that allow the user to trade off inference accuracy for computational efficiency by using a handful of tunable parameters, while keeping the error bounded. Our algorithms are closely related to the graph-theoretic concept of bisimulation. We report experiments on both synthetic and real data to show that in the presence of symmetries, run-times for inference can be improved significantly, with approximate lifted inference providing orders of magnitude speedup over ground inference.
BPR: Bayesian Personalized Ranking from Implicit Feedback
Venue: arXiv cs.IR 2012
Year: 2012

Item recommendation is the task of predicting a personalized ranking on a set of items (e.g. websites, movies, products). In this paper, we investigate the most common scenario with implicit feedback (e.g. clicks, purchases). There are many methods for item recommendation from implicit feedback like matrix factorization (MF) or adaptive knearest-neighbor (kNN). Even though these methods are designed for the item prediction task of personalized ranking, none of them is directly optimized for ranking. In this paper we present a generic optimization criterion BPR-Opt for personalized ranking that is the maximum posterior estimator derived from a Bayesian analysis of the problem. We also provide a generic learning algorithm for optimizing models with respect to BPR-Opt. The learning method is based on stochastic gradient descent with bootstrap sampling. We show how to apply our method to two state-of-the-art recommender models: matrix factorization and adaptive kNN. Our experiments indicate that for the task of personalized ranking our optimization method outperforms the standard learning techniques for MF and kNN. The results show the importance of optimizing models for the right criterion.
Regret-based Reward Elicitation for Markov Decision Processes
Venue: arXiv cs.AI 2012
Year: 2012

The specification of aMarkov decision process (MDP) can be difficult. Reward function specification is especially problematic; in practice, it is often cognitively complex and time-consuming for users to precisely specify rewards. This work casts the problem of specifying rewards as one of preference elicitation and aims to minimize the degree of precision with which a reward function must be specified while still allowing optimal or near-optimal policies to be produced. We first discuss how robust policies can be computed for MDPs given only partial reward information using the minimax regret criterion. We then demonstrate how regret can be reduced by efficiently eliciting reward information using bound queries, using regret-reduction as a means for choosing suitable queries. Empirical results demonstrate that regret-based reward elicitation offers an effective way to produce near-optimal policies without resorting to the precise specification of the entire reward function.
Exact Structure Discovery in Bayesian Networks with Less Space
Venue: arXiv cs.AI 2012
Year: 2012

The fastest known exact algorithms for scorebased structure discovery in Bayesian networks on n nodes run in time and space 2nnO(1). The usage of these algorithms is limited to networks on at most around 25 nodes mainly due to the space requirement. Here, we study space-time tradeoffs for finding an optimal network structure. When little space is available, we apply the Gurevich-Shelah recurrence-originally proposed for the Hamiltonian path problem-and obtain time 22n-snO(1) in space 2snO(1) for any s = n/2, n/4, n/8, . . .; we assume the indegree of each node is bounded by a constant. For the more practical setting with moderate amounts of space, we present a novel scheme. It yields running time 2n(3/2)pnO(1) in space 2n(3/4)pnO(1) for any p = 0, 1, . . ., n/2; these bounds hold as long as the indegrees are at most 0.238n. Furthermore, the latter scheme allows easy and efficient parallelization beyond previous algorithms. We also explore empirically the potential of the presented techniques.
Using the Gene Ontology Hierarchy when Predicting Gene Function
Venue: arXiv cs.LG 2012
Year: 2012

The problem of multilabel classification when the labels are related through a hierarchical categorization scheme occurs in many application domains such as computational biology. For example, this problem arises naturally when trying to automatically assign gene function using a controlled vocabularies like Gene Ontology. However, most existing approaches for predicting gene functions solve independent classification problems to predict genes that are involved in a given function category, independently of the rest. Here, we propose two simple methods for incorporating information about the hierarchical nature of the categorization scheme. In the first method, we use information about a gene's previous annotation to set an initial prior on its label. In a second approach, we extend a graph-based semi-supervised learning algorithm for predicting gene function in a hierarchy. We show that we can efficiently solve this problem by solving a linear system of equations. We compare these approaches with a previous label reconciliation-based approach. Results show that using the hierarchy information directly, compared to using reconciliation methods, improves gene function prediction.
Convergent message passing algorithms - a unifying view
Venue: arXiv cs.AI 2012
Year: 2012

Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright's non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains.
Temporal Action-Graph Games: A New Representation for Dynamic Games
Venue: arXiv cs.GT 2012
Year: 2012

In this paper we introduce temporal action graph games (TAGGs), a novel graphical representation of imperfect-information extensive form games. We show that when a game involves anonymity or context-specific utility independencies, its encoding as a TAGG can be much more compact than its direct encoding as a multiagent influence diagram (MAID).We also show that TAGGs can be understood as indirect MAID encodings in which many deterministic chance nodes are introduced. We provide an algorithm for computing with TAGGs, and show both theoretically and empirically that our approach improves significantly on the previous state of the art.