OpenRaiser/Intern-Atlas huggingface dataset:
Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function
Venue: arXiv cs.DM 2013
Year: 2013

A recent result has demonstrated that the Bethe partition function always lower bounds the true partition function of binary, log-supermodular graphical models. We demonstrate that these results can be extended to other interesting classes of graphical models that are not necessarily binary or log-supermodular: the ferromagnetic Potts model with a uniform external field and its generalizations and special classes of weighted graph homomorphism problems.
Determinantal Clustering Processes - A Nonparametric Bayesian Approach to Kernel Based Semi-Supervised Clustering
Venue: arXiv cs.LG 2013
Year: 2013

Semi-supervised clustering is the task of clustering data points into clusters where only a fraction of the points are labelled. The true number of clusters in the data is often unknown and most models require this parameter as an input. Dirichlet process mixture models are appealing as they can infer the number of clusters from the data. However, these models do not deal with high dimensional data well and can encounter difficulties in inference. We present a novel nonparameteric Bayesian kernel based method to cluster data points without the need to prespecify the number of clusters or to model complicated densities from which data points are assumed to be generated from. The key insight is to use determinants of submatrices of a kernel matrix as a measure of how close together a set of points are. We explore some theoretical properties of the model and derive a natural Gibbs based algorithm with MCMC hyperparameter learning. The model is implemented on a variety of synthetic and real world data sets.
Sparse Nested Markov models with Log-linear Parameters
Venue: arXiv cs.LG 2013
Year: 2013

Hidden variables are ubiquitous in practical data analysis, and therefore modeling marginal densities and doing inference with the resulting models is an important problem in statistics, machine learning, and causal inference. Recently, a new type of graphical model, called the nested Markov model, was developed which captures equality constraints found in marginals of directed acyclic graph (DAG) models. Some of these constraints, such as the so called `Verma constraint', strictly generalize conditional independence. To make modeling and inference with nested Markov models practical, it is necessary to limit the number of parameters in the model, while still correctly capturing the constraints in the marginal of a DAG model. Placing such limits is similar in spirit to sparsity methods for undirected graphical models, and regression models. In this paper, we give a log-linear parameterization which allows sparse modeling with nested Markov models. We illustrate the advantages of this parameterization with a simulation study.
Integrating Document Clustering and Topic Modeling
Venue: arXiv cs.LG 2013
Year: 2013

Document clustering and topic modeling are two closely related tasks which can mutually benefit each other. Topic modeling can project documents into a topic space which facilitates effective document clustering. Cluster labels discovered by document clustering can be incorporated into topic models to extract local topics specific to each cluster and global topics shared by all clusters. In this paper, we propose a multi-grain clustering topic model (MGCTM) which integrates document clustering and topic modeling into a unified framework and jointly performs the two tasks to achieve the overall best performance. Our model tightly couples two components: a mixture component used for discovering latent groups in document collection and a topic model component used for mining multi-grain topics including local topics specific to each cluster and global topics shared across clusters.We employ variational inference to approximate the posterior of hidden variables and learn model parameters. Experiments on two datasets demonstrate the effectiveness of our model.
A Collaborative Filtering Based Approach for Recommending Elective Courses
Venue: arXiv cs.IR 2013
Year: 2013

In management education programmes today, students face a difficult time in choosing electives as the number of electives available are many. As the range and diversity of different elective courses available for selection have increased, course recommendation systems that help students in making choices about courses have become more relevant. In this paper we extend the concept of collaborative filtering approach to develop a course recommendation system. The proposed approach provides student an accurate prediction of the grade they may get if they choose a particular course, which will be helpful when they decide on selecting elective courses, as grade is an important parameter for a student while deciding on an elective course. We experimentally evaluate the collaborative filtering approach on a real life data set and show that the proposed system is effective in terms of accuracy.
Analyzing the Reduced Required BS Density due to CoMP in Cellular Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we investigate the benefit of base station (BS) cooperation in the uplink of coordinated multi-point (CoMP) networks. Our figure of merit is the required BS density required to meet a chosen rate coverage. Our model assumes a 2-D network of BSs on a regular hexagonal lattice in which path loss, lognormal shadowing and Rayleigh fading affect the signal received from users. Accurate closed-form expressions are first presented for the sum-rate coverage probability and ergodic sum-rate at each point of the cooperation region. Then, for a chosen quality of user rate, the required density of BS is derived based on the minimum value of rate coverage probability in the cooperation region. The approach guarantees that the achievable rate in the entire coverage region is above a target rate with chosen probability. The formulation allows comparison between different orders of BS cooperation, quantifying the reduced required BS density from higher orders of cooperation.
How good is the Chord algorithm?
Venue: arXiv cs.DS 2013
Year: 2013

The Chord algorithm is a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as, multiobjective and parametric optimization, computational geometry, and graphics. We analyze the performance of the Chord algorithm, as compared to the optimal approximation that achieves a desired accuracy with the minimum number of points. We prove sharp upper and lower bounds, both in the worst case and average case setting.
A general method for common intervals
Venue: arXiv cs.DS 2013
Year: 2013

Given an elementary chain of vertex set V, seen as a labelling of V by the set {1, ...,n=|V|}, and another discrete structure over $V$, say a graph G, the problem of common intervals is to compute the induced subgraphs G[I], such that $I$ is an interval of [1, n] and G[I] satisfies some property Pi (as for example Pi= "being connected"). This kind of problems comes from comparative genomic in bioinformatics, mainly when the graph $G$ is a chain or a tree (Heber and Stoye 2001, Heber and Savage 2005, Bergeron et al 2008). When the family of intervals is closed under intersection, we present here the combination of two approaches, namely the idea of potential beginning developed in Uno, Yagiura 2000 and Bui-Xuan et al 2005 and the notion of generator as defined in Bergeron et al 2008. This yields a very simple generic algorithm to compute all common intervals, which gives optimal algorithms in various applications. For example in the case where $G$ is a tree, our framework yields the first linear time algorithms for the two properties: "being connected" and "being a path". In the case where $G$ is a chain, the problem is known as: common intervals of two permutations (Uno and Yagiura 2000), our algorithm provides not only the set of all common intervals but also with some easy modifications a tree structure that represents this set.
Analysis of Optimization Techniques to Improve User Response Time of Web Applications and Their Implementation for MOODLE
Venue: arXiv cs.AI 2013
Year: 2013

Analysis of seven optimization techniques grouped under three categories (hardware, back-end, and front-end) is done to study the reduction in average user response time for Modular Object Oriented Dynamic Learning Environment (Moodle), a Learning Management System which is scripted in PHP5, runs on Apache web server and utilizes MySQL database software. Before the implementation of these techniques, performance analysis of Moodle is performed for varying number of concurrent users. The results obtained for each optimization technique are then reported in a tabular format. The maximum reduction in end user response time was achieved for hardware optimization which requires Moodle server and database to be installed on solid state disk.
Detecting Fake Escrow Websites using Rich Fraud Cues and Kernel Based Methods
Venue: arXiv cs.CY 2013
Year: 2013

The ability to automatically detect fraudulent escrow websites is important in order to alleviate online auction fraud. Despite research on related topics, fake escrow website categorization has received little attention. In this study we evaluated the effectiveness of various features and techniques for detecting fake escrow websites. Our analysis included a rich set of features extracted from web page text, image, and link information. We also proposed a composite kernel tailored to represent the properties of fake websites, including content duplication and structural attributes. Experiments were conducted to assess the proposed features, techniques, and kernels on a test bed encompassing nearly 90,000 web pages derived from 410 legitimate and fake escrow sites. The combination of an extended feature set and the composite kernel attained over 98% accuracy when differentiating fake sites from real ones, using the support vector machines algorithm. The results suggest that automated web-based information systems for detecting fake escrow sites could be feasible and may be utilized as authentication mechanisms.
Evaluating the Usefulness of Sentiment Information for Focused Crawlers
Venue: arXiv cs.IR 2013
Year: 2013

Despite the prevalence of sentiment-related content on the Web, there has been limited work on focused crawlers capable of effectively collecting such content. In this study, we evaluated the efficacy of using sentiment-related information for enhanced focused crawling of opinion-rich web content regarding a particular topic. We also assessed the impact of using sentiment-labeled web graphs to further improve collection accuracy. Experimental results on a large test bed encompassing over half a million web pages revealed that focused crawlers utilizing sentiment information as well as sentiment-labeled web graphs are capable of gathering more holistic collections of opinion-related content regarding a particular topic. The results have important implications for business and marketing intelligence gathering efforts in the Web 2.0 era.
A General Stochastic Information Diffusion Model in Social Networks based on Epidemic Diseases
Venue: arXiv cs.SI 2013
Year: 2013

Social networks are an important infrastructure for information, viruses and innovations propagation. Since users behavior has influenced by other users activity, some groups of people would be made regard to similarity of users interests. On the other hand, dealing with many events in real worlds, can be justified in social networks; spreading disease is one instance of them. People manner and infection severity are more important parameters in dissemination of diseases. Both of these reasons derive, whether the diffusion leads to an epidemic or not. SIRS is a hybrid model of SIR and SIS disease models to spread contamination. A person in this model can be returned to susceptible state after it removed. According to communities which are established on the social network, we use the compartmental type of SIRS model. During this paper, a general compartmental information diffusion model would be proposed and extracted some of the beneficial parameters to analyze our model. To adapt our model to realistic behaviors, we use Markovian model, which would be helpful to create a stochastic manner of the proposed model. In the case of random model, we can calculate probabilities of transaction between states and predicting value of each state. The comparison between two mode of the model shows that, the prediction of population would be verified in each state.
Multiuser Diversity for Secrecy Communications Using Opportunistic Jammer Selection -- Secure DoF and Jammer Scaling Law
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose opportunistic jammer selection in a wireless security system for increasing the secure degrees of freedom (DoF) between a transmitter and a legitimate receiver (say, Alice and Bob). There is a jammer group consisting of $S$ jammers among which Bob selects $K$ jammers. The selected jammers transmit independent and identically distributed Gaussian signals to hinder the eavesdropper (Eve). Since the channels of Bob and Eve are independent, we can select the jammers whose jamming channels are aligned at Bob, but not at Eve. As a result, Eve cannot obtain any DoF unless it has more than $KN_j$ receive antennas, where $N_j$ is the number of jammer's transmit antenna each, and hence $KN_j$ can be regarded as defensible dimensions against Eve. For the jamming signal alignment at Bob, we propose two opportunistic jammer selection schemes and find the scaling law of the required number of jammers for target secure DoF by a geometrical interpretation of the received signals.
On the Tape-Number Problem for Deterministic Time Classes
Venue: arXiv cs.CC 2013
Year: 2013

For any time bound f, let H(f) denote the hierarchy conjecture which means that the restriction of the numbers of work tapes of deterministic Turing machines to some b generates an infinite hierarchy of proper subclasses DTIME_b(f) \subset \DTIME(f). We show that H(f) implies separations of deterministic from nondeterministic time classes. H(f) follows from the gap property, G(f), which says that there is a time-constructible bound f_2 such that f \in o(f_2) and DTIME(f)=DTIME(f_2). G(f) implies further separations. All these relationships relativize.
Structured Spectrum Allocation and User Association in Heterogeneous Cellular Networks
Venue: arXiv cs.NI 2013
Year: 2013

We study joint spectrum allocation and user association in heterogeneous cellular networks with multiple tiers of base stations. A stochastic geometric approach is applied as the basis to derive the average downlink user data rate in a closed-form expression. Then, the expression is employed as the objective function in jointly optimizing spectrum allocation and user association, which is of non-convex programming in nature. A computationally efficient Structured Spectrum Allocation and User Association (SSAUA) approach is proposed, solving the optimization problem optimally when the density of users is low, and near-optimally with a guaranteed performance bound when the density of users is high. A Surcharge Pricing Scheme (SPS) is also presented, such that the designed association bias values can be achieved in Nash equilibrium. Simulations and numerical studies are conducted to validate the accuracy and efficiency of the proposed SSAUA approach and SPS.
Identificación y Registro Catastral de Cuerpos de Agua mediante Técnicas de Procesamiento Digital de Imagenes
Venue: arXiv cs.CV 2013
Year: 2013

The effects of global climate change on Peruvian glaciers have brought about several processes of deglaciation during the last few years. The immediate effect is the change of size of lakes and rivers. Public institutions that monitor water resources currently have only recent studies which make up less than 10% of the total. The effects of climate change and the lack of updated information intensify social-economic problems related to water resources in Peru. The objective of this research is to develop a software application to automate the Cadastral Registry of Water Bodies in Peru, using techniques of digital image processing, which would provide tools for detection, record, temporal analysis and visualization of water bodies. The images used are from the satellite Landsat5, which undergo a pre-processing of calibration and correction of the satellite. Detection results are archived into a file that contains location vectors and images of the segmentated bodies of water.
An Efficient Authorship Protection Scheme for Shared Multimedia Content
Venue: arXiv cs.MM 2013
Year: 2013

Many electronic content providers today like Flickr and Google, offer space to users to publish their electronic media (e.g. photos and videos) in their cloud infrastructures, so that they can be publicly accessed. Features like including other information, such as keywords or owner information into the digital material is already offered by existing providers. Despite the useful features made available to users by such infrastructures, the authorship of the published content is not protected against various attacks such as compression. In this paper we propose a robust scheme that uses digital invisible watermarking and hashing to protect the authorship of the digital content and provide resistance against malicious manipulation of multimedia content. The scheme is enhanced by an algorithm called MMBEC, that is an extension of an established scheme MBEC, towards higher resistance.
Application of a Semi-automatic Algorithm for Identification of Molecular Components in SBML Models
Venue: arXiv cs.CE 2013
Year: 2013

Reactions forming a pathway can be rewritten by making explicit the different molecular components involved in them. A molecular component represents a biological entity (e.g. a protein) in all its states (free, bound, degraded, etc.). In this paper we show the application of a component identification algorithm to a number of real-world models to experimentally validate the approach. Components identification allows subpathways to be computed to better understand the pathway functioning.
Communication complexity of promise problems and their applications to finite automata
Venue: arXiv cs.CC 2013
Year: 2013

Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various models and modes of communication. Buhrman et al. [Buh98] proved that the exact quantum communication complexity for a promise version of the equality problem is ${\bf O}(\log {n})$ while the classical deterministic communication complexity is $n+1$ for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are ${\bf O}(\log {n})$. However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promise versions of the disjointness problem for which bigger gaps can be shown. We give a positive answer to such a question. Namely, we prove that there exists an exponential gap between quantum (even probabilistic) communication complexity and classical deterministic communication complexity of some specific versions of the disjointness problem. Klauck [Kla00] proved, for any language, that the state complexity of exact quantum/classical finite automata, which is a general model of one-way quantum finite automata, is not less than the state complexity of an equivalent one-way deterministic finite automata (1DFA). In this paper we show, using a communication complexity result, that situation may be different for some promise problems. Namely, we show for certain promise problem that the gap between the state complexity of exact one-way quantum finite automata and 1DFA can be exponential.
Tree Deletion Set has a Polynomial Kernel (but no OPT^O(1) approximation)
Venue: arXiv cs.DS 2013
Year: 2013

In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G-S is a tree. The problem is NP-complete and even NP-hard to approximate within any factor of OPT^c for any constant c. In this paper we give a O(k^4) size kernel for the Tree Deletion Set problem. To the best of our knowledge our result is the first counterexample to the "conventional wisdom" that kernelization algorithms automatically provide approximation algorithms with approximation ratio close to the size of the kernel. An appealing feature of our kernelization algorithm is a new algebraic reduction rule that we use to handle the instances on which Tree Deletion Set is hard to approximate.
An Image-Based Fluid Surface Pattern Model
Venue: arXiv cs.CV 2013
Year: 2013

This work aims at generating a model of the ocean surface and its dynamics from one or more video cameras. The idea is to model wave patterns from video as a first step towards a larger system of photogrammetric monitoring of marine conditions for use in offshore oil drilling platforms. The first part of the proposed approach consists in reducing the dimensionality of sensor data made up of the many pixels of each frame of the input video streams. This enables finding a concise number of most relevant parameters to model the temporal dataset, yielding an efficient data-driven model of the evolution of the observed surface. The second part proposes stochastic modeling to better capture the patterns embedded in the data. One can then draw samples from the final model, which are expected to simulate the behavior of previously observed flow, in order to determine conditions that match new observations. In this paper we focus on proposing and discussing the overall approach and on comparing two different techniques for dimensionality reduction in the first stage: principal component analysis and diffusion maps. Work is underway on the second stage of constructing better stochastic models of fluid surface dynamics as proposed here.
On the Feature Discovery for App Usage Prediction in Smartphones
Venue: arXiv cs.LG 2013
Year: 2013

With the increasing number of mobile Apps developed, they are now closely integrated into daily life. In this paper, we develop a framework to predict mobile Apps that are most likely to be used regarding the current device status of a smartphone. Such an Apps usage prediction framework is a crucial prerequisite for fast App launching, intelligent user experience, and power management of smartphones. By analyzing real App usage log data, we discover two kinds of features: The Explicit Feature (EF) from sensing readings of built-in sensors, and the Implicit Feature (IF) from App usage relations. The IF feature is derived by constructing the proposed App Usage Graph (abbreviated as AUG) that models App usage transitions. In light of AUG, we are able to discover usage relations among Apps. Since users may have different usage behaviors on their smartphones, we further propose one personalized feature selection algorithm. We explore minimum description length (MDL) from the training data and select those features which need less length to describe the training data. The personalized feature selection can successfully reduce the log size and the prediction time. Finally, we adopt the kNN classification model to predict Apps usage. Note that through the features selected by the proposed personalized feature selection algorithm, we only need to keep these features, which in turn reduces the prediction time and avoids the curse of dimensionality when using the kNN classifier. We conduct a comprehensive experimental study based on a real mobile App usage dataset. The results demonstrate the effectiveness of the proposed framework and show the predictive capability for App usage prediction.