OpenRaiser/Intern-Atlas huggingface dataset:
A Pointillism Approach for Natural Language Processing of Social Media
Venue: arXiv cs.IR 2012
Year: 2012

The Chinese language poses challenges for natural language processing based on the unit of a word even for formal uses of the Chinese language, social media only makes word segmentation in Chinese even more difficult. In this document we propose a pointillism approach to natural language processing. Rather than words that have individual meanings, the basic unit of a pointillism approach is trigrams of characters. These grams take on meaning in aggregate when they appear together in a way that is correlated over time. Our results from three kinds of experiments show that when words and topics do have a meme-like trend, they can be reconstructed from only trigrams. For example, for 4-character idioms that appear at least 99 times in one day in our data, the unconstrained precision (that is, precision that allows for deviation from a lexicon when the result is just as correct as the lexicon version of the word or phrase) is 0.93. For longer words and phrases collected from Wiktionary, including neologisms, the unconstrained precision is 0.87. We consider these results to be very promising, because they suggest that it is feasible for a machine to reconstruct complex idioms, phrases, and neologisms with good precision without any notion of words. Thus the colorful and baroque uses of language that typify social media in challenging languages such as Chinese may in fact be accessible to machines.
SkyQuery: An Implementation of a Parallel Probabilistic Join Engine for Cross-Identification of Multiple Astronomical Databases
Venue: arXiv cs.DB 2012
Year: 2012

Multi-wavelength astronomical studies require cross-identification of detections of the same celestial objects in multiple catalogs based on spherical coordinates and other properties. Because of the large data volumes and spherical geometry, the symmetric N-way association of astronomical detections is a computationally intensive problem, even when sophisticated indexing schemes are used to exclude obviously false candidates. Legacy astronomical catalogs already contain detections of more than a hundred million objects while the ongoing and future surveys will produce catalogs of billions of objects with multiple detections of each at different times. The varying statistical error of position measurements, moving and extended objects, and other physical properties make it necessary to perform the cross-identification using a mathematically correct, proper Bayesian probabilistic algorithm, capable of including various priors. One time, pair-wise cross-identification of these large catalogs is not sufficient for many astronomical scenarios. Consequently, a novel system is necessary that can cross-identify multiple catalogs on-demand, efficiently and reliably. In this paper, we present our solution based on a cluster of commodity servers and ordinary relational databases. The cross-identification problems are formulated in a language based on SQL, but extended with special clauses. These special queries are partitioned spatially by coordinate ranges and compiled into a complex workflow of ordinary SQL queries. Workflows are then executed in a parallel framework using a cluster of servers hosting identical mirrors of the same data sets.
A generic framework for video understanding applied to group behavior recognition
Venue: arXiv cs.CV 2012
Year: 2012

This paper presents an approach to detect and track groups of people in video-surveillance applications, and to automatically recognize their behavior. This method keeps track of individuals moving together by maintaining a spacial and temporal group coherence. First, people are individually detected and tracked. Second, their trajectories are analyzed over a temporal window and clustered using the Mean-Shift algorithm. A coherence value describes how well a set of people can be described as a group. Furthermore, we propose a formal event description language. The group events recognition approach is successfully validated on 4 camera views from 3 datasets: an airport, a subway, a shopping center corridor and an entrance hall.
Usage and Impact of ICT in Education Sector; A Study of Pakistan
Venue: arXiv cs.OH 2012
Year: 2012

In many countries, information and communication technology (ICT) has a lucid impact on the development of educational curriculum. This is the era of Information Communication Technology, so to perk up educational planning it is indispensable to implement the ICT in Education sector. Student can perform well throughout the usage of ICT. ICT helps the students to augment their knowledge skills as well as to improve their learning skills. To know with reference to the usage and Impact of ICT in Education sector of Pakistan, we accumulate data from 429 respondents from 5 colleges and universities, we use convenient sampling to accumulate the data from district Rawalpindi of Pakistan. The consequences show that Availability and Usage of ICT improves the knowledge and learning skills of students. This indicates that existence of ICT is improving the educational efficiency as well as obliging for making policies regarding education sector.
Three Steps to Heaven: Semantic Publishing in a Real World Workflow
Venue: arXiv cs.DL 2012
Year: 2012

Semantic publishing offers the promise of computable papers, enriched visualisation and a realisation of the linked data ideal. In reality, however, the publication process contrives to prevent richer semantics while culminating in a `lumpen' PDF. In this paper, we discuss a web-first approach to publication, and describe a three-tiered approach which integrates with the existing authoring tooling. Critically, although it adds limited semantics, it does provide value to all the participants in the process: the author, the reader and the machine.
Signal Processing and Optimal Resource Allocation for the Interference Channel
Venue: arXiv cs.IT 2012
Year: 2012

In this article, we examine several design and complexity aspects of the optimal physical layer resource allocation problem for a generic interference channel (IC). The latter is a natural model for multi-user communication networks. In particular, we characterize the computational complexity, the convexity as well as the duality of the optimal resource allocation problem. Moreover, we summarize various existing algorithms for resource allocation and discuss their complexity and performance tradeoff. We also mention various open research problems throughout the article.
Leaf vein segmentation using Odd Gabor filters and morphological operations
Venue: arXiv cs.CV 2012
Year: 2012

Leaf vein forms the basis of leaf characterization and classification. Different species have different leaf vein patterns. It is seen that leaf vein segmentation will help in maintaining a record of all the leaves according to their specific pattern of veins thus provide an effective way to retrieve and store information regarding various plant species in database as well as provide an effective means to characterize plants on the basis of leaf vein structure which is unique for every species. The algorithm proposes a new way of segmentation of leaf veins with the use of Odd Gabor filters and the use of morphological operations for producing a better output. The Odd Gabor filter gives an efficient output and is robust and scalable as compared with the existing techniques as it detects the fine fiber like veins present in leaves much more efficiently.
Analysis of Semi-Supervised Learning with the Yarowsky Algorithm
Venue: arXiv cs.LG 2012
Year: 2012

The Yarowsky algorithm is a rule-based semi-supervised learning algorithm that has been successfully applied to some problems in computational linguistics. The algorithm was not mathematically well understood until (Abney 2004) which analyzed some specific variants of the algorithm, and also proposed some new algorithms for bootstrapping. In this paper, we extend Abney's work and show that some of his proposed algorithms actually optimize (an upper-bound on) an objective function based on a new definition of cross-entropy which is based on a particular instantiation of the Bregman distance between probability distributions. Moreover, we suggest some new algorithms for rule-based semi-supervised learning and show connections with harmonic functions and minimum multi-way cuts in graph-based semi-supervised learning.
Discovering Patterns in Biological Sequences by Optimal Segmentation
Venue: arXiv cs.CE 2012
Year: 2012

Computational methods for discovering patterns of local correlations in sequences are important in computational biology. Here we show how to determine the optimal partitioning of aligned sequences into non-overlapping segments such that positions in the same segment are strongly correlated while positions in different segments are not. Our approach involves discovering the hidden variables of a Bayesian network that interact with observed sequences so as to form a set of independent mixture models. We introduce a dynamic program to efficiently discover the optimal segmentation, or equivalently the optimal set of hidden variables. We evaluate our approach on two computational biology tasks. One task is related to the design of vaccines against polymorphic pathogens and the other task involves analysis of single nucleotide polymorphisms (SNPs) in human DNA. We show how common tasks in these problems naturally correspond to inference procedures in the learned models. Error rates of our learned models for the prediction of missing SNPs are up to 1/3 less than the error rates of a state-of-the-art SNP prediction method. Source code is available at www.uwm.edu/~joebock/segmentation.
Best-First AND/OR Search for Most Probable Explanations
Venue: arXiv cs.AI 2012
Year: 2012

The paper evaluates the power of best-first search over AND/OR search spaces for solving the Most Probable Explanation (MPE) task in Bayesian networks. The main virtue of the AND/OR representation of the search space is its sensitivity to the structure of the problem, which can translate into significant time savings. In recent years depth-first AND/OR Branch-and- Bound algorithms were shown to be very effective when exploring such search spaces, especially when using caching. Since best-first strategies are known to be superior to depth-first when memory is utilized, exploring the best-first control strategy is called for. The main contribution of this paper is in showing that a recent extension of AND/OR search algorithms from depth-first Branch-and-Bound to best-first is indeed very effective for computing the MPE in Bayesian networks. We demonstrate empirically the superiority of the best-first search approach on various probabilistic networks.
CLIFT: a Cross-Layer InFormation Tool to perform cross-layer analysis based on real physical traces
Venue: arXiv cs.NI 2012
Year: 2012

Considering real physical (MAC/PHY) traces inside network simulations is a complex task that might lead to complex yet approximated models. However, realistic cross-layer analysis with the upper layer and in particular the transport layer cannot be driven without considering the MAC/PHY level. In this paper, we propose to cope with this problem by introducing a software that translates real physical events from a given trace in order to be used inside a network simulator such as $ns$-2. The main objective is to accurately perform analysis of the impact of link layer reliability schemes (obtained by the use of real physical traces) on transport layer performance. We detail the internal mechanisms and the benefits of this software with a focus on 4G satellite communications scenarios and present the resulting metrics provided by CLIFT to perform consistent cross-layer analysis.
Analysis of Coverage Region for MIMO Relay Channel
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we investigate the optimal relay location in the sense of maximizing suitably defined coverage region for MIMO relay channel. We consider the general Rayleigh fading case and assume that the channel state information is only available at the receivers (CSIR), which is an important practical case in applications such as cooperative vehicular communications. In order to overcome the mathematical difficulty regarding determination of the optimal relay location, we provide two analytical solutions, and show that it is possible to determine the optimal relay location (for a desired transmission rate) at which the coverage region is maximum. Monte Carlo simulations confirm the validity of the analytical results. Numerical results indicate that using multiple antennas increases coverage region for a fixed transmission rate, and also increases the transmission rate linearly for a fixed coverage.
Web-page Prediction for Domain Specific Web-search using Boolean Bit Mask
Venue: arXiv cs.IR 2012
Year: 2012

Search Engine is a Web-page retrieval tool. Nowadays Web searchers utilize their time using an efficient search engine. To improve the performance of the search engine, we are introducing a unique mechanism which will give Web searchers more prominent search results. In this paper, we are going to discuss a domain specific Web search prototype which will generate the predicted Web-page list for user given search string using Boolean bit mask.
A New Upper Bound for the VC-Dimension of Visibility Regions
Venue: arXiv cs.CG 2012
Year: 2012

In this paper we are proving the following fact. Let P be an arbitrary simple polygon, and let S be an arbitrary set of 15 points inside P. Then there exists a subset T of S that is not "visually discernible", that is, T is not equal to the intersection of S with the visibility region vis(v) of any point v in P. In other words, the VC-dimension d of visibility regions in a simple polygon cannot exceed 14. Since Valtr proved in 1998 that d \in [6,23] holds, no progress has been made on this bound. By epsilon-net theorems our reduction immediately implies a smaller upper bound to the number of guards needed to cover P.
Graph Based Classification Methods Using Inaccurate External Classifier Information
Venue: arXiv cs.LG 2012
Year: 2012

In this paper we consider the problem of collectively classifying entities where relational information is available across the entities. In practice inaccurate class distribution for each entity is often available from another (external) classifier. For example this distribution could come from a classifier built using content features or a simple dictionary. Given the relational and inaccurate external classifier information, we consider two graph based settings in which the problem of collective classification can be solved. In the first setting the class distribution is used to fix labels to a subset of nodes and the labels for the remaining nodes are obtained like in a transductive setting. In the other setting the class distributions of all nodes are used to define the fitting function part of a graph regularized objective function. We define a generalized objective function that handles both the settings. Methods like harmonic Gaussian field and local-global consistency (LGC) reported in the literature can be seen as special cases. We extend the LGC and weighted vote relational neighbor classification (WvRN) methods to support usage of external classifier information. We also propose an efficient least squares regularization (LSR) based method and relate it to information regularization methods. All the methods are evaluated on several benchmark and real world datasets. Considering together speed, robustness and accuracy, experimental results indicate that the LSR and WvRN-extension methods perform better than other methods.
GUBS, a Behavior-based Language for Open System Dedicated to Synthetic Biology
Venue: arXiv cs.PL 2012
Year: 2012

In this article, we propose a domain specific language, GUBS (Genomic Unified Behavior Specification), dedicated to the behavioral specification of synthetic biological devices, viewed as discrete open dynamical systems. GUBS is a rule-based declarative language. By contrast to a closed system, a program is always a partial description of the behavior of the system. The semantics of the language accounts the existence of some hidden non-specified actions possibly altering the behavior of the programmed device. The compilation framework follows a scheme similar to automatic theorem proving, aiming at improving synthetic biological design safety.
Structural analysis of high-index DAE for process simulation
Venue: arXiv cs.SY 2012
Year: 2012

This paper deals with the structural analysis problem of dynamic lumped process high-index DAE models. We consider two methods for index reduction of such models by differentiation: Pryce's method and the symbolic differential elimination algorithm rifsimp. Discussion and comparison of these methods are given via a class of fundamental process simulation examples. In particular, the efficiency of the Pryce method is illustrated as a function of the number of tanks in process design.
Locally Correct Frechet Matchings
Venue: arXiv cs.CG 2012
Year: 2012

The Frechet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Frechet distance a Frechet matching. There are often many different Frechet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Frechet matchings to "natural" matchings and to this end introduce locally correct Frechet matchings. We prove that at least one such matching exists for two polygonal curves and give an O(N^3 log N) algorithm to compute it, where N is the total number of edges in both curves. We also present an O(N^2) algorithm to compute a locally correct discrete Frechet matching.
Cascading map-side joins over HBase for scalable join processing
Venue: arXiv cs.DB 2012
Year: 2012

One of the major challenges in large-scale data processing with MapReduce is the smart computation of joins. Since Semantic Web datasets published in RDF have increased rapidly over the last few years, scalable join techniques become an important issue for SPARQL query processing as well. In this paper, we introduce the Map-Side Index Nested Loop Join (MAPSIN join) which combines scalable indexing capabilities of NoSQL storage systems like HBase, that suffer from an insufficient distributed processing layer, with MapReduce, which in turn does not provide appropriate storage structures for efficient large-scale join processing. While retaining the flexibility of commonly used reduce-side joins, we leverage the effectiveness of map-side joins without any changes to the underlying framework. We demonstrate the significant benefits of MAPSIN joins for the processing of SPARQL basic graph patterns on large RDF datasets by an evaluation with the LUBM and SP2Bench benchmarks. For most queries, MAPSIN join based query execution outperforms reduce-side join based execution by an order of magnitude.
A Generative Process for Sampling Contractive Auto-Encoders
Venue: arXiv cs.LG 2012
Year: 2012

The contractive auto-encoder learns a representation of the input data that captures the local manifold structure around each data point, through the leading singular vectors of the Jacobian of the transformation from input to representation. The corresponding singular values specify how much local variation is plausible in directions associated with the corresponding singular vectors, while remaining in a high-density region of the input space. This paper proposes a procedure for generating samples that are consistent with the local structure captured by a contractive auto-encoder. The associated stochastic process defines a distribution from which one can sample, and which experimentally appears to converge quickly and mix well between modes, compared to Restricted Boltzmann Machines and Deep Belief Networks. The intuitions behind this procedure can also be used to train the second layer of contraction that pools lower-level features and learns to be invariant to the local directions of variation discovered in the first layer. We show that this can help learn and represent invariances present in the data and improve classification error.
Predicting Preference Flips in Commerce Search
Venue: arXiv cs.LG 2012
Year: 2012

Traditional approaches to ranking in web search follow the paradigm of rank-by-score: a learned function gives each query-URL combination an absolute score and URLs are ranked according to this score. This paradigm ensures that if the score of one URL is better than another then one will always be ranked higher than the other. Scoring contradicts prior work in behavioral economics that showed that users' preferences between two items depend not only on the items but also on the presented alternatives. Thus, for the same query, users' preference between items A and B depends on the presence/absence of item C. We propose a new model of ranking, the Random Shopper Model, that allows and explains such behavior. In this model, each feature is viewed as a Markov chain over the items to be ranked, and the goal is to find a weighting of the features that best reflects their importance. We show that our model can be learned under the empirical risk minimization framework, and give an efficient learning algorithm. Experiments on commerce search logs demonstrate that our algorithm outperforms scoring-based approaches including regression and listwise ranking.
An Approximate Coding-Rate Versus Minimum Distance Formula for Binary Codes
Venue: arXiv cs.IT 2012
Year: 2012

We devise an analytically simple as well as invertible approximate expression, which describes the relation between the minimum distance of a binary code and the corresponding maximum attainable code-rate. For example, for a rate-(1/4), length-256 binary code the best known bounds limit the attainable minimum distance to 65<d(n=256,k=64)<90, while our solution yields d(n=256,k=64)=74.4. The proposed formula attains the approximation accuracy within the rounding error for ~97% of (n,k) scenarios, where the exact value of the minimum distance is known. The results provided may be utilized for the analysis and design of efficient communication systems.
Pricing-based Distributed Downlink Beamforming in Multi-Cell OFDMA Networks
Venue: arXiv cs.IT 2012
Year: 2012

We address the problem of downlink beamforming for mitigating the co-channel interference in multi-cell OFDMA networks. Based on the network utility maximization framework, we formulate the problem as a non-convex optimization problem subject to the per-cell power constraints, in which a general utility function of SINR is used to characterize the network performance. Some classical utility functions, such as the proportional fairness utility, the weighted sum-rate utility and the {$α$}-fairness utility, are subsumed as special cases of our formulation. To solve the problem in a distributed fashion, we devise an algorithm based on the non-cooperative game with pricing mechanism. We give a sufficient condition for the convergence of the algorithm to the Nash equilibrium (NE), and analyze the information exchange overhead among the base stations. Moreover, to speed up the optimization of the beam-vectors at each cell, we derive an efficient algorithm to solve for the KKT conditions at each cell. We provide extensive simulation results to demonstrate that the proposed distributed multi-cell beamforming algorithm converges to an NE point in just a few iterations with low information exchange overhead. Moreover, it provides significant performance gains, especially under the strong interference scenario, in comparison with several existing multi-cell interference mitigation schemes, such as the distributed interference alignment method.